计算机专业基础综合数据结构(排序)-试卷2

计算机专业基础综合数据结构（排序）-试卷2

(总分：56.00，做题时间：90分钟)

一、单项选择题(总题数：16，分数：32.00)

1.单项选择题1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：

2.00）__________________________________________________________________________________________

解析：

2.采用简单选择排序，比较次数与移动次数分别为( )。

（分数：2.00）

A.O(n)，O(log 2 n)

B.O(log 2 n)，O(n 2 )

C.O(n 2 )，O(n) √

D.O(nlog 2 n)，O(n)

解析：解析：简单选择排序的关键字比较次数KCN与对象的初始排列无关。第i趟选择具有最小关键字对象所需的比较次数总是n—i—1次(此处假定整个待排序对象序列有n个对象)。因此，总的关键字比较次

最坏情况是每一趟都要进行交换，总的对象移动次数为RMN=3(n一1)。

3.就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是( )。

（分数：2.00）

A.堆排序＜快速排序＜归并排序√

B.堆排序＜归并排序＜快速排序

C.堆排序＞归并排序＞快速排序

D.堆排序＞快速排序＞归并排序

解析：解析：此题考查的知识点为排序的空间复杂性。堆排序辅助空间为O(1)，快速排序为O(log 2 n)，归并排序为O(n)。应选A。

4.一组记录的关键码为(25，48，16，35，79，82，23，40，36，72)，其中，含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为( )。

（分数：2.00）

A.16，25，35，48，23，40，79，82，36，72 √

B.16，25，35，48，79，82，23，36，40，72

C.16，25，48，35，79，82，23，36，40，72

D.16，25，35，48，79，23，36，40，72，82

解析：解析：对于(25，48，16，35，79，82，23，40，36，72)，(25，48)和(16，35)归并的结果为(16，25，35，48)。(79，82)和(23，40)归并后的结果为(23，40，79，82)，余下的两个记录不归并，所以一趟归并后的结果为(16，25，35，48，23，40，79，82，36，72)，本题答案为A。

5.已知10个数据元素为(54，28，16，34，73，62，95，60，26，43)，对该序列按从小到大排序，经过一趟冒泡排序后的序列为( )。

（分数：2.00）

A.16，28，34，54，73，62，60，26，43，95

B.28，16，34，54，62，73，60，26，43，95 √

C.28，16，34，54，62，60，73，26，43，95

D.16，28，34，54，62，60，73，26，43，95

解析：解析：冒泡排序每趟经过比较、交换，从无序区中产生一个最大的元素，所以选B。

6.用某种排序方法对线性表(25，84，21，47，15，27，68，35，20)进行排序时，元素序列的变化情况如下： (1)25，84，21，47，15，27，68，35，20 (2)20，15，21，25，47，27，68，35，84 (3)15，20，21，25，35，27，47，68，84 (4)15，20，21，25，27，35，47，68，84 其所采用的排序方法是( )。（分数：2.00）

A.直接选择排序√

B.希尔排序

C.归并排序

D.快速排序

解析：解析：可以看到，每趟从无序区中找出一个最大的元素定位，所以答案为A。

7.在对一组记录(50，40，95，20，15，70，60，45，80)进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较( )次。

（分数：2.00）

A.1

B.2

C.3 √

D.4

解析：解析：第6趟的结果为(15，20，40，50，70，95，60，45，80)，此时插入60，要与95、70和50进行比较，共比较3次，本题答案为C。

8.将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是( )。

（分数：2.00）

A.N √

B.2N一1

C.2N

D.N一1

解析：解析：此题考查的知识点是归并排序思想。当第一个有序表中所有的元素都小于第二个表中元素，或者都大于第二个表中元素时，比较次数最少为N。

9.已知待排序的n个元素可分为n／k个组，每个组包含k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为( )。

（分数：2.00）

A.O(nlog 2 n)

B.O(nlog 2 k) √

C.O(klog 2 n)

D.O(klog 2 k)

解析：解析：此题考查的知识点是分块排序的思想。因组与组之间已有序，故将n／k个组分别排序即可，基于比较的排序方法每组的时间下界为O(klog 2k)。可以用二叉树分治形式描述，最好的情况是树的高度为log 2 k。全部时间下界为O(nlog 2 k)。应选B。

10.已知关键序列5，8，12，19，28，20，15，22是小根堆(最小堆)，插入关键字3，调整后得到的小根堆是( )。

（分数：2.00）

A.3，5，12，8，28，20，15，22，19 √

B.3，5，12，19，20，15，22，8，28

C.3，8，12，5，20，15，22，28，19

D.3，12，5，8，28，20，15，22，19

整后的小根堆为3，5，12，8，28，20，15，22，19。

11.归并排序中，归并的趟数是( )。

（分数：2.00）

A.O(n)

B.O(log 2 n) √

C.O(nlog 2 n)

D.O(n 2 )

解析：解析：此题考查的知识点是归并排序。第1遍归并的子序列长度为2 0，第2遍为2 1，…，第i 遍为2 i-1，所以由2 i-1≥n知，对n个记录的数据集合，总共需要归并log 2 n次。应选B。

12.有一组数据(15，9，7，8，20，一1，7，4)，用堆排序的筛选方法建立的初始堆为( )。

（分数：2.00）

A.一1，4，8，9，20，7，15，7

B.一1，7，15，7，4，8，20，9

C.一1，4，7，8，20，15，7，9 √

D.A、B、C均不对

解析：解析：此题考查的知识点是堆排序。应选C。

13.基于比较方法的n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。

（分数：2.00）

A.O(nlog 2 n) √

B.O(log 2 n)

C.O(n)

D.D(n 2 )

解析：解析：此题考查的知识点是各类排序的效率。理论上可以证明，对于基于关键字之间比较的分类，无论用什么方法都至少需要进行log 2 (n!)次比较。由Stirling公式可知，log 2 (n!)=nlog 2 n一1．44n+O(log 2 n)。所以基于关键字比较的分类时间的下界是O(nlog 2 n)。因此不存在时间复杂性低于此下界的基于关键字比较的分类。应选A。

14.以下排序方法中，稳定的排序方法是( )。

（分数：2.00）

A.直接插入排序√

B.直接选择排序

C.堆排序

D.基数排序

解析：解析：下表为各种排序方法的性能比较。由表可知，本题答案为A

