【HBU】數據結構樹練習題

• 2019 年 11 月 8 日
• 筆記

版權聲明：本文為部落客原創文章，遵循 CC 4.0 BY-SA 版權協議，轉載請附上原文出處鏈接和本聲明。

本文鏈接：https://blog.csdn.net/shiliang97/article/details/102566167

4-1

某二叉樹的前序和後序遍歷序列正好相反，則該二叉樹一定是 (4分)

1. 空或只有一個結點
2. 高度等於其結點數
3. 任一結點無左孩子
4. 任一結點無右孩子

作者: DS課程組

單位: 浙江大學

4-2

已知一棵二叉樹的先序遍歷結果是ABC，則以下哪個序列是不可能的中序遍歷結果： (4分)

1. ABC
2. BAC
3. CBA
4. CAB

作者: DS課程組

單位: 浙江大學

4-3

如果二叉樹的後序遍歷結果是FDEBGCA，中序遍歷結果是FDBEACG，那麼該二叉樹的前序遍歷結果是什麼？ (4分)

1. ABCDEFG
2. ABDFEGC
3. ABDFECG
4. ABDEFCG

作者: DS課程組

單位: 浙江大學

4-4

給定二叉樹如下圖所示。設N代表二叉樹的根，L代表根結點的左子樹，R代表根結點的右子樹。若遍歷後的結點序列為3、1、7、5、6、2、4，則其遍歷方式是： (4分)

1. NRL
2. RNL
3. LRN
4. RLN

作者: DS課程組

單位: 浙江大學

4-5

在下述結論中，正確的是： (4分)

①只有一個結點的二叉樹的度為0;

②二叉樹的度為2；

③二叉樹的左右子樹可任意交換；

④深度為K的完全二叉樹的結點個數小於或等於深度相同的滿二叉樹。

1. ①④
2. ②④
3. ①②③
4. ②③④

作者: DS課程組

單位: 浙江大學

4-6

任何一棵二叉樹的葉結點在先序、中序和後序遍歷序列中的相對次序 (4分)

1. 發生改變
2. 不發生改變
3. 不能確定
4. 以上都不對

作者: DS課程組

單位: 浙江大學

4-7

按照二叉樹的定義，具有3個結點的二叉樹有幾種？ (4分)

1. 3
2. 4
3. 5
4. 6

作者: DS課程組

單位: 浙江大學

4-8

下面的函數PreOrderPrintLeaves(BinTree BT)按前序遍歷的順序列印出二叉樹BT的所有葉子結點。則下列哪條表達式應被填在空中？(4分)

void PreOrderPrintLeaves( BinTree BT )  {  if (BT)  {        if (___________________)  printf("  %d", BT->Data);        PreOrderPrintLeaves( BT->Left  );        PreOrderPrintLeaves( BT->Right );     }  }

1. BT->Data != 0
2. !BT->Right
3. !BT->Left
4. !(BT->Left || BT->Right)

作者: 何欽銘

單位: 浙江大學

4-9

要使一棵非空二叉樹的先序序列與中序序列相同，其所有非葉結點須滿足的條件是：(4分)

1. 只有左子樹
2. 只有右子樹
3. 結點的度均為1
4. 結點的度均為2

作者: 考研試卷

單位: 浙江大學

4-10

若將一棵樹 T 轉化為對應的二叉樹 BT，則下列對 BT 的遍歷中，其遍歷序列與 T 的後根遍歷序列相同的是：(4分)

1. 先序遍歷
2. 中序遍歷
3. 後序遍歷
4. 按層遍歷

作者: 考研真題

單位: 浙江大學