公共基礎知識考題分析和歷年真題
——已按課程分類彙總
第一章資料結構 1
考點1：棧和佇列的特點 1
考點2：線性表(鍊錶)特點 2
考點3：二叉樹特點(遍歷、葉子數、深度) 3
考點4：演算法的複雜度 5
考點5：綜合 6
第二章程式設計基礎部分： 6
第三章軟體工程部分： 8
考點一：軟體工程知識概念的理解 8
考點二：軟體生命週期 9
考點三：軟體測試 10
考點四：軟體除錯 10
第四章資料庫部分： 11
考點一：資料庫的理解 11
考點二：主鍵/外來鍵/鍵值 11
考點三：模式語言和模式的理解 12
考點四：資料模型（e-r圖、層次/網狀/關係模型） 13
考點五：關係和關係操作 13
考點六：資料庫設計 15
第一章資料結構
考點1：棧和佇列的特點
典型題例：
(1)棧和佇列的共同特點是 d（棧和佇列的特點）
a)都是先進先出 b)都是先進後出
c)只允許在端點處插入和刪除元素 d)沒有共同點
解析:棧和佇列都是一種特殊的操作受限的線性表,只允許在端點處進行插入和刪除.二者的區別是:
棧只允許在表的一端進行插入或刪除操作,是一種"後進先出"的線性表;而佇列只允許在表的一端進行插入操作,在另一端進行刪除操作,是一種"先進先出"的線性表.所以沒有共同點
(2)下列關於棧敘述正確的是(棧)(11.3)a
a)棧頂元素最先能被刪除 b)棧頂元素最後才能被刪除
c)棧底元素永遠不能被刪除 d)以上三種說法都不對
(3)下列敘述中正確的是(棧)(10.9) c
a）在棧中，棧中元素隨棧底指標與棧頂指標的變化而動態變化
b）在棧中，棧頂指標不變，棧中元素隨棧底指標的變化而動態變化
c）在棧中，棧底指標不變，棧中元素隨棧頂指標的變化而動態變化
d）上述三種說法都不對
(4)如果進棧序列為e1,e2,e3,e4,則可能的出棧序列是b（棧進出順序）
a)e3,e1,e4,e2 b)e2,e4,e3,e1 c)e3,e4,e1,e2 d)任意順序
解析: 由棧"後進先出"的特點可知:a)中e1不可能比e2先出,c)中e3不可能比e4先出,且e1不可能比e2先出,d)中棧是先進後出的,所以不可能是任意順序.
b)中出棧過程如圖所示:
(5)乙個棧的初始狀態為空。首先將元素5,4,3,2,1依次入棧，然後退棧一次，再將元素 a,b,c,d依次入棧，之後將所有元素全部退棧，則所有元素退棧（包括中間退棧的元素）的順序為【1】(棧)(10.9) 1dcba2345
(6) (1)乙個佇列的初始狀態為空，先將元素a,cb,c,d,e,f,5,4,3,2,1依次入隊，然後再依次退隊，則元素退隊的順序為_abcdef__54321__。(佇列)(10.3)
(7)設某迴圈列隊的容量為50，如果頭指標front=45（指向隊頭元素的前一位置），尾指標rear=10（指向隊尾元素），則該迴圈佇列中共有___15__個元素。(佇列)(10.3)
解析：迴圈佇列中元素個數：尾指標減去頭指標，若為負值，再加上佇列容量。n=10-45+50=15.
1、下列敘述中正確的是（ ）。（2012.3）a
a．迴圈佇列是佇列的一種順序儲存結構 b．迴圈佇列是佇列的一種鏈式儲存結構
c．迴圈佇列是非線性結構d．迴圈佇列是一直邏輯結構
2、下列敘述中正確的是（ ）。（2012.3）d
a．棧是一種先進先出的線性表b．佇列是一種後進先出的線性表
c．棧和佇列都是非線性結構d．以上三種說法都不對
1、下列敘述中正確的是（ ）。（2012.3）a(資料結構佇列)
a．迴圈佇列是佇列的一種順序儲存結構 b．迴圈佇列是佇列的一種鏈式儲存結構
c．迴圈佇列是非線性結構d．迴圈佇列是一直邏輯結構
2、下列敘述中正確的是（ ）。（2012.3）d（資料結構佇列棧）
a．棧是一種先進先出的線性表b．佇列是一種後進先出的線性表
c．棧和佇列都是非線性結構d．以上三種說法都不對
2、設迴圈佇列的儲存空間為q(1:30),初始狀態為front=rear=30。現經過一系列入隊與退隊運算後，front=16，rear=15，則迴圈佇列中有（ ）個元素。
（2012.3）(資料結構迴圈佇列) 29
考點2：線性表(鍊錶)特點
典型題例：
(1)鍊錶不具有的特點是 b（鍊錶的特點）
a)不必事先估計儲存空間 b)可隨機訪問任一元素
c)插入刪除不需要移動元素 d)所需空間與線性表長度成正比
解析: 鍊錶採用的是鏈式儲存結構,它克服了順序儲存結構的缺點:它的結點空間可以動態申請和釋放;它的資料元素的邏輯次序靠結點的指標來指示,不需要移動資料元素.
但是鏈式儲存結構也有不足之處:① 每個結點中的指標域需額外占用儲存空間;② 鏈式儲存結構是一種非隨機儲存結構.
(2)用鍊錶表示線性表的優點是(鍊錶)c
a)便於隨機訪問 b)花費的儲存空間較順序儲存少
c)便於插入和刪除操作 d)資料元素的物理順序與邏輯順序相同
解析: 鏈式儲存結構克服了順序儲存結構的缺點:它的結點空間可以動態申請和釋放;它的資料元素的邏輯次序靠結點的指標來指示,不需要移動資料元素.
故鏈式儲存結構下的線性表便於插入和刪除操作.
(3) 下列敘述中正確的是 a(鍊錶)(10.3)
a)對長度為n的有序鍊錶進行查詢，最壞情況下需要的比較次數為n
b)對長度為n的有序鍊錶進行對分查詢，最壞情況下需要的比較次數為(n/2)
c)對長度為n的有序鍊錶進行對分查詢，最壞情況下需要的比較次數為(log2n)
d) 對長度為n的有序鍊錶進行對分查詢，最壞情況下需要的比較次數為(n log2n)
(4)資料結構分為邏輯結構與儲存結構,線性鍊錶屬於 【1】. 答案：儲存結構
解析: 資料的邏輯結構是指反映資料元素之間邏輯關係的資料結構;資料的儲存結構是指資料的邏輯結構在計算機儲存空間中的存放形式.在資料的儲存結構中,不僅要存放各資料元素的資訊,還需要存放各資料元素之間的前後件關係的資訊.
(5)順序儲存方法是把邏輯上相鄰的結點儲存在物理位置 【2】 的儲存單元中. 答案：相鄰
解析: 常用的儲存表示方法有4種,順序儲存,鏈式儲存,索引儲存,雜湊儲存.其中,順序儲存方法是把邏輯上相鄰的結點儲存在物理位置也相鄰的儲存單元中.
(6)下列敘述中正確的是(線性表儲存)(10.9) b
a）線性表的鏈式儲存結構與順序儲存結構所需要的儲存空間是相同的
b）線性表的鏈式儲存結構所需要的儲存空間一般要多於順序儲存結構
c）線性表的鏈式儲存結構所需要的儲存空間一般要少於順序儲存結構
d）上述三種說法都不對
(2)下列關於線性鍊錶的敘述中，正確的是11.9）c
a)各個資料結點的儲存空間可以不連續，但它們的儲存順序與邏輯順序必須一致
b)各個資料結點的儲存順序與邏輯順序或以不一致，但它們的儲存空間必須連續
c)進行插入與刪除時，不需要移動表中的元素
d)以上三種說法都不對
(1)資料結構分為線性結構和非線性結構，帶鏈的棧屬於【1】。（11.9）線性結構
(2)在長度為n的順序儲存的線性表中插入乙個元素，最壞情況下需要移動表中【2】個元素 。（11.9）n
1、將長度為n的順序儲存**性表中刪除乙個元素，最壞情況下需要移動表中的元素個數為（ ）。（2012.3）(資料結構線性表) n-1
考點3：二叉樹特點(遍歷、葉子數、深度)
典型題例：
(1)設二叉數如下：
ab c
df e g h
對該二叉樹進行後序遍歷的結果為edbghfca(樹)(10.3)
(2)已知一棵二叉樹前序遍歷和中序遍歷分別為abdegcfh和dbgeachf,則該二叉樹的後序遍歷為b（樹的遍歷）
a b c
d e f
g h
a)gedhfbca b)dgebhfca c)abcdefgh d)acbfedhg
解析: 利用前序和中序遍歷的方法可以確定二叉樹的結構,具體步驟如下:① 前序遍歷的第乙個結點a為樹的根結點;② 中序遍歷中a的左邊的結點為a的左子樹,a右邊的結點為a的右子樹;③ 再分別對a的左右子樹進行上述兩步處理,直到每個結點都找到正確的位置.
(3)已知二叉樹後序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷序列是 d （樹遍歷）ce
d ba
公共基礎知識彙總
第一章資料結構與演算法 1.1 演算法 是指解題方 而完整的描述。演算法不等於程式，也不等計算機方法，程式的編制不可能優於演算法的設計。演算法的特徵包括 1 可行性 2 確定性，演算法中每一步驟都必須有明確定義，不充許有模稜兩可的解釋，不允許有多義性。3 有窮性，演算法必須能在有限的時間內做完，包括...
公共基礎知識考點彙總
1 公文寫作的語言運用 公文語言的特點 莊重 準確 樸實 精練 嚴謹 規範。公文中需用歷史年號時，要先標出公曆年份，再注歷史年號並加圓括號，如1912年 元年 數量表示時，表示增加時用倍數或分數，表示減少時只能用分數。2 各種文種的撰寫 1 規範性公文。規範性公文一般包括檔案標題 發布或通過或批准的...
2019公共基礎知識全面彙總
2011公共基礎知識教材考點總結 第一部分馬克思主義哲學 1 哲學 世界觀 方 哲學，是系統化 理論化的世界觀。方 是人們認識世界 改造世界的根本方法。2 哲學的基本問題 哲學的基本問題，包括兩個方面，兩個層次。第一方面，是關於物質和意識誰是第一性 誰是第二性的問題，是劃分唯物主義和唯心主義的根本依...