北京邮电大学1999硕士入学考试数据结构试题<-易考网-Easy考研网提供考研试卷专业清单-考研一站式_Easy考研网_考研资料、考研专业课试题、考研专业目录、考研参考书目、考研咨询、考研辅导报名、考研书籍、考研会员服务

北京邮电大学1999硕士入学考试数据结构试题<

http://www.ezkaoyan.com

注意事项：

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分）

试写出以带头结点单链表为存储结构实现简单选择排序的算法。