计算机专业基础综合数据结构(树和二叉树)历年真题试卷汇编6

计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编10(总分：68.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：30.00)1.先序序列为a，b，c，d的不同二叉树的个数是( )。

【2015年全国试题2(2分)】（分数：2.00）A.13B.14C.15 √D.16解析：解析：先序序列为1，2，3，…，n的不同的二叉树的数目是1／(n+1)((2n)!／(n!*n!))。

2.下列选项给出的是从根分别到达两个叶结点路径上的权值序列，能属于同一棵哈夫曼树的是( )。

【201 5年全国试题3(2分)】（分数：2.00）A.24，10，5和24，10，7B.24，10，5和24，12，7C.24，10，10和24，14，11D.24，10，5和24，14，6 √解析：解析：A的错误在于若路径上有两个10，叶子5应和另一个权值5组成左右子女，7和3组成左右子女，显然不符合哈夫曼的构造规则(应该3和5组成左右子女构造双亲结点)；若路径上只有一个10，5和7并非其左右子女。

B的错误在于双亲10和双亲12不可能构造双亲24。

C的错误是路径上不可能有相同权值10的结点。

D是正确的，双亲10的另一个子女是5，双亲14的另一个子女是8，而双亲10和双亲14恰是双亲24的左右子女。

3.树是一种逻辑关系，表示数据元素之间存在的关系为( )。

【北京交通大学2007(2分)】（分数：2.00）A.集合关系B.一对一关系C.一对多关系√D.多对多关系解析：4.下列判断，( )是正确的。

【华南理工大学2005一、1(2分)】（分数：2.00）A.二叉树就是度为2的树B.二叉树中不存在度大于2的结点√C.二叉树是有序树D.二叉树的每个结点的度都为2解析：解析：二叉树与树是两个不同的概念。

相同点是二者都是树形结构，不同点有三：一是二叉树的度至多是2，树无此限制；二是二叉树的子树有左右子树之分，只有一棵子树时，也必须区分是左子树还是右子树，树不必这样；三是二叉树允许为空，树不准为空，但是多数教科书认为树可以为空，否则空二叉树无法转换成空树，本题第一问有二义性。

计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编1(总分：86.00，做题时间：90分钟)一、单项选择题(总题数：27，分数：54.00)1.一棵完全二叉树上有1001个结点，其中叶子结点的个数是( )。

【西安交通大学1996三、2(3分)】（分数：2.00）A.250B.500C.254D.505E.以上答案都不对2.一棵124个叶结点的完全二叉树，最多有( )个结点。

【中国科学技术大学1995十四、3(2分)】（分数：2.00）A.247B.248C.249D.250E.2513.已知一棵完全二叉树中共有626个结点，叶子结点的个数应为( )。

【上海交通大学2005四、6(2分)】（分数：2.00）A.3 11B.3 12C.3 13D.3 14E.其他4.具有300个结点的二叉树，其高度至少应为( )。

【北京理工大学2006五、8(1分)】（分数：2.00）A.6B.7C.8D.95.当结点数目一定时，具有最小深度的二叉树是( )。

【北京航空航天大学2005】（分数：2.00）A.满二叉树B.完全二叉树C.线索二叉树D.二叉排序树6.二叉树的第I层上最多含有的结点数为( )。

【中山大学1998二、7(2分)】【北京理工大学2001六、5(2分)】（分数：2.00）A.2 IB.2 I-1一1C.2 I-1D.2 I一17.从树根(第0层)起，自上到下，逐层从左到右给二叉树的所有结点从1开始编号，则完全二叉树的第h 层的从左到右第k个结点的编号为( )。

【电子科技大学2005一、6(1分)】（分数：2.00）A.2 h +h-1B.2 h一k+1C.2 h +k+1D.2 h一k-18.下列判断中，( )是正确的。

