数据结构自测题及解答.doc

一、 概念题（每空0.5分，共28分）1树（及一切树形结构）是一种“_”结构。在树上，_结点没有直接前趋。对树上任一结点X来说，X是它的任一子树的根结点惟一的_。2由个结点所构成的二叉树有 种形态。3一棵深度为6的满二叉树有 个分支结点和 个叶子。4一棵具有个结点的完全二叉树，它的深度为 。5二叉树第i(i=1)层上至多有_个结点；深度为k(k=1)的二叉树至多有_个结点。6对任何二叉树，若度为2的节点数为n2，则叶子数n0=_。7满二叉树上各层的节点数已达到了二叉树可以容纳的_。满二叉树也是_二叉树，但反之不然。8设一棵完全二叉树有700个结点，则共有 个叶子结点。9.设一棵完全二叉树具有1000个结点，则此完全二叉树有 个叶子结点，有 个度为2的结点，有 个结点只有非空左子树，有 个结点只有非空右子树。10.一棵含有n个结点的k叉树，可能达到的最大深度为 ，最小深度为 。11.二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即按N L R次序），后序法（即按 次序）和中序法（也称对称序法，即按L N R次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是 。12.中序遍历的递归算法平均空间复杂度为 。13.二叉树通常有_存储结构和_存储结构两类存储结构。14.如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(1=in，则结点X无_且无_；否则，X的左孩子LCHILD(X)的编号为_。（3） 若2i+1n，则结点X无_；否则，X的右孩子RCHILD(X)的编号为_。15. 每个二叉链表的访问只能从_结点的指针，该指针具有标识二叉链表的作用。16.二叉链表中每个存储结点的每个指针域必须有一个值，这个值或者是_的指针，或者是_。17.具有n个结点的二叉树中,一共有_个指针域,其中只有_个用来指向结点的左右孩子，其余的_个指针域为NULL。18.二叉树有不同的链式存储结构，其中最常用的是_与_。19.若二叉树的一个叶子是某子树的中根遍历序列中的第一个结点，则它必是该子树的后根遍历序列中的_个结点。20.树与二叉树之间最主要的差别是：二叉树中各结点的子树要区分为_和_，即使在结点只有一棵子树的情况下，也要明确指出该子树是_还是_。21.树的结点数目至少为_，二叉树的结点数目至少为_。22.树的主要遍历方法有_、_、_等三种。23.由_转换成二叉树时，其根结点的右子树总是空的。24.哈夫曼（Huffman）树是带权路径长度_的树，通常权值较大的结点离根_。25.用5个权值3, 2, 4, 5, 1构造的哈夫曼（Huffman）树的带权路径长度是 。26. n个结点的线索二叉树中的线索数目为 。27.用数组1.n存放d堆，对于位于i的节点项，其父节点为 ；子节点为 。二、 选择题（每空1分，共15分）（ ）1 不含任何结点的空树 。（）是一棵树; （）是一棵二叉树; （）是一棵树也是一棵二叉树; （）既不是树也不是二叉树（ ）2二叉树是非线性数据结构，所以 。（）它不能用顺序存储结构存储; （）它不能用链式存储结构存储; （）顺序存储结构和链式存储结构都能存储; （）顺序存储结构和链式存储结构都不能使用 （ ）3. 具有n(n0)个结点的完全二叉树的深度为 。() log2(n) () log2(n) () log2(n) +1 () log2(n)+1（ ）4把一棵树转换为二叉树后，这棵二叉树的形态是 。（）唯一的 （）有多种（）有多种，但根结点都没有左孩子 （）有多种，但根结点都没有右孩子5. 树是结点的有限集合，它 A 根结点，记为T。其余的结点分成为m（m0）个 B 的集合T1，T2，Tm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1im）。一个结点的子结点个数为该结点的 C 。供选择的答案A： 有0个或1个 有0个或多个 有且只有1个 有1个或1个以上 B: 互不相交 允许相交 允许叶结点相交 允许树枝结点相交C： 权 维数 次数 序答案：A= B= C= 6. 二叉树 A 。在完全的二叉树中，若一个结点没有 B ，则它必定是叶结点。每棵树都能惟一地转换成与它对应的二叉树。由树转换成的二叉树里，一个结点N的左子女是N在原树里对应结点的 C ，而N的右子女是它在原树里对应结点的 D 。供选择的答案A： 是特殊的树 不是树的特殊形式 是两棵树的总称 有是只有二个根结点的树形结构 B: 左子结点 右子结点 左子结点或者没有右子结点 兄弟CD： 最左子结点 最右子结点 最邻近的右兄弟 最邻近的左兄弟 最左的兄弟 最右的兄弟答案：A= B= C= D 7. 一个有n个结点的树上有多少个分支 （ ） n个 n-1个 n+1个 不能确定8. 一个有n个叶子结点的哈夫曼树的节点总数为 （ ） 2n个 2n-1个 2n-2个 不能确定9. 对一个森林的遍历，下列说法错误的是 （ ）A一个森林的前序遍历序列，与其对应的二叉树的前序遍历序列是一致的。B一个森林的中序遍历序列，与其对应的二叉树的中序遍历序列是一致的C一般对一个森林的遍历，没有后根遍历法D一个森林的层次遍历序列，与其对应的二叉树的层次遍历序列是一致的10. 以下说法错误的是 ( ) A一般在哈夫曼树中，权值越大的叶子离根结点越近B哈夫曼树中没有度数为1的分支结点C若初始森林中共有n裸二叉树，最终求得的哈夫曼树共有2n-1个结点D 若初始森林中共有n裸二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫曼树三、 综合题（1-9每题3分，10-12每题10分,共57分）1给定二叉树的两种遍历序列，分别是：前序遍历序列：D，A，C，E，B，H，F，G，I； 中序遍历序列：D，C，B，E，H，A，G，I，F，2825 3340 60 08 54 55试画出二叉树B。2. 给定如图所示二叉树T，请画出与其对应的中序线索二叉树。3试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。4. 把如图所示的树转化成二叉树。5. 编写递归算法，计算二叉树中叶子结点的数目。6. 写出求二叉树深度的算法。 7. 编写递归算法，求二叉树中以元素值为x的结点为根的子树的深度。8假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。使用07的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。9. 画出一次一个地将10、12、1、14、6、5、8、15、3、9、7、4、11、13和2插入一个初始为空的最小堆的结果。10改写Binary heap的insert函数，在0号数组元素中存放插入项的副本。11.画出依序依次将关键字1到15插入初始为空的左堆的结果。12.Suppose you have a binary tree whose data fields are single characters. When the data fields of the nodes are output in inorder, the output is ABCDEFGHIJ, and when they are output in preorder, the output is ADBCJGFEHI. Draw the binary tree showing the data in each node and the pointers between nodes.参考答案一、概念题（每空0.5分，共28分）1、 分支层次、根、直接前趋2、 53、 31 324、 95、 2i-1 2 k-16、 n2+17、 最大值、完全8、 350 （n/2350）9、 500 499 1 010、 n 211、 L R N F E G H D C B12、 O(n)13、 顺序、链式14、 根、左孩子、右孩子、2i、右孩子、2i+115、 根16、 指向该结点的一个孩子、空指针NULL17、 2n、n-1、n+118、 二叉链表、三叉链表19、 第一20、 左子树、右子树、左子树、右子树21、 1、022、 先根遍历、后根遍历、层次遍历23、 树24、 最短、较近25、 3326、 n+127、 父节点；子节点、二、选择题（每空1分，共15分）1. C 2. C 3. C 4. A 5. A= B= C= 6. A= B= C= D= 7.B 8. B 9. D 10. D 三、综合题（1-9每题3分，10-12每题10分,共57分）1解：方法是：由前序先确定root，由中序可确定root的左、右子树。然后由其左子树的元素集合和右子树的集合对应前序遍历序列中的元素集合，可继续确定root的左右孩子。将他们分别作为新的root，不断递归，则所有元素都将被唯一确定，问题得解。 D A C FE GB H I2. 解：要遵循中序遍历的轨迹来画出每个前驱和后继。中序遍历序列：55 40 25 60 28 08 33 54282540555560330854NILNIL 2825 33 40 60 08 54 553答：DLR：A B D F J G K C E H I L MLDR: B F J D G K A C H E L I MLRD：J F K G D B H L M I E C A4. 答：注意全部兄弟之间都要连线（包括度为2的兄弟）,并注意原有连线结点一律归入左子树，新添连线结点一律归入右子树。 A B E C K F H D L G I M J5和6 解答略（参考教材）7. int Get_Sub_Depth(BinaryTree T,int x)/求二叉树中以值为x的结点为根的子树深度 if(T-data=x) coutGet_Depth(T)lchild) Get_Sub_Depth(T-lchild,x); if(T-rchild) Get_Sub_Depth(T-rchild,x); /在左右子树中继续寻找 /Get_Sub_Depth int Get_Depth(BinaryTree T)/求子树深度的递归算法 if(!T) return 0; else m=Get_Depth(T-lchild); n=Get_Depth(T-rchild); return (mn?m:n)+1; /Get_Depth8 . 解：方案1；哈夫曼编码先将概率放大100倍，以方便构造哈夫曼树。 w=7,19,2,6,32,3,21,10，按哈夫曼规则：构造哈夫曼树如下： 0 1 0 1 0 119 21 32 0 10 1 0 17 10 6 0 12 3 （100）（40） （60）19 21 32 （28）（17） （11） 7 10 6 （5） 2 3方案比较：字母编号对应编码出现频率111000.072000.193111100.02411100.065100.326111110.037010.21811010.10字母编号对应编码出现频率10000.0720010.1930100.0240110.0651000.3261010.0371100.2181110.10方案1的WPL2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61方案2的WPL3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3结论：哈夫曼编码优于等长二进制编码9. 答：10.void insert( const Comparable & x