数据结构习题汇编08第八章查找试题

一、单项选择题

1. 若搜索每一个元素的概率相等，则在长度为n的顺序表上搜索到表中任一元素的平均搜索长度为

（ ）。 A. n

B. n+1 C. (n-1)/2

D. (n+1)/2

2. 对长度为10的顺序表进行搜索，若搜索前面5个元素的概率相同，均为1/8，搜索后面5个元素的概

率相同，均为3/40，则搜索到表中任一元素的平均搜索长度为（ ）。 A.

B. 5 C. 39/8

D. 19/4

3. 对长度为3的顺序表进行搜索，若搜索第一个元素的概率为1/2，搜索第二个元素的概率为1/3，搜索

第三个元素的概率为1/6，则搜索到表中任一元素的平均搜索长度为（ ）。 A. 5/3

B. 2 C. 7/3

D. 4/3

4. 对长度为n的有序单链表，若搜索每个元素的概率相等，则顺序搜索到表中任一元素的平均搜索长度

为（ ）。 A. n/2

B. (n+1)/2

C. (n-1)/2

D. n/4

5. 对于长度为n的有序顺序表，若采用折半搜索，则对所有元素的搜索长度中最大的为（ ）的值

的向上取整。 A. log2(n+1)

B. log2n C. n/2

D. (n+1)/2

6. 对于长度为n的有序顺序表，若采用折半搜索，则对所有元素的搜索长度中最大的为（ ）的值

的向下取整加一。

A. log2(n+1) B. log2n C. n/2

D. (n+1)/2

7. 对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（ ）

的值除以9。

A. 20 B. 18 C. 25 D. 22

8. 对于长度为18的有序顺序表，若采用折半搜索，则搜索第15个元素的搜索长度为（ ）。 A. 3 B. 4 C. 5 D. 6

9. 对具有n个元素的有序顺序表进行折半搜索，则搜索任一元素的时间复杂度为（ ）。

A. O(n) B. O(n)

2

C. O(1) D. O(log2n)

10. 在一棵高度为h的具有n个元素的二叉搜索树中，搜索所有元素的搜索长度中最大的为（ ）。

A. n B. log2n C. (h+1)/2 D. h+1

11. 从具有n个结点的二叉搜索树中搜索一个元素时，在等概率情况下进行成功搜索的时间复杂度大致为

（ ）。

A. O(n) B. O(1)

C. O(log2n)

D. O(n)

2

12. 从具有n个结点的二叉搜索树中搜索一个元素时，在最坏情况下进行成功搜索的时间复杂度为

（ ）。

A. O(n)

B. O(1)

C. O(log2n)

D. O(n)

2

13. 向具有n个结点的二叉搜索树中插入一个元素时，其时间复杂度大致为（ ）。 A. O(1)

B. O(log2n ) C. O(n)

D. O(nlog2n)

14. 在一棵AVL树（高度平衡的二叉搜索树）中，每个结点的平衡因子的取值范围是（ ）。 A. -1～1 B. -2～2

C. 1～2 D. 0～1

15. 向一棵AVL树（高度平衡的二叉搜索树）插入元素时，可能引起对最小不平衡子树的调整过程，此调

整分为（ ）种旋转类型。 A. 2

B. 3

C. 4

D. 5

16. 向一棵AVL树（高度平衡的二叉搜索树）插入元素时，可能引起对最小不平衡子树的左单或右单旋转

的调整过程，此时需要修改相关（ ）个结点指针域的值。 A. 2

B. 3

C. 4

D. 5

17. 向一棵AVL树（高度平衡的二叉搜索树）插入元素时，可能引起对最小不平衡子树的双向旋转的调整

过程，此时需要修改相关（ ）个结点指针域的值。 A. 2

参考答案： 1. D

6. B

B. 3

2. C

C. 4 3. A

D. 5 4. B

15. C

5. A

7. C 8. A 9. D 10. D

11. C 16. A

12. A 17. C

13. B 14. A

二、填空题

1. 以顺序搜索方法从长度为n的顺序表或单链表中搜索一个元素时，其时间复杂度为________。

2. 对长度为n的搜索表进行搜索时，假定搜索第i个元素的概率为pi，搜索长度（即在搜索过程中依次

同有关元素比较的总次数）为ci，则在搜索成功情况下的平均搜索长度的计算公式为________。

3. 假定一个顺序表的长度为40，并假定搜索每个元素的概率都相同，则在搜索成功情况下的平均搜索长

度为________。

4. 以折半搜索方法从长度为n的有序表中搜索一个元素时，时间复杂度为________。

5. 从有序表 (12, 18, 30, 43, 56, 78, 82, 95) 中折半搜索元素56时，其搜索长度为________。

6. 假定对长度n = 50的有序表进行折半搜索，则对应的判定树中最后一层的结点数为______个。

7. 从一棵二叉搜索树中搜索一个元素时，若给定值小于根结点的值，则需要向________继续搜索。

8. 从一棵二叉搜索树中搜索一个元素时，若给定值大于根结点的值，则需要向________继续搜索。

