《数据结构》期末复习提纲（计算机11级）
第一部分 章节知识点
第1章 绪论
1、基本概念
（1）数据元素：是数据的基本单位。一个数据元素由若干数据项组成，数据项是数据不可分割的最小单位。
（2）数据类型：是性质相同的数据元素的集合及在这个集合上的一组操作。 （3）数据结构
a、广义：按某种逻辑关系组织起来的一批数据应用计算机语言并按一定的存储表示方式把它们存储在计算机的存储器中，并在其上定义了一个运算的集合。
数据结构包含三个方面的内容，即数据的逻辑结构、存储结构和对数据所施加的运算（操作），具体如下图所示。
b、狭义：就是指数据的组织形式，即逻辑结构（具体4类：集合、线性结构、树形结构和图形结构）。
2、算法分析（主要分析：时间复杂度和空间复杂度）
（1）定义：是对特定问题求解步骤的一种描述，是指令的有限序列。
特性（5个）：有穷性、确定性、可行性、输入、输出。 （2）算法和程序的区别与联系：
区别：a、一个程序不一定满足有穷性（死循环）。
B、程序中的指令必须是机器可执行的，而算法中的指令则无此限制。 联系：一个算法若用计算机语言来书写，则它就可以是一个程序。 （3）会分析时间复杂度（包括时间频度）。
第2章 线性表（结点间一对一的关系）
1、线性表的逻辑结构描述。 2、线性表的存储结构及其运算。
第3章 栈和队列――都是操作受限的线性表
1、栈的定义。
2、栈的存储结构（主要指顺序栈）： （1）类型描述；（2）运算：栈空状态、栈满状态、入栈、出栈、取栈顶。 二、队列的基本内容 1、队列的定义。 2、队列的存储结构：
普通顺序队列：队空、队满、队列长度、入队、出队、取队头元素顺序存储队列链式存储
类型描述、队空、队满、队列长度、入队、出队、取队头元素循环队列：类型描述、队空、队满、队列长度、入队、出队、取队头元素链队列：
第4章 串――是一种特殊的线性表
特殊性：每个元素只有一个字符组成
1、串的定义。
2、子串、子串在主串中的位置、两串相等、空串、空格串的概念 3、以下运算的使用：
StringAssign(S,string_constant); StrCmp(S,T); StrLen(S); Strcat(S,T); StrCpy(S,T);SubStr(S,pos,len,sub); Index(S,T); Replace(S,T,V); StrInsert(S,pos,T);StrDelete(S,pos,len)
第5章 数组和广义表
1、数组的逻辑结构。
2、地址计算：对称矩阵、对角矩阵、三角矩阵中元素aij的地址计算。 3、稀疏矩阵、三元组的概念，稀疏矩阵的存储（三元组顺序表） 4、广义表的概念、基本运算（取表头、取表尾）
第二部分 相关习题（课后习题和实验指导书习题）
备注：习题中涉及到的非要求掌握的知识点内容，均不必复习。
第1章 绪论
1、课后习题
一、二、四（3） 2、指导书习题 一、二、四
第2章 线性表
1、课后习题 二（1）（2）（4）（7） 2、指导书习题 一、二、三、四
第3章 栈和队列
1、课后习题
一、二、三、四（2）（5）（6） 2、指导书习题 一、二、三、四
第4章 串
1、课后习题 一、二 2、指导书习题 一、二、四
第5章 数组和广义表
1、课后习题 一（2）（3）（7）（8）（9）
第三部分 课后习题参考答案
第1章 绪论
一、填空题
1.集合、线性结构、树型结构、图状结构（网状结构）。
2.顺序存储方法、链接存储方法、索引存储方法、散列存储方法 二、选择题。
1. B 2. C 3. D 四、算法分析题 (1) O（n） (2) O(n) (3) O(n) (4) O(n)
（5）O（n3）
（6） 本题只能计算If语句的频度。上述程序实质上是一个双重循环，对于每个y值（y>0）,if语句执行11次，其中10次执行x++。因此，if语句的频度为11×100=1100次。
第2章 线性表
1、课后习题
二、算法设计题
1.分两种情况讨论： （1）顺序表
要将该表逆置，可以将表中的开始结点与末元素结点互换，第二个元素结点与倒数第二个结点互换，以此类推，就可以将整个表逆置了。算法如下： void Reverselist ( Seqlist *L) {
Datatype t; /*设置临时空间用于存放data */ int i;
for(i=0;i
t=L->data[i]; /*交换数据*/ L->data[i]=L->data[L->lenth-1-i]; L->data[L->lenth-1-i]=t; } }
(2) 单链表
可以利用指针的指向转换来达到链表逆置的目的。算法如下： Linklist Reverselist(Linklist head)
{ /*将head所指的单链表逆置，注意：此链表带结点*/
listNode *p,*q; /*设置两个临时指针变量*/ if(head->next && head->next->next)
{ /*若链表不是空链表，也不是单结点链表 */ P=head->next; q=p->next; p->next=NULL; /*将开始结点变成末元素结点*/
while(q) /*每次循环将后一个结点变成开始结点*/ {
p=q; q=q->next; p->next=head->next; head->next=p; }
return head; }
return head; /*若是空链表或但结点链表，则直接返回head*/ }
2. 答：因已知顺序表L是递增有序表，所以只要从头找起，找到第一个比它大(或相等)的结点数.
据，把x插入到这个数所在的位置就是了。算法如下：
void InsertIncreaseList( Seqlist *L , Datatype x ) { int i;
for ( i=0 ; i < L -> length && L->data[ i ] < x ; i++) ; /* 查找并比较,分号不能少*/ InsertList ( L ，x , i ); /*调用顺序表插入函数*/ }
相关推荐：
loading