公共基礎知識歷年真題2009.9-2011.9
第1章資料結構與演算法
1.1.1演算法的基本概念
考點：演算法的概念及基本特徵
【2023年9月】(1)下列敘述中正確的是
a)演算法就是程式b)設計演算法時只需考慮資料結構的設計
c)設計演算法時只需考慮結果的可靠性d)以上三種說法都不對
答案：d
解析：演算法是指解題方案準確而完整的描述。演算法是一組嚴謹地定義運算順序的規則，並且每乙個規則都是有效的，且是明確的，此順序半形在有限的次數下終止。
演算法不等於程式，也不等於計算方法。通常程式的編制不可能優於演算法的設計，所以a答案是錯的。
演算法具有兩個基本要素：一是對資料物件的運算和操作，二是演算法的控制結構。所以b和c答案都不全面。
1.1.2演算法的複雜度
考點：時間複雜度
【2023年3月】(2)演算法的時間複雜度是指
a)演算法的執行時間
b)演算法所處理的資料量
c)演算法程式中的語句或指令條數
d)演算法在執行過程中所需要的基本運算次數
答案：d
解析：演算法的時間複雜度是指執行演算法所需要的計算工作量。演算法的工作量用演算法所執行的基本次數來度量，而演算法所執行的基本次數與問題的規模有關（即演算法所執行的基本次數是問題規模的函式）。
而對於乙個固定的規模，演算法所執行的基本次數還與特定的輸入有關。
考點：空間複雜度
【2023年9月】（4）演算法的空間複雜度是指
a）演算法在執行過程中所需要的計算機儲存空間
b）演算法所處理的資料量
c）演算法程式中的語句或指令條數
d）演算法在執行過程中所需要的臨時工作單元數
答案：a
解析：空間複雜度指執行這個演算法所需要的記憶體空間。乙個演算法所占用的儲存空間包括演算法程式所佔的空間、輸入的初始資料所占用的儲存空間以及演算法執行過程中所需要的額外空間。
額外空間包括演算法程式執行過程中的工作單元以及某種資料結構所需要的附加儲存空間。
1.2.3線性結構與非線性結構
考點：線性結構與非線性結構
【2023年9月】（1）下列資料結構中，屬於非線性結構的是
a）迴圈結構 b）帶鏈佇列 c）二叉樹 d）帶鏈棧
答案：c
解析：資料結構分為線性結構和非線性結構。如果乙個非空資料結構滿足以下兩點：
1.有且只有乙個根結點；2.每個結點最多有乙個前件，也最多有乙個後件結點，則該資料結構為線性結構。
習題演練
【2023年3月】（2）下列敘述中正確的是
a）有乙個以上根結點的資料結構不一定是非線性結構
b）只有乙個根結點的資料結構不一定是線性結構
c）迴圈鍊錶是非線性結構
d）雙向鍊錶是非線性結構
答案：b
【2023年9月】(1)資料結構分為線性結構和非線性結構，帶鏈的棧屬於 【1】 。
答案：線性結構
1.3.3順序表的插入運算
【2023年9月】(2)在長度為n的順序儲存的線性表中插入乙個元素，最壞情況下需要移動表中 【2】 個元素。
答案：n
解析：在一般情況下，要在第i(1<=i<=n)個元素之前插入乙個新元素時，首先要從最後乙個元素開始，直到第i個元素之間共n-i+1個元素依次向後移動乙個位置，移動結束後，第i個位置就被空出，然後將新元素插入到第i項。插入結束後，線性表的長度就增加了1。
顯然，如果插入運算**性表的末尾進行，則只要在表的末尾增加乙個新元素即可，不需要移動表中的元素；如果要在第1個元素前插入乙個新元素（即最壞情況下），則需要移動表中所有的元素；在平均情況下，要**性表中插入乙個新元素，需要移動表中一半的元素。
1.4.1棧及其基本運算
考點：棧
【2023年9月】（2）下列資料結構中，能夠按照「先進後出」原則訪問資料的是
a）迴圈佇列 b）棧c）佇列d）二叉樹
答案：b
解析：棧是一種特殊的線性表，其插入和刪除操作都只能**性表的一端進行。
在棧中，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的一端稱為棧底。
棧是按照「先進後出」或「後進先出」的原則來組織資料的。由此可以看出，棧具有記憶功能。
習題演練
【2023年9月】（1）乙個棧的初始狀態為空。首先將元素5，4，3，2，1 依次入棧，然後退棧一次，再將元素a,b,c,d依次入棧，之後將所有元素全部退棧，則所有元素退棧（包括中間退棧的元素）的順序為__【1】__。
答案：12345dcba
解析：對棧執行插入與刪除操作分別稱為入棧和退棧。而無論是入棧還是退棧操作都只能在棧頂端進行。
按照題意，先按5,4,3,2,1順序入棧，再依次出棧，所以出棧順序為1,2,3,4,5；接下來，再依次入棧,a,b,c,d，再依次出棧d,c,b,a。所以，題幹中所要求的總的出棧順序為1,2,3,4,5,d,c,b,a。
【2023年9月】（2）下列敘述中正確的是
a）在棧中，棧中元素隨棧底指標與棧頂指標的變化而動態變化
b）在棧中，棧頂指標不變，棧中元素隨棧底指標的變化而動態變化
c）在棧中，棧底指標不變，棧中元素隨棧頂指標的變化而動態變化
d）上述三種說法都不對
答案：c
解析：通常情況下，用指標top來表示棧頂的位置，用指標bottom來指向棧底。當棧執行入棧或退棧操作時，棧底指底不動，始終指向棧底元素，而棧頂指標則會動態地反映棧中元素的變化情況。
【2023年3月】（1）下列關於棧敘述正確的是
a) 棧頂元素最先能被刪除
b）棧頂元素最後才能被刪除
c）棧底元素永遠不能被刪除
d）以上三種說法都不對
答案：a
1.4.2佇列及其基本運算
考點：佇列
【2023年3月】(1)乙個佇列的初始狀態為空。現將元素a,b,c,d,e,f,5,4,3,2,1依次入隊，然後再依次退隊，則元素退隊的順序為 【1】 。
答案：a,b,c,d,e,f,54,3,2,1
解析：佇列是指允許在一端進行插入、而在另一端進行刪除的線性表，它按照「先進先出」或「後進後出」原則組織資料。對於佇列來講，總是把需要加入的元素插入到線性表的末尾，並總是從線性表的頭部取出（刪除）元素。
佇列中，允許插入的一端稱為隊尾，通常用乙個稱為尾指標（rear）的指標指向隊尾元素，即尾指標總是指向最後被插入元素。允許刪除的一端稱為排頭（也稱為隊頭），通常也用乙個排頭指標（front）指向排頭元素的前乙個位置。
往佇列的隊尾插入乙個元素稱為入隊運算；從佇列的排頭刪除乙個元素稱為退隊運算。
考點：迴圈佇列
【2023年9月】（3）對於迴圈佇列，下列敘述正確的是
a）隊頭指標是固定不變的
b）隊頭指標一定大於隊尾指標
c）隊頭指標一定小於隊尾指標
d）隊頭指標可以大於隊尾指標，也可以小於隊尾指標
答案：d
解析：所謂迴圈佇列，就是將佇列儲存空間的最後乙個位置繞到第乙個位置，形成邏輯上的環狀空間，供佇列迴圈使用。在迴圈佇列結構中，當儲存空間的最後乙個位置已被使用而再要進行入隊運算時，只要儲存空間的第乙個位置空閒，便可將元素加入到第乙個位置，即將儲存空間的第乙個位置作為隊尾。
在迴圈佇列中，用隊尾指標rear指向佇列中的隊尾元素，用排頭指標front 指向排頭元素的前乙個位置。
綜上所述，佇列儲存空間的乙個位置都可能成為隊頭指標指向的位置，而隊尾指標也可能指向任意乙個位置，所以隊頭指標可以大於隊尾指標，也可以小於隊尾指標。故所d。
習題演練
【2023年3月】(2)設某迴圈佇列的容量為50，如果頭指標front=45(指向隊頭元素的前一位置)，尾指標rear=10(指向隊尾元素)，則該迴圈佇列中共有 【2】 個元素。
答案：15
解析：對於容量為m的迴圈佇列，其初始狀態為空，即rear=front=m，如下圖所示：
每執行一次入隊運算，則隊尾指標就進一，當隊尾指標rear=m+1時，則置rear=1。
每執行一次退隊運算，排頭指標就進一，當排頭指標front=m+1時，則置front=1。
對於本題來講，迴圈佇列初始狀態為空，要滿足尾指標指向10，需要先入隊10個元素。而在這種情況下，無論如何執行退隊操作，隊頭指標也不可能指向45，所以需要再進行入隊及退隊操作，迴圈一圈之後，就可滿足題幹中的要求。最終結果的圖例如下：
1.5.1線性鍊錶的基本概念
考點：線性鍊錶
【2023年9月】（1）下列敘述中正確的是
a）線性表的鏈式儲存結構與順序儲存結構所需要的儲存空間是相同的
b）線性表的鏈式儲存結構所需要的儲存空間一般要多於順序儲存結構
c）線性表的鏈式儲存結構所需要的儲存空間一般要少於順序儲存結構
d）上述三種說法都不對
答案：b
解析：線性表採用鏈式儲存時，每個結點不僅需要儲存資料域，還需要儲存指標域，而順序儲存結構中，每個結點不需要儲存指標，所以本題選b。
習題演練
【2023年9月】(2)下列關於線性鍊錶敘述中，正確的是
a)各資料結點的儲存空間可以不連續，但它們的儲存順序與邏輯順序必須一致
b)各資料結點的儲存順序與邏輯順序可以不一致，但它們的儲存空間必須連續
c)進入插入與刪除時，不需要移動表中的元素
d)以上三種說法都不對
答案：c
解析：在鏈式儲存結構中，儲存資料結構的儲存空間可以不連續，各資料結點的儲存順序與資料元素之間的邏輯關係可以不一致，而資料元素之間的邏輯關係是由指標域來確定的。
在鏈式儲存結構中，進行插入與刪除操作時，不需要移動表中元素，只需要更改相應結點的指標域即可。
1.6.2二叉樹及其基本性質
考點：二叉樹的性質（度為0的結點總比度為2的節點個數多1個）
【2023年9月】（1）某二叉樹有5個度為2的結點以及3個度為1的結點，則該二叉樹中共有 【1】個結點。
答案：14
解析：根據二叉樹的性質3，度為0的結點總比度為2的結點多乙個。在本題中，度為2的結點有5個，所以度為0的結點就有6個。
從題幹中得知，度為1的結點有3個。所以該二叉樹的結點個數就為度為2的結點個數+度為1的節點個數+度為0的節點個數，即5+3+6=14。
習題演練
【2023年9月】（3）一棵二叉樹有10個度為1的結點，7個度為2的結點，則該二叉樹共有__【3】___個結點。
答案：25
【2023年3月】（3）某二叉樹共有7個結點，其中葉子結點只有1個，則該二叉樹的深度為（假設根結點在第1層）
a）3 b）4 c）6 d）7
答案：7
解析：根據性質3，該二叉樹有乙個葉子結點，則沒有度為2的結點，所以該二叉樹中，除了乙個葉子結點外，全都是度為1的結點。即該二叉樹的每一層上只有乙個結點，每個結點就佔一層，所以7個結點就是7層，即該二叉樹的深度為7。
公共基礎知識考點大全
第一部分馬克思主義哲學 1 哲學 世界觀 方 哲學，是系統化 理論化的世界觀。方 是人們認識世界 改造世界的根本方法。2 哲學的基本問題 哲學的基本問題，包括兩個方面，兩個層次。第一方面，是關於物質和意識誰是第一性 誰是第二性的問題，是劃分唯物主義和唯心主義的根本依據。第二方面，是物質和意識是否具有...
公共基礎知識考點彙總
1 公文寫作的語言運用 公文語言的特點 莊重 準確 樸實 精練 嚴謹 規範。公文中需用歷史年號時，要先標出公曆年份，再注歷史年號並加圓括號，如1912年 元年 數量表示時，表示增加時用倍數或分數，表示減少時只能用分數。2 各種文種的撰寫 1 規範性公文。規範性公文一般包括檔案標題 發布或通過或批准的...
2019公共基礎知識考點大全
第一部分馬克思主義哲學 1 哲學 世界觀 方 哲學，是系統化 理論化的世界觀。方 是人們認識世界 改造世界的根本方法。2 哲學的基本問題 哲學的基本問題，包括兩個方面，兩個層次。第一方面，是關於物質和意識誰是第一性 誰是第二性的問題，是劃分唯物主義和唯心主義的根本依據。第二方面，是物質和意識是否具有...