数据结构期末复习章节试题（附答案） - 图文(7)

8 17

2 11 16 21 4 9 13

验算方法： 用中序遍历应得到排序结果： 2,4,7,9,11,12,13,16,17，21 3. 【严题集9.9③】已知如下所示长度为12的表：

（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec）

(1) 试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其

在等概率的情况下查找成功的平均查找长度。

(2) 若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平

均查找长度。

(3) 按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。 解：

31

4. 选取散列函数H（key）=（3*key），用线性探测法处理冲突，对下列关键码序列构造一个散列地址空间为0～10，表长为11的散列表，{22，41，53，08，46，30，01，31，66}。 解：由题意知，m=11(刚好为素数)

则(22*3)=6??0 链接指针 地址 值 (41*3)=11??2

0 22 1 (53*3)=14??5 1 66 (08*3)=2??2 2 41 3 (46*3)=12??6 3 08 4,7 (30*3)=8??2 4 30 (01*3)=0??3 5 53 6 46 (31*3)=8??5 7 01 (66*3)=9??0 8 31 9 10 22 66 41 8 30 53 46 1 31 0 1 2 3 4 5 6 7 8 9 10 1 3 4， 7

五、算法设计题（4中选3，第1题7分必选，其余每题8分，共23分）

1. 已知11个元素的有序表为（05 13 19 21 37 56 64 75 80 88 92）, 请写出折半查找的算

法程序，查找关键字为key的数据元素 (建议上机调试)。

解：折半查找的C程序有很多参考资料，注意此题要求是整型量。 折半查找的一个递归算法如下，形式非常简洁！

int Search_Bin_Recursive(SSTable ST, int key, int low, int high) //折半查找的递归算法 {

32

if(low>high) return 0; //查找不到时返回0 mid=(low+high)/2;

if(ST.elem[mid].key= =key) return mid; else if(ST.elem[mid].key>key)

return Search_Bin_Recursive(ST, key, low, mid-1); else return Search_Bin_Recursive(ST, key, mid+1, high); }

}//Search_Bin_Recursive

2. 【严题集9.31④】试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。且树中结点的关键字均不同。

解：注意仔细研究二叉排序树的定义。易犯的典型错误是按下述思路进行判别：“若一棵非空的二叉树其左、右子树均为二叉排序树，且左子树的根的值小于根结点的值，又根结点的值不大于右子树的根的值，则是二叉排序树” （刘注：即不能只判断左右孩子的情况，还要判断左右孩子与双亲甚至根结点的比值也要遵循（左小右大）原则）。

若要采用递归算法，建议您采用如下的函数首部：

bool BisortTree(BiTree T, BiTree&PRE)，其中PRE为指向当前访问结点的前驱的指针。 （或者直接存储前驱的数值，随时与当前根结点比较） 一个漂亮的算法设计如下：

int last=0, flag=1; // last是全局变量，用来记录前驱结点值，只要每个结点都比前驱大就行。 int Is_BSTree(Bitree T) //判断二叉树T是否二叉排序树，是则返回1，否则返回0 {

if(T->lchild&&flag) Is_BSTree(T->lchild);

if(T->datadata;

if(T->rchild&&flag) Is_BSTree(T->rchild); return flag; }//Is_BSTree

3. 【严题集9.22④】已知一个含有1000个记录的表，关键字为中国人姓氏的拼音，请给出此表的一个哈

希表设计方案，要求它在等概率情况下查找成功的平均查找长度不超过3。 解：设计哈希表的步骤为：

a) 根据所选择的处理冲突的方法求出装载因子a的上界； b) 由a值设计哈希表的长度m；

c) 根据关键字的特性和表长m选定合适的哈希函数。 刘注：要求ASL≤3，则m必然要尽量长，以减少冲突；

4. 【严题集9.44④】已知某哈希表的装载因子小于1，哈希函数H(key)为关键字（标识符）的第一个字

母在字母表中的序号，处理冲突的方法为线性探测开放定址法。试编写一个按第一个字母的顺序输出哈希表中所有关键字的算法。

解：注意此题给出的条件：装载因子a〈1, 则哈希表未填满。由此可写出下列形式简明的算法： void PrintWord(Hash Table ht)

{//按第一个字母的顺序输出哈希表ht中的标识符。哈希函数为表示符的第一个字母在字母表中的序号，处理冲突的方法是线性探测开放定址法。 for(i=1; i<=26; i++){ j=i;

While(ht.elem[j].key){

if(Hash(ht.elem[j].key==i)printf(ht.elem[j].key); j=(j+1)%m;

33

}

}

}//PrintWord