15.在对一组记录(50，40，95，20，15，70，60，45，80)进行希尔排序时，假定d 0=9，d 1=4，d 2=2，

d 3 =1，则第二趟排序结束后前4条记录为( )。

（分数：2.00）

A.(50，20，15，70)

B.(60，45，80，50)

C.(15，20，50，40) √

D.(15，20，80，70)

解析：解析：t=3，d 0 =9，d 1 =4，d 2 =2，d 3 =1，第1趟(d 1 =4)后的结果为(15，40，60，20，50，70，95，45，80)，第2趟(d 2=2)后的结果为(15，20，50，40，60，45，80，70，95)，本题答案为(15，20，50，40)。

16.在归并排序中，若待排序记录的个数为20，则共需要进行( )趟归并，在第三趟归并中，是把长度为( )的有序表归并为长度为( )的有序表。

（分数：2.00）

A.5，4，8 √

B.6，3，9

C.7，4，3

D.3，8，2

解析：解析：n=20，共需进行[log 2 n]=5趟归并，第1趟归并后成为10个有序表，第2趟归并后成为5个有序表(每个长度为4)，第3趟归并将长度为4个的有序表归并为长度为8的有序表，本题答案为：5，4，8.

二、综合应用题(总题数：12，分数：24.00)

17.综合应用题41-47小题。（分数：2.00）

__________________________________________________________________________________________ 解析：

18.已知关键字序列(K 1，K 2，K 3，…，K n-1 )是大根堆。试写出一算法将(K 1，K 2，K 3，…，K n-1，K n )调整为大根堆，并利用调整算法写一个建大根堆的算法。

（分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：void sift(RecType R[]，int n){ ／／把R[n]调成大堆int j=n；R[0]=R[j]；for(i=n ／2；i＞=1；i=i／2) if(R[0]．key＞R[i]．key){R[j]=R[i]；j=i；} else break；R[j]=R[0]；} void HeapBuilder(RecType R[]，int n){ for(i=2；i＜=n；i++)sift(R，i)； } 提示：此题考查的知识点是堆的插入算法。从第n个记录开始依次与其双亲(n／2)比较，若大于双亲则交换，继而与其双亲的双亲比较，以此类推直到根为止。)

解析：

19.最小最大堆(min max Heap)是一种特定的堆，其最小层和最大层交替出现，根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最

(1)画出在图中插入关键字为5的结点后的最小最大堆。 (2)画出在图中插入关键字为80的结点后的最小最大堆。 (3)编写一算法实现最小最大堆的插入功能。假定最小最大堆存放在数组中，关键字为整数。

（分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：此题考查的知识点是堆的算法。将插入的元素放到最后，然后调整，方法同第13

题。(1)加入关键字值为5的结点后，最小最大堆如下图。(2)加入关键字值为80的结点后，最小

最大堆如下图。(3)从插入位置进行调整，调整过程由下到上。首先根据元素个数求出插入元素所在层次数，以确定其插入层是最大层还是最小层。若插入元素在最大层，则先比较插入元素是否比双亲小，如是，则先交换，之后，将小堆与祖先调堆，直到满足小堆定义或到达根结点：若插入元素不小于双亲，则调大堆，直到满足大堆定义。若插入结点在最小层，则先比较插入元素是否比双亲大，如是，则先交换，之后，将大堆与祖先调堆；若插入结点在最小层且小于双亲，则将小堆与祖先调堆，直到满足小堆定义或到达根结点。 void MinMaxHeapIns(RecType R[]，int n){ ／／假设R[1．．n一1]是最小最大堆，插入第n个元素，把R[1．．n]调成最小最大堆j=n；R[0]=R[j]；h=log 2n+1；／／求高度if(h％2==0){ ／／插入元素在偶数层，是最大层 i=n／2； if(R[0]．key＜R[i]．key){ ／／插入元素小于双亲，先与双亲交换，然后调小堆 R[j]=R[i]； j=i／4； while(j＞0&&R[j]＞R[i]){ R[i]=R[j]；i=j；j=i／4；} ／／调小堆 R[i]=R[0]i } else{ ／／插入元素大于双亲，调大堆 i=n；j=i／4； while(j＞0&&R[j]＜

R[i]){R[i]=R[1]；i=j；j=i／4；} R[i]=R[0]； } } else{ ／／插入元素在奇数层，是最小层 i=n／2：if(R[0]．key＞R[i]．key){ ／／插入元素大于双亲，先与双亲交换，然后调大堆 R[j]=R[i]； j=i／4；while(j＞0&&R[j]＜R[i]){ R[i]：R[j]=i：j；j=i／4； } ／／调大堆 R[i]=R[0]； } else{ ／／插入元素小于双亲，调小堆 i=n；j=i／4； while(j＞0&&R[j]＞R[i]){ R[i]=R[j]；i=j；j=i／4；}

R[i]=R[0]； } } })

解析：

20.输入N个只含一位数字的整数，试用基数排序的方法，对这N个数排序。

（分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：typedef struct{ int key；int next；}SLRecType；SLRecType R[N+1]；typedef struct{ int f，e： }SLQueue； SLQueue B[10]； int Radixsort(SLRecType R[]，int n){ ／／设各关键字已输入到R数组中 for(i=1；i＜n；i++)R[i]．next=i+l； R[n]．next=一1；P=1；／／一1表示静态链表结束for(i=0；i＜=9：i++){ ／／设置队头队尾指针初值B[i]．f=一1；B[i]．e=一1；} while(p!=一1){ ／／一趟分配k=R[p]．key；／／取关键字if(B[k]．f==一1)B[k]．f=p；／／修改队头指针else R[B[k]．e]．next=p：B[k]．e=p；p=R[p]．next；／／下一记录} i=0：／／一趟收集while(B[i]．f==一1)i++；t=B[i]．e；p=B[i]f：while(i＜9){ i++：if(B[i]．f!=一1){R[t]．next=B[i]．f；t=B[i]．e：} } R[t]．next=一1； return p；／／返回第一个记录指针 } 提示：此题考查的知识点是基数排序。基数排

序法又称“桶子法”(Bucket Sort)，它是透过键值的部分信息，将要排序的元素分配至某些“桶”中，达到排序的目的。基数排序法是属于稳定性的排序，其时间复杂度为O(dn)，其中d为所采取的基数，而n 为关键字数。本题是基数排序的特殊情况，关键字只含一位数字的整数。若关键字含d位，则要进行d趟分配和d趟收集。关键字最好放入字符数组，以便取关键字的某位。)

