第一章：绪论1．数据结构的基本概念和术语⏹数据、数据元素、数据项、数据对象、数据结构等基本概念⏹数据结构的逻辑结构，存储结构及数据运算的含义及其相互关系⏹数据结构的四种逻辑结构及四种常用的存储表示方法2．算法的描述和分析。
⏹无穷大阶的几种描述方法的区别⏹算法特征及其评价标准⏹算法的时间复杂度和空间复杂度的概念⏹几种常见复杂度的好坏程度⏹就（原）地算法的含义⏹算法描述和算法分析的方法1. 设n是偶数，试计算运行下列程序段后m的值，并给出该程序段的时间复杂度。
m=0;for (i=1; i<=n; i++)for (j=2*i; j<=n; j++)m=m+1;2. 下列算法对一n位二进制数加1，假如无溢出，该算法在最坏情况下时间复杂度是什么？并分析它的平均时间复杂度。
void func (int A[n]) //A[n]中每个元素取值0或1{inti = n;while (A[i] == 1){ A[i] = 0；i-}A[i]=1；}3. 调用下列函数f(n) 回答下列问题:（1）试给出f(n)值的大小，并写出f(n) 值的推导过程;（2）假定n= 5，试指出f(5)值的大小和执行f(5)时的输出结果。
int f(int n){inti, j，k, sum= 0;for(i=1; i<n+1;i++){for(j=n; j>i-1; j--)for(k=1; k<j+1; k++ )sum++;printf("sum=%d\n",sum)}return (sum);}第二章：线性表1．线性表的逻辑结构⏹线性表的逻辑结构特征⏹线性表上定义的基本运算，并能利用基本运算构造出较复杂的运算2．线性表的顺序存储结构⏹顺序表的存储方式及它如何映射线性表中元素之间的逻辑关系⏹顺序表的存储结构定义⏹线性表基本运算在顺序表上的实现方法及其时间性能分析⏹利用顺序表设计算法解决应用问题3．线性表的链式存储结构⏹链表的存储方式及它如何映射线性表中元素之间的逻辑关系⏹链表中头指针和头节点的使用⏹单链表、双链表、循环链表在链接方式上的区别⏹各种链表的存储结构定义⏹线性表基本运算在链表上的实现方法及其时间性能分析⏹循环链表上尾指针取代头指针的作用⏹利用链表设计算法解决简单的应用问题4．顺序表和链表的比较⏹顺序表和链表的主要优缺点⏹根据应用问题的时空要求，为线性表选择合理的存储结构1.假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。
请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。
节点结构：typedefstruct node{int data;struct node *next;} linknode,*link;link Union(link la,lb)2.请在下列算法的横线上填入适当的语句。
typedefstruct node{int data; struct node *next;}linknode,*link;bool inclusion(link ha,linkhb):boolean;/*以ha和hb为头指针的带头节点单链表分别表示递增有序表A和B，本算法判别表A是否包含在表B 内，若是，则返回“true”，否则返回“false”*/{ pa=ha->next; pb=hb->next; （1）;while (（2）){if (pa->data==pb->data )（3）;else（4）;}（5）; }3. 请写一算法link LinkListSort(link la) ，将不带头结点的单链表按结点数据域的值的大小从小到大重新链接。
要求链接过程中不得使用除该链表以外的任何链结点空间。
typedefstruct node{int data; struct node *next;}linknode,*link;linkLinkListSort(link list)4. 写出下图双链表中对换值为23和15的两个结点相互位置时修改指针的有关语句。
结点结构为：(prev,data,next)第三章：栈与队列1．栈的逻辑结构，存储结构及其相关算法⏹栈的逻辑结构特点，栈与栈性表的关系⏹顺序栈和链栈的存储结构定义⏹顺序栈和链栈上进栈、退栈等基本运算的实现方法⏹已知入栈序列求可能的出栈序列⏹栈上的“上溢”和“下溢”的概念及其判别条件⏹递归过程中栈的作用⏹设计递归程序的原则和方法⏹递归程序改写为非递归程序的方法⏹利用栈设计算法解决简单的应用问题2.队列的逻辑结构，存储结构及其相关算法⏹队列的逻辑结构特点，队列与线性表的关系⏹顺序队列和链队列的存储结构定义⏹顺序队列（主要是循环队列）和链队列上入队、出队、求队列中元素个数等基本运算的实现方法⏹队列的“上溢”和“下溢”的概念及其判别条件⏹循环队列取代普通的顺序队列的原因⏹利用队列设计算法解决简单的应用问题1.试推导求解n 阶hanoi塔问题至少要执行的移动操作move 次数。
2.试证明：若借助栈由输入序列1,2,…,n得到输出序列为P1,P2,…,P n（它是输入序列的一个排列），则在输出序列中不可能出现这样的情形：存在着i<j<k,使P j<P k<P i。
3. 假设以I和O分别表示入栈和出栈操作。
栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。
（1）下面所示的序列中哪些是合法的？A. IOIIOIOOB. IOOIOIIOC. IIIOIOIOD. IIIOOIOO（2）通过对（1）的分析，写出一个算法，形式如下：bool Judge(char A[]) ，判定所给的操作序列是否合法。
若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组A[]中）。
第四章：字符串与模式匹配1．串及其运算⏹串的概念及其与线性表的关系⏹串上定义的基本运算2．串的存储结构和基本运算的实现⏹串的两种主要存储结构—顺序串和链串的存储结构定义⏹顺序串上串的基本运算的实现⏹朴素的模式匹配算法与KMP算法的算法思想及时间复杂度分析⏹KMP算法中next和nextval数组的含义和求值方法1. 分别求出下列模式串的next和nextval数组值t1=‘aaab’ t2=‘abcabaa’ t3=‘adabbadada’2.重复子串的含义是由一个或多个连续相等的字符组成的子串;现有某个串用一维字符数组s存储，长度为n，设计算法求s的最长重复子串的长度.int LongestString(char s[],int n) //函数返回所求长度第五章：数组与广义表1. 数组和矩阵⏹多维数组的逻辑结构特征，多维数组和线性表的关系⏹多维数组的顺序存储结构及地址计算方法⏹数组是一种随机存取结构的原因⏹对称矩阵和稀疏矩阵的概念⏹对称矩阵在压缩存储时的下标变换方法⏹稀疏矩阵的三元组表和十字链表表示方法⏹稀疏矩阵压缩存储后不能进行随机存取的原因2. 广义表⏹广义表的有关概念及其与线性表的关系⏹求给定非空广义表的表头和表尾运算⏹广义表的两种主要链式存储结构的表示方法1.设有三对角矩阵(a ij)n⨯n，将其三条对角线上的元素存于数组B(-1:1, 1:n)中，使得B(u,v)=a ij，试推倒出用i、j表示u、v的下标变换公式。
2. 设对称矩阵A如下所示：(1) 若将A视为对称矩阵，画出对其压缩存储的存储表，并讨论如何存取A中元素a ij (1<=i,j<=4)；(2) 若将A视为稀疏矩阵，画出A的十字链表结构。
⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡433423.求下列广义表操作的结果：(1)Head[T ail[Head[((a,b),(c,d))]]](2)T ail[Head[Tail [((a,b),(c,d))]]]注：[ ]是函数的符号4.利用广义表的Head和T ail操作把原子c从广义表L=((a,b),(c,d))中分离出来，并求表L的长度和深度。
第六章：树与二叉树1．树的概念⏹树的逻辑结构特征⏹树的常用术语及含义2．二叉树⏹二叉树的定义，二叉树与树的差别⏹完全二叉树和满二叉树的概念⏹二叉树的性质⏹二叉树的顺序存储结构（完全二叉树方式/三元组/双亲）的定义和表示方法⏹二叉树的链式存储结构的定义和表示方法3．二叉树的遍历⏹二叉树的先序、中序、后序、层序遍历算法⏹求给定二叉树的先序、中序、后序遍历对应的结点访问序列⏹由二叉树的先序和中序、中序和后序、中序和层序的序列确定二叉树⏹以遍历算法为基础，设计有关算法解决简单的应用问题4．线索二叉树⏹二叉树线索化的目的⏹线索二叉树存储结构的表示方法⏹在线索二叉树中查找给定结点的前趋和后继的方法5．树和森林⏹树和森林与二叉树之间的转换方法和对应关系⏹树的各种存储结构的表示方法及其特点⏹树的先序和后序遍历方法⏹森林的先序和中序遍历方法⏹利用树/森林设计算法解决简单的应用问题6．哈夫曼树及其应用⏹最优二叉树的概念及特点⏹求哈夫曼树的方法⏹设计哈夫曼编码的方法7. 并查集⏹等价类和并查集的定义⏹等价类与树的关系⏹几种并操作和查操作的方法⏹不同并操作和查操作的时间性能分析1. 设某二叉树的先序遍历序列为:ABCDEFGGI，中序遍历序列为:BCAEDGHFI：（1）试画出该二叉树对应的后序线索二叉树；（2）将（1）所得的二叉树转化为对应的树或森林；（3）设具有四个结点的二叉树的前序遍历序列为ａｂｃｄ；Ｓ为长度等于四的由ａ，ｂ，ｃ，ｄ排列构成的字符序列，若任取Ｓ作为上述算法的中序遍历序列，试问是否一定能构造出相应的二叉树，为什么？试列出具有四个结点二叉树的全部形态及相应的中序遍历序列。
2. 试编写算法，判断两颗棵以二叉链表表示的二叉树p和q是否相似。
bool Similar(bitptr p, bitptr q)//若相似函数返回TRUE，否则为FLASE3. 编写算法判断一棵二叉树是否为完全二叉树。
boolJudgeComplete(bitptrbt)第2.3题算法设计时二叉树均采用如下结构存储typedefstruct node{elemtype data ;struct node *lchild, *rchild;}btnode, *bitptr ;4. 设计算法求二叉链表表示的树的度。
typedefstruct node {etype data;node *firstchild, *nextsibling;} node, *bitptr;int degree( bitptr root )5.一个深度为L的满K叉树有以下性质：第L层上的结点都是叶子结点，其余各层上每个结点都有K棵非空子树，如果按层次顺序从1开始对全部结点进行编号，求：1）各层的结点的数目是多少？2）编号为n的结点的双亲结点（若存在）的编号是多少？3）编号为n的结点的第i个孩子结点（若存在）的编号是多少？4）编号为n的结点有右兄弟的条件是什么？如果有，其右兄弟的编号是多少？请给出计算和推导过程。