数据结构练习

一、单选题1．树结构最适合用来 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示()。B.无序数据D.元素间无关联的数据A•有序数据C.元素间具有分支层次关系的数据2．除根结点外，树上每个结点()。A．d,g,b,a,e,c,h,fa,b,c,d,e,f,g,hB．D．a,b,d,g,c,e,f,hA．2B．3C．4D．4．某完全二叉树有7个叶子，则其结点总数为()。A．14B．13C．13或14D5．高度为n、结点数也为n的二叉树，共有()棵。A．nB．2n-1C．n-1D．以上都不是2n-1A.可有任意多个孩子、一个双亲B.可有任意多个孩子、任意多个双亲C.可有一个孩子、任意多个双亲D.只有一个孩子、一个双亲3．3个结点可构成()个不同形态的二叉树。则该二叉树具有的特征是()。任一结点无左孩子空或只有一个结点某二叉树的先根遍历序列和后根遍历序列相同，B．D．A•高度等于其结点数C.任一结点无右孩子9．二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序()。可能改变B.—定会改变C.一定不改变D.可能变也可能不变10•假设某完全二叉树顺序存储在数组BT[m]中，其中根结点存放在BT[0],若BT[i]中的结点有左孩子，则左孩子存放在()。A．BT[i/2]B．BT[2*i-1]C．BT[2*i]D．BT[2*i+1]11.对n个结点的二叉树，按()遍历顺序对结点编号(号码为1~n)时，任一结点的编号等于其左子树中结点的最大编号加1，又等于其右子树中结点的最小编号减1。前根B.中根C.后根D.层次12．在二叉链表上交换所有分支结点左右子树的位置，则利用()遍历方法最合适。A•前序B•中序C•后序D.按层次13•已知森林F={T],T2,T3},各棵树Ti(i=1,2,3)中所含结点的个数分别为7,3,5,则与F对应的二叉树的右子树中的结点个数为()。A．10B．12C．8D．1514．下图所示二叉树对应的森林中有()棵树。B．2C．3D.不确定15．以下叙述错误的是()。树的先根遍历需要借助栈来实现。树的层次遍历需要借助队列来实现。树的后根遍历与对应二叉树的后根遍历相同。树的先根序列与对应二叉树的先根序列相同。16．给定整数集合{3,5,6,9,12},与之对应的哈夫曼树是()。下列编码中属前缀码的是()。A.{1,01,000,001}B.{0,10,110,11}C.{1,01,011,010}D.{0,1,00,11}关于哈夫曼树,下列叙述正确的是()。A.可能有度为1的结点有可能是满二叉树线索二叉树中某结点没有左孩子的条p!=NULLB.p-〉ltag==ONULL线索二叉树中某结点为叶子的条件是(p-〉ltag==0||p-〉rtag==0p-〉ltag==1&&p-〉rtag==1总是完全二叉树WPL是深度最大叶子的带权路径长度是()。p-〉ltag==1D.p-〉lchild!=)。A.p-〉lchild!=NULL||p-〉rchild!=NULLp-〉lchild!=NULL&&p-〉rchild!=NULL二、判断题二叉树中至少有一个结点的度为2。二叉树中可能所有结点的度都小于2。树的度是指树中结点的最大度数,所以二叉树的度为2。满二叉树是一种特殊的完全二叉树。若二叉树中没有度为1的结点,则为满二叉树。不可能有二叉树的任何遍历次序是相同的。二叉树中不可能有两个结点在先根、中根和后根序列中的相对次序都不变。由二叉树的先根和后根序列可以唯一确定该二叉树。任何树或林都可转化为二叉树,反之,二叉树可转化为任何树或林。树和森林都可转化为二叉树,故对给定的二叉树,不能区分是由树还是森林转换来的。11．由普通树转换来的二叉树，其根结点一定没有右子树。12．将树转化为二叉树后，原树中的叶子结点在二叉树中不一定也是叶子结点。13、哈夫曼树是一种二叉树，所以其节点的度可为0,1或2。14．哈夫曼树中不存在度为1的结点。15．不管树的深度和形态如何，也不可能构造出一棵有100个结点的哈夫曼树。16．利用哈夫曼编码，可以进行文件压缩。17．线索二叉链表就是用结点的空指针域来存放某种遍历的前趋和后继线索，所以线索二叉链表中就没有空指针了。18．在线索二叉树上，求结点的（遍历）前趋和后继时可利用线索得到，即不必进行遍历了。19．利用栈可将递归程序转化成非递归程序。20．消除递归不一定需要使用栈。三、填空题TOC\o"1-5"\h\z1．对100个结点的树，所有结点的度数之和为。2．某树所有结点的度数之和为100，则树中边数为。深度为k的二叉树，结点数至多为—，结点数至少为—。深度为k的二叉树，叶子数至多为—，叶子数至少为—。5．200个结点的二叉树，深度至多为，深度至少为。6．在深度为7的二叉树中，第5层上的结点数最少为，最多为。7．对400个结点的完全二叉树，叶子数为。8．对400个结点的完全二叉树，度为1的结点数为。9．某完全二叉树的第5层只有6个结点，则其叶子结点数是。10．某二叉树中双分支结点数为5个，单分支结点数为4个，则叶子结点数为个。11．对100个结点的完全二叉树按层编号（编号1~100），则编号为49的结点，其双亲的编号为，编号最小的叶子结点的编号为。12．n个结点的二叉链表中，指针总数为个，其中个指针为空。13．已知哈夫曼树有100个叶子，则其结点总数是。14．某哈夫曼树有109个结点，则其叶子数是，度为2的结点数是。15．由权值为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为。16．树的三种主要的遍历方法是：、和层次遍历。17．树的三种常用存储结构是：孩子链表表示法、和。18．某二叉树有50个结点，根的右子树有45个结点，则对应的森林中第一棵树的结点数为。19．线索二叉树中，线索的含义是。请画出该树以及对应的二叉树。20．对n个结点的线索二叉树，线索有个。四、应用题、综合题1．对右图的二叉树，1）画出中序线索二叉树；2）画出对应的森林。1.已知某树的双亲表示法如下12345678910dataABCDEFJGHIparent01112234441.已知某二叉树的后序遍历和中序遍历的序列分别为：CEFBDA与CBEFAD,画出这棵二叉树。画出中序线索二叉树。1．已知如下二叉树的中序序列为｛19,28,36,47,52,63,78｝,请标出各结点的值；并画出中序线索二叉链表。已知二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，画出二叉树。已知某二叉树的中序和前序序列分别为：CBDEAGIHJF和ABCDEFGHIJ,画出二叉树、中序线索二叉链表。已知二叉树的层次序列为ABCDEFGHIJ,中序序列为DBGEHJACIF,画出二叉树。已知字符集｛d,t,e,l,r｝的概率分布为｛0.12,0.15,0.40,0.25,0.08｝,试给出字符集的哈夫曼编码,并翻译出电文1111010110111000的内容。假定用于通信的电文仅由8个字母c1,c2,c3,c4,c5,c6,c7,c8组成，各字母在电文中出现的频率分别为5,25,3,6,10,11,36,4。试为这8个字母设计不等长Huffman编码，并给出该电文的总码长。若用等长编码,每个字符至少几位编码？这时Huffman编码使电文总长压缩了多少？解：(1)Huffman编码为c1c2c3c4c5c6c7c801101000000111001010110001电文总码长为4*5+2*25+4*3+4*6+3*10+3*11+2*36+4*4=257(2)有8个字符，等长编码时，码长至少3(23=8)。这时总码长=(5+25+3+6+10+11+36+4)*3=・・・7.按给定权值｛3,7,10,15,25,30｝，构造相应的哈夫曼树，并求相应的WPL。8•假设通信电文使用的字符集为｛a,b,c,d,e,f,g｝，字符的哈夫曼编码依次为：0110,10,110，111，00，0111和010。（1）请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应字符；（2）若这些字符在电文中出现的频度分别为：3，35，13，15，20，5和9，求该哈夫曼树的带权路径长度。9．把下图的树转换成二叉树。AFGLC111.二叉树的广义表表示为a（b（c）,d（e,f））,分别写出它的先序、中序、后序、层序序列。解：先序：a,b,c,d,e,f，中序:c,b,a,e,d,f,后序：c,b,e,f,d,a,按层：a,b,d,c,e,f12．画出3个结点的树和3个结点的二叉树的所有不同形态。13•某树有叫个度为1的结点，有n2个度为2的结点，…，n个度为m的结点，则有12m解： 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 点数n=n0+n+n2+...+nTOC\o"1-5"\h\z012m或根+孩子：n=1+比+2*n2+...+m*n，两式相减贝V有12m（、n-（i-1）nI+1HYPERLINK\l"bookmark0"\o"CurrentDocument"0（严J结点数为n（n>1）的树，咼度最小、最大是多少？解：高度最小为2,有2层：1个根，其它n-1个为其孩子。高度最大为n,有n层：1个叶结点，其它n-1个为分支结点。在具有n个结点的k叉树（k>2）的k叉树链表表示中，有多少个空指针?解：kn-（n-1）=（k-1）n+1个空指针试找出分别满足下面条件的所有二叉树：（1）前序序列和中序序列相同；（2）中序序列和后序序列相同；（3）前序序列和后序序列相同；（4）前序、中序、后序序列均相同。解：（1）空或任一结点均无左子树（2）空或任一结点均无左子树（3）空或仅有一个结点（4）同（3）在何种线索树中，线索对所求指定结点在相应次序下的前趋和后继并无帮助？解：在前序线索树中找某一点的前序前趋以及在后序线索树中寻找某一点的后继，线索并无多大帮助。18．请画出下图所示的树对应的二叉树。解：对应二叉树.”246719.画出如下森林所对应的二叉树。解：FG20.能否用树的先根遍历序列和后根遍历序列唯一确定一棵树?对应二叉树E解：可以。因为树的先根遍历与对应的二叉树前序遍历相同,树的后根遍历与对应二叉树的中序遍历相同，而由二叉树的前序遍历序列和中序遍历序列能够唯一地确定二叉树，从而唯一确定相应的树。21.在什么样的情况下，等长编码是最优前缀码？解：当字符集中的各字符使用频率均匀时。22、高度为k>1非叶结点的度数等于1的树有多少棵？有一个完全二叉树按层次顺序存放在一维数组中，如下所示123456789101112HKACDpFJXBQz请指出结点P的父结点，左孩子，右孩子。五、算法设计题1.设计递归算法，求二叉树t中度为1的结点数。二叉链表的类型定义如下:typedefintdatatype;typedefstructNODE*pointer;structNODE{datatypedata;pointerlchild,rchild;};typedefpointerbitree;//结点的数据类型，假设为int//结点指针类型//根指针类型1.设计递归算法，求二叉树t中度为2的结点数。二叉链表的类型定义如下:typedefintdatatype;typedefstructNODE*pointer;structNODE{datatypedata;pointerlchild,rchild;};typedefpointerbitree;//结点的数据类型，假设为int//结点指针类型//根指针类型1.设计递归算法，判断二叉树t中是否所有结点都为正数。二叉链表的类型定义如下://结点的数据类型，假设为int//结点指针类型//根指针类型1．设计递归算法，按递减顺序输出二叉排序树t中所有结点。二叉链表的类型定义如下:typedefintdatatype;typedefstructNODE*pointer;structNODE{datatypedata;pointerlchild,rchild;};typedefpointerbitree;//结点的数据类型，假设为int//结点指针类型//根指针类型1．设计算法，输出二叉排序树t中结点的最小值。二叉链表的类型定义如下：typedefintdatatype;typedefstructNODE*pointer;structNODE{datatypedata;pointerlchild,rchild;};typedefpointerbitree;//结点的数据类型，假设为int//结点指针类型//根指针类型typedefintdatatype;typedefstructNODE*pointer;structNODE{datatypedata;pointerlchild,rchild;};typedefpointerbitree;1．2．//结点的数据类型，假设为int//结点指针类型//根指针类型设计递归算法，按递增顺序输出二叉排序树t中所有大于或等于给定值x的结点。叉链表的类型定义如下：typedefintdatatype;typedefstructNODE*pointer;structNODE{datatypedata;pointerlchild,rchild;};typedefpointerbitree;设计递归算法判断二叉树t是否为大根堆。设二叉链表类型定义如下。typedefstructNODE*pointer;//结点指针类型structNODE{intdata;pointerlchild,rchild;};typedefpointerbitree;//根指针类型1.写出二叉链表的结点类型定义，并设计一个递归算法判断二叉树t是否为大根堆。3•设计算法，求二叉树T中值最小的结点（返回该结点地址）。=＞综合TOC\o"1-5"\h\z38.设一棵二叉树结点的先根序列为ABDECFGH，中根序列为DEBAFCHG,则二叉树中叶子结点是。=＞候选2．含有15个结点的二叉树中，最小高度是（）A、6B、5C、4D、32．n个结点的二叉树，最大可能深度为（）。A．nB．n-lC．n/2D．log2n3．深度为k的二叉树叶子数至多有（)。A．2k个B．2k-1个C．2k-1个D．2k-1-1个5．深度为k的二叉树结点数至多为（)。A．kB．2k-1C．2k－1D．不确定2．深度为5的二叉树，至多有（）个结点。A．16B．32C．31D．10二叉树就是度为2的有序树。二叉树中任何一个结点的度都是2。二叉树的顺序存储将就是二叉树的节点按层次排列的顺序进行储存。不能由二叉树的先根和后根序列唯一确定该二叉树，是因为不能确定谁是根。二叉树中根序列的最后一个点若为叶子，则它也是先根序列的最后一个点。树的遍历就是用某种方法将树中各节点都访问到。在叶子数和权值相同的所有二叉树中，最优二叉树一定是完全二叉树。哈夫曼树一定是满二叉树。最优二叉树节点总数不可能为偶数。任何最优二叉树的结点总数不可能是100。在叶子节点相同的二叉树中，哈夫曼树高度最小。含有3个2度结点和4个叶结点的二叉树可含个1度结点。6.若非空二叉树的先根遍历序列和后根遍历遍历相反，则该二叉树的特点—。TOC\o"1-5"\h\z对121个结点的完全二叉树，叶子数为，度为1的结点数为，度2的结点数为。对n个叶子结点的严格二叉树，结点总数为（）5.对67个结点的严格二叉树，度为2的结点有个。1.50个结点的完全二叉树按层序顺序存于数组bt[1..5O]中，则该树最底层左边第一个结点存储在数组元素中。7•深度为8（根的层次号为1）的满二叉树有8—个叶子结点。中序遍历序列线索二叉树中，左线索指向，右线索指向39.下图的二叉树前序遍历序列是是，‘后序遍历序列是。B八CDEF二叉树是树的特殊情形。如果一个完全二叉树有2kT个叶子，则其高度必为k。TOC\o"1-5"\h\z3．在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2个，那么度为0的结点数有个。2．在一棵度为3的树中，度为2的结点有1个，度为0的结点有6个，则度为3的结点个数是。22．深度为3的满四叉树的结点数为个。=＞较深21．假定一棵三叉树的结点个数为50，则它的最小深度为，最大深度为。6•设x和y是某二叉树中的两个结点，若在先根序列中x在y之前，而在后根序列中x在y之后，则x和y的关系是()。A、x是y的左兄弟B、x是y的右兄弟C、x是y的祖先D、x是y的后代35．在左右子树均不空的先序线索二叉树中，空链域的数目是。30．在哈夫曼编码中，若编码长度只允许小于等于4，则除了已对两个字符编码为0和10外，还可以最多对个字符编码。37.—棵二叉树的广义表表示为a(b(c,d),e(f(,g))),则e结点的双亲结点为,左孩子结点为，右孩子结点为，先根序列为，层次序列为