解析：

21.设有15 000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素。在快速排序、堆排序、归并排序、基数排序和希尔排序中，宜采用哪种方法并说明理由?

（分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：上面所说的几种排序方法中，排序速度都很快，但快速排序、归并排序、基数排序和希尔排序都是在排序结束后才能确定数据元素的全部序列，而排序过程中无法知道部分连续位置上的最终元素。而堆排序则是每次输出一个堆顶元素(即最大或最小值的元素)，然后对堆进行再调整，保证堆顶元素总是当前剩下元素的最大或最小的，从而可知，如果在一个大量数据的文件中，如含有15 000个元素的记录文件中选取前10个最大的元素，宜采用堆排序。)

解析：

22.对一个具有7个记录的文件进行快速排序，请问： (1)在最好情况下需进行多少次比较?说明理由，并给出相应实例。 (2)在最坏情况下需进行多少次比较?为什么?请给出相应实例。

（分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：(1)在最好情况下，由于快速排序是一个划分子区间的排序，每次划分时最好能得到两个长度相等的子文件。设文件的长度为n=2k一1，显然，第一遍划分得到两个长度均为[n／2]的子文件。第二遍划分得到4个长度均为[n／4]的子文件，以此类推，总共进行k=log 2(n+1)遍划分，各文件的长度均为l，此时排序结束。由于n=7，k=3，在最好情况下，第一遍经过6次，可找到一个基元是正中间的元素；第二遍分别对两个子文件(此时长度为3)进行排序，各需要2次，这样就可将整个文件排序完毕，从而知n=7的最好情况下需进行10次比较。例如：4，7，5，6，3，1，2。 (2)在最坏情况下，若每次划分时用的基元，它的关键字值是当前记录中最大(或最小)，那么每次划分只能得到左子文件(或右子文件)。子文件长度只比原文件减少一个。因此，若初始排列的记录是按关键字递增或递减，而所得的结果必须为递减或递增排列，那么此时，快速排序就退化为与冒泡排序相似，而且时间复杂度为O(n 2)，反而不快了。对于n=7的记录文件，显然最坏情况下的比较次数为21。例如：7，6，5，4，3，2，1.)

解析：

23.判断下列序列是否为堆，若不是堆，则把它们调整为堆。(1)(100，85，95，75，80，60，82，40，20，10，65) (2)(100，95，85，82，80，75，65，60，40，20，10) (3)(100，85，40，75，80，60，65，95，82，10，20) (4)(10，20，40，60，65，75，80，82，85，95，100)

（分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：依据堆定义可知：序列(1)、(2)、(4)是堆，(3)不是堆，从而可对其调整使之成为大根堆(100，95，65，85，80，60，40，75，82，10，20)。)

解析：

24.将十进制的关键字用二进制数表示，对基数排序所需的时间和附设空间分别有什么影响?各是多少? （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：因为基数排序所需的时间不仅与文件的大小n有关，而且与关键字的位数和关键字的基数有关。设关键字的基数为r，显然，十进制数基数为10，二进制数的基数为2。要建立r个空队列所需时间为O(r)；把n个记录分放到各个队列中，重新收集起来需要的时间为O(n)，因此一趟排序所需的时间复杂度为O(n+r)；若每个关键字有d位，则总共要进行d遍排序，所以基数排序的时间复杂度为

O(d(n+r))。由于关键字的位数d与基数r和最大关键字取值有关。因此不同的r和关键字将需要不同的时间。所以，本题中总的时间复杂度为O(d(n+2))，d为关键字最大值对应的二进制数位数，即将十进制的关键字用二进制数表示时，复杂度增大了。另外只需要设置两个指针队列，即将十进制的关键字用二进制数表示时，空间复杂性减少了。)

解析：

25.写出快速排序的非递归算法。

（分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：设对记录R[1．．n]进行快速排序，要求用非递归算法。利用一个包含有low和high 两个整数成员的记录数组stack[]作为栈，low和high成员分别指示某个子文件的首、尾记录的下标号。算法如下： void quicksort(SeqList R，int n){／／设待排序记录放在R[1．．n]中，下标从1开始 int i，j，low，high，top=0；struct{ int low，high；}stack[Max]；／／Max为一个大于n的常量RecType temp；top=1；stack[top]．low=1；stack[top]．high=n；／／入栈 while(top＞0){ ／／栈非空，则取出一个子文件进行划分low=stack[top]．low；high=stack[top]．high；top一一；／／出栈i=low；j=high；temp=R[i]； do{ while(i＜j&&R[i]．key＞temp．key)j--； if(i＜j){ R[i]=R[j]；i++； while(i＜

j&&R[i]．key＜temp．key)i++；if(i＜j){R[j]=R[i]；j一一；} } }while(i==j)；／／划分结束R[i]=temp；／／基元元素插入 if(i+1＜high){ ／／右子文件有两个以上记录，则首、尾位置入栈 top++：

stack[top]．low=i+1；stack[top]．high=high； } if(low＜i一1){ ／／左子文件有两个以上记录，则首、尾位置入栈 top++；stack[top]．low=low；stack[top]．high=i一1； } } })

解析：

26.试设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字之前，并分析算法的时间复杂度。

（分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：采用类似于快速排序中的划分思想。算法如下：void part(KeyType A[]，int n){ int i=1；j=n；KeyType temp；while(i＜j){ while(i＜j&&A[j]＞=0)．j-一；／／从右向左找负数while(i ＜j&&A[i]＜0)i++；／／从左向右找非负数if(i＜j){ ／／交换元素A[i]和A[j] temp=A[i]；A[i]=A[j]；A[j]=temp； i++；j一一； } } } 该算法的时间复杂度为O(n)。)

解析：

27.写一个HeapInsen(R,key)算法，将关键字插入到堆R中，并保证插入后R仍是堆。请分析算法的时间复杂度。提示：将key先插入R中已有元素的尾部(即原堆的长度加1的位置，插入后堆的长度加1)，然后自下往上调整，使插入的关键字满足堆性质。