【华南理工大学2006一、2(2分)】（分数：2.00）A.深度为k的二叉树最多有2 k -1个结点(k≥1)，最少有k个结点B.二叉树中不存在度大于2的结点C.对二叉树遍历是指先序、中序或后序遍历中的一种D.构造线索二叉树是为能方便找到每个结点的双亲9.一个具有1025个结点的二叉树的高h为( )。

计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编1(总分：86.00，做题时间：90分钟)一、单项选择题(总题数：27，分数：54.00)1.一棵完全二叉树上有1001个结点，其中叶子结点的个数是( )。

【西安交通大学1996三、2(3分)】A.250B.500C.254D.505E.以上答案都不对√2.一棵124个叶结点的完全二叉树，最多有( )个结点。

【中国科学技术大学1995十四、3(2分)】A.247B.248 √C.249D.250E.2513.已知一棵完全二叉树中共有626个结点，叶子结点的个数应为( )。

【上海交通大学2005四、6(2分)】A.3 11B.3 12C.3 13 √D.3 14E.其他4.具有300个结点的二叉树，其高度至少应为( )。

【北京理工大学2006五、8(1分)】A.6B.7C.8D.9 √5.当结点数目一定时，具有最小深度的二叉树是( )。

【北京航空航天大学2005】A.满二叉树B.完全二叉树√C.线索二叉树D.二叉排序树设结点数目是n，n个结点未必是满二叉树，A错。

C和D明显错误。

6.二叉树的第I层上最多含有的结点数为( )。

【中山大学1998二、7(2分)】【北京理工大学2001六、5(2分)】A.2 IB.2 I-1一1C.2 I-1√D.2 I一17.从树根(第0层)起，自上到下，逐层从左到右给二叉树的所有结点从1开始编号，则完全二叉树的第h 层的从左到右第k个结点的编号为( )。

【电子科技大学2005一、6(1分)】A.2 h +h-1 √B.2 h一k+1C.2 h +k+1D.2 h一k-18.下列判断中，( )是正确的。

【华南理工大学2006一、2(2分)】A.深度为k的二叉树最多有2 k -1个结点(k≥1)，最少有k个结点√B.二叉树中不存在度大于2的结点√C.对二叉树遍历是指先序、中序或后序遍历中的一种D.构造线索二叉树是为能方便找到每个结点的双亲9.一个具有1025个结点的二叉树的高h为( )。

计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编1计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编1(总分：86.00，做题时间：90分钟)一、单项选择题(总题数：27，分数：54.00)1.一棵完全二叉树上有1001个结点，其中叶子结点的个数是( )。

【西安交通大学1996三、2(3分)】A.250B.500C.254D.505E.以上答案都不对√2.一棵124个叶结点的完全二叉树，最多有( )个结点。

【中国科学技术大学1995十四、3(2分)】A.247B.248 √C.249D.250E.2513.已知一棵完全二叉树中共有626个结点，叶子结点的个数应为( )。

【上海交通大学2005四、6(2分)】A.3 11B.3 12C.3 13 √D.3 14E.其他4.具有300个结点的二叉树，其高度至少应为( )。

【北京理工大学2006五、8(1分)】A.6B.7C.8D.9 √5.当结点数目一定时，具有最小深度的二叉树是( )。

【北京航空航天大学2005】A.满二叉树B.完全二叉树√C.线索二叉树D.二叉排序树设结点数目是n，n个结点未必是满二叉树，A错。

C和D明显错误。

6.二叉树的第I层上最多含有的结点数为( )。

【中山大学1998二、7(2分)】【北京理工大学2001六、5(2分)】A.2 IB.2 I-1一1C.2 I-1√D.2 I一17.从树根(第0层)起，自上到下，逐层从左到右给二叉树的所有结点从1开始编号，则完全二叉树的第h 层的从左到右第k个结点的编号为( )。

【电子科技大学2005一、6(1分)】A.2 h +h-1 √B.2 h一k+1C.2 h +k+1D.2 h一k-18.下列判断中，( )是正确的。

