第二章 数据结构及其运算
考试要求：
1. C的数据结构及其定义：基本类型，构造类型，指针类型，空类型
2. C运算符的种类，运算优先级和结合性。
3. 不同类型数据之间的转换与运算。
4. C表达式类型和求值规则：赋值表达式，算术表达式，关系表达式，逻辑表达式，条件表达式，逗号表达式。
0（整型） 1.2(实型) 244 1.414
„a‟ （字符型）
70 70.5
100 100 0
60 59.9
Student
123456
1000 2 字节
问： 为什么要分数据类型？
答：2. 不同的数据类型存储格式不同
1. 不同的数据类型所实施的操作不同.
第2.1节 数据类型
简单语句 复合语句
1. C的数据类型分为：基本类型，构造类型，指针类型，空类型。
2. 基本类型又包括：整型，字符型，实型（单精度型，双精度型），枚举型
3. 构造类型又包括：数组类型，结构体类型和共用体类型。
C语言中的数据有常量和变量之分，但是它们都属于以上这些类型。
2.1.1 常量与变量
1. 常量 28 168 5.1 3.14 ‘a’ „y‟
在程序运行中，其值不能被改变的量叫做常量。常量可以划分为不同的类型，如12，0，-3为整型常量；4.6，-3.15为实型常量；‘a’,‟p‟为字符型常量。
也可以用一个标示符来代表一个常量。如：#define pi 3.1415 符号常量
#define afsj 168
2 变量 area=2
其值可以改变的量叫做 变量。
一个变量应该有一个名字，在内存中占据一定的 存储单元。
该存储单元中存放变量的值。
注意变量名和变量值。
变量名的命名规则和标示符的命名规则相同。
int a;(为a分配了一个存储单元)
a=2;
简单说标示符就是一个名字。
1 第2章
一、填空（每空1分，共13分）
1. 在顺序表中插入或删除一个元素，需要平均移动 表中一半元素，具体移动的元素个数与 表长和该元素在表中的位置
有关。
2. 线性表中结点的集合是 有限 的，结点间的关系是 一对一的。
3. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动
n-i+1 个元素。
4. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动 n-i 个元素。
5. 在顺序表中访问任意一结点的时间复杂度均为 O(1) ，因此，顺序表也称为 随机存取 的数据结构。
6. 顺序表中逻辑上相邻的元素的物理位置 必定相邻。单链表中逻辑上相邻的元素的物理位置 不一定 相邻。
7. 在单链表中，除了首元结点外，任一结点的存储位置由 其直接前驱结点的链域的值
指示。
8． 在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。
二、判断正误（在正确的说法后面打勾，反之打叉）（每小题1分，共10分）
（ × ）1. 链表的每个结点中都恰好包含一个指针。
答：错误。链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。
（ × ）2. 链表的物理存储结构具有同链表一样的顺序。
错，链表的存储结构特点是无序，而链表的示意图有序。
（ × ）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。
错，链表的结点不会移动，只是指针内容改变。
（ × ）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
错，混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。
（ × ）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
第一章 绪论
1、简述下列术语：数据、数据元素、数据对象、数据结构、数据存储、存储结构、数据类型和抽象数据类型。
2、数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括数组、链表、 栈、队列、优先级队列等; 非线性结构包括树、图等、这两类结构各自的特点是什么？
3、什么是算法? 算法的5个特性是什么? 试根据这些特性解释算法与程序的区别。
4、什么叫算法的时间复杂度？怎样表示算法的时间复杂度？
5、两个数据结构的逻辑结构和存储结构都相同，但是它们的运算集合中有一个运算的定义不一样，它们是否可以认作是同一个数据结构？为什么？
6、试画出与下列程序段等价的框图
(1)product = 1; i = 1;
while(i <= n){
product * = i ;
i++;
}
(2)i = 0;
do{
i++;
}while ((i!=n)&&(a[i])!=x);
7、已知如下程序段
for(i=n;n>=1;n--) {语句1}
{
x++； {语句2}
for(j=n;j<=i;j--)FOR j:=n {语句3}
y++; {语句4}
}；
求语句１到语句４的频度。
8、 按增长率从小到大的顺序排列下列各组函数： 2100 ，（3/2）n，（2/3）n，（4/3）n，n，n3/2，n2/3，n!，nn，log2n，n/log2n，log2(log2n)，nlog2n
9、试写一算法，自大至小依次顺序读入的三个整数X,Y,Z的值。
10、假设有A,B,C,D,E五个高等院校进行田径对抗赛，各院校的单项成绩均已存入计算机，并构成一张表，表中每行的形式为：
项目名称 性别 校名 成绩 得分
编写算法，处理上述表格，以统计各院校的男、女总分和团体总分，并输出。
141
第7章 树与森林
习 题
1． 一棵度为2的树与一棵二叉树有何区别？树与二叉树之间有何区别？
2． 对于图7-16所示的树，试给出：
（1）双亲数组表示法示意图。
（2）孩子链表表示法示意图。
（3）孩子兄弟链表表示法示意图。
3． 画出图7-17所示的森林经转换后所对应的二叉树，并指出在二叉链表中某结点所对应的森林中结点为叶子结点的条件。
I D E F G C B A
N M K J H
D B C
I G
H A F
E J
图7-16 第2题图
图7-17 第3题图
4． 将如图7-18所示的二叉树转换成相应的森林。
H G D E F C B A
图7-18 第4题图
5． 在具有n（n>1）个结点的各棵树中，其中深度最小的那棵树的深度是多少？它共有多少叶子和非叶子结点？其中深度最大的那棵树的深度是多少？它共有多少叶子和非叶子结点？
6． 画出和下列已知序列对应的树T。
（1）树的先根次序访问序列为：GFKDAIEBCHJ。
（2）树的后根次序访问次序为：DIAEKFCJHBG。
7． 画出和下列已知序列对应的森林F。
（1）森林的前序次序访问序列为：ABCDEFGHIJKL。
（2）森林的中序次序访问次序为：CBEFDGAJIKLH。
8． 对以孩子兄弟链表表示的树编写计算树的深度的算法。 142
第7章 树与森林
9． 对以孩子链表表示的树编写计算树的深度的算法。
10．对以双亲链表表示的树编写计算树的深度的算法。