（分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：算法如下： typedef struct{ KeyType key； InfoType otherinfo； }RecType；typedef struct{ RecType Rec[MaxNum]；／／MaxNum是一个常量int len；}SeqList；HeapInsert(SeqList R，KeyType key){ int i，j： R．Rec[++R．len]．key=key；／／增加新值到原堆中已有元素的尾部且堆的长度加1 i=R．1en／2；j=R．len； while(i＞0){ ／／调整为堆 if(R．Rec[i]．key＜

R．Rec[j]．key){ R．Rec[0]=R．Rec[i]；R．Rec[i]=R．Rec[j]；R．Rec[i]=R．Rec[0]； } j=i；i=i ／2；／／继续自底向上查找 } } 设该堆对应的树高为h，则满足h≤log 2 R．len，调整是自底向上查找，最多查找到树根，所以时间复杂度为O(log 2 R．len)。)

解析：

28.写一个建立堆的算法：从空堆开始，依次读入元素，调用上题中堆插入算法将其插入堆中。

（分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：建立堆的算法如下： void BuildHeap(SeqList R，KeyType A[n]){ ／／类型定义int i： R．len=0；／／初始化 for(i=0：i＜n；i++)Heaplnsert(R，A[i])： })

解析：

计算机专业基础综合数据结构(排序)-试卷2

计算机专业基础综合数据结构（排序）-试卷2 (总分：56.00，做题时间：90分钟) 一、单项选择题(总题数：16，分数：32.00) 1.单项选择题1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数： 2.00）__________________________________________________________________________________________ 解析： 2.采用简单选择排序，比较次数与移动次数分别为( )。 （分数：2.00） A.O(n)，O(log 2 n) B.O(log 2 n)，O(n 2 ) C.O(n 2 )，O(n) √ D.O(nlog 2 n)，O(n) 解析：解析：简单选择排序的关键字比较次数KCN与对象的初始排列无关。第i趟选择具有最小关键字对象所需的比较次数总是n—i—1次(此处假定整个待排序对象序列有n个对象)。因此，总的关键字比较次 最坏情况是每一趟都要进行交换，总的对象移动次数为RMN=3(n一1)。 3.就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是( )。 （分数：2.00） A.堆排序＜快速排序＜归并排序√ B.堆排序＜归并排序＜快速排序 C.堆排序＞归并排序＞快速排序 D.堆排序＞快速排序＞归并排序 解析：解析：此题考查的知识点为排序的空间复杂性。堆排序辅助空间为O(1)，快速排序为O(log 2 n)，归并排序为O(n)。应选A。 4.一组记录的关键码为(25，48，16，35，79，82，23，40，36，72)，其中，含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为( )。 （分数：2.00） A.16，25，35，48，23，40，79，82，36，72 √ B.16，25，35，48，79，82，23，36，40，72 C.16，25，48，35，79，82，23，36，40，72 D.16，25，35，48，79，23，36，40，72，82 解析：解析：对于(25，48，16，35，79，82，23，40，36，72)，(25，48)和(16，35)归并的结果为(16，25，35，48)。(79，82)和(23，40)归并后的结果为(23，40，79，82)，余下的两个记录不归并，所以一趟归并后的结果为(16，25，35，48，23，40，79，82，36，72)，本题答案为A。 5.已知10个数据元素为(54，28，16，34，73，62，95，60，26，43)，对该序列按从小到大排序，经过一趟冒泡排序后的序列为( )。 （分数：2.00） A.16，28，34，54，73，62，60，26，43，95 B.28，16，34，54，62，73，60，26，43，95 √ C.28，16，34，54，62，60，73，26，43，95 D.16，28，34，54，62，60，73，26，43，95 解析：解析：冒泡排序每趟经过比较、交换，从无序区中产生一个最大的元素，所以选B。 6.用某种排序方法对线性表(25，84，21，47，15，27，68，35，20)进行排序时，元素序列的变化情况如下： (1)25，84，21，47，15，27，68，35，20 (2)20，15，21，25，47，27，68，35，84 (3)15，20，21，25，35，27，47，68，84 (4)15，20，21，25，27，35，47，68，84 其所采用的排序方法是( )。（分数：2.00） A.直接选择排序√

数据结构课程设计(内部排序算法比较_C语言)

数据结构课程设计 课程名称：内部排序算法比较 年级/院系：11级计算机科学与技术学院 姓名/学号： 指导老师： 第一章问题描述 排序是数据结构中重要的一个部分，也是在实际开发中易遇到的问题，所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决！该系统通过对各种内部排序算法如直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序、二路归并排序等，以关键码的比较次数和移动次数分析其特点，并进行比较，估算每种算法的时间消耗，从而比较各种算法的优劣和使用情况！排序表的数据是多种不同的情况，如随机产生数据、极端的数据如已是正序或逆序数据。比较的结果用一个直方图表示。

第二章系统分析 界面的设计如图所示： |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| 请选择操作方式： 如上图所示该系统的功能有： （1）：选择1 时系统由客户输入要进行测试的元素个数由电脑随机选取数字进行各种排序结果得到准确的比较和移动次数并 打印出结果。 （2）选择2 时系统由客户自己输入要进行测试的元素进行各种排序结果得到准确的比较和移动次数并打印出结果。 （3）选择0 打印“谢谢使用！！”退出系统的使用！！ 第三章系统设计 （I）友好的人机界面设计：（如图3.1所示） |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------|

数据结构模拟试题及答案

