2008年清华大学计算机考研真题【回忆版】

《数据结构》
一、选择题
3、给了一序列比如6.7.4.8.9.3.散列函数是H(key)=key%11.一问成功时的平均搜索长度；二问不成功的平均搜索长度。
4、哪种数据结构，从某一个结点到根结点的路径序列组成一个降序排列。
      a.  b.堆 c.最小堆 d

5、还有一个题是关于关键路径的，答案选项是49。
   /B -C
A      /F
  D-E     H
        G/

6、什么是数据结构？ A  B  C定义在一个数据集合上的属性和操作 D
7 高度为h的完全二叉树，一共有多少种？A  B 2^(h-1)  C  D
二、证明题
什么样的有向无环图有的拓扑有序序列，并证明。
三、计算题
1 有n个结点的二叉树高度，最小高度分别是多少？
2 一棵有n个结点的树有m个叶节点，如果用做兄弟-右子女表示法，则有多少个结点的右指针域为空?
3 霍夫曼树中，有n个叶结点，问一共有多少个结点?
4 有n个结点的树的不同排列形式有多少种。
四、给定一个文件有1,000,000个记录，每个200B，记录中关键码大小50B，页面大小为4kB，现以B+树（关键码复刻）方式组织该文件，尽量使每结点拥有尽可能多的关键码，已知每个指针占用5B。
     问1.该B+树有多少个叶结点，共有多少层；2.该B+树共有多少个索引结点；3.每次搜索要读盘多少次？
五、算法设计题
1.给定A[n],设计一个算法，重排数组，使得奇数都在数组前半部分，偶数都在后半部分。要求时间复杂度O(n)。
  函数头：void exstorage(int A[], int n)
2.重新设计一个直接选择算法函数，采用递归方式。
  函数头：void selectsort(int A[],int left, int right)