数据结构模拟题1

数据结构模拟题1数据结构模拟题1数据结构模拟题1数据结构模拟题1编制仅供参考审核批准生效日期地址：电话：传真:邮编:模拟题一．单项选择题1.如图所示的4棵二叉树中，哪一个是平衡二叉树A.B.C.D.2.若一个算法的语句频度之和为T(n)=3n+nlog2n+n2,则算法的时间复杂度为。A.nlog2n+n2D.nlog2n3.插入和删除操作只能在同一端进行的线性表，成为。A.队列B.循环队列C.栈D.循环栈4.一棵树Tr转换成相应的二叉树Bt，那么对Tr的后序遍历是对Bt的。 A．先序遍历 B．中序遍历 C．后序遍历 D．无法确定5.判定一个循环队列Q（最多元素为m0）为空的条件是。A．==Q.RearB.==(+1)%m0C．!=D.!=(Q.rear+1)%m06.广义表(（a,b,(),c),(d,(e))，（）)的长度是。.47.在一个无向图中，所有顶点的度数之和，是其所有边数之和的倍。 A．1/2 B．1 C．2 D．48.tail（head（（a，b），c，（c，d）））的结果是。 A．bB．（b）C．（a，b）D．（c，d）9.深度为k的满二叉树有个分支结点。-2C+110.一棵有n个结点的树，在把它转换成对应的二叉树之后，该二叉树根结点的左子树上共有个结点。 A．n-2 B．n-1 C．n+1 11.n个顶点的带权无向连通图的最小生成树包含条边。2+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}，概率分别为{、、、、、}画出相应的哈夫曼树；分别列出字符A、B、C、D、E、F的哈夫曼码；计算