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

《南昌航空大学 数据结构复习(有试题,有答案).pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》复习提纲第一章数据结构的概念及基本结构，数据结构在计算机中的表示方法及其存储结构算法的特性，会计算时间复杂度第二章线性表的顺序存储表示，掌握插入和删除操作，线性表的链式存储表示，掌握单链表的插入和删除操作第三章栈的定义及特点，栈的顺序存储表示队列的定义及特点，链队列的插入和删除，循环队列的判空判满条件第四章串的概念及常用操作，掌握模式串next函数的求法第五章特殊矩阵的存储表示，稀疏矩阵的三元组表示，会求广义表的头部和尾部第六章树的定义和基本概念，二叉树的性质，二叉树的链式存储结构――二叉链表二叉树的先序，

2、中序，后序,层次遍历操作会对二叉树进行先序，中序，后序线索化操作树的存储结构――－孩子兄弟表示法树，森林，二叉树三者之间的转换方法，以及它们遍历的对应关系掌握哈夫曼树的构造，会求树的带权路径长度WPL第七章图的定义和术语，图的邻接矩阵表示法，邻接表，逆邻接表掌握图的深度优先搜索算法，广度优先搜索算法最小生成树――普里姆算法和克鲁斯卡尔算法，会对AOV网进行拓扑排序会求AOE网的关键路径，关键活动第九章顺序查找表，有序表的折半查找，索引查找表及其平均查找长度ASL二叉排序树的建立和删除操作，会计算其平均查找长度ASL掌握

3、将二叉排序树转换成平衡二叉树的旋转处理方法，哈希表的概念，掌握哈希函数的构造方法――除留余数法掌握处理冲突的方法――线性探测再散列及平均查找长度ASL　　　　　　　　　――二次探测再散列及平均查找长度ASL第十章直接插入排序，希尔排序，快速排序，简单选择排序，堆排序，归并排序会写上述排序算法每趟排序的结果，并对其进行排序性能分析（稳定性，时间复杂度等）期末考试题型：选择题，填空题，综合题练习题一、单选题1.一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列？（c）A.1，3，2，4B.2，3，4，

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一

5、>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．一组性质

6、相同的数据元素的集合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

7、．在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（　　　）　A．队列B．栈C．线性表D．有序表　13．在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（　　　）　A．不一定相同B．都相同C．都不相同D．互为逆序　14．若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的（　c　　）A．层次遍历B．前序遍历C．中序遍历D．后序遍历　15．若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（　　　）　　A．图中每个顶点的入度B．图中每个顶点的出度　　C．图中弧的条数D．图中连通分

8、量的数目　16．图的邻接矩阵表示法适用于表示（　　　）　　A．无向图B．有向图C．稠密图D．稀疏图17．在对n个关键字进行简单选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中关键字元素的个数为（　　　）A．iB．i+1C．n-iD．n-i+1　18．下列排序算法中，其时间复杂度和记录的初始排