数据结构自考题-6

1、数据结构自考题 -6（ 总分： 100.00 ，做题时间： 90 分钟 ）一、 单项选择题 （ 总题数： 15，分数： 30.00）1. 线性结构中的一个结点代表一个数据元素，通常要求同一线性结构的所有结点所代表的数据元素具有相 同的特性，这意味着 （ ）A. 每个结点所代表的数据元素都一样B. 每个结点所代表的数据元素包含的数据项的个数要相等C. 不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致D. 结点所代表的数据元素有同一特点（分数： 2.00 ）A.B.C. VD.解析：2. 邻接表存储结构下图的广度优先遍历算法结构类似于树的 （ ）A. 先根遍历B 后根遍历C 按层

2、遍历D 先序遍历（分数： 2.00 ）A.B.C. VD.解析：3. 设栈S和队列Q的初始状态为空，元素ei、e2、e3、e。、e：和依次通过栈S, 个元素出栈后即进入队列Q,若6个元素出列的顺序是 e2、e3、e。、e5、ei，则栈S的容量至少应该是（）A. 6 B . 4 C . 3 D . 2（分数： 2.00 ）A.B.C. VD.解析：4. 在Hash函数H（k）=k MOD m中，一般来讲，m应取（）A. 奇数B .偶数C .素数D .充分大的数（分数： 2.00 ）A.B.C. VD.解析：5. 已知用某种排序方法对关键字序列（51,35,93,24,13,68,56,42,77

3、）进行排序时，前两趟排序的结果为所采用的排序方法是（）A. 插入排序B 冒泡排序C. 快速排序D 归并排序（分数：2.00 ）A.B. VC.D.解析：解析由题目中第一趟排序的结果是将所有关键字中最大的关键字（97）放在了序列最后，第二趟排序的结果是将除97以外的所有关键字中最大的关键字放在了序列中倒数第二个位置，可知此排序方法为冒泡排序。6. 如图所示二叉树的中序遍历序列是（）A. a b c d g e f B. d f e b a g cC. d b a e f c g D. d e f b a g c（分数：2.00 ）A.B.C. VD.解析：7. 考虑下列四种排序方法，在排序过程中

4、，关键码比较的次数与记录的初始排列顺序无关的是（）A. 直接插入排序和快速排序 B .快速排序和归并排序C. 直接选择排序和归并排序 D .直接插入排序和归并排序（分数：2.00 ）A.B.B. VD.解析：8. 森林T中有4棵树，第一、二、三、四棵树的结点个数分别是m，n2，讥，口，那么当把森林 T转换成一棵二叉树后，其根结点的左孩子上有（）个结点。A. n1 B . m C .厲+压+ D .山+压+臨（分数：2.00 ）A. VB.C.D.解析：9. 循环队列用数组 A0m-1存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是 ( )A(rear-front

5、+m)MODm B rear-fomt+1C rear-fribt-1 Drear-front(分数： 2.00 )A. VB.C.D.解析：10. 在一个单链表中，已知q所指结点是p所指结点的直接前趋，若在p, q之间插入s结点，则执行()操作。A. s> next=p > next;p > next=s; B . q > next=s;s > next=p;C. p> next=s > next;s > next=p; D . p> next=s;s > next=q;(分数： 2.00 )A.B. VC.D.解析：11. 堆(H

6、eap)是()A.完全二叉树 B .线性表C .二叉排序树D .平衡二叉树(分数： 2.00 )A.B. VC.D.解析：12. 指针 p、q 和 r 依次指向某循环链表中三个相邻的结点， 交换结点 *q 和结点 *r 在表中次序的程序段是 ( )Ap>next=r; q >next=r >next; r >next=q;B p> next=r; r > next=q; q > next=r > next;Cr>next=q; q >next=r >next; p >next=r;Dr>next=q; p >n

7、ext=r; q >next=r >next;(分数： 2.00 )A. VB.C.D.解析：13. 下列说法中正确的是 （ ）A. 二叉树中任何一个结点的度都为2B. 二叉树的度为 2C. 任何一棵二叉树中至少有一个结点的度为2D. 棵二叉树的度可以小于2（分数： 2.00 ）A.B.C.D. V解析：14. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 （ ）A. 数据元素具有同一特点B. 不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C. 每个数据元素都一样D. 数据元素所包含的数据项的个数要相等分数： 2.00 )A.B. VC.D.解析

8、：15. 下列排序算法中，其时间复杂度和记录的初始排列无关的是 （ ）A.插入排序B 堆排序C 快速排序D 冒泡排序分数： 2.00 )A.B. VC.D.解析：、 填空题 （ 总题数： 10，分数： 20.00）16. 设线性表L=（ai,日2,，an）（n > 2），表中元素按值的递增顺序排列。对一个给定的值k,分别用顺序检索和二分法检索查找与 k相等的元素，比较次数分别为s和b,若检索不成功，则s和b的数量关系是1（分数： 2.00 ）填空项 1: （正确答案： s> b）解析：17. 由权值为 1,2,3,4,5,6 的六个叶子结点构成一棵哈夫曼树，则带权的路径的长度为 1

9、 解析：（分数： 2.00 ）填空项 1:正确答案： 55）18. 在二叉排序树中，其左子树中任何一个结点的关键字一定 1 其右子树的各结点的关键字。（分数： 2.00 ）填空项 1: （正确答案：小于）解析：19. 若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是 1 的（分数： 2.00 ）填空项 1: （正确答案：稳定）解析：20. 对无向图，其邻接矩阵是一个关于 1 对称的矩阵（分数： 2.00 ）填空项 1: （正确答案：主对角线）解析：21. 和二分查找相比，顺序查找的优点是除了不要求表中数据元素有序之外，对 1 结构也无特殊要求 （分数： 2.00 ）填空项 1

