第页共NUMPAGES3页模拟题一．单项选择题1.如图所示的4棵二叉树中，哪一个是平衡二叉树A.B.C.D.2.若一个算法的语句频度之和为T(n)=3n+nlog2n+n2,则算法的时间复杂度为。A.nlog2n+n2B.nC.n2D.nlog2n3.插入和删除操作只能在同一端进行的线性表，成为。A.队列B.循环队列C.栈D.循环栈4.一棵树Tr转换成相应的二叉树Bt，那么对Tr的后序遍历是对Bt的。A．先序遍历B．中序遍历C．后序遍历D．无法确定5.判定一个循环队列Q（最多元素为m0）为空的条件是。A．Q.front==Q.RearB.Q.front==(Q.rear+1)%m0C．Q.front!=Q.rearD.Q.front!=(Q.rear+1)%m06.广义表(（a,b,(),c),(d,(e))，（）)的长度是。A.5B.4C.3D.27.在一个无向图中，所有顶点的度数之和，是其所有边数之和的倍。A．1/2B．1C．2D．48.tail（head（（a，b），c，（c，d）））的结果是。A．bB．（b）C．（a，b）D．（c，d）9.深度为k的满二叉树有个分支结点。A.2k-1B.2k-1-2C.2k+1D.2k-1+110.一棵有n个结点的树，在把它转换成对应的二叉树之后，该二叉树根结点的左子树上共有个结点。A．n-2B．n-1C．n+1D．n+211.n个顶点的带权无向连通图的最小生成树包含条边。A.n-1B.nC.n/2D.n+112.如图，若从顶点a出发按广度优先法进行遍历，可能得到的一种顶点序列是。A．abcedfB．abcefdC．aebcfdD．acfdeb13.无向图的邻接矩阵是矩阵。A.对称B.上三角C.下三角D.稀疏14.一个无向连通网图的最小生成树。A．可能不存在B．只有一棵C．一定有多棵D．有一棵或多棵15.在下面给出的各种排序算法中，只有是稳定排序算法。A．堆排序B．快速排序C．直接选择排序D．冒泡排序二、填空题（每题1分，共10分）1.深度为6的二叉树，最多可以有个结点。2.串中所含字符个数称为该串的______。3.广义表的深度是______。4.设数组A[0..9,0..6],已知a[2,4]的地址为2000,每个元素占2个存储单元,若以行序为主序顺序存储,则数组的首地址为______。5.在一颗二叉树中，度为0的结点个数为n0，度为2的结点个数为n2，则有n0=______。在一棵完全二叉树的共5层，第5层上有4个叶结点，棵完全二叉树有______个结点。7.在双链表中，每个结点有两个指针域，一个指向，另一个指向。8.各结点左、右子树深度之差的绝对值至多为______的二叉树称为平衡二叉树。9.数组A[0:1,0:1,0:1]共有___________元素。10.在查找过程中有插入元素或删除元素操作的，称为______查找。三、判断题（请在题号前的括号里将正确的打“√”，错误的请打“×”，每题2分，共10分）（）1.数据的逻辑结构和数据的存储结构是相同的。（）2.顺序存储方式的优点是插入、删除效率高。（）3.线性表中的每个结点最多只有一个直接前驱和一个直接后继。（）4．一个广义表的表尾总是一个广义表。（）5．若某二叉树中每一结点都没有右子树，则它的中序和后序遍历次序相同。四、画图题（每题6分，共30分，要求给出解题的主要步骤）1.试将树T转换为二叉树。2.试画出网的最小生成树（请注明所使用的方法名称）。3.设有数据结构（D,R），其中D={a,b,c,d,e,f,g,h}R={r}r={<d,b>,<d,g>,<d,a>,<b,c>,<g,e>,<g,h>,<e,f>}试画出其逻辑结构图，并说明它属于何种结构4..字符集{A、B、C、D、E、F}，概率分别为{0.06、0.14、0.18、0.21、0.16、0.25}画出相应的哈夫曼树；分别列出字符A、B、C、D、E、F的哈夫曼码；计算该树的带权路径长度WPL。5.元素1、2、3,入栈顺序1、2、3，出栈顺序2、1、3,试画出空的顺序栈和每插入或弹出一个元素之后的顺序栈示意图（顺序栈大小为4）。五、算法题（每小题10分，共20分）1.写出折半查找的算2.写出冒泡排序算法