數(shù)據(jù)結(jié)構(gòu)階段測評(píng)大全含答案

1、數(shù)據(jù)結(jié)構(gòu)-階段測評(píng)11.單選題 1.15.0計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的對(duì)象被統(tǒng)稱為(A )您答對(duì)了 a數(shù)據(jù) b數(shù)據(jù)元素 c數(shù)據(jù)結(jié)構(gòu) d數(shù)據(jù)類型本題考核數(shù)據(jù)的基本概念1.25.0非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p所指向）滿足（C）。您答對(duì)了 ap-next=NULL bp=NULL cp-next=head dp=head本題考核循環(huán)單鏈表的基本特點(diǎn)。1.35.0若長度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，在第i個(gè)位置上插入一個(gè)新元素的時(shí)間復(fù)雜度為（A）。您答對(duì)了 aO(n) bO(1) cO(n2) dO(n3)本題考核順序表的插入運(yùn)算的時(shí)間復(fù)雜度。1.45.0下面程序段中aij=0語句執(zhí)行

2、的時(shí)間復(fù)雜度是( D)。for(i=0;in;i+)for(j=1;jm;j+)aij=0；您答對(duì)了 aO(n) bO(m+n+1) cO(m+n) dO(m*n)本題考核時(shí)間復(fù)雜度的計(jì)算方法1.55.0在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并保持單鏈表仍然有序的時(shí)間復(fù)雜度是（B）。您答對(duì)了 aO(1) bO(n) cO(n2) dO(nlog2n)因要保持有序，所以需要查找插入結(jié)點(diǎn)的位置，而在鏈表中查找結(jié)點(diǎn)位置的時(shí)間復(fù)雜度為O(n)，所以本題選B。1.65.0在一個(gè)長度為n的順序表中刪除第i個(gè)元素（1=inext; bp-next=p-next-next; cp-next=p; dp

3、=p-next-next;本題考核單鏈表結(jié)點(diǎn)刪除的基本操作1.145.0在一個(gè)單鏈表中，若刪除p所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行（A）。您答對(duì)了 ap-next=p-next-next; bp=p-next; p-next=p-next-next; cp-next=p-next; dp =p-next-next;考核單鏈表的刪除操作1.155.0若結(jié)點(diǎn)的存儲(chǔ)地址與其關(guān)鍵字之間存在某種映射關(guān)系，則稱這種存儲(chǔ)結(jié)構(gòu)為（ D）。您答對(duì)了 a順序存儲(chǔ)結(jié)構(gòu) b鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) c索引存儲(chǔ)結(jié)構(gòu) d散列存儲(chǔ)結(jié)構(gòu)本題考核散列存儲(chǔ)的基本概念1.165.0若將數(shù)據(jù)結(jié)構(gòu)形式定義為二元組(K，R)，其中K是數(shù)據(jù)元素的有限集合，則

4、R是K上(D )。您答對(duì)了 a操作的有限集合 b映象的有限集合 c類型的有限集合 d關(guān)系的有限集合本題考核數(shù)據(jù)結(jié)構(gòu)的基本概念1.175.0將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時(shí)間復(fù)雜度為（C ）。您答對(duì)了 aO（1） bO（n） cO（m） dO（m+n）本題考核單鏈表的基本特點(diǎn)1.185.0關(guān)于棧和隊(duì)列的說法中正確的是（ A）。您答對(duì)了 a棧和隊(duì)列都是線性結(jié)構(gòu) b棧是線性結(jié)構(gòu)，隊(duì)列不是線性結(jié)構(gòu) c棧不是線性結(jié)構(gòu)，隊(duì)列是線性結(jié)構(gòu) d棧和隊(duì)列都不是線性結(jié)構(gòu)棧和隊(duì)列都是一種特殊的線性表。1.195.0判定“帶頭結(jié)點(diǎn)的鏈隊(duì)列為空”的條件是(C )。您答對(duì)了 aQ.front=NULL

5、 bQ.rear=NULL cQ.front=Q.rear dQ.front!=Q.rear本題考核鏈隊(duì)列的基本概念，答案選C。1.205.0設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素a,b,c,d,e,f,g依次入棧S。若每個(gè)元素出棧后立即進(jìn)入隊(duì)列Q，且7個(gè)元素出列的順序是b,d,c,f,e,a,g，則棧S的容量至少是（C）。您答對(duì)了 a1 b2 c3 d4本題考核棧與隊(duì)列的性質(zhì)以及進(jìn)棧、出棧、進(jìn)隊(duì)、出隊(duì)等基本操作方法。數(shù)據(jù)結(jié)構(gòu)-階段測評(píng)21.單選題 1.15.0引起循環(huán)隊(duì)列隊(duì)頭位置發(fā)生變化的操作是(A )。您答對(duì)了 a出隊(duì) b入隊(duì) c取隊(duì)頭元素 d取隊(duì)尾元素本題考核循環(huán)隊(duì)列的基本操作。1.25.0

