数据结构（C语言版）9-12章练习答案清华大学出版社
9-12章数据结构作业答案
第九章查
选择题
1、对n个元素的表做顺序查时，若查每个元素的概率相同，则平均查长度为
( A  )
A．（n+1）/2      B. n/2      C. n      D. [（1+n）*n ]/2 2. 下面关于二分
查的叙述正确的是  (  D  )
A. 表必须有序，表可以顺序方式存储，也可以链表方式存储
B. 表必须有序且表中
数据必须是整型，实型或字符型        C. 表必须有序，而且只能从小到大排列 D. 表
必须有序，且表只能以顺序方式存储
3. 二叉查树的查效率与二叉树的( （1）C)有关, 在 (（2)C ）时其查效率最
低    (1):  A. 高度        B. 结点的多少    C. 树型      D. 结点的位置
(2):  A. 结点太多    B. 完全二叉树    C. 呈单枝树  D. 结点太复杂。
4. 若采用链地址法构造散列表，散列函数为H（key）=key MOD 17，则需 (（1）A)
个链表。
这些链的链首指针构成一个指针数组，数组的下标范围为 (（2）C)                      （1） A．17            B. 13          C. 16          D. 任意（2） A．0至17        B. 1至17      C. 0至16      D. 1至16
判断题
1．Hash表的平均查长度与处理冲突的方法无关。 (错) 2. 若散列表的负载因子
α<1，则可避免碰撞的产生。（错）
3. 就平均查长度而言，分块查最小，折半查次之，顺序查最大。（错）
填空题
1. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查关键
码值20，需做的关键码比较次数为  4  .
算法应用题
1. 设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod
7 ，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10解决冲突。要求：对该关键字序列构造哈希表，并计算查成功的平均查长度。
2. 已知散列表的地址空间为A[0..11]，散列函数H（k）=k  mod 11，采用线性探测
法处理冲突。请将下列数据{25,16,38,47,79,82,51,39,89,151,231}依次插入到散列表中，并计算出在等概率情况下查成功时的平均查长度。
３、对长度为20 的有序表进行二分查，试画出它的一棵判定树，并求等概率情况
下的平均查长度。
４、设散列表的长度为15，散列函数H（K）=K，给定的关键字序列为20，16，29，82，37，02，06，28，55，39，23，10，试写出分别用拉链法和线性探测法解决冲突时所
构造的散列表，并求出在等概率情况下，这两种方法查成功时的平均查长度。
1
第十章内部排序
选择题
1．下面给出的四种排序法中(  D  )排序法是不稳定性排序法。
A. 插入
B. 冒泡
C. 二路归并
D. 堆排序 2．下
列排序算法中，其中（D ）是稳定的。
A. 堆排序，冒泡排序
B. 快速排序，堆排序
C. 直接选择排序，归并排序
D. 归并排序，冒泡排序 3．下面的排序算法中，不稳定的是（ CDF  ）
A.起泡排序
B.折半插入排序
C.简单选择排序
D.希尔排序
E.基数排序
F.堆排序。
4. 在下面的排序方法中，辅助空间为O（n）的是( D  ) 。
A．希尔排序      B. 堆排序        C. 选择排序        D. 归并排序    5.
下列排序算法中，占用辅助空间最多的是：(  A  )
A. 归并排序
B. 快速排序
C. 希尔排序
D. 堆排序 6．直接插
入排序在最好情况下的时间复杂度为（  B  ）
2
A． O(logn)      B． O(n)        C． O(n*logn)    D． O(n) 7．下列四个
序列中，哪一个是堆（ C  ）。
A. 75,65,30,15,25,45,20,10
B. 75,65,45,10,30,25,20,15
C.
75,45,65,30,15,25,20,10    D. 75,45,65,10,25,30,20,15  判断题
1．内排序要求数据一定要以顺序方式存储。（错）
2．排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（错）3．直接选择排序算法在最好情况下的时间复杂度为O（N）。（错） 4．在待排数据基
本有序的情况下，快速排序效果最好。（错） 5．快速排序总比选择排序快。
（对）
填空题
1．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的比
较和记录的移动。
2．关键码序列（ Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的
次序进行排序，若采用初始步长为4的Shell排序法，则一趟扫描的结果是QACSQDFXRHMY  ；若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是FHCDMAQSRQYX  。
算法应用题
1．对下列记录进行希尔排序（增量分别为：5，3，1）
21，27，10，14，75，45，9，28，16，55，70，18，32 2．对下列记录进行一趟快
速排序
30，41，15，48，60，18，77，25，43，10，12，61 3．对下列序列建成一个大根
堆
2
21，27，10，14，75，45，9，28，16，55，70，18，32
第十二章文件
选择题
4．下述文件中适合于磁带存储的是（ A  ）。
A. 顺序文件
B. 索引文件
C. 散列文件
D. 多关键字文件判断题
1. 文件是记录的集合，每个记录由一个或多个数据项组成，因而一个文件可看作由c语言的冒泡排序算法
多个记录组成的数据结构。填空题
1. 文件可按其记录的类型不同而分成两类，即操作系统和数据库文件。
2. 数据库文件按记录中关键字的多少可分成单关键字和多关键字两种文件。3
感谢您的阅读，祝您生活愉快。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。