数据结构模拟试题一 一、判断题（每小题1 分，共15分） 1.计算机程序处理的对象可分为数据和非数据两大类。 2.全体自然数按大小关系排成的序列是一个线性表。 3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。 4.顺序栈是一种规定了存储方法的栈。 5.树形结构中的每个结点都有一个前驱。 6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。 7.若某顶点是有向图的根，则该顶点的入度一定是零。 8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。 9.用一维数组表示矩阵可以节省存储空间。 10.广义表的长度与广义表中含有多少个原子元素有关。 11.分块查找的效率与线性表被分成多少块有关。 12.散列表的负载因子等于存入散列表中的结点个数。 13.在起泡排序过程中，某些元素可能会向相反的方向移动。 14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。 15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。 二、填空题（每空1分，共15分） 1.顺序表是一种_____________线性表。 2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。 3.栈和队列的区别在于________的不同。 4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。 5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域 为空的结点。 6.n个顶点的有根有向图中至少有___条边，至多有___条边。 7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。 8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是 _____。 9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。 10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。 三、选择题（每题2分，共30分） 1.计算机所处理的数据一般具有某种内在联系性，这是指________。 A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系 C．元素内部具有某种结构D．数据项和数据项之间存在某种关系 2. 假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4 。若把新插入元素存入R[6]，则________。 A．会产生运行错误B．R[1]~R[6]不构成一个顺序表 C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率 D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦 3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后一个结点时，_________。A．P所指结点指针字段的值为空B．P的值与H的值相等 C．P所指结点的地址与H的值相等D．P所指结点指针字段的值与H的值相等 4. 栈的定义不涉及数据的__________。 A．逻辑结构B．存储结构C．运算D．逻辑结构和存储结构 5. 设5个元素进栈的顺序是1,2,3,4,5，则出栈的顺序有可能是___________。 A．2,4,1,3,5 B．3,4,1,5,2 C．3,2,4,1,5 D．4,1,3,2,5 6. 若某棵二叉树结点的前序序列和中序序列相同，则该二叉树_________。 A．只有一个结点B．每个结点都没有左孩子C．每个结点都没有右孩子D．不存在 7.对于一棵具有n个结点，度为3的树来说，____________。 A．树的高度至多是n-3 B．树的高度至多是n-2 C．树的最低高度是┏log3(n+1)┓ D．至少在某一层上正好有3个结点 8．n个顶点的有向图如果可以进行拓扑排序，则可以断定该有向图__________。 A．含n个强连通分量B．有唯一的入度为0的顶点C．有多个出度为0的顶点 D．是一个有根有向图 9. 特殊矩阵用行优先顺序表表示，_____________ A．简化了矩阵元素之间的逻辑关系B．便于按行处理矩阵元素

数据库概论 习题参考答案

第1章绪论习题参考答案 1、试述数据、数据库、数据库管理系统、数据库系统的概念。（参见P3、4、5页） 参考答案： 描述事物的符号记录称为数据；数据库是长期储存在计算机内的、有组织的、可共享的数据集合；数据库管理系统是位于用户与操作系统之间的一层数据管理软件; 数据库系统是指在计算机系统中引入数据库后的系统，一般由数据库、数据库管理系统(及其开发工具)、应用系统、数据库管理员和用户构成。 2．使用数据库系统有什么好处?（参见P12页） 参考答案： 数据库系统使信息系统从以加工数据的程序为中心转向围绕共享的数据库为中心的阶段，这样既便于数据的集中管理，又有利于应用程序的研制和维护，提高了数据的利用率和相容性，提高了决策的可靠性。 3．试述文件系统与数据库系统的区别和联系。（8、9、10页） 参考答案： 1）数据结构化是数据库与文件系统的根本区别。 在文件系统中，相互独立的文件的记录内部是有结构的，管其记录内部已有了某些结构，但记录之间没有联系。数据库系统实现整体数据的结构化，是数据库的主要特征之一。 2）在文件系统中，数据的最小存取单位是记录，粒度不能细到数据项。而在数据库系统中，存取数据的方式也很灵活，可以存取数据库中的某一个数据项、一组数据项一个记录或或一组记录。 3）文件系统中的文件是为某一特定应用服务的，文件的逻辑结构对该应用程序来说是优化的，因此要想对现有的数据再增加一些新的应用会很困难，系统不容易扩充。而在数据库系统中数据不再针对某一应用，而是面向全组织，具有整体的结构化。5．试述数据库系统的特点。（9、10、11页） 参考答案： 数据结构化；数据的共享性高、冗余度低、易扩充；数据独立性高；数据由DBMS统一管理和控制。 6．数据库管理系统的主要功能有哪些? （4页）

数据结构第十章习题课

1．下列排序算法中，其中（）是稳定的。 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序 2．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。 A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序3．排序趟数与序列的原始状态有关的排序方法是( )排序法。 A．插入 B. 选择 C. 冒泡 D. 快速4．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中 的变化为（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47 （4） 15 21 25 47 84 则采用的排序是( )。 A. 选择 B. 冒泡 C. 快速 D. 插入5．对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（）排序。 A. 选择 B. 快速 C. 希尔 D. 冒泡6．若上题的数据经一趟排序后的排列为{9，15，7，8，20，-1，4}，则采用的 是（）排序。 A．选择 B. 堆 C. 直接插入 D. 冒泡 7．在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（）A．直接插入排序B．冒泡排序C．简单选择排序 8．下列排序算法中，（）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。 A. 堆排序 B. 冒泡排序 C. 快速排序 D. 插入排序 9. 下列排序算法中，占用辅助空间最多的是：( ) A. 归并排序 B. 快速排序 C. 希尔排序 D. 堆排序10．用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数 最少的是（）。 A．94,32,40,90,80,46,21,69 B．32,40,21,46,69,94,90,80 C．21,32,46,40,80,69,90,94 D．90,69,80,46,21,32,94,40 11. 若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（）次比较。 A. 3 B. 10 C. 15 D. 25 12．对n个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确

数据结构各种排序方法的综合比较

数据结构各种排序方法的综合比较 结论: 排序方法平均时间最坏时间辅助存储 简单排序O(n2) O(n2) O(1) 快速排序O(nlogn)O(n2)O(logn) 堆排序O(nlogn)O(nlogn)O(1) 归并排序O(nlogn)O(nlogn)O(n) 基数排序O(d(n+rd))O(d(n+rd))O(rd) PS:直接插入排序、冒泡排序为简单排序，希尔排序、堆排序、快速排序为不稳定排序 一、时间性能 按平均的时间性能来分，有三类排序方法： 时间复杂度为O(nlogn)的方法有：快速排序、堆排序和归并排序，其中以快速排序为最好；时间复杂度为O(n2)的有：直接插入排序、起泡排序和简单选择排序，其中以直接插入为 最好，特别是对那些对关键字近似有序的记录序列尤为如此； 时间复杂度为O(n)的排序方法只有，基数排序。 当待排记录序列按关键字顺序有序时，直接插入排序和起泡排序能达到O(n)的时间复杂度;而对于快速排序而言，这是最不好的情况，此时的时间性能蜕化为O(n2)，因此是应该尽量避免的情况。简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。 二、空间性能 指的是排序过程中所需的辅助空间大小。 1. 所有的简单排序方法(包括：直接插入、起泡和简单选择)和堆排序的空间复杂度为O(1)； 2. 快速排序为O(logn)，为栈所需的辅助空间; 3. 归并排序所需辅助空间最多，其空间复杂度为O(n ); 4.链式基数排序需附设队列首尾指针，则空间复杂度为O(rd)。 三、排序方法的稳定性能 1. 稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。 2. 当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法。 3. 对于不稳定的排序方法，只要能举出一个实例说明即可。 4. 快速排序和堆排序是不稳定的排序方法

