2022年数据结构期末试卷七.docx

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

1、精选学习资料 - - - - - - - - - 多练出技巧 巧思出硕果数据结构试卷（七）一、挑选题 30 分 1设某无向图有 n 个顶点,就该无向图的邻接表中有（）个表头结点；A 2n B n C n/2 D nn-1 2设无向图 G 中有 n 个顶点,就该无向图的最小生成树上有（）条边；A n B n-1 C 2n D 2n-1 3设一组初始记录关键字序列为 60,80,55,40,42,85,就以第一个关键字 45 为基准而得到的一趟快速排序结果是（）；A 40,42,60,55,80,85 C 42,40,55, 60,80,85 B 42,45,55,60,85,80 D 42,40

2、,60, 85,55,80 4（）二叉排序树可以得到一个从小到大的有序序列；A 先序遍历 B 中序遍历 C 后序遍历 D 层次遍历5设根据从上到下、从左到右的次序从 1 开头对完全二叉树进行次序编号,就编号为 i 结点的左孩子结点的编号为（）；A 2i+1 B 2i C i/2 D 2i-1 6程序段 s=i=0；do i=i+1； s=s+i； whileinext=0 C head-next=head D head.=0 8设某棵二叉树的高度为 10,就该二叉树上叶子结点最多有（）；A 20 B 256 C 512 D 1024 9设一组初始记录关键字序列为13, 18,24,35, 47

3、,50,62,83,90,115,134,就利名师归纳总结 用二分法查找关键字90 需要比较的关键字个数为（）；）；第 1 页,共 5 页A 1 B 2 C 3 D 4 10.设指针变量top 指向当前链式栈的栈顶,就删除栈顶元素的操作序列为（A top=top+1; B top=top-1; C top-next=top; D top=top-next; - - - - - - -精选学习资料 - - - - - - - - - 多练出技巧 巧思出硕果二、判定题 20 分 1不论是入队列操作仍是入栈操作,在次序储备结构上都需要考虑“溢出 ”情形；（）2当向二叉排序树中插入一个结点,就该结点肯

4、定成为叶子结点；（）3设某堆中有n 个结点,就在该堆中插入一个新结点的时间复杂度为Olog2n；（4完全二叉树中的叶子结点只可能在最终两层中显现；（）5哈夫曼树中没有度数为1 的结点；（）6对连通图进行深度优先遍历可以拜访到该图中的全部顶点；（7先序遍历一棵二叉排序树得到的结点序列不肯定是有序的序列；（）8由树转化成二叉树,该二叉树的右子树不肯定为空；（）9线性表中的全部元素都有一个前驱元素和后继元素；（）10.带权无向图的最小生成树是唯独的；（）三、填空题 30 分 1.1.设指针变量p 指向双向链表中的结点A,指针变量s 指向被插入的结点X,就在结点 A 的后面插入结点X 的操作序列为 _

5、=p；s-right=p-right ；_=s；p-right-left=s ；（设结点中的两个指针域分别为 left 和 right）；2. 2. 设完全有向图中有 n 个顶点,就该完全有向图中共有 _条有向条；设完全无向图中有 n 个顶点,就该完全无向图中共有 _条无向边；3. 3. 设关键字序列为 Kl,K2,Kn,就用挑选法建初始堆必需从第 _个元素开头进行挑选；4.4.解决散列表冲突的两种方法是_和_；5.5.设一棵三叉树中有50 个度数为 0 的结点, 21 个度数为 2 的结点, 就该二叉树中度数为 3 的结点数有 _个；名师归纳总结 6.6.高度为 h 的完全二叉树中最少有_个

6、结点,最多有_个结点；第 2 页,共 5 页7.7.设有一组初始关键字序列为24,35,12,27,18,26,就第 3 趟直接插入排序结8.束后的结果的是_ ；8.设有一组初始关键字序列为24,35,12,27,18,26,就第 3 趟简洁挑选排序结束后的结果的是_ ；- - - - - - -精选学习资料 - - - - - - - - - 9.9.多练出技巧巧思出硕果设一棵二叉树的前序序列为ABC,就有 _种不同的二叉树可以得到这种序列；10.10.下面程序段的功能是实现一趟快速排序,请在下划线处填上正确的语句；struct record int key;datatype others;

7、 void quickpassstruct record r, int s, int t, int &i int j=t; struct record x=rs; i=s; whileij while ix.key j=j-1; if ij ri=rj;i=i+1; while _ i=i+1; if ileft=p ,p-right 2.2.nn-1,nn-1/2 3.3.n/2 4.4.开放定址法,链地址法5.5.14 6.6.2h-1,2h-1 7.7.12,24,35,27,18,26 8.8.12,18,24,27,35,26 9.9.5 10.10.ij & ri.keynext=

8、0 return; forq=head; q.=0;q=q-next min=q-data; s=q; forp=q-next; p.=0;p=p-next ifminp-datamin=p-data; s=p; ifs.=qt=s-data; s-data=q-data; q-data=t; 名师归纳总结 - - - - - - -第 4 页,共 5 页精选学习资料 - - - - - - - - - 2.2.多练出技巧巧思出硕果设计在次序储备结构上实现求子串算法；void substringchar s , long start, long count, char t long i,j,length=strlens; if startlength printfThe copy position is wrong; else if start+count-1length printfToo characters to be copied; else fori=start-1,j=0; ikey=x return; else if bt-keyx levelbt-lchild,x; else levelbt-rchild,x; 名师归纳总结 - - - - - - -第 5 页,共 5 页