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

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