数据结构期末复习提纲（2012级）A、总体要求：1、掌握数据结构的基本概念、基本原理和基本方法。

2、掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度和空间复杂度的分析。

3、能够运用数据结构的基本原理和方法进行问题的分析与求解，具备采用C语言和C++语言设计与实现算法的能力。

一、基本概念1、数据结构、数据元素、数据项、数据类型、抽象数据类型、算法、算法的时间复杂度、算法的空间复杂度、算法的评价标准。

2、数据结构的逻辑结构和存储结构及分类。

3、线性表的定义及特点。

4、顺序表、单链表、双向链表、循环链表、静态链表的存储结构。

5、栈和队列的定义及特点。

6、顺序栈、链栈、顺序队列、链队列的存储结构。

7、字符串的定义及特点。

8、顺序串和链串的存储结构。

9、数组的定义及特点。

10、数组的按行存储与按列存储。

11、对称矩阵、三角矩阵、稀疏矩阵的压缩存储。

12、二叉树的定义、一般术语及特点。

13、二叉树的五个基本性质。

14、完全二叉树与满二叉树的概念。

15、二叉树的顺序存储结构。

16、二叉树的二叉链表与三叉链表存储结构。

17、二叉树的四种遍历方式及特点。

18、线索二叉树的存储结构及特点。

19、树和森林的概念。

20、树的双亲链表和孩子兄弟链表存储结构。

21、树和森林的二种遍历方式。

22、图的定义、一般术语及特点。

23、图的邻接矩阵、邻接表、逆邻接表存储结构。

24、图的二种遍历方式及特点、优先遍历生成树的概念。

25、图的连通性、连通图、连通分量的概念。

26、有向无环图的概念及特点。

27、查找、查找表、关键字的概念。

28、顺序查找、折半查找、分块索引查找的概念。

29、二叉排序树和平衡二叉树的定义及特点，平衡因子的概念。

30、B_树的定义及存储结构特点。

31、哈希函数、哈希表、哈希冲突、哈希查找的概念。

32、哈希表装填因子的定义及作用。

33、内部排序、外部排序、排序方法、传统排序和优化排序的概念。

34、希尔排序、快速排序、堆排序、归并排序、基数排序的概念。

35、排序方法的稳定性概念。

二、数据结构的基本操作算法1、顺序表与单链表的创建、查找、插入、删除、遍历操作算法。

2、顺序栈的创建、初始化、取栈顶元素、出栈、入栈操作算法。

3、顺序队列和循环队列的创建、初始化、取队头元素、出队、入队操作算法。

4、二叉树的先序、中序、后序遍历的递归算法。

5、中序线索二叉树的创建和遍历操作算法。

6、树和森林的孩子兄弟链表结构的先序和后序遍历操作算法。

7、图的邻接矩阵和邻接表结构的创建操作算法。

8、图的深度优先和广度优先遍历算法。

9、有序顺序表的折半查找算法。

10、二叉排序树的创建、查找、插入、删除算法。

11、传统的插入、选择、交换排序算法。

12、一趟快速排序、归并排序的算法。

三、基本方法1、简单程序的算法时间复杂度和空间复杂度的分析。

2、比较顺序表与链表、单链表、双向链表、循环链表的应用特点。

3、顺序栈的简单应用。

4、循环队列和双端队列的特点及简单应用。

5、二维、三维数组的按行、按列展开的地址计算及转换。

6、二叉树基本性质的应用及简单计算。

7、已知二叉树的遍历，求二叉树的形态。

8、已知二叉树，画出线索二叉树。

9、森林与二叉树的转换方法。

10、哈夫曼树的构造和编码方法。

11、图的邻接矩阵和邻接表结构及逆邻接表结构的转换方法。

12、连通分量、强连通分量的求解方法。

13、深度优先和广度优先遍历最小生成树的求解方法。

14、最小生成树的求解方法。

15、应用栈或队列的拓扑排序的求解方法。

16、关键路径的求解方法。

17、迪杰斯特拉求解单源最短路径的方法。

18、判定树的构造方法及平均查找长度的计算。

19、平衡二叉树的构造方法、平衡因子的计算。

20、线性探测再散列和链地址法解决冲突的哈希表构造方法，并计算平均查找长度。

21、B_树的构造和查找方法。

22、希尔排序、快速排序、堆排序、归并排序、基数排序的方法。

23、排序方法的时间性能、空间性能及稳定性的比较。

四、算法应用设计1、有序顺序表应用，如：合并、查找、排序、消除重复元素等。

2、链表应用，如：链表的合并、排序、查找、删除等。

3、二叉链表二叉树的遍历应用，如：查找、求高度和宽度等。

4、三叉链表的二叉树的非递归遍历算法。

5、图的邻接矩阵和邻接表结构及逆邻接表结构的转换算法。

6、图的深度优先和广度优先遍历的应用算法，如：查找、求解通路和最短路径等。

7、有向无环图的拓扑排序的应用算法。