【华南理工大学2006一、2(2分)】A.深度为k的二叉树最多有2 k -1个结点(k≥1)，最少有k个结点√B.二叉树中不存在度大于2的结点√C.对二叉树遍历是指先序、中序或后序遍历中的一种D.构造线索二叉树是为能方便找到每个结点的双亲9.一个具有1025个结点的二叉树的高h为( )。

计算机专业基础综合数据结构（树与二叉树）-试卷1(总分：62.00，做题时间：90分钟)一、单项选择题(总题数：23，分数：46.00)1.单项选择题1-40小题。

下列每题给出的四个选项中，只有一个选项是最符合题目要求的。

（分数：2.00）__________________________________________________________________________________________ 解析：2.在下面关于树的相关概念的叙述中，正确的是( )。

（分数：2.00）A.只有一个结点的二叉树的度为1B.二叉树的度一定为2C.二叉树的左右子树可任意交换D.深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树√解析：解析：只有一个结点的二叉树的度为零。

二叉树的度可以为0、1、2；二叉树的左右子树不能任意交换。

3.已知一算术表达式的中缀形式为A+B*C-D／E，后缀形式为ABC*+DE／一，其前缀形式为( )。

（分数：2.00）A.一A+B*C／DEB.一A+B*CD／EC.一+*ABC／DED.一+A*BC／DE √解析：解析：根据题目给出的中缀和后缀表达式可以得到其算术表达式为：(A+B*C)一D／E，前缀表达式：一+A*BC／DE。

4.算术表达式a+b*(c+d／e)转为后缀表达式后为( )。

（分数：2.00）A.ab+cde／*B.abcde／+*+ √C.abcde／*++D.abcde*／++解析：解析：根据表达式a+b*(c+d／e)可知其后缀表达式为abcde／+*+。

5.某二叉树的先序遍历序列为IJKLMNO，中序遍历序列为JLKINMO，则后序遍历序列是( )。

（分数：2.00）A.JLKMNOIB.LKNJOMIC.LKJNOMI √D.LKNOJMI可以确认后序遍历的序列为LKJNOMI。

6.设森林F对应的二叉树为B，它有m个结点，B的根为P，P的右子树结点个数为n，森林F中第一棵树的结点个数是( )。

E F D GAB/+ +* - C* 第六章树和二叉树一、选择题1．已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/-，其前缀形式为( )A ．-A+B*C/DE B. -A+B*CD/E C ．-+*ABC/DED. -+A*BC/DE【北京航空航天大学 1999 一、3 （2分)】2．算术表达式a+b*（c+d/e ）转为后缀表达式后为（）【中山大学 1999 一、5】A ．ab+cde/*B ．abcde/+*+C ．abcde/*++ D．abcde*/++3. 设有一表示算术表达式的二叉树（见下图），它所表示的算术表达式是（）【南京理工大学1999 一、20（2分）】A. A*B+C/(D*E)+(F-G)B. (A*B+C)/(D*E)+(F-G)C. (A*B+C)/(D*E+（F-G ）)D. A*B+C/D*E+F-G4. 设树T 的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T 中的叶子数为（）A ．5 B．6 C．7D ．8【南京理工大学 2000 一、8 （1.5分）】5. 在下述结论中，正确的是（）【南京理工大学 1999 一、4 （1分）】①只有一个结点的二叉树的度为0; ②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A ．①②③ B ．②③④ C．②④D ．①④6. 设森林F 对应的二叉树为B ，它有m 个结点，B 的根为p,p 的右子树结点个数为n,森林F中第一棵树的结点个数是（）A ．m-nB ．m-n-1C ．n+1D ．条件不足，无法确定【南京理工大学2000 一、17（1.5分）】7. 树是结点的有限集合，它（(1）)根结点，记为T 。

