当前位置:文档之家› 数据结构第十章习题课

数据结构第十章习题课

数据结构第十章习题课
数据结构第十章习题课

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

的是()

A.每次分区后,先处理较短的部分B.每次分区后,先处理较长的部分

C.与算法每次分区后的处理顺序无关D.以上三者都不对

13.在含有n个关键字的小根堆(堆顶元素最小)中,关键字最大的记录有可能存储在()位置上。

A.?n/2?B.?n/2? -1 C.1 D.?n/2? +2

14.对n 个记录的文件进行堆排序,最坏情况下的执行时间是多少?()A.O(log2n)B.O(n)C.O(nlog2n)D.O(n*n)

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

A.堆排序〈快速排序〈归并排序

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

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

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

16.如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列,用()方法最快。

A.起泡排序B.快速排列C.Shell排序D.堆排序E.简单选择排序17.数据序列(8,9,10,4,5,6,20,1,2)只能是下列排序算法中的( )

的两趟排序后的结果。

A.选择排序 B.冒泡排序 C.插入排序 D.堆排序18.分别采用堆排序,快速排序,冒泡排序和归并排序,对初态为有序的表,

则最省时间的是_____算法,最费时间的是______算法。

答:冒泡,快速

19. 设用希尔排序对数组{98,36,-9,0,47,23,1,8,10,7}进行排序,给出的步长(也称增量序列)依次是4,2,1则排序需__________趟,写出第一趟结束后,数组中数据的排列次序__________。

答:3,(10,7,-9,0,47,23,1,8,98,36)

20.堆是一种有用的数据结构。试判断下面的关键码序列中哪一个是堆__________。

①16,72,31,23,94,53 ②94,53,31,72,16,23 ③16,53,23,94,31,72 ④16,31,23,94,53,72 ⑤94,31,53,23,16,72 堆排序是一种_(1)_类型的排序,它的一个基本问题是如何建堆,常用的建堆算法是1964年Floyd提出的_(2)_,对含有n个元素的序列进行排序时,堆排序的时间复杂度是_(3)_,所需要的附加结点是_(4)_。

答:④是堆(1)选择(2)筛选法(3)O(nlog2n) (4)O(1)

21.关键码序列(Q,H,C,Y,Q,A,M,S,R,D,F,X),要按照关键码值递增的次序进行排序,若采用初始步长为4的Shell排序法,则一趟扫描的结果是_____;若采用以第一个元素为分界元素的快速排序法,则扫描一趟的结果是______。

答:(Q,A,C,S,Q,D,F,X,R,H,M,Y),(F,H,C,D,Q,A,M,Q,R,S,Y,X)

22.算法模拟

设待排序的记录共7个,排序码分别为8,3,2,5,9,1,6。

(1) 用直接插入排序。试以排序码序列的变化描述形式说明排序全过程(动态过程)要求按递减顺序排序。

(2) 用直接选择排序。试以排序码序列的变化描述形式说明排序全过程(动态过程)要求按递减顺序排序。

(3) 直接插入排序算法和直接选择排序算法的稳定性如何?

解答:(1)直接插入排序

第一趟(3)[8,3],2,5,9,1,6 第二趟(2)[8,3,2],5,9,1,6

第三趟(5)[8,5,3,2],9,1,6 第四趟(9)[9,8,5,3,2],1,6

第五趟(1)[9,8,5,3,2,1],6 第六趟(6)[9,8,6,5,3,2,1]

(2)直接选择排序(第六趟后仅剩一个元素,是最小的,直接选择排序结束)

第一趟(9)[9],3,2,5,8,1,6 第二趟(8)[9,8],2,5,3,1,6

第三趟(6)[9,8,6],5,3,1,2 第四趟(5)[9,8,6,5],3,1,2

第五趟(3)[9,8,6,5,3],1,2 第六趟(2)[9,8,6,5,3,2],1

(3)直接插入排序是稳定排序,直接选择排序是不稳定排序。

23. 已知某文件的记录关键字集为{50,10,50,40,45,85,80},选择一种从平均性能而言是最佳的排序方法进行排序,且说明其稳定性。

