2022年数据结构期末试卷八.docx
精选学习资料 - - - - - - - - - 多练出技巧 巧思出硕果数据结构试卷（八）一、挑选题 30 分 1. 1. 字符串的长度是指（）；A 串中不同字符的个数 B 串中不同字母的个数C 串中所含字符的个数 D 串中不同数字的个数2. 2. 建立一个长度为 n 的有序单链表的时间复杂度为（）A On B O1 C On 2 D Olog2n 3. 3. 两个字符串相等的充要条件是（）；A 两个字符串的长度相等B 两个字符串中对应位置上的字符相等C 同时具备 A和B两个条件 D 以上答案都不对4. 4. 设某散列表的长度为 100,散列函数 Hk=k % P,就 P 通常情形下最好挑选（）；A 99 B 97 C 91 D 93 5. 5. 在二叉排序树中插入一个关键字值的平均时间复杂度为（）；A On B O1og2n C Onlog2n D On 2 6. 6. 设一个次序有序表 A1:14 中有 14 个元素, 就采纳二分法查找元素 A4 的过程中比较元素的次序为 ；A A1,A2 ,A3 ,A4 C A7,A3 ,A5 ,A4 B A1,A14,A7 ,A4 D A7 ,A5 ,A3 , A4 名师归纳总结 7.7.设一棵完全二叉树中有65 个结点,就该完全二叉树的深度为（）；第 1 页,共 5 页8.A 8 B 7 C 6 D 5 8.设一棵三叉树中有2 个度数为 1 的结点, 2 个度数为 2 的结点, 2 个度数为 3 的结9.点,就该三叉链权中有（）个度数为0 的结点；A 5 B 6 C 7 D 8 9.设无向图G 中的边的集合E=a,b,a,e,a,c,b,e,e,d,d, f,f,10.c,就从顶点a 动身进行深度优先遍历可以得到的一种顶点序列为（）；A aedfcb B acfebd C aebcfd D aedfbc 10.队列是一种（）的线性表；- - - - - - -精选学习资料 - - - - - - - - - A 先进先出多练出技巧巧思出硕果D 只能删除B 先进后出C 只能插入二、判定题 20 分 1. 1. 假如两个关键字的值不等但哈希函数值相等,就称这两个关键字为同义词；（）2. 2. 设初始记录关键字基本有序,就快速排序算法的时间复杂度为 Onlog2n；（）3. 3. 分块查找的基本思想是第一在索引表中进行查找,以便确定给定的关键字可能存在的块号,然后再在相应的块内进行次序查找；（）4. 4. 二维数组和多维数组均不是特别的线性结构；（）5. 5. 向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度；（）6. 6. 假如某个有向图的邻接表中第 i 条单链表为空,就第 i 个顶点的出度为零； （）7. 7. 非空的双向循环链表中任何结点的前驱指针均不为空；（）8. 8. 不论线性表采纳次序储备结构仍是链式储备结构,删除值为 X 的结点的时间复杂度均为 On；（）9. 9. 图的深度优先遍历算法中需要设置一个标志数组,以便区分图中的每个顶点是否被拜访过；（）10. 10. 稀疏矩阵的压缩储备可以用一个三元组表来表示稀疏矩阵中的非 0 元素；（）三、填空题 30 分 1 1 设一组初始记录关键字序列为 量的一趟希尔排序终止后的结果为49,38,65,97,76,13,27,50,就以 d=4 为增 _；2 2下面程序段的功能是实现在二叉排序树中插入一个新结点,请在下划线处填上正 确的内容；typedef struct nodeint data;struct node *lchild;struct node *rchild;bitree; void bstinsertbitree *&t,int k if t=0 _;t->data=k;t->lchild=t->rchild=0; else if t->data>k bstinsertt->lchild,k;else_; 名师归纳总结 3 3设指针变量p 指向单链表中结点A,指针变量s 指向被插入的结点X,就在结点A第 2 页,共 5 页的后面插入结点X 需要执行的语句序列：s->next=p->next; _; ；- - - - - - -精选学习资料 - - - - - - - - - 4 4 设指针变量多练出技巧巧思出硕果p 指向双向链表中的第一个head 指向双向链表中的头结点,指针变量结点,就指针变量 p 和指针变量 head 之间的关系是 p=_和 head=_（设结点中的两个指针域分别为 llink 和 rlink ）；5 5设某棵二叉树的中序遍历序列为 ABCD,后序遍历序列为 BADC,就其前序遍历序列为 _；6 6完全二叉树中第 5 层上最少有 _个结点,最多有 _个结点；7 7设有向图中不存在有向边 <Vi,Vj>,就其对应的邻接矩阵 A 中的数组元素 Aij 的值等于 _；8 8 设一组初始记录关键字序列为49,38,65,97,76,13,27,50,就第 4 趟直接挑选排序终止后的结果为 _；9 9设连通图 G 中有 n 个顶点 e 条边,就对应的最小生成树上有 _条边；1010设有一组初始记录关键字序列为 50,16,23, 68,94,70, 73,就将它们调整成初始堆只需把四、算法设计题 20 分 16 与_相互交换即可；1.1.设计一个在链式储备结构上统计二叉树中结点个数的算法；2.2.设计一个算法将无向图的邻接矩阵转为对应邻接表的算法；数据结构试卷（八）参考答案一、挑选题1C 2C 3C 4B 5B 6C 7B 8C 9A 10A 二、判定题名师归纳总结 1对2错3对4错5错第 3 页,共 5 页6对7对8对9对10对- - - - - - -精选学习资料 - - - - - - - - - 多练出技巧 巧思出硕果三、填空题1.1.49,13,27,50, 76,38,65, 97 2.2.t=bitree *mallocsizeofbitree,bstinsertt->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.设计一个在链式储备结构上统计二叉树中结点个数的算法；void countnodebitree *bt,int &count ifbt.=0 count+; countnodebt->lchild,count; countnodebt->rchild,count; 2.2.设计一个算法将无向图的邻接矩阵转为对应邻接表的算法；typedef struct int vertexm; int edgemm;gadjmatrix; typedef struct node1int info;int adjvertex; struct node1 *nextarc;glinklistnode; typedef struct node2int vertexinfo;glinklistnode *firstarc;glinkheadnode; void adjmatrixtoadjlistgadjmatrix g1 ,glinkheadnode g2 int i,j; glinklistnode *p; fori=0;i<=n-1;i+ g2i.firstarc=0; fori=0;i<=n-1;i+ forj=0;j<=n-1;j+ 名师归纳总结 - - - - - - -第 4 页,共 5 页精选学习资料 - - - - - - - - - 多练出技巧 巧思出硕果if g1.edgeij=1 p=glinklistnode *mallocsizeofglinklistnode;p->adjvertex=j; p->nextarc=gi.firstarc; gi.firstarc=p; p=glinklistnode *mallocsizeofglinklistnode;p->adjvertex=i; p->nextarc=gj.firstarc; gj.firstarc=p; 名师归纳总结 - - - - - - -第 5 页,共 5 页