10、: （正确答案：存储）解析：22. 含 n 个顶点的无向连通图中至少含有 1 条边。（分数： 2.00 ）填空项 1: （正确答案： n-1 ）解析：23. 对表长为 9000 的索引顺序表进行分块查找，假设每一块的长度均为15，且以顺序查找确定块，则在各记录的查找概率均相等的情况下，其查找成功的平均查找长度为1 。（分数： 2.00 ）填空项 1: （正确答案： 308.5 ）解析：24. 查找表中主关键字指的是 ，次关键字指的是 （分数： 2.00 ）填空项 1: （正确答案：能惟一标识数据元素的数据项 不能惟一标识数据元素的数据项）解析：25. 设二维数组A10 20,5 10按行优先存

11、储，每个元素占 4个存储单元，A10,5的存储地址是1000，则 A15,10 的存储地址是 1 。（分数:2.00 ）填空项1: （正确答案：1700）解析：三、解答题（总题数：4,分数：20.00）26. 已知连通图如下:分别以邻接矩阵的邻接表实现存储，试给岀该图的邻接矩阵和邻接表，若从顶点 分别给岀一个按深度优先搜索和广度优先搜索的顶点序列。B岀发对该图进行遍历,（分数：5.00 ）正确答案：（-深度优先搜索顶点序列为：b a d f e c广度优先搜索顶点序列为：b a c e d f）解析：27. 图的邻接表的类型定义如下所示：#define MaxVertexNum 50typed

12、ef struct nodeint adjvex;struct node*next;EdgeNode;typedef structVertexType vertex;EdgeNode*firstedge;VertexNode;typedef VertexNode A djListMaxVertexNum;typedef structAdjList adjiist;int n,e;ALGraph;为便于删除和插入图的顶点的操作，可将邻接表的表头向量定义为链式结构，两种定义的存储表示实例如 下图所示，请写岀重新定义的类型说明。（分数：5.00 ）ArcNode;typedef struct VNo

13、deVertexType data; / 顶点信息struct VNode*nextVertex; / 指向下一个顶点的指针ArcNode*firstarc; /指向第一条依附该顶点的弧VNode.*AdjList;typedef structAdjList adjList;int n,e;ALGraph;)解析：28. 对于如图所示的二叉树，请画出其顺序存储结构图（分数：5.00）正确答案：（二叉树的顺序存储就是将二叉树的结点按编号存在向量B0,n中，其中B0用来存放结点T数，如果树中某些编号对应的结点不存在，则对应存储空间为“空”，根据上述规则，我们得到：解析：29. 假设有一个长度为n的

14、有序序列，在进行查找时，可以借助二叉树来进行，请结合二叉树的性质来分析 二分查找的最坏性能和平均性能。（分数：5.00）正确答案：（假设判定树的内部结点的总数为 n=2h-1。则判定树是深度为h=lg（n+1）的满二叉树，树中第 层上的结点的个数为2h-1，查找它们所需要比较的次数是 k。则在等概率下，二分查找成功时的平均查找长度为:，如果n很大，则可以用如下近似公式:lg（n+1）-1，作为二分查找成功时的平均查找长度二分查找在查找失败时所需要比较的关键字的个数不超过判定树的深度，在最坏情况下查找成功的比较次 数也不超过判定树的深度。因为判定树中度数小于2的结点只可能在最下面的两层上，所以n

15、个结点的判定树的深度和n个结点的完全二叉树的深度相同，即为lg（n+1），所以，二分查找的最坏性能和平均性能十分接近。） 解析:四、算法阅读题（总题数：3,分数：20.00）30. 请将下面的程序改成递归的过程。voide ditui(int n)int i;i=n;while(i > 1)prinft(i-);（分数：5.00 ）正确答案：(此递推过程可以改写成如下递归过程：voide dkui(int j)if(i > 1)prind(j);digui(j-l);)解析：31. 求下面算法中变量count的值：(假设n为2的乘幂，并且n >2)int Timeint nc

16、ount=0;x=2;while(x < n/2)x =2;count+;return(count)(分数：5.00 ) 正确答案：(count=log 2n)解析：假设学生成绩按学号增序存储在带头结点的单链表中，类型定义如下:typedef struct Nodeint id; /* 学号 */int score; /* 成绩 */srruct Node*next;LNode,*LinkList;阅读算法f31，并回答问题:(1)设结点结构为，成绩链表A和B如图所示，画岀执行算法f31(A,B)后A所指的链表;(2)简述算法f31的功能。void f31(LinkList A,L in

17、kList B)LinkList p,q; p=A> next; q=B> next;while(p&&q)if(p > id<Q > id) p=p> next;else if(p > id >q> id) q=q> next; else if(p > score < 60) if(q > score < 60) p> score=q > score; else p > score=60;p=p> next; q=q> next;分数： 10.00 ） 正确答案： （）解析： 正确答案：（对于表A中成绩低于60的学生，如果在表B中也有成绩记录，则将表 A中的成绩修改为其在 表B中的成绩；但若其在表 B中的成绩高于60分，则只改为60分。）解析：五、算法设计题 （ 总题数： 1，分数： 10.00）32. 设计一个双向起泡排序算法，即在排序过程中交替改变扫描方向。（分数： 10.00 ） 正确答案： ( 可通过设置一个标志位进行区分的方式来进行交替扫描，算法描述如下： Alterbubblesort(r) /* 交替扫描法起泡排序 */Reetype