1、2000 年混合班“数据结构”试卷一、选择及填空题（除非特别注明，一般每小题 2 分，共 30 分）1、下列说法哪个正确：A） 堆栈是在两端操作、先进后出的线性表B） 堆栈是在一端操作、先进先出的线性表C） 队列是在一端操作、先进先出的线性表D） 队列是在两端操作、先进先出的线性表2 已知一棵二叉树的前序遍历结果为 ABCDEF，中序遍历结果为 CBAEDF，则后序遍历的结果为：A） CBEFDA B）FEDCBA C）CBEDFA D）不定3、对哈希(HASH)函数 H(k)= k MOD m, 一般来说,m 应取A) 素数 B) 很大的数 C) 偶数 D)奇数4 _是 HASH 查找的冲突
2、处理方法:A）求余法 B) 平方取中法 C) 二分法 D) 开放地址法5、下列哪种排序算法（均在内存中进行）要求内存量最大:A） 选择排序 B）插入排序 C）冒泡排序 D）归并排序6 设有序列 12、42、37、19，当使用直接插入排序从小到大排序时，其比较次数为：A）3 B）4 C）5 D）67 下列哪种排序算法数据交换的次数最多:A） 选择排序 B）插入排序 C）冒泡排序 D）归并排序8、可用类似下列哪些算法判别一有向图是否存在回路_:宽度优先遍历算法、深度优先遍历算法、最小生成树算法、求关键路径算法、求最短路径的Dijkstra 算法、Topsort 算法。9、 （3 分）若要维护一个数
3、的集合，要求：1）能往该集合中插入任意一个数，且 2）能随时从该集合中删除最小及最大的数，你认为采用的最佳数据结构是：_10、 （3 分）请列出主要的算法设计方法_11、判别下列序列是否是最大堆，若不是，按书中的算法调整（8 分） 。序号 原始序列 是否为最大堆（Y/N）调整后的数的序列1 （100，66，48，73，35，39，42，57，86，21）2 （103，97，56，38，66，23，42，12，30，53，6，20）3 （1，2，3，4，5，6，7，8，9，10）二、 下列二叉树是某一森林的表示，请画出对应森林（8 分）：三、 画出下列无向图的相应邻接表(adjacency li
4、sts)表示法（邻接顺序按节点数字从小到大） ，并计算每一节点的 dfn（从 0 开始）和 low 值，指出哪些节点是关节点（Articulation Points）（12 分）四、 对以下关键字序列构造地址空间为 016 的哈希（HASH）表，选取哈希函数 H(k)=k/2， k 为关键字第一个字母在字母表中的序号，地址冲突处理策略为链地址法（直接插入在相应链表的头上） 。请画出当关键字序列为（Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec）时的哈希表, 并求等概率情况下查找成功与不成功的平均查找长度(10 分).五、 D
5、eap 是将最小堆作为左子树、最大堆作为右子树的堆。在 Deap 中要求最小堆中任何元素i 的值均小于最大堆中对应元素 j（按书中定义）的值。 （ 1）请写出 i 和 j 间的函数关系；（2）请画出将下列 Deap 中的最小元素删除后 Deap 的结构。 （10 分）六、 下面程序是循环归并排序的程序框架(共 18 分) ：void merge_pass(element list,element sorted, int n, int length) int i,j;for (i+0;i=n-2*length; i+=2*length)merge(list,sorted,i,_; i+2-1);
6、if (i+lengthn)merge(list,sorted,i,i+length-1,n-1);elsefor (j=i; jn; j+) sortedj=listj;void merge_sort(element list, int n) int length=1;element extraMAX_SIZE;while (lengthn) merge_pass(list,extra,n,length);length *=2;merge_pass(_);length *=2;其中，void merge(element list, element sorted, int i, int m,
7、int n)将两个已排序好的序列：listi.listm与 listm+1.listn归并，并将结果放在 sortedi.sortedn中。(1) 请将上述程序中缺少的部分补上(2) 对于待排序序列（100，66，48，73，35，39，42，57，86，21） ，请分别针对循环归并和递归归并画出相应归并过程中的子序列的划分/合并结构。(3) 请写出完整的 void merge(element list, element sorted, int i, int m, int n)函数;六、请写出函数 void UpdateHeap（element list, int n, int i, int x)将最大堆（list ，n）中的元素listi中的 key 改为 x，且保证修改后的元素仍然构成堆。 （ 12 分）
