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

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