数据结构与算法C++版_模拟试题

模拟试题（一）一、单项选择题（每小题2分，共20分）（1）以下数据结构中哪一个是线性结构？（）A）有向图B）队列C）线索二叉树D）B树（2）在一个单链表la中，若要在当前由指针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依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成（）个不同的字符串。A）14B）5C）6D）8（5）由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为（）。A）11B）35C）19D）53以下6-8题基于下图：（6）该二叉树结点的前序遍历的序列为（）。A）E、G、F、A、C、D、BB）E、A、G、C、F、B、DC）E、A、C、B、D、G、FD）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、FD）B、D、C、A、F、G、E（8）该二叉树的按层遍历的序列为（）。A）E、G、F、A、C、D、BB）E、A、C、B、D、G、FC）E、A、G、C、F、B、DD）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,zB）a,g,m,h,q,n,p,x,zC）g,m,q,a,n,p,x,h,zD）h,g,m,p,a,n,q,x,z二、（每小题4分，共8分）已知一个65稀疏矩阵如下所示，试：007000000520000000100000010000（1）写出它的三元组线性表；（2）给出三元组线性表的顺序存储表示。三、（本题8分）求网的最小生成树有哪些算法？它们的时间复杂度分别下多少，各适用何种情况？四、（每小题4分，共8分）对于如下图所示的有向图若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，试写出：（1）从顶点v1出发进行深度优先搜索所得到的深度优先生成树；（2）从顶点v2出发进行广度优先搜索所得到的广度优先生成树。五、（本题8分）已知一个图的顶点集V和边集E分别为：V={1,2,3,4,5,6,7};E={2,1,3,2,3,6,4,3,4,5,4,6,5,1,5,7,6,1,6,2,6,5};试画出此图的图形，给出所有可能的拓扑排序序列。六、（本题8分）对于序列{8,18,6,16,29,28}，试写出堆顶元素最小的初始堆。七、（本题8分）一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来。试求出空格处的内容，并画出该二叉树。先序序列：BFICEHG中序序列：DKFIAEJC后序序列：KFBHJGA八、（每小题2分，共8分）设有序列：w={23,24,27,80,28}，试给出：（1）二叉排序树；（2）哈夫曼树；（3）平衡二叉树；（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）三元组线性表的顺序存储表示如下所示：736515254123151556三、（本题8分）求网的最小生成树可使用Prim算法，时间复杂度为O(n2)，此算法适用于边较多的稠密图，也可使用Kruskal算法，时间复杂度为O(eloge)，此算法适用于边较少的稀疏图。四、（每小题4分，共8分）（1）DFS：v1v2v3v4v5（2）BFS：v2v3v4v5v1五、（本题8分）图形表示如下图所示：1542367拓扑排序为：4362517，4362571，4365721，4365217，4365271六、（本题8分）所构造的堆如下图所示：七、（本题8分）在先序序列空格中依次填ADKJ，中序中依次填BHG，后序中依次填DIEC。二叉树如下：ABDFCEGKIHJ八、（每小题2分，共8分）（1）二叉排序树如下图所示：（2）哈夫曼树如下图所示：（3）平衡二叉树如下图所示：（4）对于增量d=2按降序执行一遍希尔排序的结果：28,80,27,24,23九、（本题9分）哈希表如下图所示：5∧6723∧921∧1722∧19∧01234十、（本题15分）从上图来看，二叉树的第一层显示在第一列，第二层显示在第二列，第三层显示在第三列；每行显示一个结点，从上至下是先显示右子树，再显示根，最后最左子树，也就是以先遍历右子树，最后遍历左子树的中序遍历次序显示各结点。具体算法实现如下：//文件路径名:exam1\alg.htemplateclassElemTypevoidDisplayHelp(BinTreeNodeElemType*r,intlevel)//操作结果：按树状形式显示以r为根的二叉树，level为层次数，可设根结点的层次数为1{if(r!=NULL){//空树不显式，只显式非空树DisplayHelpElemType(r-rightChild,level+1);//显示右子树coutendl;//显示新行for(inti=0;ilevel-1;i++)cout;//确保在第level列显示结点coutr-data;//显示结点DisplayHelpElemType(r-leftChild,level+1);//显示左子树}}templateclassElemTypevoidDisplay(constBinaryTreeElemType&bt)//操作结果：树状形式显示二叉树{DisplayHelpElemType(bt.GetRoot(),1);//树状显示以bt.GetRoot()为根的二叉树coutendl;//换行}模拟试题（二）一、单项选择题（每小题2分，共20分）（1）设Huffman树的叶子结点数为m，则结点总数为（）。A）2mB）2m-1C）2m+1D）m+1（2）栈应用的典型事例是（）。A）排队B）查找C）归并D）用“算符优先法”进行表达式求值（3）下述哪一条是顺序存储方式的优点？（）A）存储密度大B）插入和删除运算方便C）获取符合某种条件的元素方便D）查找运算速度快（4）对n(n=2)个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是（）A）该树一定是一棵完全二叉树B）树中一定没有度为1的结点C）树中两个权值最小的结点一定是兄弟结点D）树中任一非叶结点的权值一定不小于下一任一结点的权值（5）下列关于二叉树遍历的叙述中，正确的是（）。A）若一个叶子是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点B）若一个结点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点C）若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点D）若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点（6）k层二叉树的结点总数最多为（）。A）2k-1B）2k+1C）2k-1D）2k-1（7）对线性表进行二分法查找，其前提条件是（）。A）线性表以链接方式存储，并且按关键码值排好序B）线性表以顺序方式存储，并且按关键码值的检索频率排好序C）线性表以顺序方式存储，并且按关键码值排好序D）线性表以链接方式存储，并且按关键码值的检索频率排好序（8）对n个记录进行堆排序，所需要的辅助存储空间为（）。A）O(1og2n)B）O(n)C）O(1)D）O(n2)（9）对于线性表（7，34，77，25，64，49，20，14）进行散列存储时，采用链地址法处理冲突，若选用H(K)=K%7作为散列函数，则散列地址为0的元素有（）个。A）1B）2C）3D）4（10）下列关于数据结构的叙述中，正确的是（）。A）数组是不同类型值的集合B）递归算法的程序结构比迭代算法的程序结构更为精炼C）树是一种线性结构D）用一维数组存储一棵完全二叉树是有效的存储方法二、（本题8分）假定一棵二叉树广义表表示为a(b(c),d(e,f))，分别写出对它进行先序、中序、后序、按层遍历的结果。三、（每小题4分，共8分）已知一个无向图的顶点集为{a,b,c,d,e}，其邻接矩阵如下所示：1011001101000111001001001（1）画出该图的图形；（2）根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。四、（本题8分）树有哪些遍历方法？它们分别对应于把树转变为二叉树的哪些遍历方法？五、（本题8分）如下图所示，设输入元素为1、2、3、P和A，输入次序为123PA，元素经过栈后到达输出序列，当所有元素均到达输出序列后，有哪些序列可以作为高级语言的变量名？输出次序输入次序123PA六、（本题8分）试列出如下图中全部可能的拓扑排序序列。123456七、（本题8分）已知哈希表地址空间为0..8，哈希函数为H(key)=key%7，采用线性探测再散列处理冲突，将数据序列{100,20,21,35,3,78,99,45}依次存入此哈希表中，列出插入时的比较次数，并求出在等概率下的平均查找长度。八、（本题8分）设有一个输入数据的序列是{46,25,78,62,12,80},试画出从空树起，逐个输入各个数据而生成的二叉搜索树。九、（本题9分）试画出表达式(a+b/c)*(d-e*f)的二叉树表示，并写出此表达式的波兰式表示，中缀表示及逆波兰式表示。十、（本题15分）以二叉链表作存储结构，试编写计算二叉树中叶子结点数目的递归算法。模拟试题（二）参考答案一、单项选择题（每小题2分，共20分）（1）B（2）D（3）A（4）A（5）A（6）A（7）C（8）C（9）D（10）D二、（本题8分）先序：a,b,c,d,e,f中序：c,b,a,e,d,f后序：c,b,e,f,d,a按层：a,b,d,c,e,f三、（每小题4分，共8分）【解答】（1）该图的图形如下图所示：（2）深度优先遍历序列为：abdce；广度优先遍历序列为：abedc。四、（本题8分）树的遍历方法有先根序遍历和后根序遍历，它们分别对应于把树转变为二叉树后的先序遍历与中序遍历方法。五、（本题8分）高级语言变量名是以字母开头，字母与数字的组合。由于必须以字母开头，有两种可能：（1）P为第一个输出字符的情形，那么必然要求123已经先后入栈，这样可得到以P开头的、并且123按逆序排列的（即321）、同时A位于P后任一位置的变量名序列：PA321，P3A21，P32A1，P32lA（2）A为第一个输出字符的情形，这时要求123P已经先后入栈，只有一种情