首页 > 教材全解 > 《数据结构（C语言版）——严蔚敏》（清华大学出版社）

《数据结构（C语言版）——严蔚敏》（清华大学出版社）

作者：严蔚敏 吴伟民  出版社：清华大学出版社

返回全部章节 >
题目 题型
试问在10.1题所列各种排序方法中，哪些是稳定的？哪些是不稳定的？并为每一种不稳定的排序方法举出一个不稳定的实例。 问答
试问：对初始状态如下（长度为n）的各序列进行直接插入排序时，至多需进行多少次关键字间的比较（要求排序后的序列按关键字自小至大顺序有序）？     (1)关键字（自小至大）顺序有序；(key1<key2<…<keyn)     (2)关键字 问答
假设我们把n个元素的序列{a1,a2,…,an}中满足条件ak<max{at}(1≤t<k)的元素ak称为“逆序元素”。若在一个无序序列有一对元素ai>aj(i<j)，试问当将ai和aj相互交换之后（即序列由{…ai…aj…}变为{ 问答
奇偶交换排序如下所述：第一趟对所有奇数i，将a[i]和a[i+1]进行比较；第二趟对所有的偶数i，将a[i]和a[i+1]进行比较，若a[i]>a[i+1]，则将两者交换；第三趟对奇数i；第四趟对偶数i，…，依次类推直至整个序列有序为止。 (1)试问 问答
不难看出，对长度为n的记录序列进行快速排序时，所需进行的比较次数依赖于这n个元素的初始排列。 (1)n=7时在最好情况下需进行多少次比较？请说明理由。 (2)对n=7给出一个最好情况的初始排列实例。 问答
试证明：当输入序列已经呈现为有序状态时，快速排序的时间复杂度为O(n2)。 问答
若将快速排序的一次划分改写为如下形式，重写快速排序的算法，并讨论对长度为N的记录序列进行快速排序时在最好的情况下所需进行的关键字间比较的次数（包括三者求中）。 int partition(SqList &L, int low, int h 问答
阅读下列排序算法，并与已学算法相比较，讨论算法中基本操作的执行次数。 void sort(SqList &r, int n) { i=1; while (i<n-i+1) { min = max = 1 问答
试问：按锦标赛排序的思想，决出八名运动员之间的名次排列，至少需编排多少场次的比赛（应考虑最坏的情况）？ 问答
判别以下序列是否为堆（小顶堆或大顶堆）。如果不是，则把它调整为堆（要求记录交换次数最少）。 (1)(100, 86, 48, 73, 35, 39, 42, 57, 66, 21); (2)(12, 70, 33, 65, 24, 56, 48, 92, 问答
一个长度为n的序列，若去掉其中少数k(k<<n)个记录后，序列是按关键字有序的，则称为近似有序序列。试对这种序列讨论各种简单排序方法的时间复杂度。 问答
假设序列由n个关键字不同的记录构成，要求不经排序而从中选出关键字从大到小顺序的前k(k<<n)个记录，试问如何进行才能使所作的关键字间比较次数达到最小？ 问答
对一个由n个关键字不同的记录构成的序列，你能否用比2n-3少的次数选出这n个记录中关键字取最大值和关键字取最小值的记录？若能，请说明如何实现？在最坏情况下至少进行多少次比较？ 问答
已知一个含有n个记录的序列，其关键字均为介于0和n2之间的整数。若利用堆排序等方法进行排序，则时间复杂度为O(nlogn)。如果将每个关键字Ki认作Ki =Ki1n+Ki2，其中Ki1和Ki2都是范围[0, n)中的整数，则利用基数排序只需用O(n)的时间 问答
已知一个单链表由3000个元素组成，每个元素是一整数，其值在1~1000000之间。试考察在第10章给出的几种排序方法中，哪些方法可用于解决这个链表的排序问题？哪些不能？简述理由。 问答
在进行多关键字排序的两种方法中，试思考在什么条件下MSD法比LSD法效率更高？ 问答
假设某大旅店共有5000个床位，每天需根据住宿旅客的文件制造一份花名册，该名册要求按省（市）的次序排列，每一省（市）按县（区）排列，又同一县（区）的旅客按姓氏排列。请你为旅店的管理人员设计一个制作这份花名册的方法。 问答
已知待排序的三个整数a，b和c(a≠b≠c≠a)可能出现的六种排列情况的概率不等，且如下表所示： a<b<c b<a< 问答
分别利用折半插入排序法和2-路归并排序法对含4个记录的序列进行排序，画出描述该排序过程的判定树，并比较它们所需进行的关键字间的比较次数的最大值。 问答
归并插入排序是对关键字进行比较次数最少的一种内部排序方法，它可按如下步骤进行（假设待排序元素存放在数组x[1..n]中）： (1)另开辟两个大小为┏n/2┓的数组small和large。从i=1到n-1，对每个奇数的i，比较x[i]和x[i+1]，将其中较 问答

全站近期热帖

热门推荐

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号