数据结构考试试题及答案

1数据结构考试试题及答案2009-05-1209:22计科2班期中考试题答案提交说明：写清题号，以word文本格式保存，文件名命名规则为：姓名+学号，放到ftp：//192.168.130.50的“计科2班考试”文件夹中。一．填空题（每题1分，共10分）（1）已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第0个元素的地址为address,则第i个结点的地址是（address+i*m）。（2）线性表有两种存储结构：顺序存储结构和链式存储结构，就两种存储结构完成下列填空：（顺序存储结构）存储密度较大，（链式存储结构）存储利用率较高，（顺序存储结构）可以随机存取，（链式存储结构）不可以随机存取，（链式存储结构）插入和删除操作比较方便。（3）顺序表中逻辑上相邻的元素在物理位置上（也相邻），在链表中逻辑上相邻的元素的物理位置（不一定）相邻。（4）在一个长度为n的顺序表中，在第i个元素（0=i=n）之前插入一个新元素时须向后移动（n-i+1）个元素。（5）在顺序表la的第i个元素前插入一个新元素，则有效的i值范围是（0=i=length-1）；在顺序表lb的第j个元素之后插入一个新元素，则j的有效范围是（0=j=length-1）；要删除顺序表lc的第k个元素，则k的有效范围是（0=k=length-1）。（6）设有一个空栈，现有输入序列为1，2，3，4，5，经过操作序列push,pop,push,push,pop,push,push,pop后，现在已出栈的序列是1,3,5，栈顶元素的值是4。（7）设有栈S，若线性表元素入栈顺序为1，2，3，4，得到的出栈序列为1，3，4，2，则用栈的基本运算Push,Pop描述的操作序列为push,pop,push,push,pop,push,pop,pop。（8）在队列结构中，允许插入的一端为队尾，允许删除的一端为对头。（9）在一个链队列中，若队头指针为front,队尾指针为rear，则判断该队列只有一个结点的条件Q.front-next=Q.rear。（10）设循环队列的头指针front指向队头元素，尾指针rear指向队尾元素后的一个空闲元素，队列的最大空间为MAX，则队空的标志为Q.front=Q.rear，队满的标志为(Q.rear+1)%MAX=Q.当rearfront时队列长度是Q.rear-Q.front+MAX二．判断题（每题0.5分，共5分。正确用T表示，错误用F表示）（1）栈和队列都是限制存取点的线性结构。T（2）设栈的输入序列是1，2，····n，若输出序列的第一个元素是n，则第i个输出元素是n-i+1.F（3）若一个栈的输入序列是1，2，3···n，输出序列的第一个元素是i，则第i个输出元素不确定。T（4）循环队列不会发生溢出。F（5）链队列与循环队列相比，前者不会发生溢出。T（6）直接或间接调用自身的算法就是递归算法。T（7）数据元素是数据的最小单位。F（8）数据结构是带有结构的数据元素的集合。T（9）算法的时间复杂度是算法执行时间的绝对度量。F（10）算法的正确性是指算法不存在错误。F三．简答题（满分5分）（1）假设我们要从线性表中删除一个数据元素b，如图1-1所示，已知p为其单链表存储结构中指向结点a的指针。写出删除结点b后，修改指针的语句。（此题2分）ab2cpp→next=p→next→next;图1-1（2）编制一程序（可用伪码描述，写出解题思路可酌情得分）：对于输入的任意一个非负十进制整数，输出与其等值的16进制数。（此题3分）voidconversion(){InitStack(S);scanf(“%d”N);while(N){Push(S,N%16);N=N/16;}while(!StackEmpty(s)){Pop(S,e);Printf(“%d”,e);}}输入一个十进制数N，使N对16求余，构造一个空栈，并将余数入栈，再将N除16的值赋给N；依次循还，再将栈中元素进行出栈操作即可。单项选择题1．用单链表方式存储的线性表，存储每个结点需要两个域，一个是数据域，另一个是（.B）。A.当前结点的所在地址B.后继结点的所在地址C.空指针域D.空闲域2．在一个单链表中，若p所指结点不是最后结点，则删除p所指结点的后继结点的正确操作是(C)A.p=p-nextB.p-next=p-nextC.p-next=p-next-nextD.p-next=p3．栈和队列(C?应该是在顶端进行取数据的操作)A.共同之处在于二者都是先进先出的特殊的线性表B.共同之处在于二者都是先进后出的特殊的线性表C.共同之处在于二者都只允许在顶端执行删除操作D.没有共同之处4．设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为（D）A．front=front+1B.front=(front+1)%mC．rear=(rear+1)%mD.front=(front+1)%(m+1)5.已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=〃SCIENCESTUDY〃，则调用函数Scopy(P,Sub(S,1,7))后得到(A)3A.P=〃SCIENCE〃B.P=〃STUDY〃C.S=〃SCIENCE〃D.S=〃STUDY〃6．在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是(C)A.快速排序B.堆排序C.归并排序D.基数排序7．图的邻接表如下所示，从顶点V1出发采用深度优先搜索法遍历该图，则可能的顶点序列是()A.V1V2V3V4V5B.V1V2V3V5V4C.V1V4V3V5V2D.V1V3V4V5V28．下列排序方法中，属于不稳定的排序方法是(A)A.直接插入排序法B.冒泡排序法C.基数排序法D.归并排序法数据结构考试试题及答案1一、判断下列叙述的对错。（1）线性表的逻辑顺序与物理顺序总是一致的。（2）线性表的顺序存储表示优于链式存储表示。（3）线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。（4）二维数组是其数组元素为线性表的线性表。（5）每种数据结构都应具备三种基本运算：插入、删除和搜索。二、设单链表中结点的结构为typedefstructnode{file://链表结点定义ElemTypedata；file://数据structnode*Link；file://结点后继指针}ListNode；（1）已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列哪一个操作？A.s-link=p；p-link=s；B.s-link=p-link；p-link=s；C.s-link=p-link；p=s；D.p-link=s；s-link=p；（2）非空的循环单链表first的尾结点（由p所指向）满足：A.p-link==NULL；B.p==NULL；C.p-link==first；D.p==first；三、设有一个顺序栈S，元素s1，s2，s3，s4，s5，s6依次进栈，如果6个元素的出栈顺序为s2，s3，s4，s6，s5，s1，则顺序栈的容量至少应为多少？四、一棵具有n个结点的理想平衡二叉树（即除离根最远的最底层外其他各层都是满的，最底层有若干结4点）有多少层？若设根结点在第0层，则树的高度h如何用n来表示（注意n可能为0）？五、从供选择的答案中选择与下面有关图的叙述中各括号相匹配的词句，将其编号填入相应的括号内。（1）对于一个具有n个结点和e条边的无向图，若采用邻接表表示，则顶点表的大小为（A），所有边链表中边结点的总数为（B）。（2）采用邻接表存储的图的深度优先遍历算法类似于树的（C）。（3）采用邻接表存储的图的广度优先遍历算法类似于树的（D）。（4）判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（E）。供选择的答案A：①n②n+1③n-1④n+eB：①e/2②e③2e④n+eC~D：①中根遍历②先根遍历③后根遍历④按层次遍历E：①求关键路径的方法②求最短路径的Dijkstra方法③深度优先遍历算法④广度优先遍历算法六、填空题（1）在用于表示有向图的邻接矩阵中，对第i行的元素进行累加，可得到第i个顶点的（①）度，而对第j列的元素进行累加，可得到第j个顶点的（②）度。（2）一个连通图的生成树是该图的（③）连通子图。若这个连通图有n个顶点，则它的生成树有（④）条边。（3）给定序列{100，86，48，73，35，39，42，57，66，21}，按堆结构的定义，则它一定（⑤）堆。（4）在进行直接插入排序时，其数据比较次数与数据的初始排列（⑥）关；而在进行直接选择排序时，其数据比较次数与数据的初始排列（⑦）关。（5）利用关键码分别为10，20，30，40的四个结点，能构造出（⑧）种不同的二叉搜索树。七、设带表头结点的双向链表的定义为typedefintElemType；typedefstructdnode{file://双向链表结点定义ElemTypedata；file://数据structdnode*lLink，*rLink；file://结点前驱与后继指针DblNode；typedefDblNode*DblList；file://双向链表试设计一个算法，改造一个带表头结点的双向链表，所有结点的原有次序保持在各个结点的右链域rLink中，并利用左链域lLink把所有结点按照其值从小到大的顺序连接起来。八、设有一个关键码的输入序列{55，31，11，37，46，73，63，02，07，（1）从空树开始构造平衡二叉搜索树，画出每加入一个新结点时二叉树的形态。若发生不平衡，指明需做的平衡旋转的类型及平衡旋转的结果。（2）计算该平衡二叉搜索树在等概率下的查找成功的平均查找长度和查找不成功的平均查找长度。5九、下面是求连通网络的最小生成树的Prim算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。constintMaxInt=INT_MAX；file://INT_MAX的值在中constintn=6；file://图的顶点数，应由用户定义typedefintAdjMatrix[n[n；file://用二维数组作为邻接矩阵表示typedefstructfile://生成树的边结点intfromVex，toVex；file://边的起点与终点intweight；file://边上的权值TreeEdgeNode；typedefTreeEdgeNodeMST[n-1；file://最小生成树定义voidPrimMST（AdjMatrixG，MSTT，intrt）{file://从顶点rt出发构造图G的最小生成树T，rt成为树的根结点TreeEdgeNodee；inti，k=0，min，minpos，v；for（i=0；in；i++）file://初始化最小生成树Tif（i！=rt）{T[k.fromVex=rt；T[k.toVex=I；T[k++.weight=G[rt；}for（k=0；kn-1；k++）{file://依次求MST的候选边min=MaxInt；for（i=k；in-1；i++）file://遍历当前候选边集合if（T.weightmin）file://选具有最小权值的候选边{min=T.weight；minpos=i；}if（min==MaxInt）file://图不连通，出错处理{cerr《“Graphisdisconnected！”《endl；exit（1）；}e=T[minpos；T[minpos=T[k；T[k=e；v=T[k.toVex；for（i=k+1；in-1；i++）file://修改候选边集合if（G[v[T.toVexT.weight）T.weight=G[v[T.toVex；T.fromVex=v；参考答案一、（1）错（2）错（3