北京大学1997硕士入学数据结构试题.doc

《北京大学1997硕士入学数据结构试题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、北京大学1997硕士入学数据结构试题1（16分）   填空 ①设只包含要根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为       ，最小结点数为          。 ②某二叉树结点的对称序序列为A，B，C，D，E，F，G，后序序列为B，D，C，A，F，G，E，则该二叉树结点的前序序列为             ，该二叉树对应的树林包括        棵树。 ③求具有最小带权外部路径长度的扩充二叉树的算法称为            算法，对于给出的一组权W={10，12，16，21，30}，通

2、过该算法求出的扩充二叉树的带权外部路径长度为             。 ④设有关键码序列（Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的次序进行排序，若采用初始步长为4的Shell排序法，则一趟扫描的结果是          ；若采用以第一个元素为分界元素的快速排序法，则一趟扫描的结果是             。 2（10分）   请简要回答下列问题 ①什么是抽象数据类型？试举一例说明之。 ②什么是广义表？请简述广义表与线性表的主要区别。 3（6分）   给定关键码序列（26，2

3、5，20，33，21，24，45，204，42，38，29，31），要用散列法进行存储，规定负载因子a=0.6。 ①请给出除余法的散列函数。 ②用开地址线性探查法解决碰撞，请画出插入所有的关键码后得到的散列表，并指出发生碰撞的次数。 4（6分）   本题要求在检索各结点的概率不相等的条件下构造最佳二叉排序树。给出关键码集合   {B,    E,    H}    key1  key2  key3   以及权的序列   (9   4   5   8   6   1   3)    p1  p2  p3  q

4、0  q1  q2  q3   请构造最佳二叉排序树。 5（12分） ①请画出往图1的5阶B-树中插入一个关键码390后得到的B-树，以及再删除关键码150后得到的B-树。 ②包括n个关键码的m阶B-树在一次检索中最多涉及多少个结点？（要求写出推导过程）图1 题5图 6（10分）   如图2所示是一棵正在进行插入运算的AVL树，关键码70的插入使它失去了平衡，按照AVL树的插入方法，需要对它的结构进行调整以恢复平衡。 ①请画出调整后的AVL树。 ②假设AVL树用llink-rlink法存储，T是指向根结点的

5、指针、请用PASCAL（或C）语句表示出这个高速的过程。   （说明：不必写出完整的程序，只需用几个语句表示出在本题所给的具体情况下调整过程中指针的变化。在调整过程中还有两个指针变量p和q可以使用）。图2 题6图 7（16分）   请仔细阅读下面的堆排序算法。待排序记录存储在一维数组中，说明如下：   TYPEnode=RECORD              key:integer;              info:datatype         END         heaptype=ARRAY[

6、1..n0]OFnode;   过程heapsort的功能是将数组heap中的前n个记录按关键码值递减的次序排序。heapsort调用sift,sift的参数heap,h和r具有如下的含义：调用sift时，以heap[h+1],heap[h+2],……，heap[r/2]为根的子树已经是堆；sift执行后，以heap[h],heap[h+1],heap[h+2],……heap[r/2]为根的子树都成为堆。   PROCEDUREsift(VARheap:heaptype;h,r:integer);     

7、  VARi,j:integer;           x:node;           finish:boolean;       BEGIN           i:=h;           x:=heap[i];           j=2*i;           finish:=false;           WHILEDO           BEGIN               IF(jheap[j+1].key)               TH

8、ENj:=j+1;               IFx.key>heap[j].key               THENBEGIN                                  END               ELSEfinish:=true;           END;                  END;   PROCEDUREheapsort(VARheap:heapty