9. 向一棵二叉搜索树中插入一个新元素时，若该新元素的值小于根结点的值，则应把它插入到根结点的

________上。

10. 向一棵二叉搜索树中插入一个新元素时，若该新元素的值大于根结点的值，则应把它插入到根结点的

________上。

11. 向一棵二叉搜索树________一个元素时，若查找到的根结点为空值，则应把该元素结点链接到这个空

指针位置上。

12. 根据n个元素建立一棵二叉搜索树的时间复杂度性大致为_____________。

13. 在一棵AVL树（高度平衡的二叉搜索树）中，每个结点的左子树高度与右子树高度之差的绝对值不超

过________。

14. 根据一组记录 ( 56, 42, 50, 64, 48 ) 依次插入结点生成一棵AVL树（高度平衡的二叉搜索树）时，

当插入到值为_______的结点时需要进行旋转调整。

15. 根据一组记录 ( 56, 74, 63, 64, 48 ) 依次插入结点生成一棵AVL树（高度平衡的二叉搜索树）时，

当插入到值为63的结点时需要进行________________调整。

16. 根据一组记录 ( 56, 42, 38, 64, 48 ) 依次插入结点生成一棵AVL树（高度平衡的二叉搜索树）时，

当插入到值为38的结点时需要进行____________调整。

17. 根据一组记录 ( 56, 42, 73, 50, 64, 48, 22 ) 依次插入结点生成一棵AVL树（高度平衡的二叉搜

索树）时，当插入到值为_______的结点时才出现不平衡，需要进行旋转调整。

18. 在一棵AVL树（高度平衡的二叉搜索树）上进行插入或删除元素时，所需的时间复杂度为_________。

参考答案： 1. O(n)

5. 3

2.

n1i0pcii 3.

4. O(log2n)

8. 右子树 12. O(nlog2n)

6. 19

7. 左子树

9. 左子树 13. 1 17. 48

10. 右子树 14. 50 18. O(lon2n)

11. 插入

15. 先右后左双旋转 16. 右单旋转

三、判断题

1. 在顺序表中进行顺序搜索时，若各元素的搜索概率不等，则各元素应按照搜索概率的降序排列存放，

则可得到最小的平均搜索长度。

2. 进行折半搜索的表必须是顺序存储的有序表。

3. 能够在链接存储的有序表上进行折半搜索，其时间复杂度与在顺序存储的有序表上相同。

4. 假定用两个有序单链表表示两个集合，则这两个集合交运算得到的集合单链表，其长度小于参加运算

的任一个集合单链表的长度。

5. 假定用两个有序单链表表示两个集合，则这两个集合的差运算得到的集合单链表，其长度小于参加运

算的任一个集合单链表的长度。

6. 折半搜索所对应的判定树，既是一棵二叉搜索树，又是一棵理想平衡二叉树（它的特点是除最底层结

点外其他各层结点数都是满的，最底层的若干结点可能散布在该层各处）。

7. 对二叉搜索树进行前序遍历得到的结点序列是一个有序序列。

8. 在由n个元素组成的有序表上进行折半搜索时，对任一个元素进行搜索的长度（即比较次数）都不会

大于log2n+1。

9. 根据n个元素建立一棵二叉搜索树的时间复杂度大致为O(log2n)。

10. 根据n个元素建立一棵二叉搜索树的时间复杂度大致为O(nlog2n)。

11. 对于同一组记录，若生成二叉搜索树时插入记录的次序不同则得到不同结构的二叉搜索树。

12. 对于同一组记录，生成二叉搜索树的结构与插入记录的次序无关。

13. 对于两棵具有相同记录集合而具有不同结构的二叉搜索树，按中序遍历得到的结点序列是相同的。

14. 在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越大的结点离树根越近，则得到的是最优

二叉搜索树。

15. 在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越小的结点离树根越近，则得到的是最优

二叉搜索树。

参考答案： 1. 是

6. 是 11. 是

2. 是 7. 否 12. 否

3. 否 8. 是 13. 是

4. 是 9. 否 14. 是

5. 否 10. 是 15. 否

四、运算题

1. 一个一维数组a[10]中存储着一个有序表，该有序表为：(15, 26, 34, 39, 45, 56, 58, 63, 74, 76 )，

根据折半搜索所对应的判定树，写出该判定树的广义表表示，并求出在等概率情况下搜索成功的平均搜索长度。

判定树的广义表表示：_______________________________ 平均搜索长度：_________________

2. 已知一个有序表 ( 15, 26, 34, 39, 45, 56, 58, 63, 74, 76, 83, 94 ) 顺序存储于一维数组a[12]

中，根据折半搜索过程填写成功搜索下表中所给元素34, 56, 58, 63, 94时的比较次数。

34 56 58 63 94 元素值 比较次数

3. 假定一个线性序列为 ( 38, 52, 25, 74, 68, 16, 30, 54, 90, 72 )，根据此线性序列中元素的排列

次序生成一棵二叉搜索树，求出对该二叉搜索树查找38, 74, 68, 30, 72等元素时的比较次数。

