计算机专业基础综合数据结构树和二叉树历年真题试卷汇编6 真题(含答案与解析)-交互.pdf

该【计算机专业基础综合数据结构树和二叉树历年真题试卷汇编6 真题(含答案与解析)-交互 】是由【学锋】上传分享，文档一共【13】页，该文档可以免费在线阅读，需要了解更多关于【计算机专业基础综合数据结构树和二叉树历年真题试卷汇编6 真题(含答案与解析)-交互 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:..计算机专业基础综合数据结构(树和二叉树)历年真题试卷汇编6(总分88,做题时间90分钟)()。【华中科技大学2006一、7(2分)】SSS_SINGLE_SELA平衡二叉树B堆C二叉排序树D哈夫曼(Huffman)树分值:2答案:B解析:完全二叉树的叶子至多在下面两层上,且一个结点若无左子树,绝不能有右子树。平衡二叉树任何结点的左右子树的高度差的绝对值不超过1,但其结点的值符合二叉排序树的定义。平衡二叉树(包括二叉排序树)的树形不一定是完全二叉树。堆是一个序列,有大堆和小堆,编号为i的结点,其父结点、左右子女结点之间位置的关系,符合完全二叉树父结点、左右子女结点之间的关系,从这点上说,可以把堆看成完全二叉树。哈夫曼树是二叉树,但树形不一定满足完全二叉树的定义。,其中空的链域的个数是()。【合肥工业大学1999一、5(2分)】SSS_SINGLE_SELA不确定B0C1D2分值:2答案:D解析:左子树为空的二叉树的根结点的左线索为空(无前驱),先序序列的最后结点的右线索为空(无后继),共2个空链域。,其中空的链域的个数是()。【合肥工业大学2000一、5(2分)】SSS_SINGLE_SELA0B1C2D不确定:..分值:2答案:,且X不为根,则X的前驱为()。【南京理工大学1996一、6(2分)】SSS_SINGLE_SELAX的双亲BX的右子树中最左的结点CX的左子树中最右结点DX的左子树中最右叶结点分值:2答案:()。【南京理工大学1998一、5(2分)】SSS_SINGLE_SELA加快查找结点的前驱或后继的速度B为了能在二叉树中方便地进行插入与删除C为了能方便地找到双亲D使二叉树的遍历结果唯一分值:2答案:()结构。【西安电子科技大学1996一、9(2分)】SSS_SINGLE_SELA逻辑B逻辑和存储C物理D线性分值:2答案:()。【中山大学1998二、8(2分)】SSS_SINGLE_SELA2nBn-1Cn+1Dn分值:2:..答案:C解析:线索二叉树是利用二叉树的空链域加上线索,n个结点的二叉树有n+1个空链域。8.()的遍历仍需要栈的支持。【中科院计算所1999一、1(2分)】SSS_SINGLE_SELA前序线索树B中序线索树C后序线索树分值:2答案:,仍不能有效求解的问题是()。【北方交通大学2003一、4(2分)】SSS_SINGLE_SELA先序线索二又树中求先序后继B中序线索二叉树中求中序后继C中序线索二叉树中求中序前驱D后序线索二叉树中求后序后继分值:2答案:D解析:答案应选D。其实,先序线索二叉树求先序前驱也不能有效求解。,下面说法不正确的是()。【南京理工大学2004一、8(1分)】SSS_SINGLE_SELA在中序线索树中,若某结点有右孩子,则其后继结点是它的右子树的左支末端结点B线索二叉树是利用二叉树的n+1个空指针来存放结点前驱和后继信息的C每个结点通过线索都可以直接找到它的前驱和后继D在中序线索树中,若某结点有左孩子,则其前驱结点是它的左子树的右支末端结点分值:2答案:,则具有n个结点的树至少需要()个指向双亲的指针。【中山大学2004】SSS_SINGLE_SELAnBn+1:..Cn-1D2n分值:2答案:C解析:树的双亲表示法除根结点外,每个结点都有一个指向双亲的指针。,每个结点有两个指针域,分别指向“第一个孩子”和“下一个兄弟”。若指向“下一个兄弟”的指针有n个为空,则该树有()个非终端结点。【哈尔滨工程大学2004】SSS_SINGLE_SELA[n/2]Bn-1CnDn+1分值:2答案:,它有m个结点,B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是()。【南京理工大学2000一、17()】SSS_SINGLE_SELAm-nBm-n-1Cn+lD条件不足,无法确定分值:2答案:,第一、第二、第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是()。【北方交通大学2001一、16(2分)】SSS_SINGLE_SELAM1BM1+M2CM3DM2+M3分值:2答案:D15.:..设F是一个森林,B是由F变换得的二叉树。若F中有n个非终端结点,则B中右指针域为空的结点有()个。【西安电子科技大学1998一、10(2分)】SSS_SINGLE_SELAn-1BnCn+1Dn+2分值:2答案:,那么T中结点的后序就是T中结22点的()。【西安电子科技大学1996一、2(2分)】【电子科技大学2005一、7(1分)】SSS_SINGLE_SELA先序B中序C后序D层次序分值:2答案:?()【北方交通大学2001一、6(2分)】SSS_SINGLE_SELA2B3C4D5分值:2答案:A解析:n(n>0)个结点可以构造出1/(n+1)木(2n)!/(n!)2种不同的二叉树。n个结点构造的不同的树的数量等于n一1个结点可以构造出的不同的二叉树的数量。()种树型。【北京邮电大学2005一、5(2分)】SSS_SINGLE_SELA4B5C10:..D14分值:2答案:?()【北方交通大学2001一、7(2分)】SSS_SINGLE_SELA2B3C4D5分值:2答案:,其中所有分支结点的度均为k则该树中叶子结点的2个数为()。【华南理工大学2005一、1(2分)】SSS_SINGLE_SELAn(k-1)/kBn/kC(n+1)/kD(nk-n+1)/k分值:2答案:,哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序()。【中国科技大学1998二、8(2分)】【中科院计算所1998二、8(2分)】【北京工业大学2005一、5(2分)】【电子科技大学2005一、1(1分)】【南京理工大学2004一、10(1分)】SSS_SINGLE_SELA二叉排序树B哈夫曼树CAVL树D堆分值:2答案:,其路径长度最短的二叉树是()。【电子科技大学2005一、3(1分)】SSS_SINGLE_SELA哈夫曼树:..B完全二叉树CAVL树D二叉排序树分值:2答案:,最优二叉树一定是完全二叉树,该说法()。【中国科技大学1998二、10(2分)】【中科院计算所1998二、10(2分)】SSS_JUDGEMENT正确错误分值:2答案:,其结点个数是15,则该二叉树最大深度为()。【北京理工大学2007一、8(1分)】SSS_SINGLE_SELA4B5C8D9分值:2答案:,对其进行Huffrnan编码,共能得到()个不同的码字。【北京邮电大学2005一、6(2分)】SSS_SINGLE_SELA107B108C214D215分值:2答案:,若已对两个字符编码为1和01,则还可以对()字符编码。【哈尔滨工程大学2005】SSS_SINGLE_SELA2B3:..C4D5分值:2答案:C解析:因为哈夫曼编码长度不超过4,且已有两个字符编码为1和01,则还可以最多为4个字符编码,这4个字符的编码分别为0000,0001,0010,0011。,其叶结点个数为n,则非叶结点的个数为()。【中科院计算所:1999一、2(2分)】SSS_SINGLE_SELAn-1B[n/m]一1C[(n-1)/(m-1)]D[n/(m-1)]一1E[(n+1)/(m+1)]一1分值:2答案:?()【中科院计算所2000一、2(2分)】SSS_SINGLE_SELA(00,01,10,11)B(0,1,00,11)C(0,10,110,111)D(1,01,000,001)分值:2答案:?()【哈尔滨工业大学2004二、1(1分)2005二、1(1分)】SSS_SINGLE_SELA{00,01,10,11)B{0,1,00,11)C{0,10,110,111)D{,010,101)分值:2答案:,()不是前缀码。【湖南大学2003】SSS_SINGLE_SEL:..A{00,01,10,11}B{0,1,00,11)C{0,10,110,111)D{10,110,1110,1111)分值:2答案:,根据其使用频率设计对应的哈夫曼编码,以下()是可能的哈夫曼编码。【武汉大学2006】SSS_MULTI_SELA000,001,010,011,1B0000,0001,001,01,1C000,001,01,10,11D00,100,101,110,111分值:2答案:A,B,C解析:D之所以错误,是因为若有编码00,至少必须有编码01,否则只一个结点不可能构成双亲。“遗传”关系,设x是y的父亲,则x可以把它的属性遗传给y,表示该遗传关系最适合的数据结构为()。【中国科学院2006】SSS_SINGLE_SELA向量B树C图D二叉树分值:2答案:()非终端结点。【北京邮电大学2007】SSS_SINGLE_SELA31B63C127D255分值:2答案:.:..在顺序存储的二叉树中,编号为i和j的两个结点处在同一层的条件是__________。【厦门大学2002六、3(4分)】SSS_TEXT_QUSTI分值:2答案:正确答案:用顺序存储结构存储二叉树时,要按完全二叉树的形式存储,非完全二叉树存储时,要加“虚结点”。设编号为i和j的结点在顺序存储中的下标为s和t,则结点i和j在同一层上的条件是[logs]=[logt]。(1)个度为1的结点、有(2)个分支(非终端)结点和(3)个叶子,该满二叉树的深度为(4)。【华中理工大学2000一、6(3分)】SSS_TEXT_QUSTI分值:2答案:正确答案:(1)0(2)(n—1)/2或[n/2](3)(n+1)/2(4)log(n+1),则高度为尼的二又树的最大结点数为__________,最小结点数为__________。【北京大学1997一、1(4分)】SSS_TEXT_QUSTI分值:2答案:正确答案:(1)2k+1一1(2)k+。【电子科技大学2008二、1(1分)】SSS_TEXT_QUSTI分值:2答案:正确答案:1,0,——个叶子结点。【合肥工业大学1999二、6(2分)】SSS_TEXT_QUSTI分值:2:..答案:正确答案:2k-2。设根结点层次为1,则该二叉树第K层有1个叶子结点,第k-1层有2k-2一1个叶子结点。,则该二叉树的总结点数至少是__________。【厦门大学2002六、4(4分)】【北京交通大学2005二、1(2分)】SSS_TEXT_QUSTI分值:2答案:正确答案:,则有64个结点的完全二叉树的深度为__________。【中南大学2005二、10(2分)】SSS_TEXT_QUSTI分值:2答案:正确答案:,则整棵树上度为1的结点数是__________。【北京交通大学2006二、3(2分)】SSS_TEXT_QUSTI分值:2答案:正确答案:1。详细分析见上面一、7。。【南京理工大学1997三、2(1分)】SSS_TEXT_QUSTI分值:2答案:正确答案:,那么结点i没有右兄弟的条件为__________。【北京工业大学2005二、2(3分)】:..SSS_TEXT_QUSTI分值:2答案:正确答案:2*i+1>,其分支结点数目为n,则其叶子结点数目为__________。【北京大学2005】SSS_TEXT_QUSTI分值:2答案:正确答案:n(k-1)+11