《数据结构》课程教学资源（作业习题）练习题及答案8

一、填空题（每空1分，共10分） 2.线件有序表( ,是从小到大排列的。对一个给定的值k,用二外法翰索表中与k相 等的元素， 在查找不成功的情况下，最多要检家 次。设有10个结点，用二分法查找时，最大比 较次数是 3.假设在有序线性表20上进行折半查找，则比较一次查找成功的结点数为1：比较两次查找成功的结 点数为2；比较四次查找成功的结点数为8；平均查找长度为37。 解：显然，平均查找长度=0(1⊙g2n)<5次(25。但具体是多少次，则不应当按照公式 4S-”+上og2a+1)来计算（即（21xog221)/20=4.6次并不正确小因为这是在假设n=2m-1的情 况下推导出来的公式。应当用穷举法罗列 全部元素的查找次数为=（1+2×2+4×3+8×4+5×5)=74：ASL=74/20=3.71!! 4.【计研题2000】折半查找有序表(4,6,12,20,28,38,50,70,88,100)，若查找表中元素20， 它将依次与表中元素28,6,12,20比较大小。 二、单项选择题（每小题1分，共27分） (B)1.在表长为的链表中进行线性查找，它的平均查找长度为 ASL=n时 B.AsL=(n+1)/2 C.ASL=n+1;D.ASL1 08:(n+1)-1 (A)2.【计研题2001】折半查找有序表(4,6,10,12,20,30,50,70,88,100)。若查找表中 元素58，则它将依次与表 _比较大小，查找结果是失 A.20,70,30, 30,88,70,50 20,50 D.30,88,50 （C)3.【计研题2001】对22个记录的有序表作折半查找，当查找失败时，至少需要比较 次 关健字。 A.3 B.4 个.5 D.6 8.【97程P18】从供选择的答案中，选出应填入下面叙述？一内的最确切的解答，把相应编号写在 答卷的对应栏 在二叉排序树中，每个结点的关健码值A B 一棵二叉排序，即可得到排序序列。同一个结点 集合，可用不同的二叉排序树表示，人们把平均检索长度最短的二叉排序树称作最佳二叉排序，最佳二叉 排序树在结构上的特点是C。 供选择的答案 ①比左子树所有结点的关键码值大，比右子树所有结点的关键码值小 ②比左子树所有结点的关键码值小，比右子树所有结点的关键码值大 ®比左右子树的所有结点的关键码值都大 ④与左子树所有结点的关健码值和右子树所有结点的关键码值无必然的大小关系 B:①前序意历②中序（对称）遍历 ③后序遗历 ④层次遍历 C:①除最下二层可以不满外，其余都是充满的 ②除最下一层可以不满外，其余都是充满的 风，维个审哥的左子网阿之差的笔对值不天干1④蒙下层的时子在 B=2 C=2

1 一、填空题（每空 1 分，共 10 分） 2. 线性有序表（a1，a2，a3，.，a256)是从小到大排列的，对一个给定的值 k，用二分法检索表中与 k 相 等的元素，在查找不成功的情况下，最多需要检索 8 次。设有 100 个结点，用二分法查找时，最大比 较次数是 7 。 3. 假设在有序线性表 a[20]上进行折半查找，则比较一次查找成功的结点数为 1；比较两次查找成功的结 点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。 解：显然，平均查找长度＝O（log2n）<5 次（25）。但具体是多少次，则不应当按照公式 log ( 1) 1 2 + + = n n n ASL 来计算（即（21×log221）/20＝4.6 次并不正确！）。因为这是在假设 n＝2m-1 的情 况下推导出来的公式。应当用穷举法罗列： 全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL＝74/20=3.7 ！！！ 4．【计研题 2000】折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素 20， 它将依次与表中元素 28，6，12，20 比较大小。 二、单项选择题（每小题 1 分，共 27 分） （ B ）1．在表长为ｎ的链表中进行线性查找，它的平均查找长度为 Ａ. ＡＳＬ＝ｎ; Ｂ. ＡＳＬ＝（ｎ＋１）／２; Ｃ. ＡＳＬ＝ n ＋１; Ｄ. ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１ （ A ）2．【计研题 2001】折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中 元素 58，则它将依次与表中 比较大小，查找结果是失败。 A．20，70，30，50 B．30，88，70，50 C．20，50 D．30，88，50 （ C ）3．【计研题 2001】对 22 个记录的有序表作折半查找，当查找失败时，至少需要比较 次 关键字。 A．3 B．4 C．5 D． 6 8. 【97 程 P18】 从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在 答卷的对应栏内。 在二叉排序树中，每个结点的关键码值 A ， B 一棵二叉排序，即可得到排序序列。同一个结点 集合，可用不同的二叉排序树表示，人们把平均检索长度最短的二叉排序树称作最佳二叉排序，最佳二叉 排序树在结构上的特点是 C 。 供选择的答案 A： ①比左子树所有结点的关键码值大，比右子树所有结点的关键码值小 ②比左子树所有结点的关键码值小，比右子树所有结点的关键码值大 ③比左右子树的所有结点的关键码值都大 ④与左子树所有结点的关键码值和右子树所有结点的关键码值无必然的大小关系 B: ①前序遍历 ② 中序（对称）遍历 ③ 后序遍历 ④ 层次遍历 C：① 除最下二层可以不满外，其余都是充满的 ②除最下一层可以不满外，其余都是充满的 ③ 每个结点的左右子树的高度之差的绝对值不大于 1 ④ 最下层的叶子必须在最左边 答案：A＝ ① B＝ ② C＝ ②

