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

1、数据结构课程(本科)第七章试题一、单项选择题1. 若搜索每一个元素的概率相等，则在长度为 n 的顺序表上搜索到表中任一元素的平均搜索长度为()。A. nB. n+1C. (n-1)/2D. (n+1)/22. 对长度为 10 的顺序表进行搜索，若搜索前面5 个元素的概率相同，均为1/8 ，搜索后面5 个元素的概率相同，均为 3/40 ，则搜索到表中任一元素的平均搜索长度为( ) 。A. 5.5B. 5C. 39/8D. 19/43. 对长度为 3 的顺序表进行搜索，若搜索第一个元素的概率为1/2，搜索第二个元素的概率为1/3 ，搜索第三个元素的概率为1/6 ，则搜索到表中任一元素的平均搜索长度

2、为() 。A. 5/3B. 2C. 7/3D. 4/34. 对长度为 n 的有序单链表，若搜索每个元素的概率相等，则顺序搜索到表中任一元素的平均搜索长度为()。A. n/2B. (n+1)/2C. (n-1)/2D. n/45. 对于长度为n 的有序顺序表，若采用折半搜索，则对所有元素的搜索长度中最大的为()的值的向上取整。A. log 2(n+1)B. log 2nC. n/2D. (n+1)/26. 对于长度为 n 的有序顺序表，若采用折半搜索，则对所有元素的搜索长度中最大的为( )的值 的向下取整加一。A. log 2(n+1)B. log 2nC. n/2D. (n+1)/27. 对于

3、长度为 9 的有序顺序表， 若采用折半搜索， 在等概率情况下搜索成功的平均搜索长度为 ()的值除以 9。A. 20B. 18C. 25D. 228. 对于长度为 18 的有序顺序表，若采用折半搜索，则搜索第15 个元素的搜索长度为( ) 。A. 3B. 4C. 5D. 69. 对具有 n 个元素的有序顺序表进行折半搜索，则搜索任一元素的时间复杂度为( ) 。A. O(n)B. O(n 2)C. O(1)D. O(log 2n)10. 在一棵高度为 h 的具有 n 个元素的二叉搜索树中，搜索所有元素的搜索长度中最大的为( ) 。A. nB. log 2nC. (h+1)/2D. h+111. 从

4、具有 n 个结点的二叉搜索树中搜索一个元素时，在等概率情况下进行成功搜索的时间复杂度大致为()。A. O(n)B. O(1)C. O(log 2n)D. O(n 2)1 / 1312. 从具有 n 个结点的二叉搜索树中搜索一个元素时，在最坏情况下进行成功搜索的时间复杂度为（）。A. O（n）B. O（1）C. O（log 2n）D. O（n 2）13. 向具有 n 个结点的二叉搜索树中插入一个元素时，其时间复杂度大致为（ ） 。A. O（1）B. O（log 2n ） C. O（n）D. O（ nlog2n）14. 在一棵AVL 树（高度平衡的二叉搜索树）中，每个结点的平衡因子的取值范围是（）

5、 。A. -1 1B. -2 2C. 1 2D. 0115. 向一棵AVL 树（高度平衡的二叉搜索树）插入元素时，可能引起对最小不平衡子树的调整过程，此调整分为（ ）种旋转类型。A. 2B. 3C. 4D. 516. 向一棵 AVL 树（高度平衡的二叉搜索树） 插入元素时， 可能引起对最小不平衡子树的左单或右单旋转的调整过程，此时需要修改相关（ ）个结点指针域的值。A. 2B. 3C. 4D. 517. 向一棵 AVL 树（高度平衡的二叉搜索树） 插入元素时， 可能引起对最小不平衡子树的双向旋转的调整过程，此时需要修改相关（ ）个结点指针域的值。A. 2B. 3C. 4D. 5参考答案： 1.

6、 D2. C3. A4. B5. A6. B7. C8. A9. D10. D11. C12. A13. B14. A15. C16. A17. C、填空题1. 以顺序搜索方法从长度为 n 的顺序表或单链表中搜索一个元素时，其时间复杂度为 。2. 对长度为n的搜索表进行搜索时，假定搜索第i个元素的率为pi,搜索长度（即在搜索过程中依次同有关元素比较的总次数）为ci ，则在搜索成功情况下的平均搜索长度的计算公式为 。3. 假定一个顺序表的长度为 40 ， 并假定搜索每个元素的概率都相同， 则在搜索成功情况下的平均搜索长度为 。4. 以折半搜索方法从长度为 n 的有序表中搜索一个元素时，时间复杂度

