当前位置：问答库＞考研试题

南昌大学2003年攻读硕士学位研究生

入 学 考 试 试 题

报考专业:计算机应用 考试科目:数据结构操作系统(A) 数据结构部分

一. 单项选择题.(每题2分, 共8分)

1. 对由n 个记录组成的文件排序, 如果n 较小(n<50)且记录的规模较大, 则采用( )排序方法节省时间.

A.直接插入 B.直接选择 C. 快速 D.堆

2. 假定有K 个关键字互为同义词, 若用线性探测法把这些同义词存入散列表中, 至少要进行( )次探测.

A. K B. K2(K的平方) C.1/2K(K-1) D.1/2K(K+1)

3. 二维数组a[0…8, 1…10]按行存放时元素a[8, 5]的起始地址与按列存放时元素( )的起始地址相同.

A. a[8,5] B. a[3,10] C. a[5,8] D. a[0, 9]

4. 有6个元素按6,5,4,3,2,1的顺序进栈, 下列( )不是合法的出栈序列.

A. 5,4,3,6,1,2 B. 4,5,3,1,2,6 C. 3,4,6,5,2,1 D. 2,3,4,1,5,6

二. 填空题(每题3分, 共12分)

1. (假定该后继结点存在):↑的中序(对放序) 后继结点q ↑设P 指向二叉树中某个S 结点, 结点有二个指针域lchild 与rchild 分别指向该结点的左, 右孩子, 则执行下列语句可找到结点P

.rchild; ______________↑ q:=p

2. 高度为6的AVL 树至少有________结点.(设空二叉树高度为0)

3. 用数组Q[0..n-1]存放循环队列, f, r分别为队头, 队尾指针, 则队列长度的计算公式是__________. 队列长度的最大值是____________.

4. 高度为h 的完全二叉树上至少有_______个结点, 至多有_______个结点.

三. 简答与画图题(共24分)

1. 设二叉树的后根序列为HDEBIFGCA, 中根序列是DHBEAIFCG, 画出此二叉树和它所对应的森林.(9分)

2. 顺序查找, 二分法查找和分块查找三种方法对查找表中元素各有什么要求? 平均的查找长度各是多少?(假设查找表的长度为n.) (9分)

3. 图的广度遍历算法中既可以在一个点入队时对其访问, 也可以在顶点出队时对其访问, 请问前一种方法有何优点? 后一种方法可能产生什么问题? 并以下图为例说明.(6分)

V0

V1 V2………Vn

Vn+1

四. 算法题.(共31分)

1. 清除重复结点. 单链表中数据域的值相同的结点称为重复结点. 如线性表(2,1,1, 3,2,1,) 清除重复结点后为(2,1, 3).试用C 语言写一函数清除单链表head 中的重复结点, 并指出每个工作指针的作用.( 15分)