- —四川最大高校综合门户网
报考专业:计算机应用 考试科目:数据结构操作系统(A) 数据结构部分 一. 单项选择题.(每题2分,共8分) 1.对由n个记录组成的文件排序,如果n较小(n50)且记录的规模较大,则采用( )排序方法节省时间. A.直接插入B.直接选择 C.快速D.堆 2.假定有K个关键字互为同义词,若用线性探
报考专业:计算机应用 考试科目:数据结构操作系统(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. 设P指向二叉树中某个S结点,结点有二个指针域lchild与rchild分别指向该结点的左,右孩子,则执行下列语句可找到结点P的中序(对放序)后继结点q(假定该后继结点存在):
q:=p.rchild; ______________
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分)
2. 找第k项. n个元素的第k项是把它们从小到大的排序后的第k个元素.如(16,12,99,95,18,87,10) 的第4项是18.假定n个整数放在数组a [1..n] 中,试写一算法,不经对整个数组排序,找到第k项.并写出此算法在最好和最坏情况下的时间复杂度. (提示,利用快速排序中的划分方法.) (16分)