数据结构模拟题1.doc

《数据结构模拟题1.doc》由会员分享，可在线阅读，更多相关《数据结构模拟题1.doc（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流数据结构模拟题1.精品文档.模拟题一单项选择题1. 如图所示的4棵二叉树中，哪一个是平衡二叉树A. B. C. D. 2. 若一个算法的语句频度之和为T(n)=3n+ nlog2n + n2,则算法的时间复杂度为 。 A. nlog2n + n2 B.n C.n2 D.nlog2n3. 插入和删除操作只能在同一端进行的线性表，成为 。 A.队列 B.循环队列 C.栈 D.循环栈4. 一棵树Tr转换成相应的二叉树Bt，那么对Tr的后序遍历是对Bt的 。A先序遍历B中序遍历C后序遍历D无法确定5. 判定一个循环队列Q（最多元素为m0）为空的条件是

2、 。AQ.front = =Q. Rear B. Q.front= =( Q.rear + 1 ) % m0CQ.front != Q.rear D. Q.front != ( Q . rear +1 ) % m06. 广义表(（a,b,( ),c),(d,(e)，（）)的长度是 。A.5 B.4 C.3 D.27. 在一个无向图中，所有顶点的度数之和，是其所有边数之和的 倍。A1/2B1C2D48. tail（head（a，b），c，（c，d）的结果是 。Ab B（b） C（a，b） D（c，d）9. 深度为k的满二叉树有 个分支结点。 A.2k-1 B.2k-1-2 C.2k+1 D.2k

3、-1+110.一棵有n个结点的树，在把它转换成对应的二叉树之后，该二叉树根结点的左子树上共有 个结点。An-2 Bn-1 Cn+1 Dn+211. n个顶点的带权无向连通图的最小生成树包含 条边。A.n-1 B.n C.n/2 D.n+112. 如图，若从顶点a出发按广度优先法进行遍历，可能得到的一种顶点序列是 。 Aabcedf Babcefd Caebcfd Dacfdeb13. 无向图的邻接矩阵是 矩阵。 A.对称 B.上三角 C.下三角 D.稀疏14.一个无向连通网图的最小生成树 。A可能不存在B只有一棵 C一定有多棵 D有一棵或多棵15. 在下面给出的各种排序算法中，只有 是稳定排序

4、算法。A堆排序 B快速排序 C直接选择排序 D冒泡排序二、填空题（每题1分，共10分）1. 深度为6的二叉树，最多可以有 个结点。2. 串中所含字符个数称为该串的_ _。3. 广义表的深度是_ _。4. 设数组A0.9,0.6,已知a2,4的地址为2000,每个元素占2个存储单元,若以行序为主序顺序存储,则数组的首地址为_ _。5. 在一颗二叉树中，度为0的结点个数为n0，度为2的结点个数为n2，则有n0=_ _。6. 在一棵完全二叉树的共5层，第5层上有4个叶结点，棵完全二叉树有_ _ 个结点。7. 在双链表中，每个结点有两个指针域，一个指向 ，另一个指向 。8. 各结点左、右子树深度之差的

5、绝对值至多为_ _的二叉树称为平衡二叉树。 9. 数组A0:1,0:1,0:1共有_ _元素。10. 在查找过程中有插入元素或删除元素操作的，称为_ _查找。三、判断题（请在题号前的括号里将正确的打“”，错误的请打“”，每题2分，共10分）（ ）1.数据的逻辑结构和数据的存储结构是相同的。（ ）2.顺序存储方式的优点是插入、删除效率高。（ ）3.线性表中的每个结点最多只有一个直接前驱和一个直接后继。（ ）4一个广义表的表尾总是一个广义表。（ ）5若某二叉树中每一结点都没有右子树，则它的中序和后序遍历次序相同。四、画图题（每题6分，共30分，要求给出解题的主要步骤）1.试将树T转换为二叉树。2.

6、试画出网的最小生成树（请注明所使用的方法名称）。3. 设有数据结构（D,R），其中 D=a,b,c,d,e,f,g,h R=r r=,试画出其逻辑结构图，并说明它属于何种结构4.字符集 A、B、C、D、E、F，概率分别为0.06、0.14、0.18、0.21、0.16、0.25 (1) 画出相应的哈夫曼树；(2) 分别列出字符A、B、C、D、E、F 的哈夫曼码；(3) 计算该树的带权路径长度WPL。5.元素1、2、3, 入栈顺序1、2、3，出栈顺序2、1、3,试画出空的顺序栈和每插入或弹出一个元素之后的顺序栈示意图（顺序栈大小为4）。 五、算法题（每小题10分，共20分）1.写出折半查找的算2.写出冒泡排序算法