课程导入
课程性质：专业必修课
总学时数：20*3=60学时
上机学时：18*2=36学时
假设前提：已有程序设计基础（C/C++基础，尤其是C语言程序设计基础）学习目标：培养数据抽象能力(Data Abstraction Ability)。注：C程序设计课则是培养结构化程序设计的能力。
具体涉及两个方面内容的学习和训练：
1)学会分析研究计算机加工数据结构的特征，以便学会针对不同的应用问题，选择合适的逻辑结构、存储结构及相应的算法描述。并做相应的时间复杂度和空间复杂度的分析。
2)复杂程序设计方法的训练过程。学会将问题求解的程序设计成结构清楚、正确、符合软件工程规范的系统。
学习方法：勤奋练习，积极上机实践。(熟悉各种数据结构的基本思想和算法描述，并不断尝试结合教材内容和课外训练的数据抽象能力的培养) 教学步骤：整体上分为两个部分内容，一是数据结构的基本思想、方法与应用技巧，二是上机实践。
具体内容：
第一章绪论
第二、三、四、五、六、七章基础(强调从ADT的角度进行描述的思想)第八章 OS/Compiler中的动态存储管理技术(×)
第九、十章查找/内排序
第十一章外排序(×)
第十二章文件结构(×)
注：由于学时数的限制，第八章、第十一章和第十二章暂时不做要求。其它章节中，带**号的章节不做要求或不做考试要求。
课程教材
《数据结构》，严蔚敏，吴伟民编著，北京：清华大学出版社，2003年3月参考书目
(1)《计算机算法：设计和分析引论》，[美] S 巴斯, 朱洪等译，上海：复旦
大学出版社，1985
(2)《Data Structures with C++》,[美] William Ford, William Topp, 北京：清华
大学出版社，Printice-Hall International, inc. 1998年4月，ISBN 7-302-02413-8
(3)《数据结构、算法与应用----C++语言描述》，[美] Sartaj Sahni 著，汪诗林，
孙小东译，北京：机械工业出版社，2002年10月，ISBN 7-111-07654-1
(4)《计算机程序设计艺术》（第2版），第3卷，[美]Donald E.Knuth 著，北
京：清华大学出版社，2002年9月，ISBN 7-302-05816-4
(5)《算法设计技巧与分析》，（沙特）M.H. Alsuwaiyel 著，北京：电子工业出
版社，2004年8月，ISBN 7-121-00108-X
注：其它很好的学习类参考书籍，请咨询高年级学长或光临书店！
习题及实验参考书
(1)《数据结构实验教程》(C语言版)，王玲主编，成都：四川大学出版社，
2003年7月
(2)《数据结构习题集》(C语言版)，严蔚敏，吴伟民编著，北京：清华大
学出版社，2003年1月
第一章绪论
需要对程序的处理对象进行组织研究的两大主要原因：
一是计算机领域的渗透早已使其应用不再局限于早期的科学计算领域→其加工处理对象由纯粹的数值类发展到具有一定结构的数据类型，如字符、表、图形、图像、声音等，使得程序设计活动面临了许多新的问题需要解决。
二是要编写出好的程序系统，人们发现，必须要对待处理对象的数据特性、各处理对象之间的关系进行分析、组织，使编写出的程序能够有效地处理和解决它们。
它们构成了数据结构的研究动力和研究内容。
1-1 什么是数据结构？
Data Structure (DS):
Data---- (1) facts; (2) Information prepared for or stored by a computer;
Structure---- way in which something is put together, organized, built, etc.
1-1-1 不同问题的数据结构模型构建实例分析
用计算机解决问题的步骤：抽象其数学模型→求解该模型的算法→编制程序→测试或调试→得解
(1)对数值计算问题
例1-1 求解梁架结构中应力的数学模型；预报人口增长的微分方程模型。
其关键在于分析问题，提取或寻找对象之间的结构关系，然后用数学语言加以描述。
(2)对无法用数学模型描述的非数值计算问题
其数学模型集中在数据结构的建立中。
例1-2 图书馆书目检索系统自动化问题。
按书名的索引表、按作者名的索引表、按分类号的索引表、按登录号排列的书目表表示
结构就是其检索问题中的基本数据关系的数学模型(此为线性的结构关系模型)。(见教材P1-2)
例1-3 人机对弈问题。
其对弈策略、规则驱动、棋盘状态、前景预测方法等模型的建立，同时，棋盘状态描述模型是对弈问题的关键性数据描述模型，但棋局之间的关系往往不是线性的，需要用非数值型结构来描述。例如：#字游戏问题(见教材P2)。需要用到所谓“树结构”来描述这些棋盘状态之间转换过程。
例1-4 多叉路口交通灯的管理问题(在多叉路口需要设多少颜色的灯，使得车辆之间互不碰撞，同时车流量最大) (见教材P2-3) 对图的顶点作图的问题。
与此相关的还有如哥黎斯堡七桥问题、逻辑电路设计问题等，用传统的数学模型是无法描述的。必须用新型的所谓“图结构”进行描述。
1-1-2 DS课程的研究内容及课程历史
DS研究内容：研究非数值计算的程序设计问题中计算机的操作对象以及它们之间关系和操作的一门学科课程。
DS作为一门独立课程的发展历史：
1968年，DS与图论、表、树为“同义语”。后来，扩充到了网络、集合代数、格、关系等(它们又构成了“离散数学”的基础内容)。再后来，将大型数据库系统中的文件管理以及内存管理等技术也纳入了本课程中来。
《计算机程序设计艺术》(第一卷) ，Donald Knuth1(Turing 奖获得者)（开创了最初的DS体系，是第一本系统阐述数据的逻辑结构、存储结构及其操作的著作）目前，DS是许多专业的选修或必修课。
DS课程的地位(综合性非常强)(见教材P4图1.4)：界于数学、计算机软件和计算机硬件之间的核心课程。既是一般程序设计的基础，更是编译程序、OS、DBS及其它大型的系统程序和应用程序设计与实现的重要基础。
发展方向：
1) 向各专门领域中的特殊问题之数据结构研究发展；
2) 从ADT观点来研究。
1-2 数据结构中涉及的基本概念与术语
1-2-1 基本概念和术语
(1)Data----(facts/information)能被计算机处理的符号总称,是待加工的“原料”
例如：求解代数方程组时的Data为integer/real型的系数或根等；
编译器的Data为：程序代码或字符序列；
文字编辑器的Data为：字符、图形等。
(2)Data Element----对数据进行处理的基本单位
例如：前述的棋盘之格局；图中的顶点等。
注：数据元素一般由若干数据项(Data Item)组成。
1
又如：前述图书书目中的书卡数据由作者姓名、书名、书号等数据项构成。
(3)Data Object----相同性质的数据元素之集合
例如：整数数据对象即集合,...}
{'B
'
C=；计
N;字母字符对象即,...}
A
','
,1
2
=
,0
{±
±
算机信息与计算科学专业2003级学生对象即全体该班的学生集合等。
(4)Data Structure----相互之间存在某种特定关系的数据元素之集合(从操作对象抽象出来的数学模型)
注1：DS中的数据元素不是孤立存在的；
注2：数据元素之间的关系即可称为“结构”；
注3：数据元素之间的关系有4种基本结构：
集合(set)关系----无序的松散关系；
线性(linear)关系----一一对应关系(one-one)；
树(tree)关系----一对多关系(one-many)；
图(graph)关系或者网(net)关系----多对多关系(many-many)。（如教材P5图1.5所示）注4：DS的形式定义为：D_S=(D,S)。其中，D为数据对象有限集合，S为D上的关系有限集合。
注5：一般而言，DS要表达的是一组具有相同结构的数据对象之值的集合。
1-2-2 实例分析
例1-4 复数关系的定义。
数据结构：Complex=(C,R)。
其中，C是两个实数集合{c1,c2}；R是定义在C上的一种关系，即R={P}={
例1-5 事务管理程序中的课题小组信息的数据结构。假设1位老师带1~3名研究生，1位研究生带1~2位学生，则数据结构如下：Group=(P,R)。
其中，P={T,G1,…,G n,S11,…S nm,1<=n<=3, 1<= m<=2}
R={R1, R2}
R1={
R2={
1-2-3 其它概念与术语
(1)逻辑结构(Logical Structure)---描述数据元素之间的逻辑关系的结构。
(2)物理结构(Physical Structure)----描述数据元素在计算机中的实际存储映射关系的结构，又称存储结构。
存储结构一般包含两个部分的内容：一是数据元素的存储，二是数据元素之间关系的存储。
(3)容量单位问题
Byte, bit, KB, MB, GB, TB
(4)数据域(Data Field)----当数据元素由若干个数据项组成时，各数据项位串被称为数据域。
(5)数据节点(Node)----数据元素。
(6)数据元素之间关系的两种映射方法
顺序映射----顺序存储结构。借助元素在存储器中存储的相对位置关系来表示数据元素之间的逻辑关系。
非顺序映射----链式存储结构。借助指示元素存储地址的指针来表示元素之间的逻辑关系。
注：数据的逻辑结构与物理结构是紧密相关的。一般来讲，任何一个算法的设计取决于其数据的逻辑结构，而算法的实现取决于其数据的存储结构。
(7)虚拟存储结构----存储结构的基于高级程序设计语言的描述方法
通过高级语言的数据类型来描述。Array例如：一维数组用于描述顺序存储结构；指
针用于描述链式存储结构；struct, union等用来表
示复杂问题的数据结构。
DS中的虚拟存储结构在计算机系统中的层
次位置如图1-3所示。
(8)数据类型(Data T ype)----用于刻画程序中的
操作对象之值的集合及定义在其上的一组相应操
作的抽象总称。
注1：每个变量、常量或表达式都有一个属于它的数据类型。显式地或者隐含地规定了变量等在程序执行期间的所有可能取值，及其上允许的一组操作。
注2：数据类型一般分为原子类型(Atom Data T ype)和结构类型(Structure Data T ype)。前者即基本数据类型，后者即复杂结构类型。
注3：数据类型的作用：从硬件的角度，它是解释计算机内存信息含义的手段；从用户的角度，它实现的信息的隐藏，将用户不必了解的细节隐藏了起来。
(9)抽象数据类型(Abstract Data T ype)----一个数学模型及定义在其上的一组操作。
注1：其定义仅取决于其逻辑结构特性，与机器内部的表示与实现无关。只要其数学特性不变，则其外部的使用将不受影响。
注2：本质上跟数据类型概念一致。但ADT比之更广泛，不再局限于处理器已经定义的类型(固定数据类型)，还包含用户设计软件时的自定义数据类型。
注3：程序设计方法学：软件系统框架应建立在数据之上，而不是建立在操作之上。其目的是为了提高软件的复用程度。具体而言，即：在软件系统每个相对独立的模块上，建立起一组数据和施加于这些数据的一组操作，并在模块内部给出这些数据的表示及相应的操作细节，但在外部的使用只是其抽象的数据和抽象的操作。
1-2-4 ADT的结构及定义方法
抽象数据类型的形式定义(三元组)：ADT=(D,S,P)
其中，D----Data, S----Relations on D, P----Operations on D。
本书对抽象数据类型的定义形式：
ADT 抽象数据类型名 {
数据对象：<数据对象的定义>
数据关系：<数据关系的定义>
基本操作：<基本操作的定义>
} ADT 抽象数据类型名
其中数据对象和数据关系用伪码描述。
基本操作的一般定义格式为：
基本操作名(参数表)
初始条件：<初始条件描述>
操作结果：<操作结果描述>
其中，参数表中的参数有赋值参数(只负责提供操作用的输入值)和引用参数(&)(既可输入值，也返回操作结果值)。
初始条件描述了操作执行之前，数据结构和参数应当满足的要求，若不满足，操作将失败，并应返回相应出错信息。如没有初始条件，则初始条件为空。
操作结果是指在正常操作完成之后，数据结构的变化及其它应该返回的结果。
例1-6 对抽象数据类型三元组的定义。
ADT T riplet {
数据对象：D={e1,e2,e3|e1,e2,e3 ElemSet}
数据关系：R1={
基本操作：
InitT riplet(&T,v1,v2,v3)
操作结果：构造三元组T，v1,v2,v3分别赋给元素e1,e2,e3。
DestroyT riplet(&T)
操作结果：三元组T被销毁。
Get(T,i,&e)
初始条件：三元组T已经存在，且1<=i<=3
操作结果：用e返回T的第i个元素
Put(&T,i,e)
初始条件：三元组T已经存在，且1<=i<=3
操作结果：改变T的第i个元素的值为e
IsAscending(T)
初始条件：三元组T已经存在
操作结果：如果T的三个元素按升序排列，则返回true,否则，返回false
IsDescending(T)
初始条件：三元组T已经存在
操作结果：如果T的三个元素按降序排列，则返回true,否则，返回false
Max(T,&e)
初始条件：三元组T已经存在
操作结果：用e返回T的三个元素中的最大者的值
Min(T,&e)
初始条件：三元组T已经存在
操作结果：用e返回T的三个元素中的最小者的值
} ADT T riplet
多形数据类型(Polymorphic Data T ype)----具有相同的数学抽象特性的类型，即不论元素的特性如何，元素之间的关系及对元素的操作都相同。
注1：多形数据类型由C++类OOPL语言实现之。即C++中的多态技术。
注2：本书以C为背景描述算法，所以，都假定其数据元素的成分是确定的。其在上机实践时需要由程序设计者确定或自行定义。
1-3 ADT的表示与实现
基本原则：通过高级语言中固有的DT来表示和实现。(本书)介于伪代码与C语言之间的类C描述，以便于转成C或C++程序实现之。
为什么选择C？C语言并不是描述抽象数据类型（即数据结构）的理想工具。但鉴于如下理由：“面向对象的程序设计”并非程序设计的入门课程或“数据结构”课程的先修课程。同时，由于C/C++又是目前计算机软件程序设计实现中的主流环境工具。
解决的办法：本书精选了一个C语言的核心子集，并增添了C++的引用调用参数传递方式，构成了数据结构和算法描述的C描述语言。其特点：不拘泥于C的细节，又容易转换成C/C++程序。
本书的类C工具核心子集说明：(教材P10-13)
(1)预定义常量
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status /*Status表示函数的类型，其值是函数结果的状态编码*/
(2)DS的表示
数据结构的表示或存储结构都用“类型定义”进行描述，即typedef。数据元素的用Elem Type表示，其具体类型由用户在实现时定义。
(3)基本操作或算法都以函数的形式描述
一般的函数格式：
函数类型函数名(函数参数表) {
/*算法说明部分*/
算法实现的语句序列
}//函数名
注1：参数类型要说明。算法内部使用的辅助变量可以不说明，或做简要注释即可。
注2：约定符号含义：
1) a,b,c,d,e等表示数据元素的名；
2) i,j,k,l,m,n表示整型变量名；
3) p,q,r等表示指针变量名；
4) 当函数返回值为结果状态时，函数类型用Status说明；
5) 函数调用有两种：值调用；引用(C++概念，用…&?表示在C中用指针的形式表示)。
(4)赋值语句的形式
简单赋值、串联赋值和条件赋值与C相似；
成组赋值形式：(变量名1,…,变量名n)=(表达式1,…,表达式n)
结构名=结构名；
变量名[]=表达式；
变量名[起始下标..终止下标]=变量名[起始下标..终止下标];
交换赋值形式：变量名 变量名；
(5)选择语句(if/switch)
(6)循环语句(for/while/do-while)
(7)结束语句(return/break/exit(异常代码))
(8)I/O语句(scanf()/printf())
(9)注释(//)
(10)基本函数
max(表达式1,…,表达式n)
min(表达式1,…,表达式n)
abs(表达式)
floor(表达式)----求不足整数值
ceil(表达式)----求进位整数值
eof(文件变量)----判定文件是否结束
eoln(文件变量)----判定行是否结束
(11)逻辑运算约定(&&, ||, !等)
例1-7 抽象数据类型Triplet的表示与实现。
//----------采用动态分配的顺序存储结构----------
typedef ElemType *Triplet; //三元组元素的数据类型，ElemType需要自us定义
//----------基本函数的原型说明----------
Status InitTriplet(Triplet &T, ElemType v1, ElemType v2, ElemType v3);
//操作结果：用v1,v2,v3构造三元组T
Status DestroyTriplet(Triplet &T);
//操作结果：销毁三元组T
Status Get(Triplet T,int i, ElemType &e);
//初始条件：三元组T已经存在，i的取值为1-3
//操作结果：将T的第i个元素取出来，用e返回之
Status Put(Triplet &T, int i, ElemType e);
//初始条件：三元组已经存在，i的取值为1-3
//操作结果：用e作为T的第i个元素的值
…
//----------基本操作的实现----------
Status InitTriplet(Triplet &T, ElemType v1, ElemType v2, ElemType v3)
{ //用v1,v2,v3构造三元组T
T=(ElemType*)malloc(3*sizeof(ElemType)); //分配三个元素空间
if (!T) exit(OVERFLOW); //分配失败时，退出程序执行
T[0]=v1; T[1]=v2; T[2]=v3;
return OK;
} // InitT riplet
Status DestroyTriplet(Triplet &T)
{ //销毁三元组T
free(T);
t=NULL;
Return OK;
} // DestroyT riplet
Status Get(Triplet T,int i, ElemType &e)
{ //将T的第i个元素取出来，用e返回之
if (i<1 || i>3) return ERROR; //下标值不合法时，直接退出
e=T[i-1];
return OK;
} // Get
…
1-4 算法与算法分析方法
1-4-1 算法及其特征
算法(Algorithm)：对特定问题求解步骤的描述指令操作的有限序列。
(Set of rules or procedures that must be followed in solving a problem)
基本特征：
1)有穷(Finite)
对任何合法的输入值，算法必须在有限步骤之内停止或完成或结束。
注：这种“有穷性”使得算法不必保证一定得解。其结果有如下几中情形：有解；无解；有理论解，但算法的运行没有得到之；不知有无解，且算法的有穷执行中也没有得到解。
2)确定性(Definite)
算法中的每一条指令必须有确切的含义，不会产生理解上的偏差。
算法在任何时候只有唯一的一条执行路径。即相同输入，得相同输出。
3)可行性(Feasibility)
算法是可行的。其描述的操作都是可以通过基本运算的有限次运算来实现的。
4)输入(Input)
有0个或多个输入。
5)输入(Output)
有1个或多个输出。
1-4-2 算法设计的要求
好算法的主要特性：
1)正确性(Correctness)：满足具体问题的要求。
四种级别要求：(1) 无语法错误→(2) 对几组输入数据可得到符合要求的解→(3) 对精选的、典型的、苛刻的输入能得到符合要求的解→(4) 对一切合法的输入都可以得到符合要求的解。
2)可读性(Readability)：好(易于阅读、理解、交流)
3)健壮性(Robustness)：对非法输入数据或操作，能从容应对并给出提示，不影响结果。
4)时空效率(Time-Space Efficiency)：高时、空效率。
1-4-3 算法(时间)效率的度量方法
两种度量方法：
1)事后统计法
其依赖的因素是算法的实现和具体的计算机软/硬环境情况。
2)事先估计法
程序执行过程的耗时分析：(1) 算法策略；(2) 问题规模；(3) 程序代码实现的语言种类(语言级别越高，时间效率越低)；(4) 编译器的质量；(5) 机器的执行速度等。
结论1：绝对的时间单位来衡量算法的效率是不合适的。
结论2：除开软、硬件因素外，效率或工作量主要决定于问题的规模大小。
算法的渐进时间复杂度(Asymptotic time complexity)或时间复杂度：
(1)一个算法取决于控制结构(顺序、选择、循环)和原操作的综合效果。因此，可以用关于问题规模的函数来表示算法的“原操作”时间为单位的效率度量。一般表示为：
O
n
T
))
f
(
(n
(
)
例如：N*N矩阵乘法中，“乘法”是该问题的基本操作或原操作，所以：
for (i=1;i<=n;++i)
{
for (j=1;j<=n;++j)
{
c[i][j]=0;
for (k=1;k<=n;++k)
{
c[i][j]+=a[i][k]*b[k][j];
}
}
}
以上算法的乘法是基本操作，其次数与n3成正比，记作T(n)=O(n3)。
(2)原操作的频度(Frequency count)：即原操作的重复执行次数。
例如：(a) {++x;s=0}
(b) for (j=1;j<=n; j++) {++x;s+=x;}
(c) for(j=1;j<=n;j++)
for(k=1;k<=n;k++)
{++x;s+=x;}
以上例中，(a), (b), (c)中“++x”的执行频度分别是1,n,n*n。其复杂度可表示为O(1), O(n), O(n2)。
1-4-4 常见的时间复杂度函数增长率分析
常见的时间复杂度：O(1)----常量阶；O(n)----线性阶；O(n2)----平方阶；O(logn)----对数阶；O(2n)----指数阶；O(n k)----多项式阶。
注1：应尽量用多项式阶的算法，少用指数阶的算法。
注2：时间复杂度往往只考虑问题的规模n的关系。
注3：除特别说明，一般指的是最坏情形之值。
增长率的分析(见教材P16图1.7)。
结论：尽可能选O(n k)型算法或log(n)型算法。
复杂度的确定的一般原则：一个问题选一个基本操作，也可选几个基本操作。根据具体问题，复杂度可以选增长率、平均值、执行次数等作为标准。
1-4-5 算法的空间复杂度(Space Complexity)
所需存储空间主要有两类：
1) 常量、指令、变量、输入输出数据空间等；
2) 对数据进行加工的工作单元和中间存储用的辅助空间。
注1：若额外空间对输入数据量来将是常数的，则可称之为原地工作。
注2：所占空间量依赖于特定输入，除特别说明外，均指最坏情形。
算法书写规范
(1)算法说明
又称算法的规格说明。是完整算法描述的不可或缺的部分。
说明内容：
1) 算法要完成的功能；
2) 算法中各个参数的含义和输入、输出意义说明；
3) 算法中引用的全局变量和外部定义变量的说明，其作用和使用方法，入口的初始
值及其应当满足的条件如何。例如：链表是否带有头结点、表中元素是否有序、是升序还是降序等。
算法说明的时间：在算法设计的开始就应当明确，并在设计过程中补充。
算法说明的作用：用于判别一个算法是否正确的基础。
注意事项：算法规格说明中，应当假定所划分出来的子问题是能够实现的，而如何实现是算法要完成的工作。
(2)注释和断言
对算法描述中的难以理解的和关键性的语句或描述段落，应当加上相应的注释以提高算法的可读性。注释不是越多越好，但其抽象程度应略高于算法语句所表达的含义。
注意事项：多些断言式注释，是增强算法可读性的重要途径。以断言式描述作为算法描述的手段，是提高结构化算法描述的手段。
(3)输入和输出
一般通过参数、输入输出语句或全局变量或外部变量形式传递算法所需要的信息。
(4)错误处理
尽量使用算法中的函数返回值形式返回执行状态，以便实际实现时的异常处理。
(5)语句选用
尽量使用类C结构的语句，如if else，while，for ，do while等。
(6)其它建议
建议尽量能够以图的形式说明算法过程或思想；
建议在算法书写完后，要用边界条件输入参数值进行验证，以便察看算法是否能够顺利执行。
算法书写的说明实例：
例1 从线性表中删除k 个元素的算法
Status Delete(SqList a,int i,int k)
//本算法从顺序存储的线性表a 中删除第i 个元素开始的k 个元素
例2 多一元多项式求值的算法
float Evaluate(SqPoly pn,float x)
//本算法计算多项式pn 中x 的确定后的值，算法不判别计算是否溢出
//算法的计算公式是：1
i
m
e i i a x =∑ //pn 为以结构体形式存放每项值的顺序存储结构，其中pn.data[i].coe
f 和pn.data[i].exp 分别存放第i 项的系数i a 和指数i e 。
//要求多项式pn 中的各项按指数升序排列，即满足120...m e e e ≤≤≤≤，且指数非负。
例3 入栈操作push 的算法
void push(TwoWayStack &tws, int i, ElemType x, bool &overflow)
//两栈共享一个大小为m 的空间，其存储空间表示为tws.elem[0..m-1]，其中，两个栈的栈顶分别在存储空间的两端，分别用tws.top[0]和tws.top[1]表示其指针。
//两栈的表示范围如下：tws.data[0..tws.top[0]]为第一个栈的范围；
// tws.data[tws.top[1]..m-1]为第二个栈的范围。
//本算法的功能是：将元素x 放入栈i ，其中，i 表示将操作的栈序号
//如果push 操作时，栈i 已经满，则不改变栈指针和栈内容，且返回overflow 为TRUE 表示栈溢出。
课外习题
1-1 简述下列术语：数据(data)、数据元素(data element)、数据对象(data object)、数据结构(data structure)、存储结构(Store Structure)、逻辑结构(Logic Structure)、数据类型(data type)、抽象数据类型(abstract data type)
1-2 试个给出数据结构、抽象数据类型和程序设计语言中的数据类型之间的区别。 1-3 有数据结构(D,R)，其中：{1,2,3,4},{}D d d d d R r ==,{(1,2),(2,3),(3,4)}r d d d d d d =，试给出其逻辑结构图。
1-4 请给出以下程序段的流程图描述：
(1) product=1;i=1;while (i<=n) {product*=i;i++}
(2)i=0;do {i++;} while ((i!=0) && (a[i]!=x));
1-5** 设n 为正整数。试确定下列程序段中前面有@的语句的执行频度。
(1) i=1;k=0;
while (i<=n-1) {
@ k+=10*i;
i++;
}
(2) i=1;k=0;
do {
@ k+=10*i;
i++
} while (i<=n-1);
(3) k=0;
for (i=1;i<=n;i++)
for (j=i;j<=n;j++)
@ k++;
(4) x=91;y=100;
while (y>0)
{
@ if (x>100) {x-=10;y--;}
else x++;
}
1-6* 假设n 为2的乘幂，且n>2，试求以下算法的时间复杂度及变量count 的值(以n 的函数的形式表示)。
int Time(int n)
{
count=0;x=2;
while (x x*=2;count++; } return (count); }//Time 1-7* 已知有实现同一功能的两个算法，其时间复杂度分别为(2)n O 和10()O n ,假设计算机可连续运算的时间为710秒(100多天)，每秒的基本操作为510次。试问两个算法可解问题的规模各是多少？哪个算法更合适？为什么？ 1-8* 试用数学归纳法证明： (1) 2 1 (1)(21)/6(0)n i i n n n n ==++≥∑ (2) 10 (1)/(1)(1,0) n i n i x x x x n +==--≠≥∑ (3) 1 1 221(1)n i n i n -==-≥∑ (4) 2 1(21)(1)n i i n n =-= ≥∑ 1-8* 假设有A,B,C,D,E 五个高校进行田径对抗赛，各院校的单项成绩均存入计算机，并构成一张表，表中每一行如下： 1-9** 试编写算法，计算!2(0,1,....,1)i i i n ?=-的值，并分别存入数组a[arrsize]的各个分量中。假设计算机中允许的整数最大值为MAXINT ，则当n>arrsize 或对某个k(01k n ≤≤-)使得!2k k M A X IN T ?>时，应按出错处理。注意选择你认为较好的出错处理方法。 1-10** 试编写算法求一元多项式0()n i n i i P x a x ==∑的值，并确定算法中每一语句的执行次数 和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。本题的输入为 (0,1,...,)i a i n 和0x 、n ，输出为0()n P x 。 数据结构练习第一章绪论 一、选择题 1.以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 2．设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02， 06>，<03，07>，<03，08>，<03，09>}，则数据结构A是（）。 A. 线性结构 B. 树型结构 C. 物理结构 D. 图型结构 3．下面程序的时间复杂为（） for（i=1，s=0； i<=n； i++） {t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；} A. O(n) B.O(n2) C. O(n3) D. O(n4) 4．数据的最小单位是（）。 A.数据项 B. 数据类型 C.数据元素 D. 数据变量 5．程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的时间复杂度为（）。 A. O(n) B. O(nlog 2 n) C. O(n2) D. O(n3/2) 6．下列程序段的时间复杂度为（）。 for(i=0； i 第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）。 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（） A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 4．一个算法应该是（） A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 5. 下面关于算法说法错误的是（） A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（）【南京理工大学 2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。【武汉交通科技大学 1996 一、4（2分）】A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。【北方交通大学 2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？【北方交通大学 2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（）【北方交通大学 2001 一、2（2分）】A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学 2001 一、10（3分）】 FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A． O(2n) B．O(n) C．O(n2) D．O(log2n) 12．程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF A[j]>A[j+1] THEN A[j]与A[j+1]对换； 其中 n为正整数，则最后一行的语句频度在最坏情况下是（） 《数据结构与算法设计》习题册 第一章绪论 一、单项选择题 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.在存储数据时，通常不仅要存储各数据元素的值，而且还要存储。 第一章绪论 一、问答题 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; 四、试编写算法，求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…anxn的值Pn(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入ai(i=0,1,…,n),x和n，输出为Pn(x0)。通常算法的输入和输出可采用下列两种方式之一： （1）通过参数表中的参数显式传递。（2）通过全局变量隐式传递。 试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。 第二章线性表 2.1 描述以下三个概念的区别：头指针，头结点，首元素结点。 2.2 填空： （1）在顺序表中插入或删除一个元素，需要平均移动＿＿＿＿元素，具体移动的元 素个数与＿＿插入或删除的位置＿＿有关。 （2）在顺序表中，逻辑上相邻的元素，其物理位置＿＿＿＿＿＿相邻。在单链表中，逻辑上相邻的元素，其物理位置＿＿＿＿＿＿相邻。 （3）在带头结点的非空单链表中，头结点的存储位置由＿＿＿＿＿＿指示，首元素结点的存储位置由＿＿＿＿＿＿指示，除首元素结点外，其它任一元素结点的存储位置由＿＿＿＿指示。 2.3 已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 一、选择题 1、数据结构通常是研究数据的（）及它们之间的相互联系。 A、存储和逻辑结构 B、存储结构 C、顺序结构 D、链式存储结构 2、数据在计算机存储器内表示时，物理地址和逻辑位置相同并且是连续的，称之为（） A、存储结构 B、逻辑结构 C、顺序存储结构 D、链式存储结构 3、线性结构是数据元素之间存在一种（） A、一对多关系 B、多对多关系 C、多对一关系 D、一对一关系 4、计算机算法指的是（），它具备输入、输出和（）等五个特性。 1）A、计算方法B、排序方法C、解决问题的有限运算序列D、调度方法2）A、可行性、可移植性和可扩充性B、可行性、确定性和有穷性 C、确定性、有穷性和稳定性 D、易读性、确定性和安全性 5、在计算机中数据有链式和顺序两种存储方式，在存储空间利用率上，链式存储比顺序存储更（） A、高 B、低 C、相同 D、不确定 6、计算机内部数据处理的基本单位是（） A、数据 B、数据元素 C、数据项 D、数据库 7、设语句x++的时间是单位时间，则语句： for(I=1;I<=n;I++) x++; 时间复杂度为（） A、O（1） B、O（n） C、O（n2） D、O（n3） 二、填空题 1、数据结构按逻辑结构可分为两大类，分别是（线性结构）和（非线性结构）。 2、一个算法的效率可分为（时间）效率和（空间）效率。 3、在树型结构中，根结点没有（双亲）结点，其余每个结点有且只有（一）个前驱结点；叶子结点没有（孩子）结点，其余每个结点的都可以（一个或多个）个这种结点。 4、下面程序段的时间复杂度是（O(N1/2)） I=s=0; while (s 数据结构与算法上机作业第一章绪论 一、选择题 1、数据结构是一门研究非数值计算程序中计算机的○1A 以及它们之间的○2B 和运算等的学科。 ○1 A. 操作对象 B. 计算方法 C. 逻辑存储 D. 数据映像 ○2 A. 结构 B. 关系 C. 运算 D. 算法 2、线性结构的顺序存储结构是一种○1 A 的存储结构，线性结构的链式存储结构是一种○2 B 的存储结构。 ○1 A. 随机存取 B. 顺序存取 C. 索引存取 D. 散列存取 ○2 A. 随机存取 B. 顺序存取 C. 索引存取 D. 散列存取 3、下面程序的时间复杂度为 C 。 for(i=0; i 第一章绪论习题练习答案 1.1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结 构、非线性结构。 ●数据：指能够被计算机识别、存储和加工处理的信息载体。 ●数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、 记录。数据元素有时可以由若干数据项组成。 课后答案网https://www.doczj.com/doc/f912544828.html, ●数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可以 看作是程序设计语言中已实现的数据结构。 ●数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容: 数据的逻辑结构、存储结构和数据的运算。 ●逻辑结构：指数据元素之间的逻辑关系。 ●存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构. ●线性结构：数据逻辑结构中的一类。它的特征是若结构为非空集，则该结构有且只有一 个开始结点和一个终端结点，并且所有结点都有且只有一个直接前趋 和一个直接后继。线性 表就是一个典型的线性结构。栈、队列、串等都是线性结构。 ●非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前 趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。 1.2 试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。 答： 例如有一张学生体检情况登记表，记录了一个班的学生的身高、体重等各项体检信息。 这张登记表中，每个学生的各项体检信息排在一行上。这个表就是一个数据结构。每个记录 (有姓名，学号，身高和体重等字段)就是一个结点，对于整个表来说，只有一个开始结点(它 的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前 趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的逻辑结 构是线性结构。 这个表中的数据如何存储到计算机里，并且如何表示数据元素之间的关系呢? 即用一片 连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点 第一章——绪论 前言（为什么会有数据结构这门课） 计算机主要应用在两个方面：一个是数值计算，另一个是非数值计算。 早期的计算机只能处理数值计算（也就是数学上的运算，特点是计算过程复杂，数据类型相对简单，数据量较少），这时候人们主要通过程序设计的思想来处理处理问题。 随着计算机渗入生活，人们开始要求计算机参与处理非数值计算（特点是计算过程相对简单，数据结构相对复杂，数据的组织排列结构从某种意义上决定着非数据计算应用的有效性，数据的组织排列结构成为处理和解决数据处理问题的核心），这时候原来的程序设计以程序为中心的设计过程已经无法满足大量的非数值计算。急需一门以复杂数据为中心，研究数据的合理组织形式，并设计出基于合理数据组织结构下的高效程序的科学来指导计算机的发展。数据结构就是在这种环境下诞生的。 每种数据结构类型都分四个描述层次——概念层、逻辑层、存储层、运算实现层。 而数据结构往往在逻辑层上为程序抽象出算法，并对算法进行优化。最终推出较优的指导性算法，方便后续的具体程序设计。 什么是数据结构 数据结构是随着计算机科学的发展而建立起来的围绕非数值计算问题的一门科学。 准确来说，数据结构就是研究大量数据在计算机中存储的组织形式，并定义且实现对数据相应的高效运算，以提高计算机的数据处理能力的一门科学。 这里的运算主要指的是非公式化的运算，如数据存取、插入、删除、查找、排序和遍历等运算。 也就是说，数据结构是管信息管理和存储的，研究怎么存比较好，怎么管理相对比较优化。 而这里就涉及到一个问题：信息应该怎么表示，根据程序设计中介绍的思路，要在电脑中写入一个数据，应该包括它的属性和它的位置。只要有他的位置和属性都确定了，那这个数据就完整地被存储到计算机中了。 所以，信息是由信息元素的值及信息元素之间的相互关系（逻辑顺序）和信息元素在计算机中的存储方式（物理顺序）共同组成。 逻辑结构就是代表了信息本身的属性，他是与计算机本身无关的“逻辑组织结构”它的构成是由数据的值、数据与数据之间的关联方式两个部分组成。 而存储方式则是代表他在计算机的位置，是将具有逻辑组织结构的数据在计算机的存储介质上如何存放的“物理组织结构”。 做好了逻辑和储存两方面的处理，信息才真正变成了计算机中的一个数据。 同时，根据定义，另一个问题无法忽视，什么高效运算？ 在我看来，高效运算指的就是算法的优化。因为算法不仅要实现问题的要求，而且，应 数据结构与算法 习题册 （课后部分参考答案） 《数据结构与算法》课程组 目录 目录 课后习题部分 第一章绪论 (1) 第二章线性表 (3) 第三章栈和队列 (5) 第四章串 (8) 第五章数组和广义表 (10) 第六章树和二叉树 (13) 第七章图 (16) 第九章查找 (20) 第十章排序 (23) 第一章绪论 一. 填空题 1. 从逻辑关系上讲，数据结构的类型主要分为集合、线性结构、树结构和图结构。 2. 数据的存储结构主要有顺序存储和链式存储两种基本方法，不论哪种存储结构，都要存储两方面的内容：数据元素和数据元素之间的关系。 3. 算法具有五个特性，分别是有穷性、确定性、可行性、输入、输出。 4. 算法设计要求中的健壮性指的是算法在发生非法操作时可以作出处理的特性。 二. 选择题 1. 顺序存储结构中数据元素之间的逻辑关系是由C表示的，链接存储结构中的数据元素之间的逻辑关系是由D表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 2. 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是B。 A 树 B 图 C 线性表 D 集合 3. 算法指的是A。 A 对特定问题求解步骤的一种描述，是指令的有限序列。 B 计算机程序 C 解决问题的计算方法 D 数据处理 三. 简答题 1. 分析以下各程序段，并用大O记号表示其执行时间。 (1)(2) i=1;k=0; i=1;k=0; While(i 数据结构题集答案 数据结构题集 第一章绪论 一、单选题 1.在数据结构中，从逻辑上可以把数据结构分成【 C 】。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 2.数据结构在计算机内存中的表示是指【A 】。 A.数据的存储结构 B.数据结构 C.数据结构的逻辑结构 D.数据元素之间的关系 3. 【A 】是数据的最小单位，【B 】是数据的基本单位。 A.数据项 B.数据元素 C.信息项 D.表元素 4. 计算机所处理数据一般具有某种内在联系，这是指【 B 】。 A.数据与数据之间存在某种关系 B.数据元素与数据元素之间存在某种关系 C.元素内部存在某种结构 D. 数据项与数据项之间存在某种关系 5.算法分析的目的是【C 】。 A.找出数据结构的合理性 B.研究输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性 6.在存储数据时，不仅要考虑存储各数据元素的值，而且还要存储【 C 】。 A.数据处理的方法 B.数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 7.算法分析的主要任务是分析【D 】。 A.算法是否具有较好的可读性 B.算法中是否存储语法错误和逻辑错误 C.算法的功能是否符合设计要求 D.算法的执行时间与问题规模之间的关系。 8.数据的运算【A 】。 A.效率与采用何种存储结构有关 B.是根据存储结构来定义的 C.有算术运算和关系运算两大类 D.必须用程序设计语言来描述 9.算法的计算量的大小称为算法的【B 】。 A.效率 B.时间复杂度 C.现实性 D.难度 10.连续存储分配时，存储单元的地址【A 】。 A.一定连续 B.一定不连续 C.不一定连续 D.部分连续，部分不连续 二、判断题 1.数据元素是数据结构的最小单位【.×】。 2.数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构【×.】。 3.数据的逻辑结构指数据元素的各数据项之间的逻辑关系【×.】。 4.算法的优劣与算法的描述语言无关，但与使用的计算机有关【.×】。 5.数据结构的抽象操作的定义与具体实现有关【.×】。 三、填空题 1.数据的逻辑结构指数据元素之间的逻辑关系。 2.一个数据结构在计算机中的表示称为存储结构。 3.数据的物理结构主要包括顺序存储结构 第一章绪论 1.1 试写一个算法，自大到小依次输出顺序读入的三个数X、Y和Z的值。 void Desceding(int &x, int &y, int &z) { //将x、y和z按从大到小的顺序排列 if (x /* 计算1！+2！+…+n! */ sum2=0; for (i=1; i<=n; ++i){ p=1; for (j=1; j<=i; ++j) p=p*j; sum2=sum2+p; } }/* sum2 */ O(n2) (4) void sort(int a[],int n){ /* 将数组a中的元素按自小到大的顺序排列*/ for (i=1; i<=n-1; ++i){ k=i; for (j=i+1; j<=n; ++j) if (a[j] 一、单选题 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、紧凑结构和非紧凑结构 B、动态结构和静态结构 C、线性结构和非线性结构 D、内部结构和外部结构 7、数据的逻辑结构是指 ______ 关系的整体。 A、数据项之间逻辑 B、数据元素之间逻辑 C、数据类型之间 D、存储结构之间 8、以下是数据结构中 ______ 属非线性结构。 A、串 B、栈 C、队列 D、平衡二叉树 9、以下属于逻辑结构是 ______。 A、双链表 B、单链表 C、顺序表 D、有序表 10、以下不属于存储结构是______。 A、顺序表 B、线性表 C、邻接表 D、单链表 11、在计算机中存储数据时，通常不仅要存储各数据元素的值，而且还有存储 ______。 A、数据元素之间的关系 B、数据元素的类型 C、数据的处理方法 D、数据的存储方法 12、数据结构在计算机内存中的表示是指 ______。 A、数据的逻辑结构 B、数据结构 C、数据元素之间的关系 第一章绪论 一、选择题 1.以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 2．设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02， 06>，<03，07>，<03，08>，<03，09>}，则数据结构A是（）。 A. 线性结构 B. 树型结构 C. 物理结构 D. 图型结构 3．下面程序的时间复杂为（） for（i=1，s=0； i<=n； i++） {t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；} A. O(n) B.O(n2) C. O(n3) D. O(n4) 4．数据的最小单位是（）。 A.数据项 B. 数据类型 C.数据元素 D. 数据变量 5．程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的时间复杂度为（）。 A. O(n) B. O(nlog2n) C. O(n2) D. O(n3/2) 6．下列程序段的时间复杂度为（）。 for(i=0； i 第一章绪论 一．单项选择题 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．在定义 ADT 时，除数据对象和数据关系外，还需说明 ____________ 。 A. 数据元素 B. 算法 C. 基本操作 D. 数据项 7．计算算法的时间复杂度是属于一种。 A. 事前统计的方法 B. 事前分析估算的方法 C. 事后统计的方法 D. 事后分析估算的方法 8．在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是 _____________ 。 A. n2 B. nlogn C. n D. logn 9．设使用某算法对 n 个元素进行处理，所需的时间是 T(n)=100nlog2n+200n+2000 ，则该算法的渐近时间复杂度为______________ 。 A. O(1) B. O(n) C. O(200n) D. O(nlog2n) 10．有如下递归函数 fact(a) ，其时间复杂度为 _________ 。 int fact(int a) { if(n==0) retrun 1; else return(n*fact(n-1)); } A. 0(n) B. 0(n2) C. 0(n3) D. O(n4) 11 .线性表若米用链式存储结构时，要求内存中可用存储单兀的地址_______ 。 A.必须是连续的 B.部分地址必须是连续的 C. 一定是不连续的 D.连续不连续都可以 一、选择题 1．组成数据的基本单位是( c )。 (A)数据项 (B)数据类型 (C)数据元素(D)数据变量 2．数据结构是研究数据的( c )以及它们之间的相互关系。 (A)理想结构，物理结构 (B)理想结构，抽象结构 (c)物理结构，逻辑结构 (D)抽象结构，逻辑结构3．下列程序的时间复杂度为( A ) for(i=0;i 5．已知某算法的执行时间为， n为问题规模，则该算法的时间复杂度是( D )。 〔A)O(n) (B)O(n2) (C)O(log2n) (D)0(n3log2n) 二、填空题 1．一个算法，如果不论问题规模大小，运行所需 时间都一样，则该算法的时间复杂度是___常量阶__。 2．巳知某算法的执行时间为(n+n2)/2+log2 (2n+1)，n为问题规模，则该算法的时间复杂度是___ O(n2)__________。 3．数据结构有线性结构、树结构、___集合、_图 状结构或网状结构等几种逻辑结构。 4．数据结构有_逻辑结构和物理结构等两种物 理结构。 数据结构考试题库含答案 Revised by Jack on December 14,2020 数据结构习题集含答案 目录 选择题 第一章绪论 1. 数据结构这门学科是针对什么问题而产生的（A ） A、针对非数值计算的程序设计问题 B、针对数值计算的程序设计问题 C、数值计算与非数值计算的问题都针对 D、两者都不针对 2. 数据结构这门学科的研究内容下面选项最准确的是（D ） A、研究数据对象和数据之间的关系 B、研究数据对象 C、研究数据对象和数据的操作 D、研究数据对象、数据之间的关系和操作 3. 某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分， 那么下面关于数据对象、数据元素、数据项描述正确的是（C ） A、某班级的学生成绩表是数据元素，90分是数据项 B、某班级的学生成绩表是数据对象，90分是数据元素 C、某班级的学生成绩表是数据对象，90分是数据项 D、某班级的学生成绩表是数据元素，90分是数据元素 4. *数据结构是指（A ）。 A、数据元素的组织形式 B、数据类型 C、数据存储结构 D、数据定义 5. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。 A、存储结构 B、逻辑结构 C、链式存储结构 D、顺序存储结构 6. 算法分析的目的是（C ） A、找出数据的合理性 B、研究算法中的输入和输出关系 C、分析算法效率以求改进 D、分析算法的易懂性和文档型性 7. 算法分析的主要方法（A ）。 A、空间复杂度和时间复杂度 B、正确性和简明性 C、可读性和文档性 D、数据复杂性和程序复杂性 8. 计算机内部处理的基本单元是（B ） A、数据 B、数据元素 C、数据项 D、数据库 9. 数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存 储比顺序存储要（B ）。 A、低 B、高 C、相同 D、不好说 10. 算法的时间复杂度取决于（ C ） A 、问题的规模B、待处理数据的初始状态 C、问题的规模和待处理数据的初始状态 D、不好说 11. 数据结构既研究数据的逻辑结构，又研究物理结构，这种观点（B ）。 A、正确 B、错误 C、前半句对，后半句错 D、前半句错，后半句对 12. 在数据结构中，从逻辑上可以把数据结构分成（ C ） A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 13. 线性表的顺序存储结构是一种( )的存储结构，线性表的链式存储结构是一种 （ A ）存储结构。 A、随机存取 B、顺序存取 C、索引存取 D、散列存取 第一章绪论 一、选择题 1.组成数据的基本单位是（） （A）数据项（B）数据类型（C）数据元素（D）数据变量 参考答案：C 2.数据结构是研究数据的（）以及它们之间的相互关系。 （A）理想结构，物理结构（B）理想结构，抽象结构 （C）物理结构，逻辑结构（D）抽象结构，逻辑结构 参考答案：C 3.在数据结构中，从逻辑上可以把数据结构分成（） （A）动态结构和静态结构（B）紧凑结构和非紧凑结构 （C）线性结构和非线性结构（D）内部结构和外部结构 参考答案：C 4.数据结构是一门研究非数值计算的程序设计问题中计算机的（①）以及它们之间的（②）和运算等的学科。 ① （A）数据元素（B）计算方法（C）逻辑存储（D）数据映像 ② （A）结构（B）关系（C）运算（D）算法 参考答案：A B 5.算法分析的目的是（）。 （A）找出数据结构的合理性（B）研究算法中的输入和输出的关系 （C）分析算法的效率以求改进（D）分析算法的易懂性和文档性 参考答案：C 6.计算机算法指的是（①）,它必须具备输入、输出和（②）等5个特性。 ① （A）计算方法（B）排序方法（C）解决问题的有限运算序列（D）调度方法 ② （A）可执行性、可移植性和可扩充性（B）可行性、确定性和有穷性 （C）确定性、有穷性和稳定性（D）易读性、稳定性和安全性参考答案：C B 二、判断题 1.数据的机内表示称为数据的存储结构。（） 2.算法就是程序。（） 3.数据元素是数据的最小单位。（） 4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。（） 5.算法的时间复杂度取决于问题的规模和待处理数据的初态。（） 参考答案：1、√2、×3、×4、×5、√ 三、填空题 1.数据逻辑结构包括________、________、_________ 和_________四种类型,其中树形结构和图形结构合称为_____。 线性、树形、图形、集合；非线性（网状） 2.在线性结构中,第一个结点____前驱结点,其余每个结点有且只有______个前驱结点；最后一个结点______后续结点,其余每个结点有且只有_______个后续结点。 没有；1；没有；1 3.在树形结构中,树根结点没有_______结点,其余每个结点有且只有_______个前驱结点；叶子结点没有________结点,其余每个结点的后续结点可以_________。 前驱；1；后继；任意多个 4.在图形结构中,每个结点的前驱结点数和后续结点数可以_________。 任意多个 5.线性结构中元素之间存在________关系,树形结构中元素之间存在______关系,图形结构中元素之间存在_______关系。 一对一；一对多；多对多 6.算法的五个重要特性是_______、_______、______、_______、_______。 有穷性；确定性；可行性；输入；输出 7.数据结构的三要素是指______、_______和________。 数据元素；逻辑结构；存储结构 8.链式存储结构与顺序存储结构相比较,主要优点是________________________________。 插入、删除、合并等操作较方便 9.设有一批数据元素,为了最快的存储某元素,数据结构宜用_________结构,为了方便插入一个元素,数据结构宜用____________结构。 顺序存储；链式存储 数据结构耿国华课后答案 本文由edu_tech贡献 第一章绪论 一、问答题 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; 【解答】 i=1时： 1 = (1+1)×1/2 = (1+12)/2 i=2时：1+2 = (1+2)×2/2 = (2+22)/2 i=3时：1+2+3 = (1+3)×3/2 = (3+32)/2 … i=n时：1+2+3+……+n = (1+n)×n/2 = (n+n2)/2 x=x+1的语句频度为： f(n) = [ (1+2+3+……+n) + (12 + 22 + 32 + …… + n2 ) ] / 2 =[ (1+n)×n/2 + n(n+1)(2n+1)/6 ] / 2 =n(n+1)(n+2)/6 =n3/6+n2/2+n/3 区分语句频度和算法复杂度： O(f(n)) = O(n3) 四、试编写算法，求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…anxn的值Pn(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入ai(i=0,1,…,n),x 和n，输出为Pn(x0)。通常算法的输入和输出可采用下列两种方式之一： （1）通过参数表中的参数显式传递。 （2）通过全局变量隐式传递。 试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出数据结构练习 第一章 绪论
数据结构 习题 第一章 绪论
《数据结构》习题汇编01 第一章 绪论 试题
数据结构(第二版)习题
数据结构(C语言版)第一章绪论练习及答案
数据结构第一章 绪论 答案
算法与数据结构1—5章 课后习题
数据结构课程总结——第一章绪论
南京晓庄学院数据结构题库参考答案
数据结构题集答案
数据结构课后习题解答第一章 绪论
《数据结构》(C语言版) 第一章 绪论 习题及答案
通信数据结构第一章绪论习题
数据结构-数据结构-1绪论
数据结构第一章绪论练习题
数据结构考试题库含答案
数据结构习题及答案 (8)
数据结构耿国华课后答案
相关主题
文本预览