待查元素： 38 74 68 30 72 比较次数：

4. 假定一个线性序列为 ( 56, 27, 34, 95, 73, 16, 50, 62, 65 )，根据此线性序列中元素的排列次序

生成一棵二叉搜索树，求出该二叉搜索树的高度（假定树根结点的高度为0）、度为2的结点个数和叶子结点个数。

高度：_____________

度为2的结点个数：____________ 叶子结点个数：____________

5. 假定一个线性序列为 ( 38, 42, 55, 15, 23, 44, 30, 74, 48, 26 )，根据此线性序列中元素的排列

次序生成一棵二叉搜索树，求出该二叉搜索树中左子树为空的所有单支结点和右子树为空的所有单支结点，请按从小到大的次序排列写出。

左子树为空的所有结点：____________ 右子树为空的所有结点：____________

6. 已知一棵二叉搜索树的广义表表示为：28 (12 ( , 16), 49 (34 (30), 72 (63) ) )，按主教材介绍

的删除算法，求出从中依次删除72, 12, 49, 28结点后得到的二叉搜索树的广义表表示。

广义表表示：_____________________________

7. 假定一组数据对象为 ( 40, 28, 16, 56, 50, 32, 30, 63 )，按次序插入每个对象生成一棵AVL树（高

度平衡的二叉搜索树），根据插入过程填写下表，在相应位置填写所需要的调整类型：“左单旋转”、“右单旋转”、“先左后右双旋转”、“先右后左双旋转”，若不需要旋转则填写“无”。

数据： 40 28 16 56 50 32 30 63

调整：

8. 假定一组数据对象为 ( 40, 28, 16, 56, 50, 32, 30, 63, 44, 38 )，按次序插入每个对象生成一棵

AVL树（高度平衡的二叉搜索树），请回答插入后需调整的结点个数和插入后不调整的结点个数。

插入时伴随旋转调整的结点个数：___________ 插入不调整的结点个数：__________

9. 假定一组记录为 ( 36, 75, 83, 54, 12, 67, 60, 40 )，按次序插入每个结点生成一棵AVL树（高度

平衡的二叉搜索树），请回答在插入时需进行“左单旋转”、“右单旋转”、“先左后右双旋转”、“先右后左双旋转”，“不调整”的结点数各是多少

左单旋转结点个数：____________ 右单旋转结点个数：____________

先左后右双旋转结点个数：___________ 先右后左双旋转结点个数：___________ 不调整结点个数：____________

10. 假定一组记录为 ( 38, 42, 55, 15, 23, 44, 30, 74, 48, 26 )，按次序插入每个结点生成一棵AVL

树（高度平衡的二叉搜索树），给出最后得到的AVL树中度为2、度为1和度为0的结点个数。

度为2的结点个数：__________ 度为1的结点个数：__________ 度为0的结点个数：__________

参考答案：

判定树的广义表表示：45 (26 (15, 34 ( , 39 ) ), 63 ( 56 ( , 58 ), 74 ( , 76 ) ) ) ey ; //向左半区查找1分 40 28 16 56 50 32 30 63 return mid; 34 56 58 63 94 ey) high = mid-138 74 68 30 72 else low = mid+1; 右单旋 无 先右后左 //向右半区查找1分 左单旋 0无2 1 3 4 4 无 先右后左 无

01 3 4 3 5 }

双旋转 双旋转

return -1; //失败返回1分 }

1. 算法如下：

BinTreeNode* Find ( BinTreeNode* BST, ElemType& x ) {

while ( BST != NULL ) { //循环条件1分

if ( x == BST->data ) return BST; //成功返回2分

else if ( x < BST->data ) BST = BST->leftChild; //向左孩子查找2分 else BST = BST->rightChild; //向右孩子查找2分 }

return NULL; //失败返回1分 }

2. 算法如下：

int Insert ( BinTreeNode*& BST, const ElemType& x ) {

if ( BST == NULL ) { //插入新结点2分 BinTreeNode* p = new BinTreeNode;

p->data = x; p->leftChild = p->rightChild = NULL;

BST = p; return 1;

)

}

else if ( x == BST->data ) return 0; //不插入返回2分

else if ( x < BST->data ) return Insert ( BST->leftChild, x ); //向左子树插入元素2分

else return Insert ( BST->rightChild, x ); }

3. 算法如下：

int Insert ( BinTreeNode*& BST, const ElemType& x ) {

BinTreeNode* t = BST, *parent = NULL;

while ( t != NULL ) { //查找插入位置，3分

parent = t;

if ( x == t->data ) return 0;

else if ( x < t->data ) t = t->leftChild; else t = t->rightChild; }

BinTreeNode* p = new BinTreeNode; //建立新结点，2分

p->data = x;

p->leftChild = p->rightChild = NULL;

//将新结点插入到二叉搜索树中的确定位置上

if ( parent == NULL ) BST = p; //1分

else if ( x < parent->data ) parent->leftChild = p; //1分 else parent->rightChild = p; //1分 }

//向右子树插入元素2分