数据结构（Data Structure）（C/C++）PTA习题+课后习题

课本：《数据结构——从概念到c++实现（第三版）》

第一章 绪论

1.1 判断题

1-1数据元素是数据的最小单位。

F

课本：数据元素是数据的基本单位；构成数据元素的最小单位称为数据项，数据元素是讨论数据结构时涉及的最小数据单位，数据结构是指相互之间存在一定关系的数据元素的集合，数据是能输入到计算机中并能被计算机程序识别和处理的符号。（第9页）

1-2数据的逻辑结构是指数据的各数据项之间的逻辑关系。

F

课本：数据的逻辑结构（logical structure）是指数据元素以及数据元素之间的逻辑关系，是从实际问题抽象出的数据模型，在形式上可以定义为一个二元组：Data_Structure=(D,R)。其中，D是数据元素的有限集合，R是D上关系的集合，实质上，这个形式定义是数据模型的一种数学描述。（第9、10页）

1-3数据结构概念包括数据之间的逻辑结构、数据在计算机中的存储方式和数据的运算三个方面。

T

课本：①数据的逻辑结构：包括表、树、图等数据结构，其核心是如何组织待处理的数据以及数据之间的逻辑关系；②数据的存储结构：如何将表、树、图等数据结构存储到计算机的存储器中，其核心是如何有效地存储数据以及数据之间的逻辑关系；③算法：如何基于数据的某种存储结构实现插入、删除、查找等基本操作，其核心是如何有效地处理数据；④常用的数据处理技术：包括查找技术和排序技术等。（第9页）

1-4数据结构的抽象操作的定义与具体实现有关。

F

抽象操作是外部怎样使用该数据结构；具体实现是内部的事情，外部不需要关心。先设计抽象操作，再完成具体实现。同一种抽象操作可以有多种具体实现。对于同一种抽象操作，可能某一种具体实现简单而另一种具体实现复杂。

数据结构作业1复习__KEVEON的博客-CSDN博客_抽象数据类型中基本操作的定义与具体实现有关

1-5算法和程序没有区别，在数据结构中二者是通用的。

F

课本：算法是对特定问题求解步骤的一种描述，是指令的有限序列，算法还必须满足以下基本特性：

①有穷性：一个算法必须总是（对任何合法的输入）在执行有穷步之后结束，且每一步都在有穷时间内完成②确定性：算法中的每一条指令必须有确切的含义，不存在二义性，并且，在任何条件下，对于相同的输入只能得到相同的输出③可行性：描述算法的每一条指令都可以转换成某种程序设计语言对应的语句，并在计算机上可以执行④有输入⑤有输出（第13页）

通常来说，算法有零个或多个输入（即算法可以没有输入），这些输入通常取自于某个特定的对象集合，但是算法必须要有输出，而且输出与输入之间有着某种特定的关系。（第13页）

算法和程序不同。程序是对一个算法使用某种程序设计语言的具体实现，原则上，算法可以用任何一种程序设计语言实现。算法的有穷性意味着并不是所有计算机程序都是算法。（第13、14页）

1-6数据结构包括数据对象集以及它们的逻辑结构和物理结构，还包括与数据对象相关联的操作集，以及实现这些操作的高效的算法。

T

1-7基于某种逻辑结构之上的基本操作，其实现是唯一的。

F

（第11页）

数据的逻辑结构是从具体问题抽象出来的逻辑模型，是面向问题的，反映了数据元素之间的的关联方式或邻接关系；数据的存储结构是面向计算机的，其基本目标是将数据元素及其逻辑关系存储到计算机的内存中去。数据的逻辑结构和存储结构是密切相关的两个方面。一般来说，一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储结构，其数据处理的效率往往是不同的。（第11页）

1-8所谓数据的逻辑结构指的是数据之间的逻辑关系。

F

课本：①数据的逻辑结构：包括表、树、图等数据结构，其核心是如何组织待处理的数据以及数据之间的逻辑关系…（第9页）

1.2 单选题

2-1在 Data_Structure = (D，R)中，D 是（ ）的有限集合。

A.数据元素

课本：数据的逻辑结构,…,在形式上可以定义为一个二元组，其中D是对数据元素的有限集合，R是对D上关系的集合。实质上，这个形式定义是对数据模型的一种数学描述。（第10页）

2-2以下关于数据结构的说法中错误的是（ ）。

A.数据结构相同，对应的存储结构也相同

数据结构通常指的是逻辑结构，同一逻辑结构可对应不同的存储结构。如字典，可用顺序表、链表、散列表、索引表来实现，数据结构的操作在不同存储下有不同的实现

百度教育 (baidu.com)

课本：一般来说，一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储结构，其数据处理的效率往往是不同的。（第11页）

2-3 可以用（ ）定义一个完整的数据结构。

D.抽象数据类型

抽象数据类型描述了数据的逻辑结构和抽象运算

数据结构绪论_一只少年~的博客-CSDN博客_数据的逻辑结构唯一决定其存储结构

课本：抽象数据类型(abstract data type,ADT)是一个数据模型以及定义在该模型上的一组操作的总称，ADT可理解为对数据类型的进一步抽象，数据类型和ADT的区别仅在于：数据类型指的是高级程序设计语言支持的基本数据类型，而ADT指的是用户自定义的数据类型。事实上，抽象数据类型理论催生了面向对象程序设计语言的诞生和发展，此类语言的最大特点是能够实现封装。（第12页）

2-4算法分析的目的是( )

C.分析算法的效率以求改进

2-5算法分析的两个主要方面是( )

A.空间复杂度和时间复杂度

课本：为了客观地反映一个算法的执行时间，可以用算法中基本语句的执行次数来度量算法的工作量。基本语句是执行次数与整个算法的执行次数成正比的语句，基本语句对算法运行时间的贡献最大，是算法中最重要的操作。这种衡量效率的方法得出的不是时间量，而是一种增长趋势的度量。换言之，只考虑当问题规模充分大时，算法中基本语句的执行次数在渐近意义下的阶，称作算法的渐进时间复杂度，简称时间复杂度(time complexity)，通常用大O记号表示。（第16、17页）

课本：算法在执行过程中所需的存储空间包括：①输入/输出数据占用的空间；②算法本身占用的空间；③执行算法需要的辅助空间。其中，输入/输出数据占用的空间取决于问题，与算法无关；算法本身占用的空间虽然与算法相关，但一般其大小是固定的。所以，算法的空间复杂度(space complexity)是指算法在执行过程中需要的辅助空间的数量，也就是除算法本身和输入输出数据所占用的空间外，算法临时开辟的存储空间。（第18页）

2-6采用链结构存储线性表时，其地址（ ）。

B.连续不连续都可以

2-7一个正确的算法应该具有 5 个特性，除输入、输出特性外，另外 3 个特性是（ ）。

A.确定性、可行性、有穷性

2-8算法的时间复杂度取决于（ ）

C.问题的规模和待处理数据的初态

2-9以下数据结构中，哪一个是线性结构（ ）

D.串

数组和广义表不是线性结构，它们是线性结构的推广。

https://blog.csdn.net/vision_noisiv/article/details/118692436

2-10 以下数据结构中，（ ）是非线性数据结构

A.树

2-11 算法的时间复杂度与（ ）有关。

A.问题规模

2-12 以下程序段的空间复杂度为

int a = 1, b = 1, i;for (i=0; i<=10; i++) {b += a;a = b - a;}

B.O(1)

单选题：以下程序段的空间复杂度为( )。 – 题库 – 雨中笔记 (hyluz.cn)

2-13下列程序段的时间复杂度是（ ）。

count=0;for(k=1;k<=n;k*=2) for(j=1;j<=n;j++) count++;

C.O(nlog2n)

注意k*=2，假设第二条语句运行次数为x，2的x次方=n推出x=log2​n

第一个语句执行1次；第二个语句执行2^x=n -> x=log2n次；第三个语句执行n次

1 *log2n * n

https://blog.csdn.net/yiqixuehaoma/article/details/126580677

2-14下面说法中，错误的是（ ）。

ⅰ.算法原地工作的含义是指不需要任何额外的辅助空间

ⅱ.在相同规模n下，复杂度为O(n)的算法在时间上总是优于复杂度为O(2n)的算法

ⅲ.所谓时间复杂度，是指最坏情况下估算算法执行时间的一个上界

ⅳ.同一个算法，实现语言的级别越高，执行效率越低

A.ⅰ

ⅲ是对的，算法原地工作是指辅助空间不随数据规模的扩大而扩大

https://blog.csdn.net/weixin_45729807/article/details/114580076

课本：如果算法所需的辅助空间相对于问题规模来说只是一个常数，称此算法为原地（或就地）工作，否则，这个辅助空间数量也应该是问题规模的函数，通常记作：S(n)=O(f(n));其中，n为问题规模，分析方法与算法的时间复杂度类似。第18页）

2-15算法的计算量的大小称为算法的____。

B.复杂度

2-16在下面的程序段中，对x的赋值语句的频度为（ ）

for (i=1;i<=n;i++)for (j=1;j<=n;j++)x=x+1;

C.O(n^2)

1.3 填空题

1.3.1 算法效率的比较

假设为解决某问题而设计的若干算法的时间复杂度分别为：

A)O(n)
B)O()
C)O()
D)O()
E)O()
F)O()
G)O(n!)
H)O(1)
I)O()
J)O()

这些算法按效率由高到低的顺序是 ____（注：请填大写字母。）

答案：HCFADIBEGJ

5道计算时间复杂度的题_yiqixuehaoma的博客-CSDN博客

算法复杂度详解（O(1)，O(n)，O（logn）等）_V5放纵丶的博客-CSDN博客_算法复杂度o(1)

