2012级数据结构期末试题提纲

１数据结构期末复习提纲（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．39B．41C．43D．455．用一个大小为1000的数组来实现循环队列，当前的队头和队尾指针分别为4和996，若要达到队列满的条件，可以继续入队的元素个数是A．5B．6C．7D．86．多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为A．数组的元素处在行和列两个关系中B．数组的元素必须从左到右顺序排列C．数组的元素之间存在次序关系D．数组是多维结构，内存是一维结构7.已知一棵含50个结点的二叉树中只有一个叶子结点，则该二叉树与所对应的孩子兄弟链表表示的二叉树的高度相比A.前者比后者低B.前者比后者高C.前者与后者相同D.不易确定8.假设一棵完全二叉树中的第6层上有24个叶子结点，则该二叉树的结点个数最多为A.55B.79C.81D.1279．设某棵二叉树的中序遍历序列为ABCDE，后序遍历序列为BADEC，则该二叉树的层次遍历序列为４A．BADCEB．BCDAEC．CAEBDD．CBDAE10.如果某图的邻接矩阵是非对称矩阵，则此图一定不．是A.有环图B.有向无环图C.强连通图D.上述答案有错11.若一个具有N个顶点和K条边的无向图（NK）是一个森林，则该森林的数目一定是A．KB．NC．N-KD．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,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分）16.双端队列是一种插入和删除仅在线性表的两端都可进行的线性表。若允许一端进行插入和删除，另一端只允许删除的双端队列为输入受限的双端队列。假设输入序列为1，2，3，4。双端队列的左端为单输入端。试求：（1）画出输入受限的双端队列的示意图。（2）给出单输入端的输出端口不可能得到的输出序列。（至少5种）17.已知带有双亲指针域的二叉树的结点类型PTNnde逻辑结构如下所示：LchildDataParentRchild试求：（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为顺序表类型，阅读下列算法，回答问题。voidSq_F(SqList&L{1.for(i=j=0;iL.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个结点置逆。函数原型定义如下：voidshift_right_k(LinkList&L,LinkListp,LinkListpre,intk)试求：（1）算法描述。（2）算法实现。五、算法设计题（本题10分）已知二叉树T的结点BNode的逻辑结构示意图如下：BNodeLchilddataRchild试求：设计算法，求二叉树中单分支结点的个数。函数原型定义如下：voidSnode_T(BNode*&T,int&count)六、算法设计题（本题10分）已知图的邻接矩阵结构定义如下：#defineMaxNum20typedefintAdjMatrix[MaxNum][MaxNum];typedefstruct{ElenTypeVexs[MaxNum];//顶点数组AdjMatrixarcs;//邻接矩阵intn,e;//图中当前的顶点数和边数}MGraph;//邻接矩阵图栈的一些基本操作定义如下：voidInitStack(SqStack&S)//voidPush(SqStack&S,ElemTypee)//voidPop(SqStack&S,ElemType&e)//intStackEmpty(SqStackS)//voidGetTop(SqStackS,ElemType&e)//试求：设计邻接矩阵图的拓扑排序算法。（可以使用栈的基本操作）函数原型定义如下：intTopo_G(MGraphG,SqStackS)薃肀莂蒃袂肀肂虿袈聿芄薂螄肈莇螇蚀肇葿薀罿肆腿莃袅肅芁薈螁膄莃莁蚇膄肃薇薃膃芅荿羁膂莈蚅袇膁蒀蒈螃膀膀蚃虿腿节蒆羈芈莄蚁袄芈蒆蒄螀芇膆蚀蚆袃莈蒃蚂袂蒁螈羀袁膀薁袆袁芃螆螂袀莅蕿蚈衿蒇莂羇羈膇薇袃羇艿莀蝿羆蒂薆螅羅膁蒈蚁羅芄蚄罿羄莆蒇袅羃蒈蚂螁羂膈蒅蚇肁芀蚁薃肀莂蒃袂肀肂虿袈聿芄薂螄肈莇螇蚀