第一章[绪论]：

(1).针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作。

其涵盖范围分为：逻辑结构、物理（存储）结构、数据运算。

逻辑结构分为：线性结构（线性表、栈、队、串、数组）和 非线性结构（树结构、图结 构）；

物理（存储结构）分为：顺序结构、链式结构、索引结构、散列结构；

数据运算分为：CURD及排序；

(2).基本概念：数据、数据项、数据元素、数据对象、数据结构、数据类型、抽象数据类型

(3).推导大O阶方法：

1.用常数1取代运行时间中的所有加法常数；

2.在修改后的运行次数函数中，只保留最高阶项；

3.如果最高阶项存在且不是1，则去除与这个项相乘的常数；

得到的结果就是大O阶。

(4).算法基本特性：输入、 输出、有穷性、确定性、可行性。

设计要求：正确性、可读性、健壮性、效率和低存储量需求。

第二章[线性表]：

(1).线性表的存储结构分为：顺序和链式存储结构。

顺序存储：把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。

特性：1.随机访问特性 2.占有连续的存储空间 3.做插入操作时要移动多个元素

链表：一种物理储存单元上非连续，非顺序的存储结构。

特性：1.不支持随机访问 2.结点的存储空间利用率较低 3.支持存储空间的动态分布 4.做插入操作时不需要移动元素

注：如果在不知道第i个元素的指针位置的时候，单链表在插入与删除上与顺序结构存储比没有太大的优势，除非一次性依次插入或删除多个元素，总的来说，操作越频繁优势越明显。

(2).试述头指针,头结点,首元结点这三个概念的区别？

答：在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等），有头结点后，对在第一元素结点前插入结点和删除第一结点，其操作与对其它结点的操作统一了。而且无论链表是否为空，头指针均不为空。首元结点也就是第一元素结点，它是头结点后边的第一个结点。

(3).链表如何表示空表

1.无头结点时，当头指针的值为空时表示空表；

2.有头结点时，当头结点的指针域为空时表示空表；

(4). sizeof(x)：计算变量x的长度（字节数）；

malloc(m)：开辟m字节长度的地址空间，并返回这段空间的首地址；

free(p)：释放指针p所指变量的存储空间，即彻底删除一个变量；

(5).链表的运算效率分析：

查找时间复杂度O(n)；

插入和删除一般情况下时间复杂度为O(1)，但是如果在单链表中进行前插或删除操作，因为从头      

查找前驱结点，所耗时间复杂度为O(n);

(6).稀疏矩阵：

三元组表存储结构 缺点：将失去随机存取功能。

十字链表存储方法  用途：方便稀疏矩阵的加减运算；方法：每个非0元素占用5个域。

第三章[栈和队列]：

(1).栈的定义及操作，栈是只准在一端进行插入和删除操作的线性表，该端称为栈的顶端。

插入元素到栈顶的操作，称为入栈；从栈顶删除最后一个元素的操作，称为出栈。

对于向上生成的堆栈：

入栈口诀：堆栈指针top “先压后加”：S[top++] = an+1;

出栈口诀：堆栈指针top “先减后弹”：e = S[--top];

(2).队列：只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。

      链队：1.空链队的特征：front=rear。2.链队会满吗？一般不会，因为删除时有free动作，除非内     存不足。3.入队（尾部插入）：rear->next = S；rear = S；出队（头部删除）：front->next = p->next。

(3).循环队列：

队空条件：front = rear (初始化时：front = rear);

队满条件：front = （rear+1）%N （N=maxsize）;

队列长度（即数据元素个数）：L = (N+rear-front) % N;

(4).链队列空的条件是首尾指针相等，而循环队列满的条件的判定，则有队尾加1等于队头和设标记两 种方法。

(5).为什么要设计堆栈？它有什么独特用途？

1.调用函数或子程序非它莫属；

2.递归运算的有力工具；

3.用于保护现场和恢复现场；

4.简化了程序设计的问题；

(6).为什么要设计队列？它有什么独特用途？

1.离散事件的模拟（模拟事件发生的先后顺序，例如CPU芯片的指令译码队列）；

2.操作系统中的作业调度（一个CPU执行多个作业）；

3.简化程序设计。

(7).什么叫”假溢出“？如何解决？

答：在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”，解决假溢出的途径——采用循环队列。

第四章[串]

(1).串是数据元素为字符的线性表，串的定义及操作。

串即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。

串比较：int strcmp（char *s1, char *s2）；

求串长：int strlen（char *s）；

串连接：char strcat（char *to，char *from）；

子串T定位：char strchr（char *s，char *c）；

(2).串的存储结构，因串是数据元素为字符的线性表，所以存在"结点大小"的问题。

(3).串的存储表示：

1.串的定长顺序存储表示

与顺序表的定义类似，使用定长存储串只需要分配一片连续的内存，即定义一个字符串类型的数组来存储字符即可完成在连续内存区域中存储的目的。在设置长度的时候，需要多留一位（字符串首位）以存储字符串的长度。

