青岛大学04数据结构

青岛大学2004年硕士研究生入学考试试题科目代码：407 科目名称：数据结构（共5页）请考生写明题号，将答案全部答在答题纸上，答在试卷上无效。

考试时间180分钟。

一、单项选择题（本大题共15小题，每小题3分，共45分）在每小题列出的四个选项中，只有一个是符合题目要求的。

错选或未选均无分。

1. 一个算法的时间复杂度为（3n2+2nlog2n+4n-7）/（10n），其数量级为【】A. O (3n2)B. O (2nlog2n)C. O (3n/10)D. O（n）2. 铁道进行火车调度时，总是把站台设成栈式站台，如果火车进站序列为123456，下面哪种出站序列不能得到：【】A. 325641B. 165432C. 435612D. 1354263. 设有广义表D(a, b, D)，其长度为：【】A. 2B. 3C. ∞D. 不确定4. 某二叉树的中序遍历序列为CBEDAHGIJF，后序遍历序列为CEDBHJIGFA，则前序序列为【】A. ABCDEFGHIJB. ABCDGHIJEFC. ACDEBHJIGFD. ACBDEFGHIJ5. 就平均时间而言，什么排序方法最好。

【】A. 希尔排序B. 快速排序C. 堆排序D. 归并排序6. 线性表若采用链式存储，所有的存储单元的地址【】A. 可连续可不连续B. 一定连续C. 一定不连续D. 以上都不对7. 对长度为10的有序表进行二分查找（折半查找），在等概率的情况下，查找成功的平均查找长度（ASL）为【】A. 3.2B. 1.7C. 2.9D. 不确定8. 图的BFS生成树的树高比DFS生成树的树高【】A. 小或相等B. 小C. 大或相等D. 大9. 如果要求一个线性表既能较快地查找，又能适应动态变化的要求，则可采用什么查找方法【】A. 有序表B. 线性链表C. A VLD. 分块有序表10. 实现任意二叉树的后序遍历的非递归算法而不使用栈，最佳方案是二叉树采用什么存储结构【】A. 二叉链表B. 三叉链表C. 广义表D. 顺序存储结构11. 对包含n个元素的哈希表进行查找时，平均查找长度【】A. 为O（log2n）B. 为O(n)C. 不直接依赖于nD. 以上都不对12. 判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以使用【】A. 求关键路径的方法B. 求最短路径的Dijkstra方法C. DFS算法D. BFS算法13. 广义表Glist(a)，则表尾为：【】A. 空表B. aC. ( )D. (( ))14. 对于含有n个顶点e条边的无向连通图，利用Kruskal算法产生最小生成树时，其时间复杂度为【】A. O (n2) B. O (n*e) C. O (nlog2n) D. O(elog2e)15. 设哈希表长m = 18，哈希函数H (K) ＝K ％17。

关键字序列为：｛53、17、12、61、98、70、87、25、63、46、14、59、67、75｝，如果使用二次探测再散列处理冲突，则查找成功的平均查找长度约为【】A. 2.18B. 1.71C. 2.96D. 1.06二、填空题（本大题共10小题，每小题2分，共20分）1. 每种数据结构都应具备三种基本运算：_______________________________。

2. 在n个结点的顺序表中插入一个结点，具体移动结点的次数取决于______________。

3. 设长度为n的链队列用单循环链表表示，若只设头指针，则出队列操作的时间复杂度为___________。

4. 在链栈中执行入栈操作时，不必考虑______________。

5. 含有n个结点的二叉树，使用二叉链表表示时，空链域的个数为___________。

6. DFS遍历类似于二叉树的_________遍历。

7. 有回路的有向图________________拓扑排序。

8. 使用二分查找法（折半查找）搜索一个线性表时，该线性表必须是__________表。

9. 设一组记录的关键字为｛3、7、6、9、8、1、4、5、2｝，进行排序的最小交换次数为_________________次。

10. 若一些单词仅由ABCDE组成，在这些单词中，5个字符出现的频率依次为23, 2, 16, 18和16，则这5个字符的哈夫曼编码为：_____________________________。

三、解答题（本大题共4小题，每小题10分，共40分）1. 如果使用一维数组Array[MAX]来存储循环队列的元素时，如何设置一个标志flag来区分头指针(front)和尾指针(rear)相等时，队列的状态是“空”还是“满”？2. 简述递归思想。

现有两个正整数M和N，如果采用递归方法解决M×N运算，试结合递归思想，说明其终止条件和递归语句是什么？3. 试给出一个关键字个数最少的序列，使得构造平衡二叉树时，四种调整平衡操作（LL、LR、RR、RL）各只执行一次，并且画出其构造过程。

4. 对于如下所示的有向图，试给出：(1)邻接矩阵;(2)邻接表;(3)逆邻接表;(4)强连通分量;(5)从顶点V1出发，给出DFS序列。

(6)从顶点V3出发，给出BFS序列。

四、算法阅读题（本大题共3道小题，每小题8分，共24题）【说明】结构定义struct ListNode{elemtype data;struct ListNode *next;};struct BtreeNode{elemtype data;struct BtreeNode *lchild, *rchild;};1.阅读下面的算法，试说明算法的功能。

int unknown(struct BTreeNode *root, int K, int tag){ //假设K的初始值为－∞if(root = =NULL)tag = 1;else {tag = unkown(root－>lchild,K,tag);if(tag = = 0 ||root－>data <K)tag = 0;else {K = root－>data;tag = unknown(root－>rchild,K,tag);}}return tag;}2.下面算法的功能是删除所有相邻结点数据域值相同的结点，只保留最后一个结点。

请在空白处填入正确的语句，使之完善。

其中，Head为带头结点的单链表指针。

V oid DelMulNode(struct ListNode *head){struct ListNode *q, *s, _______①________;while(___________②________){s = p;______________③_______;while(q != NULL)if(q－>data = =p－>data){s－>next = q－>next;_______④_________;}else{_________⑤________;q = q－>next;}______________⑥___________;}}3. 下面的算法是将所有奇数放到所有偶数之前。

请在空白处填入正确的语句，使之完善。

并且给出该算法的时间复杂度。

V oid OddEven(int a[], int n){int i = 0, j = n-1, temp;while(____①____) {while((a[i]%2 != 0)&&(i<j))i++;while(____②___)_____③______;if(i < j){temp = a[i];a[i] = a[j];a[j] = temp;____④___;____⑤___;}}}五、算法设计题（本大题共3道小题，每小题7分，共21分）1. 已知在两个单链表ListA和ListB中均不存在相同的元素值，试设计算法：求出由仅在A 中出现而不在B中出现的元素值所组成的单链表。

【说明】假设结点值为整型数。

V oid isLisA(struct ListNode *LA, struct ListNode *LB){2. 假设二叉树采用二叉链表作为存储结构，试编写一个算法：求任意一个指定结点所在的层次。

【说明】：假设二叉树中无结点值相同的，且要求采用非递归算法。

Int AnyTreeNodeLevel(struct BtreeNode *root, elemtype x){ /* x为结点中的值*/3.证明：二叉排序树的中序遍历序列是一个升序序列。

Email: zhangxinguang369@。