利用逐点插入法建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，查找元素30要进行(42)次元素间的比较。A．4B．5C．6D．7

第1题：

正确答案：A
解析：二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：①若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；③它的左右子树也分别为二叉排序树。二叉排序树也叫二叉查找树。二叉排序树是一种动态树表。其特点是，树的结构通常不是一次生成的，而是在查找过程中逐步插入结点形成的，即当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或者右孩子(若给定值小于最后一个结点的关键字值，则插入成为其左孩子，否则便插入成为其右孩子)。此题中建立二叉排序树的过程如图13-38所示。

当查找元素35时，依次要跟49、43，21、35比较，因此要比较4次。

第2题：

第3题：

用折半查找法，对长度为12的有序的线性表进行查找，最坏情况下要进行（）次元素间的比较。

A4

B3

C5

D6

第4题：

设有序列{10，12，15，19，22，25，100，130，150，200}画出对上述序列进行折半查找的判定树（以序列中的元素作为树的结点）。为了成功查找到100需要进行多少次元素间的比较？为了查找9，经过多少次元素间的比较可知道查找失败？
（1）

（2）4次；3次
略

第5题：

依次插入序列（50，72，43，85，75，20，35，45，65，30）后建立的二叉搜索树中，查找元素35要进行（）元素间的比较。

• A、4次
• B、5次
• C、7次
• D、10次

第6题：

n个元素进行冒泡法排序，第j趟冒泡要进行（）次元素间的比较。

第7题：

假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找。若查找元素54，需依次与哪些元素比较？

第8题：

利用逐点插入法建立序列{50，72，43，85，75，20，35，45，65，30}对应的二叉排序树以后，查找元素35要进行（）元素间的比较。

• A、4次
• B、5次
• C、7次
• D、10次

第9题：

第10题：

第11题：

第12题：

第13题：

第14题：

第15题：

设有一个整数序列{50，38，16，82，110，13，64}，依次取出序列中的数，构造一棵二叉排序树。利用上述二叉排序树，为了查找110，经多少次元素间的比较能成功查到？为了查找15，经多少次元素间的比较可知道查找失败？
（1）

（2）三次；四次
略

第16题：

利用逐点插入法建立序列（50，72，43，85，75，20，35，45，65，30）对应的二叉排序树以后，查找元素30要进行（）次元素间的比较。

• A、4
• B、5
• C、6
• D、7

第17题：

在序列（2，5，8，11，15，16，22，24，27，35，50）中采用折半查找（二分查找）方法查找元素24，需要进行（）次元素之间的比较。

第18题：

依次取a中各数据，构造一棵二叉排序树。 （1）对该二叉树进行查找，成功查找到38，和46各要进行多少次元素间的比较？ （2）给出按后序遍历该二叉排序树的序列。

第19题：

20个元素进行冒泡法排序，通常第6趟冒泡要进行（）次元素间的比较。

第20题：

用折半查找法，对长度为12的有序的线性表进行查找，最坏情况下要进行（）次元素间的比较。

• A、4
• B、3
• C、5
• D、6

第21题：

第22题：

第23题：