1.3.2 基本术语

____是客观事物的符号表示，是所有能输入到计算机中并被计算机程序处理的符号的总称。

答案：数据

1.3.3数据结构的数学定义

数据结构的数学定义为一个二元组：

DS=(D,R)

其中：DS是数据结构，D是____的有限集，R是D上的____的有限集。

答案：数据元素，关系

Data_Structure

1.3.4关于存储结构

存储结构包括____的表示和____的表示。

答案：数据元素，数据元素间关系

1.3.5基本术语

____一般指由用户定义的、表示应用问题的数学模型，以及定义在该模型上的一组操作的总称。

答案：抽象数据类型

1.3.6

在数据结构中，数据的逻辑结构分为____和____。

答案：线性结构，非线性结构

1.3.7

数据结构由数据的____、____和____三部分组成。

答案：逻辑结构，存储结构，算法

1.3.8算法的特性

一个算法必须满足以下几个重要特性：

1. ____: 一个算法必须总是在执行有限步后结束。

2. ____: 一个算法中每一条指令必须有确切的含义。

3. ____: 算法中的所有操作都可通过已实现的基本操作来完成。

4. ____: 一个算法有零个或多个输入。

5. ____: 一个算法有一个或多个输出。

请填：输入、输出、确定性、可行性、有穷性。

答案：E，C，D，A，B

1.3.9基本术语

____是数据的基本单位，____是数据的不可分割最小单位。其中：前者在计算机中通常作为一个整体进行考虑和处理，它可以由一个或多个后者组成。

答案：数据元素，数据项

1.3.10基本术语(实例)

观察下面的表格：

整张表格称为一个____，其中每一行称为一个____，任意一行中的每一个栏目称为一个____。

请填：数据、数据元素、数据项、数据对象。

答案：A,B,C

1.3.11沃斯的名言

瑞士科学家尼古拉斯·沃斯(Niklaus Wirth)有一句在计算机领域里人尽皆知的名言：

____ + ____ = 程序

答案：算法，程序

Algorithm+Data Structures=Programs

1.4 编程题

1.4.1求最小值和次小值

本题目要求读入n个整数，要求用最少的比较次数，输出它们的最小值和次小值。例如，对于12 13 1 10 34 1这6个数，最小值为1，次小值

为10。

输入格式:

输入有两行。第一行为整数个数n（≤1 000 000），第二行给出n个以空格分隔的整数。

输出格式:

对每一组输入，在一行中输出最小值和次小值，中间以一个空格分隔，但行尾没有多余空格。如果输入数据不足两个，则输出“Invalid Input”。如果没有次小值，则输出“There is no second smallest element”。

输入样例:

6
12 13 1 10 34 1

输出样例:

1 10

代码长度限制：16 KB

时间限制：200 ms

内存限制：64 MB

#include#includeusing namespace std;int main(){int n;cin>>n;if(n<=1) {cout<<"Invalid Input";return 0;}int str[n];for(int i = 0; i >str[i];} //for(int i = 0; i < n; i++)//{//cout<<str[i];//}int cmin = str[0]; int min = str[1]; for(int i = 0; i < n; i++) { if(str[i] < min) { min = str[i]; }} for(int i = 0; i  min && str[i] < cmin ) { cmin = str[i]; } } if(min == cmin) cout<<"There is no second smallest element";else{ cout<<min<<" "<<cmin<<endl; }return 0;}

1.4.2 求素数个数

求素数的个数。本题要求编写一个程序，求1~n的素数个数。 要求至少给出两种解法，对于相同的n，给出这两种解法的结果，通过相关数据进行测试，目的是通过对比同一问题不同解法的绝对执行时间体会如何设计“好”的算法。

输入格式:

输入在一行中给出1个整数n(<= 10 000 000)。

输出格式:

对每一组输入，在一行中输出1~n的素数个数。

输入样例1：5，输出样例1：3；

输入样例2：14，输出样例2：6；

代码长度限制：16 KB

时间限制：200 ms

内存限制：64 MB

THE FIRST

#includeusing namespace std;int main(){int n,count = 0;cin>>n;for(int i=2; i<=n; i++){int j = 2;while(j=i)count++;}cout<<count<<endl;return 0;}

THE SECOND

#include#includeusing namespace std;int main(){int n, count = 0;cin>>n;for(int i=2; i<=n; i++){int j = 2;float a = sqrt(i);while(ja)count++;}cout<<count<<endl;return 0;}

THE THIRDPTA 求素数个数 (30分) C++实现_lalula1999的博客-CSDN博客_c++素数个数

#includechar arr[10000001];int main(){int n,sum=0;int i,j;scanf("%d",&n);for(i=0;i<=n;i++){arr[i]='0';}for(i=2;i*i<=n;i++){for(j=i;i*j<=n;j++)//①{if(arr[i]=='0'){arr[j*i]='1';}}}for(i=2;i<=n;i++){if(arr[i]=='0'){sum++;}}printf("%d",sum);return 0;}

此处可以将①那一行的j=2，改成了j=i，更节省时间，随机取了几个样例，没有发现错误。

1.5 课后练习题

1.5.1 选择题

1、顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中数据元素之间的逻辑关系是由（）表示的。

存储位置、指针

课本：数据的存储结构（storage structure）又称为物理结构，是数据及其逻辑结构在计算机中的表示（也称映射）。需要强调的是，存储结构除了存储数据元素之外，必须隐式或显式地存储数据元素之间的逻辑关系。通常有两种存储结构：顺序存储结构和连接存储结构。顺序存储结构的基本思想是用一组连续的存储单元存储数据元素，数据元素之间的逻辑关系用元素之间的存储位置来表示。链接存储结构的基本思想是：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示。（第10页）

2、假如有如下遗产继承规则：丈夫和妻子可以相互继承遗产，子女可以继承父亲或母亲的遗产；子女之间不能相互继承。则表示该遗产继承关系的数据结构应该是（）

图

3、计算机所处理的数据一般具有某种内在联系，这是指：（）

A、数据和数据间之间存在某种关系

B、元素和元素之间存在某种关系

C、元素内部具有某种结构

D、数据项和数据项之间存在某种关系

4、对数据结构的描述，错误的是：（）

A、相同的逻辑结构对应的存储结构也必相同

B、数据结构由逻辑结构、存储结构和基本操作三方面组成

C、对数据结构基本操作的实现与存储结构有关

D、数据的存储结构是数据的逻辑结构的机内实现

课本：数据的存储结构（storage structure）又称为物理结构，是数据及其逻辑结构在计算机中的表示（也称映像）。需要强调的是，存储结构除了存储数据元素之外，必须隐式或显示的存储数据元素之间的逻辑关系。通常有两种存储结构：顺序存储结构和链接存储结构，顺序存储结构的基本思想是用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。链接存储结构的基本思想是用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示。（第10页）

5、算法指的是：（）

对特定问题求解步骤的一种描述，是指令的有限序列

6、算法的特性：（）

有穷性、确定性、可行性、有输入、有输出

7、算法分析的目的是( )，算法分析的两个主要方面是( )

分析算法的效率以求改进；空间复杂度和时间复杂度（空间性能和时间性能）

8、假设时间复杂度为O(n*n)的算法在有200个元素的数组上运行需要3.1ms，则在有400个元素的数组上运行需要（）ms

12.4

3.1ms*（400/200）*（400/200）

9、下列程序段加下划线的语句需要执行（）次

for( m = 0, i = 1; i <=n; i++)

for( j = 1; j <= 2 * i; j++)

m = m+1;

n(n+1)

第一条语句执行n次，第二条语句执行2*（n * (n + 1) / 2）,每次循环，第二条语句的执行次数受第一条语句影响。

1.5.2 分析一下各程序段，并用大O记号表示其执行时间

1、

i = 1; k = 0;while(i <= n){k = k + 10 * i;i++;}

O(n)

2、

i = 1; k = 0;do{k = k + 10 * i;i++;} while(i <= n)

O(n)

3、

i = 1; j = 0;while(i + j  j) j++;else i++;}

O(n)

4、

y = 0;while( (y+1) * (y+1) <=n)y = y + 1;

O(n^(1/2))

5、

#includeusing namespace std;int main(){int x = 0, n = 0;cin>>n;for( int i = 1; i <= n; i++)for( int j = 1; j <= i; j++)for(int k = 1; k <= j; k++)x++; } 

时间复杂度为O(N的立方)

结果为N(N+1)(N+2)/6，

x=0;y=0; for (int i=1;i<=n;i++) for (int j=1;j<=i;j++){ for (int k=1;k<=j;k++) x=x+y;_百度知道 (baidu.com)

6、

for(i = 1; i <= n; i++)for(j = 2 * i; j <= n; j++)y += i * j; 

O(n*n)

1.5.3 解答下列问题

1、假设有数据结构（D,R)，其中D={1,2,3,4,5,6},R={（1，2），（1，4），（2，3），（2，4），（3，4），（3，5），（3，6），（4，5），（4，6）}。请画出其中逻辑结构图并指出属于何种结构。

答：属于图，

1.5.4 算法设计（要求：分别用伪代码和c++语言描述算法，并分析时间复杂度）

第二章 线性表

1、判断题

1-1顺序存储方式只能用于存储线性结构。

F

线性结构、树形结构、图状结构都可用顺序存储方式

1-2在顺序表中取出第i个元素所花费的时间与i成正比。

F

课本：顺序表中第i个元素存储在数组下标为i-1的位置，所以，按位查找算法的时间复杂度为O(1)，（课本第34页）按位查找的成员函数定义如下：

template T SeqList::Get(int i){if(i  length) throw"查找位置非法";else return data[i-1];}

1-3线性表的顺序存储表示优于链式存储表示。

F

