者）； 3、 从顶点 A 开始进行广度优先遍历，列出顶点的访问序列 4、 画出其最小生成树； 5、 找出图中的关节点； 五、（10 分）比较简单排序、快速排序、堆排序、归并排序和基数排序方法的平均时间复杂度、辅助存储
需求的方法和稳定性。 六、（12 分）采用二叉链表作为树的存储结构写出对树进行后根遍历的非递归算法（先简要说明算法思路，
17、设稀疏矩阵 A=[ 0 4 0 0 ]按行优先顺序存储于三元组表，则结点（3，2，-2）是三
[7 0 0 1]
[ 0 -2 0 9]
[0 0 0 0]
元组表中的第（ ）项。
18、链表不具有的特点是：（ ）
A.可随机访问任一个元素
B.插入和删除时不需要移动元素
C.不必事先估计存储空间
D.所需空间与线性表的长度正比
20、 1、构造哈希表，哈希函数为：H(KEY)=KEY%11（表长为 11），采用二次探测再散列
21、
处理冲突；
22、 2、分析哈希表的查找过程；
23、 3、说明影响哈希表平均查找长度 ASL 的主要因素。
24、四、（15 分）对下图所示的网
25、
A
1 C
8
E7
5
B
13
4
D
3
H
15
11
G
F
2
要求： 1、 写出它的邻接矩阵； 2、 从顶点 A 开始进行深度优先遍历，画出深度优先生成树（同一个结点的邻接点优先选取字母顺序最小
三、解答题（本大题共 4 个小题，每小题 5 分 共 20 分） 1、 的先序序列和中序序列分别如下，请画出该二叉树。
先序序列：ABDGJKLHCEIF 中序序列：BGJLKDHAEICF 2、 画出与下列二叉树（如图 3.1）对应的森林。 3、 求出下面图中（如图 3.2）从顶点 a 到 g 和 h 的最短路径。
A
B
C
D
E
F
G
H
I
J
K
L
M
图 3.1 二叉树
b
a
c
d
g e
h f
图 3.2 求顶点 a 到 g 和 h 的最短路经
4、 对关键字序列（10，15，80，39，43，18，20）进行起泡排序（从小到大），试问，要进行多少趟？总 的关键字比较次数是多少？
1、设将整数 1，2，3，4，5 依次进栈，出栈可以在任何时刻（只要栈不空）进行，则出栈的序列不可能
是（ ）
A.23415
பைடு நூலகம்
B.54123
C.23145
D.15432
2、一个非空广义表的表头：（ ）
A.一定是子表
B.一定是原子
C.不能是子表
D.可以是原子，也可以是子表
3、具有 n 个结点的完全二叉树的深度为：（ ）
山东理工大学 2004 年硕士研究生入学考试试题（试卷 A）
注意事项：本试题的答案必须写在规定的答题纸上，写在试题纸上不给分。 考试科目：数据结构
一、填空（每空 2 分，共 30 分）
1、 N 个顶点的有向强连通图至少有 （1） 条弧。
2、 Kruskal 算法的时间复杂度是 （2） ，它最适合于求 （2） 图的最小生成树。
15、若以[4，5，6，7，9]作为权值构造 Huffman 树，则该树的带权路径长度为：（ ）
A.67 B.69 C.71 D.70
16、在下列排序方法中，[16]方法可能出现这种情况：在最后一趟开始之前，所有的元素都不在其最终应
在的正确位置上。
A.快速排序 B.起泡排序 C.堆排序 D.插入排序
16、 4、在一份电文中共使用 a,b,c,d,e,f,六个字符，它们出现的频率依次是 0.3，0.24，0.07，
17、
0.15，0.14，0.10，画出对应的哈夫曼树并写出各个字符的前缀编码；
18、 5、比较 AVL 树和 B-树元素的插入操作有何不同；
19、三、（12 分）对关键字集合{19，01，23，14，55，68，11，82，36}
3、 广义表（（（a,b）,c）,d,(e,f)）的表头是 （4） ，表尾是 （5） 。
4、 循环队列分配的最大空间微 m,front 和 rear 分别指示队列头元素和队列尾元素，则判断队列空的
条件是 （6） ，判断队列满的条件是 （7） 。
5、 中序线索二叉树的左线索指向其 （8） 。
6、 任何一棵二叉树的叶子结点在先序，中序和后序遍历序列中的相对次序 （9） 。
11、二、简答题（每小题 6 分，共 30 分）
12、 1、什么是数据的逻辑结构和存储结构？他们有何关系？
13、 2、若元素的入栈次序是 a,b,c，写出所有可能的出栈序列。
14、 3、已知一棵度为 4 的树包含 a 个度为 1 的结点、b 个度为 2 的结点、c 个度为 3 的结点
15、
和 d 个度为 4 的结点，求其叶子结点的个数（写出推导过程）
A.链表
B.队
C.线性表
D.栈
9、若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是：（ ）
A.根结点无右子树的二叉树
B.根结点无左子树的二叉树
C.根结点可能有左子树和右子树的二叉树
D.各个结点只有一个儿子的二叉树
10、若一组记录的关键码为（45，78，56，36，40，87）则利用快速排序的方法，以第一个记录为基准（枢
址为：（ ）
A.LOC(0,0)+(J*m+i)
B.LOC(0,0)+(j*n+i)
C. LOC(0,0)+[(j-1)*n-I-1]
D. LOC(0,0)+[(j-1)*m+I-1]
7、在一个具有 n 个结点的无向图中，要连通全部结点至少需要（ ）条边。
A.n
B.n+1
C.n-1
D.n/2
8、将递归过程转化为非递归过程需用到（ ）数据结构。
7、 深度为 K 的完全二叉树至少有 （10） 个结点，叶子结点个数为 n 的非满完全二叉树的深度为
（11） 。
8、 m 阶 B-树非根的分支结点最多包含 （12） 个关键字，最少有 （13） 棵子树。
9、 在最优 K 路归并树中，只有度为 （14） 的结点。
10、 10、折半查找要求查找表采用 （15） 存储结构。
A.[log2n]+1
B. log2n +1
C. log2n
D. [log2n]
4、在一个单链表中，若 P 所指结点不是最后结点，在 P 之后 S 所指结点，则执行：（ ）
A.S->next=P->next;P->next=S;
B. P->next = S->next ; S->next =P;
C.S->next=P ; P->next=S
占 4 个字节。元素 a8247 的存储地址是（ 10 ）
8、 稀疏矩阵压缩存储后，必会失去（ 11 ）存取功能。 9、 已知在一棵含有 n 个结点的树中，只有度为 k 的分支结点和度为 0 的叶子结点，该树含有叶子结点的
数目为（ 12 ） 10、具有 n 个叶子的二叉树，每个叶子地权值为 Wi(l≦i≦n)其中带权路径长度最小的二叉树被称为（ 13 ） 11、如果只考虑有序树的情形，那么具有 7 个结点的不同形态的树共有（ 14 ）棵。 12、对于给定的 n 个元素，可以构造出的逻辑结构有集合、线性结构、（ 15 ）、（ 16 ）四种。 13、G 是一个非联通无向图，共有 28 条边，则该图至少有（ 17 ）个顶点。 14、图的遍历方式有（ 18 ）和（ 19 ）。 15、若待排序的记录总数为 n，则快速排序的总执行时间为（ 20 ）；比较次数达到树形选择排序水平，同 时又不增加存储开销的排序方法是（ 21 ）
山东理工大学 2005 年硕士研究生入学考试试题（试卷 A）
注意事项：本试题的答案必须写在规定的答题纸上，写在试题纸上不给分。 考试科目：数据结构
一、单项选择（本大题共 30 小题，每题 2 分，共 60 分）在每小题列出的四个选项（ABCD）中，只有一
个是符合题目要求的，错选、多选或未选均无分。
12、对于任何一棵二叉树，如果其终端结点树为 n，度为 2 的结点数为 m，则（ ）
A.m=n+1 B.n=m+1 C.n=2m+1 D.m=2n+1
13、m 叉树中，度为 0 的结点称为：（ ）
A.根 B.叶 C.祖先 D.子孙
14、对于一个具有 n 个结点的无向图，若采用邻接矩阵表示，则该矩阵的大小是：（ ） A.n B.n-1 C.(n+1)2 D.n2
A.0 B.3 C.2 D.5
29、将一棵有 100 个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为 1，则
编号为 49 的结点的左孩子编号为：（ ）
A.99 B.98 C.50 D.48
30、二叉树在线索化后，仍不能有效求解的问题是：（ ）
A.先序线索二叉树中求先序后继 C.中序线索二叉树中求中序前驱
D. P->next = S; S->next =P;
5、栈结构通常采用的两种存储结构是（ ）
A.散列方式和索引方式
B.顺序存储结构和链表存储结构
C.链表存储结构和数组
D.线性存储结构和非线性存储结构
6、假设每个数组元素占 1 个存储单元，二维数组 A[0..m-1][0..n-1]按列优先顺序存储，则元素 A[i][j]的地
A.9 B.10 C.11 D.12
22、一棵 m 阶非空 B-树，除根结点外，所有非终端结点最少有（ ）棵子树。
A.[m/2] B.m-1 C.m D.m+1