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

《数据结构》复习提纲第一章算法的特性，会计算时间复杂度第二章线性表的顺序存储表示，掌握插入和删除操作，线性表的链式存储表示，掌握单链表的插入和删除操作第三章栈的定义及特点，栈的顺序存储表示队列的定义及特点，链队列的插入和删除，循环队列的判空判满条件第四章串的概念及常用操作，掌握模式串next函数的求法第五章会求广义表的头部和尾部第六章二叉树的先序，中序，后序,层次遍历操作会对二叉树进行先序，中序，后序线索化操作树的存储结构――－孩子兄弟表示法WPL第七章掌握图的深度优先搜索算法，广度优先搜索算法AOV网进行拓扑排序会求AOE网的关键路径，关键活动第九章顺序查找表，有序表的折半查找，索引查找表及其平均查找长度ASL二叉排序树的建立和删除操作，会计算其平均查找长度ASL掌握将二叉排序树转换成平衡二叉树的旋转处理方法，哈希表的概念，掌握哈希函数的构造方法――除留余数法ASLASL第十章直接插入排序，希尔排序，快速排序，简单选择排序，堆排序，归并排序会写上述排序算法每趟排序的结果，并对其进行排序性能分析（稳定性，时间复杂度等）期末考试题型：选择题，填空题，综合题练习题一、单选题一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列A.1，3，2，4 B.2，3，4，1C.4，3，1，2 D.3，4，2，1下列排序方法中，关键字的比较次数与记录的初始排列状态无关？（c）A.直接插入排序 B.起泡排序C.快速排序 D.直接选择排序n（d）A.O（nlogn）B.O（n2）C.O（logn） D.O（n）若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是（b ）A.9 B.11 C.12 D.不确定HL中，若要在指针qpA．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；广义表A=（a,b,(c,d),(e,(f,g))）,则式子Head(Tail(Head(Tail(Tail(A)))))的值为 d；Ag） B.(d) C.c D.d直接插入排序在最好情况下的时间复杂度为d。A.O(logn) B.O(n) C.O(n*logn) 8．数据结构是（ b）A．一种数据类型 B．数据的存储结构C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集9．算法分析的目的是（ ）A．辨别数据结构的合理性 B．评价算法的效率C．研究算法中输入与输出的关系 D．鉴别算法的可读性10．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（ A．插入B．删除 C．排序 D．定位二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，A[4][7]的存储地为1153，则数组元素A[6][7]的存储地址为（ ）A．1207B．1209 C．1211 D．1213在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（ ）队列B．栈 C．线性表D．有序表在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（ ）A．不一定相同B．都相同 C．都不相同D．互为逆序14．若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的（c 层次遍历 B．前序遍历 C．中序遍历 D．后序遍历15．若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（ A．图中每个顶点的入度B．图中每个顶点的出度C．图中弧的条数D．图中连通分量的数目图的邻接矩阵表示法适用于表示（ ）A．无向图 B．有向图 C．稠密图 D．稀疏图在对n个关键字进行简单选择排序的过程中每一趟都要从无序区选出最小关键字元素则在进第i趟排序之前，无序区中关键字元素的个数为（ ）A．i B．i+1 C．n-i D．n-i+118．下列排序算法中，其时间复杂度和记录的初始排列无关的是（c A．插入排序 B．堆排序 C．快速排序 D．冒泡排19、冒泡排序是（a）的排序方法A、稳定 B、不稳定 C、外部 D、选择若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进比较的关键字依次为（b ）A．f,c,b B．f,d,b C．g,c,b D．g,d,bS="abc123def123gh123ijT="123Index(S,T,9)，则操作的结果是 d_。A)2B)3C)4D)10设有一个10阶的对称矩阵A，采有压缩存储方式，以行序为存储主序，若a(1,1)为第一个元素，存储地址为1，且每个元素占用1个地址空间，则a(8,5)元素的地址为 。A)13B)33C)18D)40二、填空题从逻辑结构看，线性表是典型线性结构 ，树是典型树形结构 。一棵含999个结点的完全二叉树的深度为 10_ 。含n个顶点的无向连通图中至少含条边。4.若对关键字序列（43，02，80，48，26，57，15，73，21，24，66）进行一趟增量为3的希尔序，则得到的结果为 。数据的逻辑结构被分集合

线性结构

树形结构图形结构 四种。在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素行号_列号_和_元素值 三项。在一棵二叉树中，第5层上的结点数最多为 。以折半查找方法查找一个线性表时，此线性表必须存储的 表。快速排序在平均情况下的时间复杂度，在最坏情况下的时间复杂度。10.假定一组记录的排序码为（46，79，56，38，40，80，36，40，75，66，84，24），对其进行并排序的过程中，第三趟归并后的结果为。对于一个具有n个结点和e条边的无向图，若采用邻接表表示，则顶点表的大小，所边链表中边结点的总数。采用邻接表存储的图的深度优先遍历算法类似于树。采用邻接表存储的图的广度优先遍历算法类似于树三、综合题1.设待排序文件的关键码为（512,275,908,677,503,765,612,897,154,170）以第一个元素为枢轴进行快速排序（按关键码值递增顺序），请给出每趟排序的结果。2.从空树起，依次插入关键字37，50，42，18，48，12，56，30，23，构造一棵二叉排序树。画出该二叉排序树；画出从（1）37的结点之后的二叉排序树。13H(Key)=Keymodp,给定的关键码序列为19,14,23,01,68,20,84,27,55,11,试画出用线性探测再散列法解决冲突时所构造的散列表，并求出在等概率的情况下查找成功时的平均查找长度ASL。画出在一个初始为空的AVL3,1,4,6,9,8,5,7AVLSnextS=a b c a b a anext[i]= 已知二叉树的先序序列和中序序列分别为HDACBGFEADCBHFEG。画出该二叉树；画出与（1）求得的二叉树对应的森林。7．某通讯系统只可能有A,B,C,D,E,F这6种字符，其出现的概率分别是0.1,0.4,0.04,0.16,0.19,0.11,试画出相应的哈夫曼树，设计哈夫曼编码。s="IAMASTUDENT",t="GOOD",q="WORKER",求以下表达式的结果。Replace(s,"STUDENT",q)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);}输出结果 程序填空：对有序表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(k<R[mid].key) else ;}return0;}求下列无向带权图的最小生成树。bb9e4573a5d6f3c5245g5h6F，并回答问题：(1)如图所示的二叉树以二叉链表结构存储，rt为指向根结点