其余结点分成为m （m>0）个(（2）)的集合T1，T2，…，Ｔm ，每个集合又都是树，此时结点T 称为Ti 的父结点，Ti 称为T 的子结点（1≤i ≤m ）。

计算机专业（基础综合）模拟试卷6(题后含答案及解析)题型有：1. 单项选择题 2. 综合应用题单项选择题1-40小题，每小题2分，共80分。

下列每题给出的四个选项中，只有一个选项是最符合题目要求的。

1．在一个双链表中，在*p结点之前插入*q结点的操作是( )。

A．p-＞prior=q；q-＞next=p；p-＞prior-＞next=q；q-＞prior=p-＞prior；B．q-＞prior=p-＞prior；p-＞prior-＞next=q；q-＞next=p；p-＞prior=q-＞next；C．q-＞next=p；p-＞next=q；q-＞prior-＞next=q；q-＞next=p；D．p-＞prior-＞next=q；q-＞next=p；q-＞prior=p-＞prior；p-＞prior=q；正确答案：D解析：(1)p结点的前驱结点指向的后继结点指向q。

(2)q的后继结点指向p。

(3)q的前驱结点指向p的前驱结点。

(4)p的前驱结点更新为q。

2．设有n个元素进栈序列是P1，P2，P3，…，Pn，其输出序列是1，2，3，…，n，若P3=3，则P1的值( )。

A．可能是2B．一定是2C．不可能是1D．一定是1正确答案：A解析：当P3=3时，进栈序列是P1，P2，P3，…，Pn，由输出序列可知，只有以下两种情况：P1进栈后出栈，P2进栈后出栈，或P1、P2都进栈然后出栈，因此P1的值可能为1，也可能为2。

故选A。

3．A．4B．5C．6D．7正确答案：C解析：将T2还原为森林T1，其中有4棵树：C、D、F、G，I和J是叶子结点。

4．若二叉树的前序序列为DABCEFG，中序序列为BACDFGE，则其层次序列为( )。

A．BCAGFEDB．DAEBCFGC．ABCDEFGD．BCAEFGD正确答案：B解析：由前序序列和中序序列先构造出二叉树，然后按层次序列进行访问。

也可以使用排除法，由于前序序列第一个访问的结点必定是根结点，即D为根结点。

计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编8(总分：66.00，做题时间：90分钟)一、填空题(总题数：22，分数：44.00)1.设一棵完全二叉树叶子结点数为k，最后一层结点数>2，则该二叉树的高度为__________。

【北京科技大学1998一、3】（分数：2.00）__________________________________________________________________________________________ 2.已知完全二叉树的第7层有10个叶子结点，则整个二叉树的结点数最多是__________。

【东南大学2005数据结构部分二、7(1分)】（分数：2.00）__________________________________________________________________________________________ 3.将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点编号为0，则编号为50的结点的右孩子编号为__________。

【中南大学2005二、l(2分)】（分数：2.00）__________________________________________________________________________________________ 4.高度为i(i≥1)的完全二叉树最多有__________个结点；最少有__________个结点；若按自上而下，从左到右的次序给结点编号(从1开始)，则编号最小的叶子结点的编号为__________。

【大连理工大学2005一、2(3分)】【江苏大学2006二、3(2分)】（分数：2.00）__________________________________________________________________________________________ 5.对于一个具有n个结点的二叉树，当它为一棵(1)二叉树时具有最小高度，当它为一棵(2)时，具有最大高度。

计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编6(总分88, 做题时间90分钟)1. 单项选择题1.一棵完全二叉树又是一棵( )。

【华中科技大学2006一、7(2分)】SSS_SINGLE_SELA 平衡二叉树B 堆C 二叉排序树D 哈夫曼(Huffman)树分值: 2答案:B解析：完全二叉树的叶子至多在下面两层上，且一个结点若无左子树，绝不能有右子树。

