北京邮电大学1999年数据结构试题
http://www.kaoyan.com 2001/8/15 考研加油站
注意事项：
1.答案一律写在答题纸上；
2.答案卷应字迹清楚、语义确切；
3.算法应说明基本思路，应对主要数据类型、变量给出说明，所写算法应结构清晰、简明易懂，应加上必要的注释；
4.算法可用（类）PASCAL语言、C语言等你所熟悉的高级语言编写，但要注明语种。
1 （10分）
选择填空
① 字符串’ababaabab’的nextval为
A．（0，1，0，1，0，4，1，0，1） B.（0，1，0，1，0，2，1，0，1，）
C．（0，1，0，1，0，0，0，1，1，） D.（0，1，0，1，0，1，0，1，1）
②广义表A=（a,b,(c,d),(e,(f,g))）,则下面式子的值为 ；
Head(Tail(Head(Tail(Tail(A)))))
A．（g） B.(d) C.c D.d
③ 输入序列为（A，B，C，D），不可能得到的输出序列有 ；
A．（A，B，C，D）? B．（D，C，B，A）? C．（A，C，D，B）? D．（C，A，B，D）
④ 散列函数有一个共同性质，即函数值应按 取其值域的每一个值；
A.最大概率 B.最小概率 C.同等概率 D.平均概率
⑤ 直接插入排序在最好情况下的时间复杂度为 。
A,O(logn) B,O(n) C,O(n*logn) D(n2)
2 （10分）
判断下列叙述是否正确
①（101，88，46，70，34，39，45，58，66，10）是堆；
② 将一棵树转换成二叉树后，根结点没有左子树；
③ 用树的前序遍历和中序遍历可以导出树的后序遍历；
④ 即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定相同；
⑤ 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离很较近。
3 （10分）
有一高个比他人都至少高出一头，找他的人都说“根本不用与别人比较，一眼就能找到他”，你认为此话正确吗？为什么？请简要描述两种求N个数中最大值的方法，并给出所需的最少比较次数。
4 （10分）
图1是用邻接表存储的图，画出此图，并写出从C点开始按深度优先遍历该图的结果。
图1? 题4图
5（10分）
下面是求无向连通图的最小代价生成 树的一种算法：
将图中所有边按权重从大到小排序为(e1,e2,…,em)
i:=1;
While (所剩边数≥顶点数)
Begin
从图中删去ei
若图不再连通，则恢复ei
i:=i+1
End
试证明这个算法所得的图是原图的最小代价生成树。
6 （10分）
已知无向图G和G’互为补图（结点相同、边不重叠、两图合起来为完全图），试证明G或G’是连通的。
7 （10分）
用序列（46，88，45，39，70，58，101，10，66，34）建立一个排序二叉树，画出该树，并求在等概率情况下查找成功的平均查找长度。
8 （10分）
写出下面程序段的运行结果。
Program Ex(Input,Output);
type
Ttt=Array[1..20] OF Integer;
Var
I,J,K,L,N:Integer;
A:Ttt;
Function P (Var A:Ttt; Var M,N:Integer):Integer;
var
X,Y,Z:Integer;
Begin
If N=1 Then?
Begin
m:=1;
p:=a[1]
End Else
Begin
X:=N;
N:=N-1;
Y:=P(A,Z,N);
N:=X;
If A[N]>=Y Then
Begin
M:=N;
P:=A[N]
End Else
Begin
M:=Z;
P:=Y
End
End
End;
Begin
Readln(N);
For I:=1 To N Do Read(A[I]);
Readln;
L:=N;
For I:=1 To L Do
Begin
K=P9A,J,N);
A[J]:=A[N];
A[N]:=K;
N:=N-1
End;
For I;=1 To L Do Write(A[I]:3);
Writeln;
End;
输入数据为：
8
6 1 8 4 3 5 2 7
9 （10分）
已知二叉树用下面的顺序结构存储，写出中序遍历该二叉树的算法。
Type
Array [1..maxn] of?
Record
Data:Char; //存结点值
Lc,Rc:Integer? //左、右孩子下标，0表示无左、右孩子
如树T=A（B（D，E），C（#，F（H，I）））存储如表1所示：
表1? 树T的存储
1 2 3 4 5 6 7 8 9
A
B
C
D
E
F
G
H
I
2
4
0
0
0
8
0
0
0
3
5
6
0
7
9
0
0
0
10 （10分）
试写出以带头结点单链表为存储结构实现简单选择排序的算法。
http://www.kaoyan.com 2001/8/15 考研加油站
注意事项：
1.答案一律写在答题纸上；
2.答案卷应字迹清楚、语义确切；
3.算法应说明基本思路，应对主要数据类型、变量给出说明，所写算法应结构清晰、简明易懂，应加上必要的注释；
4.算法可用（类）PASCAL语言、C语言等你所熟悉的高级语言编写，但要注明语种。
1 （10分）
选择填空
① 字符串’ababaabab’的nextval为
A．（0，1，0，1，0，4，1，0，1） B.（0，1，0，1，0，2，1，0，1，）
C．（0，1，0，1，0，0，0，1，1，） D.（0，1，0，1，0，1，0，1，1）
②广义表A=（a,b,(c,d),(e,(f,g))）,则下面式子的值为 ；
Head(Tail(Head(Tail(Tail(A)))))
A．（g） B.(d) C.c D.d
③ 输入序列为（A，B，C，D），不可能得到的输出序列有 ；
A．（A，B，C，D）? B．（D，C，B，A）? C．（A，C，D，B）? D．（C，A，B，D）
④ 散列函数有一个共同性质，即函数值应按 取其值域的每一个值；
A.最大概率 B.最小概率 C.同等概率 D.平均概率
⑤ 直接插入排序在最好情况下的时间复杂度为 。
A,O(logn) B,O(n) C,O(n*logn) D(n2)
2 （10分）
判断下列叙述是否正确
①（101，88，46，70，34，39，45，58，66，10）是堆；
② 将一棵树转换成二叉树后，根结点没有左子树；
③ 用树的前序遍历和中序遍历可以导出树的后序遍历；
④ 即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定相同；
⑤ 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离很较近。
3 （10分）
有一高个比他人都至少高出一头，找他的人都说“根本不用与别人比较，一眼就能找到他”，你认为此话正确吗？为什么？请简要描述两种求N个数中最大值的方法，并给出所需的最少比较次数。
4 （10分）
图1是用邻接表存储的图，画出此图，并写出从C点开始按深度优先遍历该图的结果。
图1? 题4图
5（10分）
下面是求无向连通图的最小代价生成 树的一种算法：
将图中所有边按权重从大到小排序为(e1,e2,…,em)
i:=1;
While (所剩边数≥顶点数)
Begin
从图中删去ei
若图不再连通，则恢复ei
i:=i+1
End
试证明这个算法所得的图是原图的最小代价生成树。
6 （10分）
已知无向图G和G’互为补图（结点相同、边不重叠、两图合起来为完全图），试证明G或G’是连通的。
7 （10分）
用序列（46，88，45，39，70，58，101，10，66，34）建立一个排序二叉树，画出该树，并求在等概率情况下查找成功的平均查找长度。
8 （10分）
写出下面程序段的运行结果。
Program Ex(Input,Output);
type
Ttt=Array[1..20] OF Integer;
Var
I,J,K,L,N:Integer;
A:Ttt;
Function P (Var A:Ttt; Var M,N:Integer):Integer;
var
X,Y,Z:Integer;
Begin
If N=1 Then?
Begin
m:=1;
p:=a[1]
End Else
Begin
X:=N;
N:=N-1;
Y:=P(A,Z,N);
N:=X;
If A[N]>=Y Then
Begin
M:=N;
P:=A[N]
End Else
Begin
M:=Z;
P:=Y
End
End
End;
Begin
Readln(N);
For I:=1 To N Do Read(A[I]);
Readln;
L:=N;
For I:=1 To L Do
Begin
K=P9A,J,N);
A[J]:=A[N];
A[N]:=K;
N:=N-1
End;
For I;=1 To L Do Write(A[I]:3);
Writeln;
End;
输入数据为：
8
6 1 8 4 3 5 2 7
9 （10分）
已知二叉树用下面的顺序结构存储，写出中序遍历该二叉树的算法。
Type
Array [1..maxn] of?
Record
Data:Char; //存结点值
Lc,Rc:Integer? //左、右孩子下标，0表示无左、右孩子
如树T=A（B（D，E），C（#，F（H，I）））存储如表1所示：
表1? 树T的存储
1 2 3 4 5 6 7 8 9
A
B
C
D
E
F
G
H
I
2
4
0
0
0
8
0
0
0
3
5
6
0
7
9
0
0
0
10 （10分）
试写出以带头结点单链表为存储结构实现简单选择排序的算法。
