下载文档原格式
杭州电子科技大学全国硕士研究生入学考试业务课考试大纲考试科目名称：数据结构与组成原理科目代码：（一）数据结构部分一、数据结构的一般概念1．掌握数据结构的基本概念和术语。
2．了解抽象数据类型的概念。
3．掌握算法的特性，算法的描述和算法的分析。
二、线性表1．理解线性表的逻辑结构。
2．掌握线性表的顺序存贮结构和链式存贮结构；掌握线性表基本操作的实现。
3．了解线性表的应用。
三、其他线性结构1．掌握栈的定义、栈的存贮结构及基本操作的实现。
2．理解用栈实现表达式的求值，递归过程及其实现。
3．掌握队列的定义、存贮结构及基本操作的实现4．理解串的逻辑定义及其基本操作；理解串的存贮结构。
5．理解数组的定义、数组的顺序存贮结构及矩阵的存贮压缩。
6．理解广义表的定义及存贮结构。
四、树和二叉树1．掌握树型结构的定义。
2．掌握二叉树的定义、性质及各种存贮结构。
3．掌握遍历二叉树、线索二叉树及其他基本操作。
4．掌握树、森林与二叉树的相互转换；理解树的遍历；掌握哈夫曼树及其应用。
五、图1．掌握图的定义和术语。
2．掌握图的存贮结构；理解图的基本操作。
3．掌握图的遍历算法；了解利用图的遍历解决图的应用问题。
4．理解图的有关应用：求最小生成树、求最短路径、拓扑排序及关键路径等算法的基本思想。
六、查找1．掌握静态查找表。
2．掌握二叉排序树和平衡二叉树。
3．理解B－树；了解B＋树。
4．掌握哈希表。
5．掌握各种查找方法的时间性能分析。
七、内部排序1．掌握直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序；理解基数排序。
2．学会各种内部排序方法的比较（时间复杂度、空间复杂度、稳定性）。
参考书目：1. 《数据结构》（C语言版），严蔚敏吴伟民编著，清华大学出版社，2006.32. 《数据结构实用教程》（C++版），万健主编，电子工业出版社，2011.1（二）计算机组成原理部分一、计算机系统概述1．计算机系统的发展与分类。
姓名：报考专业：准考证号码：密封线内不要写题2019年全国硕士研究生招生考试初试自命题试题 科目名称：数据结构（C 语言版）（□√A 卷□B 卷）科目代码：856 考试时间：3小时 满分150分 可使用的常用工具：□√无 □计算器 □直尺 □圆规（请在使用工具前打√） 注意：所有答题内容必须写在答题纸上，写在试题或草稿纸上的一律无效；考完后试题随答题纸交回。
一、选择题(共15小题，每小题2分，共30分) 1. 计算算法的时间复杂度是属于一种（ ）的方法。
A ）事前统计 B ）事前分析估算 C ）事后统计 D ）事后分析估算 2. 数据的逻辑结构可以分为（ ）。
A ）静态结构和动态结构 B ）物理结构和存储结构 C ）线性结构和非线性结构 D ）虚拟结构和抽象结构 3. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）。
A ）必须是连续的 B ）部分地址必须是连续的 C ）一定是不连续的 D ）连续不连续都可以 4. 线性表既可以用带头结点的链表表示，也可以用不带头结点的链表表示，前者最主要的好处是（ ）。
A ）使空表和非空表的处理统一 B ）可以加快对表的遍历 C ）节省存储空间 D ）可以提高存取表元素的速度 5. 若用一个大小为6的数组来实现循环队列，且当前rear 和front 的值分别为0和3。
当从队列中删除一个元素，再加入两个元素后， rear 和front 的值分别为（ ）。
A ）1和5 B ）2和4 C ）4和2 D ）5和1 6. 对二叉树T 中的某个结点x ，它在先根序列、中根序列、后根序列中的序号分别为pre （x ），in （x ）、post （x ），a 和b 是T 中的任意两个结点，下列选项一定错误的是（ ）。
A ）a 是b 的后代且pre （a ）<pre （b ） B ）a 是b 的祖先且post （a ）>post （b ） C ）a 是b 的后代且in （a ）<in （b ） D ）a 在b 的左边且in （a ）<in （b ） 7. 若二叉树的前序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。
2022年武汉科技大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。
A.NB.2N-1C.2ND.N-12、若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。
A.快速排序B.堆排序C.归并排序D.直接插入排序3、线性表的顺序存储结构是一种（）。
A.随机存取的存储结构B.顺序存取的存储结构C.索引存取的存储结构D.Hash存取的存储结构4、在下列表述中，正确的是（）A.含有一个或多个空格字符的串称为空格串B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l5、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（）。
A.（rear+1）MOD n=frontB.rear=frontC.rear+1=frontD.（rear-1）MOD n=front6、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（）。
7、下列关于无向连通图特性的叙述中，正确的是（）。
Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ8、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。
A.107B.108C.214D.2159、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。
A.其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子C.其中只有一个叶结点D.其中度为2的结点最多为一个10、对n个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（）。
A.每次分区后，先处理较短的部分B.每次分区后，先处理较长的部分C.与算法每次分区后的处理顺序无关D.以上三者都不对二、填空题11、分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是______算法，最费时间的是______算法。
数据结构(C 语言版)考研真题(A 卷)辑整理：尊敬的读者朋友们：这里是精品文档编辑中心，本文档内的同事精心编辑整理后发布的，发布之前我们对文中内容进行仔细校对，但是难免会有疏漏的地方，但是任然希望（数据结构(C 语言版)考研真题(A卷)）的内容能够给您的工作和学习带来便利。
同时收到您的建议和反馈，这将是我们进步的源泉，前进的动力。
本文可编辑可修改，如果觉得对您有帮助请收藏以便随时查阅，最后祝您生活愉快业绩进步，以下为数据结构(C 语言版)考研真二O 一四年招收硕士研究生入学考试试题 考试科目代码及科目名称： 856 数据结构(C 语言版） 答题内容写在答题纸上,写在试卷或草稿纸上一律无效考完后试题随答题纸交回。
考试时间3小时,总分值 150 分。
题(A卷)的全部内容。
密封线内不要写题 一、选择题(10小题，每题2分，共20分）1。
算法分析的主要内容是（ ）。
A ）正确性 B)可读性和稳定性 C ）简单性 D ）空间复杂性和时间复杂性2。
线性表若采用链式存储结构时，要求内存中可用存储单元的地址( ）.A ）必须是连续的B ）部分地址必须是连续的C ）一定是不连续的D ）连续或不连续都可以3. 设有6个元素按1、2、3、4、5、6的顺序进栈，下列不合法的出栈序列是（ )。
A ）234165B ）324651 C)431256 D ）5463214. 设有二维数组A ［1..12,1。
.10]，其每个元素占4个字节，数据按行优先顺序存储,第一个元素的存储地址为100，那么元素A[5，5]的存储地址为（ ）.A ）76 B)176 C ）276 D ）3765. 已知一棵二叉树的先序序列为ABDGCFK ，中序序列为DGBAFCK ，则后序序列为（ ）。
A ）ACFKDBG B)GDBFKCA C ）KCFAGDB D ）ABCDFKG6。
在二叉树结点的先序,中序和后序序列中,所有叶子结点的先后顺序( ）。
姓名
：
报
考
专
业
：
准考
证号码
：
密
封
线
内
不
要
写
题
2019年全国硕士研究生招生考试初试自命题试题 科目名称：数据结构（C 语言版）（□√A 卷□B 卷）科目代码：856 考试时间：3小时 满分150分 可使用的常用工具：□√无 □计算器 □直尺 □圆规（请在使用工具前打√） 注意：所有答题内容必须写在答题纸上，写在试题或草稿纸上的一律无效；考完后试题随答题纸交回。
一、选择题(共15小题，每小题2分，共30分) 1. 计算算法的时间复杂度是属于一种（ ）的方法。
A ）事前统计 B ）事前分析估算 C ）事后统计 D ）事后分析估算 2. 数据的逻辑结构可以分为（ ）。
A ）静态结构和动态结构 B ）物理结构和存储结构 C ）线性结构和非线性结构 D ）虚拟结构和抽象结构 3. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）。
A ）必须是连续的 B ）部分地址必须是连续的 C ）一定是不连续的 D ）连续不连续都可以 4. 线性表既可以用带头结点的链表表示，也可以用不带头结点的链表表示，前者最主要的好处是（ ）。
A ）使空表和非空表的处理统一 B ）可以加快对表的遍历 C ）节省存储空间 D ）可以提高存取表元素的速度 5. 若用一个大小为6的数组来实现循环队列，且当前rear 和front 的值分别为0和3。
当从队列中删除一个元素，再加入两个元素后， rear 和front 的值分别为（ ）。
A ）1和5 B ）2和4 C ）4和2 D ）5和1 6. 对二叉树T 中的某个结点x ，它在先根序列、中根序列、后根序列中的序号分别为pre （x ），in （x ）、post （x ），a 和b 是T 中的任意两个结点，下列选项一定错误的是（ ）。
A ）a 是b 的后代且pre （a ）<pre （b ） B ）a 是b 的祖先且post （a ）>post （b ） C ）a 是b 的后代且in （a ）<in （b ） D ）a 在b 的左边且in （a ）<in （b ） 7. 若二叉树的前序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。
A ）空或只有一个结点 B ）任一结点无左子树
C ）任一结点无右子树
D ）高度等于其结点数
8. 下面几个符号串编码集合中，不是前缀编码的是（ ）。
A ）{0,10,110,1111}
B ）{11,10,001,101,0001}
C ）{00,010,0110,1000}
D ）{b,c,aa,ac,aba,abb,abc}
9. 一个n 个顶点的连通无向图,其边数至少为（ ）。
（2）给出基于该AOV网邻接表的从顶点V1出发的DFS序列。
（3）给出基于该AOV网邻接表的从顶点V1出发的BFS序列。
（4）写出对该AOV网按照上述邻接表进行拓扑排序得到的拓扑序列。
3. 根据下列二叉树，要求：
（1）写出其先序遍历序列、中序遍历序列和后序遍历序列。
（2）顺序存储该二叉树，画出其存储示意图。
4. 如果一颗非空k叉树T（k≥2）中每个非叶子结点都有k个孩子。
请回答下列问题并
给出推导过程。
（1）若T有m个非叶子结点，则T的叶子节点有多少个？
（2）若T的高度为h，则T的结点数最多是多少个？最少是多少个？
5. 散列表长度是13，散列函数H(K)=k % 13，解决冲突用线性探测再散列法。
给定的关
键字序列为{19,14,23,1,68,20,84,27,55,11,10,79}，要求：
（1）画出哈希表。
（2）求出等概率下查找成功的平均查找长度。
（3）求出等概率下查找失败的平均查找长度。
五、算法设计题(共4小题，每小题10分，共40分)
1. 用带头结点的双向循环链表（结点结构为（Left，Data，Right））表示的线性表为L=
（a1,a2, …an）。
试设计如下算法Fun实现将L改造成：L=（a1,a3,…an,…a4,a2）。
void Fun(DbLinkList &L);
2. 若表达式以字符形式已存入数组s中，‘#’为表达式的结束符，试设计如下算法Match
判断表达式中括号（‘([{}])’）是否配对，如果配对，则返回1，否则返回0。
int Match(char *s);
3. 树采用孩子兄弟链表作为存储结构（结点结构CSTree为（firstchild，data，
nextsibling）），试设计如下非递归算法Leaf计算树的叶子节点数。
int Leaf(CSTree *T); //函数返回值就是树的叶子节点数
4. 已知无向图采用邻接表存储方式，试设计如下算法DeletEdge删除图中(i,j)边。
void DeletEdge(AdjList g,int i,int j);。
