数据结构期末试题提纲

1、数据结构期末复习提纲（ 2012 级）A 、总体要求：1、掌握数据结构的基本概念、基本原理和基本方法。2、掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度 和空间复杂度的分析。3、能够运用数据结构的基本原理和方法进行问题的分析与求解，具备采用C 语言和 C+ 语言设计与实现算法的能力。一、基本概念1、数据结构、数据元素、数据项、数据类型、抽象数据类型、算法、算法的时间复杂度、 算法的空间复杂度、算法的评价标准。2、数据结构的逻辑结构和存储结构及分类。3、线性表的定义及特点。4、顺序表、单链表、双向链表、循环链表、静态链表的存储结构。5、栈和队列的定义及特点。6、顺序

2、栈、链栈、顺序队列、链队列的存储结构。7、字符串的定义及特点。8、顺序串和链串的存储结构。9、数组的定义及特点。10、数组的按行存储与按列存储。11、对称矩阵、三角矩阵、稀疏矩阵的压缩存储。12、二叉树的定义、一般术语及特点。13、二叉树的五个基本性质。14、完全二叉树与满二叉树的概念。15、二叉树的顺序存储结构。16、二叉树的二叉链表与三叉链表存储结构。17、二叉树的四种遍历方式及特点。18、线索二叉树的存储结构及特点。19、树和森林的概念。20、树的双亲链表和孩子兄弟链表存储结构。21、树和森林的二种遍历方式。22、图的定义、一般术语及特点。23、图的邻接矩阵、邻接表、逆邻接表存储结构。2

3、4、图的二种遍历方式及特点、优先遍历生成树的概念。25、图的连通性、连通图、连通分量的概念。26、有向无环图的概念及特点。27、查找、查找表、关键字的概念。28、顺序查找、折半查找、分块索引查找的概念。29、二叉排序树和平衡二叉树的定义及特点，平衡因子的概念。30、B_树的定义及存储结构特点。31、哈希函数、哈希表、哈希冲突、哈希查找的概念。32、哈希表装填因子的定义及作用。33、内部排序、外部排序、排序方法、传统排序和优化排序的概念。34、希尔排序、快速排序、堆排序、归并排序、基数排序的概念。35、排序方法的稳定性概念。二、数据结构的基本操作算法1、顺序表与单链表的创建、查找、插入、删除、遍

4、历操作算法。2、顺序栈的创建、初始化、取栈顶元素、出栈、入栈操作算法。3、顺序队列和循环队列的创建、初始化、取队头元素、出队、入队操作算法。4、二叉树的先序、中序、后序遍历的递归算法。5、中序线索二叉树的创建和遍历操作算法。6、树和森林的孩子兄弟链表结构的先序和后序遍历操作算法。7、图的邻接矩阵和邻接表结构的创建操作算法。8、图的深度优先和广度优先遍历算法。9、有序顺序表的折半查找算法。10、二叉排序树的创建、查找、插入、删除算法。11、传统的插入、选择、交换排序算法。12、一趟快速排序、归并排序的算法。三、基本方法1、简单程序的算法时间复杂度和空间复杂度的分析。2、比较顺序表与链表、单链表、

5、双向链表、循环链表的应用特点。3、顺序栈的简单应用。4、循环队列和双端队列的特点及简单应用。5、二维、三维数组的按行、按列展开的地址计算及转换。6、二叉树基本性质的应用及简单计算。7、已知二叉树的遍历，求二叉树的形态。8、已知二叉树，画出线索二叉树。9、森林与二叉树的转换方法。10、哈夫曼树的构造和编码方法。11、图的邻接矩阵和邻接表结构及逆邻接表结构的转换方法。12、连通分量、强连通分量的求解方法。13、深度优先和广度优先遍历最小生成树的求解方法。14、最小生成树的求解方法。15、应用栈或队列的拓扑排序的求解方法。16、关键路径的求解方法。17、迪杰斯特拉求解单源最短路径的方法。18、判定树

6、的构造方法及平均查找长度的计算。19、平衡二叉树的构造方法、平衡因子的计算。20、线性探测再散列和链地址法解决冲突的哈希表构造方法，并计算平均查找长度。21、B_树的构造和查找方法。22、希尔排序、快速排序、堆排序、归并排序、基数排序的方法。23、排序方法的时间性能、空间性能及稳定性的比较。四、算法应用设计1 、有序顺序表应用，如：合并、查找、排序、消除重复元素等。2、链表应用，如：链表的合并、排序、查找、删除等。3、二叉链表二叉树的遍历应用，如：查找、求高度和宽度等。4、三叉链表的二叉树的非递归遍历算法。5、图的邻接矩阵和邻接表结构及逆邻接表结构的转换算法。6、图的深度优先和广度优先遍历的应

