数据结构C语言版9-12章练习答案清华大学出版社.doc

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 ）20 的有序表进行二分查找，试画出它的一棵判定树，并求等概率情况下的平均查找长度。 ４、设散列表的长度为15，散列函数H（K）=K%13，给定的关键字序列为20，16，29，82，37，02，06，28，55，39，23，10，试写出分别用拉链法和线性探测法解决冲突时所构造的散列表，并求出在等概率情况下，这两种方法查找成功时的平均查找长度。 第十章 内部排序 选择题 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 ） A． O(logn) B． O(n) C． O(n*logn) D． O(n2) 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 。 算法应用题 对下列记录进行希尔排序（增量分别为：5，3，1） 21，27，10，14，75，45，9，28，16，55，70，18，32 对下列记录进行一趟快速排序 30，41，15，48，60，18，77，25，43，10，12，61 对下列序列建成一个大根堆 21，27，10，14，75，45，9，28，16，55，70，18，32 第十二章 文件 选择题 4．下述文件中适合于磁带存储的是（ A ）。 A. 顺序文件 B. 索引文件 C. 散列文件 D. 多关键字文件 判断题 1. 文件是记录的集合，每个记录由一个或多个数据项组成，因而一个文件可看作由多个记录组成的数据结构。 填空题 1. 文件可按其记录的类型不同而分成两类，即 操作系统 和 数据库 文件。 2. 数据库文件按记录中关键字的多少可分成 单关键字 和 多关键字 两种文件。 1