解答:平均性能最佳的排序方法是快速排序,该排序方法不稳定。

初始序列: 50,10,50,40,45,85,80

一趟排序: [45,10,50,40] 50 [85,80]

二趟排序: [40,10] 45 [50] 50 [80] 85

三趟排序: 10,40,45,50,50,80,85

24.对给定文件(28,07,39,10,65,14,61,17,50,21)选择第一个元素28进行划分,写出其快速排序第一遍的排序过程。

解答:

初始序列:[28],07,39,10,65,14,61,17,50,21

21移动:21,07,39,10,65,14,61,17,50,[]

39移动:21,07,[],10,65,14,61,17,50,39

17移动:21,07,17,10,65,14,61,[],50,39

65移动:21,07,17,10,[],14,61,65,50,39

14移动:21,07,17,10,14,[28],61,65,50,39

25.已知一关键码序列为:3,87,12,61,70,97,26,45。试根据堆排序原理,填写下示各步骤完整结果。

建立堆结构:_____________

交换与调整:

(1)87 70 26 61 45 12 3 97;(2)____________________;

(3)61 45 26 3 12 70 87 97;(4)____________________;

(5)26 12 3 45 61 70 87 97;(6)____________________;

(7)3 12 26 45 61 70 87 97;

解答:建立堆结构:97,87,26,61,70,12,3,45 (2)70,61,26,3,45,12,87,97

(4)45,12,26,3,61,70,87,97 (6)12,3,26,45,61,70,87,97

26.已知待排序的序列为(503,87,512,61,908,170,897,275,653,462),试完成下列各题。

(1) 根据以上序列建立一个堆(画出第一步和最后堆的结果图),希望先输出最小值。

(2) 输出最小值后,如何得到次小值。(并画出相应结果图)

(2) 求次小值

27.给出一组关键字T=(12,2,16,30,8,28,4,10,20,6,18),写出用下列算法从小到大排序时第一趟结束时的序列;

(1) 希尔排序(第一趟排序的增量为5)

(2) 快速排序(选第一个记录为枢轴(分隔))

(3) 链式基数排序(基数为10)

解答:(1)一趟希尔排序: 12,2,10,20,6,18,4,16,30,8,28 ( D=5)

(2)一趟快速排序:6,2,10,4,8,12,28,30,20,16,18

(3)链式基数排序LSD [0][1][2][3][4][5][6][7][8][9]

↓ ↓ ↓ ↓ ↓

分配 30 12 4 16 8

↓ ↓ ↓ ↓

10 2 6 28

↓ ↓

20 18

收集:→30→10→20→12→2→4→16→6→8→28→18

28.请写出应填入下列叙述中()内的正确答案。

排序有各种方法,如插入排序、快速排序、堆排序等。

设一数组中原有数据如下:15,13,20,18,12,60。下面是一组由不同排序方法进行一遍排序后的结果。

()排序的结果为:12,13,15,18,20,60

()排序的结果为:13,15,18,12,20,60

()排序的结果为:13,15,20,18,12,60

()排序的结果为:12,13,20,18,15,60

解答:①快速排序②冒泡排序③直接插入排序④堆排序29.写出一趟快速排序算法。

int Partition(RecType R[],int l,int h)

//一趟快速排序算法,枢轴记录到位,并返回其所在位置,

