《数据结构与算法分析考试说明与模拟试卷》由会员分享，可在线阅读，更多相关《数据结构与算法分析考试说明与模拟试卷（55页珍藏版）》请在金锄头文库上搜索。
1、考研大纲考查目标理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。能够选择合适的数据结构和方法进行问题求解。参考教材严蔚敏,数据结构(C语言版),北京,清华大学出版社,1997线性表线性表的定义和基本操作线性表的实现顺序存储结构链式存储结构线性表的应用栈、队列和数组栈和队列的基本概念栈和队列的顺序存储结构栈和队列的链式存储结构栈和队列的应用特殊矩阵的压缩存储树与二叉树树的概念二叉树二叉树的定义及其主要特征二叉树的顺序存储结构和链式存储结构二叉树的遍历线索二叉树的基本概念和构造二叉排序树平衡二叉树
2、树、森林树的存储结构森林与二叉树的转换树和森林的遍历树的应用等价类问题哈夫曼（Huffman）树和哈夫曼编码图图的概念图的存储及基本操作邻接矩阵法邻接表法图的遍历深度优先搜索广度优先搜索图的基本应用及其复杂度分析最小（代价）生成树最短路径拓扑排序关键路径查找查找的基本概念顺序查找法折半查找法B-树散列（Hash）表及其查找查找算法的分析及应用内部排序排序的基本概念插入排序直接插入排序折半插入排序气泡排序（bubble sort）简单选择排序希尔排序（shell sort）快速排序堆排序二路归并排序（merge sort）基数排序各种内部排序算法的比较内部排序算法的应用模拟试题（一）一、单项选择
3、题（每小题 2 分，共20分）（1）以下数据结构中哪一个是线性结构？（）A）有向图 B）队列 C）线索二叉树 D）B树（2）在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下（）语句序列。A）p=q; p-next=q; B）p-next=q; q-next=p;C）p-next=q-next; p=q; D）q-next=p-next; p-next=q;（3）（）不是队列的基本运算。A）在队列第i个元素之后插入一个元素B）从队头删除一个元素C）判断一个队列是否为空 D）读取队头元素的值（4）字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，
4、至多可以组成（）个不同的字符串。A）14 B）5 C）6 D）8（5）由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为（）。A）11 B）35 C）19 D）53以下6-8题基于下图：（6）该二叉树结点的前序遍历的序列为（）。A）E、G、F、A、C、D、B B）E、A、G、C、F、B、DC）E、A、C、B、D、G、F D）E、G、A、C、D、F、B（7）该二叉树结点的中序遍历的序列为（）。A）A、B、C、D、E、G、FB）E、A、G、C、F、B、DC）E、A、C、B、D、G、F D）B、D、C、A、F、G、E （8）该二叉树的按层遍历的序列为（）。A）E、G、F、A、C、D
5、、B B）E、A、C、B、D、G、FC）E、A、G、C、F、B、D D）E、G、A、C、D、F、B（9）下面关于图的存储的叙述中正确的是（）。A）用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B）用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关C）用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关D）用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关（10）设有关键码序列(q,g,m,z,a,n,p,x,h)，下面哪一个序列是从上述序列出发建堆的结果?（）A）a,g,h,m,n,p,q,x,z B）a,g,m,h,q,n
6、,p,x,z C）g,m,q,a,n,p,x,h,z D）h,g,m,p,a,n,q,x,z二、（每小题4分，共8分）已知一个65稀疏矩阵如下所示，试：（1）写出它的三元组线性表；（2）给出三元组线性表的顺序存储表示。三、（本题8分）求网的最小生成树有哪些算法？它们的时间复杂度分别下多少，各适用何种情况？四、（每小题4分，共8分）对于如下图所示的有向图若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，试写出：（1）从顶点v1出发进行深度优先搜索所得到的深度优先生成树；（2）从顶点v2出发进行广度优先搜索所得到的广度优先生成树。 五、（本题8分）已知一个图的顶
7、点集V和边集E分别为：V=1,2,3,4,5,6,7;E=,;若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，试给出得到的拓扑排序的序列。六、（本题8分）对于序列8,18,6,16,29,28，试写出堆顶元素最小的初始堆。七、（本题8分）一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来。试求出空格处的内容，并画出该二叉树。先序序列： B F ICEH G中序序列：D KFIA EJC 后序序列： K FBHJ G A八、（每小题2分，共8分）设有序列：w=23,24,27,80,28，试给出：（1）二叉排序树；（2）哈夫曼树；（3）平衡二叉
8、树；（4）对于增量d=2按降序执行一遍希尔排序的结果。九、（本题9分）有关键字序列7,23,6,9,17,19,21,22,5，Hash函数为H(key)=key % 5，采用链地址法处理冲突，试构造哈希表。十、（本题15分）假设二叉树中每个结点所含数据元素均为单字母，以二叉链表为存储结构，试编写算法按如下图所示的树状显示二叉树。模拟试题（一）参考答案一、单项选择题（1）B （2）D （3）A （4）B（5）B（6）C（7）A（8）C（9）B（10）B二、（每小题4分，共8分）（1） (1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7)（2）三元组线性表的顺序存储
9、表示如下所示：三、（本题8分）求网的最小生成树可使用Prim算法，时间复杂度为O(n2)，此算法适用于边较多的稠密图，也可使用Kruskal算法，时间复杂度为O(eloge)，此算法适用于边较少的稀疏图。四、（每小题4分，共8分）（1）DFS：v1 v2 v3 v4 v5 （2）BFS：v2 v3 v4 v5 v1 五、（本题8分）拓扑排序为： 4 3 6 5 7 2 1六、（本题8分）所构造的堆如下图所示：七、（本题8分）在先序序列空格中依次填ADKJ，中序中依次填BHG，后序中依次填DIEC。八、（每小题2分，共8分）（1）二叉排序树如下图所示：（2）哈夫曼树如下图所示：（3）平衡二叉树如
10、下图所示：（4）对于增量d=2按降序执行一遍希尔排序的结果：28,80,27,24,23九、（本题9分）哈希表如下图所示：十、（本题15分）从上图来看，二叉树的第一层显示在第一列，第二层显示在第二列，第三层显示在第三列；每行显示一个结点，从上至下是先显示右子树，再显示根，最后最左子树，也就是以先遍历右子树，最后遍历左子树的中序遍历次序显示各结点。C+语言版测试程序见exam110C+，具体算当如下：template void DisplayHelp(BinTreeNode *r, int level)/ 操作结果：按树状形式显示以r为根的二叉树，level为层次数，可设根结点的层次数为1if(
11、r != NULL)/ 空树不显式，只显式非空树DisplayHelp(r-rightChild, level + 1);/ 显示右子树cout endl;/ 显示新行for(int i = 0; i level - 1; i+)cout ;/ 确保在第level列显示结点cout data;/ 显示结点DisplayHelp(r-leftChild, level + 1);/ 显示左子树template void Display(const BinaryTree &bt)/ 操作结果：树状形式显示二叉树 DisplayHelp(bt.GetRoot(), 1);/ 树状显示以bt.GetRo
12、ot()为根的二叉树cout rchild,level+1);/显示右子树coutendl;/显示新行for(int i=0;ilevel-1;i+)cout ;/确保在第level列显示结点coutdata;/显示结点DisplayBTWithTreeShape(T-lchild,level+1);/显示左子树模拟试题（二）一、单项选择题（每小题 2 分，共20分）（1）设Huffman树的叶子结点数为m，则结点总数为（）。A）2m B）2m-1C）2m+1 D）m+1（2）若顺序存储的循环队列的QueueMaxSize=n，则该队列最多可存储（）个元素。A）n B）n-1 C）n+1 D）不确定（3）下述哪一条是顺序存储方式的优点？（）A）存储密度大 B）插入和删除运算方便 C）获取符合某种条件的元素方便 D）查找运算速度快（4）设有一个二维数组Amn，假设A00存放位置在600(10)，A33存放位置在678(10)，每个元素占一个空间，问A23(