三、简答题（每小题4分，共16分） 1,【全国专升本题】对分（折半）查找适不适合链表结构的序列，为什么？用二分查找的查找速度必然比 线性查找的速度快，这种说法对吗？ 答：不适合！虽然有序的单链表的结点是按从小到大（或从大到小）顺序排列，但因其存储结构为单链表， 查找结点时只能从头指针开始逐步搜素，故不能进行折半查找。 二分查找的速度在一般情况下是快些，但在特殊情况下未必快。例如所查数据位于首位时，则线性查找快： 而二分查找则慢得多。 2.【计研题1999】假定对有序表：(3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找，试 回答下列问题： (1)画出描述折半查我过程的判定树： (2)若查找元素54，需依次与哪些元素比较？ (3)若查找元素90，需依次与哪些元素比较？ 假定每个元素的查找概率相等，求查找成功时的平均查找长度。 解： (1)先画出判定树如下（注：mid凡(1+12）/26)： 30 42 424547295 (2)查找元素54，需依次与30,63,42,54等元素比较： (3)查找元素90， 福依次与30,6 ,87,95, 等元素比较 (4)求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找1+2×2+4X3=17次： 但最后一层未满，不能用8×4，只能用5×4=20次， 所以ASL=1/12(17+20)=37/12≈3.08 3.【全国专升本题】用比较两个元素大小的方法在一个给定的序列中查找某个元素的时间复杂度下限是 什么？如果要求时间复杂度更小，你采用什么方法？此方法的时间复杂度是多少 答：查找某个元素的时间复杂度下限，如果理解为最短查找时间，则当关键字值与表头元素相同时。比较 1次即可。 低时间复杂度，可以改用Hash查找 。此方法对表内每个元素的比较次数都是0(1)。 4.【计研题1999】设哈希(Hah)表的地址范围为0~17，哈希函数为：H(K)=KM0D16。 K为关键字，用线性探测法再散列法处理冲突，输入关键字序列： 0, 32,17 31,30,46,47,40,63,49) 造出Hash表，试回答下列问题： (1)画出哈希表的示意图： (2)若查找关键字63，需要依次与哪些关键字进行比较？ (3)芳者找关字60，需要依次与哪些关罐字比较？ (4)假定每个关健字的查找概率相等，求查找成功时的平均查找长度， 解：(1)画表如下：

2 三、简答题（每小题 4 分，共 16 分） 1.【全国专升本题】对分（折半）查找适不适合链表结构的序列，为什么？用二分查找的查找速度必然比 线性查找的速度快，这种说法对吗？ 答：不适合！虽然有序的单链表的结点是按从小到大（或从大到小）顺序排列，但因其存储结构为单链表， 查找结点时只能从头指针开始逐步搜索，故不能进行折半查找。 二分查找的速度在一般情况下是快些，但在特殊情况下未必快。例如所查数据位于首位时，则线性查找快； 而二分查找则慢得多。 2.【计研题 1999】假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试 回答下列问题： （1） 画出描述折半查找过程的判定树； （2） 若查找元素 54，需依次与哪些元素比较？ （3） 若查找元素 90，需依次与哪些元素比较？ （4） 假定每个元素的查找概率相等，求查找成功时的平均查找长度。 解： （1） 先画出判定树如下（注：mid=(1+12)/2=6）： 30 5 63 3 7 42 87 4 24 54 72 95 (2) 查找元素 54，需依次与 30, 63, 42, 54 等元素比较； (3) 查找元素 90，需依次与 30, 63,87, 95, 72 等元素比较； （4） 求 ASL 之前，需要统计每个元素的查找次数。判定树的前 3 层共查找 1＋2×2＋4×3=17 次； 但最后一层未满，不能用 8×4，只能用 5×4=20 次， 所以 ASL＝1/12（17＋20）＝37/12≈3.08 3. 【全国专升本题】用比较两个元素大小的方法在一个给定的序列中查找某个元素的时间复杂度下限是 什么? 如果要求时间复杂度更小,你采用什么方法？此方法的时间复杂度是多少? 答：查找某个元素的时间复杂度下限，如果理解为最短查找时间，则当关键字值与表头元素相同时，比较 1 次即可。要想降低时间复杂度，可以改用 Hash 查找法。此方法对表内每个元素的比较次数都是 O（1）。 4. 【计研题 1999】设哈希（Hash）表的地址范围为 0～17，哈希函数为：H（K）＝K MOD 16。 K 为关键字，用线性探测法再散列法处理冲突，输入关键字序列： （10，24，32，17，31，30，46，47，40，63，49） 造出 Hash 表，试回答下列问题： （1） 画出哈希表的示意图； （2） 若查找关键字 63，需要依次与哪些关键字进行比较？ （3） 若查找关键字 60，需要依次与哪些关键字比较？ （4） 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 解： （1）画表如下：