课本：1、时间性能比较：

所谓时间性能是指基于某种存储结构的基本操作（及算法）的时间复杂度。

像取出线性表中第i个元素这样的按位置随机访问的操作，使用顺序表更快一些，时间性能为O(1)；相比之下，链表中按位置访问只能从表头开始依次向后扫面，直至找到那个特定的问题，所需要的平均时间为O(n)。

在链表中进行插入和删除操作不需要移动元素，在给出指向链表中某个合适位置的指针后，插入和删除操作所需的时间仅为O(1)；在顺序表中进行插入和删除操作需移动元素，平均时间为O(n)，当线性表中元素个数较多时，特别是当元素占用的存储空间较多时，移动元素的时间开销很大。

作为一般规律，若线性表需频繁查找却很少进行插入和删除操作，或者操作和“数据元素在线性表中的位置”密切相关时，宜采用顺序表作为存储结构；若线性表需频繁进行插入和删除操作，宜采用链表作为存储结构。（第51页）

2、空间性能比较：

所谓空间性能是指某种存储结构所占用的存储空间的大小。

顺序表中每个节点（即数组元素）只存储数据元素，链表的每个结点除了存储数据元素，还要存储指示元素之间逻辑关系的指针。如果数据域占据的空间较小，则指针的结构性开销占去了结点的大部分空间，因而从节点的存储密度上讲，顺序表的存储空间利用率较高。

由于顺序表需要分配一定长度的存储空间，如果事先不知道线性表的大致长度，则有可能对存储空间分配得过大，致使存储空间得不到充分利用，造成浪费；若估计得过小，则会发生上溢。链表不需要固定长度的存储空间，只有有存储空间可以分配，链表中的元素个数则没有限制。

作为一定规律，当线性表中的元素个数变化较大或者未知时，最好使用链表实现；如果事先知道线性表的大致长度，使用顺序表的空间效率会更高。（第52页）

1-4 带头结点的单循环链表中，任一结点的后继结点的指针域均不空。

T

课本：在单链表中，如果将终端节点的指针有空指针改为指向头节点的指针，就使整个单链表形成一个环，这种头尾相接的单链表称为循环单链表（circular singly linked list）（第50页）

1-5顺序表 – 存储结构

顺序表中逻辑上相邻的元素，其物理位置也一定相邻。

T

课本：线性表的顺序存储结构成为线性表（sequential list），其基本思想是用一段地址连续的存储单元依次存储线性表的数据元素：。设线性表的每个元素占用v个存储单元，（第31页）

1-6链式存储的优点是插入、删除元素时不会引起后续元素的移动，缺点是只能顺序访问各元素。

T

课本：单链表的插入操作：单链表的插入操作是将值为x的新结点插入到单链表的第i个位置，即插入到与之间。

template void LinkList::Insert(int i, T x){Node *p = first, *s = nullptr;int count = 0;while(p != nullptr && count  next;count++;}if(p == nullptr) throw"插入位置错误";else{s = new Node;s -> data = x;s -> next = p -> next;p -> next = s;}}

（第44页）

像取出线性表中第i个元素这样的按位置随机访问的操作，使用顺序表更快一些，时间性能为O(1)；相比之下，链表中按位置访问只能从表头开始依次向后扫描，直至找到那个特定的位置，所需要的平均时间为O(n)。

在链表中进行插入和删除操作不需要移动元素，在给出指向链表中某个合适位置的指针后，插入和删除操作所需的时间仅为O(1)；在顺序表中进行插入和删除操作需移动元素，平均时间为O(n)，当线性表中元素个数较多时，特别是当元素占用的存储空间较多时，移动元素的时间开销很大。（第51页）

1-7线性表若采用链式存储结构时，要求内存中可用存储单元的地址一定不连续。

F

课本：单链表（singly linked list）是用一组任意的存储单元存放线性表的元素，这组存储单元可以连续也可以不连续，甚至可以零散分布在内存中任意位置。（第38页）

1-8链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。

T

课本：删除算法的时间主要耗费在查找正确位置上，因此时间复杂度为O(n)：

template T LinkList::Delete(int i){T x;Node *p = first, *q = nullptr;int count = 0;while(p != nullptr && count  next;count++;}if(p == nullptr || p -> next == nullptr){throw "删除位置错误";}else{q = p -> next;x = q -> data;p -> next = q -> next;delete q;return x;}}

（第47页）

在链表中进行插入和删除操作不需要移动元素，在给出指向某个合适位置的指针后，插入和删除操作所需的时间仅为O(1)；顺序表中进行插入和删除操作需移动元素，平均时间为O(n)，当线性表中元素个数较多时，特别是当元素占用的存储空间较多时，移动元素所需的时间开销很大。（第51页）

1-9若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用顺序表存储最节省时间。

T

线性表采用顺序表,便于进行存取任一指定序号的元素;线性表采用链表,便于进行插入和删除操作。但该题是在最后进行插入和删除运算,所以利用顺序表存储方式最节省时间。

1-10对于顺序存储的长度为N的线性表，删除第一个元素和插入最后一个元素的时间复杂度分别对应为O(1)和O(N)。

F

1-11在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。

T

课本：设顺序表的表长是n，显然，删除第i个（1<i<n)元素需要移动n-i个元素，令表示元素移动次数的平均值，pi表示删除第i个元素的概率，等概率情况下，pi = 1/n，（第31页）

1-12顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

F

课本：在链表中进行插入和删除操作不需要移动元素，在给出指向链表中某个合适位置的指针后，插入和删除操作所需的时间仅为O(1)；在顺序表中进行插入和删除操作需要移动元素，平均时间为O(n)，当线性表中元素个数较多时，特别是当元素占用的存储空间较多时，移动元素的时间开销很大。（第51页）

顺序表中每个结点（即数组元素）只存储数据元素，链表的每个结点除了存储数据元素，还要存储指示元素之间逻辑关系的指针。如果数据域占据的空间较小，则指针的结构性开销就占去了整个结点的大部分，因此从结点的存储密度上讲，顺序表的存储空间利用率较高。（第52页）

1-13在具有N个结点的单链表中，访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)。

F

像取出线性表中第i个元素这样的按位置随机访问的操作，使用顺序表更快一些，时间性能为O(1)；相比之下，链表中按位置访问只能从表头开始依次向后扫描，直至找到那个特定的位置，所需要的平均时间为O(n)。

在链表中进行插入和删除操作不需要移动元素，在给出指向链表中某个合适位置的指针后，插入和删除操作所需的时间仅为O(1)；在顺序表中进行插入和删除操作需移动元素，平均时间为O(n)，当线性表中元素个数较多时，特别是当元素占用的存储空间较多时，移动元素的时间开销很大。（第51页）

1-14线性表采用链式存储表示时，所有结点之间的存储单元地址可以连续也可以不连续。

T

课本：单链表（singly linked list）是用一组任意的存储单元存放线性表的元素，这组存储单元可以连续也可以不连续，甚至可以零散分布在内存中任意位置。（第38页）

1-15 在单链表中，要访问某个结点，只要知道该结点的指针即可。因此，单链表是一种随机存取结构。

F

课本：顺序表中数据元素的存储地址是其序号的线性函数，只要确定了存储顺序表的起始地址（即基地址），计算任意一个元素的存储地址的时间是相等的，具有这一特点的存储结构称为随机存储(random access)结构。（第31页）

像取出线性表中第i个元素这样的按位置随机访问的操作，使用顺序表更快一些，时间性能为O(1)；相比之下，链表中按位置访问只能从表头开始依次向后扫描，直至找到那个特定的位置，所需要的平均时间为O(n)。（第51页）

1-16在具有头结点的链式存储结构中，头指针指向链表中的第一个元素结点。

F

注意题目条件：具有头结点

课本：单链表（singly linked list）是用一组任意的存储单元存放线性表的元素，这组存储单元可以连续也可以不连续，甚至可以零散分布在内存中任意位置。为了正确表示元素之间的逻辑关系，每个存储单元在存储数据元素的同时，还必须存储其后继元素所在的地址信息，这个地址信息称为指针。这两部分组成了数据元素的存储映象，称为结点（node）。（第38页）

加上头节点之后，无论单链表是否为空，头指针始终指向头结点（第39页）

1-17在一个设有头指针和尾指针的单链表中，执行删除该单链表中最后一个元素的操作与链表的长度无关。

F

不能从单链表的尾指针中得到指向最后一个元素的前一个元素的指针。

课本：整个单链表的存取必须从头指针开始。由于最后一个元素无后继，故最后一个元素所在结点（成为终端结点）的指针域为空，用^表示，这个空指针成为尾指针（tail mark）。（第39页）

1-18循环链表可以做到从任一结点出发，访问到链表的全部结点。

T

1-19在单链表中，逻辑上相邻的元素，其物理位置必定相邻。

F

课本：单链表（singly linked list）是用一组任意的存储单元存放线性表的元素，这组存储单元可以连续也可以不连续，甚至可以零散分布在内存中任意位置。（第38页）

1-20在双向链表中，可以从当前结点出发访问到任何一个结点。

T

想吐槽一下，这本书第二章的2.4.5写得贼烂，可能是没把这个当作重点，想学循环链表，还是别看这本书吧。

2、单选题

2-1在一个长度为n的顺序表中，向第i个元素(1≤i≤n+1)位置插入一个新元素时需要从后向前移动多少个元素。

B.n-i+1

这描述有毛病吧，我勒个丢。

课本：平均移动次数为n/2，O(n)。（第35页）

2-2对于线性表，在顺序存储结构和链式存储结构中查找第k个元素，其时间复杂性分别是多少？

D.O(1)和O(k)

