第九章查答案
第二部分考研真题精选
一、选择题
1.若查每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查法查一个记录，其平均查长度ASL为( )。 A．(n-1)/2 B. n/2 C. (n+1)/2 D. n
2. 对N个元素的表做顺序查时，若查每个元素的概率相同，则平均查长度为( ) A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/2
3．顺序查法适用于查顺序存储或链式存储的线性表，平均比较次数为（（1）），二分法查只适用于查顺序存储的有序表，平均比较次数为（（2））。在此假定N为线性表中结点数，且每次查都是成功的。 A.N+1
B.2log2N
C.logN
D.N/2
E.Nlog2N
F.N2
4. 下面关于二分查的叙述正确的是( )
A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列
B. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储
5. 对线性表进行二分查时，要求线性表必须（）
A.以顺序方式存储
B.以顺序方式存储，且数据元素有序
C.以链接方式存储
D.以链接方式存储，且数据元素有序
6．适用于折半查的表的存储方式及元素排列要求为( )
A．链接方式存储，元素无序B．链接方式存储，元素有序
C．顺序方式存储，元素无序D．顺序方式存储，元素有序
7. 用二分（对半）查表的元素的速度比用顺序法( )
A．必然快 B. 必然慢 C. 相等 D. 不能确定
8．当在一个有序的顺序存储表上查一个数据时，即可用折半查，也可用顺序查，但前者比后者的查速度( )
A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减
9. 具有12个关键字的有序表，折半查的平均查长度（）
A. 3.1
B. 4
C. 2.5
D. 5
10. 折半查的时间复杂性为（）
A. O（n2）
B. O（n）
C. O（nlog n）
D. O（log n）
11．当采用分快查时，数据的组织方式为( )
A．数据分成若干块，每块内数据有序
B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
D. 数据分成若干块，每块（除最后一块外）中数据个数需相同
侯雄飞12. 二叉查树的查效率与二叉树的( （1）)有关, 在(（2）)时其查效率最低
(1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置
(2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。
13. 要进行顺序查，则线性表（1）；要进行折半查询，则线性表（2）；若表中元素个数为n，则顺序查的平均比较次数为（3）；折半查的平均比较次数为（4）。
（1）（2）：A. 必须以顺序方式存储；B. 必须以链式方式存储；C. 既可以以顺序方式存储，也可以链式方式存储；
D. 必须以顺序方式存储，且数据已按递增或递减顺序排好；
E. 必须以链式方式存储，且数据已按递增或递减的次序排好。
（3）（4）：A.n B.n/2 C.n*n D.n*n/2 E.log2n F.nlog2n G.(n+1)/2 H.log2(n+1)
14．在等概率情况下，线性表的顺序查的平均查长度ASL为( （1）)，有序表的折半查的ASL为( （2）)，对静态树表，在最坏情况下,ASL为( （3）)，而当它是一棵平衡树时,ASL 为( （4）)，在平衡树上删除一个结点后可以通过旋转使其平衡，在最坏情况下需( （5）)次旋转。供选择的答案：
（1）（2）（3）（4）（5）: A. O(1) B. O( log2n ) C. O((log2n)2) D.O(nlog2n) E. O(n)
15. 对大小均为n的有序表和无序表分别进行顺序查，在等概率查的情况下，对于查失
败，它们的平均查长度是((1)) ，对于查成功，他们的平均查长度是((2))供选择的答案:
A. 相同的
B.不同的
16．如果要求一个线性表既能较快的查，又能适应动态变化的要求，则可采用( )查法。
A. 分快查
B. 顺序查
C. 折半查
清咽解热口服液消炎吗D. 基于属性
17. 既希望较快的查又便于线性表动态变化的查方法是( )
A．顺序查 B. 折半查 C. 索引顺序查 D. 哈希法查
18．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( ) A．（100，80，90，60，120，110，130） B.（100，120，110，130，80，60，90）
C.（100，60，80，90，120，110，130）
D. (100，80，60，90，120，130，110)
19. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0右孩子的平衡因子为1，则应作( ) 型调整以使其平衡。
A. LL
B. LR
C. RL
D. RR
20．下列关于m阶B-树的说法错误的是( )
A．根结点至多有m棵子树B．所有叶子都在同一层次上
C. 非叶结点至少有m/2 (m为偶数)或m/2+1（m为奇数）棵子树
D. 根结点中的数据是有序的
21. 下面关于m阶B树说法正确的是( )
①每个结点至少有两棵非空子树；②树中每个结点至多有m一1个关键字;
③所有叶子在同一层上; ④当插入一个数据项引起B树结点分裂后，树长高一层。
A．①②③ B. ②③ C. ②③④ D. ③
台标
22. 下面关于B和B+树的叙述中，不正确的是( )
A. B树和B+树都是平衡的多叉树。
B. B树和B+树都可用于文件的索引结
构。
C. B树和B+树都能有效地支持顺序检索。
D. B树和B+树都能有效地支持随机检
索。
23. m阶B-树是一棵( )
A. m叉排序树
B. m叉平衡排序树
C. m-1叉平衡排序树
D. m+1叉平衡排序树
24. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key MOD 13，散列地址为1的链中有（）个记录。
A．1 B. 2 C. 3 D. 4
25. 下面关于哈希(Hash，杂凑)查的说法正确的是( )
A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小
B．除留余数法是所有哈希函数中最好的
C．不存在特别好与坏的哈希函数，要视情况而定
D．若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可
26. 若采用链地址法构造散列表，散列函数为H（key）=key MOD 17，则需(（1）) 个链表。
这些链的链首指针构成一个指针数组，数组的下标范围为(（2）) （1）A．17 B. 13 C. 16 D. 任意
（2）A．0至17 B. 1至17 C. 0至16 D. 1至16
27. 关于杂凑查说法不正确的有几个( )
（1）采用链地址法解决冲突时，查一个元素的时间是相同的
（2）采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的
（3）用链地址法解决冲突易引起聚集现象
（4）再哈希法不易产生聚集
A. 1
B. 2
C. 3
D. 4
28. 设哈希表长为14，哈希函数是H(key)=key%11，表中已有数据的关键字为15，38，61，
84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( )
A．8 B．3 C．5 D．9
29. 假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？( )
A．k-1次 B. k次 C. k+1次 D. k（k+1）/2次
30. 哈希查中k个关键字具有同一哈希值，若用线性探测法将这k个关键字对应的记录存
入哈希表中，至少要进行( )次探测。
A．k B. k+1 C. k(k+1)/2 D.1+k(k+1)/2
31. 散列函数有一个共同的性质，即函数值应当以( )取其值域的每个值。
A. 最大概率
B. 最小概率
C. 平均概率
D. 同等概率
32. 散列表的地址区间为0-17，散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将
关键字序列26，25，72，38，8，18，59依次存储到散列表中。
（1）元素59存放在散列表中的地址是（）。
A．8 B. 9 C. 10 D. 11
（2）存放元素59需要搜索的次数是（）。
A． 2 B. 3 C. 4 D. 5
33. 将10个元素散列到100000个单元的哈希表中，则（）产生冲突。理论化学
A. 一定会
电力系统自动化杂志B. 一定不会
C. 仍可能会
二、判断题
1．采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查。
2．在散列检索中，“比较”操作一般也是不可避免的。
3．散列函数越复杂越好，因为这样随机性好，冲突概率小.
4．哈希函数的选取平方取中法最好。
5．Hash表的平均查长度与处理冲突的方法无关。
6．负载因子(装填因子)是散列表的一个重要参数，它反映散列表的装满程度。
7. 散列法的平均检索长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。
8. 哈希表的结点中只包含数据元素自身的信息，不包含任何指针。
9. 若散列表的负载因子α<1，则可避免碰撞的产生。
10．查相同结点的效率折半查总比顺序查高。
11．用向量和单链表表示的有序表均可使用折半查方法来提高查速度。
12. 在索引顺序表中，实现分块查，在等概率查情况下，其平均查长度不仅与表中元素个数有关，而且与每块中元素个数有关。
13. 顺序查法适用于存储结构为顺序或链接存储的线性表。
14. 折半查法的查速度一定比顺序查法快。
15. 就平均查长度而言，分块查最小，折半查次之，顺序查最大
16．对无序表用二分法查比顺序查快。
17．对大小均为n的有序表和无序表分别进行顺序查，在等概率查的情况下，对于查成功，它们的平均查长度是相同的，而对于查失败，它们的平均查长度是不同的。18．任一查树(二叉分类树)的平均查时间都小于用顺序查法查同样结点的线性表的平均查时间.
19．最佳二叉树是A VL树（平衡二叉树）。
20．在查树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面。
21．完全二叉树肯定是平衡二叉树。
22．对一棵二叉排序树按前序方法遍历得出的结点序列是从小到大的序列。
23．二叉树中除叶结点外, 任一结点X，其左子树根结点的值小于该结点（X）的值；其右子树根结点的值≥该结点（X）的值，则此二叉树一定是二叉排序树。
24．有n个数存放在一维数组]中，在进行顺序查时，这n个数的排列有序或无序其平均查长度不同。
25. N个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的。
26. 在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二排序叉树与原二排序叉树相同。
27. 设T为一棵平衡树，在其中插入一个结点n，然后立即删除该结点后得到T1，则T与T1
五必定相同。
28. 将线性表中的结点信息组织成平衡的二叉树，其优点之一是总能保证任意检索长度均为log2n量级（n为线形表中的结点数目）。
29. B-树中所有结点的平衡因子都为零。
31. 虽然信息项序列的顺序不一样，但依次生成的二叉排序树却是一样的。
32. 在9阶B-树中，除叶子以外的任意结点的分支数介于5和9之间。
33.B-树的插入算法中，通过结点的向上“分裂”，代替了专门的平衡调整。
34. 在平衡二叉树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。
35.二叉排序树删除一个结点后，仍是二叉排序树。
36.B+树既能索引查也能顺序查。
三、填空题
1. 顺序查n个元素的顺序表，若查成功，则比较关键字的次数最多为__ __次；当使用监视哨时，若查失败，则比较关键字的次数为__ __。
2. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查关键码值20，需做的关键码比较次数为____.
3．在有序表A[1..12]中，采用二分查算法查等于A[12]的元素，所比较的元素下标依次为__________。
4. 在有序表A[1..20]中，按二分查方法进行查，查长度为5的元素个数是__________
5. 高度为4的3阶b-树中，最多有__________个关键字。
6. 在有序表A[1…20]中，按二分查方法进行查，查长度为4的元素的下标从小到大依次是__________
7. 给定一组数据{6，2，7，10，3，12}以它构造一棵哈夫曼树，则树高为__________，带权路径长度WPL的值为__________。
8. 在一棵m阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是__________；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是__________。
9. 己知有序表为(12,18,24,35,47,50,62,83,90,115，134)当用二分法查90时，需__________次查成功，47时__________成功，查100时，需__________次才能确定不成功。
10.哈希表是通过将查码按选定的__(1)__和__(2)__，把结点按查码转换为地址进行存
储的线性表。哈希方法的关键是_(3)__和__(4)__。一个好的哈希函数其转换地址应尽可能__(5)__，而且函数运算应尽可能__(6)__。
11. 平衡二叉树又称__________，其定义是__________。
12. 在哈希函数H（key）=key%p中，p值最好取__________。
13. 对于长度为255的表，采用分块查，每块的最佳长度为__________。
14. 在n个记录的有序顺序表中进行折半查，最大比较次数是__________。
15．有一个2000项的表，欲采用等分区间顺序查方法进行查，则每块的理想长度是__(1)___，分成__(2)___块最为理想，平均查长度是__(3)___。
16．假定有k个关键字互为同义词，若用线性探测再散列法把这k个关键字存入散列表中，至少要进行__________次探测。
17. 分块检索中，若索引表和各块内均用顺序查，则有900个元素的线性表分成__________块最好：若分成25块，其平均查长度为__________。
18. 执行顺序查时，储存方式可以是__(1)__，二分法查时，要求线性表__(2)__，分块查时要求线性表__(3)__，而散列表的查，要求线性表的存储方式是__(4)__。
19. 如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序
树检索时，平均比较次数为__________。
20. 如果关键码按值排序，而后用二分法依次检索这些关键码，并把检索中遇到的在二叉树
中没有出现的关键码依次插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为__________。
21. 平衡因子的定义是__________
22. 查是非数值程序设计的一个重要技术问题，基本上分成__(1)__查，__(2)__查和
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议