2025年数据结构树图测试题(1) .pdfVIP

以铜为镜，可以正衣冠；以古为镜，可以知兴替；以人为镜，可以明得失。——《旧唐书·魏征列传》

数据结构树图测试题（1）

⼀、填空题

1.⼀完全⼆叉树共有500个结点，则在该⼆叉树中有个度为2的结点。

2.设某⼆叉树的前序遍历序列为:ABCDEFGHI，中序遍历序列为:BCAEDGHFI，则该⼆叉树的后序遍历序列是。

3.对于⼀个稀疏图，在求该图对应的最⼩⽣成树时，Prim算法和kruskal算法哪⼀个算法效率更⾼。

4.对于⼀个n个结点的满⼆叉树，假设该树有m个树叶，深度为h，则h=。

5.设⾼度为h的⼆叉树上只有度为0和度为2的结点，则此类⼆叉树中所包含的结点数⾄少为，⾄多为。

6.⼀棵有n个结点的满⼆叉树有__个叶⼦，该满⼆叉树的深度为___。

7.设F是由T1,T2,T3三棵树组成的森林,与F对应的⼆叉树为B,已知T1,T2,T3的结点数分别为n1,n2和n3则⼆叉

树B的左⼦树中有___个结点。8.⼀颗含有101个结点的完全⼆叉树存储在数组A[1..101]中，若A[k]为叶⼦结点，则k的最⼩

值是。9.⼀颗深度为h的完全⼆叉树上的结点总数最⼩值为，最⼤值为。

⼆、选择题

1.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1，则T中的叶⼦数为（）。

A．5

B．6

C．7

D．8

1.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（）。

A．G中有弧

B．G中有⼀条从Vi到Vj的路径

C．G中没有弧

D．G中有⼀条从Vj到Vi的路径1.若完全⼆叉树的结点总数为偶数，则度为1的结点有()个。

A.0

B.1

C.2

D.不确定

1.已知⼀棵⼆叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（）。

A．CBEFDA

B．FEDCBA

C．CBEDFA

D．不定1.下述编码中哪⼀个不是前缀码（）。

A．（00，01，10，11）

B．（0，1，00，11）

C．（0，10，110，111）

D．（1，01，000，001）1.n个顶点的有向图G最多有()条弧。

去留无意，闲看庭前花开花落；宠辱不惊，漫随天外云卷云舒。——《幽窗小记》

A.0B．n(n-1)C.nD．n(n-1)/2

1.下列线索⼆叉树中（⽤虚线表⽰线索）

1.给定⼆叉树图所⽰.设N代表⼆叉树的根,L代表根结点的左⼦树,R代表根结点的右⼦树.若遍历后的结点序列为3,1,7,5,6,2,4,

则其遍历⽅式是

(A)LNR(B)NRL(C)RLN

(D)RNL

5.在⼀颗度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点。则树T的叶结点个数是

A.41

B.82

C.113

D.1226.对n（n≥2）个权值均不相同的字符构成的哈夫曼树，关于该树的叙述，错误的是A.该树⼀定是⼀颗完全⼆叉树B.

树中⼀定没有度为1的结点

C.树中两个权值最⼩的结点⼀定是兄弟结点

D.树中任⼀⾮叶结点的权值⼀定不⼩于下⼀层任⼀结点的权值7.对于⽆向图G=（V,E）中含7个顶点，若保证图G在任何情

况下都是连通的，则需要的边数最少是A.6B.15C.16D.218.已知⼀棵完全⼆叉树的第6层(设根为第1层)有8个叶结点,则完

全⼆叉树的结点个数最多是

博学之，审问之，慎思之，明辨之，笃行之。——《礼记》

NULNUULL

ULL

N

(A)39(B)52(C)111(D)119

8.对于下图进⾏拓扑排序，可以得到不同的拓扑排序序列的个数是

A.4

B.3

C.2

D.1

8.将森林转换为对应的⼆叉树,若在⼆叉树中,结点u是结点v的⽗结点的⽗结点,

中,u和v可能具有的关系是

Ⅰ.⽗⼦关系Ⅱ.兄弟关系Ⅲ.u的⽗结点与v的⽗结点是兄弟关系

(A)只有Ⅱ(B)Ⅰ和Ⅱ(C)Ⅰ和Ⅲ(D)Ⅰ、Ⅱ和Ⅲ

8.下列关于⽆向连通图特性的叙述中,正确的是

Ⅰ.所有顶点的度log

2

p之和为偶数Ⅱ.边数⼤于顶点个数减1Ⅲ.⾄少有⼀个顶点的度为1

(A)只有Ⅰ(B)只有Ⅱ(C)Ⅰ和Ⅱ(D)Ⅰ和Ⅲ

8.设结点x和y是⼆叉树中任意的两个结点，在该⼆叉树的先序遍历序列中x在y之前，在其后序遍历序列中x在y之后，则z和y

的关系是（）。

A）x是y的左兄弟B）x是y的右兄弟C）x是y