课本：像取出线性表中第i个元素这样的按位置随机访问的操作，使用顺序表更快一些，时间性能为O(1)；相比之下，链表中按位置访问只能从表头开始依次向后扫描，直至找到那个特定的位置，所需要的平均时间为O(n)。（第51页）

2-3在顺序结构表示的线性表中，删除第i个元素（数组下标为i-1)，需要把后面的所有元素都往前挪一位，相应的语句是：

for (___________ )PtrL->Data[j-1]=PtrL->Data[j];

其中空缺部分的内容应该是

A.j = i; jLast; j++

j的前面少一个吧int，弄得选项能不能严谨些。。。。。。。。。。。

课本：

template T SeqList::Delete(int i){T x;if(length == 0) throw "下溢";if(i  length) throw"删除位置错误";x = data[i-1];for(int j = i; j < length; j++){data[i-1] = data[j];}length--;return x;}

（第36页）

2-4向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（ ）

B.63.5

（（127）*（127+1）/2）（总移动次数）/128（元素可插入的位置）

2-5顺序表是线性表的( )

B.顺序存储结构

2-6以下说法错误的是 ( )。

C.在链表上实现读表元运算的平均时间复杂度为O（1）

课本：像取出线性表中第i个元素这样的按位置随机访问的操作，使用顺序表更快一些，时间性能为O(1)；相比之下，链表中按位置访问只能从表头开始依次向后扫描，直至找到那个特定的位置，所需要的平均时间为O(n)。（第51页）

2-7 哪个选项不是线性表的链式存储结构（ ）

B.顺序表

2-8 在向表中第i个元素（1≤i≤n+1）位置插入一个新元素时，为保持插入后表中原有元素的相对次序不变，需要从后向前依次后移（ ）个元素。

B.n-i+1

课本35页上最下面。

template void SeqList::Insert(int i, T x){if(lengrth == Maxsize) throw"上溢";if(i  length-1) throw"插入位置错误";for(int j = length; j >= i; j--)data[j] = data[j-1];data[i - 1] = x;length++;}

2-9 在删除表中第i个元素时，同样地，为保持删除后表中原有元素的相对次序不变，需要从前向后依次前移（ ）个元素。

A.n-i

课本36页最下面

2-10 与单链表相比，双链表的优点之一是（）。

D.顺序访问相邻结点更加灵活

课本：从顺序链表的任意结点出发，可以扫描到其它结点，从而提高了链表操作的灵活性。（第51页）

2-11 在单链表中，要删除某一指定结点，必须先找到该结点的（）。

A.直接前驱

课本：

template T LinkList::Delete(int i){T x;Node *p = first, *q = nullptr;int count = 0;while(p != nullptr && count  next;count++;}if(p == nullptr || p -> next == nullptr){throw "删除位置错误";}else{q = p -> next;x = q -> data;p -> next = q -> next;delete q;return x;}}

（第46、47页）

2-12 循环链表的主要优点是（）。

D.从表中的任意结点出发都能扫描到整个链表

2-13 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用（）存储方式最节省运算时间。

D.带表头附加结点的双循环链表

学！！！

2-14 单链表又称为线性链表，在单链表上实施插入和删除操作（ ）。

B.不需移动结点，只需改变结点指针

2-15 链表不具有的特点是( )。

A.可随机访问任一个元素

课本：像取出线性表中第i个元素这样的按位置随机访问的操作，使用顺序表更快一些，时间性能为O(1)；相比之下，链表中按位置访问只能从表头开始依次向后扫描，直至找到那个特定的位置，所需要的平均时间为O(n)。（第51页）

2-16 下面关于线性表的叙述中，错误的是____。

B.线性表采用顺序存储，便于进行插入和删除操作。

课本：（第51页）

2-17 单链表L（带头结点）为空的判断条件是____。

B.L->next==NULL

2-18在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ ）。

B.s->next=p->next;p->next=s

2-19 对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）

B.head→next==NULL

课本：即判断单链表是否只有头指针（第41页）

2-20 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。

D.带头结点的双循环链表

学！！！

3、填空题

3-1 顺序表 – 地址计算

假设顺序表第 1 个元素的内存地址是 100，每个元素占用 2 字节内存空间，则第 5 个元素的内存地址是 ____。

答案：108

课本：设顺序表的表长是n，显然，删除第i个（1<i<n)元素需要移动n-i个元素，令表示元素移动次数的平均值，pi表示删除第i个元素的概率，等概率情况下，pi = 1/n，（第31页）

4-2在有n个元素的顺序表中删除任意一个元素所需移动元素的平均次数为____。

答案：（n-1）/2

课本36页最下面，移动n-i

4-3在有n个元素的顺序表中的任意位置插入一个元素所需移动元素的平均次数为____。

答案：n/2

课本35页最下面，移动n-i+1

4-4 在长度为n的顺序表L中将所有值为x的元素替换成y，该算法的时间复杂度为____。

答案：O(n)

4-5 在顺序表中，逻辑上相邻的元素，其物理位置____相邻。在单链表中，逻辑上相邻的元素，其物理位置____相邻。

答案：一定、不一定

4-6 对于顺序表的插入算法insert_sqlist来说，若以结点移动为标准操作，则插入算法的在最坏情况下的移动次数为____，时间复杂度是____。在平均情况下的移动次数为____，时间复杂度是____。

答案：n、O(n)、n/2、O(n)

4-7 线性表L=(a1, a2, … , an)用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是____。

答案：n/2

据题意，该存储方式为顺序表

4、程序填空题

#includeusing namespace std;#define OK 1#define ERROR 0#define MAXSIZE 100typedef int datatype;typedef struct {datatype *elem; int length;} SqList;int ListDelete_Sq(SqList &L, int i) {if ((i  L.length))return ERROR; for (int j = i; j > n;for (i=0;i> L.elem[i];L.length = i;cin >> a;if (ListDelete_Sq(L, a)){for (i = 0; i < L.length; i++)if(i==0) cout<< L.elem[i];else cout<< " " << L.elem[i];}elsecout << "ERROR";return 0;}

先补充CreateList(LinkList &L, int n) 函数

https://blog.csdn.net/qq_25368751/article/details/107961269

#includeusing namespace std;#define OK 1#define ERROR 0typedef int ElemType;typedef struct LNode {ElemType data;struct LNode *next; } LNode, *LinkList; void CreateList(LinkList &L, int n)//该函数未{ElemType a;for(int i=0; i>a;LNode *s;s->data = a;s->next = L->next;L->next = s;}}int ListDelete_L(LinkList &L, int i) {LinkList p, q;int j;p = L;j = 0;while (①){p = p->next;++j;}if (!(p->next) || (j > i - 1))return ERROR; q = p->next;② delete q; return OK;} void print(LinkList &L){LinkList p;int flag=1;p = L->next;while (p){if(flag)cout <data;elsecout << " "<data;flag=0;p = p->next;}}int main() {LinkList L;ElemType e;int length;int i;cin >> length;CreateList(L, length);cin >> i;ListDelete_L(L,i);print(L);return 0;}

L.elem[i-1] = L.elem[i]

4-2 单链表的删除操作

#includeusing namespace std;#define OK 1#define ERROR 0typedef int ElemType;typedef struct LNode {ElemType data;struct LNode *next; } LNode, *LinkList; void CreateList(LinkList &L, int n) ;//该函数未显示细节 int ListDelete_L(LinkList &L, int i) {LinkList p, q;int j;p = L;j = 0;while (①) {p = p->next;++j;}if (!(p->next) || (j > i - 1))return ERROR; q = p->next;②delete q; return OK;} void print(LinkList &L){LinkList p;int flag=1;p = L->next;while (p) {if(flag)cout <data;elsecout << " "<data;flag=0;p = p->next;}}int main() {LinkList L;ElemType e;int length;int i;cin >> length;CreateList(L, length);cin >> i;ListDelete_L(L,i);print(L);return 0;}

(p->next) && (j < i – 1)

p->next = q ->next;

5、函数题

5-1求顺序表最大值

本题要求实现一个函数，要求返回顺序表的最大值，空表返回0。题目保证顺序表中所有元素都为正整数。

函数接口定义：

int GetMax(SqList L);

其中SqList结构定义如下：

typedef struct{ElemType *elem;int length;}SqList;

裁判测试程序样例：

#include #include #define MAXSIZE 5typedef int ElemType;typedef struct{ElemType *elem;int length;}SqList;void InitList(SqList &L);/*细节在此不表*/int GetMax(SqList L);int main(){SqList L;InitList(L);int p;p=GetMax(L);if(p) printf("The max of SequenceList L is %d.\n",p);else printf("The SequenceList is null.\n");return 0;}/* 请在这里填写答案 */

输入格式：

输入数据有1行，首先给出以-1结束的顺序表元素（不超过100个，-1不属于顺序表元素），所有数据之间用空格分隔。题目保证输入的顺序元素都是正整数。

输入样例：

2 6 4 13 9 -1

输出样例：

The max of SequenceList L is 13.

代码长度限制：16 KB

时间限制：400 ms

内存限制：64 MB

int GetMax(SqList L)的定义：

int GetMax(SqList L){ int max = 0; for(int i=0;imax)max = L.elem[i]; } return max;}

关于void InitList(SqList &L)的定义：

the first：关于c语言下用scanf的输出；L.length的初始值不是零；无法将输入数据存入elem中

