2011年华中科技大学数据结构与算法分析考研试题.pdf

华中科技大学 华中科技大学 华华中中科科技技大大学学2011年研究生入学考试试题 数据结构与算法 25 25 一．术语解释：（2255） 1 线性表 2 树的结点的层次 3 排序 4 完全图 5 最小生成树 25 25 二．单项选择：（2255） 1 在数组｛1，2，3，4，5，6，7，8，9，10｝中折半查找5，需要的比较次数是（） A 1 B 2 C 3 D 4 2 假定问题规模为N 时，某递归算法的时间复杂度记为T（N），已知T(1)=1， T(N)=2T(N/2)+N/2，用O 表示的时间复杂度为（） A O(N) B O(NlogN) C O(N²) D O(N²logN) 3 一棵二叉树的先序便利输出为ABCDEFGH，中序遍历为CBEDAFHG，则其先序遍历 输出为（）【此题的确问的是先序遍历】 A CBDEAFGH B CBEDAFHG C BCEDFAHG D 以上都不对 4 栈和队列的共同点是（） A 先进先出 B 后进先出 C 插入删除只能在端点进行 D 没有共同点 5 起泡排序的时间复杂度是（C）【此题原试卷将答案附上了】 A O(N) B O(NlogN) C O(N²) D O(N²logN) 60 60 三．简答（6600） 1 用一个数组实现两个栈，尽可能利用存储空间，写出两个栈的插入、删除操作算法。 2 已知一组关键字为｛27、25、23、37、35、33、77、75、73、97、95、93、103｝，按哈 希函数H(key)=key Mod 11（表长11），用连地址法处理冲突，画出哈希表。 3 一个递归函数具有如下形式 Void func(int n) { if(n0) { func(n/2); printf(d%,n*n); func(n/2); } return; } 请依次写出fun(1)，fun(2)，fun(3)，fun(5)执行的结果，其时间复杂度为多少？ 4 一个通信网络中共有九中字符，其概率分别为0.14、0.23、0.15、0.03、0.18、0.1、0.02、 0.11、0.04，画出相应的赫夫曼树来设计其赫夫曼编码。 5 V₁→V₂→V₃→∧； V₂→V₄→V5→∧ ； V3→V5→V6→∧ ； V4→∧； V →V →V →∧ ； V →V →∧； V →∧ ； V →V →∧ ； V →∧， 5 7 8 6 8 7 8 9 9 画出这个逻辑结构的图示，分别写出从V₁出发的深度优先和广度优先搜索序列。 40 40 四．应用编程题：（4400） 1 在一个整形数组a中既有负数又有正数，编写一个算法将a中所有负数移到整数之前， 要求其时间复杂度为O(n)，n 为数组长度，并且只使用常数个辅助空间。 例如：a[ ]={1,2,3,4,-1,1,-2,-1,-4}执行算法后的输出为a[]={-4,-1,-2,-1,1,4,3,2,1} 2 编写一个C 函数，输入一个二叉树的根节点，返回这棵树中所有值大于0的节点值 之和，如果根