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

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

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

3、握处理冲突的方法0D0D线性探测再散列及平均查找长度ASLDD二次探测再散列及平均查找长度ASL第十章直接插入排序，希尔排序，快速排序，简单选择排序，堆排序，归并排序会写上述排序算法每趟排序的结果，并对其进行排序性能分析(稳定性，时间复杂度 等)期末考试题型：选择题，填空题，综合题练习题一、单选题1. 一个栈的输入序列为1，2, 3, 4,下面哪一个序列不可能是这个栈的输出序列？(c) A. 1, 3, 2, 4 B. 2, 3, 4, 1 C. 4, 3, 1, 2 D. 3, 4, 2, 12. 下列排序方法中，关键字的比较次数与记录的初始排列状态无关？( c ) A.直接插入排序 B.起

4、泡排序C.快速排序D.直接选择排序3. 对n个记录的文件进行二路归并排序，总的时间代价为(d)2A. 0 (nlogn) B. 0 (n) C. 0 (logn) D. 0 (n)4. 若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是(b ) A. 9 B. 11 C. 12 D.不确定5. 在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，贝!|执行(d)A. q>next = p*>next； p >next = q；B. pnext = q一next； q = p；C. q>next = p>next； p 一&g

5、t;next = q；D. p>next = q一next； q>nex t = p：6. 广义表 A 二(a,b, (c, d), (e, (f, g)，则式子 Head (Tail (Head (Tail (Ta il(A)的值为 d :A. (g) B. (d) C. c D. d7. 直接插入排序在最好情况下的时间复杂度为(d)。A. O（logn） B. 0（n） C. 0（n*logn） D（n） 8.数据结构是（b ）A. 一种数据类型B.数据的存储结构C. 一组性质相同的数据元素的集合D.相互之间存在一种或多种特定关系的数据元素的集合9.算法分析的目的是（）A.辨别

6、数据结构的合理性B.评价算法的效率C.研究算法中输入与输出的关系 D.鉴别算法的可读性10. 在线性表的下列运算中，不改变数据元素之间结构关系的运算是（）A.插 入B.删除 C.排序 D.定位11. 二维数组A89按行优先顺序存储，若数组元素A23的存储地址为1087, A47的存储地址为1153,则数组元素A67的存储地址为（）A. 1207 B. 1209 C. 1211D. 121312. 在按层次遍历二义树的算法中，需要借助的辅助数据结构是（）A.队列B.栈 C.线性表D.有序表13. 在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（） A.不一定相同B.都相同 C.

7、都不相同D.互为逆序14. 若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应釆用二义树的（c ）A.层次遍历B.前序遍历C.中序遍历D.后序遍历15. 若用邻接矩阵表示一个有向图，则其中每一列包含的"1"的个数为（）A.图中每个顶点的入度B.图中每个顶点的出度C.图中弧的条数D.图中连通分量的 数目16.图的邻接矩阵表示法适用于表示（）A.无向图 B.有向图 C.稠密 图 D.稀疏图17. 在对n个关键字进行简单选择排序的过程中，每一趟都要从无序区选出最小关键 字元索，则在进行第i趟排序之前，无序区中关键字元素的个数为（）A. iB i+1 C ni D ni+l18.

8、 下列排序算法中，其时间复杂度和记录的初始排列无关的是（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, b B f, d, b C g, c, b D g, d, b21. 主串S=,若对子串T=执行定位操作Index(S, T, 9)，则操作的结果是_d_° A)2B)3 04 D)1022. 设有一个10阶的对称矩阵A,采有压缩存储方式，以行序

9、为存储主序，若a(l,l) 为第一个元素，其存储地址为1, II每个元素占用1个地址空间，则a(& 5)元素的地址为A)13 B)33 0 18 D)40二、填空题1.从逻辑结构看，线性表是典型的线性结构 ，树是典型的树形结构 。2.棵含999个结点的完全二叉树的深度为10o 3.含n个顶点的无向连通图中至少含有条边。4.若对关键字序列(43, 02, 80, 48, 26, 57, 15, 73, 21, 24, 66)进行一趟増量 为3的希尔排序，则得到的结果为。5.数据的逻辑结构被分为集合线性结构、一树形结构和图形结构_四种。6.在一个稀疏矩阵中，每个非 零元素所对应的三元组包括

10、该元索的行号_、_列号_和_元素值_三项。7. 在一棵二叉树中，第5层上的结点数最多为o8. 以折半查找方法查找一个线性表时，此线性表必须是存储的表。9. 快速排序在平均情况下的时间复朵度为,在最坏情况下的时间复杂度为。10.假定一组记录的排序码为(46, 79, 56, 38, 40, 80, 36, 40, 75,66, 84, 24),对其进行归并排序的过程中，第三趟归并后的结果为： 。11对于一个具有n个结点和e条边的无向图，若采用邻接表表 示，则顶点表的大小为，所有边链表中边结点的总数为o 12.釆用邻接表存储的图的深度优先遍历算法类似于树的13.采用邻接表存储的图的广度优先遍历算法

11、类似于树的。 三、综合题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)=Key mod p,给定的关键码序列为19, 14, 23, 01, 68, 20, 84, 27, 55, 1

12、1,试画出用线性探测再散列法解决冲突时所构造的散 列表，并求出在等槪率的情况下查找成功时的平均查找长度ASL。4.画出在一个初始为空 的AVL树中依次插入关键字3, 1, 4, 6, 9, & 5, 7时AVL树的形态。5.写出串S的next函数 值。S= a b c a b a a next 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. 1

13、1 ,试画出相应的哈夫曼树，设计哈夫曼编码。8.设 s=求以下表达式的结果。(1) Replace(s, (2) Concat(SubString(s,6, 2), Concat(t, SubString (s,7,8)9.写出以下程序段的输出结果(队列中的元素类型QElemType为char)。(4分) void main( ) Queue Q;InitQueue(Q) :char x= 工， y二；EnQueue(Q,; EnQueue(Q,; EnQueue(Q, y) ; DeQueue(Q, x);EnQueue(Q, x);DeQueue(Q, x); EnQueue(Q, W ); while(!QueueEmpty(Q) )DeQueue(Q, y);printf(y);printf (x); 输出结果为10程序填空：对有序