{ int i=l; j=h; R[0] = R[i]; x = R[i].key;

while(i

{ while(i=x) j--;

if (i

while(i

if (i

}//while

R[i]=R[0];

return i;

}//Partition

30.设有一个数组中存放了一个无序的关键序列K1、K2、…、Kn。现要求将Kn放在将元素排序后的正确位置上,试编写实现该功能的算法,要求比较关键字的次数不超过n。(注:用程序实现)

[题目分析]以Kn为枢轴的一趟快速排序。将上题算法改为以最后一个为枢轴先从前向后再从后向前。

int Partition(RecType K[],int l,int n)

{ //交换记录子序列K[l..n]中的记录,使枢轴记录到位,并返回其所在位置,此时,在它之前(后)的记录均不大(小)于它

int i=l; j=n; K[0] = K[j]; x = K[j].key;

while(i

{ while(i

if (i

while(i=x) j--;

if (i

}//while

K[i]=K[0]; return i;

}//Partition

31. 二路插入排序是将待排关键字序列r[1..n]中关键字分二路分别按序插入到

辅助向量d[1..n]前半部和后半部(注:向量d可视为循环表),其原则为,先将r[l]赋给d[1],再从r[2] 记录开始分二路插入。编写实现二路插入排序算法。void BiInsertSort(RecType R[],int n)

{//二路插入排序的算法

int d[n+1]; //辅助存储

d[1]=R[1];first=1;final=1;

for(i=2;i<=n;i++)

{ if(R[i].key>=d[1].key) //插入后部

{ low=1;high=final;

while (low<=high) //折半查找插入位置

{ m=(low+high)/2;

if(R[i].key< d[m].key) high=m-1; else low=m+1;

}//while

for (j=final;j>=high+1;j--) d[j+1] = d[j];//移动元素

d[high+1]=R[i]; final++; //插入有序位置

}

else //插入前部

{ if(first==1){ first=n; d[n]=R[i];}

else{ low=first;high=n;

while (low<=high)

{ m=(low+high)/2;

if(R[i].key< d[m].key) high=m-1; else low=m+1;

}//while

for (j=first;j<=high;j++) d[j-1] = d[j]; //移动元素

d[high]=R[i]; first--;

}//if

}//if

}//for

R[1] =d[fisrt];

for(i=first%n+1,j=2;i!=fisrt;i=i%n+1,j++) R[j] =d[i]; //将序列复制回去

}//BiInsertSort

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

数据结构实验报告全集 实验一线性表基本操作和简单程序 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 始终指向生成的单链表的最后一个节点

数据结构复习题目和答案

《数据结构-C语言版》 第一章绪论 单项选择题 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.在对算法的时间复杂度进行估计的时候,下列最佳的时间复杂度是____ __。 A. n2 B. nlogn C. n D. logn 7.设使用某算法对n个元素进行处理,所需的时间是T(n)=100nlog2n+200n+2000,则该算法的渐近时间复杂度为____ ___。 A. O(1) B. O(n) C. O(200n) D. O(nlog2n)

CDCBBDD 第二章线性表 单项选择题 1.链表不具有的特点是____ ____。 A. 可随机访问任一元素 B. 插入和删除时不需要移动元素 C. 不必事先估计存储空间 D. 所需空间与线性表的长度正比 2.设顺序表的每个元素占8个存储单元。第1个单元的存储地址是100,则第6个元素占用的最后一个存储单元的地址为。 A. 139 B. 140 C. 147 D. 148 3.在线性链表存储结构下,插入操作算法。 A. 需要判断是否表满 B. 需要判断是否表空 C. 不需要判断表满 D. 需要判断是否表空和表满 4.在一个单链表中,若删除p所指结点的后继结点,则执行。 A. p->next = p->next->next; B. p->next = p->next; C. p = p->next->next; D. p = p->next; p->next = p->next->next; 5.将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为。A. O(n) B. O(1) C. O(m) D. O(m+n) 6.需要预分较大空间,插入和删除不需要移动元素的线性表,其存储结构是。 A. 单链表 B. 静态链表 C. 线性链表 D. 顺序存储方式ACCABB 填空题 1.在带表头结点的单链表中,当删除某一指定结点时,必须找到该结点的_____结点。2.在单链表中,指针p所指结点为最后一个结点的条件是。 3.将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数是。4.在一个长度为n的顺序表中第i个元素(1≤i≤n)之前插入一个元素时,需向后移动元素的个数是。 5.在长度为n的顺序表中插入一个元素的时间复杂度为。 1前驱 2 p->next==NULL

经典数据结构面试题(含答案)

栈和队列的共同特点是__________________________ .栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中,增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是 __________________________ 13.树是结点的集合,它的根结点数目是_____________________ 14.在深度为5的满二叉树中,叶子结点的个数为_______________ 15.具有3个结点的二叉树有(_____________________ 16.设一棵二叉树中有3个叶子结点,有8个度为1的结点,则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是 ____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh,中序遍历访问顺序是dgbaechf,则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为:安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中,算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________

数据结构第10章 习题答案

1.下列排序算法中,其中( D )是稳定的。 A. 堆排序,冒泡排序 B. 快速排序,堆排序 C. 直接选择排序,归并排序 D. 归并排序,冒泡排序 2.有一组数据(15,9,7,8,20,-1,7,4)用快速排序的划分方法进行一趟划分后数据的排序为 ( A )(按递增序)。 A.下面的B,C,D都不对。 B.9,7,8,4,-1,7,15,20 C.20,15,8,9,7,-1,4,7 D. 9,4,7,8,7,-1,15,20 3.下列排序算法中,在每一趟都能选出一个元素放到其最终位置上,并且其时间性能受数据初始特性影响的是:( B )。 A. 直接插入排序 B. 快速排序 C. 直接选择排序 D. 堆排序 4.如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列,用( D )方法最快。 A.起泡排序 B.快速排列 C.Shell排序 D.堆排序 E.简单选择排序 5.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较,然后将其放在已排序序列的合适位置,该排序方法称为( A )排序法。 A. 插入 B. 选择 C. 希尔 D. 二路归并 6. 在排序算法中,每次从未排序的记录中挑出最小(或最大)关键码字的记录,加入到已排序记录的末尾,该排序方法是( A )。 A. 选择 B. 冒泡 C. 插入 D. 堆 7. 若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序,需进行( C )次比较。 A. 3 B. 10 C. 15 D. 25 8. 对序列{15,9,7,8,20,-1,4,} 用希尔排序方法排序,经一趟后序列变为{15,-l,4,8,20,9,7}则该次采用的增量是 ( B ) A. l B. 4 C. 3 D. 2 9. 堆排序是( E )类排序 A. 插入 B. 交换 C. 归并 D. 基数 E. 选择 10.排序方法有许多种,(1)法从未排序的序列中依次取出元素,与已排序序列(初始时为空)中的元素作比较,将其放入已排序序列的正确位置上;(2)法从未排序的序列中挑选元素,并将其依次放入已排序序列(初始时为空)的一端;交换排序方法是对序列中的元素进行一系列比较,当被比较的两元素逆序时,进行交换;(3)和(4)是基于这类方法的两种排序方法,而(4)是比(3)效率更高的方法;(5)法是基于选择排序的一种排序方法,是完全二叉树结构的一个重要应用。 (1)--(5): A.选择排序 B.快速排序 C.插入排序 D.起泡排序 E.归并排序 F.shell排序 G.堆排序 H.基数排序 10.1C 5 2A 3D 4B 5G 1.若不考虑基数排序,则在排序过程中,主要进行的两种基本操作是关键字的__ ____和记录的_____。比较,移动 2.分别采用堆排序,快速排序,冒泡排序和归并排序,对初态为有序的表,则最省时间的是_____算法,最费时间的是______算法。冒泡,快速 3. 设用希尔排序对数组{98,36,-9,0,47,23,1,8,10,7}进行排序,给出的步长(也称增量序列)依次是4,2,1则排序需__________趟,写出第一趟结束后,数组中数据的排列次序__________。3,(10,7,-9,0,47,23,1,8,98,36) 4.对给定文件(28,07,39,10,65,14,61,17,50,21)选择第一个元素28进行划分,写出其快速排序第一遍的排序过程。

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

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

练习题 一、单项选择题 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. 下列图示的顺序存储结构表示的二叉树是( )

数据结构习题库汇总

知识点: 01.绪论 02.顺序表 03.链表 04.栈 05.链队列 06.循环队列 07.串 08.数组的顺序表示 09.稀疏矩阵 10.广义表 11.二叉树的基本概念 12.二叉树遍历、二叉树性质 13.树、树与二叉树的转换 14.赫夫曼树 15.图的定义、图的存储 16.图的遍历 17.图的生成树 18.静态查找(顺序表的查找、有序表的查找) 19.动态查找(二叉排序树、平衡树、B树) 20.哈希查找 21.插入排序(直接插入、折半插入、2路插入、希尔排序)22.选择排序(简单选择、树形选择、堆排序) 23.快速排序、归并排序

101A1(1).数据的逻辑结构是(A)。 A.数据的组织形式B.数据的存储形式C.数据的表示形式D.数据的实现形式 101A1(2).组成数据的基本单位是(C)。 A.数据项B.数据类型C.数据元素D.数据变量 101B1(3).与顺序存储结构相比,链式存储结构的存储密度(B)。 A.大B.小C.相同D.以上都不对 101B2(4).对于存储同样一组数据元素而言,(D)。 A.顺序存储结构比链接结构多占空间B.在顺序结构中查找元素的速度比在链接结构中查找要快C.与链接结构相比,顺序结构便于安排数据元素D.顺序结构占用整块空间而链接结构不要求整块空间101B2(5).下面程序的时间复杂度为(B)。 x=0; for(i=1;ii;j++) state; A.n(n+1)/2 B.(n-1)(n+2)/2C.n(n+1)/2 D.(n-1)(n+2) 101D3(8).下面程序的时间复杂度为(A)。 for(i=0;i

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

练习题 一、单项选择题 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 1

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

《数据结构》实验报告

《数据结构》实验报告 实验序号: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.顺序查找法适合于存储结构为()的线性表。 A.散列存储 B. 顺序存储或链式存储 C. 压缩存储 D. 索引存储 2.若查找每个记录的概率均等,则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录,其平均查找长度ASL为( )。 A. (n-1)/2 B. n/2 C. (n+1)/2 D. n 3.适用于折半查找的表的存储方式及元素排列要求为( ) A.链接方式存储,元素无序 B.链接方式存储,元素有序 C.顺序方式存储,元素无序 D.顺序方式存储,元素有序 4.当在一个有序的顺序存储表上查找一个数据时,即可用折半查找,也可用顺序查找,但前者比后者的查找速度( ) A.必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减5.当采用分块查找时,数据的组织方式为 ( ) A.数据分成若干块,每块内数据有序 B.数据分成若干块,每块内数据不必有序,但块间必须有序,每块内最大(或最小)的数据组成索引块 C. 数据分成若干块,每块内数据有序,每块内最大(或最小)的数据组成索引块 D. 数据分成若干块,每块(除最后一块外)中数据个数需相同 6.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法()。 A.正确 B. 错误 7. 二叉查找树的查找效率与二叉树的((1) )有关, 在 ((2) )时其查找效率最低。 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。 8.如果要求一个线性表既能较快的查找,又能适应动态变化的要求,则可采用( )查找法。 A. 分快查找 B. 顺序查找 C. 折半查找 D. 基于属性 9.分别以下列序列构造二叉排序树,与用其它三个序列所构造的结果不同的是( )。 A.(100,80, 90, 60, 120,110,130) B.(100,120,110,130,80, 60, 90) C.(100,60, 80, 90, 120,110,130) D. (100,80, 60, 90, 120,130,110) 10.下图所示的4棵二叉树,( )是平衡二叉树。 (A)(B)(C)(D) 11.散列表的平均查找长度()。 A.与处理冲突方法有关而与表的长度无关 B.与处理冲突方法无关而与表的长度有关 C.与处理冲突方法有关且与表的长度有关 D.与处理冲突方法无关且与表的长度无关 12. 设有一组记录的关键字为{19,14,23,1,68,20,84,27,55,11,10,79},用链地址法构造散列表,散列函数为H(key)=key MOD 13,散列地址为1的链中有()个

数据结构习题

排序算法(19) 1.以单链表为存储结构,写一个直接选择排序算法。 2.设计一算法,使得在尽可能少的时间内重排数组,将所有取负值的关键字放在所有取非负值的关 键字之前。请分析算法的时间复杂度。 3.写一个双向冒泡排序的算法,即在排序过程中交替改变扫描方向。 4. 4.下面是一个自上往下扫描的冒泡排序的伪代码算法,它采用lastExchange 来记录每趟扫描中进 行交换的最后一个元素的位置,并以它作为下一趟排序循环终止的控制值。请仿照它写一个自下往上扫描的冒泡排序算法。 void BubbleSort(int A[],int n) //不妨设A[0..n-1]是整型向量 int lastExchange,j,i=n-1; while (i>0) lastExchange=0; for(j=0;j if([j+1] 交换A[j]和A[j+1]; lastExchange=j; } i=lastExchange;//将i置为最后交换的位置 }//endwhile }//BubbleSort 5.改写快速排序算法,要求采用三者取中的方式选择划分的基准记录;若当前被排序的区间长度小于等于3时,无须划分而是直接采用直接插入方式对其排序。 6.对给定的j(1 ≤ j ≤ n ),要求在无序的记录区R[1..n]中找到按关键字自小到大排在第j个位置上的记录(即在无序集合中找到第j个最小元),试利用快速排序的划分思想编写算法实现上述的查找操作。 7.以单链表为存储结构,写一个直接选择排序算法。 8.写一个heapInsert(R,key)算法,将关键字插入到堆R中去,并保证插入R后仍是堆。提示:应为堆R增加一个长度属性描述(即改写本章定义的SeqList类型描述,使其含有长度域);将key先插入R 中已有元素的尾部(即原堆的长度加1的位置,插入后堆的长度加1),然后从下往上调整,使插入的关键字满足性质。请分析算法的时间。 9.写一个建堆算法:从空堆开始,依次读入元素调用上题中堆其中。 10.写一个堆删除算法:HeapDelete(R,i),将R[i]从堆中删去,并分析算法时间,提示:先将R[i]和堆中最后一个元素交换,并将堆长度减1,然后从位置i开始向下调整,使其满足堆性质。

经典数据结构上机题_答案解析

数据结构上机实验题目 实验一线性表的顺序存储结构 实验学时 2学时 背景知识:顺序表的插入、删除及应用。 目的要求: 1.掌握顺序存储结构的特点。 2.掌握顺序存储结构的常见算法。 实验容 1.输入一组整型元素序列,建立顺序表。 2.实现该顺序表的遍历。 3.在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。4.判断该顺序表中元素是否对称,对称返回1,否则返回0。 5.实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。 6.输入整型元素序列利用有序表插入算法建立一个有序表。 7.利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。 8. 利用该顺序结构实现循环队列的入队、出队操作。 8.编写一个主函数,调试上述算法。 #include #include

#define OVERFLOW 0 #define MAXSIZE 100 typedef int ElemType; typedef struct list {ElemType elem[MAXSIZE]; int length; }Sqlist; void Creatlist(Sqlist &L) {int i; printf("请输入顺序表的长度:"); //输入一组整型元素序列,建立一个顺序表。 scanf("%d",&L.length); for(i=0;i

数据结构课程实验报告(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.下列排序算法中,其中()是稳定的。 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个记录的线性表进行快速排序为减少算法的递归深度,以下叙述正确

数据结构1-4章习题答案

第一章绪论 一、选择题 1.D 2.C 3.C 4.B 5.D 6.C 7.D 8.C 9.A 10.D 11.D 12.B 二、填空题 1. 逻辑结构存储结构运算 2. 集合结构线性结构树形结构图状结构 3. 有穷性. 确定性. 可行性. 输入. 输出 4. 顺序存储. 链式存储 5. 数据元素 6. 线性结构非线性结构 三、简答题 1. 尽管算法的含义与程序非常相似,但两者还是有区别的。首先,一个程序不一定满 有穷性,因为它不是一个算法。其次,程序中的指令必须是计算机可以执行的,而 算法中的指令却无此限制。如果一个算法采用机器可执行的语言来书写,那么它就 是一个程序。 2. 数据结构是指数据对象以及该数据对象集合中的数据元素之间的相互关系(数据元 素的组织形式)。例如:队列的逻辑结构是线性表(先进后出);队列在计算机中 既可以采用顺序存储也可以采用链式存储;队列可进行删除数据元素. 插入数据元 素. 判断是否为空队列,以及队列置空等操作。 3. 数据元素之间的逻辑关系,也称为数据的逻辑结构。数据元素以及它们之间的相互 关系在计算机存储器内的表示(又称映像)称为数据的存储结构,也称数据的物理 结构。 4. 算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表 示一个或者多个操作。此外,一个算法还具有下列5个特性: (1)有穷性:一个算法必须在执行有穷步之后结束,即算法必须在有限时间内完 成。 (2)确定性:算法中每一步必须有明确的含义,不会产生二义性。并且,在任何 条件下,算法只有唯一的一条执行路径,即对于相同的输入只能得出相同的输出。 (3)可行性:一个算法是能执行的,即算法中的每一步都可以通过已经实现的基 本运算执行有限次得以实现。 (4)输入:一个算法有零个或者多个输入,它们是算法开始时对算法给出的初始 量。 (5)输出:一个算法有一个或者多个输出,它们是与输入有特定关系的量 5. 举例说明四种基本结构的区别: 集合: 数据元素之间无任何关系,如集合A={x,5,t,&}; 线性结构: 数据元素之间存在一个对一个的关系,如线性表L=(2,3,4,5,7,10); 树形结构: 数据元素之间存在一个对多个的关系,如文件系统目录管理; 图状结构: 数据元素之间存在多个对多个的关系,如教学计划课程安排顺序图。 四. 算法设计题

数据结构经典题目c语言代码

《数据结构》课程设计题目 (程序实现采用C语言) 题目1:猴子选王(学时:3) 一堆猴子都有编号,编号是1,2,3 ...m,这群猴子(m个)按照1-m的顺序围坐一圈,从第1开始数,每数到第n个,该猴子就要离开此圈,这样依次下来,直到圈中只剩下最后一只猴子,则该猴子为大王。 要求:m及n要求从键盘输入,存储方式采用向量及链表两种方式实现该问题求解。 //链表 #include #include // 链表节点 typedef struct _RingNode { int pos; struct _RingNode *next; }RingNode, *RingNodePtr; // 创建约瑟夫环,pHead:链表头指针,count:链表元素个数 void CreateRing(RingNodePtr pHead, int count) { RingNodePtr pCurr = NULL, pPrev = NULL; int i = 1; pPrev = pHead; while(--count > 0)

{ pCurr = (RingNodePtr)malloc(sizeof(RingNode)); i++; pCurr->pos = i; pPrev->next = pCurr; pPrev = pCurr; } pCurr->next = pHead; // 构成环状链表 } void KickFromRing(RingNodePtr pHead, int n) { RingNodePtr pCurr, pPrev; int i = 1; // 计数 pCurr = pPrev = pHead; while(pCurr != NULL) { if (i == n) { // 踢出环 printf("\n%d", pCurr->pos); // 显示出圈循序 pPrev->next = pCurr->next; free(pCurr); pCurr = pPrev->next; i = 1; } pPrev = pCurr;

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

图实验 一,邻接矩阵的实现 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;

数据结构Ch10习题答案

第十章内部排序 一、择题 1.用直接插入排序法对下面四个表进行(由小到大)排序,比较次数最少的是(B)。A.(94,32,40,90,80,46,21,69) 插32,比2次 插40,比2次 插90,比2次 插80,比3次 插46,比4次 插21,比7次 插69,比4次 B.(21,32,46,40,80,69,90,94) 插32,比1次 插46,比1次 插40,比2次 插80,比1次 插69,比2次 插90,比1次 插94,比1次 C.(32,40,21,46,69,94,90,80) 插40,比1次 插21,比3次 插46,比1次 插69,比1次 插94,比1次 插90,比2次 插80,比3次 D.(90,69,80,46,21,32,94,40) 插69,比2次 插80,比2次 插46,比4次 插21,比5次 插32,比5次 插94,比1次 插40,比6次 2.下列排序方法中,哪一个是稳定的排序方法(BD)。 A.希尔排序 B.直接选择排序 C.堆排序 D.冒泡排序 下列3题基于如下代码: for(i=2;i<=n;i++) { x=A[i]; j=i-1; while(j>0&&A[j]>x) { A[j+1]=A[j]; j--; } A[j+1]=x

} 3.这一段代码所描述的排序方法称作(A)。 A.插入排序 B.冒泡排序 C.选择排序 D.快速排序 4.这一段代码所描述的排序方法的平均执行时间为(D) A.O(log2n) B.O(n) C. O(nlog2n) D.O(n2) 5.假设这段代码开始执行时,数组A中的元素已经按值的递增次序排好了序,则这段代码的执行时间为(B)。 A.O(log2n) B.O(n) C.O(nlog2n) D.O(n2) 6.在快速排序过程中,每次被划分的表(或了表)分成左、右两个子表,考虑这两个子表,下列结论一定正确是(B)。A.左、右两个子表都已各自排好序 B.左边子表中的元素都不大于右边子表中的元素 C.左边子表的长度小于右边子表的长度 D.左、右两个子表中元素的平均值相等 7.对n个记录进行堆排序,最坏情况下的执行时间为(C)。 A.O(log2n) B.O(n) C.O(nlog2n) D.O(n2) 8、设待排序关键码序列为(25、18、9、33、67、82、53、95、12、70),要按关键码值递增的顺序排序,采取以第一个关键码为分界元素的快速排序法,第一趟排序完成后关键码表33被放到了第几个位置(D)。 A.3 B.5 C.7 D.9 9.若对一个已经排好了序的序列进行排序,在下列四方法中,哪种方法比较好(C)。 A.冒泡排序法 B.直接选择排序法 C.直接插入排序法 D.堆排序法 10.快速排序的时间复杂度是(A) A.O(nlog2n) B.O(n2) C. O(n3) D.O(log2n) 11.以下关键字序列用快速排序法进行排序,速度最慢的是(C) A.{23,27,7,19,11,25,32} B.{23,11,19,32,27,35,7}

数据结构习题2011级

1.数据的四种存储结构是( ) A.顺序存储结构、链接存储结构、索引存储结构和散列存储结构 B.线性存储结构、非线性存储结构、树型存储结构和图型存储结构 C.集合存储结构、一对一存储结构、一对多存储结构和多对多存储结构 D.顺序存储结构、树型存储结构、图型存储结构和散列存储结构 2.若对某线性表最常用的操作是在最后一个结点之后插入一个新结点或删除最后一个结点,要使操作时间最少, 下列选项中,应选择的存储结构是( ) A.无头结点的单向链表 B.带头结点的单向链表 C.带头结点的双循环链表 D.带头结点的单循环链表 3.若带头结点的单链表的头指针为head,则判断链表是否为空的条件是( ) A.head=NULL B.head->next=NULL C.head!=NULL D.head->next!=head 7.若一棵二叉树的前序遍历序列与后序遍历序列相同,则该二叉树可能的形状是( ) A.树中没有度为2的结点 B.树中只有一个根结点 C.树中非叶结点均只有左子树 D.树中非叶结点均只有右子树 8.若根结点的层数为1,则具有n个结点的二叉树的最大高度是( ) A.n B. C. +1 D.n/2 9.在图G中求最小生成树可以采用的算法是( ) A.迪杰斯特拉(Dijkstra)算法 B.克鲁斯卡尔(Kruskal)算法 C.深度优先遍历(DFS)算法 D.广度优先遍历(BFS)算法 10.下图G=(V,E)是一个带权连通图,G的最小生成树的权为( ) A.15 B.16 C.17 D.18 11.在下图中,从顶点1出发进行深度优先遍历可得到的序列是( ) A.1 2 3 4 5 6 7 B.1 4 2 6 3 7 5 C.1 4 2 5 3 6 7 D.1 2 4 6 5 3 7 12.如果在排序过程中不改变关键字相同元素的相对位置,则认为该排序方法是( ) A.不稳定的 B.稳定的 C.基于交换的 D.基于选择的 13.设有一组关键字(19, 14, 23, 1,6,20, 4,27, 5,11, 10, 9),用散列函数H(key)=key%13构造散列表,用拉链法解 决冲突,散列地址为1的链中记录个数为( ) A.1 B.2 C.3 D.4 14.已知二叉树结点关键字类型为字符,下列二叉树中符合二叉排序树性质的是( )

相关主题
文本预览
相关文档 最新文档