南昌大学数据结构考研真题(南昌大学数据结构期末试卷)

导语：南昌大学考研，数据结构的重点内容，考研常考类型，整理的很详细

第一章 绪论

1.数据结构的逻辑结构，哪几种是线性结构，哪几种是非线性结构；

2.数据结构的存储结构；

3.什么是数据结构？

4.数据结构上定义的操作；

5.估算算法的时间复杂度，什么是算法及其五个特征。

第二章 线性表

1.顺序存储结构线性表的修改，插入，删除，查找，排序及其时间复杂度；

2.单链表的修改，插入，删除，查找，排序及其时间复杂度；（循环，带头节点链表和不带头节点链表）；

3.双向链表的修改，插入，删除，查找，排序及其时间复杂度；（循环，带头节点链表和不带头节点链表）；

4.系数矩阵的相关知识点。（如三元组、十字链表等等）；

小结：顺表表和链表的算法，如合并，逆置，拆开这些都是重点。

栈和队列

第三章 栈的定义及操作；

1.栈的顺序和链式和存储结构，知道这两种结构下实现栈的操作；

2.栈的应用（如数值表达式的求解，括号的配对等的原理）；（去年考了利用栈8进制变10进制）

3.队列的定义及操作（链队列，顺序队列）；

循环队列，队空的条件，队满的条件及相应概念和操作

补充1：链队列空的条件是首尾指针相等，而循环队列满的条件的判定，则有队尾加1等于队头和设标记等方法。

补充2：什么叫假溢出？在一个循环队列中，若约定队首指针指向队首元素的前一个位置，那么从循环队列中删除一个元素时，其操作是先移动队首位置，后取元素。线性表、栈、队的同异点？

第四章 树和二叉树

1.树的基本定义；

2.二叉树的性质，存储结构；

3.二叉树的几种遍历（DLR,LDR,LRD)；

4.树的存储结构，树、森林的遍历及和二叉树的相互转换；

5.二叉树的应用（哈夫曼树和哈夫曼编码）；

6.完全二叉树的性质；

7.线索二叉树，二叉排序树，平衡二叉树；

有时间可以把B树和B+树看一下。

小结：树的一些算法很重要，比如判定一个二叉树是否完全，二叉树的高度，二叉树的宽度等等。去年考了求二叉树的宽度。

第五章 图

1.有关图的基本概念问题（图的定义和特点，无向图，有向图，入读，出度，完全图，生成子图，路径长度，回路，（强）连通图，（强）连通分量等）；

2.图的几种存储形式；

3.图的两种遍历算法（建议把这两个算法背下来）；

4.生成树，最小生成树的概念以及最小生成5.树的构造，PRIM算法和KRUSKAL算法；

6.拓扑排序（有两种方法，建议把算法背下来);

7.关键路径，最短路径（注意区分关键路径和最短路径）。

第六章 查找

顺序查找，折半查找（二分查找），分块查找（索引顺序查找），基于哈希表的查找算法（应掌握哈希表的用法），把这些定义和这几种方法的区别弄熟透，特别是哈希查找。一般来说查找的算法和顺序表，链表的算法相似。最好能够把这些算法背下来，做到胜券在握。

第七章 排序

弄清楚插入、（冒泡）选择、希尔、归并、快速等五种排序方法的概念，算法和它们之间的区别，背几个所相应的算法，一定要理解这些方法的算法，很重要的，最好背下来。基数排序和堆排序也很重要，前年考了快速排序，去年考了堆排序。

免责声明:本站部份内容由优秀作者和原创用户编辑投稿，本站仅提供存储服务，不拥有所有权,不承担法律责任。若涉嫌侵权/违法的，请反馈，一经查实立刻删除内容。本文内容由快快网络小思创作整理编辑！