1、计算机专业基础综合数据结构（查找）历年真题试卷汇编 1 及答案解析(总分：108.00，做题时间：90 分钟)一、单项选择题(总题数：34，分数：76.00)1.顺序查找法适合于存储结构为_的线性表。【北京航空航天大学 2002 年】（分数：2.00）A.顺序存储结构或链式存储结构B.散列存储结构C.索引存储结构D.压缩存储结构2.若查找每个记录的概率均等，则在具有 n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度(ASL)为_。【北京航空航天大学 2004 年】（分数：2.00）A.(n1)2B.n2C.(n+1)2D.n3.当采用分块查找时，数据的组织方式为_。【太原科
2、技大学 2007 年】（分数：2.00）A.数据分成若干块，每块内数据有序B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块C.数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块D.数据分成若干块，每块(除最后一块外)中数据个数需相同4.对有 2500 个记录的索引顺序表(分块表)进行查找，最理想的块长为_。【华中科技大学 2007 年】（分数：2.00）A.50B.125C.500D.log 2 25005.下面关于二分查找的叙述正确的是_。【南京理工大学 1996 年】（分数：2.00）A.表必须有序，表可以顺序方式存储，也可以链
3、表方式存储B.表必须有序且表中数据必须是整型、实型或字符型C.表必须有序，而且只能从小到大排列D.表必须有序，且表只能以顺序方式存储6.当 n 足够大时，在按值有序的顺序表中进行折半查找，当查找概率相等的情况下，其查找成功的平均查找长度是_。【北京航空航天大学 2002 年】（分数：2.00）A.(n+1)2B.n2C.log 2 (n+1)一 1D.log 2 (n+1)7.在具有 15 个记录的排序连续顺序文件上采用折半查找方法查找一个文件中不存在的记录需要进行_次关键字值的比较。【北京航空航天大学 2004 年】（分数：2.00）A.0B.4C.5D.158.对一个长度为 50 的有序表
4、进行折半查找，最多比较_次就能查找出结果。【北京邮电大学 2005 年】（分数：2.00）A.6B.7C.8D.99.已知一个有序表(13，18，24，35，47，50，62，83，90，115，134)，当二分查找值为 90 的元素时，查找成功的比较次数为_。【浙江大学 2004 年】（分数：2.00）A.1B.2C.4D.610.折半查找有序表(2，10，25，35，40，65，70，75，81，82，88，100)，若查找元素 75，需依次与表中元素_进行比较。【华中科技大学 2007 年】（分数：2.00）A.6582，75B.70，82，75C.65，8l，75D.65，81，70，
5、7511.折半查找过程所对应的判定树是一棵_。【北京交通大学 2007 年】（分数：2.00）A.最小生成树B.平衡二叉树C.完全二叉树D.赫夫曼树12.对表长为 n 的有序表进行折半查找，其判定树高度为_。【北京交通大学 2004 年】（分数：2.00）A.log 2 (n+1)B.log 2 (n+1)C.log 2 nD.log 2 n13.图 5-1 是一棵_。【华南理工大学 2007 年】 （分数：2.00）A.4 阶 B-树B.4 阶 B+树C.3 阶 B-树D.3 阶 B+树14.下列关于 m 阶 B-树的说法错误的是_。【南京理工大学 1997 年】（分数：2.00）A.根结点
6、至多有 m 棵子树B.所有叶子都在同一层次上C.非叶结点至少有 m2(m 为偶数)或 m2+1(m 为奇数)棵子树D.根结点中的数据是有序的15.当向 B-树插入关键字时，可能引起结点的_；最终可能导致整个 B-树的高度_。【浙江大学2004 年】（分数：2.00）A.合并B.增加 1C.分裂D.减少 116.m 阶 B-树的每个分支结点中最多包含_个关键字值。【北京航空航天大学 2007 年】（分数：2.00）A.m2B.m 一 1C.mD.m+117.在一棵 m 阶 B-树中，若在某结点中插入一个新关键字而引起该结点的分裂，则此结点中原有的关键字的个数是_。【湖南大学 2003 年】（分数
7、：2.00）A.mB.m+1C.m1D.m218.理想情况下，散列表的平均比较次数为_。【北京邮电大学 2005 年】（分数：2.00）A.1B.2C.4D.n19.设有一组记录的关键字为19，14，23，1，68，20，84，27，55，11，10，79，用链地址法构造散列表，散列函数为 H(key)=keyMOD13，散列地址为 1 的链中有_个记录。【南京理工大学 1997 年】（分数：2.00）A.1B.2C.3D.4若采用链地址法构造散列表，散列函数为 H(key)=keyMOD17，则需 (1) 个链表。这些链的链首指针构成一个指针数组，数组的下标范围为 (2) 。【南京理工大学
8、1999 年】（分数：4.00）(1).(1)（分数：2.00）A.17B.13C.16D.任意(2).(2)（分数：2.00）A.017B.117C.016D.11620.关于杂凑查找说法不正确的有_个。【南京理工大学 2000 年】(1)采用链地址法解决冲突时，查找一个元素的时间是相同的(2)采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的(3)用链地址法解决冲突易引起聚集现象(4)再散列法不易产生聚集（分数：2.00）A.1B.2C.3D.4散列表的地址区间为 017，散列函数为 H(K)=Kmod17。采用线性探测法处理冲突，并将关键字序列26，25，72，
9、38，8，18，59 依次存储到散列表中。【北京交通大学 2001 年】（分数：4.00）(1).元素 59 存放在散列表中的地址是_。（分数：2.00）A.8B.9C.10D.11(2).存放元素 59 需要搜索的次数是_。（分数：2.00）A.2B.3C.4D.521.采用链地址法解决冲突的散列表中，查找成功的平均查找长度_。【北京交通大学 2007 年】（分数：2.00）A.直接与关键字个数有关B.直接与装填因子有关C.直接与表的容量有关D.直接与散列函数有关22.在采用链地址法处理冲突所构成的散列表上查找某一关键字，则在查找成功的情况下，所探测的这些位置上的键值_。【北京交通大学 20
10、06 年】（分数：2.00）A.一定都是同义词B.不一定都是同义词C.都相同D.一定都不是同义词23.设初始为空的散列表的地址空间为(O10)，散列函数为 H(k)=kmod11，采用线性探测再散列法处理冲突，若依次插入关键字 37，95，27，14，48，则最后一个关键字值 48 的插入位置是_。【北京航空航天大学 2007 年】（分数：2.00）A.4B.5C.6D.724.在构造散列表方面，下面的说法_是正确的。【华南理工大学 2006 年】（分数：2.00）A.再散列法在处理冲突时不会产生聚集B.散列表的装填因子越大，说明空间利用率越好，因此应使装填因予尽量大C.散列函数选的好可减少冲
11、突现象D.对于任何具体关键字都不可能找到不产生冲突的散列函数25.将 10 个元素散列到 100000 个单元的散列表中，则_产生冲突。【北京邮电大学 2001 年】（分数：2.00）A.一定会B.一定不会C.仍可能会26.用二分(对半)查找表的元素的速度比用顺序法_。【南京理工大学 1998】（分数：2.00）A.必然快B.必然慢C.相等D.不能确定27.折半查找的时间复杂度为_。【中山大学 1999 年】【华南理工大学 2007 年】（分数：2.00）A.O(n 2 )B.O(n)C.O(nlog 2 n)D.O(log 2 n)28.在等概率情况下，线性表的顺序查找的平均查找长度(ASL
12、)为_，有序表的折半查找的 ASL，为_。【上海海事大学 1999 年】（分数：2.00）A.O(1)B.O(log 2 n)C.O(log 2 n) 2 )D.O(nlog 2 n)EO(n)29.衡量查找算法性能好坏的主要标准是_。【北京航空航天大学 2004 年】（分数：2.00）A.参加比较的关键字值的多少B.被查找的关键字值在关键字序列中的位置C.关键字值序列中是否存在被查找关键字值D.关键字值的平均比较次数的多少30.只能在顺序存储结构上进行的查找方法是_。【北京航空航天大学 2005 年】（分数：2.00）A.顺序查找法B.折半查找法C.树型查找法D.散列查找法若采用链地址法构造
13、散列表，散列函数为 H(key)=keyMOD17，则需 (1) 个链表。这些链的链首指针构成一个指针数组，数组的下标范围为 (2) 。【南京理工大学 1999 年】（分数：4.00）(1).(1)（分数：2.00）A.17B.13C.16D.任意(2).(2)（分数：2.00）A.017B.117C.016D.116散列表的地址区间为 017，散列函数为 H(K)=Kmod17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59 依次存储到散列表中。【北京交通大学 2001 年】（分数：4.00）(1).元素 59 存放在散列表中的地址是_。（分数：2.00）A.8
14、B.9C.10D.11(2).存放元素 59 需要搜索的次数是_。（分数：2.00）A.2B.3C.4D.5二、综合题(总题数：7，分数：32.00)假定折半查找表长为 10 的有序表：【华中科技大学 2006 年】（分数：4.00）(1).试画出描述折半查找过程的带外表结点(表示查找不成功情况的结点)的判定树。（分数：2.00）_(2).假定每个元素的查找概率相等，试计算查找成功时的平均查找长度。（分数：2.00）_31.写出二分查找的递归程序。【北京交通大学 2006 年】初始调用时，low 为 1，high 为ST.1ength。（分数：2.00）_32.请写一非递归算法，该算法在按值严
15、格递增排序的顺序表 A【1n】中采用折半查找法查找值不小于item 的最小元素。若表中存在这样的元素，则算法给出该最小元素在表中的位置，否则，给出信息0。【北京航空航天大学 2007 年】（分数：2.00）_对图 5-2 所示的 3 阶 B-树，依次执行下列操作，画出各步操作的结果。【合肥工业大学 1999 年】（分数：10.00）(1).插入 90（分数：2.00）_(2).插入 25（分数：2.00）_(3).插入 45（分数：2.00）_(4).删除 60（分数：2.00）_(5).删除 80（分数：2.00）_对下面的关键字集30，15，21，40，25，26，36，37)若查找表的装
16、填因子为 08，采用线性探测再散列方法解决冲突，做：（分数：8.00）(1).设计散列函数。（分数：2.00）_(2).画出散列表。（分数：2.00）_(3).计算查找成功和查找失败的平均查找长度。（分数：2.00）_(4).写出将散列表中某个数据元素删除的算法。【东北大学 2001 年】（分数：2.00）_设散列函数 H(K)=3Kmod11，散列地址空间为 010，对关键字序列(32，13，49，24，38，21，4，12)按下述两种解决冲突的方法构造散列表：（分数：4.00）(1).线性探测再散列。（分数：2.00）_(2).链地址法。并分别求出等概率下查找成功时和查找失败时的平均查找长
17、度 ASLSUCO 和ASLunsucc。【北方交通大学 1998 年】（分数：2.00）_33.将一组数据元素按散列函数 H(key)散列到散列表 H(0m)中，用线性探测法处理冲突(H(key)+1、H(key)+2、H(key)一 1)，假设空单元用 EMPTY 表示，删除操作是将散列表中结点标志位从INIJSE 标记为 DELETED，试写出该散列表的查找、插入和删除三个基本操作算法。【北京邮电大学 2001年】（分数：2.00）_计算机专业基础综合数据结构（查找）历年真题试卷汇编 1 答案解析(总分：108.00，做题时间：90 分钟)一、单项选择题(总题数：34，分数：76.00)
18、1.顺序查找法适合于存储结构为_的线性表。【北京航空航天大学 2002 年】（分数：2.00）A.顺序存储结构或链式存储结构 B.散列存储结构C.索引存储结构D.压缩存储结构解析：解析：考查顺序查找的适合结构。顺序查找从线性表的一端开始，逐个检查关键字是否满足给定的条件。存储结构为顺序存储或链式存储。2.若查找每个记录的概率均等，则在具有 n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度(ASL)为_。【北京航空航天大学 2004 年】（分数：2.00）A.(n1)2B.n2C.(n+1)2 D.n解析：解析：考查顺序查找法平均查找长度。查找第 1 个记录的查找长度为 1，
19、查找第 n 个记录的查找长度为 n，查找每个记录的概率为 1n。ASL 为n(1+n)2n=(n+1)2。3.当采用分块查找时，数据的组织方式为_。【太原科技大学 2007 年】（分数：2.00）A.数据分成若干块，每块内数据有序B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块 C.数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块D.数据分成若干块，每块(除最后一块外)中数据个数需相同解析：解析：考查分块查找的定义。分块查找要求将查找表按照关键码的区间分成若干个子表，并对子表建立索引表。索引表有序，子表不一定有序。子表中最大或最小
20、的数据组成索引块。4.对有 2500 个记录的索引顺序表(分块表)进行查找，最理想的块长为_。【华中科技大学 2007 年】（分数：2.00）A.50 B.125C.500D.log 2 2500解析：解析：考查分块查找的最优块长。分块查找的平均查找长度不仅和表的总长度 n 有关，而且和所分的子表个数 s 有关，对于 n 给定的情况下，s 取 时，ASL 取得最小值5.下面关于二分查找的叙述正确的是_。【南京理工大学 1996 年】（分数：2.00）A.表必须有序，表可以顺序方式存储，也可以链表方式存储B.表必须有序且表中数据必须是整型、实型或字符型C.表必须有序，而且只能从小到大排列D.表必
21、须有序，且表只能以顺序方式存储 解析：解析：考查折半查找的条件。顺序查找只要求是线性表，顺序存储还是链式存储都可以，元素不要求有序。折半查找要求以顺序方式存储且数据元素有序。6.当 n 足够大时，在按值有序的顺序表中进行折半查找，当查找概率相等的情况下，其查找成功的平均查找长度是_。【北京航空航天大学 2002 年】（分数：2.00）A.(n+1)2B.n2C.log 2 (n+1)一 1 D.log 2 (n+1)解析：解析：考查折半查找平均查找长度的计算。在等概率查找时，查找成功的平均查找长度为 7.在具有 15 个记录的排序连续顺序文件上采用折半查找方法查找一个文件中不存在的记录需要进行
22、_次关键字值的比较。【北京航空航天大学 2004 年】（分数：2.00）A.0B.4 C.5D.15解析：解析：考查折半查找不存在的记录所需比较次数。可以通过分析判定树的方式计算。判定树中共有4 层，是一棵满二叉树。查找一个文件中不存在的记录需要进行 4 次比较。8.对一个长度为 50 的有序表进行折半查找，最多比较_次就能查找出结果。【北京邮电大学 2005 年】（分数：2.00）A.6 B.7C.8D.9解析：解析：考查折半查找最多比较次数的计算。对应判定树总共 6 层，其中，第 6 层未满。所以比较次数最多为 6 次。9.已知一个有序表(13，18，24，35，47，50，62，83，9
23、0，115，134)，当二分查找值为 90 的元素时，查找成功的比较次数为_。【浙江大学 2004 年】（分数：2.00）A.1B.2 C.4D.6解析：解析：考查折半查找某元素的详细过程。开始时 low 指向 13，high 指向 134，mid 指向 50，比较第 1 次 9050，所以将 low 指向 62，high 指向 134，mid 指向 90，第 2 次比较找到 90.10.折半查找有序表(2，10，25，35，40，65，70，75，81，82，88，100)，若查找元素 75，需依次与表中元素_进行比较。【华中科技大学 2007 年】（分数：2.00）A.6582，75B.7
24、0，82，75C.65，8l，75D.65，81，70，75 解析：解析：考查折半查找某元素的详细过程。开始时 low 指向 2，high 指向 100，mid 指向 65。第 1 次比较 7565。然后 low 指向 70，high 指向 100，mid 指向 81。第 2 次比较，7570。low 指向 75，high 指向 75，mid 指向 75。第 4 次比较查找成功。11.折半查找过程所对应的判定树是一棵_。【北京交通大学 2007 年】（分数：2.00）A.最小生成树B.平衡二叉树 C.完全二叉树D.赫夫曼树解析：解析：考查折半查找判定树的类型。判定树只有最低一层有可能不满，其他
25、各层都是满的。最低一层叶子结点不一定全在左边，所以不一定是完全二叉树，是一棵平衡二叉树。12.对表长为 n 的有序表进行折半查找，其判定树高度为_。【北京交通大学 2004 年】（分数：2.00）A.log 2 (n+1) B.log 2 (n+1)C.log 2 nD.log 2 n解析：解析：考查折半查找判定树的高度。判定树只有最低一层有可能不满。类似完全二叉树的计算过程，可得，高度应该为log 2 (n+1)或者log 2 (n)+1。13.图 5-1 是一棵_。【华南理工大学 2007 年】 （分数：2.00）A.4 阶 B-树 B.4 阶 B+树C.3 阶 B-树D.3 阶 B+树解
26、析：解析：考查 B 树的识别。关键字数目比子树数目少 1，所以不是 B+树，是 B 树。又有 m 阶 B 树结点关键字数最多为 m 一 1，有一个结点关键字个数为 3，所以，不可能为 3 阶。14.下列关于 m 阶 B-树的说法错误的是_。【南京理工大学 1997 年】（分数：2.00）A.根结点至多有 m 棵子树B.所有叶子都在同一层次上C.非叶结点至少有 m2(m 为偶数)或 m2+1(m 为奇数)棵子树 D.根结点中的数据是有序的解析：解析：考查 B 树的相关性质。除根之外的所有非终端结点至少有m2棵子树。对于根结点，最多有 m 棵子树，若不是叶子结点至少有 2 棵子树。15.当向 B-
27、树插入关键字时，可能引起结点的_；最终可能导致整个 B-树的高度_。【浙江大学2004 年】（分数：2.00）A.合并B.增加 1C.分裂 D.减少 1解析：解析：B。考查 B-树的插入。如果遇到添加新关键字使得某结点个数超过了上限，引起结点分裂，则将其按中间一个关键字为界分裂两个新的结点，分别包含m21 和 mm2个关键字，而将中间的第m2个关键字添加到其父结点中去。若此时导致其父结点也超过了上限，则继续这种分裂操作。最终可能导致 B-树高度加 1。16.m 阶 B-树的每个分支结点中最多包含_个关键字值。【北京航空航天大学 2007 年】（分数：2.00）A.m2B.m 一 1 C.mD.
28、m+1解析：解析：考查 B-树结点关键字个数。B-树中每个结点至多有 m 棵子树，m 一 1 个关键字值。17.在一棵 m 阶 B-树中，若在某结点中插入一个新关键字而引起该结点的分裂，则此结点中原有的关键字的个数是_。【湖南大学 2003 年】（分数：2.00）A.mB.m+1C.m1 D.m2解析：解析：考查 B-树结点关键字最大限制。m 阶 B 树中结点最大关键字数目为 m 一 1。18.理想情况下，散列表的平均比较次数为_。【北京邮电大学 2005 年】（分数：2.00）A.1 B.2C.4D.n解析：解析：考查散列表的理想甲均比较次数。敞列表平均比较次数和装填因了直接相关，在最理想情
29、况下，散列表的平均比较次数为 1，通过散列函数直接计算即可得到元素位置。19.设有一组记录的关键字为19，14，23，1，68，20，84，27，55，11，10，79，用链地址法构造散列表，散列函数为 H(key)=keyMOD13，散列地址为 1 的链中有_个记录。【南京理工大学 1997 年】（分数：2.00）A.1B.2C.3D.4 解析：解析：考查通过散列函数计算散列地址。易得，14，1，27，79 的散列地址为 1。若采用链地址法构造散列表，散列函数为 H(key)=keyMOD17，则需 (1) 个链表。这些链的链首指针构成一个指针数组，数组的下标范围为 (2) 。【南京理工大学
30、 1999 年】（分数：4.00）(1).(1)（分数：2.00）A.17 B.13C.16D.任意解析：(2).(2)（分数：2.00）A.017B.117C.016 D.116解析：解析：考查链地址法构造散列表。根据散列函数可得，最终计算的地址共有 17 种可能，所以需要17 个链表。指针数组中下标从 0 开始，共 17 个地址。20.关于杂凑查找说法不正确的有_个。【南京理工大学 2000 年】(1)采用链地址法解决冲突时，查找一个元素的时间是相同的(2)采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的(3)用链地址法解决冲突易引起聚集现象(4)再散列法不易产
31、生聚集（分数：2.00）A.1B.2 C.3D.4解析：解析：考查散列查找法的几种冲突解决办法。链地址法解决冲突时查找一个元素可能需要在链表中遍历，所需时间不一样。聚集又称堆积，是指散列地址不同的结点争夺同一个后继散列地址的现象。注意：同义词发生冲突不是聚集，链地址法解决冲突时将同义词放在同一个链表中，不会引起聚集现象。散列表的地址区间为 017，散列函数为 H(K)=Kmod17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59 依次存储到散列表中。【北京交通大学 2001 年】（分数：4.00）(1).元素 59 存放在散列表中的地址是_。（分数：2.00）A.
32、8B.9C.10D.11 解析：(2).存放元素 59 需要搜索的次数是_。（分数：2.00）A.2B.3C.4 D.5解析：解析：考查线性探测法实现的散列表的散列过程。将前面各元素分别放入散列表中，其中8、9、10 的位置分别存放 25、26、8。元素 59 经过散列函数计算应该存入位置 8，有冲突，采用线性探测再散列，依次比较 9、10、11，发现 11 为空，所以放入 11 中。总过程需搜索 4 次。21.采用链地址法解决冲突的散列表中，查找成功的平均查找长度_。【北京交通大学 2007 年】（分数：2.00）A.直接与关键字个数有关B.直接与装填因子有关 C.直接与表的容量有关D.直接
33、与散列函数有关解析：解析：考查链地址法散列表查找成功的平均查找长度的决定因素。实际上，散列表的平均性能依赖于散列表的装载因子 ，并不直接依赖于关键字个数或表长，见表 5-1。22.在采用链地址法处理冲突所构成的散列表上查找某一关键字，则在查找成功的情况下，所探测的这些位置上的键值_。【北京交通大学 2006 年】（分数：2.00）A.一定都是同义词 B.不一定都是同义词C.都相同D.一定都不是同义词解析：解析：考查链地址法散列表的查找。在此种散列表中，同一条链中存放的元素必然是同义词。每次查找时先计算元素在表中的位置，然后遍历链，直到找到所查找元素为止。23.设初始为空的散列表的地址空间为(O
34、10)，散列函数为 H(k)=kmod11，采用线性探测再散列法处理冲突，若依次插入关键字 37，95，27，14，48，则最后一个关键字值 48 的插入位置是_。【北京航空航天大学 2007 年】（分数：2.00）A.4B.5C.6 D.7解析：解析：考查线性探测法实现的散列表的插入。前 4 个元素分别插入到 4、7、5、3 的位置上，关键字 48 的元素通过散列函数计算得应插入到位置 4 当中，有冲突，依次探测 5、6，发现 6 为空则插入。24.在构造散列表方面，下面的说法_是正确的。【华南理工大学 2006 年】（分数：2.00）A.再散列法在处理冲突时不会产生聚集B.散列表的装填因子
35、越大，说明空间利用率越好，因此应使装填因予尽量大C.散列函数选的好可减少冲突现象 D.对于任何具体关键字都不可能找到不产生冲突的散列函数解析：解析：考查散列表相关性质。再散列法也可能产生聚集。装填因予越大，则空闲空间越少，探测的次数便越多，平均查找长度变长。对于具体的关键字可以找到不产生冲突的散列函数。25.将 10 个元素散列到 100000 个单元的散列表中，则_产生冲突。【北京邮电大学 2001 年】（分数：2.00）A.一定会B.一定不会C.仍可能会 解析：解析：考查冲突的产生。无论散列表表长多大，只要插入的元素不止一个，通过散列函数计算的插入位置便有可能相同。26.用二分(对半)查找
36、表的元素的速度比用顺序法_。【南京理工大学 1998】（分数：2.00）A.必然快B.必然慢C.相等D.不能确定 解析：解析：考查折半查找和顺序查找的速度比较。27.折半查找的时间复杂度为_。【中山大学 1999 年】【华南理工大学 2007 年】（分数：2.00）A.O(n 2 )B.O(n)C.O(nlog 2 n)D.O(log 2 n) 解析：解析：考查折半查找的时间复杂度。28.在等概率情况下，线性表的顺序查找的平均查找长度(ASL)为_，有序表的折半查找的 ASL，为_。【上海海事大学 1999 年】（分数：2.00）A.O(1)B.O(log 2 n) C.O(log 2 n)
37、2 )D.O(nlog 2 n)EO(n)解析：解析：考查顺序查找和折半查找的 ASL。顺序查找的平均查找长度为(n+1)2，折半查找查找成功的 ASL 为(n+1)，n10g 2 (n+1)1。29.衡量查找算法性能好坏的主要标准是_。【北京航空航天大学 2004 年】（分数：2.00）A.参加比较的关键字值的多少B.被查找的关键字值在关键字序列中的位置C.关键字值序列中是否存在被查找关键字值D.关键字值的平均比较次数的多少 解析：解析：考查查找算法性能的衡量方式。关键字值的平均比较次数越少，查找时间越短，算法的性能越好。30.只能在顺序存储结构上进行的查找方法是_。【北京航空航天大学 20
38、05 年】（分数：2.00）A.顺序查找法B.折半查找法 C.树型查找法D.散列查找法解析：解析：考查各种查找所要求的存储结构。顺序查找可以是顺序存储或者链式存储，折半查找只能是顺序存储并且元素值有序，树型查找法要求采用树的存储结构，即可以采用顺序存储也可以采用链式，散列查找中连接法解决冲突的时候是采用顺序存储与链式存储结合的方式。若采用链地址法构造散列表，散列函数为 H(key)=keyMOD17，则需 (1) 个链表。这些链的链首指针构成一个指针数组，数组的下标范围为 (2) 。【南京理工大学 1999 年】（分数：4.00）(1).(1)（分数：2.00）A.17 B.13C.16D.任
39、意解析：(2).(2)（分数：2.00）A.017B.117C.016 D.116解析：解析：考查链地址法构造散列表。根据散列函数可得，最终计算的地址共有 17 种可能，所以需要17 个链表。指针数组中下标从 0 开始，共 17 个地址。散列表的地址区间为 017，散列函数为 H(K)=Kmod17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59 依次存储到散列表中。【北京交通大学 2001 年】（分数：4.00）(1).元素 59 存放在散列表中的地址是_。（分数：2.00）A.8B.9C.10D.11 解析：(2).存放元素 59 需要搜索的次数是_。（分数：
40、2.00）A.2B.3C.4 D.5解析：解析：考查线性探测法实现的散列表的散列过程。将前面各元素分别放入散列表中，其中8、9、10 的位置分别存放 25、26、8。元素 59 经过散列函数计算应该存入位置 8，有冲突，采用线性探测再散列，依次比较 9、10、11，发现 11 为空，所以放入 11 中。总过程需搜索 4 次。二、综合题(总题数：7，分数：32.00)假定折半查找表长为 10 的有序表：【华中科技大学 2006 年】（分数：4.00）(1).试画出描述折半查找过程的带外表结点(表示查找不成功情况的结点)的判定树。（分数：2.00）_正确答案：(正确答案：折半查找过程的带外表结点的
41、判定树如图 5-3 所示。 )解析：(2).假定每个元素的查找概率相等，试计算查找成功时的平均查找长度。（分数：2.00）_正确答案：(正确答案：ASL SUCC =(1+22+34+43)10=29。)解析：31.写出二分查找的递归程序。【北京交通大学 2006 年】初始调用时，low 为 1，high 为ST.1ength。（分数：2.00）_正确答案：(正确答案：算法的基本设计思想：根据查找的起始位置和终止位置，将查找序列一分为二，判断所查找的关键字在哪一部分，然后用新的序列起始位置和终止位置递归求解。算法的代码： typedef struct 查找表的数据结构 E1emType*ele
42、m； 存储空间基址，建表时按实际长度分配，0 号留空 int length; 表的长度 SSTable； int Search(SSTable ST，ElemType Key，int low，int high) 在有序表中递归折半查找其关键字为 Key 的元素，返回其在表中序号 int mid=(10w+high)2; if(10whigh) return 0； if(KeySTelemmid) Search(ST，Key，mid+l，high)；向后半部分查找 else if(Key解析：32.请写一非递归算法，该算法在按值严格递增排序的顺序表 A【1n】中采用折半查找法查找值不小于item 的最小元素。若表中存在这样的元素，则算法给出该最小元素在表中的位置，否则，给出信息0。【北京航空航天大学 2007 年】（分数：2.00）_正确答案：(正确答案：算法的基本设计思想：采用折半查找法查找等于 item 的元素，查找到则成功，未查找到则判断查找失败的位置，若不是表尾，则此位置后的元素即为所求，若到表尾则说明查找失败。算法的代码： int Search(SSTable ST，ElemType item) 在有序表中折半查找值不小于 i