7、用算法，如：查找、求解通路和最短路径等。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. 在下列对顺序表进行的操作中，算法时间复杂度为0（1）的是A. 对顺序表中元素进行排序B. 插入第i个元素C. 删除第i个元

8、素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. 39B. 41C. 43D . 455. 用一个大小为 1000的数组来实现循环队列,当前的队头和队

9、尾指针分别为 4和 996,若 要达到队列满的条件,可以继续入队的元素个数是A. 5B. 6C. 7D . 86. 多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为A. 数组的元素处在行和列两个关系中B. 数组的元素必须从左到右顺序排列C. 数组的元素之间存在次序关系D. 数组是多维结构，内存是一维结构7. 已知一棵含 50 个结点的二叉树中只有一个叶子结点, 则该二叉树与所对应的孩子兄弟链 表表示的二叉树的高度相比A.前者比后者低B. 前者比后者高C.前者与后者相同D. 不易确定8. 假设一棵完全二叉树中的第 6层上有 24个叶子结点,则该二叉树的结点个数最多为A. 55B.79C.

10、 81D.1279.设某棵二叉树的中序遍历序列为ABCDE后序遍历序列为 BADEC则该二叉树的层次遍历序列为A. BADCEBC. CAEBDD. BCDAE. CBDAE10. 如果某图的邻接矩阵是非对称矩阵，则此图一定不.是A. 有环图B.有向无环图C.强连通图D.上述答案有错11. 若一个具有N个顶点和K条边的无向图(N>K是一个森林，则该森林的数目一定是A. KB. NC. N-KD. 112. 已知哈希表的存储空间为T0.18，哈希函数H( key) = key%17,并用线性探测再散列法处理冲突。哈希表中已插入下列关键字：T5=39 , T6=57和T7=7，则下一个关键字

11、23插入的位置是若允许一端进行插入A. T2B. T4先后进行比较的关键字依次为A . f,r,s,tB.f,s,g,qC . g,q,s,tD.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分)C. T8D. T1013 .若有序表的关键字序列为(b,c,d

12、,e,f,g,q,r,s,t)，则在二分查找关键字为w的过程中,16.双端队列是一种插入和删除仅在线性表的两端都可进行的线性表。假设输入序列为1,2,3,和删除，另一端只允许删除的双端队列为输入受限的双端队列。4。双端队列的左端为单输入端。 试求：(1)画出输入受限的双端队列的示意图。(2)给出单输入端的输出端口不可能得到的输出序列。(至少5种)17. 已知带有双亲指针域的二叉树的结点类型PTNn de逻辑结构如下所示：LchildDataPare ntRchild试求：(1)给出该二叉树的存储结构定义。(2)说明在非递归且不使用栈的中序遍历中，Pare nt域的作用。18. 已知一个无向带权

13、图的边结点结构为(顶点 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, 5»。试求：(1)给出该序列的快速排序的前三趟结果。(2)举例说明快速排序的不稳定性。20.已知

14、一组初始记录关键字序列为(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.le ngth;i+)2. if(L.elemi>=0)3. if(i!=j) / 注释(1)4. L. elem j= L.elemi;5. j+; / 注释(2)6. /if7

15、. /for8. L.le ngth=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的前驱结点指针。结点 Ln ode的结构为(data, next)。设计算法，从任意给 定位置开始，将指针 p右边的k个结点置逆。函数原型定义如下：void shift_right_k(LinkList &L, Li

16、nkList p,LinkList pre,int k)试求：(1)算法描述。(2)算法实现。五、 算法设计题(本题10分)已知二叉树T的结点BNode的逻辑结构示意图如下：BNodeLchilddataRchild试求：设计算法，求二叉树中单分支结点的个数。函数原型定义如下：void Snode_T( BNode* &T,int &count)六、算法设计题(本题10分)已知图的邻接矩阵结构定义如下：#define MaxNum 20typedef int AdjMatrixMaxNumMaxNum;typedef struct Ele nType VexsMaxNum; 顶点数组AdjMatrix arcs;/邻接矩阵int n,e;/图中当前的顶点数和边数 MGraph;/邻接矩阵图栈的一些基本操