数据结构试卷查找附标准答案

《数据结构试卷查找附标准答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第9章集合一．选择题1.C2.A3.1D3.2C4.D5.B6.D7.D8.C9.A10.D11.B12.1C12.2C13.1C13.2D13.3G13.4H14.1E14.2B14.3E14.4B14.5B15.1B15.2A16.A17.C18.C19.C20.D21.B22.C23.B24.C25.1B25.2F25.3I26.A27.D28.C29.1A29.2C30.B31.D32.D33.C34.D35.1D35.2C36.C二．判断题1.√2.√3.×4.×5.×6.√7.√8.×9.×10.×11.×

2、12.√13.√14.×15.×16.×17.√18.×19.√20.×21.×22.×23.×24.×25.√26.×27.×28.√29.√30.×31.×32.√33.√34.×35.√36.√部分答案解释如下。4．不能说哪种哈希函数的选取方法最好，各种选取方法有自己的适用范围。8．哈希表的结点中可以包括指针，指向其元素。11．单链表不能使用折半查找方法。20．按插入后中序遍历是递增序列的原则，若某结点只有右子树，而插入元素的关键字小于该结点的关键字，则会插入到该结点的左侧，成为其左孩子。这种插入就不是插入到叶子

3、下面。矚慫润厲钐瘗睞枥庑赖。21．从平衡因子定义看，完全二叉树任一结点的平衡因子的绝对值确实是小于等于1。但是，平衡二叉树本质上是二叉排序树，完全二叉树不一定是排序树。故不能说完全二叉树是平衡二叉树。聞創沟燴鐺險爱氇谴净。23．某结点的左子树根结点不一定是它的中序前驱，其右子树根结点也不一定是它的中序后继。24．在等概率下，查找成功时的平均查找长度相同，查找失败时的平均查找长度不相同。26．只有被删除结点是叶子结点时命题才正确。三．填空题1．nn+12．43．6,9,11,124．5残骛楼諍锩瀨濟溆塹籟。5．26（第4

4、层是叶子结点，每个结点两个关键字）6．1,3,6,8,11,13,16,19酽锕极額閉镇桧猪訣锥。7．5,968．m-1,「m/2ù-19．2,4,3彈贸摄尔霁毙攬砖卤庑。10．(1)哈希函数(2)解决冲突的方法(3)选择好的哈希函数(4)处理冲突的方法(5)均匀(6)简单謀荞抟箧飆鐸怼类蒋薔。11．AVL树（高度平衡树，高度平衡的二叉排序树），或为空二叉树，或二叉树中任意结点左子树高度与右子树高度差的绝对值小于等于1。厦礴恳蹒骈時盡继價骚。12．小于等于表长的最大素数或不包含小于20的质因子的合数13．1614．ë㏒

5、2n」+1茕桢广鳓鯡选块网羈泪。15．(1)45(2)45(3)46（块内顺序查找）16．k(k+1)/217．30，31.5（块内顺序查找）鹅娅尽損鹌惨歷茏鴛賴。18．(1)顺序存储或链式存储(2)顺序存储且有序(3)块内顺序存储，块间有序(4)散列存储籟丛妈羥为贍偾蛏练淨。19．(n+1)/220．(n+1)/n*log2(n+1)-121．结点的左子树的高度减去结点的右子树的高度預頌圣鉉儐歲龈讶骅籴。22．(1)顺序表(2)树表(3)哈希表(4)开放定址方法(5)链地址方法(6)再哈希(7)建立公共溢出区渗釤呛俨

6、匀谔鱉调硯錦。23．直接定址法24．logém/2ù()+125．O(N)26．n(n+1)/2铙誅卧泻噦圣骋贶頂廡。27．5428．3129．37/1230．主关键字31．左子树右子树擁締凤袜备訊顎轮烂蔷。32．插入删除33．1434．(1)126(2)64(3)33(4)65贓熱俣阃歲匱阊邺镓騷。35．（1）low<=high(2)(low+hig)DIV2(3)binsrch:=mid(4)binsrch:=0坛摶乡囂忏蒌鍥铃氈淚。36．(1)k(2)I

7、d+1(3)head>rear蜡變黲癟報伥铉锚鈰赘。38．(1)p!=null(2)pf=p(3)p!=*t(4)*t=null四．应用题1．概念是基本知识的主要部分，要牢固掌握。这里只列出一部分，目的是引起重视，解答略。2．（1）散列表存储的基本思想是用关键字的值决定数据元素的存储地址（2）散列表存储中解决碰撞的基本方法：①开放定址法形成地址序列的公式是：Hi=（H（key）+di）%m，其中m是表长，di是增量。根据di取法不同，又分为三种：買鲷鴯譖昙膚遙闫撷凄。a．di=1，2，…，m-1称为线性探测再散列，其特

8、点是逐个探测表空间，只要散列表中有空闲空间，就可解决碰撞，缺点是容易造成“聚集”，即不是同义词的关键字争夺同一散列地址。綾镝鯛駕櫬鹕踪韦辚糴。b．di=12，-12，22，-22，…，±k2（k≤m/2）称为二次探测再散列，它减少了聚集，但不容易探测到全部表空间，只有当表长为形如4j+3（j为整数）的素数时才有可能。驅踬髏彦浃绥譎