7、为 。5. 从有序表 （12, 18, 30, 43, 56, 78, 82, 95） 中折半搜索元素56 时，其搜索长度为 。6. 假定对长度n = 50 的有序表进行折半搜索，则对应的判定树中最后一层的结点数为 个。7. 从一棵二叉搜索树中搜索一个元素时，若给定值小于根结点的值，则需要向 继续搜索。8. 从一棵二叉搜索树中搜索一个元素时，若给定值大于根结点的值，则需要向 继续搜索。9. 向一棵二叉搜索树中插入一个新元素时，若该新元素的值小于根结点的值，则应把它插入到根结点的上。10. 向一棵二叉搜索树中插入一个新元素时，若该新元素的值大于根结点的值，则应把它插入到根结点的上。11. 向一棵

8、二叉搜索树 一个元素时，若查找到的根结点为空值，则应把该元素结点链接到这个空指针位置上。12. 根据 n 个元素建立一棵二叉搜索树的时间复杂度性大致为 。13. 在一棵 AVL 树（高度平衡的二叉搜索树）中，每个结点的左子树高度与右子树高度之差的绝对值不超过 。14. 根据一组记录 （ 56, 42, 50, 64, 48 ） 依次插入结点生成一棵AVL 树（高度平衡的二叉搜索树）时，当插入到值为 的结点时需要进行旋转调整。15. 根据一组记录（ 56, 74, 63, 64, 48 ） 依次插入结点生成一棵AVL 树（高度平衡的二叉搜索树）时，当插入到值为 63 的结点时需要进行 调整。16

9、. 根据一组记录（ 56, 42, 38, 64, 48 ） 依次插入结点生成一棵AVL 树（高度平衡的二叉搜索树）时，当插入到值为 38 的结点时需要进行 调整。17. 根据一组记录 （ 56, 42, 73, 50, 64, 48, 22 ） 依次插入结点生成一棵AVL 树（高度平衡的二叉搜索树）时，当插入到值为 的结点时才出现不平衡，需要进行旋转调整。18. 在一棵 AVL 树（高度平衡的二叉搜索树） 上进行插入或删除元素时， 所需的时间复杂度为 n13. 20.57. 左子树11. 插入15. 先右后左双旋转4. O(log 2n)8. 右子树12. O(nlog 2n)16. 右单旋

10、转参考答案： 1. O(n)2. picii05. 36. 199. 左子树10. 右子树13. 114. 5017. 4818. O(lon 2n)三、判断题1. 在顺序表中进行顺序搜索时，若各元素的搜索概率不等，则各元素应按照搜索概率的降序排列存放，则可得到最小的平均搜索长度。2. 进行折半搜索的表必须是顺序存储的有序表。3. 能够在链接存储的有序表上进行折半搜索，其时间复杂度与在顺序存储的有序表上相同。4. 假定用两个有序单链表表示两个集合，则这两个集合交运算得到的集合单链表，其长度小于参加运算的任一个集合单链表的长度。5. 假定用两个有序单链表表示两个集合，则这两个集合的差运算得到的集

11、合单链表，其长度小于参加运算的任一个集合单链表的长度。6. 折半搜索所对应的判定树，既是一棵二叉搜索树，又是一棵理想平衡二叉树(它的特点是除最底层结点外其他各层结点数都是满的，最底层的若干结点可能散布在该层各处) 。7. 对二叉搜索树进行前序遍历得到的结点序列是一个有序序列。8. 在由n个元素组成的有序表上进行折半搜索时，对任一个元素进行搜索的长度(即比较次数)都不会大于log2n+1 。9. 根据n个元素建立一棵二叉搜索树的时间复杂度大致为O(log2n)。10. 根据n个元素建立一棵二叉搜索树的时间复杂度大致为O(nlog 2n) 。11. 对于同一组记录，若生成二叉搜索树时插入记录的次序

12、不同则得到不同结构的二叉搜索树。12. 对于同一组记录，生成二叉搜索树的结构与插入记录的次序无关。13. 对于两棵具有相同记录集合而具有不同结构的二叉搜索树，按中序遍历得到的结点序列是相同的。14. 在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越大的结点离树根越近，则得到的是最优二叉搜索树。15. 在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越小的结点离树根越近，则得到的是最优二叉搜索树。参考答案：1. 是2. 是3. 否4. 是5. 否6. 是7. 否8. 是9. 否10. 是11. 是12. 否13. 是14. 是15. 否四、运算题1. 一个一维数组a10中存储着一个有序

