|
河北科技大学 2023年攻读硕士学位研究生入学考试试题 |
[B]卷 |
||||||
|
科目名称 |
数据结构 |
科目代码 |
847 |
共 |
3 |
页 |
|
|
适用专业 |
计算机技术 |
||||||
|
注：所有试题答案一律写在答题纸上，答案写在试卷、草稿纸上一律无效。 |
|||||||
一、选择题（共30分，每题3分。答案一律写在答题纸上，否则无效。）
1. 以下与数据的存储结构有关的术语是（）。
A. 有序表 B. 有向图 C. 树 D. 链表
2. 已知一个带有表头结点的的双向循环链表L，结点结构为prev data next，其中，prev和next分别是指向其直接前驱和直接后继的指针。现要删除指针q所指的结点，正确的语句序列是（）。
A. q→next→prev=q→prev; q→prev→next=q→prev; free(q);
B. q→next→prev=q→next; q→prev→next=q→next; free(q);
C. q→next→prev=q→prev; q→prev→next=q→next; free(q);
D. q→next→prev=q→next; q→prev→next=q→prev; free(q);
3. 操作符包括‘+’，‘-’，‘*’，‘/’和‘（’，‘）’。将中缀表达式a+b-a*((c+d)/e-f)+g转换为等价的后缀表达式ab+acd+e/f-*-g+时，用栈来存放暂时还不能确定运算次序的操作符，若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是（）。
A. 11 B. 8 C. 7 D. 5
4. 将三对角矩阵M[1,…,80][1,…,80]按行优先存入一维数组A[0,…,237],M中元素M[66,65]在A中的位置K为（）。
A. 193 B. 194 C. 195 D. 197
5. 已知一颗完全二叉树的第6层（设根为第1层）有8个叶子结点，则该完全二叉树的结点个数最多是（）。
A. 39 B. 52 C. 111 D. 119
6. 对图1中所示的有向图G1进行拓扑排序，可以得到不同的拓扑序列的个数是（）。
A. 4 B. 3 C. 2 D. 1
图1 有向图G1
7. 分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（）。
A. 100，80，90，60，120，110，130 B. 100，120，110，130，80，60，90
C. 100，60，80，90，120，110，130 D. 100，80，60，90，120，130，110
8. 下列叙述中，不符合m阶B-树定义要求的是（）。
A. 根结点最多有m棵子树 B. 所有的叶子结点都在同一层上
C. 各结点内关键字均升序或降序排列 D. 叶子结点之间通过指针链接
9. 已知关键字序列{5，8，12，19，28，20，15，22}是小根堆，插入关键字3，调整后得到的小根堆是（）。
A. 3，5，12，8，28，20，15，22，19 B. 3，5，12，19，20，15，22，8，28
C. 3，8，12，5，20，15，22，28，19 D. 3，12，5，8，28，20，15，22，19
10. 已知关键字序列{11，12，13，7，8，9，23，4，5}是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（）。
A. 插入排序 B. 起泡排序 C. 选择排序 D. 归并排序
二、填空题（共30分，每题3分。答案一律写在答题纸上，否则无效。）
1. 循环队列存储在一维数组A[0,…,m]中，队头和队尾指针分别为front和rear，则入队时的操作为 。
2. 若对n阶对称矩阵A以行序为主序方式将其上三角形的元素（包括主对角线上所有元素）依次存放于一维数组B[0…(n(n+1))/2-1]中，A[1][1]存放于B [0]，则在B中确定aij（i>j）的位置k的关系为 。
3. 在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶子结点个数是 。
4. 若森林F有15条边、25个结点，则F中包含树的个数是 。
5. G是一个非连通无向图，共有28条边，则该图至少有 个顶点。
6. 设有向图G=(V，E)，顶点集V={V0，V1，V2，V3}，E={< V0，V1>，< V0，V2>，< V0，V3>，< V1，V3>}，若从顶点V0开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是 。
7. 已知一个长度为16的顺序表L，其元素按关键字有序排列，若采用折半查找法查找一个不存在的元素，则比较次数最多为 。
8. 设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶子结点，则B中右指针域为空的结点个数是 。
9. 希尔排序的组内排序采用的是 。
10. 在归并排序中，数据元素的比较次数为 。
三、(共12分，答案一律写在答题纸上，否则无效)
已知如图2所示的有向图G2，请给出
（2）图G2的邻接表。
图2 有向图G2
已知一颗二叉树的先序遍历序列为A，B，D，G，J，E，H，C，F，I，K，L；中序遍历序列为：D，J，G，B，E，H，A，C，K，I，L，F。
（2）试写出该二叉树的后序遍历序列。
（3）求该二叉树的高度H，以及二叉树中度为2，1，0的结点的个数N2，N1，N0。
五、(共12分，答案一律写在答题纸上，否则无效)
已知有6个顶点（顶点编号为V0，V1，V2,V3，V4，V5）的有向带权图G，其邻接矩阵为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中（不含邻接矩阵的主对角线元素）。
|
4 |
6 |
∞ |
∞ |
∞ |
5 |
∞ |
∞ |
∞ |
4 |
3 |
∞ |
∞ |
3 |
3 |
（2）画出图G的关键路径。
（3）计算该关键路径的长度。
六、(共12分，答案一律写在答题纸上，否则无效)
设有一组关键字（37，25，14，36，49，68，57，11），采用的哈希函数是H(key)=key%19，表长为19，采用二次探测再散列法解决冲突（di=12，-12，22，-22，32，…，±k2，k≤m/2）。
（1）画出哈希表的示意图。
（2）假设每个关键字的查找概率相等，求查找成功时的平均查找长度ASLsucc。
（3）假设每个关键字的查找概率相等，求查找不成功时的平均查找长度ASLunsucc。
七、(共12分，答案一律写在答题纸上，否则无效)
已知待排序的关键字序列为（48，62，35，77，55，14，38，98）。
（1）写出简单选择排序前两趟排序后的关键字序列，并说明该算法的稳定性。
（2）写出起泡排序前两趟排序后的关键字序列，并说明该算法的稳定性。
八、(共15分，答案一律写在答题纸上，否则无效)
设从键盘输入一个整数序列：a1, a2, a3，…，an，试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（如入栈满等）给出相应的信息。
（1）描述算法的设计思想。
（2）采用C或C++语言描述算法，必要语句之处给出简要注释。
（3）写出算法的时间复杂度。
九、(共15分，答案一律写在答题纸上，否则无效)
求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值。
（1）描述算法的设计思想。
（2）采用C或C++语言描述算法，必要语句之处给出简要注释。
（3）写出算法的时间复杂度。