第1章习题解答
1.1什么是数据结构？一个数据结构结构的二元组定义形式是什么样的？举例解释其含义。
[解答]
概括地说，数据结构是互相有关联的数据元素的集合。也就是说，数据结构是由某个数据元素的集合和该集合中的数据元素之间的关系组成的，因此数据结构可以用一个二元组来表示。例如，B=（D，R），其中D是某一数据元素的集合，R是D上的关系的有限集。R所表示的是集合D的数据元素之间的逻辑关系，它表示的可能是数据元素之间客观存在的某种联系，也可能是为了处理问题的需要而人为组织的数据元素之间的某种关系，因此，称之为数据的逻辑结构。例如，一个农历节气表，就构成了一个数据结构，其数据元素是一年的农历二十四节气，数据元素之间的关系是节气的时间先后关系。又如，一个某年级学生的成绩排序表，也是一个数据结构，其数据元素是包含成绩项的该年级的学生记录，数据元素之间的关系是学生之间的成绩高低关系。为了在计算机中进行数据处理，必须把从实际问题中抽象出来的数据的逻辑结构映象到计算机的存储器中，即要把抽象出来的数据元素集合D 和数据元素之间的关系存储到计算机的存储器中，称之为数据的物理结构或存储结构，它是数据的逻辑结构在计算机中的表示。
1.2假设R是集合M上的一个关系，R的定义是什么？对实际问题而言，其含义是什么？
[解答]
如果R是对集合M自身的笛卡尔积所取的一个子集，那么我们就说“R是集合M上的一个关系”。对实际问题而言，它表示的是集合M中元素的某种相关性。例如，对于参加一个羽毛球比赛的运动员集合，可以用一个二元关系表示出各场比赛的胜负关系。对于一组课程的集合，可以用一个二元关系表示出各门课程之间的先修和后续关系等等。
1.3设有集合M={d1,d2,d3,d4,d5}上的一个关
R={(d1,d2),(d2,d4),(d4,d5),(d2,d5),(d1,d4),(d1,d5),(d3,d5),(d1,d3)}，试说明关系R具有什么样的性质。
[解答]
从二元关系的基本性质容易验证，该关系R是反自反的、反对称的、传递的关系。
因为关系R中没有(d i,d i)这样的元素，所以它是反自反的。
因为关系R中没有(元素d i,d j)和(d j,d i)同时存在的情况，所以它是反对称的。
关系R 的传递性表现在：
有元素(d1,d2),(d2,d4)，同时有元素(d1,d4),
有元素(d1,d2),(d2,d5)，同时有元素(d1,d5),
有元素(d1,d3),(d3,d5)，同时有元素(d1,d5)，
有元素(d1,d4),(d4,d5)，同时有元素(d1,d5)，
有元素(d2,d4),(d4,d5)，同时有元素(d2,d5)。
1.4什么是线性结构？什么是非线性结构？举例说明。
[解答]
线性结构与非线性结构是针对数据的逻辑结构而言的。它们的主要区别是：线性结构表示的是数据元素之间一对一的关系，而非线性结构表示的是数据元素之间一对多或多对多的关系。线性结构具有以下特点：
①存在唯一的没有前驱、只有一个直接后继的“头”元素；
②存在唯一的没有后继、只有一个直接前驱的“尾”元素；
③除了“头”元素和“尾”元素之外，集合中的每个元素有且只有一个直接前驱、有且只有一个直接后继。
由以上特点可以看出，线性结构中的数据元素之间存在一对一的关系，结构中的数据元素依照它们的逻辑关系可以排成一个有“头”、有“尾”的序列。例如，前面所说的农历节气表，就是一个线性结构，它是一个从“春分”开始，然后是“雨水”，…，最后是“大寒”。这样一个序列。
除线性结构以外的结构称为非线性结构。在非线性结构中，各数据元素的关系不一定保持一个线性序列，每个数据元素可能与零个或多个数据元素有联系。也就是说，非线性结构中的数据元素之间存在一对多或者是多对多的关系。
例如，一个学校的教学组织关系可以构成一个有明显层次的数据结构：学校下属有若干学院，每个学院下设若干个系，每个系有多个研究所和教研组，有若干的学生班，这个一对多的关系的抽象就是非线性结构。
又如，对一个销售系统的各个连锁店及相互之间的联系的抽象是一个非线性结构，这个数据结构中的数据元素是各连锁店，数据元素之间的关系是各连锁店之间的联系，因为各连锁店之间都可以有联系，显然各连锁店之间的联系是多对多的联系。也就是说，每一个连锁店都可以与其余多个连锁店发生联系。这个结构也是非线性结构。
1.5数据的存储结构有哪几种？其中最常用的有哪几种？说明它们的特点。
[解答]
数据存储结构也称物理结构，它是数据的逻辑结构在计算机中的表示。数据的存储结构有顺序存储、链式存储、索引存储、散列存储四种方式。其中最常用的存储结构有顺序存储和链式存储两种。
在顺序存储方式中，要开辟一块连续的存储空间来存放数据结构；对每个数据元素给以等长的数据单元，结构中的数据元素按照它们之间的逻辑顺序依次存放于连续的内存单元中。顺序存储方式的特点是除了存储数据元素以外，不必耗费另外的空间，数据元素之间的关系是由数据元素在存储器中的邻接关系来表示的。由于数据元素在存储器中的物理顺序和它们之间的逻辑顺序一致，因此这种存储方式是非常直观的一种存储方式。
在链式存储方式中，数据元素可以存放在不连续的内存单元中，数据元素在存储器中的物理存放顺序可以和逻辑顺序不一致，数据元素之间的逻辑关系是通过指示数据元素存储地址的指针来表示的。因此，每个数据元素除了存储自身以外，同时还要存储指示其后件(或前件)的存储地址的指针，它们构成一个结点。也就是说，在链式存储方式中每个数据元素的存储映象是一个结点，它包括存储数据元素的数据域(也称作值域)和存储指针的指针域两部分，通过各结点的指针把各数据元素按照它们的逻辑关系链成一条“链”，从而清晰的表示了数据元素之间的逻辑关系。链式存储的明显优点是存储空间的利用比较灵活，数据元素的增减操作比较方便。
除了上述两种常用的存储方式以外，还有索引存储和散列存储方式。
在索引存储方式中，按照某种性质把一个大表的元素划分成若干个子表，使每个子表中的元素具有相同的性质。存储时以子表为单位存放，同时建立一个索引表，索引表中的每个索引项对应一个子表，指出该子表的起始地址、长度和子表的性质，这样能够给查找等操作
带来很大的方便。显然，在该存储方式下数据元素之间的逻辑关系是通过数据元素在索引表中的位置得以反映的。
在散列存储方式中，通过数据元素的关键字值来确定数据元素的存储位置，因而可以直接通过计算查找到相应的数据元素。使得它比通过“比较”查找有更高的效率。
1.6设数据元素的集合为D={a1,a2,a3,a4,a5,a6}，请分别画出与以下各关系R对应
的数据结构B=(D,R)的结构示意图，并指出它属于哪类结构。
(1)R={(a3,a4),(a4,a5),(a1,a2),(a2,a3),(a5,a6)}
(2)R={(a3,a2),(a2,a4),(a3,a1),(a2,a5),(a2,a6)}
(3)R={(a i+1,a i)︱i=5,4,3,2,1}
(4)R={(a i,a j)︱i>j}
(5)R={ }
[解答]
(1)为线性结构，其图形表示如图1-1 (a) 所示。
(2)为非线性结构，其图形表示如图1-1 (b) 所示。
(3)为线性结构，其图形表示如图1-1(c) 所示。
(4)非线性结构，其图形表示如图1-1(d) 所示。
(5)集合结构，除了同属一个集合外，数据元素间无其他关系。
(a) (c)
(b) (d)
图 1-1
1.7什么是抽象数据类型？抽象数据类型和面向对象的程序设计方法有什么关系？
[解答]
抽象数据类型是指用以表示应用问题的一个数据模型以及定义在该模型上的一组操作。它与一般的数据类型的概念在本质上是一致的，都是对数据类型的数学特性的抽象，其目的是可以使程序设计者，在程序设计中更专注于数据的逻辑特性，而不必关心抽象数据类型实现的具体细节。但抽象数据类型比一般数据类型的抽象层次更高、范畴更广，它不局限于计算机系统中已定义和实现的数据类型，通常它是由用户根据实际问题的需要而定义，且通过计算机系统中已经定义的数据类型来表示和实现。因此，它是基于一般数据类型的更高层次上的一种数据抽象。
抽象数据类型的概念是由于程序设计方法和技术的发展而提出来的。为了更好的提高软件模块的可复用性和可扩充性，现代程序设计方法强调以数据为基础来构建软件系统，更加
强调“封装”和“信息隐蔽”策略。面向对象的程序设计方法正是符合这种要求的方法。“类”是面向对象的程序设计方法中的核心概念，它是数据抽象的结果，类不但体现了封装和信息隐蔽的原则，而且具有继承性，因而为模块的复用提供了很好的条件。抽象数据类型具有封装和信息隐蔽的特点，可以做到使用与实现分离。由此可见，抽象数据类型与面向对象的方法的思想是一致的，从抽象数据类型出发来进行面向对象的程序设计，会使程序设计更加顺理成章。
1.8 完成以下问题：
(1) 设计二次多项式ax2+bx+c的一种抽象数据类型，其数据部分为多项式的三个系数项a、b、c；操作部分包括：初始化数据成员a、b、c，实现两个多项式相加，给定x求多项式的值，求方程ax2+bx+c=0的两个实根，按照ax**2+bx+c的格式输出二次多项式。
(2) 假定数据成员a、b、c定义如下：
typedef struct
{ float a,b,c ;
}Quadratic ;
请写出上述各操作的具体实现。
[解答]
(1) 对题中的二次多项式抽象数据类型可以作以下定义：
ADT Quadratic
{数据：
一元二次多项式的二次项系数a，一次项系数b，常数项c；其结构类型为：Quadratic 操作：
// 初始化一元二次多项式
Quadratic *InitQuadratic (flaot aa, float bb, float cc) ；
Quadratic *Add (Quadratic *f1, Quadratic *f2 ) ；// 两个多项式相加
float Value (Quadratic *f, float x)；// 计算一元二次多项式的值
int Root (quadratic *f, float& r1, float& r2)；// 求一元二次方程的两个实根
void print (Quadratic *f)；// 按指定格式输出多项式
}
(2) 数据成员定义和指定的操作的实现如下：
数据成员定义：
typedef struct
{ float a, b, c ；
} Quadratic；
数据成员初始化：
Quadratic *InitQuadratic (flaot aa, float bb, float cc )
{ Quadratic *f ；
f->a=aa；f->b=bb；f->c=cc ；
return f ；
}
两个二次多项式相加：
Quadratic *Add ( Quadratic *f1, Quadratic *f2 )
{ Quadratic *f ；
f->a=f1->a + f2->a ；
f->b=f1->b + f2->b ；
f->c=f1->c + f2->c ；
return f ；
}
由给定的x，求二次多项式的值：
float Value (Quadratic *f, float x )
{ return (f->a*x*x+f->b*x+f->c ) ；
}
求一元二次方程的实根：
int Root (quadratic f, float *r1, float *r2 )
{float d ;
if (f->a==0) return –1 ；
d=f->b*f->b-4*f->a*f->c ；
if (d>=0)
{ r1=(-f->b+sqrt(d))/(2*f->a) ；
r2=(-f->b-sqrt(d))/(2*f->a) ；
return 1 ；
}
else return 0 ；
}
按照要求的形式输出二次多项式：
void print (Quadratic *f )
{ if (f.a) printf (〞%f x**2〞, f.a ) ；
if (f.b )
{ if (f.b>0 ) printf (〞+%f x 〞, f.b ) ；
else printf (〞%f x 〞, f.b ) ；
}
if (f.c )
{ if (f.c>0 ) printf (〞+%f 〞, f.c ) ；
else printf (〞%f 〞, f.c ) ；
}
printf (〞\n ) ；
}
1.9 算法的基本特征是什么？算法分析主要针对哪些方面？[解答]
算法是解决问题方案的准确而完整的描述。它是为解决某一特定问题而确定的一个指令序列。算法具有以下的特性：
(1) 有穷性。一个算法必须在执行有穷步之后结束，而且每一步都应该能够在有限时间内完成。
(2) 确定性。算法中的每一步含义都必须是确切的、无歧义的。并且在任何情况下算法只有一条唯一的执行路径。
(3) 可执行性。算法中描述的运算都应该能够准确的执行。
(4) 有输入。一个算法应该有0个或多个取自于特定对象的集合的输入。
(5) 有输出。一个算法应该有0个或多个经算法计算得到输出。
对同一个问题可以设计出不同的算法，各个算法特点不同，性能也会不一样，因而对一个算法需要进行性能的分析。对算法的性能分析包括算法的正确性、可读性、健壮性、执行效率等方面，但通常对算法的分析主要是针对算法的执行效率进行分析，即对算法执行时的时间和空间代价进行分析比较，也就是分析算法的时间复杂度和空间复杂度。
1.10 分治法与减治法的思路有什么相同之处？又有什么不同？
[解答]
分治法和减治法的共同之处是，它们都是在“分而治之”思想的指导下发展起来的，基本思路就是把一个规模较大的问题划分为若干个规模较小的子问题，通过对子问题的求解，得到原问题的解。
但分治法和减治法又各自适用于不同的情况，因此它们的求解过程有所不同。用分治法求解的问题，所划分的子问题是互相独立的，且原问题的解需要由各子问题的解合并而成。因此，需要对各子问题分别求解，并合并子问题的解，才能得到原问题的解。可以用减治法求解的问题，虽然也要对原问题进行划分，但因为原问题的或者解只在其中一个子问题中，或者是只与其中的一个子问题的解之间有着某种对应关系，因此只要对相关的一个子问题进行求解，就可以得到原问题的解。当然它也就不存在合并解的过程。可以说，减治法是一种退化了的分治法。
1.11 简述回溯法的基本思想，采用这种算法的关键是什么？
[解答]
回溯法是一种有组织的系统化搜索问题解的技术，它是对穷举搜索的改进，其采用的是“向前走，碰壁回头”思想。具体的说，首先要对问题进行分析，确定问题的所有可能解，即确定问题的解空间，然后沿着所确定的路线搜索向前搜索。在搜索过程中，对每一步得到的部分解进行判断，如果该部分解有可能构成一个完整解，说明这一步走得通，则继续向前走，也就是进一步构造问题解。否则，说明“此路不同”，则需要回退，找另一条路线再搜索，也就是回溯，从新的路线上继续构造问题的解。
由回溯法的求解过程可以看出，采用回溯法的关键是确定正确的解空间，即确定解的搜索范围，并确定搜索的路线，只有做到这两步，才可能有效地对问题解进行搜索。
例如，“给定一个正整数集合X={ x1, x2, …, x n }和一个正整数y，求集合X的一个子集Y，使得Y中的元素之和等于y。”，这个问题可以采用回溯法来求解。其求解思路是：从X集合中依次选取各元素并将其与Y中的元素相加，考察相加结果。具体做法是：·初始子集Y为空，其元素和等于0；
·选取x1，将其与子集Y的元素和相加，检查结果:
若相加结果大于y，则放弃当前所选x i ：
若X中还有后续元素，继续选取x i+1再试；
否则，回溯：放弃x i之前一个选中的元素，继续向后选取；
若相加结果小于y，做Y=Y+x i，继续向后选取x i+1再试；
若相加结果等于y，输出Y中的元素。
由于这个问题的解空间比较明确（求X的子集），因此，实现这个回溯算法的关键，是确定求满足条件的子集的思路确定对当前项x i取或舍的准则。即，确定对x1, x2, …, x n求和的顺序以及判断当前和是否满足条件的准则。确定了这两个条件，这个回溯算法的搜索路线也就确定了。算法思路也就明确了。
1.12 简述贪心法和动态规划法思路的异同。
[解答]
贪心法和动态规划法都是用于解决多阶段决策的最优化问题。基本的求解思路，都是把一个复杂的问题分解为若干子问题，通过对子问题求解的一系列的决策或选择，最后得到原问题的解。
但是，两者的决策方法不相同。贪心法总是把原问题分解为一系列较为简单的局部最优选择，每一步选择都是在当前状态下做出的最优选择，同时扩展了当前的部分解，直到求得问题的完整解。这个贪心选择过程是以自顶向下的方式进行的，即从原问题出发，每做一步贪心选择都把问题简化为规模更小的子问题，直到对规模最小的子问题做出贪心选择。动态规划法中，分解成的子问题具有两个特点。其一，子问题之间往往不是互相独立的，而是有重叠的部分，这种重叠关系通过动态规划函数表现出来，为了避免对重叠部分的重复计算，以表格形式保存每一步对子问题的求解结果，当需要再次求解已经解决的子问题时，只要做简单的查表操作即可。其二，每个子问题对应决策过程的一个阶段，每步所做的决策往往依赖于相关子问题的解，因此，只有在解决了相关的子问题之后，才能做出决策或选择。正因为此，其求解子问题时，通常以自底向上的方式进行，即从求解最后分解得到的子问题开始，逐层向前，最后求得原问题的解。
1.13 什么是算法的渐近时间复杂度？如何分析一个算法的渐近时间复杂度？
[解答]
算法的渐近时间复杂度是对算法的时间效率的度量。也就是对一个算法执行所需要的时间进行分析。一个算法执行所需要的具体时间与所使用的计算机系统的软、硬件性能及问题的规模等因素有关。为了比较算法本身的时间性能，应该采用能够反映算法本身的时间性能的度量。实际上，通常算法运行所需要的时间T是问题规模n的函数，可记为T(n)。所谓算法的渐近时间复杂度，是当问题规模充分大时，算法运行时间的增长趋势的度量。因为增长率的上限对算法的比较更具意义，所以经常分析的是算法运行时间的增长率的上限，这就是算法的时间复杂度的大O表示，也常简称为算法的时间复杂度。
为了分析一个算法的时间复杂度，一般情况下需要考察算法中基本语句的执行次数，找出其与问题规模n的函数关系f(n)，从而得到算法的渐近时间复杂度。所谓基本语句是执行次数与算法的执行次数成正比的语句，它是算法中的关键操作。算法的基本语句大多包含在循环和递归结构中，对于单循环结构，循环体中的简单语句就是基本语句，其执行次数的大O表示就是该算法段的渐近时间复杂度；对于并列的循环结构，要先分析各个循环结构的渐近时间复杂度，然后利用大O表示法的加法规则求出算法的时间复杂度；对于多层嵌套的循环结构，最内层循环中的简单语句就是算法的基本语句，要自外向内逐层分析各层循环的渐近时间复杂度，再利用大O表示法的乘法规则来求出算法的渐近时间复杂度。对于递归结构，则可以根据递归过程递推出基本语句的执行次数，进而得到它的大O表示。总之，
只要分析求出算法中关键操作的执行次数与问题规模的函数关系，也就得到了该次数的大O 表示，从而也就求出了算法的渐近时间复杂度。
1.14 什么是算法的渐近空间复杂度？如何分析一个算法的渐近空间复杂度？
[解答]
算法的渐近空间复杂度是对算法的空间效率的度量。也就是对一个算法执行所需要的存储空间进行分析。一个算法执行时所需要的空间包括几个方面，如存储程序指令所需要的空间，存储输入数据的空间等。与分析算法的时间复杂度类似，为了能够反映一个算法的空间性能，要排除与算法性能无关的存储空间需求，仅考虑算法执行时所需要的辅助存储空间,因为它直接与算法的空间性能有关。一个算法执行时所需要的辅助存储空间量也可以表示为问题规模n的函数，其大O表示称之为算法的渐近时间复杂度。也简称为算法的空间复杂度。
根据上述概念，分析算法的渐近空间复杂度就是要考察和分析算法执行时所需要的临时工作单元、动态使用的空间、递归工作栈所占空间等辅助空间的需求量，然后将其表示为问题规模的函数，也就是用大O表示法表示它，即可得到算法的渐近空间复杂度。
1.15 给以下程序加上必要的注释，指出其功能，并分析时间复杂度和空间复杂度。［解答］
(1)int sum (int n )
{ int i, j, p, s=0 ；//s存放n! 的累加和
for (i=1；i<=n；i++)
{ p=1；
for ( j=1；j<=i；j++) p* = j ；// p存放n!
s+=p；
}
return s；
}
功能：求n! 的累加和。
算法的时间复杂度：该算法中反映其执行时间的操作是内循环中的求阶乘语句，其执行次数为：1+2+ … +n =n(n+1)/2 ，算法的时间复杂度为：O(n2)。
算法的空间复杂度：原地工作，即O(1)。
(2) int fac ( int n )
{ int i, p=1, s= 0；
for ( i=1；i<=n；i++)
{ p*= i ；// 求n!
s+= p ；// s 存放n! 的累加和
}
return s ；
}
功能：n! 的累加和
算法的时间复杂度：循环中的求阶乘及其累加和语句的执行次数为n，算法的时间复杂度为O(n)。
算法的空间复杂度：原地工作，即O(1)。
(3) void writ ( int n )
{ if (n!= 0 )
{ writ (n-1) ；// n层递归，从1开始执行n次输出printf (〞%d \n〞, n ) ；
}
return ；
}
功能：采用递归，依次输出自然数1到n
算法的时间复杂度：n层递归执行n次输出，算法的时间复杂度为O(n)。
算法的空间复杂度：由递归栈的深度决定，递归栈深度为n，所以算法的空间复杂度为O(n) 。
(4) void Order ( float a[], int k, int m )
{ int i ;
flaot temp ;
if ( k { for ( i=k；i<=m；i++ )// 选出a中k到m的最小元素，放于k位置if ( a[i]< a[k] ) { temp=a[i] ； a[i]= a[k] ； a[k]= temp ； } k++ ；// k指向下一个位置 order (a, k, m )；// 执行递归，对剩余元素选出最小的放于k位置 } } 功能：采用递归，对数组a中k到m的元素做“冒泡”排序。 算法的时间复杂度：设排序的时间为T(n)，则有： T(n)=T(n-1)+n-1=T(n-2)+n-2+n-1= …=T(1)+1+2+ …+n-1= n(n-1)/2，其中T(1)=0算法的时间复杂度为O(n2) 。 算法的空间复杂度：决定于递归栈的深度，递归栈的深度为m-k，所以该算法空间复杂度为O(m-k) 。 (5) void Bubb_Sort (float a[], int n) { flaot temp ； int i, j, flag ；// fiag标志本趟扫描是否有交换发生， // 并记录最后一次发生的位置 flag = n-1 ； while ( f lag>0 ) // 有交换发生，继续做 { j =flag-1; flag= 0 ； for ( i=0; i<=j; i++ ) // 实现一趟扫描 if (a[i] > a[i+1]) { temp= a[i]；a[i]= a[i+1]；// 使相邻元素正序 a[i+1]= temp ； flag= i ； } } } 功能：对数组a中的元素a[0]到a[n-1]做冒泡排序。 算法的时间复杂度： 最好情况下，数组a中的元素全部为正序，只需一趟扫描，做n-1次比较，没有交换发生。其时间复杂度为O(n)； 最坏情况下，数组a中的元素全部为逆序，需要n-1趟扫描，共经过 (n-1)+(n-2)+…+2+1次比较—交换操作，其时间复杂度为O(n2)； 平均情况下，比较—交换操作的次数约为最坏情况的一半，其时间复杂度为O(n2)。 算法的空间复杂度：原地工作，即O(1)。 上机练习思路提示 1.1 采用两种不同的算法，找出数组a[n](n=2k, k≥1)中的最大元素，说明两种算法所采用的设计方法及其特点。 ［参考算法］： 本题可以采用多种方法来解决，以下给出几种不同的求解算法。 ①采用一趟选择,选出最大元素: ElemType Select_max1 (ElemType a[], int n ) { int i, max= 0 ；// max记录最大元素所在的下标，初始取第1个元素位置 for ( i=1；i return ( a[max] ) ；// 返回最大元素值 } 该算法对全部数组元素进行一遍扫描，比较n-1次，只需做一次交换，数据移动次数少。 ②采用一趟冒泡,得到最大元素: ElemType Select_max2 (ElemType a[], int n ) { int i ; for (i=0；i { if (a[i]> a[i+1] ) { int temp=a[i] ； a[i]=a[i+1] ； a[i+1]=temp ； } } return ( a[n-1] ) ；// a[n-1]是数组中最大元素 } 该算法对全部数组元素进行一遍扫描，比较n-1次，最坏情况下可能需要做n-1元素的交换，数据移动次数可能较算法①多。 ③采用递归方法,找出最大值: ElemType Select_max3 ( ElemType a[], int low, int high ) // 查找数组元素a[low]到a[high]的最大元素，返回其下标 { int mid ; ElemType j, k ; if ((high-low) ==1) // 若该段只有两个元素，返回大者的值 { if (a[low]< a[high]) return ( a[high] ) ； else return ( a[low] ) ； } else // 如果该段多于两个元素，将其对后分别找出两部分的最大值，再返回其中的大者 { mid= (low+high)/2 ；// 将当前要查找的元素段对分为两部分 j= Select_max3 ( a, low, mid ) ；// 找出前一部分的最大元素的值 k=Select_max3 (a, mid+1, high ) ；// 找出后一部分的最大元素的值 if ( j >k ) return j ；// 比较两部分的最大元素值，返回大者 else return k ； } } 该算法思路简洁，数据比较次数为：n/2 + n/4 + n/8 + … + 1= n-1；因为是递归算法，它需要一个递归栈，栈的深度为log2n 。 1.2 有一个早晨7点到晚上 11点营业的连锁店，叫7-11店。一次，一位顾客在该店选了4样东西，付款时，营业员计算后说：“总共是7.11元。”顾客开玩笑说：“哦？难道因为你们是7-11店，所以我就要付7.11元吗？”营业员没有听出是在开玩笑，便回答说：“当然不是，我是把4样东西的价格相乘才得出结果的！”顾客非常吃惊，说：“你怎么把它们相乘呢？，应该把它们相加才对！”营业员听后，忙说：“噢，对不起，我今天头非常疼，所以按错计算器的键了。”并赶紧把4样东西的价格相加重算了一遍，但结果令两个人都十分惊讶：总和还是7.11元。请设计一个算法计算这四样东西的价格各是多少？ [参考算法]： 该问题可以采用穷举法求解，算法描述如下: void Price () { int a, b, c, d ; for (a=1；a<=708；a++) // a,b,c,d分别代表顾客所购的四件物品的价格 for (b=1；b<=708；b++) // 每件物品的价格不会超过7.08元 for (c=1；c<=708；c++) { d=711-a-b-c ； if ((a*b*c*d)/1e08==(a+b+c+d)/100.0) // 输出满足条件的解 {printf (〞a=%f , b=%f, c=%f, d=%f\n〞, a/100.0, b/100.0, c/100.0, d/100.0 )； exit (0) ；// 找到一组解，程序退出执行 } } } 需要注意所用系统的整型数据的上界，否则需用长整形数据类型。 Chap1 一、选择题 1.算法的计算量的大小称为计算的（）。 A．效率 B.复杂性 C.现实性 D.难度 2.计算机算法指的是（1），它必须具备（2）这三个特性。 (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．在下面的程序段中，对x的赋值语句的频度为（） FOR i:=1TO n DO FOR j:=1TO n DO x:=x+1; n) A．O(2n)B．O(n)C．O(n2)D．O(log 2 7．程序段FOR i:=n-1DOWNTO1DO FOR j:=1TO i DO IF A[j]>A[j+1] THEN A[j]与A[j+1]对换； 其中n为正整数，则最后一行的语句频度在最坏情况下是（）。 A.O（n） B.O(nlogn) C.O(n3) D.O(n2) 8．以下哪个数据结构不是多型数据类型（） A．栈B．广义表C．有向图D．字符串 9．以下数据结构中，（）是非线性数据结构 A．树B．字符串C．队D．栈 二、判断题 1．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。() 2．算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。() 3．程序一定是算法。() 4．数据的物理结构是指数据在计算机内的实际存储形式。() 5.数据结构的抽象操作的定义与具体实现有关。() 6.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。() 栈和队列的共同特点是__________________________ .栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中，增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是 __________________________ 13.树是结点的集合，它的根结点数目是_____________________ 14.在深度为5的满二叉树中，叶子结点的个数为_______________ 15.具有3个结点的二叉树有（_____________________ 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是 ____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中，算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________ 第一章习题 一、问答题 1.什么是数据结构？ 2.叙述四类基本数据结构的名称与含义。 3.叙述算法的定义与特性。 4.叙述算法的时间复杂度。 5.叙述数据类型的概念。 6.叙述线性结构与非线性结构的差别。 7.叙述面向对象程序设计语言的特点。 8.在面向对象程序设计中，类的作用是什么？ 9.叙述参数传递的主要方式及特点。 10.叙述抽象数据类型的概念。 二、判断题（在各题后填写“√”或“×”） 1.线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。（） 2.算法就是程序。（） 3.在高级语言（如C或 PASCAL）中，指针类型是原子类型。（） 三、计算下列程序段中X=X+1的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 四、试编写算法，求一元多项式P n (x)=a +a 1 x+a 2 x2+a 3 x3+…a n x n的值P n (x )，并确定算法中的每 一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用 求幂函数。注意：本题中的输入a i (i=0,1,…,n),x和n，输出为P n (x )。通常算法的输入和输 出可采用下列两种方式之一： （1）通过参数表中的参数显式传递。 （2）通过全局变量隐式传递。 试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。 实习题 设计实现抽象数据类型“有理数”。基本操作包括有理数的加法、减法、乘法、除法，以及求有理数的分子、分母。 第一章答案 1.3计算下列程序中x=x+1的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 【解答】x=x+1的语句频度为： T(n)=1+(1+2)+（1+2+3）+……+（1+2+……+n）=n(n+1)(n+2)/6 1.4试编写算法，求p n(x)=a0+a1x+a2x2+…….+a n x n的值p n(x0),并确定算法中每一语句的执 行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入为a i(i=0,1,…n)、x和n,输出为P n(x0)。算法的输入和输出采用下列方法（1）通过参数表中的参数显式传递（2）通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。 【解答】 （1）通过参数表中的参数显式传递 优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。 缺点：形参须与实参对应，且返回值数量有限。 （2）通过全局变量隐式传递 优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗 数据结构模拟卷(含答案)经典习题 练习题 一、单项选择题 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. 若将数据结构形式定义为二元组(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 《数据结构》第一章练习题 1、单项选择题 1.1数据结构是一门非数值计算的程序设计问题中计算机的（ ）以及它们之间的（ ）和运算等的学科。 ①A 数据元素 B 计算方法 C 逻辑存储 D 数据映像 ②A 结构 B 关系 C 运算 D 算法 1.2数据结构被形式的定义为（K,R ），其中K 是（ ）的有限集，R 是K 上的（ ）有限集。 ①A 算法B 数据元素C 数据操作D 逻辑结构 ②A 操作B 映像C 存储D 关系 1.3在数据结构中，从逻辑上可以把数据结构分为（ ）。 A 动态结构和静态结构 B 紧凑结构和非紧凑结构 C 线性结构和非线性结构 D 内部结构和外部结构 1.4数据结构在计算机内存中的表示是指（ ）。 A 数据的存储结构 B 数据结构 C 数据的逻辑结构 D 数据元素之间的关系 1.5在数据结构中，与所使用的计算机无关的是数据的（ ）结构。 A 逻辑 B 存储 C 逻辑和存储 D 物理 1.6算法分析的目的是（)，算法分析的两个主要方面是（ ）。①A 找出数据结构的合理性 B 研究算法中输入与输出的关系 C 分析算法效率以求改进 D 分析算法的易懂性和文档性 ②A 空间复杂度和时间复杂度 B 正确性和简明性 C 可读性和文档性 D 数据复杂性和程序复杂性 1.7计算机算法是指（ ），它必须具备输入、输出和（ ）等5个特性。 ①A 计算方法 B 排序方法 C 解决问题的有限运算序列 D 调度方法 ②A 可行性、可移植性和可扩充性 B 可行性、确定性和有穷性 C 确定性、有穷性和稳定性 D 易读性、稳定性和安全性 1.8在以下的叙述中，正确的是（ ）。 A 线性表和线性存储结构优于链表存储结构 B 二维数组是其数据元素为线性表的线性表 C 栈的操作方式是先进先出 D 队列的操作方式是先进后出 1.9在决定选择何种存储结构时，一般不考虑（ ）。 、管路敷设技术通过管线不仅可以解决吊顶层配置不规范高中资料试卷问题，而且可保障各类管路习题到位。在管路敷设过程中，要加强看护关于管路高中资料试卷连接管口处理高中资料试卷弯扁度固定盒位置保护层防腐跨接地线弯曲半径标等，要求技术交底。管线敷设技术中包含线槽、管架等多项方式，为解决高中语文电气课件中管壁薄、接口不严等问题，合理利用管线敷设技术。线缆敷设原则：在分线盒处，当不同电压回路交叉时，应采用金属隔板进行隔开处理；同一线槽内强电回路须同时切断习题电源，线缆敷设完毕，要进行检查和检测处理。、电气课件中调试对全部高中资料试卷电气设备，在安装过程中以及安装结束后进行 高中资料试卷调整试验；通电检查所有设备高中资料试卷相互作用与相互关系，根据生产工艺高中资料试卷要求，对电气设备进行空载与带负荷下高中资料试卷调控试验；对设备进行调整使其在正常工况下与过度工作下都可以正常工作；对于继电保护进行整核对定值，审核与校对图纸，编写复杂设备与装置高中资料试卷调试方案，编写重要设备高中资料试卷试验方案以及系统启动方案；对整套启动过程中高中资料试卷电气设备进行调试工作并且进行过关运行高中资料试卷技术指导。对于调试过程中高中资料试卷技术问题，作为调试人员，需要在事前掌握图纸资料、设备制造厂家出具高中资料试卷试验报告与相关技术资料，并且了解现场设备高中资料试卷布置情况与有关高中资料试卷电气系统接线等情况 ，然后根据规范与规程规定，制定设备调试高中资料试卷方案。 、电气设备调试高中资料试卷技术电力保护装置调试技术，电力保护高中资料试卷配置技术是指机组在进行继电保护高中资料试卷总体配置时，需要在最大限度内来确保机组高中资料试卷安全，并且尽可能地缩小故障高中资料试卷破坏范围，或者对某些异常高中资料试卷工况进行自动处理，尤其要避免错误高中资料试卷保护装置动作，并且拒绝动作，来避免不必要高中资料试卷突然停机。因此，电力高中资料试卷保护装置调试技术，要求电力保护装置做到准确灵活。对于差动保护装置高中资料试卷调试技术是指发电机一变压器组在发生内部故障时，需要进行外部电源高中资料试卷切除从而采用高中资料试卷主要保护装置。 数据结构上机实验题目 实验一线性表的顺序存储结构 实验学时 2学时 背景知识:顺序表的插入、删除及应用。 目的要求： 1．掌握顺序存储结构的特点。 2．掌握顺序存储结构的常见算法。 实验容 1．输入一组整型元素序列，建立顺序表。 2．实现该顺序表的遍历。 3．在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。4．判断该顺序表中元素是否对称,对称返回1,否则返回0。 5．实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。 6．输入整型元素序列利用有序表插入算法建立一个有序表。 7．利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。 8. 利用该顺序结构实现循环队列的入队、出队操作。 8．编写一个主函数,调试上述算法。 #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 《数据结构与算法设计》习题册 第一章绪论 一、单项选择题 1.数据结构是一门研究非数值计算的程序设计问题中计算机的①以及它们之间的②和运 算等的学科。 ①A. 数据元素 B. 计算方法 C. 逻辑存储 D. 数据映象 ②A. 结构 B. 关系 C. 运算 D. 算法 2.数据结构被形式地定义为（K，R），其中K是①的有限集，R是K上的②有限集。 ①A. 算法 B. 数据元素 C. 逻辑结构 D. 数据操作 ②A. 操作 B. 存储 C. 映象 D. 关系 3.在数据结构中，从逻辑上可以把数据结构分成。 A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D. 内部结构和外部结构 4.数据结构在计算机内存中的表示是指。 A. 数据的存储结构 B. 数据结构 C. 数据的逻辑结构 D. 数据元素之间的关系 5.在数据结构中，与所使用的计算机无关的是数据的结构。 A. 逻辑 B. 存储 C. 逻辑和存储 D. 物理 6.算法分析的目的是①，算法分析的两个主要方面是②。 ①A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 ②A. 空间复杂度和时间复杂度 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 7.计算机算法指的是①，它必须具备输入、输出和②等5个特性。 ①A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ②A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 8.在以下叙述中，正确的是。 A. 线性表的线性存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C. 栈的操作方式是先进先出 D. 队列的操作方式是先进后出 9.在决定选取何种存储结构时，一般不考虑。 A. 各结点的值如何 B. 结点个数的多少 C. 对数据有哪些运算 D. 所用编程语言实现这种结构是否方便 10.在存储数据时，通常不仅要存储各数据元素的值，而且还要存储。 《数据结构》课程设计题目 (程序实现采用C语言) 题目1：猴子选王（学时：3） 一堆猴子都有编号，编号是1，2，3 ...m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 要求：m及n要求从键盘输入，存储方式采用向量及链表两种方式实现该问题求解。 //链表 #include { 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.1什么是数据结构？一个数据结构结构的二元组定义形式是什么样的？举例解释其含义。 [解答] 概括地说，数据结构是互相有关联的数据元素的集合。也就是说，数据结构是由某个数据元素的集合和该集合中的数据元素之间的关系组成的，因此数据结构可以用一个二元组来表示。例如，B=（D，R），其中D是某一数据元素的集合，R是D上的关系的有限集。R所表示的是集合D的数据元素之间的逻辑关系，它表示的可能是数据元素之间客观存在的某种联系，也可能是为了处理问题的需要而人为组织的数据元素之间的某种关系，因此，称之为数据的逻辑结构。例如，一个农历节气表，就构成了一个数据结构，其数据元素是一年的农历二十四节气，数据元素之间的关系是节气的时间先后关系。又如，一个某年级学生的成绩排序表，也是一个数据结构，其数据元素是包含成绩项的该年级的学生记录，数据元素之间的关系是学生之间的成绩高低关系。为了在计算机中进行数据处理，必须把从实际问题中抽象出来的数据的逻辑结构映象到计算机的存储器中，即要把抽象出来的数据元素集合D 和数据元素之间的关系存储到计算机的存储器中，称之为数据的物理结构或存储结构，它是数据的逻辑结构在计算机中的表示。 1.2假设R是集合M上的一个关系，R的定义是什么？对实际问题而言，其含义是什么？ [解答] 如果R是对集合M自身的笛卡尔积所取的一个子集，那么我们就说“R是集合M上的一个关系”。对实际问题而言，它表示的是集合M中元素的某种相关性。例如，对于参加一个羽毛球比赛的运动员集合，可以用一个二元关系表示出各场比赛的胜负关系。对于一组课程的集合，可以用一个二元关系表示出各门课程之间的先修和后续关系等等。 1.3设有集合M={d1,d2,d3,d4,d5}上的一个关 R={(d1,d2),(d2,d4),(d4,d5),(d2,d5),(d1,d4),(d1,d5),(d3,d5),(d1,d3)}，试说明关系R具有什么样的性质。 [解答] 从二元关系的基本性质容易验证，该关系R是反自反的、反对称的、传递的关系。 因为关系R中没有(d i,d i)这样的元素，所以它是反自反的。 因为关系R中没有(元素d i,d j)和(d j,d i)同时存在的情况，所以它是反对称的。 关系R 的传递性表现在： 有元素(d1,d2),(d2,d4)，同时有元素(d1,d4), 有元素(d1,d2),(d2,d5)，同时有元素(d1,d5), 有元素(d1,d3),(d3,d5)，同时有元素(d1,d5)， 有元素(d1,d4),(d4,d5)，同时有元素(d1,d5)， 有元素(d2,d4),(d4,d5)，同时有元素(d2,d5)。 1.4什么是线性结构？什么是非线性结构？举例说明。 [解答] 数据结构经典例题 1.设计一个算法将L拆分成两个带头节点的单链表L1和L2。 void split(LinkList *&L,LinkList *&L1,LinkList *&L2) { LinkList *p=L->next,*q,*r1; //p指向第1个数据节点 L1=L; //L1利用原来L的头节点 r1=L1; //r1始终指向L1的尾节点 L2=(LinkList *)malloc(sizeof(LinkList));//创建L2的头节点 L2->next=NULL; //置L2的指针域为NULL while (p!=NULL) { r1->next=p; //采用尾插法将*p(data值为ai)插入L1中 r1=p; p=p->next; //p移向下一个节点(data值为bi) q=p->next; //由于头插法修改p的next域,故用q保存*p的后继节点 p->next=L2->next; //采用头插法将*p插入L2中 L2->next=p; p=q; //p重新指向ai+1的节点 } r1->next=NULL; //尾节点next置空 } 2.查找链表中倒数第k个位置上的节点（k为正整数）。若查找成功，算法输出该节点的data域的值，并返回1；否则，只返回0。 typedef struct LNode {int data; struct LNode *link; } *LinkList; int Searchk(LinkList list,int k) { LinkList p,q; int count=0; p=q=list->link; while (p!=NULL) { if (count 第一章概论 一、填空题 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。 2. 数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的关系有限集合。 3. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。 4. 数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。 5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 6．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。 7. 在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点数可以任意多个。 8. 在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。 9．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散列。 10. 数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。 11. 一个算法的效率可分为时间效率和空间效率。 二、单项选择题 （B）1. 非线性结构是数据元素之间存在一种： A）一对多关系 B）多对多关系 C）多对一关系 D）一对一关系 （ C ）2. 数据结构中，与所使用的计算机无关的是数据的 结构； A) 存储 B) 物理 C) 逻辑 D ) 物理和存储 （C）3. 算法分析的目的是： A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性 （A）4. 算法分析的两个主要方面是： A) 空间复杂性和时间复杂性 B) 正确性和简明性 C) 可读性和文档性 D) 数据复杂性和程序复杂性 （ C ）5. 计算机算法指的是： A) 计算方法 B) 排序方法 基本概念典型例题 一、单项选择题 [例6-1]数据结构用集合的观点可以表示为一个二元组DS＝(D，R)。其中，D是( ①)的有穷集合，R是D上( ②)的有限集合。 ①A.算法B. 数据元素C. 数据操作D. 逻辑结构 ②A. 操作B. 映像C. 存储D．关系 解析：由数据结构的集合形式化定义可知，本题答案为：①B；②D。 [例6-2]数据的常用存储结构中不包括( )。 A．顺序存储结构B．线性结构C．索引存储结构D．散列存储结构 解析：数据通常有四种基本的存储方法，即顺序存储方法、链式存储方法、索引存储 方法和散列存储方法。由此可知，本题答案为：B。 [例6-3] 算法指的是( ①)，它必须具备( ②)这三个特性。 ①A．计算方法B．排序方法C．解决问题的步骤序列D．调度方法 ②A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性 C．确定性、有穷性、稳定性D．易读性、稳定性、安全性 解析：算法是对特定问题求解步骤的一种描述，是由若于条指令组成的有限序列。它 必须满足以下性质：输人性、输出性、有穷性、确定性、无二义性和可行性。由此可知，本 题答案为：①㈠②B。 [例6-4] 在下面的程序段中，对x的赋值语句的执行频度为( )。 for(i=0；i 数据结构第一章绪论习题 一、【单选题】 1. （A）是数据的基本单位。 Ａ、数据元素Ｂ、数据对象Ｃ、数据项Ｄ、数据结构 2. （C）是数据的不可分割的最小单位。 Ａ、数据元素Ｂ、数据对象Ｃ、数据项Ｄ、数据结构 3. 若采用非顺序映象，则数据元素在内存中占用的存储空间（C）。 Ａ、一定连续Ｂ、一定不连续Ｃ、可连续可不连续 4. 若采用顺序映象，则数据元素在内存中占用的存储空间（A）。 Ａ、一定连续Ｂ、一定不连续Ｃ、可连续可不连续 5. 在数据结构中，从逻辑上可以把数据结构分为（C） Ａ、动态结构和静态结构Ｂ、紧凑结构和非紧凑结构Ｃ、线性结构和非线性结构Ｄ、内部结构和外部结构 6. 在树形结构中，数据元素间存在（B）的关系。 Ａ、一对一Ｂ、一对多Ｃ、多对多Ｄ、除同属一个集合外别无关系 7. 下列说法中错误的是（B）。 Ａ、数据对象是数据的子集 Ｂ、数据元素间关系在计算机中的映象即为数据的存储结构 Ｃ、非顺序映象的特点是借助指示元素存储地址的指针来表示数据元素间逻辑关系 Ｄ、抽象数据类型指一个数学模型及定义在该模型上的一组操作 8. 计算机算法指的是（C）。 Ａ、计算方法Ｂ、排序方法Ｃ、解决问题的有限运算序列Ｄ、调度方法 9. 下列不属算法特性的是（D）。 Ａ、有穷性Ｂ、确定性Ｃ、零或多个输入Ｄ、健壮性 10.算法分析的目的是（C）。 Ａ、找出数据结构的合理性Ｂ、研究算法中的输入和输出的关系Ｃ、分析算法的效率以求改进Ｄ、分析算法的易读性和文档性 11.算法分析的两个主要方面是（A）。 Ａ、空间复杂性和时间复杂性Ｂ、正确性和简明性Ｃ、可读性和文档性Ｄ、数据复杂性和程序复杂性 12.算法的计算量的大小称为算法的（A）。 Ａ、效率Ｂ、复杂性Ｃ、现实性Ｄ、难度 13.在下面的程序段中，对x的赋值语句的频度为（C）。 for(i=1;i<=n;++i) for(j=1;j<=n;++j) x=x+1; Ａ、2nＢ、nＣ、n2Ｄ、log2n 14.设n为正整数，则如下程序段中最后一行的语句频度在最坏情况下是（D）。 for(i=n-1;i>=1;--i) for(j=1;j<=i;++j) if(A[j]>A[j+1]) A[j]←→A[j+1]; Ａ、nＢ、n(n-1)/2Ｃ、n(n+1)/2Ｄ、n2 1．假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。【北京大学1998 三、1 （5分）】 LinkedList Union(LinkedList la,lb) { pa=la->next; pb=lb->next; la->next=null; while(pa!=null && pb!=null) ∥当两链表均不为空时作 if(pa->data<=pb->data) { r=pa->next; pa->next=la->next; ∥将pa结点链于结果表中，同时逆置。 la->next=pa; pa=r; } else {r=pb->next; pb->next=la->next; ∥将pb结点链于结果表中，同时逆置。 la->next=pb; pb=r; } while(pa!=null) ∥将la表的剩余部分链入结果表，并逆置。 {r=pa->next; pa->next=la->next; la->next=pa; pa=r; } while(pb!=null) {r=pb->next; pb->next=la->next; la->next=pb; pb=r; } } 1）设有两个无头结点的单链表,头指针分别为ha,hb,链中有数据域data,链域next,两链表的数据都按递增序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归并中ha表中已有的数据若hb中也有,则hb中的数据不归并到ha中,hb的链表在算法中不允许破坏。【南京理工大学1997 四、3（15分）】 LinkedList Union(LinkedList ha, hb)∥ha和hb是两个无头结点的数据域值递增有序的单链 ｛LinkedList 表，本算法将hb中并不出现在ha中的数据合并到ha中，合并中不能破坏hb链表。 la; la=(LinkedList)malloc(sizeof(LNode)); la->next=ha; pa=ha; pb=hb; pre=la; while(pa&&pb) if(pa->data 第1章 绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 1. 填空 （1）（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 （2）（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 （3）从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 （4）数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 （5）算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 （6）在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 （7）设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 ⑵假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（）。 A 树 B 图 C 线性表 D 集合 【解答】B 【分析】将丈夫、妻子和子女分别作为数据元素，根据题意画出逻辑结构图。 ⑶算法指的是（）。 A 对特定问题求解步骤的一种描述，是指令的有限序列。 B 计算机程序 C 解决问题的计算方法 D 数据处理 【解答】A 【分析】计算机程序是对算法的具体实现；简单地说，算法是解决问题的方法；数据处理是 典型题目分类 §1 概述 ［全真模拟试卷３选择题３］数据结构中，与计算机无关的是数据的 Ａ存储结构Ｂ物理结构Ｃ逻辑结构Ｄ物理和存储结构 答案：Ｃ ［全真模拟试卷５选择题１］数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及Ａ数据的存储结构Ｂ计算方法Ｃ数据映象Ｄ逻辑存储 答案：Ａ ［全真模拟试卷５选择题３］在计算机中，算法是指 Ａ加工方法Ｂ解决方案的准确而完整的描述 Ｃ排序方法Ｄ查询方法 答案：Ｂ ［全真模拟试卷１填空题１］算法的基本特征是可行性、确定性、和拥有足够的情报。 答案：有穷性 ［全真模拟试卷６选择题２］算法分析的目的是 Ａ找出数据结构的合理性Ｂ找出算法中输入和输出之间的关系Ｃ分析算法的易懂性和可靠性Ｄ分析算法的效率以求改进 答案：Ｄ ［全真模拟试卷６填空题１］在算法正确的前提下，评价一个算法的两个标准是。答案：时间复杂度和空间复杂度［专家预测试卷３填空题１］算法的工作量大小和实现算法所需的存储单元多少分别称为算法的。 答案：时间复杂度和空间复杂度 ［全真模拟试卷３选择题１］算法的空间复杂度是指 Ａ算法程序的长度Ｂ算法程序中的指令条数 Ｃ算法程序所占的存储空间Ｄ执行过程中所需要的存储空间答案：Ｄ §2 线性表 ［全真模拟试卷６选择题３］线性表Ｌ＝（a1,a2,……,a i,……,a n），下列说法正确的是 Ａ每个元素都有一个直接前件和直接后件 Ｂ线性表中至少要有一个元素 Ｃ表中诸元素的排列顺序必须是由小到大或由大到小 Ｄ除第一个元素和最后一个元素外，其余每个元素都有且只有一个直接前件和一个直接后件 答案：Ｄ ［全真模拟试卷７选择题１］下列叙述正确的是 Ａ线性表是线性结构Ｂ栈和队列是非线性结构 Ｃ线性链表是非线性结构Ｄ二叉树是线性结构 答案：Ａ ［专家预测试卷３选择题１］根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成 Ａ动态结构和静态结构Ｂ紧凑结构和非紧凑结构 Ｃ线性结构和非线性结构Ｄ内部结构和外部结构 答案：Ｃ ［全真模拟试卷３填空题１］数据的逻辑结构有线性结构和两大类。 答案：非线性结构 ［专家预测试卷１选择题３］线性表的顺序存储结构和线性表的链式存储结构分别是 Ａ顺序存取的存储结构，顺序存取的存储结构 Ｂ随机存取的存储结构，顺序存取的存储结构 Ｃ随机存取的存储结构，随机存取的存储结构 Ｄ任意存取的存储结构，任意存取的存储结构 答案：Ｂ ［全真模拟试卷５填空题１］长度为ｎ的顺序存储线性表中，当在任何位置上插入一个元素概率都相等时，插入一个元素所需移动元素的平均个数为。 答案：ｎ/2 §3 栈和队列 ［全真模拟试卷１选择题１］栈和队列的共同特点是 Ａ都是先进先出Ｂ都是后进先出 Ｃ只允许在端点处插入和删除元素Ｄ没有共同点 答案：Ｃ ［全真模拟试卷２选择题３］如果进栈序列为e1,e2,e3,e4，则可数据结构第一章试题
经典数据结构面试题(含答案)
数据结构课后习题及解析第一章
数据结构模拟卷(含答案)经典习题培训讲学
数据结构模拟卷(含答案)经典习题
数据结构第一章练习题
经典数据结构上机题_答案解析
数据结构习题汇编01 第一章 绪论 试题
数据结构经典题目c语言代码
数据结构第1章习题解答..
数据结构经典例题
数据结构第1章 练习题及答案
数据结构典型例题
《数据结构》吕云翔编著第1章绪论习题解答
数据结构经典算法试题
数据结构课后习题详解(超完整,超经典)
数据结构第1章习题兼解答
[IT认证]全国计算机等级考试《数据结构》典型试题
相关主题
文本预览