平衡二叉树任何结点的左右子树的高度差的绝对值不超过1，但其结点的值符合二叉排序树的定义。

平衡二叉树(包括二叉排序树)的树形不一定是完全二叉树。

堆是一个序列，有大堆和小堆，编号为i的结点，其父结点、左右子女结点之间位置的关系，符合完全二叉树父结点、左右子女结点之间的关系，从这点上说，可以把堆看成完全二叉树。

哈夫曼树是二叉树，但树形不一定满足完全二叉树的定义。

2.一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是( )。

【合肥工业大学1999一、5(2分)】SSS_SINGLE_SELA 不确定B 0C 1D 2分值: 2答案:D解析：左子树为空的二叉树的根结点的左线索为空(无前驱)，先序序列的最后结点的右线索为空(无后继)，共2个空链域。

3.一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是( )。

【合肥工业大学2000一、5(2分)】SSS_SINGLE_SELA 0B 1C 2D 不确定分值: 2答案:B4.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为( )。

【南京理工大学1996一、6(2分)】SSS_SINGLE_SELA X的双亲B X的右子树中最左的结点C X的左子树中最右结点D X的左子树中最右叶结点分值: 2答案:C5.引入二叉线索树的目的是( )。

【南京理工大学1998一、5(2分)】SSS_SINGLE_SELA 加快查找结点的前驱或后继的速度B 为了能在二叉树中方便地进行插入与删除C 为了能方便地找到双亲D 使二叉树的遍历结果唯一分值: 2答案:A6.线素二叉树是一种( )结构。

计算机专业基础综合数据结构（图）历年真题试卷汇编6(总分：60.00，做题时间：90分钟)一、单项选择题(总题数：6，分数：12.00)1.有n个顶点、e条边的图G采用邻接表存储，则拓扑排序算法的时间复杂度为( )。

【南京理工大学2005一、2(1分)】（分数：2.00）A.O(n)B.O(n+e)C.O(n * e)D.O(n 2 )2.在下列网中，( )是边不带权值的图。

【华南理工大学2007】（分数：2.00）A.邮电图B.AOV网C.公路网D.AOE网3.关键路径是AOE网中( )。

【中南大学2003一、10(1分)】（分数：2.00）A.从始点到终点的最短路径B.从始点到终点的最长路径C.从始点到终点的边数最多的路径D.从始点到终点的边数最少的路径4.下面关于求关键路径的说法不正确的是( )。

【南京理工大学1998一、12(2分)】（分数：2.00）A.求关键路径是以拓扑排序为基础的B.一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C.一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D.关键活动一定位于关键路径上5.下列关于AOE网的叙述中，不正确的是( )。

【北方交通大学1999一、7(3分)】【北京工业大学1999一、1(2分)】【哈尔滨工业大学2004二、3(1分)】（分数：2.00）A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动若提前完成，那么整个工程将会提前完成6.下列有关图的说法错误的是( )。

【中南大学2003二、19(1分)】（分数：2.00）A.在有向图中，出度为0的结点称为叶子B.用邻接矩阵表示图，容易判断任意两个结点之间是否有边相连，并求得各结点的度C.按深度方向遍历图和先根次序遍历树类似，得到的结果是唯一的D.若有向图G中从结点Vi到结点Vj有一条路径，则在图G的结点的线性序列中结点V i必在结点V j之前的话，则称为一个拓扑序列二、填空题(总题数：10，分数：20.00)7.若一个具有n个顶点、e条边的无向图是一个森林，则该森林中必有__________棵树。

计算机专业基础综合数据结构（排序）历年真题试卷汇编6(总分108,考试时间90分钟)1. 单项选择题1. 某内部排序方法的稳定性是指____。

【南京理工大学1997年】A. 该排序算法不允许有相同的关键字记录B. 该排序算法允许有相同的关键字记录C. 平均时间为O(nlogn)的排序方法D. 以上都不对2. 若要求尽可能快地对序列进行稳定的排序，则应选____。

