当前位置：问答库＞考研试题

一、应用题

1． 设散列表为数分别为

：

注：％是求余数运算中，函数码序列为

（2）计算搜索成功的平均搜索长度

表示颠倒十进制数x 的各位，如

即表的大小为

其

等。若插入的关键

，现采用双散列法解决冲突。散列函数和再哈希函

（1）试画出插入这8个关键码后的哈希表；

【答案】（1）插入这8个关键码后的哈希表如表所示：

表 插入关键字后的哈希表

（2）

个最小元素，你所学过的排序方法中哪个最小元素，应使用快速排序方法。其基本

2． 如果只要找出一个具有n 个元素的集合的第种最适合? 给出实现的思想。

【答案】在具有n 个元素的集合中找第

思想如下：设n 个元素的集合用一维数组表示，其第一个元素的下标为1，最后一个元素下标为n 。以第一个元素为“枢轴”，经过快速排序的一次划分，找到“枢轴”的位置i ，若i=k，则该位置的元素即为所求；若

则在1至i-1间继续进行快速排序的划分；若

则在i+1至n 间继续进

个最小元

行快速排序的划分。这种划分一直进行到i=k为止，第i 位置上的元素就是第素。

3． （1）判定起泡排序的结束条件是什么？

（2）请简单叙述希尔排序的基本思想。 （3）将下列序列调整成堆（堆顶为最小值）。

（4）在16个关键字中选出最小的关键字至少要进行多少次比较? 再选出次小的关键字至少要进行多少次比较? 请简要说明选择的方法和过程。

【答案】（1）至多进行n-1趟起泡排序，或一趟起泡排序中未发生交换（即已有序）时，结束排序。

（2）希尔排序是对直接插入排序算法的改进，它从“记录个数少”和“基本有序”出发，将，从而减少参与直接插入排序的数据量，当经过几次分待排序的记录划分成几组（缩小增量分组）

组排序后，记录的排列已经基本有序，这个时候再对所有的记录实施直接插入排序。

（3）13，24，33，65，70，56，48，92，80，112

（4）采用树形锦标赛排序选出最小关键字至少要15次比较。再选出次小关键字比较4次（两两比较8次选出8个优胜，再两两比较4次选出4个优胜，半决赛两场，决赛一场，共比较了15次。将冠军的叶结点改为最大值，均与兄弟比较，共4次选出亚军）。

4． 设二叉树BT 的存储结构如表：

表 二叉树BT 的存储结构

其中BT 为树根结点的指针，其值为6, Lchild 、Rchild 分別为结点的左、右孩子指针域data 为结点的数据域。试完成下列各题：

（1）画出二叉树BT 逻辑结构；

（2）写出按前序、中序、后序遍历该二叉树所得到的结点序列： （3）画出二叉树的后序线索树。

【答案】（1）二叉树的逻辑结构如图1所示：

图1

（2）前序序列：ABCEDFHGIJ 中序序列：ECBHFDJIGA 后序序列：ECHFJIGDBA

（3）:二叉树的后续线索树如图2所示：

图2

5． 给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：

（1）归并排序，每归并一次书写一个次序。 （2）快速排序，每划分一次书写一个次序。

（3）堆排序，先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。 【答案】（1）2—路归并第一趟：18，29，25，47，12，58，10，51: 第二趟：18，25，29， 47，10，12，51，58; 第三趟：10，12，18，25，29，47，51，58

（2）快速排序第一趟：10，18，25，12，29，58，51，47; 第二趟：10，18，25，12，29，47，51，88; 第三趟：10，12，18，25，29，47，51，88 （3）堆排序

建大堆：58，47，51，29，18，12，25，10; ①51，47，25，29，18，12，10，58; ②47，29，25，10，18，12，51，58; ③29，18，25，10，12，47，51，58; ④25，18，12，10，29，47，51，58; ⑤18，10，12，25，29， 47，51，58; ⑥12，10，18，25，29，47，51，58; ⑦10，12，18，25，29， 47，51，58