2007年中国科技大学计算机专业基础综合(数据结构)真题试卷.doc

2007年中国科技大学计算机专业基础综合（数据结构）真题试

卷

(总分：28.00，做题时间：90分钟)

一、单项选择题(总题数：6，分数：12.00)

1.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用( )存储方式最节省运算时间。（分数：2.00） A.非循环的单链表

B.仅有头指针的单循环链表 C.非循环的双链表

D.仅有尾指针的单循环链表

2.以下与数据的存储结构无关的术语是( )。（分数：2.00） A.循环队列 B.链表 C.哈希表 D.栈

3.一个栈的输入序列为1，2，3，…，n．若输出序列的第一个元素是n，输出第i(1≤i A.不确定 B.n-i+1 C.i D.n-i

4.已知广义表LS===((a，b)，(d，e，f))，运用laead和tail函数取出LS中原子e的运算是( )。（分数：2.00） A.head(tail(LS)) B.tail(head(LS))

C.head(tail(head(tail(LS)))) D.head(tail(tail(head(LS))))

5.算术表达式a+b*(c+d／e)转为后缀表达式后为( )。（分数：2.00） A.ab+cd+e／* B.aI=)cde／+*+ C.abode／*++ D.abcode*／++

6.B+树应用在( )文件系统中。（分数：2.00） A.ISAM B.VSAM C.MAAA D.MNHA

二、简答题(总题数：6，分数：12.00)

7.设指针p指向双向链表中的一个结点，请写出在p所指结点之后插入由s所指向的结点的操作序列。（分数：2.00）

__________________________________________________________________________________________ 8.设有关键字10，20，30，40和50，依照不同的输入顺序，共可能组成多少棵不同的二叉排序树。请说明推导理由。（分数：2.00）

__________________________________________________________________________________________

9.假设二维数组A的维界为[一2…7,3…6]，当它在内存中按行存放和按列存放时，分别写出数组元素A[i，j]的地址计算公式(设每个元素占两个存储单元)。（分数：2.00）

__________________________________________________________________________________________ 10.设有一棵空的3阶B一树，一次插入关键值32，18，10，40，60，58，47，50，29，22，要求： (1)画出该3阶B-树； (2)画出在该3阶B-树中删除关键字32后的树的形态。（分数：2.00）

__________________________________________________________________________________________ 11.已知二叉树的先序遍历序列为ABCELMNDFGHK，中序遍历序列为(；BLM-NEAFDHKG，要求： (1)画出该二叉树； (2)画出与该二二叉树相对应的森林。（分数：2.00）

__________________________________________________________________________________________ 12.在含有n(n>0)个关键字的小根堆(堆顶元素最小)中，关键字最大的记录可能存储在什么位置上?说明理由。（分数：2.00）

__________________________________________________________________________________________

三、设计题(总题数：2，分数：4.00)

13.编写一个算法，输出二叉树中距给定结点最近的叶子子孙(可以是给定结点的孩子)。注：二叉树用二叉链表示。（分数：2.00）

__________________________________________________________________________________________ 14.编写克鲁斯卡尔算法求无向连通网的最小生成树，并分析你所编写的算法的时间和空间复杂度。（分数：2.00）

__________________________________________________________________________________________