大工数据结构课程考试模拟试卷a

少年易学老难成，一寸光阴不可轻- 百度文库 《数据结构》 一、单项选择题（本大题共10小题，每小题3分，共30分） 1、若进栈的序列为1，2，3，4，则不可能得到的出栈序列是（）。 A. 3,2,1,4 B. 3,2,4,1 C. 4,2,3,1 D. 2,3,4,1 2、深度为k的完全二叉树所含叶结点的个数最多为（），设根结点在第1层上。 A. 2k B. 2k-1 C. k D. 2k-1 3、衡量查找算法效率的主要标准是（）。 A. 元素个数 B. 所需的存储量 C. 平均查找长度 D. 算法难易程度 4、与线性表的顺序存储不相符的特性是（）。 A. 插入和删除操作灵活 B. 需要连续的存储空间 C. 便于随机访问 D. 存储密度大 5、若进队序列为1，2，3，则出队序列是（）。 A. 3,2,1 B. 1,2,3 C. 1,3,2 D. 3,1,2 6、不带头结点的单链表L为空的判定条件是（）。 A. L==NULL B. L->next==NULL C. L->next==L D. L!=NULL 7、union(A,B,C)表示求集合A和B的并集C。若A={a,b,c},B={c,d},则union(A,B,C)运算后C=（）。 A．{a,b,c,d} B．{a,b,c} C．{a,b} D．{c,d} 8、数组A中，每个元素的长度为3个存储单元，行下标i从1到5，列下标j从1到6，从首地址SA开始连续存放在存储器内，存放该数组至少需要的存储单元数是（）。 A. 90 B. 70 C. 50 D. 30 9、遍历一棵具有n个结点的二叉树，在先序序列、中序序列和后序序列中所有叶子结点的相对次序（）。 A. 都不相同 B. 完全相同 C. 先序和中序相同 D. 中序和后序相同 10、用给定的哈夫曼编码来压缩数据文件，其压缩效率主要取决于（）。 A. 文件长度 B. 平均码长 C. 被压缩文件的特征 D. 以上都不是 1、设有如下遗产继承规则：丈夫和妻子可以互相继承遗产，子女可以继承父亲或母亲的遗产，子女间不能相互继承，则表示该遗产继承关系的最合适的数据结构应该是（）。 A. 树 B. 图 C. 数组 D. 二叉树 2、下列排序中，占用辅助空间最多的是（）。 A. 堆排序 B. 冒泡排序 C. 直接选择排序 D. 二路归并 3、排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（）。 A. 选择排序 B. 冒泡排序 C. 希尔排序 D. 插入排序 4、在待排序序列局部有序的情况下，最好的内部排序应该是（）。 A. 直接选择排序 B. 堆排序 C. 直接插入排序 D. 快速排序 5、下列排序算法中不稳定的是（）。 A. 直接选择排序 B. 直接插入排序 C. 起泡排序 D. 归并排序 6、当利用大小为N的数组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时，首先应执行（）语句修改top指针。 A. top++ B. top-- C. top=0 D. top=N-1 7、在一个带头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（）个指针域的值。 A. 2 B. 3 C. 4 D. 5 8、利用3,6,8,12,5,7这六个值作为叶子结点的权，生成一棵哈夫曼树，该树的深度为（）。 A. 3 B. 4

数据结构(本)期末综合练习

数据结构（本）期末综合练习 综合练习一 一、单项选择题 1．设有头指针为head的带有头结点的非空单向循环链表, 指针p指向其尾结点, 要删除头结点,并使其仍为单向循环链表,则可利用下述语句head =head->next ;（）。 A．p =head; B．p=NULL; C．p->next =head; D．head=p; 2．在一个单链表中p指向结点a, q指向结点a的直接后继结点b，要删除结点b，可执行（）。 A．p->next=q->next ; B．p=q->next; C．p->next=q; D．p->next=q; 3. 以下说法不正确的是 A. 线性表的链式存储结构不必占用连续的存储空间 B．一种逻辑结构只能有唯一的存储结构 C. 一种逻辑结构可以有不同的存储结构 D．线性表的顺序存储结构必须占用连续的存储空间 4．在一个单向链表中,在p所指结点之后插入一个s所指的结点时，可执行（）;和p->next=s; A．p= s; B．p->next=s->next; C．p=s->next; D．s->next=p->next; 5．把数据存储到计算机中，并具体体现( )称为物理结构。 A. 数据元素间的逻辑关系 B．数据的处理方法 C．数据的性质 D．数据的运算 6．设有一个长度为23的顺序表，要删除第8个元素需移动元素的个数为（）。 A．16 B．14 C．15 D．13 7．链表所具备的特点之一是（）。 A．可以随机访问任一结点B．需要占用连续的存储空间 C．插入元素的操作不需要移动元素D．删除元素的操作需要移动元素 8．设一棵有8个叶结点的二叉树，度数为1的结点有3个,则该树共有（） 个结点。 A．20 B．18 C．17 D．16 9．图状结构中数据元素的位置之间存在（）的关系。 A．一对一B．多对多 C．一对多D．每一个元素都有一个直接前驱和一个直接后继 10．一棵具有5层的完全二叉树，最后一层有4个结点，则该树总共有（）个结点。 A．14 B．15 C．19 D．18 11．元素15，9，11，13按顺序依次进栈，则该栈的不可能输出序列是（） （进栈出栈可以交替进行）。 A．13，11，9，15 B．15，9，11，13 C．13，11，15，9 D．9，15，13，11 12.设主串为“FABcCDABcdEFaBc”，以下模式串能与主串成功匹配的是（）。 A. EFaBc B. ABCdE C. DABCC D .FAbcC 13．设有一个14阶的对称矩阵A(第一个元素为a1,1)，采用压缩存储的方式，将其下三角部分以行序为主序存

数据结构中的内部排序算法及性能分析

