1.6习题与上机操作
1．选择题：⑴C⑵Ｃ⑶A⑷C⑸B⑹C
2．填空题：
⑴一对一一对多多对多
⑵算法的时间效率算法的空间效率
⑶线性结构非线性结构
⑷顺序存储链式存储索引存储散列存储
⑸字
⑹有穷性确定性
⑺n*(n+1)/2
⑻O(n3)
3.分析题:
⑴
⑵
4．应用题：
⑴答案
⑵答案：
⑶答案：
5．操作题
⑴已知一棵二叉树按顺序方式存储在数组A[1..n]中。设计算法，求出下标分别为i和j
的两个结点的最近的公共祖先结点的值。
①编程思想：二叉树顺序存储，是按完全二叉树的格式存储，利用完全二叉树双亲结点
与孩子结点编号间的关系，求下标为i和j的两结点的双亲，双亲的双亲等，直至找到最近
的公共祖先。
②C源程序：
typedefintElemType;
voidAncestor(ElemTypeA[],inti,intj)
{
while(i!=j)
if(i>j)
i=i/2;
else
j=j/2;
printf("所查结点的最近公共祖先的下标是%d,值是%d",i,A[i]);
}main()/*从下标为1的单元存放树结点*/
{intA[14]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14};
inti,j;
scanf("%d%d",&i,&j);
Ancestor(A,i,j);
}
⑵假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深
度的算法(注：已知树中结点数)
①编程思想：由于以双亲表示法作树的存储结构，找结点的双亲容易。因此我们可求出
每一结点的层次，取其最大层次就是树的深度。对每一结点，找其双亲，双亲的双亲，直至
结点双亲为0为止。
②C源程序：
#defineMAX_SIZE100
typedefintElemType;
typedefstructPTNode{
ElemTypedata;
intparent;}PTNode;
typedefstruct{
PTNodenodes[MAX_SIZE];
intn;}PTree;
Ch1绪论
1．下列与数据元素有关的叙述中，哪一个是不正确的（ B ）。
A．数据元素是数据的基本单位，即数据集合中的个体
B．数据元素是有独立含义的数据最小单位
C．数据元素又称结点
D．数据元素又称作记录
2．下列关于数据的逻辑结构的叙述中，哪一个是正确的（ A ）。
A．数据的逻辑结构是数据间关系的描述
B．数据的逻辑结构反映了数据在计算机中的存储方式
C．数据的逻辑结构分为顺序结构和链式结构
D．数据的逻辑结构分为静态结构和动态结构
3．数据的基本单位是（数据元素），在计算机中通常作为一个（整体）进行处理。
4．所有能输入到计算机中并被计算机程序处理的（符号）称为数据。
5．数据结构是一门研究非数值计算的程序设计问题中计算机的（① A）以及它们之间的（② B）和运算等的学科。
① A．数据元素 B．计算方法 C．逻辑存储 D．数据映像
② A．结构 B．关系 C．运算 D．算法
6．数据结构被形式的定义为（K，R），其中K是（①B）的有限集，R是K上的（②D）有限集。
① A．算法 B．数据元素 C．数据操作 D．逻辑结构
② A．操作 B．映像 C．存储 D．关系
7．具有线性结构的数据结构是（ D ）。
A．树 B．图 C．广义表 D．栈
8．在数据结构中，从逻辑上可以把数据结构分为（ D ）。
A．动态结构和静态结构 B．紧凑结构和非紧凑结构
C．内部结构和外部结构 D．线性结构和非线性结构
9．线性结构中元素之间存在（ A）关系。
A．一对一 B．一对多 C．多对一 D．多对多
10．数据逻辑结构包括（集合）、（线性结构 ）、（ 树形结构 ）和（ 图状结构）四种类型，树形结构和图形结构合称为（ 非线性结构）。
《数据结构(C语言版)》复习重点
重点在二、三、六、七、九、十章，考试内容两大类：概念，算法
第1章、绪论
1. 数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
2. 数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
3. 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
其4类基本结构：集合、线性结构、树形结构、图状结构或网状结构
4. 逻辑结构：是数据元素之间的逻辑关系的描述。
5. 物理结构（存储结构）：是数据结构在计算机中的表示（又称映像）。
其4种存储结构：顺序存数结构、链式存数结构、索引存数结构、散列存数结构
6. 算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。
其5个重要特性：有穷性、确定性、可行性、输入、输出
7. 时间复杂度：算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间度量记作，T(n)=O(f(n)) ；他表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称做算法的渐进时间复杂度，简称时间复杂度。
例如： (a) {++x;s=0;}
(b) for(i=1;i<=n;++i){++x;s += x;}
(c) for(j=1;j<=n;++j)
for(k=1;k<=n;++k){++x;s += x;}
含基本操作“x增1”的语句的频度分别为1、n和n²，则这3个程序段的时间复杂度分别为O(1)、O(n)和O(n²)，分别称为常量阶、线性阶和平方阶。还可呈现对数阶O(log n)、指数阶O(2的n次方)等。
8. 空间复杂度：算法所需存储空间的度量记作，S(n)=O(f(n))。
第2章、线性表
1. 线性表：是最常用最简单的一种数据结构，一个线性表是n个数据元素的有限序列。
2. 线性表的顺序存储结构：是用一组地址连续的存储单元依次存储线性表的数据元素。其特点为逻辑关系上相邻的两个元素在物理位置上也相邻，可以随机存取表中任一元素。
第1章 绪论
教材中练习题及参考答案
1. 简述数据与数据元素的关系与区别。
答：凡是能被计算机存储、加工的对象统称为数据，数据是一个集合。数据元素是数
据的基本单位，是数据的个体。数据元素与数据之间的关系是元素与集合之间的关系。
2. 采用二元组表示的数据逻辑结构S=，其中D={a，b，„，i}，R={r}，r={
b>，，，，，，，}，问关系r是什么类型
的逻辑结构？哪些结点是开始结点，哪些结点是终端结点？
答：该逻辑结构为树形结构，其中a结点没有前驱结点，它是开始结点，b、e、i和g、
结点没有后继结点，它们都是终端结点。
3. 简述数据逻辑结构与存储结构的关系。
答：在数据结构中，逻辑结构与计算机无关，存储结构是数据元素之间的逻辑关系在
计算机中的表示。存储结构不仅将逻辑结构中所有数据元素存储到计算机内存中，而且还
要在内存中存储各数据元素间的逻辑关系。通常情况下，一种逻辑结构可以有多种存储结
构，例如，线性结构可以采用顺序存储结构或链式存储结构表示。
4. 简述数据结构中运算描述和运算实现的异同。
答：运算描述是指逻辑结构施加的操作，而运算实现是指一个完成该运算功能的算法。
它们的相同点是，运算描述和运算实现都能完成对数据的“处理”或某种特定的操作。不
同点是，运算描述只是描述处理功能，不包括处理步骤和方法，而运算实现的核心则是设
计处理步骤。
5. 数据结构和数据类型有什么区别？
答：数据结构是相互之间存在一种或多种特定关系的数据元素的集合，一般包括三个
方面的内容，即数据的逻辑结构、存储结构和数据的运算。而数据类型是一个值的集合和
定义在这个值集上的一组运算的总称，如C语言中的short int数据类型是由-32768～32767
（16位机）的整数和+、-、*、/、%等运算符构成。
6. 在C/C++中提供了引用运算符，简述其在算法描述中的主要作用。
答：在算法设计中，一个算法通常用一个或多个C/C++函数来实现，在C/C++函数之
