國家二級ACCESS機試選擇題（數據結構與算法）模擬試卷5(總分：60.00，做題時間：90分鐘)一、選擇題(總題數：30，分數：60.00)1.設順序表的長度為n。下列算法中，最壞情況下比較次數小于n的是（分數：2.00）A.尋找最大項√B.堆排序C.快速排序D.順序查找法解析：解析：如果順序表是線性存儲的(不包括線性的鏈式表)，那么元素要不就是從大到小，要不就是小到大的順序，假設第一個數就是最大值，那么需要比較1次，n一1應該是最壞情況下要比較的次數，所以選項A正確。2.設棧的順序存儲空間為S(1：m)，初始狀態為top=m+1?，F經過一系列正常的入棧與退棧操作后，top=0；則棧中的元素個數為（分數：2.00）A.不可能√B.m+1C.1D.m解析：解析：棧是向上增長的，每次壓入一個元素，棧的TOP指針向上移動一位，即top-1。對于這個題目，由于top初始值等于m+1，此時入棧一個元素，top值減1，即m+1-1=m，依次類推，當棧滿時，top的值等于1，不會出現top的值等于0。所以選項A正確。3.某二叉樹的后序遍歷序列與中序遍歷序列相同，均為ABCDEF，則按層次輸出(同一層從左到右)的序列為（分數：2.00）A.FEDCBA√B.CBAFEDC.DEFCBAD.ABCDEF解析：解析：后序遍歷次序：左右根；中序遍歷次序：左根右。由定義可知：①后序遍歷中最后一個是樹的根結點，即F結點；②在中序遍歷中，根結點左邊的是左子樹集，右邊的是右子樹集，即ABCDE是根結點F的左子樹集合。問題就會轉化為：求后序遍歷是ABC。DE，中序遍歷是ABCDE的子樹。方法同上，因為中序遍歷中，E結點右邊沒有結點了，所以E結點不包含右子樹，否則就會被分為2個子問題。以下是這道題的詳細推理過程：步驟1：由ABCDEF。得出根結點為F，由中序遍歷可知：{ABCDE}F，右子樹為空；步驟2：由ABCDE得出左子樹集合的根節點為E，由中序可知：{ABCD}E，右子樹為空；步驟3：同理，二叉樹更新后如下。所以按層次輸出(同一層從左到右)的序列為FEDCBA。4.循環隊列的存儲空間為Q(1：200)，初始狀態為front=rear=200。經過一系列正常的入隊與退隊操作后，front=rear=1，則循環隊列中的元素個數為（分數：2.00）A.0或200√B.1C.2D.199解析：解析：循環隊列中，由于入隊時尾指針rear向前追趕頭指針front；出隊時頭指針front向前追趕尾指針rear，造成隊空和隊滿時頭尾指針均相等。因此，無法通過條件front=rear來判別隊列是“空”還是“滿”。對于這個題目來說，經過一系列正常的入隊與退隊操作后，front=rear=1，此時，要么隊列為空(元素個數為0)，要么隊列為滿(元素個數為200)。所以選項A正確。5.設棧的順序存儲空間為S(1：m)，初始狀態為top=0?，F經過一系列正常的入棧與退棧操作后，top=m+1，則棧中的元素個數為（分數：2.00）A.不可能√B.m+1C.0D.m解析：解析：棧是向上增長的，每次壓入一個元素，棧的TOP指針向上移動一位，即top-1。對于這個題目，由于top初始值等于0，此時入棧一個元素，top值減1，即0．1=-1，出現下溢錯誤，所以選項A正確。6.下列排序法中，最壞情況下時間復雜度最小的是（分數：2.00）A.堆排序√B.快速排序C.希爾排序D.冒泡排序解析：解析：假設線性表的長度為n，則在最壞情況下，冒泡排序需要經過n／2遍的從前往后掃描和n／2遍的從后往前掃描，需要比較次數為n(n—1)／2?？焖倥判蚍ǖ淖顗那闆r比較次數也是n(n-1)／2。簡單插入排序，無論是否最壞都需要n(n一1)／2比較。堆排序，無論是否最壞情況都是比較O(nlog2n)次。所以選項A正確。7.某二叉樹的前序遍歷序列與中序遍歷序列相同，均為ABCDEF，則按層次輸出(同一層從左到右)的序列為（分數：2.00）A.ABCDEF√B.BCDEFAC.FEDCBAD.DEFABC解析：解析：前序遍歷次序：根左右；中序遍歷次序：左根右。由定義可以知道：①前序遍歷中第一個就是樹根結點，即A結點；②在中序遍歷中，根結點左邊的是左子樹集，右邊的是右子樹集，即BCDEF是根結點A的右子樹集合。問題就會轉化為：求前序遍歷是BCDEF，中序遍歷是BCDEF的子樹，方法同上。詳細推理過程：步驟1：由ABCDEF得出根結點為A，由中序遍歷可知：左子樹為空，A{BCDEF}；步驟2：由BCDEF得出右子樹集合的根節點為B，由中序可知：左子樹為空，B{CDEF}；步驟3：同理，二叉樹更新后如下。所以按層次輸出(同一層從左到右)的序列為ABCDEF，選項A正確。8.下列敘述中正確的是（分數：2.00）A.對數據進行壓縮存儲會降低算法的空間復雜度√B.算法的優化主要通過程序的編制技巧來實現C.算法的復雜度與問題的規模無關D.數值型算法只需考慮計算結果的可靠性解析：解析：算法的空間復雜度是指執行這個算法所需要的內存空間，包括3個部分：輸入數據所占的存儲空間；程序本身所占的存儲空間；算法執行過程中所需要的額外空間。為了降低算法的空間復雜度，主要應減少輸入數據所占的存儲空間以及額外空間，通常采用壓縮存儲技術，A選項正確。9.設數據結構B=(D，R)，其中D={a，b，c，d，e，DR={(a,b)，(b,c)，(c,(d)，(d,e)，(e，D，(f,(a)}該數據結構為（分數：2.00）A.非線性結構√B.循環隊列C.循環鏈表D.線性結構解析：解析：該邏輯結構為非線性結構，在R={(a,b)，(b,c)，(c,d)，(d,e)，(e,f)，(f,a)}中，各結點之間形成一個循環鏈。10.下列排序法中，每經過一次元素的交換會產生新的逆序的是（分數：2.00）A.快速排序√B.冒泡排序C.簡單插入排序D.簡單選擇排序解析：解析：冒泡排序只交換相令昏元素，但不是每次移動都產生新韻逆序。簡單插入排序的元素移動不會產生新的逆序?？焖倥判蛎恳淮谓粨Q移動都會產生新的逆序，因為當不會有新的逆序產生時，本輪比較結束。故選項A正確。11.某帶鏈的隊列初始狀態為front=rear=NULL。經過一系列正常的入隊與退隊操作后，front=rear=10。該隊列中的元素個數為（分數：2.00）A.1√B.0C.1或0D.不確定解析：解析：循環隊列用數組A[0；m-1]存放其元素值，已知其頭尾指針分別是front和rear，則當前隊列的元素個數是(rear-front+m)％m=1，所以選項A正確。12.某完全二叉樹按層次輸出(同一層從左到右)的序列為ABCDEFGH。該完全二叉樹的前序序列為（分數：2.00）A.ABDHECFG√B.ABCDEFGHC.HDBEAFCGD.HDEBFGCA解析：解析：完全二叉樹的特點是除最后一層外，每一層上的節點數均達到最大值；在最后一層上只缺少右邊的若干結點。根據上述的特點，完全二叉樹按層次輸出(同一層從左到右)的序列為ABCDEFGH，可以得到其結構如下：所以此完全二叉樹的前序序列是ABDHECFG，選項A正確。13.下列敘述中正確的是（分數：2.00）A.有的二叉樹也能用順序存儲結構表示√B.有兩個指針域的鏈表就是二叉鏈表C.多重鏈表一定是非線性結構D.順序存儲結構一定是線性結構解析：解析：完全二叉樹如果“根”從1開始編號，則第i結點的左孩子編號為2i，右孩子為2i+1，雙親編號為(i／2)下取整，空間緊密，適合順序存儲結構。所以選項A正確。小提示：取整是指取不超過實數x的最大整數，稱為x的整數部分。上取整就是對實數取大于當前實數的第一個整數；下取整就是對當前實數去掉小數取整。14.下列各排序法中，最壞情況下時間復雜度最小的是（分數：2.00）A.堆排序√B.快速排序C.希爾排序D.冒泡排序解析：解析：快速排序、冒泡排序最壞情況下時間復雜度是O(n2)：希爾排序最壞情況下時間復雜度是O(n1.2)。堆排序最壞情況下時間復雜度是O(nlog2n)，所以選項A正確。15.某帶鏈隊列初始狀態為front=rear=NULL。經過一系列正常入隊與退隊操作后，front=10，rear=5。該隊列中的元素個數為（分數：2.00）A.不確定√B.5C.4D.6解析：解析：循環隊列用數組A[0：m-1]存放其元素值，己知其頭尾指針分別是front和rear，則當前隊列的元素個數是(rear-front+m)％m=(5-10+m)％m=(m-5)％m。因為本題中的m值不確定，所以(m-5)％m的值不能確定。所以選項A正確。16.某二叉樹的前序序列為ABDFHCEG，中序序列為HFDBACEG。該二叉樹按層次輸出(同一層從左到右)的序列為（分數：2.00）A.ABCDEFGH√B.HFDBGECAC.HGFEDCBAD.ACEGBDFH解析：解析：由于二叉樹的前序序列ABDFHCEG，可以確定這個二叉樹的根結點是A。再由中序序列HFDBACEG，可以得到，HFDB為A的左子樹，CEG為A的右子樹。同理依次對左子樹HFDB和右子樹CEG進行同樣的推理，得到這個二叉樹的結構如下ABCDEFGH，所以選項A正確。該二叉樹按層次輸出(同一層從左到右)的序列為17.某帶鏈棧初始狀態為top=bottom=NULL，經過一系列正常的入棧與退棧操作后，top=10，bottom=20，該棧中的元素個數為（分數：2.00）A.不確定√B.10C.1D.0解析：解析：對于鏈棧而言，使用了鏈表來實現棧，鏈表中的元素存儲在不連續的地址。所以當top=10，bottom=20時，不能確定棧中的元素個數，所以選項A正確。18.設表的長度為15。則在最壞情況下，快速排序所需要的比較次數為（分數：2.00）A.105√B.55C.15D.75解析：解析：假設線性表的長度為n，在最壞情況下，快速排序法的比較次數是n(n-1)／2。題中n=15，所以15*14／2=105。所以選項A正確。19.設循環隊列的存儲空間為Q(1：100)，初始狀態為空。現經過一系列正常操作后，front=49，則循環隊列中的元素個數為（分數：2.00）A.不確定√B.49C.51D.50解析：解析：循環隊列用數組Q[1：100]存放其元素值，已知其頭尾指針分別是front和rear，則當前隊列的元素個數是(rear—front+100)％100，題目中首指針rear的值未知，所以循環隊列中的元素個數不能確定。所以選項A正確。20.某完全二叉樹按層次輸出(同一層從左到右)的序列為ABCDEFGH。該完全二叉樹的中序序列為（分數：2.00）A.HDBEAFCG√B.HDEBFGCAC.ABDHECFGD.ABCDEFGH解析：解析：完全二叉樹的特點是除最后一層外，每一層上的節點數均達到最大值：在最后一層上只缺少右邊的若干結點。根據上述特點，完全二叉樹按層次輸出(同一層從左到右)的序列為ABCDEFGH。可以得到其結構如下：所以此完全二叉樹的中序序列是HDBEAFCG。所以選項A正確。21.下列敘述中正確的是（分數：2.00）A.解決一個問題可以有不同的算法，且它們的時間復雜度可以是不同的√B.解決一個問題可以有不同的算法，但它們的時間復雜度必定是相同的C.解決一個問題的算法是唯一的D.算法的時間復雜度與計算機系統有關解析：解析：算法的時間復雜度和問題有關系，因為一個問題很有可能有許多類算法，但是它們的時間復雜度不同，如排序問題就有10種左右算法，它們復雜度顯然是不一樣的。所以選項A正確。22.設表的長度為n。下列查找算法中，在最壞情況下，比較次數最少的是（分數：2.00）A.有序表的二分查找√B.順序查找C.尋找最大項D.尋找最小項解析：解析：有序表的二分法查找只適用于順序存儲的有序表。二分查找的基本方法是：將被查元素x與線性表的中間項進行比較，若中間項的值等于x，則說明查到；若小于中間項的值則在線性表的前半部分以相同的方法進行查找；若大于中間項的值則在線性表的后半部分以相同的方法進行查找。在最壞情況下，二分查找需要比較log2n次。順序查找、尋找最大項、尋找最小項，在最壞情況下，比較次數都是n次。所以選項A正確。23.某帶鏈棧的初始狀態為top=bottom=NULL，經過一系列正常的入棧與退棧操作后，top=bottom=20。該棧中的元素個數為（分數：2.00）A.1B.0C.20D.不確定√解析：解析：對于鏈棧而言，使用了鏈表來實現棧，鏈表中的元素存儲在不連續的地址。所以當top=bottom=20時，不能確定棧中的元素個數。所以選項D正確。24.某二叉樹的前序序列為ABDFHCEG，中序序列為HFDBACEG。該二叉樹的后序序列為（分數：2.00）A.HFDBGECA√B.ABCDEFGHC.HGFEDCBAD.ACEGBDFH解析：解析：由于二叉樹的前序序列ABDFHCEG，可以確定這個二叉樹的根結點是A。再由中序序列HFDBACEG，可以得到，HFDB為A的左子樹，CEG為A的右子樹子同理依次對左子樹。HFDB和右子樹CEG進行同樣的推理，得到這個二叉樹的結構如下：以選項A正確。對該二叉樹的后序遍歷序列為HFDBGECA，所25.下列敘述中錯誤的是（分數：2.00）A.算法的時間復雜度與問題規模無關√B.算法的時間復雜度與計算機系統無關C.算法的時間復雜度與空間復雜度沒有必然的聯系D.算法的空間復雜度與算法運行輸出結果的數據量無關解析：解析：一般情況下，算法中基本操作重復執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n)，使得當n趨近于無窮大時，T(n)／f(n)的極限值為不等于零的常數，則稱f(n)是T(n)的同數量級函數。記作T(n)=O(f(n))，稱O(f(n))為算法的漸進時間復雜度，簡稱時間復雜度。所以選項A正確。26.設表的長度為20。則在最壞情況下，冒泡排序的比較次數為（分數：2.00）A.90B.20C.19D.190√解析：解析：假設線性表的長度為n，則在最壞情況下，冒泡排序的比較次數為n(n一1)／2。本題中，n=20，所以20*19／2=190。所以選項D正確。27.在帶鏈棧中，經過一系列正常的操作后，如果top=bosom，則棧中的元素個數為（分數：2.00）A.1B.0C.0或I√D.棧滿解析：解析：鏈棧就是沒有附加頭結點的、運算受限的單鏈表。棧頂指針就是鏈表的頭指針。如果棧底，指針指向的存儲單元中存有1元素，則當top=bottom時，棧中的元素個數為1；如果棧底指針指向的存儲單元中沒有存元素，則當top=bottom時，棧中的元素個數為0。所以選項C正確。28.設一棵樹的度為3，共有27個結點，其中度為3，2，0的結點數分別為4，1，10。該樹中度為l的結點數為（分數：2.00）A.11B.12√C.13D