还剩3页未读,继续阅读
文本内容:
数据结构(本)_202203模拟卷2
一、填空题(共10题,每题1分,共10分)
1.树是结点的有限集合,它有____________________根结点,记为T其余的结点分成为m(m0)个(1分)★标准答案
1.0个或1个;
2.互不相交;
3.父结点;
4.结点的度;
2.堆排序通常采用_______存储结构(1分)★标准答案
1.顺序;
3.队列是一种先进先出的线性表,允许插入的一端称为__________o(1分)★标准答案
1.队尾;
4.假设用循环单链表实现队列,若队列非空,且队尾指针为R,则将新结点S加入队列时,需执行下面语句O(1分)★标准答案
1.S-next=R-next;
2.R-next=S;
3.R=S;
5.在哈希存储中,装填因子a的值越大,则;a的值越小,则_0(1分)★标准答案
1.发生冲突的可能性就越大;
2.发生冲突的可能性就越小;
6.广义表((a,b),c,d)的表头是___________________________,表尾是____________________(1分)★标准答案
1.(a,b);
2.(c,d);
7.若一个算法中的语句频度之和为T(n)=100n+4nlogn+5n,则该算法的时间复杂度为________________________o(1分)★标准答案
1.0(n A2);
8.一棵高度为h的满二叉树共有_____________________________个终端结点(1分)★标准答案
1.2h-l);
9.具有n个顶点的有向图最多有_________________________条边(1分)★标准答案
1.n(n-1);
10.哈希表的查找效率主要取决于哈希表造表时选取的____________________和________________O(]分)★标准答案
1.哈希函数;
2.处理冲突的方法;
二、单选题(共10题,每题2分,共20分)
1.在一棵二叉树的二叉链表中,空指针域数的个数为()(2分)A.n B.n一1C.n+1D.2n★标准答案C
2.在具有n个单元的循环队列中,队列满时共有()个元素(2分)A.n-1B.n C.2n D.无法确定★标准答案A
3.判断线索二叉树中某结点p没有左孩子的条件是()(2分)A.p!=null B.p-lchild!=null C.p-ltag=O D.p-ltag=l★标准答案D
4.设有1000个无序元素,希望用较快速度挑选出其中前10个最大元素,采用()方法最好(2分)A.直接插入排序B.堆排序C.快速排序D.归并排序★标准答案B
5.已知一个图共有n个顶点,c条边,用邻接矩阵表示,要删除所有从第i个结点出发的边,在其时间复杂度为()(2分)A.O(n)B.O(n A2)C.O(n+e)D.O(n*e)★标准答案B
6.在顺序表(3,6,8,10,12,15,16,18,21,25,30)中,用折半法查找关键码值11,所需的关键码比较次数为()次(2分)A.2B.3C.4D.5★标准答案C
7.图的广度优先遍历类似于树的()遍历(2分)A.先序B.中序C.后序D.层次★标准答案D
8.线性表L在()情况下适用于使用链式结构实现(2分)A.需经常修改L中的结点值B.需不断对L进行删除插入C.L中含有大量的结点D.L中结点结构复杂★标准答案B
9.向一个有115个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移动()个元素(2分)A.15B.
57.5C.115D.116★标准答案B
10.顺序栈初始化的条件是栈顶指针top的值为()(2分)A.-l B.O C.MAXSIZE D.任意值★标准答案A
三、问答题(共4题,每题5分,共20分)
1.简述什么是深度(5分)★标准答案树中所有结点的度的最大值
2.简述什么是树的定义(5分)★标准答案树是结点的有限集合,它有0个或1个根结点,记为T其余的结点分成为m(m0)个有0个或1个互不相交的集合Tl,T2,Tm,每个集合乂都是树,此时结点T称为Ti的父结点,Ti称为T的子结点(lim)o一个结点的子结点个数为该结点的度
3.简述线性数据结构与非线性数据结构的区别(5分)★标准答案线性数据结构中数据的关系只有一种,每个结点元素的直接前驱和直接后继是唯一的;非线性数据结构中数据的关系可以有两种或者多种,每个结点元素的直接前驱和直接后继是不唯一的
4.在哈希表中,发生冲突的可能性与哪些因素有关?为什么?(5分)★标准答案主要与哈希函数、装填因子a有关如果用哈希函数计算的地址分布均匀,则冲突的可能性较小在哈希存储中,装填因子a的值越大,则发生冲突的可能性就越大;a的值越小,则发生冲突的可能性就越小
四、计算题(共3题,每题1()分,共3()分)
1.设关键字的输入顺序为56,20,62,17,40,100请写出生成的二叉排序树及其中序遍历序列(10分)★标准答案1740100,/中序遍历序列:17,20,40,56,62,
100.已知一个无向图的顶点集为{a,b,c,d}o其邻接矩阵如下所示a何111b1011c1101
(1)画出该图的图形;
2.2)根据邻接矩阵从顶点a出发的深度优先遍历序列和广度优先遍历序列(10分)★标准答案
3.己知某通讯系统使用8种字符,其概率分布分别为
0.06,
0.28,
0.07,
0.08,
0.14,
0.22,
0.03,
0.12,试设计其哈夫曼编码(10分)★标准答案哈夫曼不唯一,其对应编码也不唯一,写对即可得分
五、算法设计题(共2题,每题1()分,共20分)
1.设计一递归算法,在以二叉链表为存储结构的二叉树中,统计二叉树中叶子结点的个数1分★标准答案BSTNode*temp;Void ChangeBSTreeT/*T为树根指针if T-lchild!=null||T-rchild!=nulltemp=T-lchild;T-lchild=T-rchild;T-rchild=temp;count_leafT-lchild;/递归求左子树的叶子结点数count_lcafT-rchild;/递归求右子树的叶子结点数
2.设计一递归算法,实现在二又链表为存储结构的二又树中交换每个结点的左孩子和右孩子二叉链表存储结构如下typedef struct node{int data;structnode*lchild,*rchild;BitNodc»*BiTree;10分★标准答案BSTNode气emp;Void ChangeBSTreeT/叮为树根指针{if T-lchild!=null||T-rchild!=nulltemp=T-lchiId;T-lchild=T-rchild;T-rchild=temp;counl_leafT-lchild;/递归求左子树的叶子结点数count」eafT-rchild;/递归求右子树的叶子结点数。