数据结构考题.docVIP

1. 已知哈希表的地址空间是0..10,哈希函数为H(k)=key mod 11, 采用开放地址法线性探测处理冲突,将下面各数依次存入该散列表中（19,01,23,14,55,68,11,86,37）, 并求出在等概率下的平均查找长度。(5分) 0 1 2 3 4 5 6 7 8 9 10 55 01 23 14 68 11 37 19 86 ASL=19/9 2、二叉树、树、森林都可以用二叉链表来作为它们的存储结构，因此二叉链表所表示的逻辑结构不一样，在其上的计算也不一样。试设计一个求树的深度的递归算法，并说明在此基础上求二叉树和森林的深度的不同（5分） 注：若二叉链表表示的是二叉树时，若左子树的深度为d1，右子树的深度为d2， 则二叉树的深度为MAX（d1，d2）+1； 若二叉链表（孩子-兄弟链表）表示的是树时，则只有左子树，若其深度为d1，则树的深度为d1+1； 若二叉链表（孩子-兄弟链表）表示的是森林时，则根结点的左分支所指的是森林中第一棵树的子树森林，根结点的右分支所指的森林中去掉第一棵树之后由其它树构成的森林，则森林的深度为MAX（d1+1，d2）。 3、若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为___C______ (A) (B) (C) (D)n 4、具有10个叶结点的二叉树中有___B_____个度为2的结点。 (A)8 (B)9 (C)10 (D)11 5、判断以下序列是否为堆，如果不是，逐步将它调整为小顶堆（要求写出调整过程）。（56,37,48,24,61,05,16,37） 待排序记录存放在数组R[1..8]之中，将R看作一棵二叉树，每个结点表示一个记录，将第一个记录R[1]作为二叉树的根，以下各记录R[2..8]依次逐层从左到右顺序排列，构成一棵完全二叉树，任意结点R[i]的左孩子是R[2i]，右孩子是R[2i+1]，双亲是R[ i/2 ] 。 待排序的所有记录放到一棵完全二叉树的各个结点中 3） 从i=[8/2]的结点R[4]开始，比较根结点与左、右孩子的关键字值，若根结点的值小于左、右孩子中的较小者，则交换根结点和值较小孩子的位置，即把根结点下移，然后根结点继续和新的孩子结点比较，如此一层一层地递归下去，直到根结点下移到某一位置时，它的左、右子结点的值都大于它的值或者已成为叶子结点。 6.知某二叉树的先序遍历序列为ABDEFCG，中序遍历序列为DFEBAGC，请问此二叉树的形态如何？高度为几？ 答：高度为5 。 7.出广义表LS=(a,b,(c,d),e)的存储结构（两种表示方法中的任一种） 8.知哈希表的地址空间是0..12,哈希函数为H(k)=key mod 13, 采用开放地址法线性探测再散列处理冲突,将下面关键字集合依次存入该散列表中, 并求出在等概率下的平均查找长度。 关键字集合：{ 16,74,60,43,54,90,46,31,29,88,77}。 解：ASL=15/11 下标 0 1 2 3 4 5 6 7 8 9 10 11 12 k 77 54 16 43 31 29 46 60 74 88 90 探查次数 2 1 1 1 1 4 1 1 1 1 1 9.于给定11个数据元素的有序表{2,3,10,15,20,25,28,29,30,35,40},采用二分查找,试问： (1)若查找给定值为20的元素,将依次与表中哪些元素比较？ (2)若查找给定值为26的元素,将依次与哪些元素比较？ (3)假设查找表中每个元素的概率相同,求查找成功时的平均查找长度 解：(1)若查找给定值为20的元素,依次与表中25,10,15,20元素比较,共比较4次。 (2)若查找给定值为26的元素,依次与25,30,28元素比较,共比较3次。 (3)在查找成功时,会找到图中某个圆形结点,则成功时的平均查找长度： 10、已知某二叉树的先序遍历序列为abdgcefh，中序遍历序列为dgbaechf，请问此二叉树的形态如何？高度为几？ 答：高度为4。二叉树的形态略。 11、已知哈希表的地址空间是0..6,哈希函数为H(k)=key mod 7, 采用开放地址法线性探测再散列处理冲突,将下面关键字集合依次存入该散列表中, 并求出在等概率下的平均查找长度。 关键字集合：{ 37，38，72，11, 48，98，56}。 解：ASL=11/7 下标 0 1 2 3 4 5 6 7 k 98 56 37 38 72 11 48 探查次数 1 2