内容发布更新时间 : 2024/11/18 10:46:02星期一 下面是文章的全部内容请认真阅读。

94. 在含有n个元素的有序顺序表中进行二分查找，最大的比较次数是 。

参考答案：.?log2?+1

n

95. 用二分查找一个查找表，该查找表必须具有的特点是 。

参考答案：顺序存储且关键字有序

96.

分块查找发将待查找的表均匀地分成若干块且块中诸记录的顺序可以是任意的，但块与块之间 。

参考答案：关键字有序

97. 在分块查找方法中，首先查找 ，然后再查找相应的 。

参考答案：关键字表 ， 对应的块

98. 用二叉排序树在n个元素中进行查找，最坏情况下查找时间复杂度为 ，最好情况的查找时间复杂度为

参考答案：O(n) ，O(log2)

n

99. 折半查找的存储结构仅限于 ，且是 。

参考答案： 顺序存储结构 ，关键字有序排列

100. 一个无序序列可以通过构造一棵 树而变成有序序列，构造树的过程即是对无序序列进行排序的过程参考答案： 二叉排序

101. 画出对长度为10的右序表进行折半查找的一棵判定树，并求其等概率时查找成功的平均查找长度。

参考答案：

平均查找长度=(1+2*2+4*3+3*4)/10=2.9

102. 设有数据集合d={1，12，5，8，3，10，7，13，9}，回答下列问题： ① 依次取d中各数据，构造一棵二叉排序树； ②如何依据此二叉排序树得到d的一个有序序列。

参考答案：

①构造的二叉排序树如下图所示。

11 / 12

②对该二叉排序树进行中序遍历，就可以得到d的一个有序序列：

{1，3，5，7，8，9，10，12，13}

103. 每次从无序子表中取出一个元素，把它插入到有序子表中恰当位置，此种排序方法叫做 排序；若每次

大元素，把它交换到有序表的一端，此种排序方法叫做 排序。 参考答案：插入 ；直接选择

104. 每次通过基准元素间接比较两个元素，不满足约定要求时就交换位置，该排序方法叫做 排序；每次使两表的排序方法叫做 排序。 参考答案：快速 ； 归并

105. 排序方法采用二分法的思想， 排序方法将数据的组织采用完全二叉树的结构。

参考答案：快速 ， 堆

106. 对n个元素的表进行直接选择排序，所需要的关键字的比较次数为 。

参考答案： n(n-1)/2

107. 在堆和快速排序中，若原始记录接近正序或反序，则选用 ，若原始记录无序，则选用 。

参考答案：堆 ，快速

108. 在插入和选择排序中，若初始数据基本正序，则选用 ，若初始数据基本反序，则选用 。

参考答案：插入 ，选择

109. 在堆排序、快速排序和归并排序中，若只从存储空间考虑，则应首先选取 方法，其次选择 方法，最后选择 方

快考虑，则应选取 方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取 方法。 参考答案：堆排序 ，快速排序， 归并排序 ，快速排序 ，堆排序 。

12 / 12