8、习题集算法例题举例：2.15、2.20、2.29、2.37、6.39、6.41、6.44、6.48、6.52、7.22、7.27、7.34、7.35B、试题举例：数据结构试题（2011级）一、单选题（每小题2分）1．抽象数据类型ADT的三个组成部分是A．数据对象、数据关系和基本操作B．数据元素、逻辑结构和存储结构C．数据项、数据元素和数据类型D．数据元素、数据结构和数据类型2. 在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是A. 对顺序表中元素进行排序B. 插入第i个元素C. 删除第i个元素D. 访问第i个元素的前驱3．设p指向单链表中的一个结点，s指向单链表表外待操作的结点，则下述程序段的功能是：s->next=p->next; p->next=s; t=p->data; p->data=s ->data; s->data=t; A．删除结点pB．插入结点sC．在结点p之后插入结点sD．结点p与插入结点s的数据域互换4．如果入栈序列是1,3,5，…，97,99，且出栈序列的第1个元素为99，则出栈序列中第30个元素是A．39 B．41C．43 D．455．用一个大小为1000的数组来实现循环队列，当前的队头和队尾指针分别为4和996，若要达到队列满的条件，可以继续入队的元素个数是A．5 B．6C．7 D．86．多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为A．数组的元素处在行和列两个关系中B．数组的元素必须从左到右顺序排列C．数组的元素之间存在次序关系D．数组是多维结构，内存是一维结构7. 已知一棵含50个结点的二叉树中只有一个叶子结点，则该二叉树与所对应的孩子兄弟链表表示的二叉树的高度相比A. 前者比后者低B. 前者比后者高C. 前者与后者相同D. 不易确定8. 假设一棵完全二叉树中的第6层上有24个叶子结点，则该二叉树的结点个数最多为A. 55B.79C. 81D.1279．设某棵二叉树的中序遍历序列为ABCDE，后序遍历序列为BADEC，则该二叉树的层次遍历序列为A．BADCE B．BCDAEC．CAEBD D．CBDAE10.如果某图的邻接矩阵是非对称矩阵，则此图一定不．是A. 有环图B. 有向无环图C. 强连通图D. 上述答案有错11. 若一个具有N个顶点和K条边的无向图（N>K）是一个森林，则该森林的数目一定是A．K B．NC．N-K D．112. 已知哈希表的存储空间为T[0..18]，哈希函数H（key）= key%17,并用线性探测再散列法处理冲突。

哈希表中已插入下列关键字：T[5]=39，T[6]=57和T[7]=7，则下一个关键字23插入的位置是A. T[2]B. T[4]C. T[8]D. T[10]13．若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字为w的过程中，先后进行比较的关键字依次为A．f,r,s,t B．f,s,g,qC．g,q,s,t D．g,d,q,s14．对关键字序列（5，1，4，3，7）进行堆排序时，输出第2个元素后的系列结果为A．（1，3，4，5，7） B．（7，3，5，4，1）C．（1，4，3，5，7） D．（7，4，5，3，1）15．下列排序算法中，时间复杂度不受数据初始状态影响，恒为0(nlogn)的是A. 归并排序B. 冒泡排序C. 直接选择排序D. 快速排序二、应用题（每小题6分）16. 双端队列是一种插入和删除仅在线性表的两端都可进行的线性表。

若允许一端进行插入和删除，另一端只允许删除的双端队列为输入受限的双端队列。

假设输入序列为1，2，3，4。

双端队列的左端为单输入端。

试求：（1）画出输入受限的双端队列的示意图。

（2）给出单输入端的输出端口不可能得到的输出序列。

（至少5种）17.试求：（1（2）说明在非递归且不使用栈的中序遍历中，Parent域的作用。

18.已知一个无向带权图的边结点结构为（顶点1，顶点2，权值），顶点集V和边集E分别为：V={1,2,3,4,5};E={<1,2,2>,<1,4,6>,<2,3,8>,<2,4,3>,<3,5,5>,<3,4,2>,<4,5,9>}。

试求：（1）画出该图的邻接矩阵存储结构示意图。

（2）采用普利姆算法，求最小生成树，画出求解过程，给出最小代价的结果。

19．已知一组初始记录关键字序列为(3，9，51，8，4，7，2，52)。

试求：（1）给出该序列的快速排序的前三趟结果。

（2）举例说明快速排序的不稳定性。

20. 已知一组初始记录关键字序列为(35，20，33，48，59，47，62，50，48)。

其哈希函数为H(key)=key%13，处理冲突的方法为链地址法。

试求：（1）设计哈希表。

（2）在等概率查找时查找成功的平均查找长度。

三、算法阅读与分析题（本题10分）已知SqList为顺序表类型，阅读下列算法，回答问题。

void Sq_F(SqList &L {1. for(i=j=0;i<L.length;i++){2. if(L.elem[i]>=0){3. if(i!=j) //注释（1）4. L. elem [j]= L.elem[i];5. j++; //注释（2）6. }//if7. }//for8. L.length=j;9. }// Sq_F试求：（1）说明算法的功能。

（2）在语句3和语句5后面加上注释。

（3）若初始顺序表L=(19，-8，49，-56，-10，10，0，20，-50)，给出算法执行后L 的结果。

四、算法设计题（本题10分）已知LinkList为单链表类型，L为带头结点的单链表的头指针。

指针p为当前访问的结点指针，pre为p的前驱结点指针。

结点Lnode的结构为（data,next）。

设计算法，从任意给定位置开始，将指针p右边的k个结点置逆。

函数原型定义如下：void shift_right_k(LinkList &L, LinkList p,LinkList pre,int k)试求：（1）算法描述。