2001年混合班99数据结构与算法试卷

1、2001年混合班99“数据结构与算法”试卷考试时间：2小时10分一、 单项选择及填空题（除非特别注明，一般每小题2分，共38分，请选择题答案写在试卷左边）1 若语句S的执行时间为O（1），那么下列程序段的时间复杂度为：for(i=0; i<n; i+)for(j=0; j<=i; j+)S;A) O(n) B) O(n*n) C) O(nlogn) D) O(n*i)2 已知一堆栈的进栈序列为：1234，则下列哪个序列为不可能的出栈序列：A）1234 B）4321 C）2143 D）41233 深度为5的二叉树至多有_个结点.A) 16 B) 32 C）31 D) 104 堆(HE

2、AP)是一种_A) 二叉树 B) 线性表 C) 图 D) 算法5 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？A） 1和5 B）2和4 C）4和2 D）5和16 下列哪种排序算法的平均时间复杂度为O（nlogn）：A） 简单选择排序 B）简单插入排序 C）冒泡排序 D）归并排序7 用冒泡排序（交换排序）算法对下列数据进行从小到大排序。在将最大的数“沉”到最后时，数据的顺序是什么？ 12 37 42 19 27 35 56 42 10A） 12 37 42 19 27 35 44

3、10 56B） 12 37 42 19 27 35 10 44 56C） 12 37 19 27 35 42 44 10 56D） 10 12 19 27 35 37 42 44 568 下列哪种排序算法更适合于外部排序A） 选择排序 B）插入排序 C）冒泡排序 D）归并排序9 数据结构中的DIJKSTRA方法是用来求:A) 关键路径 B) 最短路径 C) 拓扑排序 D) 字符串匹配10 对下列二叉树进行后序遍历，其遍历结果为： a b c d e f gA) gfedcba B) dbegfca C) bdecgfa D) dbaecgf11稀疏矩阵（SPARSE MATRIX）一般的压缩存

4、储方法有以下两种：A）二维数组和三维数组 B）三元组（TRIPES）和哈希表（HASH TABLE）C）三元组（TRIPES）和十字链表（cross linked） D）哈希表和十字链表12 在待排序的元素基本有序的前提下，效率最高的排序方法是：A）简单插入排序 B）简单选择排序 C）快速排序 D）归并排序13 设以单向链表方式表示一个多项式（按指数expon递减方式）,请写出链表中节点结构的C语言定义并对其中分量的用途作简要注释：14（4分）在简单插入排序、希尔排序、简单选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有：_15（4分）请至少给出三种常用的算法设计方法并各给出

5、对应的一个例子 _16（4分）按满二叉数的概念可推广出满K叉数的概念。若对满K叉树的节点逐层编号（从1开始，同层中从左到右），则编号为i的节点的父节点编号是_，编号为i的节点的第j个儿子的编号是_。二、请对下列有向图（共9分）：（1） 画出相应邻接链表（adjacency list）表示法（链表中，按节点编号大小从小到大向后排），（2） 指出按教材中TOPSORT算法在上述表示的基础上进行遍历的输出结果。三、（8分）对于下列二叉树（1） 请画出其对应的中序线索（thread）（2） 请将下列用于中序线索二叉树遍历的程序的空白部分填上。threaded_pointer insucc( threa

6、ded_pointer tree) threaded_pointer temp; temp = tree->right_child; if ( !tree->right_thread )while( _ )temp = temp->left_child; return temp;void tinorder ( threaded_pointer tree) threaded_pointer temp=tree; for(; ;)temp = insucc (temp);if (_) break;printf ("%3c", temp->data); 四

7、、（8分）选取哈希函数H(k)=k mod 11, 用线性探测（linear probing）冲突解决策略(H(k)+i)%11. 试在0-10的哈希地址空间中对关键字序列(22,41,53,46,30,13,01,67)构造哈希表, 并求等概率情况下查找成功与不成功的平均查找长度。五、（9分）下面是将删除最大堆(MAX HEAP)堆顶元素的算法，请将空白部分填上：element delete_max_heap(int *n) int parent,child; element item, temp; if (HEAP_EMPTY(*n) fprintf (stderr, "The

8、heap is emptyn"); exit (1); item = heap1; temp = heap_ ; parent = 1; child = 2; while (child <=*n) if (child < *n) && (heapchild.key< heapchild+1.key) _; if (temp.key >= heapchild.key) break; heapparent = _; parent = child; child* = 2; heap parent = temp; return item;六、 （8分）Deap是将最小堆作为左子树、最大堆作为右子树的堆。在Deap中要求最小堆中任何元素i的值均小于等于最大堆中对应元素j（按教材中定义）的值。（1） 请写出i和j间的函数关