数据结构中的排序算法及性能分析 一、引言 排序（sorting ）是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。为了查找方便通常希望计算机中的表是按关键字有序的。因为有序的顺序表可以使用查找效率较高的折半查找法。 在此首先明确排序算法的定义： 假设n 个记录的序列为 { 1R ，2R ，…n R } （1） 关键字的序列为： { 1k ，2k ，…，n k } 需要确定1，2，…，n 的一种排列：12,n p p p ，…，使（1）式的序列成为一个按关键字有序的序列： 12p p pn k k k ≤≤≤… 上述定义中的关键字Ki 可以是记录Ri （i=1,2，…，n ）的主关键字，也可以是记录i R 的次关键字，甚至是若干数据项的组合。若在序列中有关键字相等的情况下，即存在i k =j k （1,1,i n j n i j ≤≤≤≤≠），且在排序前的序列中i R 领先于j R 。若在排序后的序列中Ri 仍领先于j R ，则称所用的排 序方法是稳定的；反之若可能使排序后的序列中j R 领先于i R ，则称所用的排序方法是不稳定的。 一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法的时间与算法中语句执行次数成正比，那个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度，记为T(n)。 在刚才提到的时间频度中，n 称为问题的规模，当n 不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。 一般情况下，算法中基本操作重复执行的次数是问题规模n 的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n 趋近于无穷大时，T （n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。

数据结构模拟试题1

一、单项选择题（在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。每小题2分，共40分） 1、串的长度是（）。 A、串中不同字母的个数 B、串中不同字符的个数 C、串中所含字符的个数，且大于0 D、串中所含字符的个数 2、若用数组S[1..n]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（）。 A、S1的栈底位置为0，S2的栈底位置为n+1 B、S1的栈底位置为0，S2的栈底位置为n/2 C、S1的栈底位置为1，S2的栈底位置为n D、S1的栈底位置为1，S2的栈底位置为n/2 3、队列操作的原则是（）。 A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除 4、有64个结点的完全二叉树的深度为（）（根的层次为1）。 A、8 B、7 C、6 D、5 5、在有n个结点的二叉链表中，值为非空的链域的个数为（）。 A、n-1 B、2n-1

C、n+1 D、2n+1 6、带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中（）。 A、第i行非∞的元素之和 B、第i列非∞的元素之和 C、第i行非∞且非0的元素个数 D、第i列非∞且非0的元素个数 7、在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。 A、0(n) B、0(log2n) C、0(nolg2n) D、0(n2) 8、若表R在排序前已按键值递增顺序排列，则（）算法的比较次数最少。 A、直接插入排序 B、快速排序 C、归并排序 D、选择排序 9、下列排序算法中，（）排序在某趟结束后不一定选出一个元素放到其最终的位置上。 A、选择 B、冒泡 C、归并 D、堆

数据结构综合练习题

数据结构综合练习题

数据结构（一） 一、选择题 1．组成数据的基本单位是（ C ）。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A 是（ C ）。 (A) 线性结构(B) 树型结构(C) 图型结构(D) 集合 3．数组的逻辑结构不同于下列（ D ）的逻辑结构。(A) 线性表(B) 栈(C) 队列(D) 树 4．二叉树中第i(i≥1)层上的结点数最多有（C ）个。 (A) 2i (B) 2i(C) 2i-1(D) 2i-1 5．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（A ）。 (A) p->next=p->next->next (B) p=p->next (C) p=p->next->next (D) p->next=p 6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（ C ）。 (A) 6 (B) 4 (C) 3 (D) 2

