第九章排序习题_数据结构

习题九排序

一、单项选择题

1．下列内部排序算法中：

A．快速排序 B.直接插入排序

C. 二路归并排序

D. 简单选择排序

E. 起泡排序

F. 堆排序

（1）其比较次数与序列初态无关的算法是（）

（2）不稳定的排序算法是（）

（3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k<

（4）排序的平均时间复杂度为O(n?logn)的算法是（）为O(n?n)的算法是（）2．比较次数与排序的初始状态无关的排序方法是( )。

A．直接插入排序 B．起泡排序 C．快速排序 D．简单选择排序3．对一组数据（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. 插入

4．下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。

A. 选择

B. 冒泡

C. 归并

D. 堆

5．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。

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)

6．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )排序。

A．冒泡 B. 希尔 C. 快速 D. 堆

7. 就平均性能而言，目前最好的内排序方法是( )排序法。

A. 冒泡

B. 希尔插入

C. 交换

D. 快速

8. 下列排序算法中，占用辅助空间最多的是：( )

A. 归并排序

B. 快速排序

C. 希尔排序

D. 堆排序

9. 若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（）次比较。

A. 3

B. 10

C. 15

D. 25

10. 快速排序方法在（）情况下最不利于发挥其长处。

A. 要排序的数据量太大

B. 要排序的数据中含有多个相同值

C. 要排序的数据个数为奇数

D. 要排序的数据已基本有序

11．下列四个序列中，哪一个是堆（）。

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

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

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均不对。

二、填空题

1.若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方法是________的，否则称为________的。

2.按照排序过程涉及的存储设备的不同，排序可分为________排序和________排序。

3．直接插入排序用监视哨的作用是___________________________。

4．对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为_______。

5．下面的c函数实现对链表head进行选择排序的算法,排序完毕,链表中的结点按结点值从小到大链接。请在空框处填上适当内容,每个空框只填一个语句或一个表达式：

#include

typedef struct node {char data; struct node *link; }node;

node *select(node *head)

{node *p,*q,*r,*s;

p=(node *)malloc(sizeof(node));

p->link=head; head=p;

while(p->link!=null)

{q=p->link; r=p;

while ((1)____________)

{ if (q->link->datalink->data) r=q;

q=q->link;

}

if ((2)___________) {s=r->link; r->link=s->link;

s->link= ((3)_________); ((4)_________);}

((5)________) ;

}

p=head; head=head->link; free(p); return(head);

}

6．下面的排序算法的思想是：第一趟比较将最小的元素放在r[1]中，最大的元素放在r[n]中，第二趟比较将次小的放在r[2]中，将次大的放在r[n-1]中，…,依次下去，直到待排序列为递增序。（注：<-->）代表两个变量的数据交换）。

void sort(SqList &r,int n) {

i=1;

while((1)______) {

min=max=1;

for (j=i+1;(2)________ ;++j)

{if((3)________) min=j; else if(r[j].key>r[max].key) max=j; }

if((4)_________) r[min] < ---- >r[j];

if(max!=n-i+1){if ((5)_______) r[min] < ---- > r[n-i+1]; else ((6)______); } i++;

}

}//sort

7．下列算法为奇偶交换排序，思路如下：第一趟对所有奇数的i,将a[i]和a[i+1]进行比较,第二趟对所有偶数的i,将a[i]和a[i+1]进行比较,每次比较时若a[i]>a[i+1],将二者交换;以后重复上述二趟过程,直至整个数组有序。

void oesort (int a[n])

