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

《数据结构》复习提纲第一章数据结构的概念及基本结构，数据结构在计算机中的表示方法及其存储结构算法的特性，会计算时间复杂度第二章线性表的顺序存储表示，掌握插入和删除操作，线性表的链式存储表示，掌握单链表的插入和删除操作第三章栈的定义及特点，栈的顺序存储表示队列的定义及特点，链队列的插入和删除，循环队列的判空判满条件第四章串的概念及常用操作，掌握模式串next函数的求法第五章特殊矩阵的存储表示，稀疏矩阵的三元组表示，会求广义表的头部和尾部第六章树的定义和基本概念，二叉树的性质，二叉树的链式存储结构――二叉链表二叉树的先序，中序，后序,层次遍历操作会对二叉树进行先序，中序，后序线索化操作树的存储结构――－孩子兄弟表示法树，森林，二叉树三者之间的转换方法，以及它们遍历的对应关系掌握哈夫曼树的构造，会求树的带权路径长度WPL第七章图的定义和术语，图的邻接矩阵表示法，邻接表，逆邻接表掌握图的深度优先搜索算法，广度优先搜索算法最小生成树――普里姆算法和克鲁斯卡尔算法，会对AOV网进行拓扑排序会求AOE网的关键路径，关键活动第九章顺序查找表，有序表的折半查找，索引查找表及其平均查找长度ASL二叉排序树的建立和删除操作，会计算其平均查找长度ASL掌握将二叉排序树转换成平衡二叉树的旋转处理方法，哈希表的概念，掌握哈希函数的构造方法――除留余数法掌握处理冲突的方法――线性探测再散列及平均查找长度ASL――二次探测再散列及平均查找长度ASL第十章直接插入排序，希尔排序，快速排序，简单选择排序，堆排序，归并排序会写上述排序算法每趟排序的结果，并对其进行排序性能分析（稳定性，时间复杂度等）期末考试题型：选择题，填空题，综合题练习题一、单选题1.一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列？（c）A.1，3，2，4B.2，3，4，1C.4，3，1，2D.3，4，2，12.下列排序方法中，关键字的比较次数与记录的初始排列状态无关？（c）A.直接插入排序B.起泡排序C.快速排序D.直接选择排序3.对n个记录的文件进行二路归并排序，总的时间代价为（d）A.O（nlogn）B.O（n2）C.O（logn）D.O（n）4.若一棵二叉树具有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)))))的值为d；A．（g）B.(d)C.cD.d7.直接插入排序在最好情况下的时间复杂度为（d）。A.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．二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，A[4][7]的存储地址为1153，则数组元素A[6][7]的存储地址为（）A．1207B．1209C．1211D．121312．在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（）A．队列B．栈C．线性表D．有序表13．在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（）A．不一定相同B．都相同C．都不相同D．互为逆序14．若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的（c）A．层次遍历B．前序遍历C．中序遍历D．后序遍历15．若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（）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）A．f,c,bB．f,d,bC．g,c,bD．g,d,b21.主串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个顶点的无向连通图中至少含有______条边。4.若对关键字序列（43，02，80，48，26，57，15，73，21，24，66）进行一趟增量为3的希尔排序，则得到的结果为______。5．数据的逻辑结构被分为______集合_____、___线性结构___、_树形结构和____图形结构__四种。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=abcabaanext[i]=6.已知二叉树的先序序列和中序序列分别为HDACBGFE和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)(2)Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)))9.写出以下程序段的输出结果（队列中的元素类型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.程序填空：对有序表R[1]至R[n]进行二分查找，成功时返回记录在表中的位置，失败时返回0。（6分）structsqlist{keytypekey;};intbinsrch(sqlistR[],keytypek)//在表R中查找关键字k{intlow,high,mid;low=1;high=n;while()mid=(low+high)/2;if(k==R[mid].key)returnmid;elseif(kR[mid].key);else;}return0;}11.求下列无向带权图的最小生成树。12.阅读下列函数F，并回答问题：(1)如图所示的二叉树以二叉链表结构存储，rt为指向根结点的指针。写出调用函数F(rt)的输出结果。(2)说明函数F的功能。voidF(BinTreeT){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);}}}befgdac3554556267534h9