《2022年数据结构课后习题汇编 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构课后习题汇编 .pdf（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、一选择题1.设高度为 h 的二叉树只有为 0 和 2 的结点，则此类二叉树的结点数至少有（）个，至多有几个（）A.2h B.2h-1 C.2h+1 D.2h-1E.2h-1 F.2h+1 2.高度为 h 的完全二叉树有（）个结点，至多有（）个结点。A.2hB. 2h-1 C. 2h+1 D. 2h-1 3.具有 n 个结点的满二叉树有（）个叶结点。A.n/2 B.(n-1)/2 C.(n+1)/2 D.n/2+1 4.一棵具有 n 个叶节点的哈夫曼树，共有（）个结点。A.2n B. 2n-1 C.2n+1 D.2n-15.一棵具有 25 个结点的完全二叉树最多有（）个结点。A.48 B.49
2、C.50 D.51 6.已知二叉树的前序遍历序列为ABCDEF ，中序遍历序列为CBAEDF ，则后序遍历序列是（）。A.CBEFDA B.FEDCBA C.CBEDFA D.不定7.已知二叉树的中序遍历序列是debac,后序遍历序列是 dabec,则前序遍历序列是（） 。A.acbed B.decab C.deabc D.cedba 8.下面 4 棵二叉树中，（）不是完全二叉树。A B C D 9.在线索化二叉树中， t 所指结点没有左子树的充分必要条件是（）。A.t-left=null B. t-ltag=1 C. t-left=null 且 t-ltag=1 D.以上都不对10.下列线索
3、二叉树中（用虚线表示线索） ，符合后续线索树的定义的是（） 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 7 页 - - - - - - - - - 11.算术表达式 a+b*(c+d/c)转换为后缀表达式是（） 。Aab+cde/* Babcde/+*+ C abcde/*+ D. abcde*/+ 12.具有 10 个叶结点的二叉树中有（）个度为 2 的结点。A8 B.9 C.10 D.11 13.一个具有 1025 个结点的二叉树的高h 为（） 。A.11 B.
4、10 C.111025 D.101024 14.前序遍历与中序遍历结果相同的二叉树为（） ；前序遍历和后序遍历结果相同的二叉树为（）的二叉树。A.空二叉树B.只有根结点C.根结点无左孩子D.根结点无右孩子15.一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ） 。A.所有非叶结点均无左孩子B.所有非叶结点均无右孩子C.只有一个叶子结点D.A和 B同时成立16.某二叉树的中序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。A.空或只有一个根结点B.任一非叶结点无左子树C.高度等于其结点数D.任一非叶结点无右子树17.线索二叉树是一种（）结构。A. 逻辑B逻辑和存储
5、C物理D 线性18.n个结点的线索二叉树上含有的线索数为（） 。A.2n B.n-1 C.n+1 D.n 19.由 3 个结点可以构造出（）种不同的二叉树。A.2 B.3 C.4 D.5 20.若度为 m 的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（） 。A.n-1 B.n/m-1 C. （n-1）/ （m-1） D. n/ （m-1） -1 21. 对 n（n=2）个权值均不同的字符构成的哈夫曼树，关于该树的叙述中，错误的是（ ） 。A. 该树一定是一棵完全二叉树B. 树中一定没有度为1 的结点名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - -
6、- - - - - - 名师精心整理 - - - - - - - 第 2 页，共 7 页 - - - - - - - - - C. 树中两个权值最小的结点一定是兄弟结点D. 树中任一非叶结点的权值一定不小于下一层结点的权值11.算术表达式 a+b*(c+d/c)转换为后缀表达式是（） 。Aab+cde/* Babcde/+*+ C abcde/*+ D. abcde*/+ 12.具有 10 个叶结点的二叉树中有（）个度为 2 的结点。A8 B.9 C.10 D.11 13.一个具有 1025 个结点的二叉树的高h 为（） 。A.11 B.10 C.111025 D.101024 14.前序遍历
7、与中序遍历结果相同的二叉树为（） ；前序遍历和后序遍历结果相同的二叉树为（）的二叉树。A.空二叉树B.只有根结点C.根结点无左孩子D.根结点无右孩子15.一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ） 。A.所有非叶结点均无左孩子B.所有非叶结点均无右孩子C.只有一个叶子结点D.A和 B同时成立16.某二叉树的中序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。A.空或只有一个根结点B.任一非叶结点无左子树C.高度等于其结点数D.任一非叶结点无右子树17.线索二叉树是一种（）结构。A. 逻辑B逻辑和存储C物理D 线性18.n个结点的线索二叉树上含有的线索数为
8、（） 。A.2n B.n-1 C.n+1 D.n 19.由 3 个结点可以构造出（）种不同的二叉树。A.2 B.3 C.4 D.5 20.若度为 m 的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（） 。A.n-1 B.n/m-1 C. （n-1）/ （m-1） D. n/ （m-1） -1 21. 对 n（n=2）个权值均不同的字符构成的哈夫曼树，关于该树的叙述中，错误的是（ ） 。E. 该树一定是一棵完全二叉树F. 树中一定没有度为1 的结点G. 树中两个权值最小的结点一定是兄弟结点H. 树中任一非叶结点的权值一定不小于下一层结点的权值11.算术表达式 a+b*(c+d/c)转换为后缀
9、表达式是（） 。Aab+cde/* Babcde/+*+ C abcde/*+ D. abcde*/+ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 7 页 - - - - - - - - - 12.具有 10 个叶结点的二叉树中有（）个度为 2 的结点。A8 B.9 C.10 D.11 13.一个具有 1025 个结点的二叉树的高h 为（） 。A.11 B.10 C.111025 D.101024 14.前序遍历与中序遍历结果相同的二叉树为（） ；前序遍历和后序遍历结
10、果相同的二叉树为（）的二叉树。A.空二叉树B.只有根结点C.根结点无左孩子D.根结点无右孩子15.一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ） 。A.所有非叶结点均无左孩子B.所有非叶结点均无右孩子C.只有一个叶子结点D.A和 B同时成立16.某二叉树的中序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。A.空或只有一个根结点B.任一非叶结点无左子树C.高度等于其结点数D.任一非叶结点无右子树17.线索二叉树是一种（）结构。A. 逻辑B逻辑和存储C物理D 线性18.n个结点的线索二叉树上含有的线索数为（） 。A.2n B.n-1 C.n+1 D.n 19.
11、由 3 个结点可以构造出（）种不同的二叉树。A.2 B.3 C.4 D.5 20.若度为 m 的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（） 。A.n-1 B.n/m-1 C. （n-1）/ （m-1） D. n/ （m-1） -1 21. 对 n（n=2）个权值均不同的字符构成的哈夫曼树，关于该树的叙述中，错误的是（ ） 。I.该树一定是一棵完全二叉树J.树中一定没有度为1 的结点K. 树中两个权值最小的结点一定是兄弟结点L. 树中任一非叶结点的权值一定不小于下一层结点的权值二、填空1.一颗二叉树有 67个结点，结点的度要么是0，要么是 2，则这个二叉树中度为2 的结点有（）个2.含
12、 A、B、C三个结点的不同形态的二叉树有（）棵3.一棵含有 n 个结点的二叉树，可能达到的最大深度是（）最小深度是（）4.一棵哈夫曼树有19个结点，则其叶子结点的个数是（）5.设二叉树的中序遍历序列序列是abcdefg，后序遍历序列是bdcafge，则二叉树的前序遍历序列是（）该二叉树对应的森林应该包含（）棵树名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 7 页 - - - - - - - - - 6.一棵树含 n 个结点的满二叉树有（）个度为1 的结点，有（）个分支（
13、非终端）结点和（）个叶子，该满二叉树的深度为（）7.含 4 个度为 2 的结点和 5 个叶子结点的完全二叉树，有（）个度为1 的结点8.已知二叉树前序序列为abcdegcf，中序遍历序列为dbgeacf，则后序序列一定是（）9.设数据 wg=（7,19,2,6,32,3,21,10 ）为叶节点权重集合，则所建Huffman 树的树高是（） ，带权路径长度 wpl 为（）10 现有按中序遍历二叉树的结果为abc，则有（）种不同的二叉树可以得到这一遍历结果11 有一份电文中的共使用6 个字符： a，b，c，d，e，f，它们的出现频率依次为2.3.4.7.8.9，则字符 c的哈夫曼编码是（） ，电文
14、的编码总长度为（）12.在具有 n 个结点的二叉树的二叉链表表示中，其空指针的个数是（）三、问答题1、写出下列算法的功能。Void ABC (BiTree BT) if (BT =NULL )return; ABC(BT-lchild), Printf(“%c ”,BT-data); ABC(BT-rchild); 该算法的功能是：2、写出下列算法的功能。Void LevelOrderTraverse(BiTree T,Status(*vist)(TelemType e) InitQueue(Q ）;EnQueue （Q,T）; While (!QueueEmpty(Q) DeQueue(Q,
15、p);if (Visit(p-data)return ERROR; If (p-lchild) EnQueue(Q,p-lchild); If (p-rchild) EnQueue(Q,p-rchild); Return OK; 该算法的功能是：3、写出下列算法的功能。Status PreOrderTraverse(BiTree T,Status(* visit )(TelemType(e) InitStack(s);Push(S,T); While (!StackEmpty(Q) Pop(S,p);if(Visit(p-data) return ERROR; If(p-rchild) Pus
16、h(S,p-rchild); If(p-lchild) Push(S,p-lchild); Return OK; 该算法的功能是：4、写出下列算法的功能。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 7 页 - - - - - - - - - Void ABC (BiTree BT,int & c1,int & c2) if (BT!=NULL) ABC (BT-lchild,c1,c2); c1+；If(BT -lchild=NULL&BT-rchild=NULL)c
17、2+; 该算法的功能是：四、计算题1.试分别画出具有4 个结点的二叉树的所有不同形态。2.对于如图 6.33 所示的二叉树，试分别写出其先序、 中序、后序和层次遍历序列，并画出其顺序存储结构和二叉链表存储结构。图 6.33 3.试画出图 6.33 所示的二叉树的先序线索二叉树的后序线索二叉树。4.对于 n 个结点的完全二叉树， 用 1 到 n 的连续整数顺序编号， 试回答下列问题。（1）它共有多少层？各层的结点数分别是多少？（2）各层最左边的结点的编号分别是多少？各层最右边的结点的编号分别是多少？（3）对于编号为i（1=i=n）的结点，它的层是多少？他的双亲（若存在）的编号是多少？它的左孩（若
18、存在）和右孩（若存在）的编号分别是多少？5.已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树，并画出它的后序线索二叉树。6.已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG 和 DECBHGFA ， 请画出此二叉树。7.已知二叉树的静态链表储存结构如下，画出此二叉树。下标1 2 3 4 5 6 7 8 9 10 11 Lifti Datai Righti 8.对二叉树中结点进行按层次顺序(每一层自左到右 )的访问操作称为二叉树的层次遍历，遍历所得的结点序列称为二叉树的层次序列，现已知一棵二叉树的层6 0 7 0 8 0 5 0 2 0
19、 0 m f a k b l c r d s e 0 0 9 0 10 4 11 0 1 0 0 1 4 7 6 2 3 5 8 9 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 7 页 - - - - - - - - - 次序列为 ABCDEFGHIJ，中序序列为 DBGEHJACIF，请画出此二叉树。9.欲传输一段电文如下： CATEATDATACAECATAEAAE。设计出这段电文中的每个字符的哈夫曼编码，并计算整段电文的编码长度。10.给定叶子结点的权值集合 1
20、5，3，14，2，6，9，16，17，构造相应的哈夫曼树，并计算它的带权路径长度。五、算法设计题1.已知二叉树 T的数据域均为正数，写一个算法求数据域的最大值int maxdata（Bitree T）2.已知非空二叉树T 的数据域均为字符型数据，数据域的值是“A”只有一个结点，写一个算法求这个结点的双亲Char Parent （Bitree T）3.已知非空二叉树T，写一个算法，求度为2 的结点个数4.用递归方法写一个算法求二叉树的叶节点数int Leafnum（Bitree T） ，先写出基本项和归纳项，然后写算法5.写一个算法求二叉树的深度int Depth （Bitree T）6.写一个算法交换二叉树所有结点的左，右子树status changchild（Bitree T）7.一棵具有 n 个结点的完全二叉树以数组储存，试写一非递归算法实现对该树的前序遍历8.以二叉链储存二叉树，写出在二叉树中查找值为x 的结点在树中的层号算法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 7 页 - - - - - - - - -