數據結構習題匯編

加*號的為選做題。

一、選擇題

1．數據結構中，與所使用的計算機無關的是數據的（）。

A．存儲結構B．物理結構C．邏輯結構D．物理和存儲結構

2．下面有關數據的存儲結構的敘述中，正確的是（）。

A．順序存儲方式只能用于存儲線性結構

B．順序存儲方式的優點是存儲密度大，且插入和刪除運算效率高

C．鏈表的每一個結點都恰好包含一個指針

D．棧和隊列的存儲方式既可以順序存儲，也可以采用鏈式存儲方式

3．下列敘述中正確的是（）。

A．線性表是線性結構B．棧與隊列是非線性結構

C．線性鏈表是非線性結構D．隊列是后進先出的線性表

4．鏈表不具有的特點是（）。

A．可隨機訪問任一元素B．插入和刪除不需要移動元素

C．不必事先估計存儲空間D．所需空間與線性表長度成正比

5．棧底至棧頂依次存放元素A、B、C、D，在第五個元素E入棧前，棧中元素可以出棧，則出棧序列可能是（）。

A．ABCED B．DBCEA C．CDABE D．DCBEA

6．若進棧序列為1，2，3，4，則（）不可能是出棧序列。

A．1，2，3，4 B．4，3，2，1 C．3，4，2，1 D．2，4，3，1

7．在深度為8的滿二叉樹中,葉子結點的個數為（）。

A．63 B．64 C．127 D．128

*8．已知二叉樹后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是（）。A．cedba B．acbed C．decab D．deabc

二、填空題

1．棧的基本運算有三種：入棧、退棧和【1】。

2．對長度為N的線性表進行順序查找，當查找失敗時比較次數為【2】。

3．在長度為N的線性表中進行二分查找，在最快的情況下，需要比較的次數為【3】。

4．設待排數據元素的關鍵字為（67，24，14，22，33，15，11，15），用選擇法將其按升序排序，需要比較的次數為【4】。

5．某二叉樹中度為2的結點有12個，則該二叉樹中有【5】個葉子結點。

6．設一棵二叉樹中有3個葉子結點，有6個度為1的結點，則該二叉樹中總的結點數為【6】個。

*7．在深度為5的完全二叉樹中，度為2的結點數最多為【7】個。

8．對下列二叉樹進行前序、中序和后序遍歷的結果分別是【8】、【9】和【10】。