2017年9月計算機等級考試將於9月23日-26日舉行，目前處於緊張的備考階段。下面是小編分享的2017年9月計算機二級《公共基礎》練習試題，歡迎大家練習！
一、選擇題
(1)演算法的時間複雜度是指（ ）。
A．執行演算法程式所需要的時間
B．演算法程式的長度
C．演算法執行過程中所需要的基本運算次數
D．演算法程式中的指令條數
(2)下列敘述中正確的是（ ）。
A．線性連結串列是線性表的鏈式儲存結構
B．棧與佇列是非線性結構
C．雙向連結串列是非線性結構
D．只有根結點的二叉樹是線性結構
(3)有下列二叉樹，對此二叉樹進行前序遍歷的結果為（ ）。
A．ACBEDGFH
B．ABDGCEHF
C．HGFEDCBA
D．ABCDEFGH
(4)某二叉樹共有60個葉子結點與50個度為1的結點，則該二叉樹中的總結點數為（ ）。
A．148
B．169
C．182
D．198
(5)下列敘述中正確的是（ ）。
A．一個邏輯資料結構只能有一種儲存結構
B．邏輯結構屬於線性結構，儲存結構屬於非線性結構
C．一個邏輯資料結構可以有多種儲存結構，且各種儲存結構不影響資料處理的效率
D．一個邏輯資料結構可以有多種儲存結構，且各種儲存結構影響資料處理的效率
(6)有下列二叉樹，對此二叉樹進行中序遍歷的結果為（ ）。
A．BDYEACFXZ
B．DYBEAFCZX
C．ABCDEFXYZ
D．ABDYECFXZ
(7)已知一個有序線性表為(13，18，24，35，47，50，62，83，90，115，134)，當用二分法查詢其中值為90的元素時，查詢成功的比較次數為（ ）。
A．1
B．2
C．3
D．9
(8)下列敘述中錯誤的是（ ）。
A．線性表是由11個元素組成的一個有限序列
B．線性表是一種線性結構
C．線性表的所有結點有且僅有一個前件和後件
D．線性表可以是空表
(9)棧S最多能容納4個元素，現有6個元素按A、B、C、D、E、F的順序進棧，則（ ）不是可能的出棧序列。
A．C、B、E、D、A、F
B．C、D、B、F、E、A
C．A、D、E、C、B、F
D．A、F、E、D、C、B
(10)兩個或兩個以上模組之間聯絡的緊密程度稱為（ ）。
A．耦合性
B．內聚性
C．複雜性
D．資料傳輸特性
(11)在下列關於二叉樹的敘述中，正確的一項是（ ）。
A．在二叉樹中，任何一個結點的度都是2
B．二叉樹的度為2
C．在二叉樹中，至少有一個結點的度為2
D．一棵二叉樹的度可以小於2
(12)待排序的關鍵碼序列為(33，18，9，25，67，82，53，95，12，70)，如要按關鍵碼值遞增的順序排序，並採取以第一個關鍵碼為基準元素的快速排序法，則第一趟排序後關鍵碼33被放到第（ ）個位置。
A．3
B．5
C．7
D．9
(13)設根結點的層次為0，高度為K的二叉樹的最大結點數為（ ）個。
A．2K
B．2K+l-1
C．2K+1
D．2K+l+1
(14)演算法的有窮性是指（ ）。
A．演算法程式的長度是有限的
B．演算法程式所處理的資料量是有限的
C．演算法程式的執行時間是有限的
D．演算法只能被有限的使用者使用
(15)以下描述中，不是線性表順序儲存結構特徵的是（ ）。
A．不便於插入和刪除
B．需要連續的儲存空間
C．可隨機訪問
D．需另外開闢空間來儲存元素之間的'關係
(16)按照“先進後出”原則組織資料的資料結構是（ ）。
A．佇列
B．棧
C．雙向連結串列
D．二叉樹
(17)已知一棵二叉樹的先根序列為ABCDEFK，中根序列為DGBAFCK，則結點的後根序列為（ ）。
A．ACFKDBG
B．GDBFKCA
C．KCFAGDB
D．ABCDFKG
(18)深度為6的滿二叉樹中，度為2的結點個數為（ ）。
A．31
B．32
C．63
D．64
(19)下列資料結構中，能用二分法進行查詢的是（ ）。
A．順序儲存的有序線性表
B．線性連結串列
C．二叉連結串列
D．有序線性表
(20)以下關於順序儲存結構的敘述中，（ ）是正確的。
A．每個結點中至少包含一個指標域
B．邏輯上相鄰的結點物理上不必鄰接
C．可用於棧、佇列、樹等邏輯結構的儲存表示
D．插入、刪除運算操作不方便
(21)有3個結點的二叉樹有（ ）。
A．2種形態
B．4種形態
C．7種形態
D．5種形態
(22)在一棵二叉樹的前序遍歷、中序遍歷、後序遍歷所產生的序列中，所有葉結點的先後順序（ ）。
A．都不相同
B．完全相同
C．前序和中序相同，而與後序不同
D．中序和後序相同，而與前序不同
(23)下列敘述中正確的是（ ）。
A．線性連結串列的各元素在儲存空間中的位置必須是連續的
B．線性連結串列的頭元素一定儲存在其他元素的前面
C．線性連結串列中的各元素在儲存空間中的位置不一定是連續的，但表頭元素一定儲存在其他元素的前面
D．線性連結串列中的各元素在儲存空間中的位置不一定是連續的，且各元素的儲存順序也是任意的
(24)線性表常採用的兩種儲存結構是（ ）。
A．順序儲存結構和鏈式儲存結構
B．雜湊方法和索引方式
C．連結串列儲存結構和陣列
D．線性儲存結構和非線性儲存結構
(25)設棧S和佇列Q的初始狀態為空，元素a、b、c、d、e和f依次通過棧S，一個元素出棧後即進入佇列O，若6個元素出隊的順序是b、d、c、f、e、a，則棧s的容量至少應該是（ ）。
A．6
B．4
C．3
D．2
(26)對於長度為n的線性表，在最壞情況下，下列各種排序法所對應的比較次數中正確的是（ ）。
A．氣泡排序為n／2
B．氣泡排序為n
C．快速排序為n
D．快速排序為n(n一1)／2
(27)實現演算法所需要的儲存單元的多少稱為（ ）。
A．可實現性
B．空間複雜度
C．時間複雜度
D．困難度
(28)以下關於棧的描述中，錯誤的是（ ）。
A．棧是先進後出的線性表
B．棧只能順序儲存
C．棧具有記憶作用
D．對棧的插入與刪除操作中，不需要改變棧底指標
(29)下面資料結構中，屬於非線性的是（ ）。
A．線性表
B．佇列
C．樹
D．棧
(30)下列資料結構中，能用二分法進行查詢的是（ ）。
A．順序儲存的有序線性表
B．線性連結串列
C．二叉連結串列
D．有序線性連結串列
答案：
(1)C (2)A (3)B (4)B (5)D (6)B (7)B (8)C (9)D (10)A
(11)B (12)B (13)B (14)C (15)D (16)B (17)B (18)A (19)A (20)D
(21)D (22)B (23)D (24)A (25)C (26)D (27)B (28)B (29)C (30)A
二、填空題
1．順序儲存方法是把邏輯上相鄰的結點儲存在物理位置______的儲存單元中。
答：相鄰
2．資料結構包括資料的邏輯結構、資料的______以及對資料的操作運算。
答：儲存結構
3．演算法的基本特徵是可行性、確定性、______和擁有足夠的情報。
答：有窮性
4．實現演算法所需的儲存單元多少和演算法的工作量大小分別稱為演算法的______。
答案：空間複雜度和時間複雜度
5．資料的邏輯結構在計算機儲存空間中的存放形式稱為資料的______。
答案：儲存結構
6．資料結構包括資料的______結構和資料的儲存結構。
答：邏輯
7．資料模型按不同的應用層次分為三種類型，它們是______資料模型、邏輯資料模型和物理資料模型。
答：概念
8．在一個容量為15的迴圈佇列中，若頭指標front=6，尾指標rear=9，則該迴圈佇列中有______個元素。
答案：3
9．棧的基本運算有三種：入棧、退棧和______。
答案：讀棧頂元素#讀棧頂的元素#讀出棧頂元素
10．演算法的複雜度主要包括______複雜度和空間複雜度。
答：時間
11．若串s="Program"，則其子串的數目是______。
答：29
12．設一棵完全二叉樹共有700個結點,則在該二叉樹中有______個葉子結點。
答案：350
13．在先左後右的原則下，根據訪問根結點的次序，二叉樹的遍歷可以分為三種：前序遍歷、______遍歷和後序遍歷。
答：中序
14．設一棵完全二叉樹共有500個結點，則在該二叉樹中有______個葉子結點。
答：250
答案：DEBFC
