武汉大学 1999 、2000、2001 年数据结构试题

武汉大学1999年,2001年数据结构试题!

武汉大学一九九年攻读硕士学位硕士生入学考试试题 编号：02A

一．前空（每小题2分，共16分）

1． 将中缀表达式转换成等价的后缀表达式，需要使用________这种数据结构存放表达式中的开括号和暂时不能确定计算次数的运算符。

2． 广义表L=（（），（））的长度为___________。

3． 设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶子结点，B中右指针域为空的结点有_______个。

4． 据有n个结点的无向图的生成树，有_______条边。

5． 一棵m阶的B-树，若在某结点中插入一个关键字而引起结点分裂，则此结点中原有______个关键字。

6． 设数据结构(D,R)由数据结点集合D={di|1≤1≤8}即其上的关系R{<d i-1,di>|di-1,diεD,2≤i≤8}

这个数据结构对应于___________。

7． 直接存取文件是采用_______组织起来的的文件。

8． 在外部排序中，可以使用________________产生初始归并段。

二．选择前空（只选一个答案，每小题2分，共16分）。

1． 在程序设计语言中，过程一般函数和子程序，他们都不能通过对__________的赋值来返回值。

A 值参数B变量参数C实在参数D形式参数

2． 在通常的程序设计中，应将程序的__________作为首要考虑的问题。 A执行效率B占用空间C长度D结构

3． 局部变量的作用范围为_________________。

A定义点开始至本层程序结束为止B定义点开始至程序尾C定义点开始至上层程序结束 D视具体程序才能确定

4． 下面的程序段

for i:=1 to n do

for j:=1 to i do

for k:=1 to j do

x:=x+1;

的时间复杂度为__________________。

A O(n) B O(n3|2) C O(n2) D O(n3)

5． 设单链表中指针P指着结点A之后的结点（若存在），则修改指针的操作为_____________。

A p^.link:=(p^.link)^.link B p:=p^.link

Cp:= (p^.link)^.link D p^.link:=p

6． 最佳二叉排序数的结构特点是______________。

A除最下两层可以不满外，其余都是满的

B除最下一层可以不满外，其余都是满的

C每个结点的左右子树的高度之差的绝对值不大于1

D最下层的叶子结点必须在最左边

7． 堆排序的时间复杂度和需附加的存储空间分别是_______________。

A O(n2) 和O(1) B O(nlog2n)和O(1)