南昌航空大学数据结构复习(有试题,有答案)

数据结构复习提纲第一章数据结构的概念及基本结构，数据结构在计算机中的表示方法及其存储结构算法的特性，会计算时间复杂度第二章线性表的顺序存储表示，掌握插入和删除操作，线性表的链式存储表示，掌握单链表的插入和删除操作第三章栈的定义及特点，栈的顺序存储表示队列的定义及特点，链队列的插入和删除，循环队列的判空判满条件第四章串的概念及常用操作，掌握模式串next函数的求法第五章特殊矩阵的存储表示，稀疏矩阵的三元组表示，会求广义表的头部和尾部第六章树的定义和基本概念，二叉树的性质，二叉树的链式存储结构二叉链表二叉树的先序，中序，后序,层次遍历操作会对二叉树进行先序，中序，后序线索化操作树的存储结构孩子兄弟表示法树，森林，二叉树三者之间的转换方法，以及它们遍历的对应关系掌握哈夫曼树的构造，会求树的带权路径长度WPL第七章图的定义和术语，图的邻接矩阵表示法，邻接表，逆邻接表掌握图的深度优先搜索算法，广度优先搜索算法最小生成树普里姆算法和克鲁斯卡尔算法，会对AOV网进行拓扑排序会求AOE网的关键路径，关键活动第九章顺序查找表，有序表的折半查找，索引查找表及其平均查找长度ASL二叉排序树的建立和删除操作，会计算其平均查找长度ASL掌握将二叉排序树转换成平衡二叉树的旋转处理方法，哈希表的概念，掌握哈希函数的构造方法一一除留余数法掌握处理冲突的方法线性探测再散列及平均查找长度ASL二次探测再散列及平均查找长度ASL第十章直接插入排序，希尔排序，快速排序，简单选择排序，堆排序，归并排序会写上述排序算法每趟排序的结果，并对其进行排序性能分析（稳定性，时间复杂度等）期末考试题型：选择题，填空题，综合题练习题、单选题1.一个栈的输入序列为A.1，3，2，4B.21，2，3，4，下面哪一个序列不可能是这个栈的输出序列？（，3，4，1c）C.4，3，1，2D.3，4，2，1下列排序方法中，关键字的比较次数与记录的初始排列状态无关？（c）A.直接插入排序B.起泡排序C.快速排序D.直接选择排序对n个记录的文件进行二路归并排序，总的时间代价为（d）2A.O（nlogn）B.O（n2）C.O（logn）D.O（n）若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是（b）A.9B.11C.12D.不确定5在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（d）A.q一>next=p一>next；p>next=q;B.p一>next=q一>next；q=p;C.q一>next=p一>next；p>next=q;D.p一>next=q一>next；q一>next=p;6. 广义表A=（a,b,（c,d）,（e,（f,g）,则式子Head（Tail（Head（Tail（Tail（A）的值为d7. A（g）直接插入排序在最好情况下的时间复杂度为（d）。2A.O（logn）B.O（n）C.O（n*logn）D（n2）8数据结构是（b）A.种数据类型B数据的存储结构C.一组性质相同的数据元素的集合D相互之间存在一种或多种特定关系的数据元素的集合9算法分析的目的是（）A.辨别数据结构的合理性B评价算法的效率C.研究算法中输入与输出的关系D鉴别算法的可读性10. 在线性表的下列运算中，不改变数据元素之间结构关系的运算是（）A.插入B.删除C.排序D.定位11. 二维数组A89按行优先顺序存储，若数组元素A23的存储地址为1087,A47的存储地址为1153，则数组元素A67的存储地址为（）A.1207B.1209C.1211D.121312.在按层次遍历二叉树的算法中,需要借助的辅助数据结构是（）A.队列B.栈C.线性表D.有序表13. 在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系()A.不一定相同B都相同C都不相同D互为逆序14. 若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的(c)A.层次遍历B前序遍历C中序遍历D后序遍历15. 若用邻接矩阵表示一个有向图，则其中每一列包含的T的个数为()A.图中每个顶点的入度B.图中每个顶点的出度C.图中弧的条数D图中连通分量的数目16. 图的邻接矩阵表示法适用于表示()A.无向图B.有向图C.稠密图D.稀疏图17. 在对n个关键字进行简单选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中关键字元素的个数为()A.iB.i+1C.n-iD.n-i+118. 下列排序算法中，其时间复杂度和记录的初始排列无关的是(c)A.插入排序B.堆排序C.快速排序D.冒泡排序19、冒泡排序是(a)的排序方法A、稳定B、不稳定C、外部D、选择20. 若有序表的关键字序列为(b,c,d,e,f,g,q,r,s,t)，则在二分查找关键字b的过程中，先后进行比较的关键字依次为(b)21. A.f,c,bB.f,d,bC.g,c,bD.g,d,b主串S="abc123def123gh123ij"，若对子串T="123"执行定位操作Index(S,T,9)，则操作的结果是_d_。A)2B)3C)4D)1022. 设有一个10阶的对称矩阵A,采有压缩存储方式，以行序为存储主序，若a(1,1)为第一个元素，其存储地址为1，且每个元素占用1个地址空间，则a(8,5)元素的地址为。A)13B)33C)18D)40二、填空题1. 从逻辑结构看，线性表是典型的线性结构，树是典型的树形结构。2. 一棵含999个结点的完全二叉树的深度为10。3.含n个顶点的无向连通图中至少含有条边。若对关键字序列(43,02,80,48,26,57,15,73,21,24,66)进行一趟增量为3的希尔排序，则得到的结果为。4. 数据的逻辑结构被分为集合、线性结构、树形结构和图形结构四种。6.在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的行号_、_列号_和_元素值_三项。7在一棵二叉树中，第5层上的结点数最多为。8. 以折半查找方法查找一个线性表时，此线性表必须是存储的表。9快速排序在平均情况下的时间复杂度为，在最坏情况下的时间复杂度为。10. 假定一组记录的排序码为(46,79,56,38,40,80,36,40,75,66,84,24),对其进行归并排序的过程中，第三趟归并后的结果为：。11. 对于一个具有n个结点和e条边的无向图，若采用邻接表表示，则顶点表的大小为，所有边链表中边结点的总数为。12. 采用邻接表存储的图的深度优先遍历算法类似于树的。13. 采用邻接表存储的图的广度优先遍历算法类似于树的。三、综合题1. 设待排序文件的关键码为(512,275,908,677,503,765,612,897,154,170)以第一个元素为枢轴进行快速排序(按关键码值递增顺序)，请给出每趟排序的结果。2. 从空树起，依次插入关键字37,50,42,18,48,12,56,30,23,构造一棵二叉排序树。(1) 画出该二叉排序树；(2) 画出从(1)所得树中删除关键字为37的结点之后的二叉排序树。3. 设散列表的长度为13;散列函数为H(Key)=Keymodp,给定的关键码序列为19,14,23,01,68,20,84,27,55,11,试画出用线性探测再散列法解决冲突时所构造的散列表，并求出在等概率的情况下查找成功时的平均查找长度ASL。4. 画出在一个初始为空的AVL树中依次插入关键字3,1,4,6,9,8,5,7时AVL树的形态。5. 写出串S的next函数值。S=abcabaanexti=6. 已知二叉树的先序序列和中序序列分别为HDACBGF和ADCBHFEG(1)画出该二叉树；(2)画出与(1)求得的二叉树对应的森林。7.某通讯系统只可能有A,B,C,D,E,F这6种字符，其出现的概率分别是0.1,0.4,0.04,0.16,0.19,0.11,试画出相应的哈夫曼树，设计哈夫曼编码。8.设s="IAMASTUDENT",t="GOOD",q="WORKER",求以下表达式的结果。(1) Replace(s,"STUDENT",q)9. Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)写出以下程序段的输出结果(队列中的元素类型QElemType为char)。(4分)voidmain()QueueQ;InitQueue(Q);charx=e',y=c'；EnQueue(Q,'h');EnQueue(Q,r');EnQueue(Q,y);DeQueue(Q,x);EnQueue(Q,x);DeQueue(Q,x);EnQueue(Q,a');while(!QueueEmpty(Q)DeQueue(Q,y);printf(y);printf(x);10. 输出结果为程序填空：对有序表R1至Rn进行二分查找，成功时返回记录在表中的位置，失败时返回0。(6分)structsqlistkeytypekey;intbinsrch(sqlistR,keytypek)/在表R中查找关键字kintlow,high,mid;low=1;high=n;while()mid=(low+high)/2;if(k=Rmid.key)returnmid;elseif(k<Rmid.key);else;return0;11.求下列无向带权图的最小生成树。12阅读下列函数F,并回答问题：(1)如图所示的二叉树以二叉链表结构存储,说明函数F的功能。voidF(BinTreeT)rt为指向根结点的指针。写出调用函数F(rt)的输出结果。StackS;if(T)InitStack(&S);Push(&S,NULL);while(T)printf("%c",T->data);if(T->rchild)Push(&S,T->rchild);if(T->lchild)T=T->lchild;elseT=Pop(&S);