第9章 排序 自测卷 一、填空题（每空1分，共24分）

1. 大多数排序算法都有两个基本的操作： 比较 和 移动 。 2. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插

入到有序表时，为寻找插入位置至少需比较 6 次。 3. 在插入和选择排序中，若初始数据基本正序，则选用 插入 ；若初始数据基本反序，则选用

选择 。 4. 在堆排序和快速排序中，若初始记录接近正序或反序，则选用 堆排序 ；若初始记录基本无序，则最好选用 快速排序 。 5. 对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是 O(n2) 。若对其进行快速

排序，在最坏的情况下所需要的时间是 O(n2) 。

6. 对于n个记录的集合进行归并排序，所需要的平均时间是 O(nlog2n) ，所需要的附加空间

是 O(n) 。 7． 对于n个记录的表进行2路归并排序，整个归并排序需进行 ┌log2n┐ 趟（遍）。 8. 设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则： 冒泡排序一趟扫描的结果是 H C Q P A M S R D F X Y ；

初始步长为4的希尔（shell）排序一趟的结果是 P A C S Q H F X R D M Y ； 二路归并排序一趟扫描的结果是 H Q C Y A P M S D R F X； 快速排序一趟扫描的结果是 F H C D P A M Q R S Y X ； 堆排序初始建堆的结果是 A D C R F Q M S Y P H X 。

9. 在堆排序、快速排序和归并排序中，

若只从存储空间考虑，则应首先选取 方法，其次选取 快速排序方法，最后选取归并排序方法； 若只从排序结果的稳定性考虑，则应 选取 归并排序 方法； 若只从平均情况下最快考虑，则应选取 堆排序、快速排序和归并排序 方法； 若只从最坏情况下最快并且要节省内存考虑，则应选取 堆排序 方法。 二、单项选择题（每小题1分，共18分）

（ C ）1．将5个不同的数据进行排序，至多需要比较 次。

Ａ. 8 Ｂ. 9 Ｃ. 10 Ｄ. 25 （ C ）2． 排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为

Ａ. 希尔排序 Ｂ. 冒泡排序 Ｃ. 插入排序 Ｄ. 选择排序

（ D ）3．从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为

Ａ. 希尔排序 Ｂ. 归并排序 Ｃ. 插入排序 Ｄ. 选择排序 （ B ）4．对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。

Ａ. 从小到大排列好的 Ｂ. 从大到小排列好的 Ｃ. 元素无序 Ｄ. 元素基本有序 （ D ）5．对ｎ个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为

Ａ. n+1 Ｂ. n Ｃ. n-1 Ｄ. n(n-1)/2 （ C ）6．快速排序在下列哪种情况下最易发挥其长处。

Ａ. 被排序的数据中含有多个相同排序码 Ｂ. 被排序的数据已基本有序

Ｃ. 被排序的数据完全无序 Ｄ. 被排序的数据中的最大值和最小值相差悬殊

34

（ B ）7． 对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是

A．O(n) B．O(n2) C．O(nlog2n) D．O(n3)

（ C ）8．若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用快速排序的方法，以第一个记录为基

准得到的一次划分结果为

Ａ. 38, 40, 46, 56, 79, 84 Ｂ. 40, 38, 46 , 79, 56, 84 Ｃ. 40, 38，46, 56, 79, 84 Ｄ. 40, 38, 46, 84, 56, 79 （ D ）9．下列关键字序列中， 是堆。

Ａ. 16, 72, 31, 23, 94, 53 Ｂ. 94, 23, 31, 72, 16, 53 Ｃ. 16, 53, 23, 94，31, 72 Ｄ. 16, 23, 53, 31, 94, 72 （ B ）10．堆是一种 排序。

Ａ. 插入 Ｂ.选择 Ｃ. 交换 Ｄ. 归并

（ C ）11．堆的形状是一棵

Ａ. 二叉排序树 Ｂ.满二叉树 Ｃ. 完全二叉树 Ｄ. 平衡二叉树

（ B ）12．若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用堆排序的方法建立的初始堆为

Ａ. 79, 46, 56, 38, 40, 84 Ｂ. 84, 79, 56, 38, 40, 46 Ｃ. 84, 79, 56, 46, 40, 38 Ｄ. 84, 56, 79, 40, 46, 38 （ C ）17． 下述几种排序方法中，要求内存最大的是

Ａ. 插入排序 Ｂ.快速排序 Ｃ. 归并排序 Ｄ. 选择排序

35

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构期末复习章节试题（附答案） - 图文(7)在线全文阅读。