國家二級ACCESS機試選擇題(數(shù)據(jù)結(jié)構(gòu)與算法)模擬試卷18

國家二級ACCESS機試選擇題（數(shù)據(jù)結(jié)構(gòu)與算法）模擬試卷18(總分：64.00，做題時間：90分鐘)一、選擇題(總題數(shù)：32，分數(shù)：64.00)1.下列敘述中正確的是（分數(shù)：2.00）A.循環(huán)隊列是線性結(jié)構(gòu)√B.循環(huán)隊列是線性邏輯結(jié)構(gòu)C.循環(huán)隊列是鏈式存儲結(jié)構(gòu)D.循環(huán)隊列是非線性存儲結(jié)構(gòu)解析：解析：為充分利用向量空間，克服“假溢出”現(xiàn)象的方法是：將向量空間想象為一個首尾相接的圓環(huán)，并稱這種向量為循環(huán)向量。存儲在其中的隊列稱為循環(huán)隊列(CircularQueue)。線性結(jié)構(gòu)是一個有序數(shù)據(jù)元素的集合。常用的線性結(jié)構(gòu)有：線性表，棧，隊列，雙隊列，數(shù)組，串。常見的非線性結(jié)構(gòu)有：二維數(shù)組，多維數(shù)組，廣義表，樹(二叉樹等)，圖。2.設(shè)某棵樹的度為3，其中度為3、2、1的結(jié)點個數(shù)分別為3、0、4。則該樹中的葉子結(jié)點數(shù)為（分數(shù)：2.00）A.7√B.8C.6D.不可能有這樣的樹解析：解析：樹的度是指一棵樹中，最大的結(jié)點的度稱為“樹的度”。根據(jù)題目可知本樹中沒有度為2的結(jié)點。樹的總結(jié)點=(度1*個數(shù)+度2*個數(shù)…)+1，這里我們設(shè)總結(jié)點數(shù)為n，那么n=3*3+2*0+1*4+1=14。樹的葉子結(jié)點數(shù)等于總結(jié)點減去所有度不為0的結(jié)點，也就是14-3-4=7。3.設(shè)有一個棧與一個隊列的初始狀態(tài)均為空。現(xiàn)有一個序列A，B，C，D，E，F(xiàn)，G，H。先分別將序列中的前4個元素依次入棧，后4個元素依次入隊；然后分別將棧中的元素依次退棧，再將隊列中的元素依次退隊。最后得到的序列為（分數(shù)：2.00）A.D，C，B，A，E，F(xiàn)，G，H√B.D，C，B，A，H，G，F(xiàn)，EC.A，B，C，D，E，F(xiàn)，G，HD.A，B，C，D，H，G，F(xiàn)，E解析：解析：棧(stack)又名堆棧，它是一種運算受限的線性表。其限制是僅允許在表的一端進行插入和刪除運算。因此棧的出棧順序是先入后出，所以順序是D，C，B，A。隊列是一種特殊的線性表，特殊之處在于它只允許在表的前端(front)進行刪除操作，而在表的后端(rear)進行插入操作，和棧一樣，隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。因此，隊的出隊順序是，先入先出，所以順序是E，F(xiàn)，G，H。最后的順序是：D，c，B，A，E，F(xiàn)，G，H。4.下列敘述中錯誤的是（分數(shù)：2.00）A.具有兩個根結(jié)點的數(shù)據(jù)結(jié)構(gòu)一定屬于非線性結(jié)構(gòu)B.具有兩個以上指針域的鏈式結(jié)構(gòu)一定屬于非線性結(jié)構(gòu)√C.具有兩個以上葉子結(jié)點的數(shù)據(jù)結(jié)構(gòu)一定屬于非線性結(jié)構(gòu)D.具有一個根結(jié)點且只有一個葉子結(jié)點的數(shù)據(jù)結(jié)構(gòu)也可能是非線性結(jié)構(gòu)解析：解析：非線性結(jié)構(gòu)，數(shù)學用語，其邏輯特征是一個結(jié)點元素可能有多個直接前驅(qū)和多個直接后繼。常見的非線性結(jié)構(gòu)有：二維數(shù)組，多維數(shù)組，廣義表，樹(二叉樹等)，圖。5.下列結(jié)構(gòu)中屬于線性結(jié)構(gòu)鏈式存儲的是（分數(shù)：2.00）A.雙向鏈表√B.循環(huán)隊列C.二叉鏈表D.二維數(shù)組解析：解析：數(shù)據(jù)元素之間的關(guān)系有兩種不同的表示方法：順序映象和非順序映象，并由此得到兩種不同的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。數(shù)據(jù)的存儲結(jié)構(gòu)是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示。雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)結(jié)點中都有兩個指針，分別指向直接后繼和直接前驅(qū)，它的存儲方式是線性結(jié)構(gòu)鏈式。循環(huán)隊列、二叉鏈表和二維數(shù)組都是順序存儲結(jié)構(gòu)。6.下列敘述中錯誤的是（分數(shù)：2.00）A.循環(huán)鏈表中有一個表頭結(jié)點B.循環(huán)鏈表的存儲空間是連續(xù)的√C.循環(huán)鏈表實現(xiàn)了空表與非空表運算的統(tǒng)一D.循環(huán)鏈表的表頭指針與循環(huán)鏈表中最后一個結(jié)點的指針均指向表頭結(jié)點解析：解析：循環(huán)鏈表是另一種形式的鏈式存儲結(jié)構(gòu)。它的特點是表中最后一個結(jié)點的指針域指向頭結(jié)點，整個鏈表形成一個環(huán)。循環(huán)鏈表的結(jié)點是指針指向，它不一定要是連續(xù)的存儲空間，也可以是斷開的空間。7.度為3的一棵樹共有30個結(jié)點，其中度為3、1的結(jié)點個數(shù)分別為3、4。則該樹中的葉子結(jié)點數(shù)為（分數(shù)：2.00）A.14B.15√C.16D.不可能有這樣的樹解析：解析：根據(jù)題目可知本樹中還有度為2的結(jié)點。樹的總結(jié)點=(度1*個數(shù)+度2*個數(shù)…)+1，這里我們設(shè)度為2的結(jié)點數(shù)為x，那么30=3*3+2*x+1*4+1=2*x+14，由此可計算出x=8。樹的葉子結(jié)點數(shù)等于總結(jié)點減去所有度不為0的結(jié)點，也就是30-3-8-4=15。8.在長度為97的順序有序表中作二分查找，最多需要的比較次數(shù)為（分數(shù)：2.00）A.7√B.96C.48D.6解析：解析：二分查找又稱折半查找，優(yōu)點是比較次數(shù)少，查找速度快，平均性能好；其缺點是要求待查表為有序表，且插入刪除困難。最多比較次數(shù)的計算方式：k=log2n。其中n代表長度，k為比較次數(shù)。本題中可以計算出k=7。9.下列結(jié)構(gòu)中屬于非線性結(jié)構(gòu)的是（分數(shù)：2.00）A.二叉鏈表B.二維數(shù)組√C.循環(huán)隊列D.雙向鏈表解析：解析：線性結(jié)構(gòu)是一個有序數(shù)據(jù)元素的集合。常用的線性結(jié)構(gòu)有：線性表，棧，隊列，雙隊列，數(shù)組，串；常見的非線性結(jié)構(gòu)有：二維數(shù)組，多維數(shù)組，廣義表，樹(二叉樹等)，圖。循環(huán)隊列、雙向鏈表和二叉鏈表都是線性結(jié)構(gòu)，而二維數(shù)組是非線性結(jié)構(gòu)。10.從表中任何一個結(jié)點位置出發(fā)就可以不重復地訪問到表中其他所有結(jié)點的鏈表是（分數(shù)：2.00）A.循環(huán)鏈表√B.雙向鏈表C.單向鏈表D.二叉鏈表解析：解析：循環(huán)鏈表是另一種形式的鏈式存儲結(jié)構(gòu)。它的特點是表中最后一個結(jié)點的指針域指向頭結(jié)點，整個鏈表形成一個環(huán)，循環(huán)一圈就訪問到了表中其它所有結(jié)點而不重復。11.設(shè)二叉樹的前序序列與中序序列均為ABCDEFGH，則該二叉樹的后序序列為（分數(shù)：2.00）A.HGFEDCBA√B.ABCDEFGHC.ABCDHGFED.DCBAHGFE解析：解析：前序遍歷(DLR)是二叉樹遍歷的一種，也叫做先根遍歷、先序遍歷、前序周游，可記做根左右；中序遍歷(LDR)是二叉樹遍歷的一種，也叫做中根遍歷、中序周游，可記做左根右；后序遍歷(LRD)是二叉樹遍歷的一種，也叫做后根遍歷、后序周游，可記做左右根。根據(jù)題中前序和中序序列均為ABCDEFGH，可畫出二叉樹，該二叉樹是一個子結(jié)點全部在右側(cè)二叉樹，然后根據(jù)后序遍歷方法，可得出后序遍歷為HGFEDCBA。12.設(shè)某棵樹的度為3，其中度為3、1、0的結(jié)點個數(shù)分別為3、4、15。則該樹中總結(jié)點數(shù)為（分數(shù)：2.00）A.22B.30√C.35D.不可能有這樣的樹解析：解析：本題采用畫圖法來求出結(jié)果。首先先畫出包含3個度為3的結(jié)點；然后再添加4個度為1的結(jié)點，此時最大度為0的結(jié)點數(shù)為8。根據(jù)題目中描述的度為0的結(jié)點數(shù)有15個，這時要在書中添加度為2的結(jié)點，直到度為0的結(jié)點數(shù)位15。畫圖結(jié)束后，不管是什么樣的樹，總結(jié)點數(shù)都是30。13.下列敘述中正確的是（分數(shù)：2.00）A.矩陣是非線性結(jié)構(gòu)B.數(shù)組是長度固定的線性表√C.對線性表只能作插入與刪除運算D.線性表中各元素的數(shù)據(jù)類型可以不同解析：解析：所謂數(shù)組，就是相同數(shù)據(jù)類型的元素按一定順序排列的集合，就是把有限個類型相同的變量用一個名字命名，然后用編號區(qū)分它們的變量的集合，這個名字稱為數(shù)組名，編號稱為下標。14.在快速排序法中，每經(jīng)過一次數(shù)據(jù)交換(或移動)后（分數(shù)：2.00）A.能消除多個逆序√B.只能消除一個逆序C.不會產(chǎn)生新的逆序D.消除的逆序個數(shù)一定比新產(chǎn)生的逆序個數(shù)多解析：解析：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。15.線性表的長度為n。在最壞情況下，比較次數(shù)為n-1的算法是（分數(shù)：2.00）A.順序查找B.有序表的插入C.尋找最大項√D.同時尋找最大項與最小項解析：解析：尋找最大項算法是，首先取出第一個數(shù)作為最大數(shù)，然后和后面的所有項進行比較查找。因此，比較次數(shù)為n-1。16.設(shè)某棵樹的度為3，其中度為2、1、0的結(jié)點個數(shù)分別為3、4、15。則該樹中總結(jié)點數(shù)為（分數(shù)：2.00）A.22B.30C.35D.不可能有這樣的樹√解析：解析：本題采用畫圖法來求出結(jié)果。首先先畫出包含3個度為2的結(jié)點：然后再添加4個度為1的結(jié)點。根據(jù)題目中描述的度為0的結(jié)點數(shù)有15個，這時要在書中添加度為3的結(jié)點，不管怎么添加都不能添加出15個度為0的結(jié)點，因此不可能有這樣的樹。17.下列敘述中錯誤的是（分數(shù)：2.00）A.向量是線性結(jié)構(gòu)B.非空線性結(jié)構(gòu)中只有一個結(jié)點沒有前件C.非空線性結(jié)構(gòu)中只有一個結(jié)點沒有后件D.只有一個根結(jié)點和一個葉子結(jié)點的結(jié)構(gòu)必定是線性結(jié)構(gòu)√解析：解析：線性結(jié)構(gòu)是n個數(shù)據(jù)元素的有序(次序)集合。①集合中必存在唯一一的一個“第一個元素”；②集合中必存在唯一的一個“最后的元素”；③除最后元素之外，其它數(shù)據(jù)元素均有唯一的“后件”；④除第一元素之外，其它數(shù)據(jù)元素均有唯一的“前件”。相對應(yīng)于線性結(jié)構(gòu)，非線性結(jié)構(gòu)的邏輯特征是一個結(jié)點元素可能對應(yīng)多個直接前驅(qū)和多個后繼。向量符合線性結(jié)構(gòu)特點。非線性結(jié)構(gòu)也會存在只有一個根結(jié)點和葉子結(jié)點的情況。18.在希爾排序法中，每經(jīng)過一次數(shù)據(jù)交換后（分數(shù)：2.00）A.能消除多個逆序√B.只能消除一個逆序C.不會產(chǎn)生新的逆序D.消除的逆序個數(shù)一定比新產(chǎn)生的逆序個數(shù)多解析：解析：希爾排序法(縮小增量法)屬于插入類排序，是將整個無序列分割成若干小的子序列分別進行插入排序的方法。插入排序能夠消除多個逆序，也會產(chǎn)生新的逆序。消除的逆序與新產(chǎn)生的逆序有多有少。19.設(shè)二叉樹的后序序列與中序序列均為ABCDEFGH，則該二叉樹的前序序列為（分數(shù)：2.00）A.HGFEDCBA√B.ABCDEFGHC.ABCDHGFED.DCBAHGFE解析：解析：后序遍歷中，最后一個字母是根結(jié)點，也就是H是根結(jié)點；在中序遍歷中，根結(jié)點前面的是左子樹、后面的是右子樹，H后面沒有，因此該樹沒有右子樹。同理，可判斷出該樹是第一個完全的左子樹。由此可畫出這個二叉樹，然后根據(jù)二叉樹可的前序序列為HGFEDCBA。20.下列敘述中正確的是（分數(shù)：2.00）A.循環(huán)隊列是隊列的鏈式存儲結(jié)構(gòu)B.能采用順序存儲的必定是線性結(jié)構(gòu)C.所有的線性結(jié)構(gòu)都可以采用順序存儲結(jié)構(gòu)√D.具有兩個以上指針的鏈表必定是非線性結(jié)構(gòu)解析：解析：根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間的前后件關(guān)系的復雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)與非線性結(jié)構(gòu)。有序線性表既可以采用順序存儲結(jié)構(gòu)，又可以采用鏈式存儲結(jié)構(gòu)。所有的線性結(jié)構(gòu)都可以采用順序存儲結(jié)構(gòu)。21.下列敘述中正確的是（分數(shù)：2.00）A.算法的復雜度是指算法所處理的數(shù)據(jù)量B.算法的復雜度是指算法程序中指令的數(shù)量C.算法的復雜度是指算法控制結(jié)構(gòu)的復雜程度D.算法的復雜度包括時間復雜度與空間復雜度√解析：解析：算法分析的目的在于選擇合適算法和改進算法。一個算法的評價主要從時間復雜度和空間復雜度來考慮。22.設(shè)二叉樹的時序序列為ABDEGHCFIJ，中序序列為DBGEHACIFJ。則按層次輸出(從上到下，同一層從左到右)的序列為（分數(shù)：2.00）A.ABCDEFGHIJ√B.DGHEBIJFCAC.JIHGFEDCBAD.GHIJDEFBCA解析：解析：前序遍歷中，第一個字母是根結(jié)點，也就是A是根結(jié)點；在中序遍歷中，根結(jié)點前面的是左子樹、后面的是右子樹。前序中，B在A的后面，中序中在左子樹中，可知B為A的左結(jié)點。中序中D在B的前面，前序中在B的后面，可知D為B的左結(jié)點，GEH為B的右子樹。前序中順序為EGH，由此可知，E為B的右結(jié)點，G為E的左結(jié)點、H為E的右結(jié)點。右子樹中，前序中c在最前，因為右子樹根結(jié)點，也就是A的右結(jié)點，根據(jù)前序中的子樹FIJ和中序中的IFJ子樹可知F為C的右結(jié)點，I為F的左結(jié)點、J為F的右結(jié)點。由此可畫出這個二叉樹，然后根據(jù)二叉樹，可知按層次輸出(從上到下，同一層從左到右)的序列為：ABCDEFGHIJ。23.設(shè)循環(huán)隊列的存儲空間為Q(1：50)，初始狀態(tài)為front=rear=S0。經(jīng)過一系列正常的操作后，front-1=rear。為了在該隊列中尋找值最大的元素，在最壞情況下需要的比較次數(shù)為。（分數(shù)：2.00）A.0B.1C.48√D.49解析：解析：front指向隊頭位置，刪除一個元素就將front順時針移動一位；rear指尾指針指向元素要插入的位置，插入一個元素就將rear順時針移動一位；操作后循環(huán)隊列的隊頭指針-1等于尾指針，說明出隊一位，那么總數(shù)就是49了。在該隊列中尋找最大值元素，最多比較次數(shù)是總數(shù)-1，因此是49-1=48次。24.設(shè)順序表的長度為40，對該表進行冒泡排序。在最壞情況下需要的比較次數(shù)為（分數(shù)：2.00）A.780√B.820C.40D.41解析：解析：冒泡排序(BubbleSort)，是一種計算機科學領(lǐng)域的較簡單的排序算法。冒泡排序算法的運作如下：比較相鄰的元素。如果第一個比第二個大，就交換它們兩個：對每一對相鄰元素作同樣的工作．從開始第一對到結(jié)尾的最后一對。在這一點，最后的元素應(yīng)該會是最大的數(shù)；針對所有的元素重復以上的步驟，除了最后一個；持續(xù)每次對越來越少的元素重復上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。冒泡排序的最壞時間復雜度為(n*(n-1))／2=780。25.設(shè)表的長度為n。在下列算法中，最壞情況下時間復雜度最高的是（分數(shù)：2.00）A.堆排序B.希爾排序√C.有序鏈表查找D.循環(huán)鏈表中尋找最大項解析：解析：希爾排序(ShellSort)是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進版本。排序方法最壞時間復雜度：直接插入為O(n2)、簡單選擇為O(n2)、起泡排序為O(n2)、快速排序為O(n2)、堆排序為O(nlog2n)、歸并排序為O(nlog2n)。26.設(shè)循環(huán)隊列的存儲空間為Q(1：50)，初始狀態(tài)為front=rear=50。經(jīng)過一系列正常的操作后，front=rear-1。為了在該隊列中尋找值最大的元素，在最壞情況下需要的比較次數(shù)為（分數(shù)：2.00）A.0√B.1C.49D.50解析：解析：front指定隊頭位置，刪除一個元素就將front順時針移動一位：rear指尾指針，指向元素要插入的位置，插入一個元素就將rear順時針移動一位；操作后，循環(huán)隊列的隊頭指針等于尾指針-1，說明此時隊列已經(jīng)是空隊列，那么就不用比較了。27.設(shè)二叉樹的前序序列為ABDEGHCFIJ，中序序列為DBGEHACIFJ。則后序序列為（分數(shù)：2.00）A.DGHEBIJFCA√B.JIHGFEDCBAC.GHIJDEFBCAD.ABCDEFGHIJ解析：解析：前序遍歷中，第一個字母是根結(jié)點，也就是A是根結(jié)點：在中序遍歷中，根結(jié)點前面的是左子樹、后面的是右子樹。前序中，B在A的后面，中序中在左子樹中，可知B為A的左結(jié)點。中序中D在B的前面，前序中在B的后面，可知D為B的左結(jié)點，GEH為B的右子樹。前序中順序為EGH，由此可知，E為B的右結(jié)點，G為E的左結(jié)點、H為E的右結(jié)點。右子樹中，前序中C在最前，因為右子樹根結(jié)點，也就是A的右結(jié)點，根據(jù)前序中的子樹FIJ和中序中的IFJ子樹可知F為C的右結(jié)點，I為F的左結(jié)點、J為F的右結(jié)點。由此可畫出這個二叉樹，然后根據(jù)二叉樹可的后序序列為DGHEBIJFcA。28.設(shè)順序表的長度為16，對該表進行簡單插入排序。在最壞情況下需要的比較次數(shù)為（分數(shù)：2.00）A.15B.30C.60D.120√解析：解析：插入排序的基本思想是：每步將一個待排序的記錄，按其關(guān)鍵碼值的大小插入前面已經(jīng)排序的文件中適當位置上，直到全部插入完為止。最壞情況計算方法(n*(n-1))／2=16*15／2=120。29.下列結(jié)構(gòu)中為非線性結(jié)構(gòu)的是（分數(shù)：2.00）A.樹√B.向量C.二維表D.矩陣解析：解析：線性結(jié)構(gòu)是一個有序數(shù)據(jù)元素的集合。常用的線性結(jié)構(gòu)有：線性表，棧，隊列，雙隊列，數(shù)組，串。常見的非線性結(jié)構(gòu)有：二維數(shù)組，多維數(shù)組，廣義表，樹(二叉樹等)，圖。30