2.堆分配存储表示

以一段连续分配的地址作为存储字符串的地址，与定长不同的是，要求使用malloc()与free()函数进行内存的动态添加与删除。如果分配地址成功，要求返回一个指向起始地址的指针ch，方便进行后续内存的访问。

3.串的块链存储表示

用链表来表示串，存储串的信息。在串的定长存储与堆分配存储中，串的一个个字符都是作为单个的单元或者整体连续的内存开始存储的。在串块链存储表示中由于链表的结构因素，使得每一个节点会由不同的字符所组成，节点中的字符数目也不一定相同。由于串的长度不一定是节点大小的整倍数，则链表的最后一个节点不一定全部都是字符，相对地，可以由‘#’符号进行补齐。以链表存储串值时，需要同时设置一个尾指针来指示链表中的最后一个节点。

(4).空串和空白串有无区别：

答：有区别；空串（Null String）是指长度为零的串；而空白串（Blank String）是指包含一个或多个空白字符“ ”（空白键）的字符串。

(5).空串是任意串的子串；任意串S都是S本身的子串，除S本身外，S的其他子串称为S的真子串。

(6).串分为：逻辑结构 s='a1a2.........an'；

      存储结构分为：定长顺序存储结构、堆存储结构、块链存储结构；

      操作（或运算）分为：若干函数的实现、模式匹配算法；

模式匹配即子串定位运算，即如何实现Index（S，T，pos）函数。

第六章[树和二叉树]

(1).二叉树的主要性质：

性质一：非空二叉树上叶子结点数等于双分支结点数加一。

性质二：二叉树的第i层最多有2^（i-1）个结点。

性质三：高度（或深度）为k的二叉树最多有（2^k）-1个结点。

性质四：有n个结点的完全二叉树，对各结点从上而下、从左到右依次编号（编号范围为1到n），则结点关系如下。

1.若i为某结点a的编号，则：

2.如果i不等于1，则a的双亲结点编号为 ⌊ⅈ/2⌋。

3.如果2i<=n，则a左孩子结点的编号为2i；如果2i>n，则a无左孩子结点。

4.如果2i+1<=n，则a右孩子结点的编号为2i+1；如果2i+1>n，则a无右孩子结点。

性质五：给定n（n>=1）个结点，能构成1/(n+1) C_2n^n种不同的二叉树。

性质六：具有n（n>=1）个结点的完全二叉树的高度（或深度）为⌊log_2⁡n ⌋+1。

(2).树的存储结构，数、森林的遍历及和二叉树的相互转换：

1.树如何转为二叉树？

方法：

step1：加线，在所有兄弟结点之间加一条连线【兄弟相连】；

step2：抹线，树中的每个结点，只保留它与第一个孩子结点的连线，删除它与其它孩子结

点之间的连线【长兄为父】；

step3：旋转，层次调整，以树的根结点为轴心，将整棵树顺时针旋转一定角度，使之结构

层次分明，（注意第一个孩子是结点的左孩子，兄弟转换过来的孩子是结点的右孩子）【孩

子靠左】；

2.二叉树怎样还原为树？

总结：逆操作，把所有右孩子变为兄弟。

(1).加线，若某结点X的左孩子结点存在，则将这个左孩子的右孩子结点、右孩子的右孩子结点直到最后一层结点。

(2).去线，删除原二叉树中所有结点与其右孩子结点的连线。

(3).层次调整。

3.森林转换为二叉树？

step1：将每棵树转换为二叉树；

step2：第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一      

棵二叉树的根结点的右孩子，用线连接起来。

4.二叉树转换为森林？

假如一棵二叉树的根结点有右孩子，则这棵二叉树能够转换为森林，否则将转换为一棵

树。

step1：从根结点开始，若右孩子存在，则把与右孩子结点的连线删除。在查看分

离后的二叉树，若其根结点的右孩子存在，则连线删除.......；直到所有这些根结点与右  

孩子的连线都删除为止。

step2：将每棵分离后的二叉树转换为树。

(3).树和森林的存储方式：

树有三种常用存储方式：

1.双亲表示法 2.孩子表示法 3.孩子——兄弟表示法

问：树->二叉树的”连线--抹线--旋转“ 如何由计算机自动实现？

答：用“左孩子右 兄弟”表示法来存储即可。

存储过程就是树转换为二叉树的过程：

(4).树、森林的遍历：

树的遍历 深度优先遍历（先根、后根）；【树没有中序遍历（因子数不分左右）】

广度优先遍历（层次）；

先根遍历:若树不空，则先访问根结点，然后依次先根遍历各棵子树。

后根遍历:若树不空，则先依次后根遍历各棵子树，然后访问根结点。

按层次遍历:若树不空，则自上而下自左至右访问树中每个结点。（用队列+递归实现）

树若采用“先转换，后遍历”方式，结果是否一样？

1.树的先根遍历与二叉树的先序遍历相同；

2.树的后根遍历相当于二叉树的中序遍历；

3.树没有中序遍历，因为子树无左右之分；