{int flag,i,t;

do {flag=0;

for(i=1;i

if(a[i]>a[i+1])

{flag=(1)______; t=a[i+1]; a[i+1]=a[i]; (2)________;}

for (3)________

if (a[i]>a[i+1])

{flag=(4)________;t=a[i+1]; a[i+1]=a[i]; a[i]=t;}

}while (5)_________;

}

三、应用题

1．对于给定的一组键值：83，40，63，13，84，35，96，57，39，79，61，15，分别画出应用直接插入排序、直接选择排序、快速排序、堆排序、归并排序对上述序列进行排序中各趟的结果。

2．判断下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，请将它们调整为堆）。

（1）100，85，98，77，80，60，82，40，20，10，66

（2）100，98，85，82，80，77，66，60，40，20，10

（3）100，85，40，77，80，60，66，98，82，10，20

（4）10，20，40，60，66，77，80， 82，85，98，100

3．填空并回答相关问题

(1)下面是将任意序列调整为最大堆（MAX HEAP）的算法，请将空白部分填上：

将任意序列调整为最大堆通过不断调用adjust函数，即：FOR（i=n/2；i >0；i- -）adjust（list，i，n）；其中list为待调整序列所在数组（从下标1开始），n为序列元素个数，adjust函数为：

void adjust（int list[]，int root，int n）

/*将以root为下标的对应元素作为待调整堆的根，待调整元素放在list数组中，最大元素下标为n*/

{int child,rootkey;

rootkey=list[root];

child=2*root;

while(child<=n)

{if((child

(1)_______;

if(rootkey>list[child])

break;

else{List[(2) ]=list[child];

child*=2;

}

}

list[child/2]=rootkey;

}

(2)．判断下列序列能否构成最大堆：（12，70，33，65，24，56，48，92，86，33）；

若不能按上述算法将其调整为堆，调整后的结果为：

（）。

四、算法设计题：

1．设计一个用链表表示的直接选择排序算法。

2．冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替进行的冒泡排序算法（即双向冒泡排序法）。

3．输入50个学生的记录（每个学生的记录包括学号和成绩），组成记录数组，然后按成绩由高到低的次序输出（每行10个记录）。排序方法采用选择排序。

4．已知（k1,k2……，k n）是堆，试写一个算法将（k1,k2,……，k n,k n+1）调整为堆。按此思想写一个从空堆开始一个一个填入元素的建堆算法（题示：增加一个k n+1后应从叶子向根的方向调整）。

第九章排序

一、单项选择题

1．（1） DC （2）ADF （3）B （4）ACF BDE

2．D

3．A

4．C

5．C

6．C

7. D

8. A

9. C

10. D

11．C

12. C

二、填空题

1.稳定、不稳定

2.内部、外部

3．免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。

4．n(n-1)/2

5．题中为操作方便，先增加头结点（最后删除），p指向无序区的前一记录，r指向最小值结点的前驱，一趟排序结束，无序区第一个记录与r所指结点的后继交换指针。

(1)q->link!=NULL (2)r!=p (3)p->link (4)p->link=s (5)p=p->link 6．.(1)ir[n-i+1]

7．(1)1 (2)a[i]=t (3)(i=2;i<=n;i+=2) (4)1 (5)flag

三、应用题

1．解答：①直接插入排序

序号 1 2 3 4 5 6 7 8 9 10 11 12

关键字83 40 63 13 84 35 96 57 39 79 61 15

i = 2 40 83 [63 13 84 35 96 57 39 79 61 15]

i = 3 40 63 83 [13 84 35 96 57 39 79 61 15]

i = 4 13 40 63 83 [84 35 96 57 39 79 61 15]

i = 5 13 40 63 83 84 [35 96 57 39 79 61 15]

i = 6 13 35 40 63 83 84 [96 57 39 79 61 15]

i = 7 13 35 40 63 83 84 96 [57 39 79 61 15]

i = 8 13 35 40 57 63 83 84 96 [39 79 61 15]

i = 9 13 35 39 40 57 63 83 84 96 [79 61 15]

i = 10 13 35 39 40 57 63 79 83 84 96 [61 15]

i = 11 13 35 39 40 57 61 63 79 83 84 96 [15]

i = 12 13 15 35 39 40 57 61 63 79 83 84 96

②直接选择排序

序号 1 2 3 4 5 6 7 8 9 10 11 12

关键字83 40 63 13 84 35 96 57 39 79 61 15

i = 1 13 [40 63 83 84 35 96 57 39 79 61 15]

i = 2 13 15 [63 83 84 35 96 57 39 79 61 40]

i = 3 13 15 35 [83 84 63 96 57 39 79 61 40]

i = 4 13 15 35 39 [84 63 96 57 83 79 61 40]

i = 5 13 15 35 39 40 [63 96 57 83 79 61 84]

i = 6 13 15 35 39 40 57 [96 63 83 79 61 84]

i = 7 13 15 35 39 40 57 61 [63 83 79 96 84]

i = 8 13 15 35 39 40 57 61 63 [83 79 96 84]

i = 9 13 15 35 39 40 57 61 63 79 [83 96 84]

i = 10 13 15 35 39 40 57 61 63 79 83 [96 84]

i = 11 13 15 35 39 40 57 61 63 79 83 84 [96]

③快速排序

关键字83 40 63 13 84 35 96 57 39 79 61 15

第一趟排序后 [15 40 63 13 61 35 79 57 39] 83 [96 84]

第二趟排序后 [13] 15 [63 40 61 35 79 57 39] 83 84 [96]

第三趟排序后 13 15 [39 40 61 35 57] 63 [79] 83 84 96

第四趟排序后 13 15 [35] 39 [61 40 57] 63 79 83 84 96

第五趟排序后 13 15 35 39 [57 40] 61 63 79 83 84 96

第六趟排序后 13 15 35 39 40 [57] 61 63 79 83 84 96

第七趟排序后 13 15 35 39 40 57 61 63 79 83 84 96

④堆排序

关键字：83 40 63 13 84 35 96 57 39 79 61 15

排序成功的序列：96 84 83 79 63 61 57 40 39 35 15 13

排序过程如图简答题8－1.1、8－1.2、8－1.3所示。

⑤归并排序

关键字83 40 63 13 84 35 96 57 39 79 61 15

第一趟排序后 [40 83] [13 63] [35 84] [57 96] [39 79] [15 61]

第二趟排序后 [13 40 63 83] [35 57 84 96] [15 39 61 79]

第三趟排序后 [13 35 40 57 63 83 84 96] [15 39 61 79]

第四趟排序后 13 15 35 39 40 57 61 63 79 83 84 96

2．(1)是大堆； (2)是大堆；（4）是小堆；

(3)不是堆，调成大堆 100，98，66，85，80，60，40，77，82，10，20

3．(1)①child=child+1; ②child/2

(2)不能，调为大堆：92,86,56,70,33,33,48,65,12,24

四、算法设计题：

1．解答：分析：每趟从单链表头部开始，顺序查找当前链值最小的结点。找到后，插入

到当前的有序表区的最后。

Void selesort ( lklist L ) /* 设链表L带头结点 */

{ q=L; /* 指向第一数据前趋 */

while ( q-> next !=NULL )

{ pl = q -> next ;

minp =pl; /* minp指向当前已知的最小数 */

while ( pl -> next != NULL )

{ if ( pl -> next -> data < minp -> data )

minp = pl -> next ; /* 找到了更小数 */

pl = pl -> next ; /* 继续往下找 */

}

if ( minp != q -> next) /* 将最小数交换到第一个位置上 */

{ r1 = minp -> next ;

minp -> next = r1 -> next ; /* 删除最小数 */

r2 = q -> next ;

q -> next = r2 -> next ; /* 删除当前表中第一个数 */

r1 -> next = q -> next ;

q -> next = r1 ; /* 将最小数插入到第一个位置上 */

r2 -> next = minp -> next ;

minp -> next = r2 ; /* 将原第一个数放到最小数原位置上*/

}

q = q > next ; /* 选择下一个最小数 */

}

}

2．void BubbleSort2(int a[],int n) //相邻两趟向相反方向起泡的冒泡排序算法{ change=1;low=0;high=n-1; //冒泡的上下界

while(low

{ change=0; //设不发生交换

for(i=low;i

if(a[i]>a[i+1]){a[i]<-->a[i+1];change=1;} //有交换，修改标志change high--; //修改上界

for(i=high;i>low;i--) //从下向上起泡

if(a[i]a[i-1];change=1;}

low++; //修改下界

}//while

}//BubbleSort2

[算法讨论]题目中“向上移”理解为向序列的右端，而“向下移”按向序列的左端来处理。

3．typedef struct

{ int num; float score; }RecType;

void SelectSort(RecType R[51]，int n)

{ for(i=1; i

{ //选择第i大的记录，并交换到位

k=i; //假定第i个元素的关键字最大

for(j=i+1;j<=n;j++) //找最大元素的下标

if(R[j].score>R[k].score) k=j;

if(i!=k) R[i] <-->R[k]; //与第i个记录交换

}//for

for(i=1; i<=n; i++) //输出成绩

{ printf("%d,%f",R[i].num,R[i].score); if(i%10==0) printf("\n");} }//SelectSort

4．解答：分析：此问题分为两个算法，第一个算法 shift 假设 a[ 1] , a[ 2 ],…,a[ k]为堆，增加一个无素a[ k + 1 ],把数组a[ 1 ],a[ 2 ], …,a[ k + 1 ]调整为堆。第二个算法heep 从1开始调用算法sift将整个数组调整为堆。

Void sift (datatype A[ n ] , int K) /* n > = k + 1 */

{ x = A[ K+1] ;

i = K +1 ;

while ( ( i/2 > 0 )&&( A[i/2]>x) ) { A[i]= A[i./2]; i = i/2;} /*从下往上插入位置 */

A[i] = x ;

}

Void heap ( datatype A[ n ] ) ; /* 从1开始调用算法sift ，将整个数组调整为堆 */

{ for ( k = 1 ; k <= n-1; k++ ) sift ( A,k ) ; }

数据结构第六章习题课

1、下图所示的4棵二叉树中，不是完全二叉树的是（） 2、二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法（）。 A 、正确 B 、错误 C 、不一定 3、已知某二叉树的后序遍历序列是dabec ，中序遍历序列是debac ，它的前序遍历序列是（）。 A 、acbed B 、decab C 、deabc D 、cedba 4、如果T2是由有序树T 转换而来的二叉树，那么T 中结点的后序就是T2中结点的（）。 A 、前序 B 、中序 C 、后序 D 、层次序 5、深度为5的二叉树至多有（）个结点。 A 、16 B 、32 C 、31 D 、10 6、在一个非空二叉树的中序遍历序列中，根结点的右边（）。 A 、只有右子树上的所有结点 B 、只有右子树上的部分结点 C 、只有左子树上的部分结点 D 、只有左子树上的所有结点 7、树最适合用来表示（）。 A 、有序数据元素 B 、无序数据元素 C 、元素之间具有分支层次关系的数据 D 、元素之间无联系的数据。 8、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）。 A 、不发生改变 B 、发生改变 C 、不能确定 D 、以上都不对 9、实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用（）存储结构。 A 、二叉链表 B 、广义表存储结构 C 、三叉链表 D 、顺序存储结构 10、对一个满二叉树，m 个树叶，n 个结点，深度为h ，则（）。 A 、n=m+h B 、h+m=2n C 、m=h-1 D 、n=2h -1 11、设n ，m 为二叉树上的两个结点，在中序遍历时，n 在m 前的条件是（）。 A 、n 在m 右方 B 、n 是m 祖先 C 、n 在m 左方 D 、n 是m 子孙 12．已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/- ， A B C D

(完整版)数据结构实验报告全集

数据结构实验报告全集 实验一线性表基本操作和简单程序 1 ．实验目的 （1 ）掌握使用Visual C++ 6.0 上机调试程序的基本方法； （2 ）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2 ．实验要求 （1 ）认真阅读和掌握和本实验相关的教材内容。 （2 ）认真阅读和掌握本章相关内容的程序。 （3 ）上机运行程序。 （4 ）保存和打印出程序的运行结果，并结合程序进行分析。 （5 ）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>// 头文件 #include// 库头文件------ 动态分配内存空间 typedef int elemtype;// 定义数据域的类型 typedef struct linknode// 定义结点类型 { elemtype data;// 定义数据域 struct linknode *next;// 定义结点指针 }nodetype; 2）创建单链表

nodetype *create()// 建立单链表，由用户输入各结点data 域之值， // 以0 表示输入结束 { elemtype d;// 定义数据元素d nodetype *h=NULL,*s,*t;// 定义结点指针 int i=1; cout<<" 建立一个单链表"<> d; if(d==0) break;// 以0 表示输入结束 if(i==1)// 建立第一个结点 { h=(nodetype*)malloc(sizeof(nodetype));// 表示指针h h->data=d;h->next=NULL;t=h;//h 是头指针 } else// 建立其余结点 { s=(nodetype*) malloc(sizeof(nodetype)); s->data=d;s->next=NULL;t->next=s; t=s;//t 始终指向生成的单链表的最后一个节点

数据结构第九章排序习题与答案

习题九排序 一、单项选择题 1．下列内部排序算法中： A．快速排序 B.直接插入排序 C. 二路归并排序 D.简单选择排序 E. 起泡排序 F.堆排序 （1）其比较次数与序列初态无关的算法是（） （2）不稳定的排序算法是（） （3）在初始序列已基本有序（除去n 个元素中的某 k 个元素后即呈有序， k<

《数据结构》知识题汇编09第九章排序试题

数据结构课程（本科）第九章试题 一、单项选择题 1.若待排序对象序列在排序前已按其排序码递增顺序排列，则采用（）方法比较次数最少。 A. 直接插入排序 B. 快速排序 C. 归并排序 D. 直接选择排序 2.如果只想得到1024个元素组成的序列中的前5个最小元素，那么用（）方法最快。 A. 起泡排序 B. 快速排序 C. 直接选择排序 D. 堆排序 3.对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作， 直到子序列为空或只剩一个元素为止。这样的排序方法是（）。 A. 直接选择排序 B. 直接插入排序 C. 快速排序 D. 起泡排序 4.对5个不同的数据元素进行直接插入排序，最多需要进行（）次比较？ A. 8 B. 10 C. 15 D. 25 5.如果输入序列是已经排好顺序的，则下列算法中（）算法最快结束？ A. 起泡排序 B. 直接插入排序

C. 直接选择排序 D. 快速排序 6.如果输入序列是已经排好顺序的，则下列算法中（）算法最慢结束？ A. 起泡排序 B. 直接插入排序 C. 直接选择排序 D. 快速排序 7.下列排序算法中（）算法是不稳定的。 A. 起泡排序 B. 直接插入排序 C. 基数排序 D. 快速排序 8.假设某文件经过内部排序得到100个初始归并段，那么如果要求利用多路平衡归并在3 趟内完成排 序，则应取的归并路数至少是（）。 A. 3 B. 4 C. 5 D. 6 9.采用任何基于排序码比较的算法，对5个互异的整数进行排序，至少需要（）次比较。 A. 5 B. 6 C. 7 D. 8 10.下列算法中（）算法不具有这样的特性：对某些输入序列，可能不需要移动数据对象即可完成 排序。 A. 起泡排序 B. 希尔排序 C. 快速排序 D. 直接选择排序 11.使用递归的归并排序算法时，为了保证排序过程的时间复杂度不超过O(nlog2n)，必须做到（）。

数据结构第十章习题课

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个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确

中南大学数据结构与算法第10章内部排序课后作业答案

第10章内部排序习题练习答案 1.以关键字序列(265，301，751，129，937，863，742，694，076，438)为例，分别写出执行以下排序算法的各趟排序结束时，关键字序列的状态。 (1) 直接插入排序(2)希尔排序(3)冒泡排序(4)快速排序 (5) 直接选择排序(6) 堆排序(7) 归并排序(8)基数排序 上述方法中，哪些是稳定的排序?哪些是非稳定的排序?对不稳定的排序试举出一个不稳定的实例。 答： (1)直接插入排序:(方括号表示无序区) 初始态: 265[301 751 129 937 863 742 694 076 438] 第一趟：265 301[751 129 937 863 742 694 076 438] 第二趟：265 301 751[129 937 863 742 694 076 438] 第三趟：129 265 301 751[937 863 742 694 076 438] 第四趟：129 265 301 751 937[863 742 694 076 438] 第五趟：129 265 301 751 863 937[742 694 076 438] 第六趟：129 265 301 742 751 863 937[694 076 438] 第七趟：129 265 301 694 742 751 863 937[076 438] 第八趟：076 129 265 301 694 742 751 863 937[438] 第九趟：076 129 265 301 438 694 742 751 863 937

(2)希尔排序(增量为5，3，1) 初始态: 265 301 751 129 937 863 742 694 076 438 第一趟：265 301 694 076 438 863 742 751 129 937 第二趟：076 301 129 265 438 694 742 751 863 937 第三趟：076 129 265 301 438 694 742 751 863 937 (3)冒泡排序(方括号为无序区) 初始态[265 301 751 129 937 863 742 694 076 438] 第一趟：076 [265 301 751 129 937 863 742 694 438] 第二趟：076 129 [265 301 751 438 937 863 742 694] 第三趟：076 129 265 [301 438 694 751 937 863 742] 第四趟：076 129 265 301 [438 694 742 751 937 863] 第五趟：076 129 265 301 438 [694 742 751 863 937] 第六趟：076 129 265 301 438 694 742 751 863 937 (4)快速排序：（方括号表示无序区，层表示对应的递归树的层数）

《数据结构》实验报告

《数据结构》实验报告 实验序号：4 实验项目名称：栈的操作

附源程序清单： 1. #include #define MaxSize 100 using namespace std; typedef int ElemType; typedef struct { ElemType data[MaxSize]; int top; }SqStack; void InitStack(SqStack *st) //初始化栈 { st->top=-1; } int StackEmpty(SqStack *st) //判断栈为空{ return (st->top==-1); } bool Push(SqStack *st,ElemType x) //元素进栈{ if(st->top==MaxSize-1)

{ return false; } else { st->top++; //移动栈顶位置 st->data[st->top]=x; //元素进栈 } return true; } bool Pop(SqStack *st,ElemType &e) //出栈 { if(st->top==-1) { return false; } else { e=st->data[st->top]; //元素出栈 st->top--; //移动栈顶位置} return true; } //函数名：Pushs //功能：数组入栈 //参数：st栈名,a->数组名，i->数组个数 bool Pushs(SqStack *st,ElemType *a,int i) { int n=0; for(;n数组名，i->数组个数 bool Pops(SqStack *st,ElemType *a,int i) { int n=0; for(;n

数据结构之排序算法操作论文

排序算法操作 课程名称：数据结构研究 论文题目：排序算法操作 院系： 学生姓名： 学号： 专业班级： 年月日

数据结构之排序算法操作 摘要：本文通过对数据结构中排序算法深入研究,实现了排序算法中的直接插入排序、快速排序和简单选择排序操作，进一步加深了对数据结构中排序算法的理解，得到的算法可以应用到以后的编程实践中。 关键词：排序时间复杂度空间复杂度稳定性 1.引言 排序是日常生活和工作中的一个常见问题，其目的是将一组原本无序的数据元素（或记录）序列，按照人们所需要的顺序，排列成有规律的按关键字有序的序列。 在现实生活中，人们要用到排序。如：学生成绩往往需要按照成绩高低或按学号从前到后排序；在图书馆众多的图书中，需要按照各个学科将书籍归类；排队时从高到低的顺序排队等问题。同样，排序也是计算机程序设计中的一个非常重要的操作，在计算机软件设计中占有极其重要的地位。本文将对排序算法中直接插入排序、快速排序和简单选择排序三种算法的实现做一些研究。 2.算法的实现 直接插入排序算法中，第i趟进行的操作为：在含有i-1个记录的有序子序列r[1…i-1]中插入一个记录r[i]后，变成含有i个记录的有序子序列r[1….i]；并且为了在查找插入位置的过程中避免数组下标出界，在r[0]处设置监视哨，在自i-1起往前搜索的过程中，可以同时后移记录。 算法1 直接插入排序算法 Step1:从第二个记录起逐个进行关键字与前面关键字的比较并判断是否把该记录作为哨兵 for ( i=2; i<=L.length; ++i ) if(LT(L.r[i].key, L.r[i-1].key))

数据结构课后习题答案第九章

第九章查找（参考答案） 9.1 int seqsearch( rectype r[], keytype k) // 监视哨设在n个元素的升序顺序表低下标端，顺序查找关键字为k的数据// 元素。若存在，则返回其在顺序表中的位置，否则，返回0 r[0].key=k; i=n; while (r[i].key>k) i--; if (i>0 && r[i].key==k) return(i); else return(0) } // 算法结束 查找过程的判定树是单支树。 查找成功的平均查找长度为 ASL=∑PICI =1/n*∑i = 1/2*(n+1) 查找不成功的平均查找长度为 ASL=1/(n+1)(∑i+(n+1))=(n+2)/2. 9.2 typedef struct lnode {int freq; // 访问频率域 keytype key; // 关键字 ElemType other; struct lnode *prior,*next; // 双向链表 }seqlist; typedef struct snode {int freq; // 访问频率域 keytype key; // 关键字 ElemType other; }snode; void locate(seqlist L,keytype X) // 在链表中查找给定值为X的结点，并保持访问频繁的结点在前 //调用本函数前，各结点的访问频率域（freq）值均为0。 {seqlist *p; // p是工作指针 p=L->next; // p指向第一元素 while (p!=null && p->key!=X) p=p->next; // 查找X结点 if (p==null) {printf(“no X”); return; } else {q=p->prior; // q是p的前驱 p->next->prior=p->prior; // 先将p结点从链表中摘下 q->next=p->next; while (q!=L && q->freqprior; // 找p结点位置 q->next->prior=p; // 将p结点插入链表 p->next=q->next; p->prior=q; q->next=p; } // 算法结束 void locate(snode L[],int n;keytype X)

数据结构课程实验报告(15)

课程实验报告课程名称：数据结构 专业班级：信安1302 学号： 姓名： 指导教师： 报告日期：2015. 5. 12 计算机科学与技术学院

目录 1 课程实验概述............ 错误!未定义书签。 2 实验一基于顺序结构的线性表实现 2.1 问题描述 ...................................................... 错误!未定义书签。 2.2 系统设计 ...................................................... 错误!未定义书签。 2.3 系统实现 ...................................................... 错误!未定义书签。 2.4 效率分析 ...................................................... 错误!未定义书签。 3 实验二基于链式结构的线性表实现 3.1 问题描述 ...................................................... 错误!未定义书签。 3.2 系统设计 ...................................................... 错误!未定义书签。 3.3 系统实现 ...................................................... 错误!未定义书签。 3.4 效率分析 ...................................................... 错误!未定义书签。 4 实验三基于二叉链表的二叉树实现 4.1 问题描述 ...................................................... 错误!未定义书签。 4.2 系统设计 ...................................................... 错误!未定义书签。 4.3 系统实现 ...................................................... 错误!未定义书签。 4.4 效率分析 ...................................................... 错误!未定义书签。 5 实验总结与评价 ........... 错误!未定义书签。 1 课程实验概述 这门课是为了让学生了解和熟练应用C语言进行编程和对数据结构进一步深入了解的延续。

数据结构实验报告--图实验

图实验 一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template class MGraph { public: MGraph(DataType a[], int n, int e); ~MGraph(){ } void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; int vertexNum, arcNum; }; #endif MGraph.cpp #include using namespace std; #include "MGraph.h" extern int visited[MaxSize]; template MGraph::MGraph(DataType a[], int n, int e)

{ int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0; for(k = 0; k < arcNum; k++) { cout << "Please enter two vertexs number of edge: "; cin >> i >> j; arc[i][j] = 1; arc[j][i] = 1; } } template void MGraph::DFSTraverse(int v) { cout << vertex[v]; visited[v] = 1; for(int j = 0; j < vertexNum; j++) if(arc[v][j] == 1 && visited[j] == 0) DFSTraverse(j); } template void MGraph::BFSTraverse(int v) { int Q[MaxSize]; int front = -1, rear = -1; cout << vertex[v]; visited[v] = 1; Q[++rear] = v; while(front != rear) { v = Q[++front]; for(int j = 0;j < vertexNum; j++) if(arc[v][j] == 1 && visited[j] == 0){ cout << vertex[j]; visited[j] = 1;

数据结构各种排序算法总结

数据结构各种排序算法总结 计算机排序与人进行排序的不同：计算机程序不能象人一样通览所有的数据，只能根据计算机的"比较"原理，在同一时间内对两个队员进行比较，这是算法的一种"短视"。 1. 冒泡排序BubbleSort 最简单的一个 public void bubbleSort() { int out, in; for(out=nElems-1; out>0; out--) // outer loop (backward) for(in=0; in a[in+1] ) // out of order? swap(in, in+1); // swap them } // end bubbleSort() 效率：O(N2) 2. 选择排序selectSort public void selectionSort() { int out, in, min; for(out=0; out

3. 插入排序insertSort 在插入排序中，一组数据在某个时刻实局部有序的，为在冒泡和选择排序中实完全有序的。public void insertionSort() { int in, out; for(out=1; out0 && a[in-1] >= temp) // until one is smaller, { a[in] = a[in-1]; // shift item to right --in; // go left one position } a[in] = temp; // insert marked item } // end for } // end insertionSort() 效率：比冒泡排序快一倍，比选择排序略快，但也是O(N2) 如果数据基本有序，几乎需要O(N)的时间 4. 归并排序mergeSort 利用递归，不断的分割数组，然后归并有序数组 效率为O(N*logN),缺点是需要在存储器中有一个大小等于被排序的数据项数目的数组。public void mergeSort() // called by main() { // provides workspace long[] workSpace = new long[nElems]; recMergeSort(workSpace, 0, nElems-1); } //-----------------------------------------------------------

数据结构实验报告(图)

附录A 实验报告 课程：数据结构（c语言）实验名称：图的建立、基本操作以及遍历系别：数字媒体技术实验日期： 12月13号 12月20号 专业班级：媒体161 组别：无 姓名：学号： 实验报告内容 验证性实验 一、预习准备： 实验目的： 1、熟练掌握图的结构特性，熟悉图的各种存储结构的特点及适用范围； 2、熟练掌握几种常见图的遍历方法及遍历算法； 实验环境：Widows操作系统、VC6.0 实验原理： 1.定义： 基本定义和术语 图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)，其中：V(G)是顶点(V ertex)的非空有限集E(G)是边(Edge)的有限集合，边是顶点的无序对(即：无方向的，（v0,v2）)或有序对（即：有方向的,）。 邻接矩阵——表示顶点间相联关系的矩阵 设G=(V,E) 是有n 1 个顶点的图，G 的邻接矩阵A 是具有以下性质的n 阶方阵特点： 无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2 有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n2 9

无向图中顶点V i的度TD(V i)是邻接矩阵A中第i行元素之和有向图中， 顶点V i的出度是A中第i行元素之和 顶点V i的入度是A中第i列元素之和 邻接表 实现：为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧） 特点: 无向图中顶点Vi的度为第i个单链表中的结点数有向图中 顶点Vi的出度为第i个单链表中的结点个数 顶点Vi的入度为整个单链表中邻接点域值是i的结点个数 逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表。 图的遍历 从图中某个顶点出发访遍图中其余顶点，并且使图中的每个顶点仅被访问一次过程.。遍历图的过程实质上是通过边或弧对每个顶点查找其邻接点的过程，其耗费的时间取决于所采用的存储结构。图的遍历有两条路径：深度优先搜索和广度优先搜索。当用邻接矩阵作图的存储结构时，查找每个顶点的邻接点所需要时间为O（n2），n为图中顶点数；而当以邻接表作图的存储结构时，找邻接点所需时间为O（e），e 为无向图中边的数或有向图中弧的数。 实验内容和要求： 选用任一种图的存储结构，建立如下图所示的带权有向图： 要求：1、建立边的条数为零的图；

数据结构严蔚敏版第十章答案

第十章内部排序 10.23 void Insert_Sort1(SqList &L)//监视哨设在高下标端的插入排序算法 { k=L.length; for(i=k-1;i;--i) //从后向前逐个插入排序 if(L.r[i].key>L.r[i+1].key) { L.r[k+1].key=L.r[i].key; //监视哨 for(j=i+1;L.r[j].key>L.r[i].key;++j) L.r[j-1].key=L.r[j].key; //前移 L.r[j-1].key=L.r[k+1].key; //插入 } }//Insert_Sort1 10.24 void BiInsert_Sort(SqList &L)//二路插入排序的算法 { int d[MAXSIZE]; //辅助存储 x=L.r.key;d=x; first=1;final=1; for(i=2;i<=L.length;i++) { if(L.r[i].key>=x) //插入前部 { for(j=final;d[j]>L.r[i].key;j--) d[j+1]=d[j]; d[j+1]=L.r[i].key; final++; } else //插入后部 { for(j=first;d[j]

数据结构第九章查找练习及答案

一、选择题 1、对线性表进行二分查找时，要求线性表必须（） A、以顺序方式存储 B、以链表方式存储 C、以顺序方式存储，且结点按关键字有序排列 D、以链表方式存储，且结点按关键字有序排列 2、采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（） A、n B、n/2 C、(n+1)/2 D、(n-1)/2 3、采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为（） A、n2 B、nlog2n C、n D、log2n 4、二分查找和二叉排序树的时间性能（） A、相同 B、不相同 C、有时相同 D、有时不相同 5、有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，（）次比较后查找成功。 A、1 B、2 C、4 D、8 6、哈希表长m=14，哈希表函数H（key）=key%11，表中已有4个结点：ADDR（15）=4，ADDR（38）=5；ADDR（61）=6；ADDR（84）=7；其余地址为空，如果用二次探测再散列处理冲突，关键字为49的结点的地址是（） A、8 B、3 C、5 D、9 7、一个长度为12的有序表，按二分查找法对该表进行查找，在表内每个元素等概率情况下查找成功所需的平均比较次数（） A、35/12 B、37/12 C、39/12 D、43/12 8、用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分（）结点最佳。 A、10 B、25 C、6 D、625 9、如果要求一个线性表既能较快的查找，又能适应动态变化的要求，可以采用（）查找方法。 A、分块 B、顺序 C、二分 D、散列 10、有100个元素，用折半查找法进行查找时，最大比较次数是（） A、25 B、50 C、10 D、7 11、有100个元素，用折半查找法进行查找时，最小比较次数是（） A、7 B、4 C、2 D、1 12、散列函数有一个共同性质，即函数值应当以（）取其值域的每个值。 A、同等概率 B、最大概率 C、最小概率 D、平均概率 13、散列地址空间为0到m-1，k为关键字，用p去除k，将所得的余数作为k的散列地址，即H（k）=k%p。为了减少发生冲突的概率，一般取p为（） A、小于m的最大奇数 B、小于m的最大偶数 C、小于m的最大素数 D、小于m的最大合数 14、顺序存储的表格中有90000个元素，按关键字值额定升序排列，假定对每个元素进行查找的概率是相同的，且每个元素的关键字的值皆不相同，用顺序查找法查找时，平均比较次数约为（C），最大比较次数约为（D） A、25000 B、30000 C、45000 D、90000 二、填空题 1、若有一棵二叉排序树，则按照中序遍历顺序将产生一个（有序）序列 2、顺序查找法的平均查找长度为（(N+1)/2）；二分查找法的平均查找长度为（LOG2N）；分

数据结构排序超级总结

数据结构排序超级总结

一、插入排序(Insertion Sort) 1. 基本思想： 每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。 2. 排序过程： 【示例】： [初始关键字] [49] 38 65 97 76 13 27 49 J=2(38) [38 49] 65 97 76 13 27 49 J=3(65) [38 49 65] 97 76 13 27 49 J=4(97) [38 49 65 97] 76 13 27 49 J=5(76) [38 49 65 76 97] 13 27 49 J=6(13) [13 38 49 65 76 97] 27 49 J=7(27) [13 27 38 49 65 76 97] 49 J=8(49) [13 27 38 49 49 65 76 97] 1 2Procedure InsertSort(Var R : FileType); 3//对R[1..N]按递增序进行插入排序, R[0]是监视哨// 4Begin 5for I := 2 To N Do //依次插入

R[2],...,R[n]// 6begin 7R[0] := R; J := I - 1; 8While R[0] < R[J] Do //查找R的插入位置// 9begin 10R[J+1] := R[J]; //将大于R的元素后移// 11J := J - 1 12end 13R[J + 1] := R[0] ; //插入R // 14end 15End; //InsertSort // 复制代码 二、选择排序 1. 基本思想： 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

《数据结构》第九章作业参考答案

第九章查找 9.3 画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。 解：判定树应当描述每次查找的位置： 9.9已知如下所示长度为12的表： （Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec） (1)试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树， 并求其在等概率的情况下查找成功的平均查找长度。 (2)若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成 功的平均查找长度。 (3)按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。解：

9.19解： H(22)=(3×22) mod 11=0 H(41)=(3×41) mod 11=2 H(53)=(3×53) mod 11=5 H(46)=(3×46) mod 11=6 H(30)=(3×30) mod 11=2 冲突d1=(7×30) mod 10+1=1 H1（30）=(2+1)/11=3 H(13)=(3×13) mod 11=6 冲突d1=(7×13) mod 10+1=2 H1（13）=(6+2)/11=8 H(01)=(3×01) mod 11=3冲突d1=(7×1) mod 10+1=8 H1（01）=(3+8)/11=0冲突d2=2*（(7×1) mod 10+1）=16 H2（01）=（3+16）/11=8冲突 d3=3*（(7×1) mod 10+1）=24 H3（01）=（3+24）/11=5冲突 d4=4*（(7×1) mod 10+1）=32 H4（01）=（3+32）/11=2冲突 d5=5*（(7×1) mod 10+1）=40 H5（01）=（3+40）/11=10 H(67)=(3×67) mod 11=3冲突 d1=(7×67) mod 10+1=10 H1（67）=（3+10）/11=2冲突 d2=2*((7×67) mod 10+1)=20 H2（67）=（3+20）/11=1

数据结构实验报告

数据结构实验报告 想必学计算机专业的同学都知道数据结构是一门比较重要的课程，那么，下面是给大家整理收集的数据结构实验报告，供大家阅读参考。 数据结构实验报告1 一、实验目的及要求 1)掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们。 本实验训练的要点是"栈"和"队列"的观点; 二、实验内容 1) 利用栈，实现数制转换。 2) 利用栈，实现任一个表达式中的语法检查(选做)。 3) 编程实现队列在两种存储结构中的基本操作(队列的初始化、判队列空、入队列、出队列); 三、实验流程、操作步骤或核心代码、算法片段 顺序栈： Status InitStack(SqStack ) { S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType)); if(!S.base) return ERROR; S.top=S.base;

S.stacksize=STACK_INIT_SIZE; return OK; } Status DestoryStack(SqStack ) { free(S.base); return OK; } Status ClearStack(SqStack ) { S.top=S.base; return OK; } Status StackEmpty(SqStack S) { if(S.base==S.top) return OK; return ERROR; } int StackLength(SqStack S) { return S.top-S.base;

} Status GetTop(SqStack S,ElemType ) { if(S.top-S.base>=S.stacksize) { S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType)); if(!S.base) return ERROR; S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e; return OK; } Status Push(SqStack ,ElemType e) { if(S.top-S.base>=S.stacksize) { S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType)); if(!S.base) return ERROR;