发布时间 : 星期三 文章1数据结构习题及参考答案更新完毕开始阅读
A.快速排序 B.堆排序 C.归并排序 D.冒泡排序
（4）在基于关键码比较的排序算法中， 算法在最坏情况下，关键码比较次数不高于 O（nlog2n）。
A.冒泡排序 B.直接插入排序 C.二路归并排序 D.快速排序 （5）一组记录为｛46，79，56，38，84，40｝，则采用冒泡排序法按升序排列时第一趟排序 的结果是 。
A.46，79，56，38，40，84 B.46，56，38，79，40，84 C.38，40，46，56，84，79 D.38，46，79，56，40，84
（6）每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做 排序。
A.插入 B.堆 C.快速 D.归并
（7）每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做 排序。
A.插入 B.堆 C.快速 D.归并
（8）设一组初始记录关键字序列（5，2，6，3，8），以第一个记录关机键字5为基准进行一趟快速排序的结果为 。
A.2，3，5，8，6 B.3，2，5，8，6 C.3，2，5，6，8 D.2，3，6，5，8
（9）设有n个待排序的记录关键字，则在堆排序中需要 个辅助记录单元。 A.1 B. n C.nlog2n D.n^2
（10）对于关键字值排序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从关键字值为 的结点开始。 A.100 B.100 C.60 D.15
（11）下列排序方法中， 方法的比较次数与记录的初始排列状态无关。 A.直接插入排序 B.冒泡排序 C.快速排序 D.直接选择排序
（12）设有关键码初始序列｛Q，H，C，Y，P，A，M，S，R，D，F，X｝，新序列｛F，H，C，D，P，A，M，Q，R，S，Y，X｝是采用 方法对初始序列进行第一趟排序的结果。 A.直接插入排序 B.二路归并排序 C.以第一元素为分界元素的快递排序 D.基数排序
（13）在待排序文件已基本有序的前提下，下述排序方法中效率最高的是 。 A.直接插入排序 B.直接选择排序 C.快速排序 D.二路归并排序
（14）排序的算法很多，若按排序的稳定性和不稳定性分类，则 是不稳定排序。 A.冒泡排序 B.归并排序 C.直接插入排序 D.希尔排序
（15）若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选排序方法是 。
A.快速排序 B.堆排序 C.归并排序 D.直接插入排序
（16）将两个各有n个元素的有序表归并成一个有序表，最少的比较次数是 。 A.n B.2n-1 C.2n D.n-1
（17）下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(long2n)的是 。 A.堆排序 B.冒泡排序 C.直接选择排序 D.快速排序
（18）下列排序算法中， 算法可能会出现下面情况：初始数据有序时，花费的时间反
而最多。
A.堆排序 B.冒泡排序 C.快速排序 D.希尔排序 （19）数据表A中有10000个元素，如果仅要求求出其中最大的10个元素，则采用 最节省时间。
A.堆排序 B.希尔排序 C.快速排序 D.直接选择排序
（20）如果只想得到1024个元素组成的序列中第5个最小元素之前的部分排序的序列，用 方法最快。
A.冒泡排序 B.快速排序 C.简单选择排序 D.堆排序 8.2填空题
（1）当待排序的记录数较大、排序码较随机且对稳定性不做要求时，宜采用
____________________排序；当待排序的记录数较大，存储空间允许且要求排序是稳定时，宜采用________________________排序。
（2）在堆排序的过程中，对任意一个分支结点进行筛运算的时间复杂度为_______，整个堆排序过程的时间复杂度为__________。
（3）快速排序、堆排序、归并排序中，_________排序是稳定的。
（4）当向一个大根堆插入一个具有最大值的元素时，需要逐层________调整，直到被调整到_________位置为止。
（5）设一组初始记录关键字序列为（20，18，22，16，30，19），则以20为中轴的一趟快速排序结果为________________________。
（6）设一组初始记录关键字序列为（20，18，22，16，30，19），则根据这些初始关键字序列建成的初始堆为_____________________。
（7）设一组初始记录关键字序列为（49，38，65，97，76，13，27，50），则以d=4为增量的一趟希尔排序结束后的结果为________________________。
（8）对一组初始关键字序列为（40，50，95，20，15，70，60，45，10）进行冒泡排序，则第一趟需要进行相邻记录比较的次数为___________，在整个排序过程中最多需要进行___________趟排序才可以完成。
（9）在插入和选择排序中，若初始数据基本正序，则选用________；若初始数据基本反序，则选用________________。
（10）在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序中，平均比较次数最少的是________________，需要内存容量最多的是________________。
（11）堆排序是不稳定的，空间复杂度为________________。在最坏情况下，其时间复杂度为________________。
（12）若待排序的文件中存在多个关键字相同的记录，经过某种排序方法排序后，具有相同关键字的记录间相对位置保持不变，则这种排序方法是________________的排序方法。 （13）在对一组记录（50，40，95，20，15，70，60，45，80）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较________________次。
（14）在对一组记录（50，40，95，20，15，70，60，45，80）进行希尔排序时，假定取d(i++1)=[di/2]，0 （15）二路归并排序的时间复杂度是________________。 （16）对于n个记录的集合进行归并排序，所需的附加空间消耗是________________。 （17）设表中元素的初始状态是按键值递增的，分别用堆排序，快速排序，冒泡排序和归并排序方法对其仍按递增顺序进行排序，则________________最省时间，________________最费时间。 （18）从无序序列建立堆的方法是：首先将要排序的所有元素分放到一棵________________的各个结点中，然后从i=________________的结点ki开始，逐步把以kn/2，kn/2-1，kn/2-2，…….为根的子树排成堆，直到以k1为根的树排成堆，就完成了建堆的过程。 （19）若待排序的序列中多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方法是________________的，否则称为是________________的。 （20）在利用快速排序方法对一组记录（50，40，95，20，15，70，60，45，80）进行快速排序后，递归调用使用的栈所能达到的最大深度为________________，需递归调用的次数为________________，其中第二次递归调用是对________________组记录进行快速排序。 习题8 参考答案 8．1 选择题 （1）B (2)A (3)D (4)C (5)B (6)A (7)B (8)C (9)A (10)C (11)D (12)C (13) C （14）D （15）C (16)B (17) D 8.2填空题 （1） 快速，归并 （2） O（log2n）,O(nlog2n) （3） 归并 （4） 向上，根结点 （5） 19，18，16，20，30，22 （6） 30 20 23 16 18 19 （7）49，13，27，50，76，38，65，97 （8）8，8 （9）插入，选择（每次选择最大的） （10）快速，归并 (11)O(1), O(nlog2n) (12)稳定 (13)3 (14)(15,20,50,40) (15)O(log2n) (16)O(n2 ) (17)冒泡排序,快速排序 (18)完全二叉树,n/2 (19)稳定,不稳定 （18）C （19）B （20）D 三、判断题(10分) 1.线性表的逻辑顺序总是与其物理顺序一致。（ X ） 2.完全二叉树一定是满二叉树。(X ) 3.顺序表和一维数组一样，都可以按下标随机（或直接）访问。（ V ） 4. 边数很多的稠密图，适宜用邻接矩阵表示。（V ） 5. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。（ V ） 6.若让元素1,2,3依次进栈，则出栈次序1,3,2是不可能出现的情况。（ X ） 7.链表中的头结点仅起到标识的作用。( X) 8. 完全二叉树的某结点若无左孩子，则它必是叶结点。( V ) 9. 使用三元组表示稀疏矩阵中的非零元素能节省存储空间。（V ） 10. 算法和程序原则上没有区别，在讨论数据结构时二者是通用的。( X ) 四、问答求解题 1.已知稀疏矩阵A(下标使用从1开始)如下，写出右边对应格式的压缩存储的三元组表。 i j v 7 0 0 8 0 -1 0 1 3 0 0 0 1 1 1 7 A= 0 0 0 5 0 0 2 1 4 8 0 0 0 0 0 0 3 1 6 -1 9 0 0 0 0 0 4 2 2 1 0 0 0 0 0 0 5 2 3 3 6 3 4 5 7 5 1 9 2．按给定的输入序列：40，20，50，10，30，60构成一棵二叉排序树。（5分） 3. 已知一棵二叉树的前序遍历的结果为ABCDEF，中序遍历的结果为CBAEDF，试画出此二叉树，并写出它的后序遍历序列。 后序遍历序列：CBEFDA