6、從廣義表L=(e),c,d)中分解得到原子c的操作為(B )。您答對(duì)了 ahead(head(head(L) bhead(tail(head(L) ctail(head(head(L) dtail(tail(head(L)本題考核廣義表的基本操作。1.35.0對(duì)矩陣壓縮存儲(chǔ)是為了（B ）。您答對(duì)了 a方便運(yùn)算 b節(jié)省空間 c方便存儲(chǔ) d提高運(yùn)算速度壓縮存儲(chǔ)就是為了節(jié)省存儲(chǔ)空間。1.45.0順序循環(huán)隊(duì)列中（數(shù)組的大小為6），隊(duì)頭指示front和隊(duì)尾指示rear的值分別為3和0，當(dāng)從隊(duì)列中刪除1個(gè)元素，再插入2個(gè)元素后，front和rear的值分別為（D）。您答對(duì)了 a5和1 b2和4 c1和5

7、d4和2本題考核順序循環(huán)隊(duì)列的基本特點(diǎn)。1.55.0設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素a,b,c,d,e,f,g依次入棧S。若每個(gè)元素出棧后立即進(jìn)入隊(duì)列Q，且7個(gè)元素出列的順序是b,d,c,f,e,a,g，則棧S的容量至少是（C）。您答對(duì)了 a1 b2 c3 d4本題考核棧與隊(duì)列的性質(zhì)以及進(jìn)棧、出棧、進(jìn)隊(duì)、出隊(duì)等基本操作方法。1.65.0隊(duì)列和棧的主要區(qū)別是（ A）。您答對(duì)了 a限定插入和刪除的位置不同 b存儲(chǔ)結(jié)構(gòu)不同 c所包含的運(yùn)算個(gè)數(shù)不同 d邏輯結(jié)構(gòu)不同本題考核棧與隊(duì)列的基本特點(diǎn)1.75.0表達(dá)式a*(b+c)-d的后綴表達(dá)式是(B)。您答對(duì)了 aabc*d+- babc+*d- cabc

8、*+d- d-+*abcd本題考核中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式的基本方法。1.85.0棧是一種特殊的線性表，具有（B）性質(zhì)。您答對(duì)了 a先進(jìn)先出 b先進(jìn)后出 c后進(jìn)后出 d順序進(jìn)出考核棧的基本概念1.95.0對(duì)廣義表L=(a,b),(c,d),(e,f)執(zhí)行操作tail(tail(L)的結(jié)果是(B)您答對(duì)了 a(e,f) b(e,f) c(f) d( )考核廣義表的基本操作1.105.0設(shè)棧的輸入序列為（1、2、3、4），則不可能的出棧序列為（ C）。您答對(duì)了 a1243 b2134 c4312 d1432本題考核棧的進(jìn)棧與出棧特點(diǎn)，根據(jù)先進(jìn)后出、后進(jìn)先出的特點(diǎn)，可知本題答案選C。1.115.0操作

9、系統(tǒng)的CPU管理程序?yàn)閷?shí)現(xiàn)先來先服務(wù)的作業(yè)管理，需要設(shè)置一個(gè)存儲(chǔ)區(qū)，用于記錄當(dāng)前用戶作業(yè)，這個(gè)存儲(chǔ)區(qū)的邏輯結(jié)構(gòu)是（ B）。您答對(duì)了 a棧 b隊(duì)列 c樹 d圖本題考核隊(duì)列的基本特點(diǎn)。1.125.0若進(jìn)棧序列為1，2，3，4，5，6，且進(jìn)棧和出棧可以穿插進(jìn)行，則不可能出現(xiàn)的出棧序列是( C)。您答對(duì)了 a2，4，3，1，5，6 b4，3，2，1，5，6 c2，3，5，1，6，4 d3，2，4，1，6，5核具有先進(jìn)后出，后進(jìn)先出的特點(diǎn)，根據(jù)這個(gè)特點(diǎn)，可知本題答案為C。1.135.0判定“帶頭結(jié)點(diǎn)的鏈隊(duì)列為空”的條件是(C )。您答對(duì)了 aQ.front=NULL bQ.rear=NULL cQ.fr

10、ont=Q.rear dQ.front!=Q.rear本題考核鏈隊(duì)列的基本概念，答案選C。1.145.0關(guān)于棧和隊(duì)列的說法中正確的是（ A）。您答對(duì)了 a棧和隊(duì)列都是線性結(jié)構(gòu) b棧是線性結(jié)構(gòu)，隊(duì)列不是線性結(jié)構(gòu) c棧不是線性結(jié)構(gòu)，隊(duì)列是線性結(jié)構(gòu) d棧和隊(duì)列都不是線性結(jié)構(gòu)棧和隊(duì)列都是一種特殊的線性表。1.155.0已知循環(huán)隊(duì)列的存儲(chǔ)空間為數(shù)組data21，且當(dāng)前隊(duì)列的頭指針和尾指針的值分別為8和3，則該隊(duì)列當(dāng)前長度為(C)您答對(duì)了 a5 b6 c16 d17考核順序循環(huán)隊(duì)列的特點(diǎn)1.165.0從廣義表LS（(p, q), r, s）中分解出原子q的運(yùn)算是（B）。您答對(duì)了 atail (head (

11、LS) bhead (tail (head (LS) chead (tail (LS) dtail (tail (head (LS)本題考核廣義表的基本操作。1.175.0鏈棧與順序棧相比，比較明顯的優(yōu)點(diǎn)是( D)。您答對(duì)了 a插入操作更加方便 b刪除操作更加方便 c不會(huì)出現(xiàn)下溢的情況 d不會(huì)出現(xiàn)上溢的情況鏈棧采用動(dòng)態(tài)內(nèi)存分配，一般不會(huì)出現(xiàn)棧滿的情況，即一般不會(huì)出現(xiàn)上溢的情況。所以答案選D。1.185.0將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時(shí)間復(fù)雜度為（ C）。您答對(duì)了 aO（1） bO（n） cO（m） dO（m+n）本題考核單鏈表的基本特點(diǎn)1.195.0在一個(gè)具有n個(gè)結(jié)點(diǎn)的

12、有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并保持單鏈表仍然有序的時(shí)間復(fù)雜度是（B）。您答對(duì)了 aO(1) bO(n) cO(n2) dO(nlog2n)因要保持有序，所以需要查找插入結(jié)點(diǎn)的位置，而在鏈表中查找結(jié)點(diǎn)位置的時(shí)間復(fù)雜度為O(n)，所以本題選B。1.205.0下面程序段中aij=0語句執(zhí)行的時(shí)間復(fù)雜度是( D)。for(i=0;in;i+)for(j=1;j0），空鏈域的個(gè)數(shù)為（ B）。您答對(duì)了 a2n-1 bn+1 cn-1 d2n+1n個(gè)結(jié)點(diǎn)的二叉樹共有n-1條邊，所以空鏈域的個(gè)數(shù)為n+1。1.25.0若鄰接表中有奇數(shù)個(gè)表結(jié)點(diǎn)，則一定（D）。您答對(duì)了 a圖中有奇數(shù)個(gè)頂點(diǎn) b圖中有偶數(shù)個(gè)頂點(diǎn) c圖為

13、無向圖 d圖為有向圖本題考核圖的鄰接表存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)。1.35.0一棵完全二叉樹有999個(gè)結(jié)點(diǎn)，它的深度為（B）。您答對(duì)了 a9 b10 c11 d12本題考核完全二叉樹的性質(zhì)。1.45.0一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)為（D）。您答對(duì)了 a250 b500 c254 d501本題考核完全二叉樹的性質(zhì)1.55.0n個(gè)頂點(diǎn)的強(qiáng)連通圖中至少含有（B ）。您答對(duì)了 an-1條有向邊 bn條有向邊 cn（n-1）/2條有向邊 dn（n-1）條有向邊本題考核強(qiáng)連通圖的基本性質(zhì)。1.65.0無向圖中一個(gè)頂點(diǎn)的度是指圖中( B)。您答對(duì)了 a通過該頂點(diǎn)的簡單路徑數(shù) b與該頂點(diǎn)相鄰接的

14、頂點(diǎn)數(shù) c通過該頂點(diǎn)的回路數(shù) d與該頂點(diǎn)連通的頂點(diǎn)數(shù)本題考核頂點(diǎn)的度的基本概念。1.75.0下列哪一個(gè)選項(xiàng)不是圖所示有向圖的拓?fù)渑判蚪Y(jié)果（C）。您答對(duì)了 aAFBCDE bFABCDE cFACBDE dFADBCE本題考核圖的拓?fù)渑判蚧舅枷搿?.85.0設(shè)有一個(gè)有向圖如圖所示，請(qǐng)指出下列哪個(gè)序列不是該圖的拓?fù)渑判蛐蛄校– ）。您答對(duì)了 aEAFBGDC bAEBCGFD cABCGEFD dEABGFCD本題考核圖的拓?fù)渑判蚧舅枷搿?.95.0無向圖的鄰接矩陣是一個(gè)（ A）您答對(duì)了 a對(duì)稱矩陣 b零矩陣 c上三角矩陣 d對(duì)角矩陣由于是無向圖，所以該圖的鄰接矩陣是對(duì)稱矩陣。1.105.0如

15、果某圖的鄰接矩陣是對(duì)角線元素均為零的上三角矩陣，則此圖是（D）。您答對(duì)了 a有向完全圖 b連通圖 c強(qiáng)連通圖 d有向無環(huán)圖本題考核圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)的基本特點(diǎn)。1.115.0設(shè)有向圖的鄰接鏈表如圖所示，則該圖的邊的數(shù)目是（ A）。您答對(duì)了 a6 b7 c8 d12本題考核圖的鄰接表存儲(chǔ)結(jié)構(gòu)的基本特點(diǎn)。1.125.0下列陳述中正確的是( D)您答對(duì)了 a二叉樹是度為2的有序樹 b二叉樹中結(jié)點(diǎn)只有一個(gè)孩子時(shí)無左右之分 c二叉樹中必有度為2的結(jié)點(diǎn) d二叉樹中最多只有兩棵子樹，并且有左右之分本題考核二叉樹與度為二的樹的區(qū)別，答案選D。1.135.0對(duì)于一棵具有n個(gè)節(jié)點(diǎn)，度為4的樹來說，（ A）。您答

16、對(duì)了 a樹的高度至多是n-3 b樹的高度至多是n-4 c第i層至多有4（i-1）個(gè)節(jié)點(diǎn) d至少在某一層上正好有4個(gè)節(jié)點(diǎn)本題考核樹的基本性質(zhì)。1.145.0一棵含18個(gè)結(jié)點(diǎn)的二叉樹的高度至少為( C)。您答對(duì)了 a3 b4 c5 d6當(dāng)二叉樹為完全二叉樹時(shí)該樹具有最小高度。本題考核二叉排序樹的基本概念。1.155.0假設(shè)一個(gè)有n個(gè)頂點(diǎn)和e條弧的有向圖用鄰接表表示，則刪除與某個(gè)頂點(diǎn)vi相關(guān)的所有弧的時(shí)間復(fù)雜度是（B）。您答對(duì)了 aO(n) bO(e) cO(n+e) dO(n*e)考核鄰接表的基本特點(diǎn)1.165.0設(shè)有一棵哈夫曼樹的節(jié)點(diǎn)總數(shù)為35，則該哈夫曼樹共有（A ）個(gè)葉子結(jié)點(diǎn)。您答對(duì)了 a1

17、8 b20 c35 d30具有n個(gè)葉子結(jié)點(diǎn)（外部結(jié)點(diǎn)）的哈夫曼樹具有n-1個(gè)內(nèi)部結(jié)點(diǎn)。根據(jù)這個(gè)性質(zhì)可以計(jì)算出本題的葉子結(jié)點(diǎn)數(shù)為18。1.175.0深度為k的二叉樹至多有（C ）您答對(duì)了 a2k個(gè)結(jié)點(diǎn) b2k-1個(gè)結(jié)點(diǎn) c2k-1個(gè)結(jié)點(diǎn) d2k-1-1個(gè)結(jié)點(diǎn)當(dāng)二叉樹為滿二叉樹時(shí)，具有最多的結(jié)點(diǎn)個(gè)數(shù)。1.185.0無向圖G=（V，E），其中：V=a,b,c,d,e,f，E=（a,b），（a,e），（a,c），（b,e），（c,f），（f,d），（e,d），對(duì)該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是（C）。您答對(duì)了 aa,b,e,c,d,f ba,c,f,e,b,d ca,e,d,f,c,b d

18、a,e,b,c,f,d考核深度優(yōu)先遍歷的基本思想1.195.0按照二叉樹的定義，具有三個(gè)結(jié)點(diǎn)的二叉樹有（A ）。您答對(duì)了 a5種 b4種 c3種 d6種二叉樹嚴(yán)格區(qū)分左、右子樹，根據(jù)定義易知具有三個(gè)結(jié)點(diǎn)的二叉樹共有5種。1.205.0在按層次遍歷二叉樹的算法中，需要借助的輔助數(shù)據(jù)結(jié)構(gòu)是（A）。您答對(duì)了 a隊(duì)列 b棧 c線性表 d有序表層次遍歷二叉樹需要用到隊(duì)列結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)-階段測評(píng)41.單選題 1.15.0在下列各棵二叉樹中，二叉排序樹是(B)。您答對(duì)了 aA bB cC dD1.25.0若需在O（nlogn）的時(shí)間內(nèi)完成對(duì)數(shù)組的排序，且要求排序算法是穩(wěn)定的，則可選擇的排序方法是（B）。您答

19、對(duì)了 a堆排序 b歸并排序 c快速排序 d直接插入排序考核各種排序算法的穩(wěn)定性與時(shí)間復(fù)雜度1.35.0對(duì)關(guān)鍵字序列(56，23，78，92，88，67，19，34)進(jìn)行增量為3的一趟希爾排序的結(jié)果為(D )。您答對(duì)了 a(19，23，56，34，78，67，88，92) b(23，56，78，66，88，92，19，34) c(19，23，34，56，67，78，88，92) d(19，23，67，56，34，78，92，88)本題考核希爾排序的基本思想。1.45.0設(shè)二叉排序樹中關(guān)鍵字由1至1000的整數(shù)構(gòu)成，現(xiàn)要檢索關(guān)鍵字為363的結(jié)點(diǎn)，下述關(guān)鍵字序列哪一個(gè)不可能是二叉排序樹上搜索到的序列

20、（C ）。您答對(duì)了 a2， 252， 401， 398， 330， 344， 397， 363 b924， 220， 911， 244， 898， 258， 362， 363 c952， 202， 911， 240， 912， 245， 363 d2， 399， 387， 219， 266， 382， 381， 278， 363本題考核二分查找的基本思想。1.55.0在待排關(guān)鍵字序列基本有序的前提下，效率最高的排序方法是(A )。您答對(duì)了 a直接插入排序 b快速排序 c直接選擇排序 d歸并排序直接插入排序在序列基本有序的情況下，具有較好的排序效率。本題答案選A。1.65.0希爾排序的增量序列必

21、須是（ C）。您答對(duì)了 a遞增的 b隨機(jī)的 c遞減的 d非遞減的希爾排序是一種改進(jìn)的插入排序，要求增量序列必須遞減的。1.75.0有數(shù)據(jù)53，30，37，12，45，24，96，從空二叉樹開始逐步插入數(shù)據(jù)形成二叉排序樹，若希望高度最小，則應(yīng)該選擇下列（A）的序列輸入。您答對(duì)了 a37,24,12,30,53,45,96 b45,24,53,12,37,96,30 c12,24,30,37,45,53,96 d30,24,12,37,45,96,53考核二叉排序樹的建立算法1.85.0查找運(yùn)算主要是對(duì)關(guān)鍵字的（C ）。您答對(duì)了 a移位 b交換 c比較 d定位查找運(yùn)算主要是通過比較判斷是否查找成功

22、。1.95.0已知一組關(guān)鍵字為25,48,36,72,79,82,23,40,16,35，其中每相鄰兩個(gè)為有序子序列。采用歸并排序?qū)@些子序列進(jìn)行一趟兩兩歸并的結(jié)果是( C)。您答對(duì)了 a25,36,48,72,16,23,35,40,79,82 b25,36,48,72,16,23,40,79,82,35 c25,36,48,72,23,40,79,82,16,35 d16,23,25,35,36,40,48,72,79,82本題考核歸并排序的基本思想。1.105.0對(duì)于哈希函數(shù)H(key)=key%13，被稱為同義詞的關(guān)鍵字是（C）。您答對(duì)了 a35和41 b23和39 c25和51 d15和44考核散列存儲(chǔ)中同義詞的基本概念1.115.0在下列算法中，（B）算法可能出現(xiàn)下列情況：在最后一趟開始之前，所有的元素都不在其最終的位置上。您答對(duì)了 a堆排序 b插入排序 c冒泡排序 d快速排序本題考核插入排序的基本思想。1.125.0適用于折半查找的表的存儲(chǔ)方式及元素排列要求為（D）。您答對(duì)了 a鏈?zhǔn)椒绞酱鎯?chǔ)，元素?zé)o序 b鏈?zhǔn)椒绞酱鎯?chǔ)，元素有序 c順序方式存儲(chǔ)，元素?zé)o序 d順序方式存儲(chǔ)，元素有序考核折半查找的基本概念1.135.0下列說法錯(cuò)誤的是（D）。您答對(duì)了 a冒泡排序在數(shù)據(jù)有序的情況下具有最少的比較