【北京邮电大学2001年】A. 快速排序B. 归并排序C. 冒泡排序D. 根排序3. 下列排序方法中，____是稳定的排序方法。

【北方交通大学2001】A. 直接选择排序B. 二分法插入排序C. 希尔排序D. 快速排序4. 对有n个记录的表做直接插入排序，在最好情况下，需比较____次关键字。

【华中科技大学2006年】A. n-1B. n+1C. n／2D. n(n-1)／25. 对n个不同的数据利用冒泡法从小到大排序，在下列哪种情况下元素交换的次数最多____。

【北京交通大学2007年】A. 从大到小排列好的B. 从小到大排列好的C. 元素无序D. 元素基本有序6. 采用简单选择排序，比较次数与移动次数分别为____。

【南京理工大学2000年】A. O(n)，O(10gn)B. O(logn)，O(n*n)C. O(n*n)，O(n)D. O(nlogn)，O(n)7. 希尔排序属于____。

【太原科技大学2006年】A. 插入排序B. 交换排序C. 选择排序D. 归并排序8. 对序列{15，9，7，8，20，一1，4}用希尔排序方法排序，经一趟后序列变为{15，一1，4，8，20，9，7}则该次采用的增量是____。

【南京理工大学1999年】A. 1B. 4C. 3D. 29. 有些排序算法在每趟排序过程中，都会有一个元素被放置到其最终位置上，下列算法不会出现此种情况的是____。

【北京交通大学2005年】A. 希尔排序B. 堆排序C. 冒泡排序D. 快速排序10. 从未排序序列中选择一个元素，该元素将当前参加排序的那些元素分成前后两个部分，前一部分中所有元素都小于等于所选元素，后一部分中所有元素都大于等于所选元素，而所选元素处在排序的最终位置。

计算机专业基础综合数据结构（树与二叉树）-试卷2(总分：64.00，做题时间：90分钟)一、单项选择题(总题数：23，分数：46.00)1.单项选择题1-40小题。

下列每题给出的四个选项中，只有一个选项是最符合题目要求的。

（分数：2.00）__________________________________________________________________________________________解析：2.设树T的度为4，其中度为1、2、3和4的结点个数分别为4、1、1、1，则T中的叶子数为( )。

（分数：2.00）A.10B.11C.9D.7 √解析：解析：根据题中条件可知，1×4+2×1+3+4+1=4+1+1+1+n 0，由此可以得出：n 0=1×4+2×1+3+4+1一(4+1+1+1)=14—7=7.3.用下列元素序列(22，8，62，35，48)构造平衡二叉树，当插入( )时，会出现不平衡的现象。

（分数：2.00）A.22B.35C.48 √D.6248后，首次出现不平衡子树，虚线框内即为最小不平衡子树。

4.下面的算法实现了将二叉树中每一个结点的左右子树互换。

addQ(Q，bt)为进队的函数，delQ(Q)为出队的函数，empty(Q)为判别队列是否为空的函数，空白处应填的内容是( )。

typedef struct node{ int data；struct node*lchild，*rchild；}btnode；void exchange(btnode*bt){ btnode*p，*q；if(bt){ addQ(Q，bt)；while(!EMPTY(Q)){ p=delQ(Q)；q=p-＞rchild；p一＞rchild=p一＞lchild；( (1) )=q；if(p->lchild) ( (2) )； if(p-＞rchild)addQ(Q，p-＞rchild)； } }}（分数：2.00）A.p-＞lchild，delQ(Q，p一＞lchild)B.p-＞rchild，delQ(Q，p-＞lchild)C.p-＞lchild，addQ(Q，p-＞lchild) √D.p-＞rchild，addQ(Q，p-＞lchild)解析：5.已知有一棵二叉树，其高度为n，并且有且只有n个结点，那么二叉树的树形有( )种。