7．将10阶对称矩阵压缩存储到一维数组A中，则数组A 的长度最少为（ C ）。 (A) 100 (B) 40 (C) 55 (D) 80 8．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（ B ）。 (A) 3 (B) 4 (C) 5 (D) 1 9．根据二叉树的定义可知二叉树共有（ B ）种不同的形态。 (A) 4 (B) 5 (C) 6 (D) 7 10.设有以下四种排序方法，则（ B ）的空间复 杂度最大。 (A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序 11、以下说法正确的是（ A ） A.连通图的生成树，是该连通图的一个极小连通子图。 B.无向图的邻接矩阵是对称的，有向图的邻接矩阵一定是不对称的。 C.任何一个有向图，其全部顶点可以排成一个拓扑序列。 D.有回路的图不能进行拓扑排序。 12、以下说法错误的是 ( D ) A.一般在哈夫曼树中，权值越大的叶子离根结点越近 B.哈夫曼树中没有度数为1的分支结点 C.若初始森林中共有n裸二叉树，最终求得的哈夫曼树

数据结构课程设计(内部排序算法比较 C语言)

课题：内部排序算法比较 第一章问题描述 排序是数据结构中重要的一个部分，也是在实际开发中易遇到的问题，所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决！该系统通过对各种内部排序算法如直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序、二路归并排序等，以关键码的比较次数和移动次数分析其特点，并进行比较，估算每种算法的时间消耗，从而比较各种算法的优劣和使用情况！排序表的数据是多种不同的情况，如随机产生数据、极端的数据如已是正序或逆序数据。比较的结果用一个直方图表示。 第二章系统分析 界面的设计如图所示： |******************************| |-------欢迎使用---------| |-----（1）随机取数-------|

|-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| 请选择操作方式： 如上图所示该系统的功能有： （1）：选择 1 时系统由客户输入要进行测试的元素个数由电脑随机选取数字进行各种排序结果得到准确的比较和移动次数并打印出结果。 （2）选择 2 时系统由客户自己输入要进行测试的元素进行各种排序结果得到准确的比较和移动次数并打印出结果。 （3）选择0 打印“谢谢使用！！”退出系统的使用！！ 第三章系统设计 （I）友好的人机界面设计：（如图3.1所示） |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| （3.1） （II）方便快捷的操作：用户只需要根据不同的需要在界面上输入系统提醒的操作形式直接进行相应的操作方式即可！如图（3.2所示） |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------|

数据结构模拟卷(含答案)经典习题培训讲学

数据结构模拟卷(含答案)经典习题

练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4

6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位10. 下列图示的顺序存储结构表示的二叉树是( )

数据结构第九、十章 作业答案

第九章 查找 一、填空题 1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。 2. 线性有序表（a 1，a 2，a 3，…，a 256)是从小到大排列的，对一个给定的值k ，用二分法检索 表中与k 相等的元素，在查找不成功的情况下，最多需要检索 8 次。设有100个结点，用二分法查找时，最大比较次数是 7 。 3. 假设在有序线性表a[1..20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ,其下标从小到大依次是1,3,6,8,11,13,16,19______，平均查找长度为 3.7 。 解：显然，平均查找长度＝O （log 2n ）<5次（25）。但具体是多少次，则不应当按照公式 )1(log 12++=n n n ASL 来计算（即（21×log 221）/20＝4.6次并不正确！）。因为这是在假设n ＝2m -1 的情况下推导出来的公式。应当用穷举法罗列： 全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL ＝74/20=3.7 ！！！ 4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它 将依次与表中元素 28，6，12，20 比较大小。 5. 在各种查找方法中，平均查找长度与结点个数n 无关的查找方法是 散列查找 。 6. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。 7. 有一个表长为m 的散列表，初始状态为空，现将n （n

计算机专业基础综合数据结构(排序)历年真题试卷汇编1

计算机专业基础综合数据结构（排序）历年真题试卷汇编1 (总分：72.00，做题时间：90分钟) 一、单项选择题(总题数：15，分数：30.00) 1.下列序列中，( )是执行第一趟快速排序后所得的序列。【福州大学1998一、9(2分)】 A.[68，11，18，69] [23，93，73] B.[68，11，69，23] [18，93，73] C.[93，73][68，11，69，23，18] √ D.[68，11，69，23，18] [93，73] 枢轴是73。 2.适合并行处理的排序算法是( )。【西安电子科技大学2005一、8(1分)】【电子科技大学2005一、8(1分)】 A.选择排序 B.快速排序√ C.希尔排序 D.基数排序 3.一组记录的关键字为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为( )。【北京交通大学2005一、8(2分)【燕山大学2001一、4(2分)】 A.(38，40，46，56，79，84) B.(40，38，46，79，56，84) C.(40，38，46，56，79，84) √ D.(40，38，46，84，56，79) 如何对一趟快速排序的结果在最短的时间内做出正确判断，这里给出建议：首先84应该不动，所以D排除了；接着40应调到序列首，所以A排除了；接着79应调到移走40的空位上，B排除了。选择答案C，不必再继续做了(假定确有唯一正确答案)。 4.下列排序算法中，( )算法可能会出现下面的情况：初始数据有序时，花费的时间反而最多。【中南大学2005一、4(2分)】 A.快速排序√ B.堆排序 C.希尔排序 D.冒泡排序 5.将一组无序的数据重新排列成有序序列，其方法有：( )。【武汉理工大学2004一、8(3分)】 A.拓扑排序 B.快速排序√ C.堆排序√ D.基数排序√ 6.就平均性能而言，目前最好的内排序方法是( )排序法。【西安电子科技大学1998一、9(2分)】 A.冒泡 B.希尔插，A C.交换 D.快速√ 7.如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用( )方法最快。【清华大学1998一、2(2分)】 A.起泡排序 B.快速排列 C.Shell排序 D.堆排序√ E.简单选择排序

数据结构与算法 模拟试卷三四及参考答案

模拟试卷三 一、单选题（每题 2 分，共20分） 1.对一个算法的评价，不包括如下（）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3.对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5.AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。 A．行号B．列号C．元素值D．非零元素个数 9.快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、运算题（每题 6 分，共24分） 1.数据结构是指数据及其相互之间的______________。当结点之间存在M对N（M：N） 的联系时，称这种结构为_____________________。 2.队列的插入操作是在队列的_________进行，删除操作是在队列的__________进行。 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件 是_____________________。 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为_________， 在表尾插入元素的时间复杂度为____________。 5.设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7 ，列下标j 从0到3 ，则二维数组W的数据元素共占用＿_____＿个字节。W中第6 行的元素和第4 列的元素共占用＿_______＿个字节。若按行顺序存放二维数组W，其起始地址为100，则二维数组元素W[6，3]的起始地址为＿________＿。 6.广义表A= (a,(a,b),((a,b),c)),则它的深度为____________，它的长度为____________。 7.二叉树是指度为2的____________________树。一棵结点数为N的二叉树，其所有结 点的度的总和是_____________。 8.对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个______________。对一棵由 算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的

目前最完整的数据结构1800题包括完整答案 第十章 排序

第10章排序 一、选择题 1．某内排序方法的稳定性是指( )。【南京理工大学 1997 一、10（2分）】A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录 C．平均时间为0（n log n）的排序方法 D．以上都不对 2．下面给出的四种排序法中( )排序法是不稳定性排序法。【北京航空航天大学 1999 一、 10 （2分）】 A. 插入 B. 冒泡 C. 二路归并 D. 堆积 3．下列排序算法中，其中（）是稳定的。【福州大学 1998 一、3 (2分)】 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序 4．稳定的排序方法是（）【北方交通大学 2000 二、3（2分）】 A．直接插入排序和快速排序 B．折半插入排序和起泡排序 C．简单选择排序和四路归并排序 D．树形选择排序和shell排序 5．下列排序方法中，哪一个是稳定的排序方法？（）【北方交通大学 2001 一、8（2分）】 A．直接选择排序 B．二分法插入排序 C．希尔排序 D．快速排序6．若要求尽可能快地对序列进行稳定的排序，则应选（A．快速排序 B．归并排序 C．冒泡排序）。 【北京邮电大学 2001 一、5（2分）】 7．如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。（）就是不稳定的排序方法。【清华大学 1998 一、3 (2分）】 A．起泡排序 B．归并排序 C．Shell排序 D．直接插入排序 E．简单选择排序 8．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（）排序为宜。 A．直接插入 B．直接选择 C．堆 D．快速 E．基数【中科院计算所 2000 一、5（2分）】 9．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。 A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序【中国科技大学 1998 二、4（2分）】【中科院计算所 1998 二、4（2分）】 10．下面的排序算法中，不稳定的是（）【北京工业大学 1999 一、2 (2分)】 A.起泡排序 B.折半插入排序 C.简单选择排序 D.希尔排序 E.基数排序 F.堆排序。 11．下列内部排序算法中：【北京工业大学 2000 一、1 (10分每问2分)】A．快速排序 B.直接插入排序 C. 二路归并排序 D. 简单选择排序 E. 起泡排序F. 堆排序 （1）其比较次数与序列初态无关的算法是（）（2）不稳定的排序算法是（）（3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k<