数据结构考研讲义
目录
绪论 (3)
0.1 基本概念 (3)
第一章线性表 (4)
1.1 线性表的定义 (4)
1.2 线性表的实现 (4)
1.2.2 线性表的链式存储结构 (6)
第二章栈、队列和数组 (11)
2.1 栈 (11)
2.2 队列 (15)
2.3 特殊矩阵的压缩存储 (17)
2.3.1 数组 (17)
2.3.2 特殊矩阵 (17)
第三章树与二叉树 (20)
3.1 树的概念 (20)
1.树的定义 (20)
2．相关术语 (20)
3.2 二叉树 (21)
3.2.1 定义与性质 (21)
3.2.2 二叉树的存储 (22)
3.2.3 二叉树的遍历 (23)
3.2.4 线索二叉树 (25)
3.3 树和森林 (29)
3.3.1 树的存储结构 (29)
3.3.2 森林和二叉树的转换 (29)
3.3.3 树和森林的遍历 (30)
3.4 哈夫曼（Huffman）树和哈夫曼编码 (31)
第四章图 (32)
4.1 图的概念 (32)
4.2 图的存储及基本操作 (33)
4.2.1 邻接矩阵 (33)
4.2.2 邻接表 (33)
4.3 图的遍历 (35)
4.3.1 深度优先搜索 (35)
4.3.2 广度优先搜索 (35)
4.4 图的基本应用 (37)
4.4.1 最小生成树 (37)
4.4.2 最短路径 (37)
4.4.3 拓扑排序 (39)
4.4.4 关键路径 (40)
第五章查找 (42)
5.1 查找的基本概念 (42)
5.2 顺序查找法 (43)
5.3 折半查找法 (44)
5.4 动态查找树表 (45)
1
5.4.1 二叉排序树 (45)
5.4.2 平衡二叉树 (47)
5.4.3B 树及其基本操作、B+树的基本概念 (49)
5.5 散列表 (51)
5.5.2 常用的散列函数 (51)
5.5.3 处理冲突的方法 (52)
5.5.4 散列表的查找 (52)
5.5.5 散列表的查找分析 (53)
第六章排序 (54)
6.1 插入排序 (54)
6.1.1 直接插入排序 (54)
6.1.2 折半插入排序 (54)
6.2 冒泡排序 (55)
6.3 简单选择排序 (56)
6.4 希尔排序 (57)
6.5 快速排序 (58)
6.6 堆排序 (60)
6.7 二路归并排序 (62)
6.8 基数排序 (63)
6.9 各种内部排序算法的比较 (64)
2
绪论
0.1 基本概念
1、数据结构
数据结构是指互相之间存在着一种或多种关系的数据元素的集合。
数据结构是一个二元组Data_Structure ＝（D，R），其中，D 是数据元素的有限集，R 是D 上关系的有限集。
2、逻辑结构：是指数据之间的相互关系。通常分为四类结构：
（1）集合：结构中的数据元素除了同属于一种类型外，别无其它关系。
（2）线性结构：结构中的数据元素之间存在一对一的关系。
（3）树型结构：结构中的数据元素之间存在一对多的关系。
（4）图状结构：结构中的数据元素之间存在多对多的关系。
3、存储结构：是指数据结构在计算机中的表示，又称为数据的物理结构。通常由四种基本的存储方法实现：
（1）顺序存储方式。数据元素顺序存放，每个存储结点只含一个元素。存储位置反映数据元素间的逻辑关系。存储密度大。但有些操作（如插入、删除）效率较差。
（2）链式存储方式。每个存储结点除包含数据元素信息外还包含一组（至少一个）指针。指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操作（如插入、删除等），但存储空间开销大（用于指针），另外不能折半查找等。
（3）索引存储方式。除数据元素存储在一组地址连续的内存空间外，还需建立一个索引表，索引表中索引指示存储结点的存储位置（下标）或存储区间端点（下标）。
（4）散列存储方式。通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将散列函数的值解释成关键字所在元素的存储地址。其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。
2 算法和算法的衡量
1、算法是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。算法具有下列特性：⑴有穷性⑵确定性⑶可行性⑷输入⑸输出。
算法和程序十分相似，但又有区别。程序不一定具有有穷性，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。一个算法若用程序设计语言来描述，则它就是一个程序。
2、算法的时间复杂度：以基本运算的原操作重复执行的次数作为算法的时间度量。一般情况下，算法中基本运算次数T(n)是问题规模n（输入量的多少，称之为问题规模）的某个函数f(n)，记作：
T(n) ＝Ο(f(n))；也可表示T(n) ＝m(f(n))，其中m 为常量。记号“O”读作“大O”，它表示随问题规模n 的增大，算法执行时间T(n)的增长率和f(n)的增长率相同。
注意：有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。
常见的渐进时间复杂度有：
Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜Ο(2n) ＜O(n!) ＜O(nn)。
3、算法的空间复杂度：是对一个算法在运行过程中临时占用的存储空间大小的量度。只需要
分析除输入和程序之外的辅助变量所占额外空间。
原地工作：若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作，空
间复杂度为O(1)。
3
第一章线性表
1.1 线性表的定义
线性表是一种线性结构，在一个线性表中数据元素的类型是相同的，或者说线性表是由同一类型的数据元素构成的线性结构，定义如下：
线性表是具有相同数据类型的n(n≥0)个数据元素的有限序列，通常记为：
(a1，a2，…ai-1，ai，ai+1，…an)
其中n为表长，n＝0 时称为空表。
需要说明的是：ai为序号为i 的数据元素（i=1,2,…,n），通常将它的数据类型抽象为ElemType，ElemType根据具体问题而定。
1.2 线性表的实现
1.2.1 线性表的顺序存储结构
1.顺序表
线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称其为顺序表。因为内存中的地址空间是线性的，因此，用物理上的相邻实现数据元素之间的逻辑相邻关系是既简单又自然的。
设a１的存储地址为Loc(a１)，每个数据元素占d个存储地址，则第i个数据元素的地址为：
Loc(ai)=Loc(a１)+(i-1)*d 1≤i≤n
这就是说只要知道顺序表首地址和每个数据元素所占地址单元的个数就可求出第i个数据元素的地址来，这也是顺序表具有按数据元素的序号随机存取的特点。
线性表的动态分配顺序存储结构：
#define LIST_INIT_SIZE 100 //存储空间的初始分配量
#define LISTINCREMENT 10 //存储空间的分配增量
typedef struct{
ElemType *elem; //线性表的存储空间基址
int length; //当前长度
int listsize; //当前已分配的存储空间
}SqList;
2.顺序表上基本运算的实现
（1）顺序表的初始化
顺序表的初始化即构造一个空表，这对表是一个加工型的运算，因此，将L设为引用参数，
首先动态分配存储空间，然后，将length置为0，表示表中没有数据元素。
int Init_SqList (SqList &L){
L.elem = (ElemType * )malloc(LIST_INIT_SIZE * sizeof(ElemType));
if (!L.elem) exit (OVERFLOW); //存储分配失败
L.length=0;
L. listsize = LIST_INIT_SIZE; //初始存储容量
return OK;
}
（2）插入运算
线性表的插入是指在表的第i(i的取值范围：1≤i≤n+1)个位置上插入一个值为x 的新元素，
4
插入后使原表长为n的表:
(a1，a2，... ，ai-1，ai，ai+1，... ，an)
成为表长为n+1 表:
(a1，a2，...，ai-1，x，ai，ai+1，...，an ) 。
顺序表上完成这一运算则通过以下步骤进行：
①将ai～an 顺序向下移动，为新元素让出位置；（注意数据的移动方向：从后往前依次后移一个元素）
②将x 置入空出的第i个位置；
③修改表长。
int Insert_SqList (SqList &L，int i，ElemType x){
if (i < 1 || i > L.length+1) return ERROR; // 插入位置不合法
if (L.length >= L.listsize) return OVERFLOW; // 当前存储空间已满,不能插入
//需注意的是，若是采用动态分配的顺序表，当存储空间已满时也可增加分配
q = &(L.elem[i-1]); // q 指示插入位置
for (p = &(L.elem[L.length-1]); p >= q; --p)
*(p+1) = *p; // 插入位置及之后的元素右移
*q = e; // 插入e
++L.length; // 表长增1
return OK;
}
顺序表上的插入运算，时间主要消耗在了数据的移动上，在第i个位置上插入x ，从ai 到an 都要向下移动一个位置，共需要移动n－i＋1个元素。
（3）删除运算
线性表的删除运算是指将表中第i （i 的取值范围为：1≤i≤n）个元素从线性表中去掉，
删除后使原表长为n 的线性表：
(a1，a2，... ，ai-1，ai，ai+1，...，an)
成为表长为n－1 的线性表：
(a1，a2，... ，ai-1，ai+1，... ，an)。
顺序表上完成这一运算的步骤如下：
①将ai+1～an 顺序向上移动；（注意数据的移动方向：从前往后依次前移一个元素）
②修改表长。
int Delete_SqList (SqList &L;int i) {
if ((i < 1) || (i > L.length)) return ERROR; // 删除位置不合法
p = &(L.elem[i-1]); // p 为被删除元素的位置
e = *p; // 被删除元素的值赋给e
q = L.elem+L.length-1; // 表尾元素的位置
for (++p; p <= q; ++p)
*(p-1) = *p; // 被删除元素之后的元素左移
--L.length; // 表长减1
return OK;
}
顺序表的删除运算与插入运算相同，其时间主要消耗在了移动表中元素上，删除第i个元素时，其后面的元素ai+1～an 都要向上移动一个位置，共移动了n-i 个元素，顺序表的插入、删除需移动大量元素O(n)；但在尾端插入、删除效率高O(1)。
5
1.2.2 线性表的链式存储结构
1.2.2.1 单链表
1.链表表示
链表是通过一组任意的存储单元来存储线性表中的数据元素的。为建立起数据元素之间的线性关系，对每个数据元素ai，除了存放数据元素的自身的信息ai 之外，还需要和ai一起存放其后继ai+1 所在的存储单元的地址，这两部分信息组成一个“结点”，结点的结构如图所示。
其中，存放数据元素信息的称为数据域，存放其后继地址的称为指针域。因此n个元素的线性表通过每个结点的指针域拉成了一个“链”，称之为链表。因为每个结点中只有一个指向后继的指针，所以称其为单链表。
线性表的单链表存储结构C语言描述下：
typedef struct LNode{
ElemType data; // 数据域
struct LNode *next; // 指针域
}LNode，*LinkList;
LinkList L；// L 为单链表的头指针
通常用“头指针”来标识一个单链表，如单链表L、单链表H等，是指某链表的第一个结点的地址放在了指针变量L、H 中，头指针为“NULL”则表示一个空表。
2.单链表上基本运算的实现
(1)建立单链表
单链表结点结构
data next
●头插法——在链表的头部插入结点建立单链表
链表与顺序表不同，它是一种动态管理的存储结构，链表中的每个结点占用的存储空间不是预先分配，而是运行时系统根据需求而生成的，因此建立单链表从空表开始，每读入一个数据元素则申请一个结点，然后插在链表的头部。
LinkList CreateListF ( ){
LinkList L=NULL；//空表
LNode *s;
int x; //设数据元素的类型为int
scanf(＂%d＂,&x);
while (x!=flag) {
s=(LNode *)malloc(sizeof(LNode));
s->data=x;
s->next=L; L=s;
scanf (＂%d＂,&x);
}
return L;
}
●尾插法——在单链表的尾部插入结点建立单链表
头插入建立单链表简单，但读入的数据元素的顺序与生成的链表中元素的顺序是相反的，若希望次序一致，则用尾插入的方法。因为每次是将新结点插入到链表的尾部，所以需加入一个指针r 用来始终
6
指向链表中的尾结点，以便能够将新结点插入到链表的尾部。
初始状态，头指针L=NULL，尾指针r=NULL; 按线性表中元素的顺序依次读入数据元素，不是结束标志时，申请结点，将新结点插入到r 所指结点的后面，然后r 指向新结点（注意第一个结点有所不同）。
LinkList CreateListR1 ( ){
LinkList L=NULL;
LNode *s,*r=NULL;
int x; //设数据元素的类型为int
scanf(＂%d＂,&x);
while (x!=flag) {
s=(LNode *)malloc(sizeof(LNode));
s->data=x;
if (L==NULL) L=s; //第一个结点的处理
else r->next=s; //其它结点的处理
r=s; //r 指向新的尾结点
scanf(＂%d＂,&x);
}
if ( r!=NULL) r->next=NULL; //对于非空表，最后结点的指针域放空指针
return L;
}
在算法CreateListR1中，第一个结点的处理和其它结点是不同的，原因是第一个结点加入时链表为空，它没有直接前驱结点，它的地址就是整个链表的指针，需要放在链表的头指针变量中；而其它结点有直接前驱结点，其地址放入直接前驱结点的指针域。“第一个结点”的问题在很多操作中都会遇到，如在链表中插入结点时，将结点插在第一个位置和其它位置是不同的，在链表中删除结点时，删除第一个结点和其它结点的处理也是不同的，等等。
为了方便操作，有时在链表的头部加入一个“头结点”，头结点的类型与数据结点一致，标识链表的头指针变量L中存放该结点的地址，这样即使是空表，头指针变量L也不为空了。
头结点的加入使得“第一个结点”的问题不再存在，也使得“空表”和“非空表”的处理成为一致。头结点的加入完全是为了运算的方便，它的数据域无定义，指针域中存放的是第一个数据结点的地址，空表时为空。
尾插法建立带头结点的单链表，将算法CreateListR1改写成算法CreateListR2形式。
LinkList CreateListR2( ){
LinkList L=(LNode *)malloc(sizeof(LNode));
L->next=NULL；//空表
LNode *s,*r=L;
int x; //设数据元素的类型为int
scanf(＂%d＂,&x);
while (x!=flag) {
s=(LNode *)malloc(sizeof(LNode));
s->data=x;
r->next=s;
r=s; //r 指向新的尾结点
scanf(＂%d＂,&x);
}
r->next=NULL;
7
8 return L;
}
因此，头结点的加入会带来以下两个优点：
第一个优点：由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其它位置上的操作一致，无需进行特殊处理；
第二个优点：无论链表是否为空，其头指针是指向头结点在的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。在以后的算法中不加说明则认为单链表是带头结点的。
(2)查找操作
●按序号查找 Get_LinkList(L,i)
从链表的第一个元素结点起，判断当前结点是否是第i 个，若是，则返回该结点的指针，否则继续后一个，表结束为止，没有第ｉ个结点时返回空。
LNode * Get_LinkList(LinkList L, int i); {
LNode * p=L;
int j=0;
while (p->next !=NULL && j
p=p->next; j++;
}
if (j==i) return p;
else return NULL;
}
(3)插入运算
●后插结点：设p 指向单链表中某结点， s 指向待插入的值为x 的新结点，将*s 插入到*p 的后面，插入示意图如图所示。
操作如下：
①s->next=p->next;
②p->next=s;
注意：两个指针的操作顺序不能交换。
(4)删除运算
●删除结点
设p 指向单链表中某结点，删除*p 。操作过程如图。要实现对结点*p 的删除，首先要找到*p 的前驱结点*q ，然后完成指针的操作即可。
操作如下：①
q=L;
9 while (q->next!=p)
q=q->next; //找*p 的直接前驱
②q->next=p->next;
free(p);
因为找*p 前驱的时间复杂度为O(n)，所以该操作的时间复杂度为O(n)
通过上面的基本操作我们得知：
(1) 单链表上插入、删除一个结点，必须知道其前驱结点。
(2) 单链表不具有按序号随机访问的特点，只能从头指针开始一个个顺序进行。
1.2.2.2 循环链表
对于单链表而言，最后一个结点的指针域是空指针，如果将该链表头指针置入该指针域，则使得链表头尾结点相连，就构成了单循环链表。
在单循环链表上的操作基本上与非循环链表相同，只是将原来判断指针是否为 NULL 变为是否是头指针而已，没有其它较大的变化。
对于单链表只能从头结点开始遍历整个链表，而对于单循环链表则可以从表中任意结点开始遍历整个链表，不仅如此，有时对链表常做的操作是在表尾、表头进行，此时可以改变一下链表的标识方法，不用头指针而用一个指向尾结点的指针 R 来标识，可以使得操作效率得以提高。
1.2.2.3 双向链表
单链表的结点中只有一个指向其后继结点的指针域 next ，因此若已知某结点的指针为 p ，其后继结点的指针则为 p->next ，而找其前驱则只能从该链表的头指针开始，顺着各结点的next 域进行，也就是说找后继的时间性能是 O(1)，找前驱的时间性能是 O(n)，如果也希望找前驱的时间性能达到 O(1)，则只能付出空间的代价：每个结点再加一个指向前驱的指针域，结点的结构为如图所示，用这种结点组成的链表称为双向链表。
线性表的双向链表存储结构C 语言描述下：
typedef struct DuLNode{
ElemType data;
struct DuLNode *prior,*next;
}DuLNode,*DuLinkList;
和单链表类似，双向链表通常也是用头指针标识，也可以带头结点。
（ 1）双向链表中结点的插入：设 p 指向双向链表中某结点， s 指向待插入的值为 x 的新结点，将*s 插入到*p 的前面，插入示意图如所示。
操作如下：
① s->prior=p->prior;
② p->prior->next=s;
③
s->next=p;
④p->prior=s;
指针操作的顺序不是唯一的，但也不是任意的，操作①必须要放到操作④的前面完成，否则*p 的前驱结点的指针就丢掉了。
（2）双向链表中结点的删除：设p 指向双向链表中某结点，删除*p。操作示意图如图所示。
操作如下：
①p->prior->next=p->next;
②p->next->prior=p->prior;
free(p);
1.2.2.4 顺序表和链表的比较
总之，两种存储结构各有长短，选择那一种由实际问题中的主要因素决定。通常“较稳定”
的线性表选择顺序存储，而频繁做插入删除的即动态性较强的线性表宜选择链式存储。
10
第二章栈、队列和数组
2.1 栈
2.1.1 栈的定义
栈是限制在表的一端进行插入和删除的线性表。允许插入、删除的这一端称为栈顶，另一个固定端称为栈底。当表中没有元素时称为空栈。
2.1.2 栈的存储实现和运算实现
栈是运算受限的线性表，线性表的存储结构对栈也是适用的，只是操作不同而已。
利用顺序存储方式实现的栈称为顺序栈。与线性表类似，栈的动态分配顺序存储结构如下：
#define STACK_INIT_SIZE 100 //存储空间的初始分配量
#define STACKINCREMENT 10 //存储空间的分配增量
typedef struct{
SElemType *base; //在栈构造之前和销毁之后，base 的值为NULL
SElemType *top; //栈顶指针
int stacksize; //当前已分配的存储空间
}SqStack;
需要注意，在栈的动态分配顺序存储结构中，base 始终指向栈底元素，非空栈中的top始终在栈顶元素的下一个位置。
下面是顺序栈上常用的基本操作的实现。
（1）入栈：若栈不满，则将e 插入栈顶。
int Push (SqStack &S, SElemType e) {
if (S.top-S.base>=S.stacksize)
{……} //栈满，追加存储空间
*S.top++ = e;//top 始终在栈顶元素的下一个位置
return OK;
}
（2）出栈：若栈不空，则删除S 的栈顶元素，用e 返回其值，并返回OK，否则返回ERROR。
int Pop (SqStack &S, SElemType &e) {
if (S.top==S.base) return ERROR;
e = *--S.top;
return OK;
}
出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。通常栈空常作为一种控制转移的条件。
2.1.3 栈的应用举例
由于栈的“先进先出”特点，在很多实际问题中都利用栈做一个辅助的数据结构来进行求解，下面通过几个例子进行说明。
1．数制转换
十进制数N 和其他d 进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于下列原理：
11
假设现要编制一个满足下列要求的程序：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。由于上述计算过程是从低位到高位顺序产生八进制数的各个数位，而打印输出，一般来说应从高位到低位进行，恰好和计算过程相反。因此，若将计算过程中得到的八进制数的各位顺序进栈，则按出栈序列打印输出的即为与输入对应的八进制数。
算法思想：当N>0 时重复（1），（2）
（1）若N≠0，则将N % r 压入栈s 中，执行（2）;若N=0，将栈s 的内容依次出栈，算法结束。
（2）用N / r 代替N。
void conversion () {
InitStack(S); // 构造空栈
scanf ("%d",N);
while (N) {
Push(S, N % 8);
N = N/8;
}
while (!StackEmpty(S)) {
Pop(S,e);
printf ( "%d", e );
}}
2..表达式求值
表达式求值是程序设计语言编译中一个最基本的问题，它的实现也是需要栈的加入。下面的算法是由运算符优先法对表达式求值。在此仅限于讨论只含二目运算符的算术表达式。
（1）中缀表达式求值：
中缀表达式：每个二目运算符在两个运算量的中间，假设所讨论的算术运算符包括：+ 、- 、*、/、%、^（乘方）和括号（）。
设运算规则为：
．运算符的优先级为：（）——> ^ ——>＊、/、%——> +、- ；
．有括号出现时先算括号内的，后算括号外的，多层括号，由内向外进行；
．乘方连续出现时先算最右面的。
表达式作为一个满足表达式语法规则的串存储，如表达式“3*2^（4+2*2-１*3）-5”,它的的求值过程为：自左向右扫描表达式，当扫描到3*2 时不能马上计算，因为后面可能还有更高的运算，正确的处理过程是：需要两个栈：对象栈s1 和运算符栈s2。当自左至右扫描表达式的每一个字符时，若当前字符是运算对象，入对象栈，是运算符时，若这个运算符比栈顶运算符高则入栈，继续向后处理，若这个运算符比栈顶运算符低则从对象栈出栈两个运算量，从运算符栈出栈一个运算符进行运算，并将其运算结果入对象栈，继续处理当前字符，直到遇到结束符。
12
13
中缀表达式表达式 “3*2^（ 4+2*2-１*3） -5”求值过程中两个栈的状态情况见图所示。
图 中缀表达式 3*2^（ 4+2*2-1*3） -5 的求值过程
为了处理方便，编译程序常把中缀表达式首先转换成等价的后缀表达式，后缀表达式的运算符在运算对象之后。在后缀表达式中，不在引入括号，所有的计算按运算符出现的顺序，严格从左向右进行，而不用再考虑运算规则和级别。
中缀表达式“3*2^（ 4+2*2-1*3） -5 ”的后缀表达式为： “32422*+13*-^*5-”。
（ 2）后缀表达式求值
计算一个后缀表达式，算法上比计算一个中缀表达式简单的多。这是因为表达式中即无括号又无优先级的约束。具体做法：只使用一个对象栈，当从左向右扫描表达式时，每遇到一个操作数就送入栈中保存，每遇到一个运算符就从栈中取出两个操作数进行当前的计算，然后把结果再入栈，直到整个表达式结束，这时送入栈顶的值就是结果。
（ 3） 中缀表达式转换成后缀表达式：
将中缀表达式转化为后缀表达示和前述对中缀表达式求值的方法完全类似，但只需要运算符栈，遇到运算对象时直接放后缀表达式的存储区，假设中缀表达式本身合法且在字符数组 A
中，转换后
的后缀表达式存储在字符数组B 中。具体做法：遇到运算对象顺序向存储后缀表达式的B 数组中存放，遇到运算符时类似于中缀表达式求值时对运算符的处理过程，但运算符出栈后不是进行相应的运算，而是将其送入B 中存放。具体算法在此不再赘述。
3．栈与递归
在高级语言编制的程序中，调用函数与被调用函数之间的链接和信息交换必须通过栈进行。当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三件事:
（1）将所有的实在参数、返回地址等信息传递给被调用函数保存;
（2）为被调用函数的局部变量分配存储区;
（3）将控制转移到被调用函数的入口。
从被调用函数返回调用函数之前，应该完成:
（1）保存被调函数的计算结果;
（2）释放被调函数的数据区;
（3）依照被调函数保存的返回地址将控制转移到调用函数。
多个函数嵌套调用的规则是：后调用先返回，此时的内存管理实行“栈式管理”。
递归函数的调用类似于多层函数的嵌套调用，只是调用单位和被调用单位是同一个函数而已。在每次调用时系统将属于各个递归层次的信息组成一个活动记录（ActivaTion Record），这个记录中包含着本层调用的实参、返回地址、局部变量等信息，并将这个活动记录保存在系统的“递归工作栈”中，每当递归调用一次，就要在栈顶为过程建立一个新的活动记录，一旦本次调用结束，则将栈顶活动记录出栈，根据获得的返回地址信息返回到本次的调用处。
将递归程序转化为非递归程序时常使用栈来实现。
14
15
2.2 队列
2.2.1 队列的定义及基本运算
栈是一种后进先出的数据结构，在实际问题中还经常使用一种“先进先出”的数据结构：即插入在表一端进行，而删除在表的另一端进行，将这种数据结构称为队或队列，
把允许插入的一端叫队尾(rear) ；把允许删除的一端叫队头(front)。
2.2.2 队列的存储实现及运算实现
与线性表、栈类似，队列也有顺序存储和链式存储两种存储方法。
1．顺序队列
循环队列的类型定义如下：
#define MAXQSIZE 100 //最大队列长度
typedef struct {
QElemType *base; //动态分配存储空间
int front; //头指针，若队列不空，指向队列头元素
int rear; //尾指针，若队列不空，指向队列尾元素的下一个位置
} SqQueue;
下面是循环队列上基本操作的实现。
（ 3）求循环队列元素个数：
int QueueLength （ SqQueue Q ） {
return (Q.rear-Q.front+MAXQSIZE) %MAXQSIZE ；
}
2．链队列
链式存储的队称为链队列。和链栈类似，用单链表来实现链队列，根据队的先进先出原 则，为了操作上的方便，分别需要一个头指针和尾指针。
定义一个指向链队列的指针： LinkQueue Q;
下面是链队列的基本运算的实现。
（ 1）入队
int EnQueue (LinkQueue &Q, QElemType e) {
QNode *p;
p = （QNode *）malloc（sizeof（QNode））;
p->data = e;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return OK;
}
（2）出队
int DeQueue (LinkQueue &Q, QElemType &e) {
if (Q.front == Q.rear) return ERROR; //队空，出队失败
p = Q.front->next;
e = p->data; //队头元素放e 中
Q.front->next = p->next;
if(Q.rear==p) Q.rear= Q.front; //只有一个元素时，此时还要修改队尾指针
free (p);
return OK;
}
3．除了栈和队列之外，还有一种限定性数据结构是双端队列。
（1）双端队列：可以在双端进行插入和删除操作的线性表。
（2）输入受限的双端队列：线性表的两端都可以输出数据元素，但是只能在一端输入数据元素。（3）输出受限的双端队列：线性表的两端都可以输入数据元素，但是只能在一端输出数据元素。
16
2.3 特殊矩阵的压缩存储
2.3.1 数组
数组可以看作线性表的推广。数组作为一种数据结构其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型，数组是一个具有固定格式和数量的数据有序集，每一个数据元素有唯一的一组下标来标识，因此，在数组上不能做插入、删除数据元素的操作。通常在各种高级语言中数组一旦被定义，每一维的大小及上下界都不能改变。
现在来讨论数组在计算机中的存储表示。通常，数组在内存被映象为向量，即用向量作为数组的一种存储结构，这是因为内存的地址空间是一维的，数组的行列固定后，通过一个映象函数，则可根据数组元素的下标得到它的存储地址。
对于一维数组按下标顺序分配即可。对多维数组分配时，要把它的元素映象存储在一维存储器中，一般有两种存储方式：一是以行为主序（或先行后列）的顺序存放，即一行分配完了接着分配下一行。另一种是以列为主序（先列后行）的顺序存放，即一列一列地分配。
以行为主序的分配规律是：最右边的下标先变化，即最右下标从小到大，循环一遍后，右边第二个下标再变，…，从右向左，最后是左下标。以列为主序分配的规律恰好相反：最左边的下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变，…，从左向右，最后是右下标。
设有m×n 二维数组Amn，下面我们看按元素的下标求其地址的计算：
以“以行为主序”的分配为例：设数组的基址为LOC(a11)，每个数组元素占据 d 个地址单元，那么aij 的物理地址可用一线性寻址函数计算：
LOC(aij) = LOC(a11) + ( (i-1)*n + j-1 ) * d
这是因为数组元素aij 的前面有i-1 行，每一行的元素个数为n，在第i 行中它的前面还有j-1 个数组元素。
在C 语言中，数组中每一维的下界定义为0，则：
LOC(aij) = LOC(a00) + ( i*n + j ) * d
推广到一般的二维数组：A[c1..d1] [c2..d2]，则aij 的物理地址计算函数为：
LOC(aij)=LOC(a c1 c2)+( (i- c1) *( d2 - c2 + 1)+ (j- c2) )d
2.3.2 特殊矩阵
对于一个矩阵结构显然用一个二维数组来表示是非常恰当的，矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为1。但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，比如常见的一些特殊矩阵，如三角矩阵、对称矩阵、对角矩阵、稀疏矩阵等，从节约存储空间的角度考虑，这种存储是不太合适的，看起来存储密度仍为1，但实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储空间，我们可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。
1.对称矩阵
对称矩阵的特点是：在一个n 阶方阵中，有aij=aji ，其中1≤i , j≤n，对称矩阵关于主对角线对称，因此只需存储上三角或下三角部分即可，比如，我们只存储下三角中的元素aij，其特点是中j≤i 且1≤i≤n，对于上三角中的元素aij ，它和对应的aji 相等，因此当访问的元素在上三角时，直接去访问和它对应的下三角元素即可，这样，原来需要n*n 个存储单元，现在只需要n(n+1)/2 个存储单元了，节约了n(n-1)/2 个存储单元。
对下三角部分以行为主序顺序存储到一个向量中去，在下三角中共有n*(n+1)/2 个元素，
17
因此，不失一般性，设存储到向量SA[n(n+1)/2]中，存储顺序可用图示意，这样，原矩阵下三角中的某一个元素aij 则具体对应一个sak，下面的问题是要找到k 与i、j 之间的关系。
对于下三角中的元素aij，其特点是：i≥j 且1≤i≤n，存储到SA 中后，根据存储原则，它前面有i-1 行，共有1+2+…+i-1=i*(i-1)/2 个元素，而aij 又是它所在的行中的第j 个，所以在上面的排列顺序中，aij 是第i*(i-1)/2+j 个元素，因此它在SA 中的下标k 与i、j 的关系为：
k=i*(i-1)/2+j-1 (０≤k 若i k=j*(j-1)/2+i-1 (０≤k 综上所述，对于对称矩阵中的任意元素aij，若令I=max(i,j)，J=min(i,j)，则将上面两个式子综合起来得到： k=I*(I-1)/2+J-1。 2.三角矩阵 （1）下三角矩阵 与对称矩阵类似，不同之处在于存完下三角中的元素之后，紧接着存储对角线上方的常量，因为是同一个常数，所以存一个即可，这样一共存储了n*(n+1)+1 个元素，设存入向量： （2）上三角矩阵 对于上三角矩阵，存储思想与下三角类似，以行为主序顺序存储上三角部分，最后存储对角线下方的常量。 3.对角矩阵 对角矩阵也称为带状矩阵。，在这种三对角矩阵中，所有非零元素都集中在以主对角线为中心的对角区域中，即除了主对角线和它的上下方若干条对角线的元素外，所有其他元素都为零(或同一个常数c)。 三对角矩阵 A 也可以采用压缩存储,将三对角矩阵压缩到向量SA 中去，按以行为主序，顺序的存储其非零元素，如图所示，按其压缩规律，找到相应的映象函数。 18 19 第三章树与二叉树 3.1 树的概念 1.树的定义 树（Tree）是n（n≥0）个有限数据元素的集合。当n＝0 时，称这棵树为空树。在一棵非树T 中：1）有一个特殊的数据元素称为树的根结点，根结点没有前驱结点； 2）若n>1，除根结点之外的其余数据元素被分成m （m>0）个互不相交的集合T1，T2，…Tm，其中每一个集合Ti（1≤i≤m）本身又是一棵树。树T1，T2，…，Tm 称为这个根结点的子 树。 2．相关术语 （1）结点的度：结点所拥有的子树的个数称为该结点的度。 （2）叶结点：度为0 的结点称为叶结点，或者称为终端结点。 （3）分支结点：度不为0 的结点称为分支结点，或者称为非终端结点。一棵树的结点除叶结点外，其余的都是分支结点。 （4）孩子、双亲、兄弟：树中一个结点的子树的根结点称为这个结点的孩子。这个结点称为它孩子结点的双亲。具有同一个双亲的孩子结点互称为兄弟。 （5）路径、路径长度：如果一棵树的一串结点n1,n2,…,nk 有如下关系：结点ni 是ni+1 的父结点（1≤i （6）祖先、子孙：在树中，如果有一条路径从结点M 到结点N，那么M 就称为N 的祖先，而N 称为M 的子孙。 （7）结点的层数：树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1。 （8）树的深度：树中所有结点的最大层数称为树的深度。 （9）树的度：树中各结点度的最大值称为该树的度。 （10）有序树和无序树：如果一棵树中结点的各子树从左到右是有次序的，即若交换了某结点各子树的相对位置，则构成不同的树，称这棵树为有序树；反之，则称为无序树。 （11）森林：零棵或有限棵不相交的树的集合称为森林。自然界中树和森林是不同的概念，但在数据结构中，树和森林只有很小的差别。任何一棵树，删去根结点就变成了森林。 20 第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）; A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（）; A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（），它必须具备（）这三个特性; (1)A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2)A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性4．一个算法应该是（）; A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C 5. 下面关于算法说法错误的是（）; A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（）; (1）算法原地工作的含义是指不需要任何额外的辅助空间;（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法;（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界;（4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类; A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）; A．循环队列 B. 链表 C. 哈希表 D. 栈9．以下数据结构中，哪一个是线性结构（）; A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串10．以下那一个术语与数据的存储结构无关？（）; A．栈 B. 哈希表 C. 线索树 D. 双向链表 《数据结构》必须掌握的知识点与算法 第一章绪论 1、算法的五个重要特性（有穷性、确定性、可行性、输入、输出） 2、算法设计的要求（正确性、可读性、健壮性、效率与低存储量需求） 3、算法与程序的关系： （1）一个程序不一定满足有穷性。例操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。 （2）程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。 （3）一个算法若用程序设计语言来描述，则它就是一个程序。 4、算法的时间复杂度的表示与计算（这个比较复杂，具体看算法本身，一般关心其循环的次数与N的关系、函数递归的计算） 第二章线性表 1、线性表的特点： （1）存在唯一的第一个元素；（这一点决定了图不是线性表） （2）存在唯一的最后一个元素； （3）除第一个元素外，其它均只有一个前驱（这一点决定了树不是线性表） （4）除最后一个元素外，其它均只有一个后继。 2、线性表有两种表示：顺序表示（数组）、链式表示（链表），栈、队列都是线性表，他们都可以用数组、链表来实现。 3、顺序表示的线性表（数组）地址计算方法： （1）一维数组，设DataType a[N]的首地址为A0，每一个数据（DataType类型）占m个字节，则a[k]的地址为：A a[k]＝A0+m*k（其直接意义就是求在数据a[k]的前面有多少个元素，每个元素占m个字节） （2）多维数组，以三维数组为例，设DataType a[M][N][P]的首地址为A000，每一个数据（DataType 类型）占m个字节，则在元素a[i][j][k]的前面共有元素个数为：M*N*i+N*j+k，其其地址为： A a[i][j][k]＝A000+m*(M*N*i+N*j+k)； 4、线性表的归并排序： 设两个线性表均已经按非递减顺序排好序，现要将两者合并为一个线性表，并仍然接非递减顺序。可见算法2.2 5、掌握线性表的顺序表示法定义代码，各元素的含义； 6、顺序线性表的初始化过程，可见算法2.3 7、顺序线性表的元素的查找。 8、顺序线性表的元素的插入算法，注意其对于当原来的存储空间满了后，追加存储空间（就是每次增加若干个空间，一般为10个）的处理过程，可见算法2.4 9、顺序线性表的删除元素过程，可见算法2.5 10、顺序线性表的归并算法，可见算法2.7 11、链表的定义代码，各元素的含义，并能用图形象地表示出来，以利分析； 12、链表中元素的查找 13、链表的元素插入，算法与图解，可见算法2.9 14、链表的元素的删除，算法与图解，可见算法2.10 15、链表的创建过程，算法与图解，注意，链表有两种（向表头生长、向表尾生长，分别用在栈、队列中），但他们的区别就是在创建时就产生了，可见算法2.11 16、链表的归并算法，可见算法2.12 17、建议了解所谓的静态单链表（即用数组的形式来实现链表的操作），可见算法2.13 18、循环链表的定义，意义 19、循环链表的构造算法（其与单链表的区别是在创建时确定的）、图解 目录 绪论 (3) 0.1 基本概念 (3) 第一章线性表 (4) 1.1 线性表的定义 (4) 1.2 线性表的实现 (4) 1.2.2 线性表的链式存储结构 (6) 第二章栈、队列和数组 (11) 2.1 栈 (11) 2.2 队列 (15) 2.3 特殊矩阵的压缩存储 (17) 2.3.1 数组 (17) 2.3.2 特殊矩阵 (17) 第三章树与二叉树 (20) 3.1 树的概念 (20) 1.树的定义 (20) 2．相关术语 (20) 3.2 二叉树 (21) 3.2.1 定义与性质 (21) 3.2.2 二叉树的存储 (22) 3.2.3 二叉树的遍历 (23) 3.2.4 线索二叉树 (25) 3.3 树和森林 (29) 3.3.1 树的存储结构 (29) 3.3.2 森林和二叉树的转换 (30) 3.4 哈夫曼（ Huffman）树和哈夫曼编码 (31) 第四章图 (32) 4.1 图的概念 (32) 4.2 图的存储及基本操作 (33) 4.2.1 邻接矩阵 (33) 4.2.2 邻接表 (33) 4.3 图的遍历 (35) 4.3.1 深度优先搜索 (35) 4.3.2 广度优先搜索 (35) 4.4 图的基本应用 (37) 4.4.1 最小生成树 (37) 4.4.2 最短路径 (37) 4.4.3 拓扑排序 (39) 4.4.4 关键路径 (40) 第五章查找 (42) 5.1 查找的基本概念 (42) 5.2 顺序查找法 (43) 5.3 折半查找法 (44) 5.4 动态查找树表 (45) 5.4.1 二叉排序树 (45) 5.4.2 平衡二叉树 (47) 5.4.3 B 树及其基本操作、 B+树的基本概念 (49) 5.5 散列表 (51) 5.5.2 常用的散列函数 (51) 目 录 第一部分 历年考研真题汇编 .......................................................................................................................... 2000年华南师范大学计算机学院925数据结构考研真题 ................................................................. 1999年华南师范大学计算机学院925数据结构考研真题 ................................................................. 第二部分 兄弟院校真题汇编 .......................................................................................................................... 2011年厦门大学845数据结构考研真题 ............................................................................................... 2009年厦门大学845数据结构考研真题 ............................................................................................... 2008年厦门大学845数据结构考研真题 ............................................................................................... 2006年厦门大学496数据结构考研真题 ............................................................................................... 华南师范大学计算机学院 925数据结构历年考研真题汇编 最新资料，WORD 格式，可编辑修改！ 考试科目名称 数据结构 （A1卷） 考试方式：闭卷 考试日期 年 月 日 教师 系（专业） 计算机科学与技术系 年级 二 班级 学号 姓名 成绩 题号 一 二 三 四 五 六 七 八 九 十 分数 1、填空题。（每小题2分，本题满分20分） (1) C++语言中，数组是按行优先顺序存储的，假设定义了一个二维数组A[20][30]，每个元 素占两个字节，其起始地址为2140，则二维数组A 的最后一个数据元素的地址为 2140+2*(30*20-1) = 3338(3338,3339) 。 (2) 若A ，B 是两个单链表，链表长度分别为n 和m ，其元素值递增有序，将A 和B 归并成 一个按元素值递增有序的单链表，并要求辅助空间为O(1)，则实现该功能的算法的时间复杂度为 O(m+n) 。 (3) 快速排序的平均时间复杂度是____n*lg n___________。 (4) 假设有一个包含9个元素的最小堆，存放在数组A 中，则一定比A[3]大的元素有_ _2 (A[7],A[8]) ____个；一定比A[3]小的元素有__2 (A[0],A[1])____个。（元素从第0个位置开始存放） (5) 广义表(((A)),(B,C), D, ((A), ((E,F)))) 的长度是 4 ，深度是 4 。 (6) 有10个元素的有序表，采用折半查找，需要比较4次才可找到的元素个数为____3_____。 (7）当两个栈共享一存储区时，栈利用一维数组A[n]表示，两栈顶指针为top[0]与top[1]， 则栈满时的判断条件为___top[0]+1=top[1]_ 或者 top[0] = top[1]+1 ___。 (8) 假设计算斐波那契数的函数Fib(long n)定义如下： long Fib(long n){ if(n<=1) return n; else return Fib(n-1)+Fib(n-2) } 计算Fib(5)时的递归调用树（即指明函数调用关系的树）的高度是___4 _____。假设叶子结点所在的高度为0。 (9) 完全二叉树按照层次次序，自顶向下，同层从左到右顺序从0开始编号时，编号为i 的 结点的左子结点的编号为___2*i+1______。 (10) 假设用子女—兄弟链表方式表示森林，对应的二叉树的根结点是p ，那么森林的第三棵 树的根结点在二叉树中对应的结点是： ___p->rightchild->rightchild____________。假设二叉树的结点结构为： 得分 leftchild data rightchild 2018考研计算机：数据结构重难点及 复习建议 新东方在线推荐： 一、重难点解析和复习建议 数据结构的考查目标定位为掌握数据结构的基本概念、基本原理和基本方法，掌握数据的逻辑结构、存储结构以及基本操作的实现;能够对算法进行基本的时间复杂度和空间复杂度的分析;能够运用数据结构的基本原理和方法进行问题的分析求解，具备采用C、C++或JAVA语言设计程序与实现算法的能力。 当然，考生也不必因此而专门复习一遍C或C++程序设计，毕竟复习时间有限，而且数据结构要求的重点在于算法设计的能力，而不是编写代码的能力，因此，只要能用类似伪代码的形式把思路表达清楚就行，不用强求写出一个没有任何语法错误的程序。 下面我们来解析一下知识点： 线性表这一章里面的知识点不多，但要做到深刻理解，能够应用相关知识点解决实际问题。链表上插入、删除节点时的指针操作是选择题的一个常考点，诸如双向链表等一些相对复杂的链表上的操作也是可以出现在综合应用题当中的。 栈、队列和数组可以考查的知识点相比链表来说要多一些。最基本的，是栈与队列FILO和FIFO的特点。比如针对栈FILO的特点，进栈出栈序列的问题常出现在选择题中。其次，是栈和队列的顺序和链式存储结构，这里一个常考点是不同存储结构下栈顶指针、队首指针以及队尾指针的操作，特别是循环队列判满和判空的2种判断方法。再次，是特殊矩阵的压缩存储，这个考点复习的重点可以放在二维矩阵与一维数组相互转换时，下标的计算方法，比如与对角线平行的若干行上数据非零的矩阵存放在一维数组后，各个数据点相应的下标的计算。这一章可能的大题点，在于利用堆栈或队列的特性，将它们作为基础的数据结构，支持实际问题求解算法的设计，例如用栈解决递归问题，用队列解决图的遍历问题等等。 树和二叉树：这一章中我们从顺序式的数据结构，转向层次式的数据结构，要掌握树、二叉树的各种性质、树和二叉树的不同存储结构、森林、树和二叉树之间的转换、线索化二叉树、二叉树的应用(二叉排序树、平衡二叉树和Huffman树)，重点要熟练掌握的，是森林、树以及二叉树的前中后三种遍历方式，要能进行相应的算法设计。这一部分是数据结构考题历来的重点和难点，复习时要特别关注。一些常见的选择题考点包括：满二叉树、完全二叉树节点数的计算，由树、二叉树的示意图给出相应的遍历序列，依据二叉树的遍历序列还原二叉树，线索化的实质，计算采用不同的方法线索化后二叉树剩余空指针域的个数，平衡二叉树的定义、性质、建立和四种调整算法以及回溯法相关的问题。常见的综合应用题考点包括：二叉树的遍历算法，遍历基础上针对二 1数据（Data ）:是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并 被计算机程序处理的符号的总称。 数据元素（Data Element ）:是数据的基本单位，在程序中通常作为一个整体来进行考虑和 处理。 一个数据元素可由若干个 数据项（Data Item ）组成。数据项是数据的不可分割的最小单位。数 据项是对客观事物某一方面特性的数据描述。 数据对象（Data Object ）:是性质相同的数据元素的集合，是数据的一个子集。如字符 集合 C={ ‘ A , ' B'。，' C,…} 数据结构（Data Structure ）:是指相互之间具有（存在）一定联系（关系）的数据元素的集合。 元素 之间的相互联系（关系）称为逻辑结构。 数据元素之间的逻辑结构有四种基本类型，如图 1-3 所 示。 ① ② ③ ④ 2、 链式结构：数据元素存放的地址是否连续没有要求。 数据的逻辑结构和物理结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑 结构，而算法的实现依赖于所采用的存储结构。 在C 语言中，用一维数组表示顺序存储结构；用结构体类型表示链式存储结构。 3、 C 语言中用带指针的结构体类型来描述 typ edef struct Lnode { ElemType data; /*数据域，保存结点的值 struct Ln ode *n ext; /* 指针域 */ }LNode; /*结点的类型 */ 4、 循环队列为空：fron t=rear 。 循环队列满：（rear+1）%MAX_QUEUE_SIZE =front 。 5、 性质1:在非空二叉树中，第i 层上至多有2i-1 个结点（i 仝1）。 性质2：深度为k 的二叉树至多有2k -1个结点（k 仝1）。 性质3:对任何一棵二叉树，若其叶子结点数为 n 0,度为2的结点数为n 2,则n o = n 2+1。 一棵深度为 k 且有2k -1个结点的二叉树称为满二叉树 （Full Bin ary Tree ）。 完全二叉树的特点：若完全二叉树的深度为 k ,则所有的叶子结点都出现在第 k 层或k-1 集合：结构中的数据元素除了“同属于一个集合”外，没有其它关系。 线性结构：结构中的数据元素之间存在一对一的关系。 树型结构：结构中的数据元素之间存在一对多的关系。 图状结构或网状结构：结构中的数据元素之间存在多对多的关系。 顺序结构：数据元素存放的地址是连续的 ； */ 数据结构考研大纲 【硕士研究生考试】 Ⅰ考查目标 计算机学科专业基础综合考试涵盖数据机构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。要求考生比较系统地掌握上述专业基础课程的概念、基本原理和方法，能够运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。 Ⅱ考试形式和试卷结构 一、试卷满分及考试时间本试卷满分为150分，考试时间为180分钟 二、答题方式答题方式为闭卷、笔试 三、试卷内容结构 数据结构45分计算机组成原理45分 操作系统35分计算机网络25分 四、试卷题型结构单项选择题80分（40小题，每小题2分）综合应用题70分 数据结构 【考查目标】 1.理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。 2.掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。 3.能够选择合适的数据结构和方法进行问题求解。 一、线性表 （一）线性表的定义和基本操作 （二）线性表的实现 1.顺序存储结构 2.链式存储结构 3.线性表的应用 二、栈、队列和数组 （一）栈和队列的基本概念 （二）栈和队列的顺序存储结构 （三）栈和队列的链式存储结构 （四）栈和队列的应用 （五）特殊矩阵的压缩存储 三、树与二叉树 （一）树的概念 （二）二叉树 1.二叉树的定义及其主要特征 2.二叉树的顺序存储结构和链式存储结构 3.二叉树的遍历 4.线索二叉树的基本概念和构造 5.二叉排序树 6.平衡二叉树 （三）树、森林 1.书的存储结构 2.森林与二叉树的转换 3.树和森林的遍历 （四）树的应用 1.等价类问题 2.哈夫曼（Huffman）树和哈夫曼编码 四、图 （一）图的概念 （二）图的存储及基本操作 1. 邻接矩阵法 2. 邻接表法 （三）图的遍历 1. 深度优先搜索 2. 广度优先搜索 （四）图的基本应用及其复杂度分析 1. 最小（代价）生成树 2. 最短路径 3. 拓扑排序 4. 关键路径 五、查找 （一）查找的基本概念 （二）顺序查找法 （三）折半查找法 （四）B-树 （五）散列（Hash）表及其查找（六）查找算法的分析及应用 六、内部排序 （一）排序的基本概念 （二）插入排序 1. 直接插入排序 2. 折半插入排序 （三）气泡排序（bubble sort）（四）简单选择排序 （五）希尔排序（shell sort）（六）快速排序 （七）堆排序 （八）二路归并排序（merge sort）（九）基数排序 （十）各种内部排序算法的比较（十一）内部排序算法的应用 1.最小生成树：无向连通图的所有生成树中有一棵边的权值总和最小的生成树 1.1 问题背景： 假设要在n个城市之间建立通信联络网，则连通n个城市只需要n—1条线路。这时，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网。在每两个城市之间都可以设置一条线路，相应地都要付出一定的经济代价。n个城市之间，最多可能设置n(n-1)/ 2条线路，那么，如何在这些可能的线路中选择n-1条，以使总的耗费最少呢? 1.2 分析问题（建立模型）： 可以用连通网来表示n个城市以及n个城市间可能设置的通信线路，其中网的顶点表示城市，边表示两城市之间的线路，赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。即无向连通图的生成树不是唯一的。连通图的一次遍历所经过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树，对连通图的不同遍历，就可能得到不同的生成树。 图 G5无向连通图的生成树为(a)、(b)和(c)图所示： G5 G5的三棵生成树： 可以证明，对于有n 个顶点的无向连通图，无论其生成树的形态如何，所有生成树中都有且仅有n－1 条边。 1.3最小生成树的定义： 如果无向连通图是一个网，那么，它的所有生成树中必有一棵边的权值总和最小的生成树，我们称这棵生成树为最小生成树，简称为最小生成树。 最小生成树的性质： 假设N=(V,{ E}) 是个连通网，U是顶点集合V的一个非空子集，若（u,v）是个一条具有最小权值(代价)的边，其中， 则必存在一棵包含边（u,v）的最小生成树。 1.4 解决方案： 两种常用的构造最小生成树的算法：普里姆（Prim）和克鲁斯卡尔（Kruskal）。他们都利用了最小生成树的性质 1.普里姆（Prim）算法：有线到点，适合边稠密。时间复杂度O(N^2) 一.选择题篇 1. 算法的计算量的大小称为计算的（）。【北京邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（）【中科院计算所 1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1）它必须具备（2）这三个特性。【南京理工大学 1999 一、1（2分）【武汉交通科技大学 1996 一、1（ 4分）】 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 4．一个算法应该是（）。【中山大学 1998 二、1（2分）】 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 5. 下面关于算法说法错误的是（）【南京理工大学 2000 一、1（1.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) 目前刚整理了2009-2015的试题过几天2016的也会上传上去 希望对你有帮助。。。。。。。 2009 1.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是 A.栈 B.队列 C.树 D.图 2.设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是bdcfeag，则栈S的容量至少是 A．1 B.2 C.3 D.4 3.给定二叉树图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3，1，7，5，6，2，4，则其遍历方式是 A．LRN B.NRL C.RLN D.RNL 4.下列二叉排序树中，满足平衡二叉树定义的是 5.已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则完全二叉树的结点个数最多是 A．39 B.52 C.111 D.119 6.将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的 父结点，则在原来的森林中，u和v可能具有的关系是I．父子关系 II.兄弟关系 III.u的父结点与v的父结点是兄弟关系 A.只有II B.I和II C.I和III D.I、II和III 7.下列关于无向连通图特性的叙述中，正确的是 I．所有顶点的度之和为偶数 II.边数大于顶点个数减1 III.至少有一个顶点的度为1 A.只有I B.只有II C.I和II D.I和III 8.下列叙述中，不符合m阶B树定义要求的是 A．根节点最多有m棵子树 B.所有叶结点都在同一层上 C．各结点内关键字均升序或降序排列 D.叶结点之间通过指针链接 9.已知关键序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后得到的小根堆是 A．3，5，12，8，28，20，15，22，19 B.3，5，12，19，20，15，22，8，28 C．3，8，12，5，20，15，22，28，19 D.3，12，5，8，28，20，15，22，19 10.若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是 A．起泡排序 B.插入排序 C.选择排序 D.二路归并排序 41.（10分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法： 数据结构考研必背算法5星 文档说明：本文档是针对考研专业课《数据结构》所编写的，是对考研数据结构的核心算法进行总结，我们知道，不管是统考还是非统考，都会涉及至少10分的算法题（非统考至少25分），而这些题的答案都是在一些经典算法的思想上进行改进的，本文总结出必须要熟练掌握的算法，这些算法不管是考研初期还是冲刺，都应该高度重视，只要对这些代码进行熟练掌握，才能随机应变，希望对大家有所帮助； 线性表 1.逆转顺序表中的所有元素 void Reverse(int A[ ],int n){ int i,t; for(i=0;i 第一章绪论 一、填空题（每空1分，共33分） 1. 一个计算机系统包括硬件系统和软件系统两大部分。 2. 一台计算机中全部程序的集合，称为这台计算机的软件资源/（系统）。 3. 计算机软件可以分为系统软件和应用软件两大类。科学计算程序包属于应用软 件，诊断程序属于系统软件（工具）。 4. 一种用助忆符号来表示机器指令的操作符和操作数的语言是汇编语言。 5. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。 6. 数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的关系有限集合。 7. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。 8. 数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。 9. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 10．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。 11. 在树形结构中，树根结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点数可以任意多个。 12. 在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。 13．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散列。 14. 数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。 15. 一个算法的效率可分为时间效率和空间效率。 16. 任何一个C程序都由一个主函数和若干个被调用的其它函数组成。 二、单项选择题（每小题1分，共15分） （ B ） 1. 通常所说的主机是指∶ A) CPU B) CPU和内存C) CPU、内存与外存D) CPU、内存与硬盘 （ C ）2. 在计算机内部，一切信息的存取、处理和传送的形式是∶ A) ACSII码B) BCD码C)二进制D)十六进制 （ D ）3. 软件与程序的区别是∶ A)程序价格便宜、软件价格昂贵； B)程序是用户自己编写的，而软件是由厂家提供的； C) 程序是用高级语言编写的，而软件是由机器语言编写的； D) 软件是程序以及开发、使用和维护所需要的所有文档的总称，而程序只是软件的一部分。 （ C ）4. 所谓“裸机”是指∶ A) 单片机B)单板机C) 不装备任何软件的计算机D) 只装备操作系统的计算机 （ D ）5. 应用软件是指∶ A)所有能够使用的软件B) 能被各应用单位共同使用的某种软件 C)所有微机上都应使用的基本软件D) 专门为某一应用目的而编制的软件 天津大学数据结构和程序设计考研真题-考研资料-笔记讲义 许多学生在考研复习的时候，都会遇到重点不明确，不知道从何复习的情况。为此，天津考研网建议，考研复习中，专业的考研复习资料，是帮助考生能够快速掌握复习重点及方法必不可少的因素，然后就是真题和讲义，可以让同学了解历年考研的出题方向和大致范围。天津考研网推出了天津大学数据结构和程序设计的考研复习资料及真题解析班，以下为详细介绍: 天津大学数据结构和程序设计考研真题等资料由天津考研网签约的天津大学计算机科学与技术学院高分考研学生历时近一月所作，该考生在考研中取得了专业课129分的好成绩并在复试中更胜一筹，该资料包含该优秀本校考生的考研经验、考研试题解题思路分析、复试流程经验介绍以及针对官方指定参考书的重难要点并根据天津大学本科授课重点整理等，从漫漫初试长路到紧张复试亮剑为各位研友提供全程考研指导攻关。 特别说明：此科目06年以前科目名称为数据结构；自06年到08年科目名称改为计算机基础（包含数据结构、程序设计、计算机原理）；自09年开始全国统考，科目名称为计算机学科专业基础综合；自2013年开始由学校自主命题，科目名称改为901数据结构与程序设计。 第一部分由天津考研网提供的核心复习资料： 天津大学数据结构和程序设计资料编者序言：本文的重点在于C++，数据结构的复习和复试基本情况介绍。C++、数据结构又分别从复习规划，复习用书，重点知识点结合历年考题这四个方面来展开的。复习规划大家务必看一下，然后根据自己的实际情况在制定自己的复习时间，因为内容很多，大多数同学都在考试之前复习不完，在心理因素上就落了一节。重点知识点一定要看了，这些知识点几乎每年都会有题了。另外我还给了历年试题的答案供大家参考。有的答案是自己做的答案，可能会有疏忽的地方。望大家提出宝贵的意见和建议。复试的东西现在了解一下即可，等到进复试了，还是有足够的时间看的。另外我还给了些自己复习心得。考完后感慨很多，回顾了这多半年来自己的成败得失。希望大家从一开始就沿着比较高效的方向前进，减少不必要时间的浪费。本资料格式为A4纸打印版，总量达到了130页共计50000余字，清晰易复习，已于编写者签订资料保真转让协议，各位研友可放心使用参考！特别提示：本站尽力保证资料的有用性，但由于个人复习态度进度不同，故请酌情参考本资料！ 天津大学数据结构和程序设计考研真题等资料目录 一、学院专业综述 二、近年来的录取情况及分数线 三、05、06年专业课试题的变化及其今后的趋势 四、复习策略和复习时间的统筹安排及所需要的辅助资料 五、C++和数据结构复习规划及复习侧重点(特别是05，06年的变化) 5七、复习经验与教训(学习生活心理诸方面) 八、关于数学和政治复习的小小的建议 九、计算机复试 十、附言 《数据结构》复习重点知识点归纳 一．数据结构的章节结构及重点构成 数据结构学科的章节划分基本上为：概论，线性表，栈和队列，串，多维数组和广义表，树和二叉树，图，查找，内排，外排，文件，动态存储分配。 对于绝大多数的学校而言，“外排，文件，动态存储分配”三章基本上是不考的，在大多数高校的计算机本科教学过程中，这三章也是基本上不作讲授的。所以，大家在这三章上可以不必花费过多的精力，只要知道基本的概念即可。但是，对于报考名校特别是该校又有在试卷中对这三章进行过考核的历史，那么这部分朋友就要留意这三章了。 按照以上我们给出的章节以及对后三章的介绍，数据结构的章节比重大致为： ·概论：内容很少，概念简单，分数大多只有几分，有的学校甚至不考。 ·线性表：基础章节，必考内容之一。考题多数为基本概念题，名校考题中，鲜有大型算法设计题，如果有，也是与其它章节内容相结合。 ·栈和队列：基础章节，容易出基本概念题，必考内容之一。而栈常与其它章节配合考查，也常与递归等概念相联系进行考查。 ·串：基础章节，概念较为简单。专门针对于此章的大型算法设计题很少，较常见的是根据KMP进行算法分析。 ·多维数组及广义表：基础章节，基于数组的算法题也是常见的，分数比例波动较大，是出题的“可选单元”或“侯补单元”。一般如果要出题，多数不会作为大题出。数组常与“查找，排序”等章节结合来作为大题考查。 ·树和二叉树：重点难点章节，各校必考章节。各校在此章出题的不同之处在于，是否在本章中出一到两道大的算法设计题。通过对多所学校的试卷分析，绝大多数学校在本章都曾有过出大型算法设计题的历史。 ·图：重点难点章节，名校尤爱考。如果作为重点来考，则多出现于分析与设计题型当中，可与树一章共同构成算法设计大题的题型设计。 ·查找：重点难点章节，概念较多，联系较为紧密，容易混淆。出题时可以作为分析型题目给出，在基本概念型题目中也较为常见。算法设计型题中可以数组结合来考查，也可以与树一章结合来考查。 ·排序：与查找一章类似，本章同属于重点难点章节，且概念更多，联系更为紧密，概念之间更容易混淆。在基本概念的考查中，尤爱考各种排序算法的优劣比较此类的题。算法设计大题中，如果作为出题，那么常与数组结合来考查。 数据结构精选考研试题 [注]：编写程序可选用任一种高语言，算法描述可采用类语言，必要时加上注释一、回答下列问题：[20分] 1、算法的定义和性质2、为什么说数组与广义表是线性表的推广？ 3、什么是结构化程序设计？ 4、哈希方法的基本思想 5、给出一不稳定排序方法名称与实例二、构造结果：[24分] 确定x:=x+1语句在下面程序段中的频率，要求写出分析过程。for i:=1 to n do for j:=1 to I do for k:=1 to j do x:=x+1 画出对长度为8的有序表进行折半查找的判定树，并求其在等概率时查找成功的平均查找长度。已知一棵二叉树如右图，给出对这棵二叉树进行前序、中序、后序遍历的结果序列．假设用于通讯的电文仅8个字母组成，字母在电文中出现的频率 分别为{2，3，5，7，11，4，13，15}，试为这8个字母设计哈夫曼编码．在地址空间为0~15的散列区中，对以下关键字序列构G造哈希表，关键字序列为，H(x)=[i/2] ，其中i为关键字中第一字母在字母表中的序号。要求用线性探测开放定址法处理冲突，并求出在等概率情况下查找成功的平均查找长度。构造有7个元素组成的线性表一实例，是进行快速排序时比较次数最少的初始排序。三、写一算法，完成对这棵二叉树的左右子树的交换，设二叉树以二叉链表作存储结构。[15分] 四、编写一非递归算法，对一棵二叉排序树实现中序遍历。[15分] 五、编写程序，完成下列功能：[15分] 1．读入整数序列，以整数0作为序列的结束标志，建立一个单链表。2．实现单链表原地逆转，即单链表中结点指针方向反转，反转操作不使用额外的链表结点，可使用临时工作单元。例：输入序列为：1，8，4，3，0 六、 计算机考研数据结构复习重点归纳计算机考研数据结构复习重点归纳 二叉树是数据结构中的重点内容，在这两年的考试中也将二叉树作为重点内容来考查。二叉树这部分内容要求大家掌握二叉树的定义、性质、存储结构、遍历、线索化、森林和二叉树的转换等内容。算法的重点是二叉树的遍历及其应用，这也是二叉树这部分的重点 和难点。遍历是二叉树各种操作的基础，可以在遍历过程中对结点 进行各种操作。例如：求二叉树结点总数，建立二叉树，建立二叉 树的存储结构等。二叉树的很多算法是在遍历算法基础上改造完成的，这就要求大家在复习时，熟练掌握二叉树遍历的递归和非递归 算法。 下面为大家介绍一下二叉树的几种遍历方法： 由二叉树的定义可知，一颗二叉树由根节点及左、右子树三个基本部分组成，因此，只要依次遍历这三部分，就可以遍历整个二叉树。 1.先序遍历 先序遍历的递归过程为：若二叉树为空，遍历结束。否则， (1)访问根节点; (2)先序遍历根节点的左子树; (3)先序遍历根节点的右子树。 2.中序遍历 中序遍历的递归过程为：若二叉树为空，遍历结束。否则， (1)中序遍历根节点的左子树; (2)访问根节点; (3)中序遍历根节点的右子树。 3.后序遍历 后序遍历的递归过程为：若二叉树为空，遍历结束。否则，同济大学四平路 (1)后序遍历根节点的左子树; (2)后序遍历根节点的右子树; (3)访问根节点。 层次遍历 二叉树的层次遍历，是指从二叉树的第一层(根结点)开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。在进行层次遍历时，对一层结点访问完后，再按照它们的访问次序 对各个结点的左孩子和右孩子顺序访问，这样一层一层进行，先遇 到的结点先访问，这与队列的操作原则比较吻合。因此，在进行层 次遍历时，可设置一个队列结构，遍历从二叉树的根结点开始，首 先将根结点指针入队列，然后从对头取出一个元素，每取一个元素，执行下面两个操作： (1)访问该元素所指结点; (2)若该元素所指结点的左、右孩子结点非空，则将该元素所指 结点的左孩子指针和右孩子指针顺序入队。 此过程不断进行，当队列为空时，二叉树的层次遍历结束。 下面大家来看二叉树遍历这部分在考试中常考题型 2.以遍历为基础的二叉树算法设计是考试的重点和难点。常见的试题有以下几类： (1)基于二叉树遍历的递归算法 湖北工业大学计算机学院数据结构历年考研真题汇 编 Final approval draft on November 22, 2020 目 录 说明：数据结构科目代码更换频繁，2016年科目代码是836，本书以此为准。 湖北工业大学计算机学院 836数据结构历年考研真题汇编 最新资料，WORD 格式，可编辑修改！ 2008年湖北工业大学计算机学院917数据结构历年考研真题汇编考研真题 试卷代号 917 试卷名称 数据结构 ①试题内容不得超过画线范围，试题必须打印，图表清晰，标注准确 ②考生请注意：答案一律做在答题纸上，做在试卷上一律无效。 二○○八年招收硕士学位研究生试卷 一．单项选择题（在每小题列出四个供选择的答案A ．B ．C ．D 中，选一个正确的答案,将其代号填在答卷纸相应题号后的下横线上，每小题2分，共20分） 1．以下术语与数据的存储结构无关的是（ ）。 A ．栈 B. 哈希表 C. 双向链表 D. 线索二叉树 2．在一个以 h 为头指针的双向循环链表中，指针p 所指的元素是尾元素的条件是（ ）。 A. p==h B. h->rlink==p C. p->llink==h D. p- >rlink==h 3．设栈S 和队列Q 的初始状态为空，元素a,b,c,d,e,f 依次通过栈S ，一个元素 出栈后即进队列Q ，若6个元素出队的序列是a,c,f,e,d,b ，则栈S 的容量至 少应该是( )。 A ． 6 B. 5 C. 4 D. 3 4．用循环链表表示队列，设队列的长度为n ，若只设尾指针，则出队和入队的时 间复杂度分别为( )。 A ．O(1)，O(1) B. O(1)，O(n) C. O(n)，O(1) D. O(n)，O(n) 5．设串s1=“ABCDEFG”， s2=“12345”，则strconcat (strsub (s1, 2, strlen(s2)), strsub (s1, strlen(s2), 7))的结果串是( )。 A ．BCDEF B ．BCDEFG C ．EFG D ．BCDEEFG 6．某二叉树T 有n 个结点，设按某种顺序对T 中的每个结点进行编号，编号为 1，2，… ，n ，且有如下性质：T 中任一结点V ，其编号等于V 左子树上的最 小编号减1，而V 的右子树的结点中，其最小编号等于V 左子树上结点的最大 编号加1。这时是按( )编号的。 A.中序遍历序列 B.前序遍历序列 C.后序遍历序列 D.层次遍历序列 7．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是 ( ) 。 A ．（15，13，14，6，17，16，18） B.（15，17，16，18，13，6，14） C.（15，6，13，14，17，16，18） D. (15，13，6，14，17，18，16) 8．已知由7个顶点组成的无向图的邻接矩阵为： A B C D E F G计算机数据结构考研真题及其答案
考研数据结构必须掌握的知识点与算法-打印版
大数据结构考研讲义
华南师范大学计算机学院925数据结构历年考研真题汇编34p
考研资料数据结构试卷A1-答案
2018考研计算机：数据结构重难点及复习建议
清华大学严蔚敏版数据结构考研要点(精华版)
最新数据结构考研大纲资料
考研数据结构图的必背算法及知识点
计算机考研数据结构真题汇总
计算机考研数据结构统考历年真题
数据结构考研必背算法5星
考研资料数据结构试题汇总
天津大学数据结构和程序设计考研真题
考研《数据结构》复习知识点归纳
数据结构精选考研试题
计算机考研数据结构复习重点归纳
湖北工业大学计算机学院数据结构历年考研真题汇编
- 湖北工业大学计算机学院数据结构历年考研真题汇编
- 数据结构考研真题及解答
- 数据结构考研真题和答案
- 【数据结构考研真题精选及答案】第4章 串
- 数据结构精选考研试题
- 最新计算机考研数据结构统考历年真题-
- 计算机考研数据结构统考历年真题
- 考研基础专业课“数据结构”历年考研真题与典型题详解-第一章至第四章【圣才出品】
- 计算机考研数据结构真题汇总
- 数据结构考研真题及解答
- 湖北工业大学计算机学院数据结构历考研真题汇编p
- 河北大学《数据结构含语言》(2019-2010)[官方-完整版]历年考研真题
- 数据结构考研真题与其答案
- 华南师范大学计算机学院925数据结构历年考研真题汇编34p
- 北京理工大学计算机学院数据结构专业硕士历年考研真题汇编
- 历年《数据结构》考研真题及解答
- 浙江理工大学信息学院991数据结构历年考研真题专业课考试试题
- 数据结构考研真题
- 2008年西南大学837数据结构考研试题(1)
- 湖北工业大学计算机学院数据结构历年考研真题汇编