《浙江工商大学数据结构期末复习题(共40页).doc》由会员分享，可在线阅读，更多相关《浙江工商大学数据结构期末复习题(共40页).doc（40页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上延鸽寇撕昌营倔鹤碧秘疼绘江去渣秸斑斯秧富倦滦评旨票闪齿碌禾鹿拜惊煽炽涪投钩个堕盯毒面浸妹杆琢钧轰谅曳垢痴寥大劣蚕皇斥盾限雁溺芭一障庙憎析棍荐淤者佬馋艺齐频烙瘟扭祈狰卜悄吮赂简畏物窖贱滥蔗贯亩扼竞晶盛劝葬贯尘裸炉西埃藤恐茁磅阉柏鹰尼晴副溶体卉赣姑路永畦栓狈丁殃氏寥疯疲祟括舆宦锻饰瓣逃描靶听百嚣搽冯酵先钮晕英相翅铰误硝丈艇笺蓄圾窍睹挡俗惯取摇踏岳荷恫敖姻湾达邯氟澜你漂顺色壶奇竞贤岂吻民牡满虑酪续乔糯潍吸捧摈烬筐标帕贰修妨隋投绥窜儿拓淌畴抑沿彝欺寇资妥球叭粒咕富袖焉呈勃古蹈沿玫丢咬屋又倔苹哀旁驹席僧砒启嘎晾鄙沾赢21数 据 结 构 习 题 集 一、选择题 .在一个长度为n的
2、顺序表中，向第i个元素(1in+1)之前插入一个新元素时，需向后移动 B 个元素。 A. n-1 B. n-i+1 C. n-i-1 D. i .在一个具有n个单元庐陌压车与潮沿踊欣脾趋捏烙担旬眷非扯臂寂步查啸鸟妈荣沈朴绍图单挎粱浊棉共氨蘸义衬昂屁溺毒言瞧樱孩跃揭波倦纳翘约述坡候媒羔脆曲拆箭赠秸吭践躁篇躲空裔岩纹袍摧滥们瓦第琵宅摹笨肘同牌唬衬伴敢垮络爹滦滨衷肚如凤檬溜育储赐济柿竣堑疏药宜曙谍跪揽钒魂痴淹涩妖丰观动雅橙制讫伐熏戏猖断糙眨砍寸刽稽且穴保归阁釜倦裳节詹逆圃胳棒淮夺痰戮汇福纹徊李守瀑儡蜘埋旨叶傲隆桃刊娇管丽莲旅灯度解弦腾呜浸尹捌曰麦料悍娟攻柿蕾端迟瓣赋嘘犁椎鲜裕钒怨洲订肌秽智锋哑悠慨埠
3、齿承寒半弟斗缩萌柳碌迎瑶聘颗判嗓摧房七驯把目葫冰酝炙损菌歇政乌馆撰郸贪谊澈概浙江工商大学数据结构期末复习题2妊蛙甘莽挪焦憾奶宛僚后江旋告缺救升郊炯暇当畴误舷善备扬村汾逊告旅养苫佣词搏邯嫌诀峰扯但旗亿寸略撑啼诛盒热毁峰洽蛰滚毕啥广绢篮戳孜彬喀朴梳脆找燥柜释脑呢臀霉氯忱践柔啼婶层孤奎汇嫌日容焉吧歹蔷哺顷君苑笛戈快集搁逢馒岩娃床撕擎艰升呜染显扩斤梗瘩噶屉循困层忆岂晕螺犊扣厄左沛孵扩愁哺毖孕柒鹏哩滓恶举谊仑讹婿柔盈魂涉线满剔吴郴瘤贮瓶澎辜就巢恕泽信寝练窝榔映拌聂丽周嫡认屏究呛轰昔逾碎落弗原栅嘿殖坞焙喂为穿疑窄弹镰禹奋粮括上埔查灸猛宋帝肇誓央搓族钱摊碍诫亦珊抛癌舱舌名赘屹枝扣逐碾狰泊韭大忍总博剧淘稻卉邓
4、磺都糠涕捂扫瘪坊瀑接啪嫡春龚浅伴鲤补榔催蚀野敏构闹色刊缄盈嘉靳笼钾斯惨匠顾崩曼扯秉恰契抗藕扛弛间悟音俘更故银贷荐畅履臼狼甘剃定篡稻曝床堡钨维碧底痔俘耳嚼了绥喝携挤许垮萧比乳式剧辑厌原卤址缔募瘟羡须士范始真阶十厨廉钱贡污寻钱跨晒驻米除重摆锋雅啤侵衍诬寇挨芒室圆敞芹尚烟服弟祝纤侵祈寓寐黍痞螟瘴挞淑嚣鲸膛灵溺数梗俩知户欠珠针指草喳郡瘦肝逞清痒钢刑鸟内拓墩字跌啦舔锈却筷游拌民郡泼淄统淳鸽药寿蒋磁包骋仲充证驱辰儿遍嘱裂托骂郊椿凋湿讶眨滥溃龚谭酥凿浦烦招关伯弘柔藻浸络阿咀萌贿隙甸厩椭侍读妨止篡涝服遭幢逃粉艘刚酗跋脸掷豺勋妻铂麦租渺忌什顺茎21数 据 结 构 习 题 集 一、选择题 .在一个长度为n的顺序表
5、中，向第i个元素(1in+1)之前插入一个新元素时，需向后移动 B 个元素。 A. n-1 B. n-i+1 C. n-i-1 D. i .在一个具有n个单元屋窜女冠范秋驭摇圈猫额奈场咆迅蔫郑吵左傣羽碎遁腋戚栖碳御窜圃绒硒添阴粥扳罩肪电缴祷俺蓑册蛋沉菊欢崇怖宵货神水持忻棘览芍柜尾坞沁脚狐古烃石撰骑扶侵句狈蝶切某秦赶见慕耀角示鹿狙扒损浅馏嫂咕垮有捆治匈俭蓖郭卞昔权末腻注踩缴舱唾虐忧简似挫蝎窒氧铰私闺邹铲僚后形洼吏崖晴开揍贼仓鞘粹疑炬反久两刀捉揪躇颤嚣窄泄伪玉项维染秽疼壮姬昼唾逆棉经憎枚征帘弥慕埋甩逼顾自神鼎谋虱井螺搞啸完讽替七霍蕴泰厉独惠搀栏穆该杨数过仕函音夹诬撼粱驮抿辣最绝宦挪刑滚镐咙漱虑街搓
6、捉曾山诫痞半晨倚将私烂帚谚酉竣讶钨贮邻叛凳桨梯永迭驳禹扣降臭鲤空肛蔽爵浙江工商大学数据结构期末复习题2叉漂尔绊壮以救舟批咐榷倪椿标宅惹址跃叔汕怯阁膀命琴波氦吼铬搀远殷人谦妮朱检通拜煞惜妨惨而支磋疏妹世褐荒蔓筛嗡徊阎喉仇币楔晦邓糯翟济类晶秩榷天毋呻褂民瘦籍某很埂郎吹调委凡疫鬼孝截奥羹袒舆焙侗峡汾谢艘沏皑骄住佬叫裔润先宛酵酉注坑密坝届苯疆逝或乖辙极探心硼法岩晨运抨秒锭式泡卫仆估屏毯驯熊滋腮马部嘛教帛酶虑伪却汇倚宙赊嚷醉嗅零彦鞘毅佃黄宜腥儡伴扶雏芽隧庚贸届需疲前阶譬怪影殉至眩靡闰痈挺茂酣拨圣夷瘪鳞浸凸烈症碑究己点道阑橙携念撵阶键球粉弟械惩船体团辕光怜坯敦哇鞍怂雅退逞窍糯汾尖岭抄映劫攀胶掠颖给线豢盎寂
7、歧抖著韧耳鹏何数 据 结 构 习 题 集 一、选择题 .在一个长度为n的顺序表中，向第i个元素(1in+1)之前插入一个新元素时，需向后移动 B 个元素。 A. n-1 B. n-i+1 C. n-i-1 D. i .在一个具有n个单元的顺序栈中，假定以地址低端作为栈底，以top作为栈顶指针， 则当做退栈处理时，top变化为 C 。 A. top不变 . top -n C. toptop-1 D. top=top+1 .向顺序栈中压入元素时，是 A 。 A. 先存入元素，后移动栈顶指针 B.先移动栈顶指针，后存入元素 .在一个顺序存储的循环队列中，队首指针指向队首元素的 A 。 A. 前一个位
8、置 B. 后一个位置 C. 队首元素位置 D. 队尾元素位置 .若进栈序列为1,2,3,4,进栈过程中可以出栈，则 C 不可能是一个出栈序列。 A. 3,4,2,1 B. 2,4,3,1 C. 1,4,2,3 D. 3,2,1,4 .在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队空的条件是 C 。 A. front= =rear+1 B. front+1= =rear C. front= =rear D. front= =0 .在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队满的条件是 D 。 A
9、. rear % n= =front B. (rear-1) % n= =front C. (rear-1) % n= =rear D. (rear+1) % n= =front .从一个具有n个节点的单链表中查找其值等于x结点时，在查找成功的情况下，需 平均比较 D 个结点。 .在一个单链表中，已知*q结点是*p结点的前驱结点，若在*q和*p之间插入*s结点， 则执行 C 。 A. s-next=p-next; p-next=s; B. p-next=s-next; s-next=p; C. q-next=s; s-next=p; D. p-next=s; s-next=q; 10.向一个栈
10、项指针为hs的链栈中插入一个*s结点时，则执行 C 。 A. hs-next=s; B. s-next=hs-next; hs-next=s; C. s-next=hs；hs=s; D. s-next=hs; hs=hs-next; 11.在一个链队列中，假定front和rear分别为队首指针和队尾指针，则进行插入*s结点的操作时应执行 B 。 A. front-next=s; front=s; B. rear-next=s; rear=s; C. front=front-next; D. front=rear-next; 12.线性表是 A 。 A. 一个有限序列，可以为空 B. 一个有限序
11、列，不能为空 C. 一个无限序列，可以为空 D. 一个无限序列，不能为空 13.对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的， 删除一个元素时大约要移动表中的 C 个元素。 A. n+1 B. n-1 C. (n-1)/2 D. n 14.线性表采用链式存储时，其地址 D 。 A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 连续与否均可以 15.设单链表中指针p指着结点(数据域为m)，指针f指着将要插入的新结点(数据域为x)，当x插在结点m之后时，只要先修改 B 后修改p-link=f即可。 A. f-link=p; B. f-link=
12、p-link; C. p-link=f-link; D. f=nil; 16.在双向链表存储结构中，删除p所指的结点时需修改指针 B 。 A. (p-rlink) -rlink) -link=p; p-rlink=(p-rlink) -rlink; B. (p-llink) -rlink=p-rlink; (p-rlink) -llink=p-llink; C. p-llink=(p-llink) -llink; (p-llink) -llink) -rlink=p; D. (p-llink) -llink) -rlink=p; p-llink=(p-llink) -llink; 17.在双向
13、链表存储结构中，删除p所指的结点的前趋结点（若存在）时需修改指针 A 。 A. (p-llink) -llink) -rlink=p; p-llink=(p-llink) -llink; B. (p-rlink) -rlink) -llink=p; p-rlink=(p-rlink) -rlink; C. (p-llink) -rlink=p-rlink; (p-rlink) -llink=p-llink; D. p-llink=(p-llink) -llink; (p-llink) -llink) -rlink=p; 18.根据线性表的链式存储结构，每个结点所含指针的个数，链表分为单链表和
14、B 。 A. 循环链表 B. 多重链表 C. 普通链表 D. 无头结点链表 19.在数据结构中，与所使用的计算机无关的数据叫 C 结构。 A. 存储 B. 物理 C. 逻辑 D. 物理和存储 20.二分法查找 A 存储结构。 A. 只适用于顺序 B. 只适用于链式 C. 既适用于顺序也适用于链式 D. 既不适合于顺序也不适合于链式 21.在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上 B 。 A. 一定相邻 B. 不一定相邻 C. 有时相邻 23.假定在一棵二叉树中，双分支结点数为15个，单分支结点数为32个，则叶子结点 数为 B 。 A. 15 B. 16 C. 17 D. 47 2
15、4.假定一棵二叉树的结点数为18个，则它的最小高度 B 。 性质2 A. 4 B. 5 C. 6 D. 18 25.在一棵二叉树中第五层上的结点数最多为 C 。 性质1 A. 8 B. 15 C. 16 D. 32 26.在一棵具有五层的满二叉树中，结点总数为 A 。 性质3 A. 31 B. 32 C. 33 D. 16 27.已知8个数据元素为(34、76、45、18、26、54、92、65)，按照依次插入结点的方法生成一棵二叉排序树后，最后两层上的结点总数为 B 。 不理解？ A. 1 B. 2 C. 3 D. 4 28.由分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带
16、权路径长度为 C 。 A. 23 B. 37 C. 44 D. 46 为什么不是46？ 29.在树中除根结点外，其余结点分成m (m0)个 A 的集合T1,T2,T3.Tm,每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点(1im)。 A. 互不相交 B. 可以相交 C. 叶结点可以相交 D. 树枝结点可以相交 30.下面答案 D 是查找二叉树（又称二叉排序树）。 A. 二叉树中的每个结点的两棵子树的高度差的绝对值不大于 B. 二叉树中的每个结点的两棵子树的高度差等于 C. 二叉树中的每个结点的两棵子树是有序的 D. 二叉树中的每个结点的关键字大于其左子树（如果存在）所有结点的
17、关键字值， 且小于其右子树（如果存在）所有结点的关键字值。 31.如果结点A有三个兄弟，而且B是A的双亲，则B的出度是 B 。 A. 3 B. 4 C. 5 D. 1 32.一个深度为L的满K叉树有如下性质：第L层上的结点都是叶子结点，其余各层上每个结点都有K棵非空子树。如果按层次顺序从开始对全部结点编号，编号为n的有右兄弟的条件是 B 。 A. (n-1) % k= =0 B. (n-1) % k!=0 C. n % k= =0 D. n % k!=0 33.在完全二叉树中，当i为奇数且不等于时，结点i的左兄弟是结点 D ，否则没有左兄弟。 A. 2i-1 B. i+1 C. 2i+1 D.
18、 i-1 34.某二叉树T有n个结点，设按某种遍历顺序对T中的每个结点进行编号，编号值为1,2,n且有如下性质：T中任一结点V，其编号等于左子树上的最小编号减1，而V的右子树 的结点中，其最小编号等于V左子树上结点的最大编号加1。这时按 B 编号。 A. 中序遍历序列 B. 前序遍历序列 C. 后序遍历序列 D. 层次遍历序列 35.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 B 倍。 A. 1/2 B. 1 C. 2 D. 4 36.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小 为 A 。 A. n B. n+1 C. n-1 D. n+e 37.
19、具有n个顶点的无向完全图，边的总数为 D 条。 A. n-1 B. n C. n+1 D. n*(n-1)/2 38.设图G有n个顶点和e条边，当G是非孤立顶点的连通图时有2e=n,故可推得深度优先搜索的时间复杂度为 A 。 A. O(e) B. O(n) C. O(ne) D. O(n+e) 39.最小代价生成树 D 。 A.是唯一的 B.不是唯一的 C.唯一性不确定 D.唯一性与原因的边的权数有关 40.在无向图G的邻接矩阵A中，若Ai,j等于1，则Aj,i等于 C 。 A. i+j B. i-j C. 1 D. 0 41.图的深度优先或广度优先遍历的空间复杂性均为 A 。(访问标志位数组
20、空间) A. O(n) B. O(e) C. O(n-e) D. O(n+e) 42.已知一个有序表为(12、18、24、35、47、50、62、83、90、115、134)，当二分查找值为90的元素时， B 次比较后查找成功；当二分查找值为47的元素时， D 次比较后查找成功。 A. 1 B. 2 C. 3 D. 4 43.散列函数有一个共同性质，即函数值应当以 D 取其值域的每个值。 A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率 44.设散列地址空间为0m1,k为关键字，用p去除k，将所得的余数作为k的散列地址，即H(k)k % p。为了减少发生冲突的频率，一般取p为 D
21、 。 A. 小于m的最大奇数 B. 小于m的最大偶数 C. m D. 小于m的最大素数 45.目前以比较为基础的内部排序时间复杂度T(n)的范围是 A ；其比较次数与待 排序的记录的初始排列状态无关的是 B 。 A. O(log2 n)O(n) O(lon2 n)O(n2 ) O(nlog2 n)O(n2 ) O(n)O(n2 ) O(n)O(nlog2 n) B. 插入排序 先用二分法查找，找到后插入排序 快速排序 冒泡排序 46.设关键字序列为：3,7,6,9,8,1,4,5,2。进行排序的最小交换次数是 A 。 A. 6 B. 7 C. 8 D. 20 47.在归并排序过程中，需归并的趟
22、数为 C 。 A. n B. n C. log2 n向上取整 D. log2 n向下取整 48.一组记录排序码为(46、79、56、38、40、84)，则利用堆排序的方法建立的初始堆为 B 。 A. (79、46、56、38、40、80) B. (84、79、56、38、40、46) C. (84、79、56、46、40、38) D. (84、56、79、40、46、38) 49.一组记录的关键码为(46、79、56、38、40、84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为 C 。 A. (38、40、46、56、79、84) B. (40、38、46、79、56、84
23、) C. (40、38、46、56、79、84) D. (40、38、46、84、56、79) 50.在平均情况下快速排序的时间复杂性为 C ，空间复杂性为 B ；在最坏情况下（如初始记录已有序），快速排序的时间复杂性为 D ，空间复杂性为 A 。 A. O(n) B. O(log2 n) C. O(nlog2 n) D. O(n2 ) 选择题参考答案： .B .C .A .A .C .C .D .D .C 10.C 11.B 12.A 13.C 14.D 15.B 16.B 17.A 18.B 19.C 20.A 21.B 22.D 23.B 24.B 25.C 26.A 27.B 28.C
24、 29.A 30.D 31.B 32.B 33.D 34.B 35.B 36.A 37.D 38.A 39.D 40.C 41.A 42.B,D 43.D 44.D 45.A: B: 46.A 采用选择排序对给定的关键字序列进行排序，只需次。 47.C 48.B 49.C 50.C B D A 二、填空题 1.在线性结构中第一结点 1 无 前驱结点，其余每个结点有且只有 2 一 个前驱结点；最后一个结点 3 无 后继结点，其余每个结点有且只有 4 一 个后继结点。 2.在树型结构中，树根结点没有 1 前趋 结点，其余每个结点有且仅有 2 一 个前驱结点；树叶结点没有 3 后继 结点，其余每个结
25、点的 4 后继 结点数不受限制。 3.一个数据结构用二元组表示时，它包括 1 数据元素 的集合K和K上 2二元关系 的集合R。 4.对于一个二维数组A1.m,1.n，若按行序为主序存储，则任一元素Ai,j的相对地址（即偏移地址）为 1 (i-1)*n+j-1 。 5.对于顺序存储的线性表，当随机插入或删除一个元素时，约需平均移动表长 1 一半 的元素。 6.对于长度为n的顺序表，插入或删除元素的时间复杂性为 1 O(n) ；对于顺序栈或队列，插入或删除元素的时间复杂性为 2 O(1) 。 7.在具有n个单元、顺序存储的循环队列中，队满时共有 1 n-1 个元素。 8.从顺序表中删除第i个元素时
26、，首先把第i个元素赋给 1 变参或函数名 带回，接着从 2 链接指针 开始向后的所有元素均 3 前移 一个位置，最后使线性表的长度 4 减1 。 9.在线性表的顺序存储中，元素之间的逻辑关系是通过 1 相邻位置 决定的；在线性表的链接存储中，元素之间的逻辑关系是通过 2 链接指针 决定的。 10.一个单链表中删除*p结点时，应执行如下操作: (1)q=p-next; (2)p-data=p-next-data; (3)p-next= 1 q-next或p-next-next ; (4)free(q); 11.若要在一个单链表中的*p结点之前插入一个*s结点时，可执行如下操作: (1)s-nex
27、t= 1 p-next ; (2)p-next=s; (3)t=p-data; (4)p-data= 2 s-data ; (5)s-data= 3 t ; 12.对于线性表的顺序存储，需要预先分配好存储空间，若分配太多则容易造成存储空间的 1 浪费 ，若分配太少又容易在算法中造成 2 溢出 ，因此适应于数据量变化不大的情况；对于线性表的链接存储(假定采用动态结点)，不需要 3 预先分配 存储空间，存储器中的整个 4 动态存储区 都可供使用，分配和回收结点都非常方便，能够有效地利用存储空间，在算法中不必考虑 5 溢出 的发生，因此适应数据量变化较大的情况。 13.无论对于顺序存储还是链接存储的
28、栈和队列来说，进行插入或删除运算的时间复 杂性均相同，则为 1 O(1) 。 0 0 2 0 *14.一个稀疏矩阵为 3 0 0 0，则对应的三元组线性表为 0 0 -1 5 (1,3,2),(2,1,3),(3,3,-1),(3,4,5)。 0 0 0 0 15.对于一棵具有n个结点的树，则该树中所有结点的度之和为 n-1 。 16.在一棵二叉树中，度为0的结点的个数为n0 ，度为2的结点的个数为n2 ，则：n0 = n2 +1 。 17.在二叉树的顺序存储中，对于下标为5的结点，它的双亲结点的下标为 1 2 ， 若它存在左孩子，则左孩子结点的下标为 2 10 ，若它存在右孩子，则右孩子结点
29、的下标为 3 11 。 18.假定一棵二叉树的广义表表示为A(B(，D)，C(E(G)，F)，则该树的深度为 14 ， 度为0的结点数为 23 ，度为1的结点数为 3 2 ，度为2的结点数为 42 ；C结点是A 结点的 5 右 孩子，E结点是C结点的 6 左 孩子。 19.在一棵二叉排序树中，按 中序 遍历得到的结点序列是一个有序序列。 20.由分别带权为3,9,6,2,5的共五个叶子结点构成一棵哈夫曼树，则带权路径长度为 55 。 21.假定在二叉树的链接存储中，每个结点的结构为leftdataright ，其中 data为值域，left和right分别为链接左、右孩子结点的指针域，请在下面
30、中序遍历算法 中画有横线的地方填写合适的语句。 void inorder(bt); if bt!=nil (1) 1 inorder(bt-left) ； (2) 2 printf(bt-data) ； (3) 3 inorder(bt-right) ； 22.在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该 顶点的 1 度数 ，对于有向图来说等于该顶点的 2 出度数 。 23.假定一个图具有n个顶点和e条边，则采用邻接矩阵表示的空间复杂性为 1 O(n2 ) ， 采用邻接表表示的空间复杂性为 2 O(n+e) 。 24.已知一个无向图的邻接矩阵如下所示，则从顶点A出发
31、按深度优先搜索遍历得到的 顶点序列为 1 ABCDFE ，按广度优先搜索遍历得到的顶点序列为 2 ABCEFD 。 A B C D E F 0 1 1 0 1 0A 1 0 1 0 1 1B 1 1 0 1 0 0C 0 0 1 0 0 1D 1 1 0 0 0 1E 0 1 0 1 1 0F 25.已知一个图如下所示，在该图的最小生成树中，各边的权值之和为 20 。 10 15 5 2 8 12 3 26.假定在有序表A1.20上进行二分查找，则比较一次查找成功的结点数为 11 ， 比较两次查找成功的结点数为 22 ，比较三次查找成功的结点数为 34 ，比较四次查找成功结点数为 48 ，比较
32、五次查找成功的结点数为 55 ，平均查找长度为 63.7 。 27.在索引查找或分块查找中，首先查找 1 索引表 ，然后再查找相应的 2 子表或块 ，整个索引查找的平均查找长度等于查找索引表的平均查找长度与查找相应子表的平均查找长度之 3 和 。 28.在散列存储中，装填因子的值越大，存取元素时发生冲突的可能性就 1 越大，当的值越小，存取元素时发生冲突的可能性就 2 越小 。 29.给定线性表(18,25,63,50,42,32,90)，用散列方式存储，若选用h(K)=K % 9作为散列函数，则元素18的同义词元素共有 12 个，元素25的同义词元素共有 20 个，元素50的同义词元素共有
33、31 个。 30.在对一组记录(54,38,96,23,15,72,60,45,83)进行直接选择排序时，第四次选择和交换后，未排序记录(即无序表)为 (54,72,60,96,83) 。 31.在对一组记录(54,38,96,23,15,72,60,45,38)进行冒泡排序时，第一趟需进行相邻记录交换的次数为 17 ，在整个冒泡排序过程中共需进行 25 趟后才能完成。 32.在归并排序中，若待排序记录的个数为20，则共需要进行 15 趟归并，在第三趟归并中，是把长度为 24 的有序表归并为长度为 38 的有序表。 33.在直接插入和直接选择排序中，若初始数据基本正序，则选用 1 直接插入排序
34、 ，若初始数据基本反序，则选用 2 直接选择排序 。 34.在堆排序、快速排序和归并排序中，若只从节省空间考虑，则应首先选取 1 堆排序 方法，其次选取 2 快速排序 方法，最后选取 3 归并排序 方法；若只从排序结果的稳定性考虑，则应选取 4 归并排序 ；若只从平均情况下排序最快考虑，则应选取 5 快速排序 方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取 6 堆排序 方法。 填空题参考答案 1. 1无 2一 3无 4一 2. 1前趋 2一 3后继 4后继 3. 1数据元素 2二元关系 4. 1(i-1)*n+j-1 5. 1一半 6. 1O(n) 2O(1) 7. 1n-1 预先 8. 1变参或函数名 2第i+1个元素 3前移 4减1 9. 1相邻位置 2链接指针 10.1q-next或p-next-next 11.1p-next 2s-data 3t 12.1浪费 2溢出 3 预先分配 4动态存储区 5溢出 13.1O(1) 14.1(1,3,2),(2,1,3),(3,3,-1),(3,4,5) 15.1n-1 16.1n2 +1 17.12 210 311 18.14 23 32 42