计算机专业基础综合数据结构查找历年真题试卷汇编1_真题-无答案
- 格式：docx
- 大小：32.21 KB
- 文档页数：5
计算机专业基础综合数据结构（查找）历年真题试卷汇编1
(总分108,考试时间90分钟)
1. 单项选择题
1. 顺序查找法适合于存储结构为____的线性表。【北京航空航天大学2002年】
A. 顺序存储结构或链式存储结构 B. 散列存储结构
C. 索引存储结构 D. 压缩存储结构
2. 若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度(ASL)为____。【北京航空航天大学2004年】
A. (n—1)／2 B. n／2
C. (n+1)／2 D. n
3. 当采用分块查找时，数据的组织方式为____。【太原科技大学2007年】
A. 数据分成若干块，每块内数据有序
B. 数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块
C. 数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块
D. 数据分成若干块，每块(除最后一块外)中数据个数需相同
4. 对有2500个记录的索引顺序表(分块表)进行查找，最理想的块长为____。【华中科技大学2007年】
A. 50 B. 125
C. 500 D. [log22500]
5. 下面关于二分查找的叙述正确的是____。【南京理工大学1996年】
A. 表必须有序，表可以顺序方式存储，也可以链表方式存储
B. 表必须有序且表中数据必须是整型、实型或字符型
C. 表必须有序，而且只能从小到大排列
D. 表必须有序，且表只能以顺序方式存储
6. 当n足够大时，在按值有序的顺序表中进行折半查找，当查找概率相等的情况下，其查找成功的平均查找长度是____。【北京航空航天大学2002年】
A. (n+1)／2
B. n／2
C. log2(n+1)一1
D. log2(n+1)
7. 在具有15个记录的排序连续顺序文件上采用折半查找方法查找一个文件中不存在的记录．需要进行____次关键字值的比较。【北京航空航天大学2004年】
A. 0 B. 4
C. 5 D. 15
8. 对一个长度为50的有序表进行折半查找，最多比较____次就能查找出结果。【北京邮电
大学2005年】
A. 6 B. 7
C. 8 D. 9
9. 已知一个有序表(13，18，24，35，47，50，62，83，90，115，134)，当二分查找值为90的元素时，查找成功的比较次数为____。【浙江大学2004年】
A. 1 B. 2
C. 4 D. 6
10. 折半查找有序表(2，10，25，35，40，65，70，75，81，82，88，100)，若查找元素75，需依次与表中元素____进行比较。【华中科技大学2007年】
A. 65．82，75 B. 70，82，75
C. 65，8l，75 D. 65，81，70，75
11. 折半查找过程所对应的判定树是一棵____。【北京交通大学2007年】
A. 最小生成树 B. 平衡二叉树
C. 完全二叉树 D. 赫夫曼树
12. 对表长为n的有序表进行折半查找，其判定树高度为____。【北京交通大学2004年】
A. [log2(n+1)]
B. [log2(n+1)]
C. [log2n]
D. [log2n]
13. 图5-1是一棵____。【华南理工大学2007年】
A. 4阶B-树 B. 4阶B+树
C. 3阶B-树 D. 3阶B+树
14. 下列关于m阶B-树的说法错误的是____。【南京理工大学1997年】
A. 根结点至多有m棵子树
B. 所有叶子都在同一层次上
C. 非叶结点至少有m／2(m为偶数)或m／2+1(m为奇数)棵子树
D. 根结点中的数据是有序的
15. 当向B-树插入关键字时，可能引起结点的____；最终可能导致整个B-树的高度____。【浙江大学2004年】
A. 合并 B. 增加1
C. 分裂 D. 减少1
16. m阶B-树的每个分支结点中最多包含____个关键字值。【北京航空航天大学2007年】
A. [m／2] B. m一1
C. m D. m+1
17. 在一棵m阶B-树中，若在某结点中插入一个新关键字而引起该结点的分裂，则此结点中原有的关键字的个数是____。【湖南大学2003年】
A. m B. m+1
C. m—1 D. m／2
18. 理想情况下，散列表的平均比较次数为____。【北京邮电大学2005年】
A. 1 B. 2
C. 4 D. n
19. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H(key)=keyMOD13，散列地址为1的链中有____个记录。【南京理工大学1997年】
A. 1 B. 2
C. 3 D. 4
若采用链地址法构造散列表，散列函数为H(key)=keyMOD17，则需(1)个链表。这些链的链首指针构成一个指针数组，数组的下标范围为(2)。【南京理工大学1999年】
20. (1)
A. 17 B. 13
C. 16 D. 任意
21. (2)
A. 0～17 B. 1～17
C. 0～16 D. 1～16
22. 关于杂凑查找说法不正确的有____个。【南京理工大学2000年】(1)采用链地址法解决冲突时，查找一个元素的时间是相同的(2)采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的(3)用链地址法解决冲突易引起聚集现象(4)再散列法不易产生聚集
A. 1 B. 2
C. 3 D. 4
散列表的地址区间为0～17，散列函数为H(K)=Kmod17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。【北京交通大学2001年】
23. 元素59存放在散列表中的地址是____。
A. 8 B. 9
C. 10 D. 11
24. 存放元素59需要搜索的次数是____。
A. 2 B. 3
C. 4 D. 5
25. 采用链地址法解决冲突的散列表中，查找成功的平均查找长度____。【北京交通大学2007年】
A. 直接与关键字个数有关 B. 直接与装填因子有关
C. 直接与表的容量有关 D. 直接与散列函数有关
26. 在采用链地址法处理冲突所构成的散列表上查找某一关键字，则在查找成功的情况下，所探测的这些位置上的键值____。【北京交通大学2006年】
A. 一定都是同义词 B. 不一定都是同义词
C. 都相同 D. 一定都不是同义词
27. 设初始为空的散列表的地址空间为(O…10)，散列函数为H(k)=kmod11，采用线性探测再散列法处理冲突，若依次插入关键字37，95，27，14，48，则最后一个关键字值48的插入位置是____。【北京航空航天大学2007年】
A. 4 B. 5
C. 6 D. 7
28. 在构造散列表方面，下面的说法____是正确的。【华南理工大学2006年】
A. 再散列法在处理冲突时不会产生聚集
B. 散列表的装填因子越大，说明空间利用率越好，因此应使装填因予尽量大
C. 散列函数选的好可减少冲突现象
D. 对于任何具体关键字都不可能找到不产生冲突的散列函数
29. 将10个元素散列到100000个单元的散列表中，则____产生冲突。【北京邮电大学2001年】
A. 一定会
B. 一定不会
C. 仍可能会
30. 用二分(对半)查找表的元素的速度比用顺序法____。【南京理工大学1998】
A. 必然快 B. 必然慢
C. 相等 D. 不能确定
31. 折半查找的时间复杂度为____。【中山大学1999年】【华南理工大学2007年】
A. O(n2)
B. O(n)
C. O(nlog2n)
D. O(log2n)
32. 在等概率情况下，线性表的顺序查找的平均查找长度(ASL)为____，有序表的折半查找的ASL，为____。【上海海事大学1999年】
A. O(1)
B. O(log2n)
C. O((log2n)2)
D. O(nlog2n)E．O(n)
33. 衡量查找算法性能好坏的主要标准是____。【北京航空航天大学2004年】
A. 参加比较的关键字值的多少
B. 被查找的关键字值在关键字序列中的位置
C. 关键字值序列中是否存在被查找关键字值
D. 关键字值的平均比较次数的多少
34. 只能在顺序存储结构上进行的查找方法是____。【北京航空航天大学2005年】
A. 顺序查找法 B. 折半查找法
C. 树型查找法 D. 散列查找法
若采用链地址法构造散列表，散列函数为H(key)=keyMOD17，则需(1)个链表。这些链的链首指针构成一个指针数组，数组的下标范围为(2)。【南京理工大学1999年】
35. (1)
A. 17 B. 13
C. 16 D. 任意
36. (2)
A. 0～17 B. 1～17
C. 0～16 D. 1～16
散列表的地址区间为0～17，散列函数为H(K)=Kmod17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。【北京交通大学2001年】
37. 元素59存放在散列表中的地址是____。
A. 8 B. 9
C. 10 D. 11