13、表，该有序表为：(15, 26, 34, 39, 45, 56, 58, 63, 74, 76 ),根据折半搜索所对应的判定树，写出该判定树的广义表表示，并求出在等概率情况下搜索成功的平均搜索长度。判定树的广义表表示:平均搜索长度：2.已知一个有序表 ( 15,26,34,39,45,56,58,63,74,76,83,94)顺序存储于一维数组 a12中，根据折半 搜索过程填写成功搜索下表中所给元素34, 56, 58, 63, 94时的比较次数。3456586394元素值比较次数3.假定一个线T曲序列为(38, 52, 25, 74, 68, 16, 30, 54, 90, 72 ),根据此

14、线性序列中元素的排列次序生成一棵二叉搜索树，求出对该二叉搜索树查找38, 74, 68, 30, 72等元素时的比较次数。3874683072待查元素: 比较次数:4.假定一个线T曲序列为(56, 27, 34, 95, 73, 16, 50, 62, 65 ),根据此线性序列中元素的排列次序生成一棵0)、度为2的结点个数和叶子结点个二叉搜索树，求出该二叉搜索树的高度(假定树根结点的高度为高度：度为2的结点个数：叶子结点个数：5.假定一个线T曲序列为(38, 42, 55, 15, 23, 44, 30, 74, 48, 26),根据此线性序列中元素的排列次序生成一棵二叉搜索树，求出该二叉搜索

15、树中左子树为空的所有单支结点和右子树为空的所有单支结点，请按 从小到大的次序排列写出。左子树为空的所有结点： 右子树为空的所有结点：6.已知一棵二叉搜索树的广义表表示为：28 (12 (,16),49 (34 (30), 72 (63),按主教材介绍的删除算法,求出从中依次删除72, 12, 49, 28结点后得到的二叉搜索树的广义表表示。广义表表示：7.假定一组数据对象为 (40, 28, 16, 56, 50, 32, 30, 63 ),按次序插入每个对象生成一棵AVL树(高度平衡的二叉搜索树)，根据插入过程填写下表，在相应位置填写所需要的调整类型：“左单旋转”、“右单旋转”、“先左后右双

16、旋转”、“先右后左双旋转”，若不需要旋转则填写“无”。4028165650323063数据: 调整:8.假定一组数据对象为(40, 28, 16, 56, 50, 32, 30, 63, 44, 38 ),按次序插入每个对象生成一棵AVL树(高度平衡的二叉搜索树)，请回答插入后需调整的结点个数和插入后不调整的结点个数。插入时伴随旋转调整的结点个数: 插入不调整的结点个数：9 .假定一组记录为(36, 75, 83, 54, 12, 67, 60, 40 ),按次序插入每个结点生成一棵AVL树(高度平衡的二叉搜索树)，请回答在插入时需进行“左单旋转”、“右单旋转”、“先左后右双旋转”、“先右后左

17、双旋 转”，“不调整”的结点数各是多少？左单旋转结点个数：右单旋转结点个数：先左后右双旋转结点个数： 先右后左双旋转结点个数： 不调整结点个数：10 .假定一组记录为 (38, 42, 55, 15, 23, 44, 30, 74, 48, 26 ),按次序插入每个结点生成一棵AVL树(高度平衡的二叉搜索树)，给出最后得到的 AVL树中度为2、度为1和度为0的结点个数。度为2的结点个数：度为1的结点个数：度为0的结点个数：参考答案：/4分/2分1.判定树的广义表表示：45 (26 (15, 34 ( , 39 ) ), 63 ( 56 ( , 58 ), 74 ( , 76 )平均查找长度：2

18、9/102.3.判断结果 元素值比较次数判断结果 待查元素：比较次数：3456586394021344/对1个名1分，全对给6分3874683072013435/对1个名1分，全对给6分14 / 13/2分/2分/2分/全又4分，否则不得分/2分4 .高度：4度为2的结点个数：2叶子结点个数：35 . 左子树为空的结点：15, 23, 42, 44右子树为空的结点：306 . 广义表表示：30 (16,63 (34)7 .插入结果和调整类型为插入数据： 调整类型：4028165650323063无无右单旋无先右后左 双旋转先右后左 双旋转无左单旋8.插入时伴随旋转调整的结点个数：4插入不调整的

19、结点个数：6/3分，若误差1给1分，其余情况不得分/3分，若误差1给1分，其余情况不得分9 .左单旋转结点个数：1右单旋转结点个数：0先左后右双旋转结点个数：1先右后左双旋转结点个数：0不调整结点个数：610 .度为2的结点个数：4度为1的结点个数：1度为0的结点个数：5/1分/1分/1分/1分/2分/2分/2分/2分五、算法分析题1. 已知二叉搜索树中的结点类型用BinTreeNode表示，被定义为：struct BinTreeNode ElemType data; BinTreeNode *leftChild , *rightChild ; ;其中data为结点值域，leftChild和r

20、ightChild分别为指向左、右子女结点的指针域。假定具有 BinTreeNode*类型的指针参数 BST指向一棵二叉搜索树的根结点，试根据下面的函数定义指出此算法所能实现的功能。ElemType unknown ( BinTreeNode* BST ) if ( BST = NULL ) cerr << ”此树为空树"<< endl; exit (1); BinTreeNode* t = BST ;while (t-> rightChild != NULL ) t = t -> rightChild ;return t-> data;算法

21、功能：2. 假定p1和p2是两个有序单链表的表头指针，用来表示两个集合，单链表中的结点包括值域data和指向后继结点的指针域link，试根据下面算法指出算法功能。LinkNode* unknown ( LinkNode* p1 , LinkNode* p2 ) LinkNode* p3 = new LinkNode , * p = p3 ;while ( p1 != NULL && p2 != NULL ) LinkNode* newptr = new LinkNode ;if ( p1-> data < p2-> data ) newptr-> dat

22、a = p1-> data; p1 = p1 -> link ; else if ( p1-> data > p2-> data ) newptr-> data = p2-> data; p2 = p2-> link ; else newptr-> data = p1-> data; p1 = p1 -> link ; p2 = p2-> link ; p3-> link = newptr ; p3 = newptr;if ( p2 != NULL ) p1 = p2 ;while (p1 != NULL ) p3

23、= p3-> link = new LinkNode ;p3-> data = p1-> data; p1 = p1 -> link ;p3-> link = NULL ;return p-> link ;算法功能： data和指向后3. 假定 p1 和 p2 是两个单链表的表头指针，用来表示两个集合，单链表中的结点包括值域继结点的指针域link ，试根据下面算法指出算法功能。int unknown ( LinkNode* p1 , LinkNode* p2 ) while ( p2 != NULL ) LinkNode* r = p1 ;while ( r

24、 != NULL ) if ( p2-> data = r-> data ) break;r = r-> link ;if ( r = NULL ) return 0;p2 = p2-> link;return 1;算法功能： 4. 假定 HL 为保存一个集合的有序单链表的表头指针， item 为一个新元素， HL 单链表中的结点包括值域data和指向后继结点的指针域link,试根据下面算法指出算法功能。void unknown ( LinkNode * & HL , const ElemType & item ) LinkNode* newptr ;N

25、ewptr = new LinkNode ;Newptr -> data = item;if ( HL = NULL | item < HL -> data ) newptr-> link = HL ;HL = newptr ;return;LinkNode *cp , *ap;ap = HL ; cp = HL->link ;while (cp != NULL ) if ( item < cp->data ) break;ap = cp; cp = cp-> link ;newptr-> link = cp ;ap-> link =

26、 newptr ;算法功能： 5. 已知二叉搜索树中的结点类型用 BinTreeNode 表示，被定义为struct BinTreeNode ElemType data; BinTreeNode *leftChild, *rightChild ; ;其中 data 为结点值域， leftChild 和 rightChild 分别为指向左、右子女结点的指针域。假定 pt 所指向的二叉搜索树的广义表表示为 : 25 (10 (5, 16 (12) ), 40 (32 ( , 38) ) ) ，按照下面算法，则：(1) 执行unknown( pt,40 )调用后返回的值为 。(2) 执行unknow

27、n( pt,38 )调用后返回的值为 。(3) 执行 unknown ( pt, 5 ) 调用后返回的值为 。(4) 执行unknown( pt,60 )调用后返回的值为 。int unknown ( BinTreeNode* t , ElemType x ) if ( t = NULL ) return 0;else if ( t-> data = x ) return 1;else if ( t-> data > x )return 1+unknown ( t -> leftChild , x ); elsereturn 1+unknown ( t -> ri

28、ghtChild , x ) ;6. 已知二叉树中的结点类型用 BinTreeNode 表示，被定义为 :struct BinTreeNode ElemType data; BinTreeNode *leftChild , *rightChild ; ;其中 data 为结点值域， leftChild 和 rightChild 分别为指向左、右子女结点的指针域。假定具有BinTreeNode *类型的指针参数bt指向一棵二叉树的根结点，引用参数x初始具有最小值(即小于树中所有结点的值)，试根据下面的函数定义指出此算法所能实现的功能。int unknown ( BinTreeNode* bt ,

29、 ElemType & x ) if ( bt = NULL ) return 1; else if (unknown ( bt -> leftChild, x ) = 0 ) return 0;if ( bt-> data < x ) return 0;x = bt-> data;if (unknown ( bt -> rightChild, x ) = 0 ) return 0;else return 1;算法功能： 参考答案：1. 算法功能：从二叉搜索树BST 中查找出具有最大值的结点并返回这个值。2. 算法功能：实现集合的并运算，即把有序单链表表示

30、的两个集合合并为一个新的集合，并由函数返回 新集合的表头指针。3. 算法功能：判断p2 单链表所代表的集合是否为 p1 单链表所代表的集合的子集合，若是则返回 1 否则返回0 。4. 算法功能：向表示集合的有序单链表HL 中插入一个新元素，使得插入后仍然保持集合单链表有序。/2 分5. (1) 2(2) 4/2分(3) 3/2分(4) 0/2分6. 算法功能：判断二叉树bt 是否为一棵二叉搜索树，若是则返回 1 否则返回 0 。六、算法设计题1. 假定元素类型为 ElemType 的一维数组 Rn 中保存着按关键码升序排列的 n 个对象， 对象的关键码域key 的类型为 KeyType ，试按

31、照下面的函数声明编写一个非递归算法，从一维数组 Rn 中用折半搜索 法找出关键码等于k 的对象，若搜索成功则返回对象位置(即元素下标) ，否则返回 -1 。int BinSearch ( ElemType R , int n, KeyType k ) ;2. 已知二叉搜索树中的结点类型用 BinTreeNode 表示，被定义为 :struct BinTreeNode ElemType data; BinTreeNode *leftChild , *rightChild ; ;其中 data 为结点值域， leftChild 和 rightChild 分别为指向左、右子女结点的指针域。假定具有B

32、inTreeNode * 类型的指针参数 BST 指向一棵二叉搜索树的根结点，试根据下面的函数声明编写一个非递归算法，从 BST 树中查找出具有x 参数值的结点，若查找成功则返回该结点的地址，否则返回NULL 。BinTreeNode* Find ( BinTreeNode* BST , ElemType& x ) ;3. 已知二叉搜索树中的结点类型用 BinTreeNode 表示，被定义为 :struct BinTreeNode ElemType data; BinTreeNode *leftChild , *rightChild ; ;其中 data 为结点值域， leftChil

33、d 和 rightChild 分别为指向左、右子女结点的指针域。假定具有BinTreeNode * 类型的指针参数 BST 指向一棵二叉搜索树的根结点，试根据下面的函数声明编写一个递归算法，向 BST 树中插入值为 x 的结点，若树中不存在x 结点则进行插入并返回 1 表示插入成功，若树中已存在 x 结点则不插入并返回 0 表示插入失败。int Insert ( BinTreeNode * & BST, const ElemType & x ) ;4. 已知二叉搜索树中的结点类型用 BinTreeNode 表示，被定义为 :struct BinTreeNode ElemType

34、 data; BinTreeNode *leftChild , *rightChild ; ;其中 data 为结点值域， leftChild 和 rightChild 分别为指向左、右子女结点的指针域。假定具有BinTreeNode * 类型的指针参数 BST 指向一棵二叉搜索树的根结点，试根据下面的函数声明编写一个非递归算法， 向 BST 树中插入值为 x 的结点，若树中不存在x 结点则进行插入并返回 1 表示插入成功，若树中已存在 x 结点则不插入并返回 0 表示插入失败。int insert ( BinTreeNode* & BST , const ElemType &

35、 x );参考答案：1. 算法如下：int BinSearch ( ElemType R , int n, KeyType k ) / 赋初值 2 分/ 循环条件 1 分int low = 0 , high = n-1;while ( low <= high ) int mid = (low + high) / 2 ;if ( k = Rmid.key ) return mid ;else if ( k < Rmid.key) high = mid - 1;else low = mid+1 ;return -1;/ 中点位置1分/ 成功返回1分/ 向左半区查找1 分/ 向右半区查找1 分/ 失败返回1分2. 算法如下：BinTreeNode* Find ( BinTreeNode* BST ,