2022年数据结构期末试卷八 .pdf

《2022年数据结构期末试卷八 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构期末试卷八 .pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、多练出技巧巧思出硕果数据结构试卷（八）一、选择题 (30 分) 1.1.字符串的长度是指（） 。(A) 串中不同字符的个数(B) 串中不同字母的个数(C) 串中所含字符的个数(D) 串中不同数字的个数2.2.建立一个长度为n 的有序单链表的时间复杂度为（）(A) O(n) (B) O(1) (C) O(n2) (D) O(log2n) 3.3.两个字符串相等的充要条件是（） 。(A) 两个字符串的长度相等(B) 两个字符串中对应位置上的字符相等(C) 同时具备 (A)和(B)两个条件(D) 以上答案都不对4.4.设某散列表的长度为100，散列函数H(k)=k % P ，则 P通常情况下最好选择

2、（） 。(A) 99 (B) 97 (C) 91 (D) 93 5.5.在二叉排序树中插入一个关键字值的平均时间复杂度为（） 。(A) O(n) (B) O(1og2n) (C) O(nlog2n) (D) O(n2) 6.6.设一个顺序有序表A1:14 中有 14 个元素， 则采用二分法查找元素A4的过程中比较元素的顺序为( )。(A) A1，A2，A3，A4 (B) A1，A14，A7，A4 (C) A7，A3，A5，A4 (D) A7，A5 ，A3， A4 7.7.设一棵完全二叉树中有65 个结点，则该完全二叉树的深度为（） 。(A) 8 (B) 7 (C) 6 (D) 5 8.8.设一

3、棵三叉树中有2 个度数为1 的结点， 2 个度数为2 的结点， 2 个度数为 3 的结点，则该三叉链权中有（）个度数为0 的结点。(A) 5 (B) 6 (C) 7 (D) 8 9.9.设无向图G 中的边的集合E=(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d， f)，(f，c)，则从顶点a 出发进行深度优先遍历可以得到的一种顶点序列为（） 。(A) aedfcb (B) acfebd (C) aebcfd (D) aedfbc 10.10.队列是一种（）的线性表。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 5 页

4、多练出技巧巧思出硕果(A) 先进先出(B) 先进后出(C) 只能插入(D) 只能删除二、判断题 (20 分) 1.1.如果两个关键字的值不等但哈希函数值相等，则称这两个关键字为同义词。（）2.2.设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。 （）3.3.分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。（）4.4.二维数组和多维数组均不是特殊的线性结构。（）5.5.向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。（）6.6.如果某个有向图的邻接表中第i 条单链表为空，则第i 个顶点的出度

5、为零。 （）7.7.非空的双向循环链表中任何结点的前驱指针均不为空。（）8.8.不论线性表采用顺序存储结构还是链式存储结构，删除值为X 的结点的时间复杂度均为 O(n)。 （）9.9.图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问过。（）10.10.稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0 元素。 （）三、填空题 (30 分) 1 1设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则以 d=4 为增量的一趟希尔排序结束后的结果为_。2 2下面程序段的功能是实现在二叉排序树中插入一个新结点，请在下划线处填上正确的内容。

6、typedef struct nodeint data;struct node *lchild;struct node *rchild;bitree; void bstinsert(bitree *&t,int k) if (t=0 ) _;t-data=k;t-lchild=t-rchild=0; else if (t-datak) bstinsert(t-lchild,k);else_; 3 3设指针变量p 指向单链表中结点A，指针变量s 指向被插入的结点X，则在结点A的后面插入结点X 需要执行的语句序列：s-next=p-next; _; 。精选学习资料 - - - - - - - -

7、- 名师归纳总结 - - - - - - -第 2 页，共 5 页多练出技巧巧思出硕果4 4设指针变量head 指向双向链表中的头结点，指针变量p 指向双向链表中的第一个结点，则指针变量p 和指针变量head 之间的关系是p=_和 head=_（设结点中的两个指针域分别为llink 和 rlink） 。5 5设某棵二叉树的中序遍历序列为ABCD ，后序遍历序列为BADC，则其前序遍历序列为 _。6 6完全二叉树中第5 层上最少有 _个结点，最多有_个结点。7 7设有向图中不存在有向边，则其对应的邻接矩阵A 中的数组元素Aij 的值等于 _。8 8设一组初始记录关键字序列为(49，38，65，9

8、7，76，13，27，50)，则第 4 趟直接选择排序结束后的结果为_。9 9设连通图 G 中有 n 个顶点 e 条边，则对应的最小生成树上有_条边。1010设有一组初始记录关键字序列为(50，16，23， 68，94，70， 73)，则将它们调整成初始堆只需把16 与_相互交换即可。四、算法设计题(20 分) 1.1.设计一个在链式存储结构上统计二叉树中结点个数的算法。2.2.设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。数据结构试卷（八）参考答案一、选择题1C 2C 3C 4B 5B 6C 7B 8C 9A 10A 二、判断题1对2错3对4错5错6对7对8对9对10对精选学习资料 -

9、 - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 5 页多练出技巧巧思出硕果三、填空题1.1.(49，13，27，50， 76，38，65， 97) 2.2.t=(bitree *)malloc(sizeof(bitree)，bstinsert(t-rchild,k) 3.3.p-next=s 4.4.head-rlink ，p-llink 5.5.CABD 6.6.1，16 7.7.0 8.8.(13，27，38，50， 76，49，65， 97) 9.9.n-1 10.10.50 四、算法设计题1.1.设计一个在链式存储结构上统计二叉树中结点个数的算

10、法。void countnode(bitree *bt,int &count) if(bt!=0) count+; countnode(bt-lchild,count); countnode(bt-rchild,count); 2.2.设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。typedef struct int vertexm; int edgemm;gadjmatrix; typedef struct node1int info;int adjvertex; struct node1 *nextarc;glinklistnode; typedef struct node2int

11、vertexinfo;glinklistnode *firstarc;glinkheadnode; void adjmatrixtoadjlist(gadjmatrix g1 ,glinkheadnode g2 ) int i,j; glinklistnode *p; for(i=0;i=n-1;i+) g2i.firstarc=0; for(i=0;i=n-1;i+) for(j=0;jadjvertex=j; p-nextarc=gi.firstarc; gi.firstarc=p; p=(glinklistnode *)malloc(sizeof(glinklistnode);p-adjvertex=i; p-nextarc=gj.firstarc; gj.firstarc=p; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 5 页