数据结构考试试题及答案

1、数据结构考试试题及答案2009-05-12 09: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 ）；在顺序表l

2、b的第j个元素之后插入一个新元素，则j的有效范围是（ 0 = j=length-1 ）；要删除顺序表lc的第k个元素，则k的有效范围是（ 0 =knext=Q.rear 。（10）设循环队列的头指针 front 指向队头元素，尾指针 rear 指向队尾元素后的一个空闲元素，队列的最大空间为 MAX ，则队空的标志为Q.front=Q.rear ，队满的标志为 (Q.rear+1)%MAX=Q. 当 rearnext B. p-next=p-nextC. p-next=p-next-next D. p-next=p3栈和队列( C?应该是在顶端进行取数据的操作 )A.共同之处在于二者都是先进先出的特殊的线性表B.共同之处在于二者都是先进后出的特殊的线性表C.共同之处在于二者都只允许在顶端执行删除操作D.没有共同之处4设数组Data0.m作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为（D ） Afront=front+1 B. front=(front+1)%mCrear=(rear+1)%m D. front=(front+1)%(m+1)5

3、. 已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=SCIENCESTUDY，则调用函数Scopy(P,Sub(S,1,7)后得到(A )A.P=SCIENCE B.P=STUDYC.S=SCIENCE D.S=STUDY6在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是(C )A.快速排序 B.堆排序C.归并排序 D.基数排序7图的邻接表如下所示，从顶点V1出发采用深度优先搜索法遍历该图，则可能的顶点序列是( ) A.V1V2V3V4V5 B.V1V2V3V5V4C.V1V4V3V5V2 D.V1V3V4V5V28下列排序方法中，属于不稳定的排序方法是(A )A.直接插入排序法 B.冒泡排序法C.基数排序法 D.归并排序法 数据结构考试试题及答案1一、判断下列叙述的对错。（1）线性表的逻辑顺序与物理顺序总是一致的。（2）线性表的顺序存储表示优于链式存储表示。（3）线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。（4）二维数组是其数组元素为线性表的线性表。（5）

4、每种数据结构都应具备三种基本运算：插入、删除和搜索。二、设单链表中结点的结构为typedef struct node file:/链表结点定义ElemType data； file:/数据struct node * 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个结点的理想平衡二叉树（即除离根最远的最底层外其他各

5、层都是满的，最底层有若干结点）有多少层？若设根结点在第0层，则树的高度h如何用n来表示（注意n可能为0）？五、从供选择的答案中选择与下面有关图的叙述中各括号相匹配的词句，将其编号填入相应的括号内。（1）对于一个具有n个结点和e条边的无向图，若采用邻接表表示，则顶点表的大小为（A），所有边链表中边结点的总数为（B）。（2）采用邻接表存储的图的深度优先遍历算法类似于树的（C）。（3）采用邻接表存储的图的广度优先遍历算法类似于树的（D）。（4）判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（E）。供选择的答案A：nn+1n-1n+eB：e/2e2en+eCD：中根遍历先根遍历后根遍历按层次遍历E：求关键路径的方法求最短路径的Dijkstra方法深度优先遍历算法广度优先遍历算法六、填空题（1）在用于表示有向图的邻接矩阵中，对第i行的元素进行累加，可得到第i个顶点的（）度，而对第j列的元素进行累加，可得到第j个顶点的（）度。（2）一个连通图的生成树是该图的（）连通子图。若这个连通图有n个顶点，则它的生成树有（）条边。（3）给定序列100， 86， 48， 73， 35， 39，

6、42， 57， 66， 21，按堆结构的定义，则它一定（）堆。（4）在进行直接插入排序时，其数据比较次数与数据的初始排列（）关；而在进行直接选择排序时，其数据比较次数与数据的初始排列（）关。（5）利用关键码分别为10， 20， 30， 40的四个结点，能构造出（）种不同的二叉搜索树。七、设带表头结点的双向链表的定义为typedef int ElemType；typedef struct dnode file:/双向链表结点定义ElemType data； file:/数据struct dnode * lLink， * rLink； file:/结点前驱与后继指针DblNode；typedef DblNode * DblList； file:/双向链表试设计一个算法，改造一个带表头结点的双向链表，所有结点的原有次序保持在各个结点的右链域rLink中，并利用左链域lLink把所有结点按照其值从小到大的顺序连接起来。八、设有一个关键码的输入序列 55， 31， 11， 37， 46， 73， 63， 02， 07 ，（1）从空树开始构造平衡二叉搜索树，画出每加入一个新结点时二叉树的形态。若发生不平衡，指明需做的平衡旋转的类型及平衡旋转的结果。（2）计算该平衡二叉搜索树在等概率下的查找成功的平均查找长度和查找不成功的平均查找长度。九、下面是求连通网络的最小生成树的Prim算法的实现，中间有5个地方缺失，请阅读程序

《数据结构考试试题及答案》由会员cl****1分享，可在线阅读，更多相关《数据结构考试试题及答案》请在金锄头文库上搜索。