《数据结构》习题集：第9章_查找第9章找到1。
如果一个由18个元素组成的有序表被存储在一维数组中，[19]，第一个元素被放入[1]，现在执行二进制搜索，用于寻找[3]的比较序列的下标是()A1，2，3 B，5，2，3 C，5，3 D，4，2，32。
如果二进制排序树中有n个节点，则二进制排序树中的平均搜索长度为()2a . o(1)b . o(log2n)c . o(n)d . o(n)5。
如果有序表中有1000个元素，通过二进制搜索找到元素x所需的最大比较次数是()次。
A.25b.10c.7d.1 6。
顺序搜索的时间复杂度是()a . o(n)b . o(N2)c . o(n1/2)d . o(1 og2n)8。
()二叉树可以获得从小到大的有序序列A。
一阶遍历b .中间阶遍历c .后阶遍历d .层次遍历9。
将一组初始记录键序列设置为(13，18，24，35，47，50，62，83，90，115，134)，然后通过二分法查找键90时要比较的键的数量为()如果哈希表的长度为100，并且哈希函数H(k)=k% P，那么P通常是最佳选择()a.99b.97c.91d.9311。
将键值插入二进制排序树的平均时间复杂度为() a . o(n)b . o(1 og2n)c . o(nlog2n)d . o(N2)12。
如果在顺序表A中有14个元素，[1:14]，在通过二分法寻找元素A[4]的过程中，比较元素的顺序是()A.一个[1)，一个[2)，一个[3)，一个[4)，一个[1)，一个[14)，一个[7)，一个[4] C.A[7]，A[3]，A[5]，A[4] D. A[7]，A[5]，A[3]，a [4] 13。
如果哈希表中有m个存储单元，哈希函数H(key)= key% p，那么p最好选择()A.小于或等于m b的最大奇数，小于或等于m c的最大素数，小于或等于m d的最大偶数，小于或等于m 14的最大组合数。
如果序列表的长度是n，序列搜索的平均比较次数是()a . nb . n/2c(n+1)/2d(n-1)/215。
如果有序表中的元素是(13，18，24，35，47，50，62)，那么对值为24的元素的二进制搜索需要()比较a.1b.2c.3d.417。
对于一组初始记录关键字序列(34，76，45，18，26，54，92)，由该组记录关键字生成的二进制排序树的深度是()a.4b.5c.6d.718 .二进制排序树中左子树上所有节点的值都是()根节点的值A.26。
对于二进制排序树，通过中间根遍历输出的数据必须是()a .升序或降序序列b .降序序列c .无序序列d .升序序列27。
有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当1二进制搜索值为82时，成功比较的次数为()a.1b.2c.4d.828。
如果构造了一个具有n个节点的二进制排序树，在最坏的情况下，其深度不超过()na1 c d n+1230。
在搜索查找表的过程中，如果要搜索的数据元素不存在，则将该数据元素插入集合中该方法主要适用于()a .静态查找表 b .动态查找表c。
静态查找表和动态查找表d .静态查找表或动态查找表31。
将一组记录的键值设置为{62，50，14，28，19，35，47，56，83}，哈希函数为H(key)=key mod 13，则哈希表中哈希地址为1的链中的节点数为()a.1b.2c.3d.432。
众所周知，有序表是(13，18，24，35，47，50，62，83，90，115，134)，当二进制搜索值为90时，成功搜索的次数为()a.1b.2c.3d.4 36。
有100个元素，当使用二进制搜索时，最大比较次数是()a.25b.7c.10d.137。
有1000个元素。
按二分法搜索时，最少比较次数为()a.0b.1c.10d.50040。
在有n个元素的有序单链表中查找具有给定关键字的节点。
平均而言，时间复杂度为(b)a . o(1)b . o(n)c . 0(N2)d . o(nlogn)41。
当对线性表进行二进制搜索时，要求线性表必须()A。
b .以顺序方式存储，并且数据元素被排序c .以链接方式存储d .以链接方式存储。
并且数据元素被排序42。
在下列二进制排序树中，搜索效率最高的是()a .平衡二叉树b .二进制搜索树c .没有左子树的二进制排序树d .没有右子树的二进制排序树44。
二进制排序树分别按照以下顺序构建。
与用其他三个序列构建的结果不同的是()a。
(100，80，90，60，120，110，130) b. (100，120，110，130，80，60，90) c. (100，60，80，90，20，110，130) d. (100，80，60，90，120，130，110)50。
设置哈希表长度M=14，哈希函数H(KEY)=KEY MOD 11表中已经有4个节点:ADDR(15)=4，ADDR(38)=5，ADDR(61)=6，ADDR(84)=7。
其余的地址都是空的。
如果通过二次检测和重新散列来处理冲突，则具有关键字49的节点的地址是()a.8b.3c.5d.952 .将10个元素散列成100，000个单元的散列表，然后()冲突A.肯定是b。
肯定不是c。
仍然可能是55。
二叉树的搜索效率与二叉树的树型有关，在()中搜索效率最低A.节点太多b .完整的二叉树c .单分支树d .节点太复杂64.对于按顺序存储的长度为18的有序表，如果采用二进制搜索，第15个元素的搜索长度为()2a . 3b . 4c . 5d . 62，填写问题7。
根据初始密钥序列(19，22，01，38，10)建立的二进制排序树的高度是_ _ _ _ _ _ _ _ _ _ _12。
如果二进制排序树的高度是h，在树中搜索关键字最多需要比较_ _ _ _ _ _ _ _ _ _ _次13。
如果哈希表长度为8，哈希函数H(k)=k% 7，冲突通过线性检测方法解决，则根据一组初始密钥序列(8，15，16，22，30，32)构造的哈希表的平均查找长度为_ _ _ _ _ _ _ _ _16。
解决哈希表冲突的两种方法是_ _ _ _ _ _ _ _ _ _ _ _ _ _和_ _ _ _ _ _ _ _ _ _ _ _ _ _ _18.从二进制搜索树中搜索元素时，如果元素的值等于根节点的值，则表示_ _ _ _ _ _。
如果元素的值小于根节点的值，它将继续搜索_ _ _ _ _ _。
如果元素的值大于根节点的值，它将继续搜索_ _ _ _ _ _。
20。
通过二叉搜索树的中间顺序遍历获得的节点序列是_ _ _ _ _ _ _ _ _27。
通过遍历二进制排序树上的_ _ _ _ _ _ _ _ _获得的节点序列是有序序列28.二进制搜索的存储结构仅限于顺序存储结构，元素排列必须是_ _ _ _。
31。
平衡二叉树中任何节点的平衡因子只能是_ _ _ _ _ _ _ _ _ _32.二进制搜索的时间复杂度是_ _ _ _ _ _ _ _ _41。
在线性表的_ _ _ _ _ _ _存储中，每个元素只能使用顺序查找48。
对于对应于二进制搜索的决策树，它既是_ _ _ _ _ _ _树又是_ _ _ _ _ _ _64.平衡二叉树也叫_ _ _ _ _ _ _ _，它的定义是_ _ _ _ _ _ _ _ _69.在具有N个节点的二进制排序树中查找关键字。
关键字比较的最大数量是72。
动态查找表和静态查找表的重要区别在于前者包含_ _ _ _ _ _ _ _和_ _ _ _ _ _ _ _操作，而后者不包含这两种操作83。
在二叉排序树中，每个分支节点的左子树中所有节点的值必须是该节点的值，右子树中所有节点的值必须是该节点的值86.当将一个元素插入到二进制排序树中时，如果该元素的值小于根节点的值，则它被插入到根节点的_ _ _ _ _ _ _中；如果元素的值大于根节点的值，则它被插入到根节点的_ _ _ _ _ _ _中89。
在平衡二叉排序树中，每个节点的左子树的高度和右子树的高度之差的绝对值不超过_ _ _ _ _ _ _ _ _4.简答6。
对长度为20的有序表执行二进制搜索，并尝试绘制决策树38。
线性表是B=(12，23，45，57，20，03，78，31，15，36)。
让哈希表为[0..12]，散列函数是H(键)=键% 13，并使用线性探测方法来解决冲突。
请绘制哈希表并计算在同等概率条件下搜索成功的平均搜索长度21。
二进制排序树具有以下结构。
每个节点的值从小到大为1-9。
请标记每个节点的值22。
哨兵在搜索和排序算法中的作用是什么？23。
输入正整数序列(53，17，12，66，58，70，87，25，56，60)，并尝试完成以下问题(1)按顺序构造二叉排序树BS(2)根据这种二叉排序树，如何得到从大到小的有序序列？(2)显示了在此二进制排序树中删除“66”后的树结构45，申请问题3。
已知待散列的线性表是(36，15，40，63，22)，用于散列的一维地址空间是[0..6]，假设所选择的散列函数是H(K)= K mod 7，并且如果发生冲突，则采用线性探测方法。
尝试:(1)计算每个元素的哈希地址，并填写下图中的哈希表:` 0 1 2 3 4 5 6 (2)当搜索每个元素的概率相等时，计算平均搜索长度11。
依次输入表{30，15，28，20，24，10，12，68，35，50，46，55}中的元素，以生成二进制搜索树①尝试绘制生成的二叉搜索树；②对二叉搜索树进行中间顺序遍历，并尝试写出遍历序列③假设每个元素的搜索概率相等，尝试计算二元搜索树的平均搜索长度18。
假设要被散列和存储的线性表是(32，75，29，63，48，94，25，46，18，70)，并且散列地址空间是[13]，如果散列函数是通过使用除法和剩余法构造的，并且使用线性探测方法来处理冲突，则尝试找到每个元素的散列地址，绘制最终的散列表，并且找到平均搜索长度519。
假设要散列的线性表是(32，75，29，63，48，94，25，46，18，70)，散列地址空间是[11]，如果散列函数是用除法和留数法构造的，而链接法是用来处理冲突的，试着找出每个元素的散列地址，画出最终的散列表，并找出平均搜索长度6，程序填写问题(或算法阅读问题)1。
二进制搜索树搜索-递归算法: 布尔函数(btree enode * BST，elem type//搜索失败否则{if (item = = BST->数据){item = BST->数据；//搜索成功返回_ _ _ _ _ _ _ _ _；}否则，如果(itemdata)返回查找(______________，项)；否则返回查找(_______________，项目)；}//if}7。