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

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

1、精选学习资料 - - - - - - - - - 多练出技巧 巧思出硕果数据结构试卷（六）一、挑选题 30 分 1 设一组权值集合 W=2,3,4,5,6,就由该权值集合构造的哈夫曼树中带权路径长度之和为（）；A 20 B 30 C 40 D 45 2执行一趟快速排序能够得到的序列是（）；A 41,12, 34,45,27 55 72 ,63 B 45,34, 12,41 55 72 ,63,27 C 63,12, 34,45,27 55 41 ,72 D 12,27,45,41 55 34 ,63,72 名师归纳总结 3设一条单链表的头指针变量为head 且该链表没有头结点,就其判空条件是（

2、）；）；第 1 页,共 5 页A head=0 B head-next=0 C head-next=head D head.=0 4时间复杂度不受数据初始状态影响而恒为Onlog2n的是（）；A 堆排序B 冒泡排序C 希尔排序D 快速排序5设二叉树的先序遍历序列和后序遍历序列正好相反,就该二叉树满意的条件是（A 空或只有一个结点B 高度等于其结点数C 任一结点无左孩子D 任一结点无右孩子6一趟排序终止后不肯定能够选出一个元素放在其最终位置上的是（）；A 堆排序B 冒泡排序C 快速排序D 希尔排序7设某棵三叉树中有40 个结点,就该三叉树的最小高度为（）；A 3 B 4 C 5 D 6 8次序查

3、找不论在次序线性表中仍是在链式线性表中的时间复杂度为（）；A On B On 2 C On 1/2 D O1og2n 9二路归并排序的时间复杂度为（）；A On B On 2 C Onlog2n D O1og2n 10. 深度为 k 的完全二叉树中最少有（）个结点；- - - - - - -精选学习资料 - - - - - - - - - A 2 k-1-1 k-1 B 2多练出技巧巧思出硕果D 2 k-1 C 2 k-1+1 11.设指针变量 front 表示链式队列的队头指针,指针变量 rear 表示链式队列的队尾指针,指针变量 s 指向将要入队列的结点 X,就入队列的操作序列为（）；A

4、front-next=s ；front=s ；C rear-next=s；rear=s；B s-next=rear；rear=s；D s-next=front ；front=s ；12.设某无向图中有n 个顶点 e 条边,就建立该图邻接表的时间复杂度为（）；）；）；A On+e B On 2 C One D On3 13.设某哈夫曼树中有199 个结点,就该哈夫曼树中有（）个叶子结点；A 99 B 100 C 101 D 102 14.设二叉排序树上有n 个结点,就在二叉排序树上查找结点的平均时间复杂度为（A On B On 2 C Onlog2n D O1og2n 15.设用邻接矩阵A 表示

5、有向图G 的储备结构,就有向图G 中顶点 i 的入度为（A 第 i 行非 0 元素的个数之和B 第 i 列非 0 元素的个数之和C 第 i 行 0 元素的个数之和 D 第 i 列 0 元素的个数之和二、判定题 20 分 1调用一次深度优先遍历可以拜访到图中的全部顶点；（）（）2分块查找的平均查找长度不仅与索引表的长度有关,而且与块的长度有关；3冒泡排序在初始关键字序列为逆序的情形下执行的交换次数最多；（4满二叉树肯定是完全二叉树,完全二叉树不肯定是满二叉树；（）（）5设一棵二叉树的先序序列和后序序列,就能够唯独确定出该二叉树的外形；6层次遍历初始堆可以得到一个有序的序列；（）7设一棵树T 可以

6、转化成二叉树BT,就二叉树BT中肯定没有右子树； （8线性表的次序储备结构比链式储备结构更好；（）9中序遍历二叉排序树可以得到一个有序的序列；（）10.快速排序是排序算法中平均性能最好的一种排序；（）三、填空题 30 分 名师归纳总结 - - - - - - -第 2 页,共 5 页精选学习资料 - - - - - - - - - 多练出技巧 巧思出硕果1fori=1 ,t=1,s=0；i=n；i+ t=t*i ； s=s+t；的时间复杂度为 _；2设指针变量 p 指向单链表中结点 A,指针变量 s 指向被插入的新结点 X,就进行插入操作的语句序列为 _（设结点的指针域为 next ）；3设有

7、向图 G 的二元组形式表示为 G =（D,R）,D=1,2,3,4,5,R=r,r=, ,就给出该图的一种拓扑排序序列 _；4设无向图 G 中有 n 个顶点,就该无向图中每个顶点的度数最多是 _；5设二叉树中度数为 0 的结点数为 50,度数为 1 的结点数为 30,就该二叉树中总共有 _个结点数；6设 F 和 R 分别表示次序循环队列的头指针和尾指针,就判定该循环队列为空的条件为_；7设二叉树中结点的两个指针域分别为 lchild 和 rchild,就判定指针变量 p 所指向的结点为叶子结点的条件是 _ ；8简洁挑选排序和直接插入排序算法的平均时间复杂度为 _；9快速排序算法的空间复杂度平均

8、情形下为 _,最坏的情形下为 _；10.散列表中解决冲突的两种方法是四、算法设计题 20 分 _和_；设计在次序有序表中实现二分查找的算法；设计判定二叉树是否为二叉排序树的算法；在链式储备结构上设计直接插入排序算法数据结构试卷（六）参考答案一、挑选题1D 2A 3A 4A 5 D 6D 7B 8A 9C 10B 11C 12A 13B 14D 15B 二、判定题名师归纳总结 - - - - - - -第 3 页,共 5 页精选学习资料 - - - - - - - - - 1错2对3对4对多练出技巧巧思出硕果5错6错7对8错9对10对三、填空题1.1.On 2.2.s-next=p-next;

9、p-next=s 3.3.1,3,2,4,5 4.4.n-1 5.5.129 6.6.F=R 7.7.p-lchild=0&p-rchild=0 8.8.On2 9.9.Onlog2n, On 10.10.开放定址法,链地址法四、算法设计题1.1.设计在次序有序表中实现二分查找的算法；struct record int key; int others; int bisearchstruct record r , int k int low=0,mid,high=n-1; whilelowk high=mid-1; else low=mid+1; return0; 名师归纳总结 - - - -

10、- - -第 4 页,共 5 页精选学习资料 - - - - - - - - - 2.2.多练出技巧巧思出硕果设计判定二叉树是否为二叉排序树的算法；int minnum=-32768,flag=1; typedef struct nodeint key; struct node *lchild,*rchild;bitree; void inorderbitree *bt if bt.=0 inorderbt-lchild; ifminnumbt-keyflag=0; minnum=bt-key;inorderbt-rchild; 3.3.在链式储备结构上设计直接插入排序算法void straightinsertsortlklist *&head lklist *s,*p,*q; int t; if head=0 | head-next=0 return; else forq=head,p=head-next;p.=0;p=q-next fors=head;s.=q-next;s=s-next if s-datap-data break; ifs=q-nextq=p; elseq-next=p-next; p-next=s-next; s-next=p; t=p-data;p-data=s-data;s-data=t; 名师归纳总结 - - - - - - -第 5 页,共 5 页