2021年北京交通大学925数据结构考研真题回忆版
2021北京交通大学数据结构925研究生入学考试试题
制作人：杨路恒
一、填空题
1.一组关键字为(46，79，56，38，40，84)，则利用堆排序的方法建立大顶堆的初始堆为_
2.A=((a,b),(c,d,e),f)的表头的表尾___
3.已知模式串T=“abaaaabab”，则next函数值及nextval函数值为__
4.n个结点的无向完全图用邻接表存储的边结点
5.已知二维数组A0...6 按行优先顺序存储，若数组元素A0的存储地址为100，则每个元素占2个存储单元，则数组元素A5的存储地址
6.n个结点的森林最多有几棵树_
7.折半查找的查找成功的平均查找长度
8.从有序表中折半查找元素30时(12、18、30、43、56、78、82、95)，查找成功的比较次数为
9.有n个顶点的有向强连通图至少需要___条弧
10.完全二叉树共有2021个叶节点，则总结点
二、选择题
1.有些排序算法在每趟排序过程中都会有一个元素被放在其最终位置上，下列算法不会出现此情况的是()
A.堆排序 B.Shell排序 C.冒泡排序 D.快速排序
2.一组关键字为{46、79、56、38、40、84}，利用快速排序的方法，以第一个记录为枢轴得到的一次划分结果是()
A.38、40、46、56、79、84 B.40、38、46、79、56、84 C.40、38、46、56、79、84 D.40、38、46、84、56、79
3.有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵，所需的字节数是()
A.60 B.66 C18000 D.33
4.节点数为13的二叉树的最大深度()
A. 4 B.5 C6 D.7
5.在双向链表中在指针p所指结点之前插入结点其操作是()
A.s->prior=p->prior;s->next=p;p->next->prior=s;p->next=s;
B.p->prior=s;s->prior=p->prior;p->next->prior=s;s->next=p->next;
C.s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;
D.p->prior=s;p->next-prior=s;s->prior=p;s->next=p->next;
6.AVL树是一种平衡的二叉排序树，树中任意节点的()
A.左右子树的高度相同 B.左、右子树高度差的绝对值不超过1
7.在一棵度为3的树T中，若有20个度为3的结点，10个度为2的结点，1个度为2的结点，10个度为1的结点，则树T的叶子结点个数是()
A. 66 B.21
8.栈元素a、b、c、d、e、f依次进栈，如果6个元素出栈的顺序是b、e、d、f、c、a，则栈的容量至少是()
A.2 B.3 C.4 D.5
9.图的深度优先搜索类似于二叉树的()遍历
A.中序 B.后续 C.先序 D.后序
10.折半查找过程所对应的判定树是一棵()
A.最小生成树 B.平衡二叉树 C.完全二叉树 D.哈夫曼树
11.设哈希表长M=14，哈希函数H(KEY)=KEY%11。表中已有4个结点：ADDR(15)=4,ADDR(38)=5,ADDR(61)=6,ADDR(84)
=7,其余地址为空，如果用二次探测再散列法处理冲突，关键字为49的结点的地址是()
A.8 B.3 C.5 D.9
12.主串"abaaabc"，则INDEX("abaaabc","baaa",2)利用next值需匹配()次
A.5 B.6
13.下面关于求关键路径的说法不正确的是()
A.求关键路径是以拓扑排序为基础的
B.一个事件的最早开始时间同以该事件为尾的活动最早开始时间相同
C.一个事件的最迟开始时间为以该事件为尾的活动最迟开始时间与该活动的持续时间的差
D.关键活动一定在关键路径上
三、判断题
1.线性探测再散列法查找成功的平均查找长度与哈希函数无关()
2.AVL树左子树比右子树高1()
3.最小生成树唯一()
4.对AOV网进行拓扑排序，若当前图中虽有顶点，但不存在无前驱的顶点，则说明此有向图中存在环()
5.哈夫曼树中结点权值越大的越接近根结点()
6.层序遍历需要用到栈()
7.完全二叉树中，若一个节点没有左孩子，则它必是叶子节点()
8.哈希表的平均查找长度与处理冲突的方法无关()
9.排序的存储结构只能用顺序存储()
10.有向强连通图的连通是极大联通子图()
11.无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵()
12.在索引顺序表中，实现分块查找，在等概率查找情况时，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关()
13.栈和队列都是顺序存取的线性表，操作位置不同()
14.顺序存储的最大缺点是插入删除要移动大量元素()
四、m阶B-树插入删除
五、二叉平衡树
六、先序和后序
设先序遍历序列为abdgcefh，中序遍历序列为dgbaechf，画出该二叉树。
七、基数排序
八、关键路径
九、代码阅读题
1.链式队列
2.希尔排序
3.二叉树
给出了二叉树的孩子表示法，三个函数，分别是插入构造二叉树（按照左子树<根<右子树）、计算二叉树深度、按照右根左遍历二叉树
十、Primer算法
应用Primer算法构造最小生成树。
(1)请用自然语言描述算法过程。
(2)请写出数据结构。
(3)请用伪代码写出算法。