0123456789101121314151617 32176349 24401030314647 (2)查找63，首先要与H(63)=63%16-15号单元内容比较，即63v831,n0: 然后顺移，与46,47,32,17,63相比，一共比较了6次1 (3)查找60，首先要与H(60=60%16=12号单元内容比较，但因为12号单元为空（应当有空标记），所以 应当只比较这一次即可。 (4)对于黑色数据元素，各比较1次：共6次： 对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需 要3次，“47”需要3次， 所以ASL=1/11(6+2+3×3)=1711=1.5454545454≈1.55 四、分析题（每小题6分，共24分） 1.【严题集9.3②】画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均 杏投长度。 解：判定树应当描述每次查找的位置 ASL=1/10(1+2×2+3×4+4×3) =1/10(1+4+12+12) =29/10=2.9 2.【全国专升本考题】在一棵空的二叉查找树中依次插入关健字序列为12,7,17,1山，16,2,13,9， 21,4,请画出所得到的二叉查找树。 答： 12、 21 4 验算方法：用中序遍历应得到排序结果：2,4,7,9,11,12,13,16,17,21 4.选取散列函数(ky)=(3*ke）%1山，用线性探测法处理冲突，对下列关键码序列构造一个散列地 址空间为0一10，表长为11的散列表，22,41,53,08,46,30,01,31,66。 解：由题意知，m=11(刚好为素数) 地址值 则(22*3)%11=6.0 (41*3)%11=11.2 41 .2 4.7 (46*3)%11=12*+( (30*3)%11=82 (01*3)%11=0*3 (31*3%11=8.5 (66*3)%11=9 .0 22T6641T830T53T46T1T31TT☐ 3

3 地址 值 链接指针 0 22 1 1 66 2 41 3 3 08 4,7 4 30 5 53 6 46 7 01 8 31 9 10 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 32 17 63 49 24 40 10 30 31 46 47 （2） 查找 63,首先要与 H(63)=63%16=15 号单元内容比较，即 63 vs 31 ,no; 然后顺移，与 46,47,32,17,63 相比，一共比较了 6 次！ （3）查找 60,首先要与 H(60)=60%16=12 号单元内容比较，但因为 12 号单元为空（应当有空标记），所以 应当只比较这一次即可。 （4） 对于黑色数据元素，各比较 1 次；共 6 次； 对红色元素则各不相同，要统计移位的位数。“63”需要 6 次，“49”需要 3 次，“40”需要 2 次，“46”需 要 3 次，“47”需要 3 次， 所以 ASL=1/11（6＋2＋3×3）＝17/11=1.5454545454≈1.55 四、分析题（每小题 6 分，共 24 分） 1. 【严题集 9.3②】画出对长度为 10 的有序表进行折半查找的判定树，并求其等概率时查找成功的平均 查找长度。 解：判定树应当描述每次查找的位置： 5 2 8 1 3 6 9 4 7 10 2. 【全国专升本考题】在一棵空的二叉查找树中依次插入关键字序列为 12，7，17，11，16，2，13，9， 21，4，请画出所得到的二叉查找树。 答： 12 7 17 2 11 16 21 4 9 13 验算方法： 用中序遍历应得到排序结果： 2,4,7,9,11,12,13,16,17，21 4. 选取散列函数 H（key）=（3*key）%11，用线性探测法处理冲突，对下列关键码序列构造一个散列地 址空间为 0～10，表长为 11 的散列表，{22，41，53，08，46，30，01，31，66}。 解：由题意知，m=11(刚好为素数) 则(22*3)%11=6.0 (41*3)%11=11.2 (53*3)%11=14.5 (08*3)%11=2.2 (46*3)%11=12.6 (30*3)%11=8.2 (01*3)%11=0.3 (31*3)%11=8.5 (66*3)%11=9.0 22 66 41 8 30 53 46 1 31 ASL＝1/10（1＋2×2＋3×4＋4×3） ＝1/10（1＋4＋12＋12） ＝29/10=2.9

12 345678910 41

4 0 1 2 3 4 5 6 7 8 9 10 1 3 4，7