数据结构考题.doc

1. 已知哈希表的地址空间是0.10,哈希函数为H(k)=key mod 11, 采用开放地址法线性探测处理冲突,将下面各数依次存入该散列表中（19,01,23,14,55,68,11,86,37）, 并求出在等概率下的平均查找长度。(5分) 012345678910550123146811371986 ASL=19/92、二叉树、树、森林都可以用二叉链表来作为它们的存储结构，因此二叉链表所表示的逻辑结构不一样，在其上的计算也不一样。试设计一个求树的深度的递归算法，并说明在此基础上求二叉树和森林的深度的不同（5分） 注：若二叉链表表示的是二叉树时，若左子树的深度为d1，右子树的深度为d2，则二叉树的深度为MAX（d1，d2）+1； 若二叉链表（孩子-兄弟链表）表示的是树时，则只有左子树，若其深度为d1，则树的深度为d1+1； 若二叉链表（孩子-兄弟链表）表示的是森林时，则根结点的左分支所指的是森林中第一棵树的子树森林，根结点的右分支所指的森林中去掉第一棵树之后由其它树构成的森林，则森林的深度为MAX（d1+1，d2）。 3、若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为_C_(A)(B)(C)(D)n4、具有10个叶结点的二叉树中有_B_个度为2的结点。(A)8 (B)9(C)10(D)115、判断以下序列是否为堆，如果不是，逐步将它调整为小顶堆（要求写出调整过程）。（56,37,48,24,61,05,16,37）1） 待排序记录存放在数组R1.8之中，将R看作一棵二叉树，每个结点表示一个记录，将第一个记录R1作为二叉树的根，以下各记录R2.8依次逐层从左到右顺序排列，构成一棵完全二叉树，任意结点Ri的左孩子是R2i，右孩子是R2i+1，双亲是R i/2 。2） 待排序的所有记录放到一棵完全二叉树的各个结点中3）3）从i=8/2的结点R4开始，比较根结点与左、右孩子的关键字值，若根结点的值小于左、右孩子中的较小者，则交换根结点和值较小孩子的位置，即把根结点下移，然后根结点继续和新的孩子结点比较，如此一层一层地递归下去，直到根结点下移到某一位置时，它的左、右子结点的值都大于它的值或者已成为叶子结点。 ACBDEFG6.知某二叉树的先序遍历序列为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下标0123456789101112k7754164331294660748890探查次数211114111119.于给定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下标01234567k98563738721148探查次数121132112.编写算法实现求以二叉链表表示的二叉树的深度的递归算法。typedef struct BiTnode ElemType data; BiTnode *Lchild；*Rchild; BiTnode,*BiTree; Int Depth（BiTree T） if（！T）return 0； else h1=Depth（ T -Lchild）； h2=Depth（ T -Rchild）； if（h1=h2）return h1+1； else return h2+1；/DepthACBDEFG13、对二叉树进行中序线索化。答： 关键活动为a2，a5，a7，这些活动构成了关键路径：14、现有一待排序列为49，38，65，97，76，13，27，50，如果以第一个数据元素49为支撑元素，在经过一趟快速排序后的结果序列是什么？ 答案：27，38，13，49,76，97，65，5015.将下列森林转换为二叉树。（简述转换过程） 答案：16.已知一组关键字为25,18,46,2,53,39,32,4,74,67,60,11。按表中的元素顺序依次插入到一棵初始为空的二叉排序树中,画出该二叉排序树,并求在等概率的情况下查找成功的平均查找长度。答案：17.已知哈希表的地址空间是0.12,哈希函数为H(k)=key mod 13, 采用开放地址法线性探测再散列处理冲突,将下面关键字集合依次存入该散列表中, 并