void InitList(SqList &L){int a;scanf("%d",&a);L.length = 0 ;while(a != -1){printf("%d",L.length);L.elem[L.length] = a;L.length++;scanf("%d",&a);}//printf("%d",L.length);}

the last：elem被定义为指针，将elem指向数组首地址；

void InitList(SqList &L){int a;scanf("%d",&a);L.length = 0 ;int b[100];L.elem = b;while(a != -1){printf("%d",L.length);L.elem[L.length] = a;printf("%d",L.elem[L.length]);L.length++;scanf("%d",&a);}//printf("%d",L.length);}

5-2单链表逆置*

已知单链表的结点结构定义如下：

typedef struct _NODE_{int data;struct _NODE_ *next;} NODE;

说明：data为数据域。next为指针域，指示后继结点。

请编写函数，将带附加头结点的单链表逆置。

函数原型

void Reverse(NODE *head);

说明：参数head为单链表的头指针。函数将单链表中数据元素的排列顺序颠倒过来。

裁判程序

int main(){NODE *h;Create(&h);Input(h);Reverse(h);Output(h);putchar('\n');Destroy(&h);return 0;}

说明：Create 函数用于创建链表，Destroy 函数用于销毁链表。Input 函数用于输入链表：首先输入结点数，然后输入这些数据元素。Output 函数用于输出单链表，数据元素之间以空格间隔。

输入样例

5
28 47 79 52 36

输出样例

36 52 79 47 28

代码长度限制：16 KB

时间限制：400 ms

内存限制：64 MB

void Reverse(NODE *head) {NODE *p, *q, *r; //p为工作指针，q为p的后继，以防断链p = head->next;head->next = NULL;while (p != NULL) { //头节点不空q = p->next;p->next = head->next;head->next = p;p = q;}return head;}

5-3单链表统计正数个数

本题要求实现一个函数，返回带头结点的单链表中正整数的个数。

函数接口定义：

int PositiveInt(LinkList L);

L是带头结点的单链表的头指针，函数PositiveInt返回L中正整数的个数。如果单链表为空，返回0。

其中LinkList结构定义如下：

typedef struct LNode{ElemType data;struct LNode *next;}LNode,*LinkList;

裁判测试程序样例：

#include #include typedef int ElemType;typedef struct LNode{ElemType data;struct LNode *next;}LNode, *LinkList;LinkList Create();/* 细节在此不表 */int PositiveInt(LinkList L);int main(){LinkList L, p;L = Create();printf("The number of positive integers is %d.\n", PositiveInt(L));return 0;}/* 你的代码将被嵌在这里 */

输入格式：

输入数据为1行，给出以-1结束的单链表元素（-1不属于单链表元素），所有数据之间用空格分隔。

输入样例：

6 3 4 5 3 -1

输出样例：

The number of positive integers is 5.

代码长度限制:16 KB

时间限制:400 ms

内存限制:64 MB

the first

int PositiveInt(LinkList L){int num = 0;while(L->next){L = L->next;num++;}return num;} 

the last:倒是没想到竟然还要考虑输入的0，

int PositiveInt(LinkList L){int num = 0;LNode *p = L->next;while(p){if((p->data) next;continue;}p = p->next;num++;}return num;} 

6、编程题

6-1学生顺序表的建立

完成对一个顺序表的建立，表中的每个元素是同学们的学号、姓名和三门课程的成绩，输入5个同学的信息，然后显示在屏幕上。（要求利用顺序表的基本操作）

输入格式:

首先收入学生人数5，然后依次输入5个学生的学号、姓名和三门课的成绩

输出格式:

输入5个学生的学号、姓名和三门课的成绩

输入样例:

5
01 张三 89 89 89
02 李四 90 90 90
03 王五 89 89 89
04 钱六 97 97 97
05 赵倩 90 90 90

输出样例:

1 张三 89.0 89.0 89.0
2 李四 90.0 90.0 90.0
3 王五 89.0 89.0 89.0
4 钱六 97.0 97.0 97.0
5 赵倩 90.0 90.0 90.0

代码长度限制：16 KB

时间限制：400 ms

内存限制：64 MB

​

#includeusing namespace std;#includeclass seqlist{public:seqlist(){cin>>len;for(int i=0;i>id[i];cin>>name[i];cin>>a[i]>>b[i]>>c[i];}}void printlist(){for(int i=0;i<len;i++){cout<<id[i]<<" "<<name[i]<<" ";printf("%.1f %.1f %.1f\n",a[i],b[i],c[i]);}}private:int id[100];string name[100];double a[100],b[100],c[100];int len;};int main(){seqlist l;l.printlist();return 0;}

6-2求两个一元多项式的和

输入格式:

输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。

输出格式:

输出分1行，分别以指数递降方式输出和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。

输入样例1:

4 3 4 -5 2 6 1 -2 0
3 5 20 -7 4 3 1

输出样例1:

5 20 -4 4 -5 2 9 1 -2 0

代码长度限制:16 KB

时间限制:400 ms

内存限制:64 MB

the first：显示同类项有合并的和系数和指数取上限，结果有零的多项式没有考虑，就是指数不为零，系数为零的时候，不输出；

#includeusing namespace std;int main(){int a[1000][2];int b[1000][2];int c,d;cin>>c;int n,k;int num = c;for(int i=0;i>n>>k;a[i][0] = n;a[i][1] = k;}// //text// coutd;for(int i=0;i>n>>k;b[i][0] = n;b[i][1] = k;}////text// cout<<b[0][0]<<" "<<b[0][1];// for(int i=1;i<d;i++)// {// cout<<" "<<b[i][0]<<" "<<b[i][1];// }// cout<<endl;//for(int i=0;i<d;i++){int j;for( j=0;j<c;j++){int th = b[i][1];int fh = a[j][1];if(th == fh){//cout<

the last:要充分考虑样例和题目要求，

#includeusing namespace std;int main(){int a[1000][2];int b[1000][2];int c,d;cin>>c;int n,k;int num = c;for(int i=0;i>n>>k;a[i][0] = n;a[i][1] = k;}// //text// coutd;for(int i=0;i>n>>k;b[i][0] = n;b[i][1] = k;}////text// cout<<b[0][0]<<" "<<b[0][1];// for(int i=1;i<d;i++)// {// cout<<" "<<b[i][0]<<" "<<b[i][1];// }// cout<<endl;//for(int i=0;i<d;i++){int j;for( j=0;j<c;j++){int th = b[i][1];int fh = a[j][1];if(th == fh){//cout<

https://blog.csdn.net/lin__hao/article/details/106559027

运用链表的版本：暂时不想写，再说吧

6-3 两个有序链表合并（新表不含重复元素）

已知两个非降序链表序列S1与S2，设计函数构造出S1与S2合并后的新的非降序链表S3。
要求S3中没有重复元素。

输入格式:

输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。

输出格式:

在一行中输出合并后新的非降序链表，要求链表中没有重复元素。数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。

输入样例:

在这里给出一组输入。例如：

1 3 3 5 8 -1
2 3 4 6 8 10 -1

输出样例:

在这里给出相应的输出。例如：

1 2 3 4 5 6 8 10

代码长度限制：16 KB

时间限制：400 ms

内存限制：64 MB

https://blog.csdn.net/karshey/article/details/115256971

#includeusing namespace std;typedef struct LNode{int data;struct LNode *next;}LNode,*LinkList;void createList(LinkList &L){int n;L=new LNode;L->next=NULL;LinkList p,r=L;//r是扫描指针 while(cin>>n){if(n==-1) break;p=new LNode;p->data=n;p->next=NULL;r->next=p;r=p;}}void Union(LinkList s1,LinkList s2,LinkList &s3){s3=new LNode;s3->next=NULL;LinkList r=s3,p1=s1->next,p2=s2->next;//先比较第一个：两个都非空表的情况if(p1&&p2) {if(p1->data==p2->data){LinkList p=new LNode;p->data=p2->data;p->next=NULL;r->next=p;r=p;p2=p2->next;p1=p1->next;}else if(p1->datadata){LinkList p=new LNode;p->data=p1->data;p->next=NULL;r->next=p;r=p;p1=p1->next;}else if(p1->data>p2->data){LinkList p=new LNode;p->data=p2->data;p->next=NULL;r->next=p;r=p;p2=p2->next;}}//有至少一个空表 else{//先放第一个if(p1){LinkList p=new LNode;p->data=p1->data;p->next=NULL;r->next=p;r=p;p1=p1->next;}else if(p2){LinkList p=new LNode;p->data=p2->data;p->next=NULL;r->next=p;r=p;p2=p2->next;}//再往后放while(p1){if(r->datadata){LinkList p=new LNode;p->data=p1->data;p->next=NULL;r->next=p;r=p;}p1=p1->next;} while(p2){if(r->datadata){LinkList p=new LNode;p->data=p2->data;p->next=NULL;r->next=p;r=p;}p2=p2->next;} }//两个表都存在的情况 while(p1&&p2){//要先判断是否相同 if(p1->data==p2->data&&(r->datadata)){LinkList p=new LNode;p->data=p2->data;p->next=NULL;r->next=p;r=p;p2=p2->next;p1=p1->next;}else if(p1->datadata&&(r->datadata)){LinkList p=new LNode;p->data=p1->data;p->next=NULL;r->next=p;r=p;p1=p1->next;}else if(p1->data>p2->data&&(r->datadata)){LinkList p=new LNode;p->data=p2->data;p->next=NULL;r->next=p;r=p;p2=p2->next;}//注意，这里要设置都不满足的操作，不然又会死循环//这里是r->data==p->data的情况else{if(r->data==p1->data) p1=p1->next;if(r->data==p2->data) p2=p2->next;} }//有一遍已经循环完毕 while(p1){if(p1->data>r->data){LinkList p=new LNode;p->data=p1->data;p->next=NULL;r->next=p;r=p;p1=p1->next;}else{p1=p1->next;}}while(p2){if(p2->data>r->data){LinkList p=new LNode;p->data=p2->data;p->next=NULL;r->next=p;r=p;p2=p2->next;}else p2=p2->next;}}int main(){LinkList s1,s2,s3;createList(s1);createList(s2);Union(s1,s2,s3);if(s3->next==NULL){cout<next;int temp=0;while(p){if(temp) cout<<" ";cout<data;p=p->next;temp++;}return 0;}

6-4在有序链表中插入数据

给定一批严格递增排列的整型数据，给定一个x，若x不存在，则插入x，要求插入后保持有序。存在则无需任何操作。

输入格式:

输入有两行：
第一个数是n值，表示链表中有n个数据。后面有n个数，分别代表n个数据。
第二行是要插入的数。

输出格式:

输出插入后的链表数据，以空格分开。行末不能有多余的空格。

输入样例1:

在这里给出一组输入。例如：

5 1 3 6 9 11
4

输出样例1:

在这里给出相应的输出。例如：

1 3 4 6 9 11

输入样例2:

在这里给出一组输入。例如：

5 1 3 6 9 11
3

输出样例2:

在这里给出相应的输出。例如：

1 3 6 9 11

代码长度限制：16 KB

时间限制：400 ms

内存限制：64 MB

#includeusing namespace std;template struct Node{DataType data; //数据域Node *next; //指针域};template class LinkList{public:LinkList();//无参构造函数，建立只有头结点的空链表LinkList(DataType a[], int n); //有参构造函数，建立有n个元素的单链表~LinkList(); //析构函数int Length(); //求单链表的长度void Insert(DataType x); //插入操作，第i个位置插入值为x的结点void PrintList( );//遍历操作，按序号依次输出各元素private:Node *first; //单链表的头指针};template LinkList :: LinkList( ){first = new Node;//生成头结点first->next = nullptr;//头结点的指针域置空}template LinkList :: ~LinkList( ){Node *q = NULL;while (first != NULL)//释放单链表的每一个结点的存储空间{q = first; //暂存被释放结点first = first->next; // first指向被释放结点的下一个结点delete q;}}template void LinkList :: PrintList( ){int flag=0;Node *p = first->next;//工作指针p初始化while (p!= nullptr){if(flag==0){cout <data;flag=1;}else{cout << " "<data ;}p = p->next; //工作指针p后移，注意不能写作p++}cout<<endl;}/*插入函数*/template void LinkList :: Insert(DataType x){Node *Z = new Node;Z->data = x;Node *p = first, *s = first->next;//工作指针p指向要插入的前一个结点//s为p之后的一个结点，判断是否与要插入的值相等if (p->next == NULL)//链表为空链表{//要插入的元素放在开头Z->next = NULL;p->next = Z;p = Z;return;}while (s->data data&&s->next!=nullptr)//查找第i – 1个结点{p = p->next;s=s->next;}if(s->data == Z->data){//元素已存在delete Z;//删除要插入的结点return;}if(s->data>Z->data){Z->next = p->next; //将结点Z插入到结点p之后p->next = Z;return;}if(s->next==nullptr){//找到链表结尾了，也找不到第i-1个结点s->next=Z;//将结点插在最后Z->next=nullptr;return;}}template LinkList :: LinkList(DataType a[ ], int n){first = new Node;//生成头结点Node *r = first, *s = nullptr; //尾指针初始化for (int i = 0; i < n; i++){s = new Node;s->data = a[i];r->next = s;r = s; //将结点s插入到终端结点之后}r->next = nullptr;//单链表建立完毕，将终端结点的指针域置空}int main( ){int a[10000];int i,n;cin>>n;for(i=0;i>a[i];}LinkList L(a,n);int b;cin>>b;L.Insert(b);L.PrintList();return 0;}

https://blog.csdn.net/qq_40468936/article/details/109011574

2-7 课后题

2-7-1 单选题

1、线性表的顺序存储结构是一种（）的存储结构，线性表的链接存储结构是一种（）的存储结构

随机存取，顺序存取

课本：算法的基本语句时工作指针p后移，该语句执行的次数与被查结点在表中的位置有关。在查找成功的情况下，若查找次数为n（1<=i<=n），则需要执行i-1次，等概率情况下，平均时间性能为O(n)。因此单链表是顺序存储（sequential access）结构。（第34页）

2、线性表采用链接存储时，地址（）

连接与否均可

3、循环单链表的主要优点是（）

B、从表中任一结点出发都能扫描到整个链表

D、在进行插入、删除操作时，能更好地保证链表不断开

4、链表不具备的特点是（）

A、可随机访问任一元素

D、所需空间与线性表长度成正比

5、若某线性表中最常用的操作时去第i个元素和找第i个元素的前驱，则采用（）存储方法最节省时间

顺序表

6、⭐若线性中表最常用的操作是在最后一个元素之后插入一个元素和删除第一个结点，则采用（）存储方法最节省时间

带尾指针的单循环链表

7、⭐若链表中表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用（）存储方法最节省时间

B、循环双链表

D、带尾指针的单循环链表

8、在具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（）

O(n)

9、对于n个元素组成的线性表，建立一个有序单链表的时间复杂度是（）

O（n^2）

﹏建立一个有n个元素的有序单链表的时间复杂度度为什么是O(n^2) 求详解哇……(>﹏<)_百度知道 (baidu.com)

10、使用双链表存储线性表，其优点是可以（）

A、提高检索速度

B、更方便数据的插入和删除

单链表是顺序存取结构（第43页）

11、在一个单链表中已知q所指结点是p所指结点的直接前驱，若在q和p之间插入s所指结点，则执行（）操作

q ->next = s;

s -> next = p;

12、在循环双链表的p所指结点后插入s所指结点的操作是（）

s -> prior = p;

s -> next = p -> next;

p -> next -> prior = s;

p -> next = s;

13、用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中某结点，则j后移的操作语句为（）

j = r[j].next

静态链表-----用数组实现的单链表。_单链表是静态链表吗_Nactua的博客-CSDN博客

课本54页

14、设线性表有n个元素，以下操作中，（）在顺序表上实现比在链表上实现的效率更高。

输出第i（1<=i<=n）个元素值

15、假设线性表只有4种基本操作：删除第一个元素：删除最后一个元素；在第一个元素前插入新元素；在最后一个元素之后插入新元素，则最好使用（）

A.只设尾指针的循环单链表。

B.只设尾指针的非循环双链表。

C.只设头指针的循环双链表。

D.同时设置头指针和尾指针的循环单链表。

第三章 栈和队列

3.1 判断题

1-1若一个栈的输入序列为1，2，3，…，N，输出序列的第一个元素是i，则第j个输出元素是j−i−1。

F

举例子

1-2所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。

F

将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列成为循环队列。这种循环队列可以以单链表的方式在实际编程应用中来实现。循环队列是一种抽象的数据结构，单向循环链表和循环数组是具体的实现方式，不是数据结构本身。

#数据结构#第三章：队列_vircorns的博客-CSDN博客_所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。

1-3在对不带头结点的链队列作出队操作时，不会改变头指针的值。

F

1-4 不论是入队列操作还是入栈操作,在顺序存储结构上都需要考虑"溢出"情况。

T

在顺序队列中，随着队列的插入和删除操作，整个队列向着数组的高端移过去，从而产生了队列的“单向移动性”。当元素被插入到数组中下标最大的位置之后，数组空间就用尽了，尽管此时数组的低端还有空闲空间，这种现象叫做假溢出（false overflow）。（课本第79、80页）

1-5 队列和栈都是运算受限的线性表，只允许在表的两端进行运算。

F

1-6 栈和队列的存储方式，既可以是顺序方式，也可以是链式方式。

T

1-7循环队列也存在着空间溢出问题。

T

队列满了

1-8 循环队列执行出队操作时会引起大量元素的移动。

F

只需要将队头front在循环意义下+1（课本第82页）

1-9 栈是插入和删除只能在一端进行的线性表；队列是插入在一端进行，删除在另一端进行的线性表。

T

1-10在n个元素连续进栈以后，它们的出栈顺序和进栈顺序一定正好相反。

T

连续

1-11 环形队列中有多少个元素可以根据队首指针和队尾指针的值来计算。

T

count=(rear-front+MaxSize)%MaxSize

环形队列2-基于队头指针和队列中元素的个数的另一种实现_热爱艺术的程序员的博客-CSDN博客

1-12 栈和队列的插入和删除操作特殊，所以，栈和队列是非线性结构。

F

1-13 序列{1,2,3,4,5}依次入栈，则不可能得到{3,4,1,2,5}的出栈序列。

T

1-14 队列中允许插入的一端叫队头，允许删除的一端叫队尾。

F

3.2 单选题

2-1 若用大小为6的数组来实现循环队列，且当前front和rear的值分别为0和4。当从队列中删除两个元素，再加入两个元素后，front和rear的值分别为多少？

A.2和0

D.2和6

大小为6的数组的下标最大是5，入队后rear=(rear+2)%6

https://blog.csdn.net/m0_52561302/article/details/124173589

2-2 如果循环队列用大小为m的数组表示，且用队头指针front和队列元素个数size代替一般循环队列中的front和rear指针来表示队列的范围，那么这样的循环队列可以容纳的元素个数最多为：

B.m

我们前面采用front与rear指针来实现循环队列其中队满的判断是front = （rear+ 1）% n来判断的，因此我们是实际容纳元素的个数就是m-1，但是这里我们用size代替了rear指针，也就是说我们队满可以用size与m的关系来判断。因此这里的实际容纳元素的数目就是m。！！！！！

https://blog.csdn.net/qq_43446165/article/details/102376464

2-3 以下数据结构中，（ ）是非线性数据结构。

A.树

2-4 设栈S和队列Q的初始状态均为空，元素{1, 2, 3, 4, 5, 6, 7}依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是{2, 5, 6, 4, 7, 3, 1}，则栈S的容量至少是：

D.4

2-5 线性表、堆栈、队列的主要区别是什么？

B.堆栈和队列都是插入、删除受到约束的线性表

2-6 栈和队列的共同点( )。

C.只允许在端点处插入和删除元素

2-7 下列关于线性表,栈和队列叙述,错误的是( )。

A.线性表是给定的n(n必须大于零)个元素组成的序列

可以为零，即为空，只有表头。

2-8 设用一个数组A[1……N]来存储一个栈，令A[N]为栈底，用整型变量T指示当前栈顶位置，A[T]为栈顶元素。当从栈中弹出一个元素时，变量T的变化为（ ）。

A.T=T+1

2-9 链式栈与顺序栈相比，一个比较明显的优点是（ ）。

B.通常不会出现栈满的情况

2-10 (neuDS)在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的长度是（ ）。

C.(rear-front+maxSize)%maxSize

2-11 (nueDS_C++)设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（　　 ）。提示：对于栈，可以全进再依次出；也可以进一个出一个；也可以进一部分，出一个，再进一部分；但是出栈之后，不能再入栈。

A.3

2-12 作者DS课程组 单位临沂大学

关于栈和队列的下列说法正确的是（）

B.栈是后进先出的结构，出栈时除了栈顶元素，其余元素无需移动；

2-13 作者赵玉霞 单位滨州学院

一个栈的入栈序列是a,b,c,d,e，则栈的出栈序列不可能的是（ ）。

C.dceab

2-14作者王俊玲单位集美大学

在一个链表表示的队列中， f和r分别指向队列的头和尾。下列哪个操作能正确地将s结点插入到队列中：

B.r->next=s; r=s;

2-15 作者王东单位贵州师范学院

栈和队列具有相同的。

B.逻辑结构

都属于线性结构，对数据的运算不同，表现出不同的特点

2-16 作者王东单位贵州师范学院

假定利用数组a[n]顺序存储一个栈，用top表示栈顶指针，用top==-1表示栈空，并已知栈未满，当元素x进栈时所执行的操作为（　）。

C. a[++top]=x

2-17 作者王东 单位贵州师范学院

队列的“先进先出”特性是指（　）。

Ⅰ.最后插入队列中的元素总是最后被删除

Ⅱ.当同时进行插入、删除操作时，总是插入操作优先

Ⅲ.每当有删除操作时，总要先做一次插入操作

Ⅳ.每次从队列中删除的总是最早插入的元素

B.Ⅰ、Ⅳ

2-18 作者王东单位贵州师范学院

已知循环队列存储在一维数组A[0...n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第一个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是（　）。

B.0,n-1

https://blog.csdn.net/weixin_38233103/article/details/108932624

2-19 作者王东 单位贵州师范学院

执行函数时，其局部变量一般采用（　）进行存储。

C.栈结构

2-20作者考研真题 单位浙江大学

对空栈S进行 Push 和 Pop 操作，入栈序列为 a, b, c, d, e，经过 Push, Push, Pop, Push, Pop, Push, Push, Pop 操作后，得到的出栈序列是：

D.b, c, e

2-21 作者ZXM单位西南石油大学

用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为( )。

D.SXSSXSXX

3.3 填空题

3-1作者李廷元 单位中国民用航空飞行学院

栈的运算遵循____的原则。

答案：后进先出

3-2 作者DS课程组 单位西南石油大学

以下运算实现在链队上的入队列，请在空白处用适当句子予以填充。

void EnQueue(QueptrTp *lq,DataType x){ LqueueTp *p; p=(LqueueTp *)malloc(sizeof(LqueueTp)); ____=x; p->next=NULL; (lq->rear)->next=____; ____; }

答案：p->data，p，lq->rear=p

3-3 作者ZXM 单位西南石油大学

以下运算实现在链栈上的初始化，请在空白处用请适当句子予以填充。

typedef struct Node{DataType data;struct Node *next;}StackNode,*LStackTp;void InitStack(LStackTp &ls){ ____;}

答案：top=-1
3.4 课后题

3.4.1 选择题

1、一个栈的入栈序列是1、2、3、4、5，则栈的不可能输出序列是（）

C 43512

2、若一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素是（）

n-i+1

第四章 字符串和多维数组

1、判断题

假设模式串是abababaab，则KMP模式匹配算法中的next[j] =0 1 1 2 3 4 5 6 2。

T

2、单选题

2-1KMP算法下，长为n的字符串匹配长度为m的字串的时间复杂度为

B.O（M+N）

2-2 作者李廷元单位中国民用航空飞行学院

串的长度是指

B.串中所含字符的个数

2-3 作者考研真题单位浙江大学

设主串 T =abaabaabcabaabc，模式串 S =abaabc，采用 KMP 算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是：

B.10

2-4 作者王东单位贵州师范学院

串“ababaaababaa”的next数组为（ ）。

C.011234223456

2-5 作者历年考研真题单位湖州师范学院

已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”。采用KMP算法进行匹配，第一次出现“失配”(s[i]≠t[j])时，i=j=5，则下次开始匹配时，i和j的值分别是()。

C.i=5,j=2

2-6作者叶斌单位成都信息工程大学

2 符号串abcde的子串共有：

C.16

落了个空字符串

2-7作者考研试卷 单位浙江大学

适用于压缩存储稀疏矩阵的两种存储结构是：

A.三元组表和十字链表

2-8作者徐婉珍 单位广东东软学院

(neuDS)以下( )是稀疏矩阵的一种存储方法。

A.十字链表

2-9 作者王俊玲单位集美大学

一个稀疏矩阵采用压缩后，和直接采用二维数组存储相比会失去（ ） 特性。

B.随机存取

2-10作者王东单位贵州师范学院

对特殊矩阵采用压缩存储的主要目的是（　）。

D.减少不必要的存储空间

2-11 作者王东单位贵州师范学院

对n阶对称矩阵压缩存储时，需要表长为（　）的顺序表。

C.n(n+1)/2

2-12作者M

单位西南石油大学

顺序查找法适合于存储结构为（ ）的线性表。

B.顺序存储或链式存储

2-13作者黄诚

单位西南石油大学

（SWPU-DS）设有一个 10 阶的对称矩阵 A，采用压缩存储方式，以行序为主存储，a[1, 1] 为第一元素，其存储地址为 1，每个元素占一个地址空间，则 a[8, 5] 的地址为（ ）。

C.33

第五章 数和二叉树

1、单选题

1-1 设一棵非空完全二叉树T的所有叶节点均位于同一层，且每个非叶结点都有 2 个子结点。若T有k个叶结点，则T的结点总数是：

A.2k−1

2-2作者考研真题单位浙江大学

已知字符集{ a, b, c, d, e, f }，若各字符出现的次数分别为{ 6, 3, 8, 2, 10, 4 }，则对应字符集中各字符的哈夫曼编码可能是：

A.00, 1011, 01, 1010, 11, 100

2-3作者佚名单位互联网

已知二叉树的先序遍历序列为ABCDEFGH，中序遍历序列为CBEDFAGH，则该二叉树形态中，父节点的右子节点为（）。

C.G

2-4 作者考研真题单位浙江大学

若将一棵树T转化为对应的二叉树BT，则下列对BT的遍历中，其遍历序列与T的后根遍历序列相同的是：

B.中序遍历

2-5作者考研真题单位浙江大学

对n个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有 115 个结点，则n的值是：

C.58

2-6作者魏宝刚单位浙江大学

设 T 是非空二叉树，若 T 的先序遍历和中序遍历序列相同，则 T 的形态是 __

D.所有结点只有右孩子

2-7作者魏宝刚单位浙江大学

以二叉链表作为二叉树的存储结构，在具有n个结点的二叉链表中（n>0），空链域的个数为 __

A.n+1

2-8作者魏宝刚单位浙江大学

已知二叉树的前序遍历序列为 ABDCEFG，中序遍历序列为 DBCAFEG，则后序遍历序列为 __

B.DCBFGEA

2-9作者考研真题单位浙江大学

对于任意一棵高度为 5 且有 10 个结点的二叉树，若采用顺序存储结构保存，每个结点占 1 个存储单元（仅存放结点的数据信息），则存放该二叉树需要的存储单元的数量至少是：

A.31

2-10 作者考研真题单位浙江大学

已知森林F及与之对应的二叉树T，若F的先根遍历序列是 a, b, c, d, e, f，后根遍历序列是 b, a, d, f, e, c，则T的后序遍历序列是：

C.b, f, e, d, c, a

2、填空题

2-1已知一棵完全二叉树的第5层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是：____。

答案：47

2-2作者周强单位青岛大学

一棵二叉树的前序遍历序列是ABDFECGHK，中序遍历序列是DBEFAGHCK，则它的后序遍历序列是 ____. (填写半角大写字母且不要添加空格，格式如ABCDEFG）.

答案：DEFBHGKCA

4-3作者YJ单位西南石油大学

具有n个结点的二叉树中,一共有____个指针域,其中只有____个用来指向结点的左右孩子，其余的____个指针域为NULL。

答案：2n,n-1,n+1

第八章 排序

8.1 判断题

1、作者DS课程组单位浙江大学

仅基于比较的算法能得到的最好的“最坏时间复杂度”是O(NlogN)。

T

2、作者DS课程组单位浙江大学

对N个记录进行简单选择排序，比较次数和移动次数分别为O(N2)和O(N)。

T

课本：容易看出，在简单选择排序中记录的移动次数较少。待排序序列为正序时，记录的移动次数最少，为0次，待排序序列为逆序时，记录的移动次数最多，为3(n-1)次。无论记录的初始排序如何，记录的比较次数相同，第i趟排序需进行n-i次比较，简单选择排序需进行n-1趟排序，则总的排序次数是。
所以，简单选择排序最好、最坏和平均的时间性能均为。在简单选择排序过程中，只需要一个用作记录交换的暂存单元。由于记录交换不是在相邻单元中进行，简单选择排序是一种不稳定的排序方式。（课本268页）

void Sort :: SelectSort(){int i, j, index, temp;for(i = 0; i < length-1; i++)//进行length-1趟简单排序{index = i;for(j = i+1; j < length; j++)//在无序区中选最小记录{if(data[j]<data[index]) {index = j;}}if(index != i){temp = data[i];data[i] = data[index];data[index] = temp;}}}

3、作者DS课程组单位浙江大学

对N个记录进行快速排序，在最坏的情况下，其时间复杂度是O(NlogN)。

F

课本：最坏情况下，待排序记录序列正序或逆序，每次划分只得到一个比上一次划分少一个记录的子序列，另一个子序列为空。此时，必须经过n-1次递归调用才将所有记录定位，而且第i趟划分需要经过n-i次比较才能找到第i个元素的轴值位置，，因此，总的比较次数为，记录的移动次数小于等于比较次数，因此时间复杂度为。（266页快速排序）

//一次划分算法的成员函数int Sort :: Partition(int first, int last){int i = farst, j = last, temp;//初始化一次划分的区间while(i < j){while(i<j && data[i]<=data[j]) j--;//右侧扫描if(i < j){temp = data[i];data[i] = data[j];data[j] = temp;i++;}while(i<j && data[i]<=data[j]) i++;//左侧扫描if(i = last) return;//区间长度为1，递归结束else{int pivot = partition(first,last);//一次划分QuickSort(first, pivot-1);//对左侧子序列进行快速排序OuickSort(pivot+1, last);//对右侧子序列进行快速排序}}

4、作者DS课程组单位浙江大学

希尔排序是稳定的算法。

F

课本：希尔排序的时间性能在和之间。如果选定合适的增量序列，希尔排序的时间性能可以达到.希尔排序只需要一个记录的辅助空间，用于暂存当前待插入的记录。由于在希尔排序过程中记录是跳跃移动的，因此，希尔排序是不稳定的。（第261、262页）

void Sort ShellSort(){int d, i, j, temp;for(d = length/2; d >= 1; d = d/2)//增量为d进行直接插入排序{for(i = d; i =0&&temp<data[j]; j = j-d){data[j+d] = data[j];}//记录后移d个位置data[j+d] = temp;}}}

5、作者DS课程组单位临沂大学

堆排序是稳定的排序算法。（ ）

F

课本：堆排序的运行时间主要消耗在初始建堆和重建堆时进行的堆调整上，初始建堆需要时间，第i次取堆顶记录重建堆需要用时间，并且需要取n-1次堆顶记录，因此总的时间复杂度为，这是堆排序最好、最坏和平均的时间代价。堆排序对待排序序列的初始状态并不敏感，相对于快速排序，这是堆排序最大的优点。在堆排序算法中，只需要一个用来交换的暂存单元。堆排序是一种不稳定的排序方法。（第273页）

6、作者DS课程组单位临沂大学

在堆排序中，若要进行升序排序，则需要建立大根堆。（ ）

T

堆（heap）是具有下列性质的完全二叉树：每个结点的值都小于或等于其左右孩子结点的值（称为小根堆），或者每个结点的值都大于或等于其左右孩子结点的值（称为大根堆）。

从堆的定义可以看出，一个完全二叉树如果是堆，则其根结点（成为堆顶）一定是当前所有结点的最大值（大根堆）或最小值（小根堆）。

7、作者DS课程组单位临沂大学

排序算法中的比较次数与初始元素序列的排列无关。

F

课本：希尔排序的时间性能在和之间。如果选定合适的增量序列，希尔排序的时间性能可以达到.希尔排序只需要一个记录的辅助空间，用于暂存当前待插入的记录。由于在希尔排序过程中记录是跳跃移动的，因此，希尔排序是不稳定的。（第261、262页）

8、作者DS课程组单位临沂大学

排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。

F

9、作者王东单位贵州师范学院

对于n个记录的集合进行冒泡排序，在最坏情况下需要的时间是O(n2)。

T

课本：起泡排序的执行时间取决于排序的趟数。最好情况下，待排序序列为正序，算法只执行了一趟，进行了n-1次比较，不需要移动记录，时间复杂度为O(n)；最坏情况下，待排序记录序列为反序，每趟排序在无序序列中只有一个最大记录被交换到最终位置，故算法执行了n-1趟，第i趟排序执行了n-1次比较和n-1次交换，则记录的比较次数是，记录的移动次数是，因此，时间复杂度为；平均情况下，起泡排序的时间复杂度与最坏情况同数量级。起泡排序只需要一个记录的辅助空间，用来作为记录交换的暂存单元。起泡排序是一种稳定的排序方法。（263页）

void Sort :: BubbleSort(){int j, exchange, bound, temp;exchange = length - 1;//第一趟起泡排序的区间是[0 ~ length - 1]while(exchange != 0){bound = exchange;exchange = 0;for(j = 0; j  data[j+1]){temp = data[j];data[j] = data[j+1];data[j+1] = temp;exchange = j;//记载每次记录交换的位置}}}}

10、作者王东单位贵州师范学院

直接选择排序的时间复杂度为O(n2)，不受数据初始排列的影响。

T

8.2 单选题

1、对N个不同的数据采用冒泡算法进行从大到小的排序，下面哪种情况下肯定交换元素次数最多？

A.从小到大排好的

B.从大到小排好的

C.元素无序

D.元素基本有序

2、作者DS课程组

单位浙江大学

在对N个元素进行排序时，基于比较的算法中，其“最坏时间复杂度”中最好的是：

A.

O(logN)

B.

O(N)

C.

O(NlogN)

D.

O(N2)

2-3

分数1

作者DS课程组

单位浙江大学

对N个记录进行归并排序，归并趟数的数量级是：

A.

O(logN)

B.

O(N)

C.

O(NlogN)

D.

O(N2)

2-4

分数2

作者DS课程组

单位浙江大学

有组记录的排序码为{ 46，79，56，38，40，84 }，则利用堆排序的方法建立的初始堆为：

A.

79，46，56，38，40，80

B.

84，79，56，46，40，38

C.

84，56，79，40，46，38

D.

84，79，56，38，40，46

2-5

分数2

作者DS课程组

单位浙江大学

采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是：

A.

每次划分后，先处理较长的分区可以减少递归次数

B.

每次划分后，先处理较短的分区可以减少递归次数

C.

递归次数与每次划分后得到的分区处理顺序无关

D.

递归次数与初始数据的排列次序无关

2-6

分数2

作者DS课程组

单位浙江大学

有组记录的排序码为{46，79，56，38，40，84 }，采用快速排序（以位于最左位置的对象为基准而）得到的第一次划分结果为：

A.

{38,46,79,56,40,84}

B.

{38,79,56,46,40,84}

C.

{38,46,56,79,40,84}

D.

{40,38,46,56,79,84}

2-7

分数2

作者DS课程组

单位浙江大学

对于10个数的简单选择排序，最坏情况下需要交换元素的次数为：

A.

9

B.

36

C.

45

D.

100

2-8

分数2

作者陈越

单位浙江大学

将序列{ 2, 12, 16, 88, 5, 10, 34 }排序。若前2趟排序的结果如下：

• 第1趟排序后：2, 12, 16, 10, 5, 34, 88
• 第2趟排序后：2, 5, 10, 12, 16, 34, 88

则可能的排序算法是：

A.

冒泡排序

B.

归并排序

C.

快速排序

D.

插入排序

2-9

分数2

作者考研真题

单位浙江大学

对初始数据序列{ 8, 3, 9, 11, 2, 1, 4, 7, 5, 10, 6 }进行希尔排序。若第一趟排序结果为（ 1, 3, 7, 5, 2, 6, 4, 9, 11, 10, 8 ），第二趟排序结果为（ 1, 2, 6, 4, 3, 7, 5, 8, 11, 10, 9 ），则两趟排序采用的增量（间隔）依次是：

A.

3, 1

B.

3, 2

C.

5, 2

D.

5, 3

2-10

分数2

作者DS课程组

单位临沂大学

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

A.

归并排序

B.

快速排序

C.

希尔排序

D.

堆排序

2-11

分数1

作者考研真题

单位浙江大学

选择一个排序算法时，除算法的时空效率外，下列因素中，还需要考虑的是：

• I、数据的规模
• II、数据的存储方式
• III、算法的稳定性
• IV、数据的初始状态

A.

仅 III

B.

仅 I、II

C.

仅 II、III、IV

D.

I、II、III、IV

2-12

分数2

作者考研真题

单位浙江大学

排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。下列序列中，不可能是快速排序第二趟结果的是：

A.

5, 2, 16, 12, 28, 60, 32, 72

B.

2, 16, 5, 28, 12, 60, 32, 72

C.

2, 12, 16, 5, 28, 32, 72, 60

D.

5, 2, 12, 28, 16, 32, 72, 60

2-13

分数2

作者考研真题

单位浙江大学

对大部分元素已有序的数组进行排序时，直接插入排序比简单选择排序效率更高，其原因是：

• (I). 直接插入排序过程中元素之间的比较次数更少
• (II). 直接插入排序过程中所需要的辅助空间更少
• (III). 直接插入排序过程中元素的移动次数更少

A.

仅 I

B.

仅 III

C.

仅 I、II

D.

I、II 和 III

14、作者zxm单位西南石油大学

下述几种排序方法中,( )是稳定的排序方法。

A.

希尔排序

B.

快速排序

C.归并排序

D.

堆排序

上一题