03數(shù)據(jù)結(jié)構(gòu)階段測(cè)評(píng)共80題

1、 1.數(shù)據(jù)結(jié)構(gòu)-階段測(cè)評(píng)1 1 .計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的對(duì)象被統(tǒng)稱為(A) A.數(shù)據(jù)B.數(shù)據(jù)元素C.數(shù)據(jù)Z構(gòu)D.數(shù)據(jù)類型本題考核數(shù)據(jù)的基本概念 2 .非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)(由p所指向)滿足(Q。 A.p-next=NULLB.p=NULIC.p-next=headD.p=head 本題考核循環(huán)單鏈表的基本特點(diǎn)。 3 .若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，在第i個(gè)位置上插入一個(gè)新元素的時(shí)間復(fù)雜度為(A)。 A.O(n)B.O(1)C.O(n2)D.O(n3) 本題考核順序表的插入運(yùn)算的時(shí)間復(fù)雜度。 4 .下面程序段中aij=0語(yǔ)句執(zhí)行的時(shí)間復(fù)雜度是(D)。 for(i=0;

2、in;i+) for(j=1;jO(n)B.O(m+n+1)C.O(m+n)D.O(m*n) 本題考核時(shí)間復(fù)雜度的計(jì)算方法 5 .在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并保持單鏈表仍然有序的時(shí)間復(fù)雜度是(B)。 A.O(1)B.O(n)C.O(n2)D.O(nlog2n) 因要保持有序，所以需要查找插入結(jié)點(diǎn)的位置，而在鏈表中查找結(jié)點(diǎn)位置的時(shí)間復(fù)雜度為O(n),所以本題選Bo 6 .在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素(1=inext;B.p-next=p-next-next;C.p-next=p;D.p=p-next-next;本題考核單鏈表結(jié)點(diǎn)刪除的基本操作 14 .在一個(gè)單鏈表中

3、，若刪除p所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行(A)。 A.p-next=p-next-next;B.p=p-next;p-next=p-next-next;C.p-next=p-next;D.p=p-next-next;考核單鏈表的刪除操作 15 .若結(jié)點(diǎn)的存儲(chǔ)地址與其關(guān)鍵字之間存在某種映射關(guān)系，則稱這種存儲(chǔ)結(jié)構(gòu)為(D)。 A.順序存儲(chǔ)結(jié)構(gòu)B.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)C.索引存儲(chǔ)結(jié)構(gòu)D.散列存儲(chǔ)結(jié)構(gòu)本題考核散列存儲(chǔ)的基本概念 16 .若將數(shù)據(jù)結(jié)構(gòu)形式定義為二元組(K,R),其中K是數(shù)據(jù)元素的有限集合，則R是K上(D)。 A.操作的有限集合B.映象的有限集合C.類型的有限集合D.關(guān)系的有限集合本題考核數(shù)據(jù)結(jié)構(gòu)的基本

4、概念 17 .將長(zhǎng)度為n的單鏈表鏈接在長(zhǎng)度為m的單鏈表之后的算法的時(shí)間復(fù)雜度為(C)。 A.O(1)B.O(n)C.O(m)D.O(m+n)本題考核單鏈表的基本特點(diǎn) 18 .關(guān)于棧和隊(duì)列的說(shuō)法中正確的是(A)。 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ì)列都是一種特殊的線性表。 19 .判定“帶頭結(jié)點(diǎn)的鏈隊(duì)列為空”的條件是(C)。 A.Q.front=NULLB.Q.rear=NULLC.Q.front=Q.rearD.Q.front!=Q.rear本題考核鏈隊(duì)列的基本概念，答案選Co 20 .設(shè)棧S和隊(duì)列Q的

5、初始狀態(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)。 A.1B.2C.3D.4 本題考核棧與隊(duì)列的性質(zhì)以及進(jìn)棧、出棧、進(jìn)隊(duì)、出隊(duì)等基本操作方法。 21 數(shù)據(jù)結(jié)構(gòu)-階段測(cè)評(píng)2 1 .引起循環(huán)隊(duì)列隊(duì)頭位置發(fā)生變化的操作是(A)。 A.出隊(duì)B.入隊(duì)C取隊(duì)頭元素D取隊(duì)尾元素本題考核循環(huán)隊(duì)列的基本操作。 2 .從廣義表L=(e),c,d)中分解得到原子c的操作為(B)。 A.head(head(head(L)B.head(tail(head(L)C.tail(head(head(L)D.ta

6、il(tail(head(L)本題考核廣義表的基本操作。| 3 .對(duì)矩陣壓縮存儲(chǔ)是為了(B)。 A.方便運(yùn)算B.節(jié)省空間C方便存儲(chǔ)D.提高運(yùn)算速度壓縮存儲(chǔ)就是為了節(jié)省存儲(chǔ)空間。 4 .順序循環(huán)隊(duì)列中(數(shù)組的大小為6),隊(duì)頭指示front和隊(duì)尾指示rear的值分別為3和0,當(dāng)從隊(duì)列中刪除1個(gè) 元素，再插入2個(gè)元素后，front和rear的值分別為(D)。 A.5和1B.2和4C.1和5D.4和2本題考核順序循環(huán)隊(duì)列的基本特點(diǎn)。 5 .設(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的容

7、量至少是(C)。 A.1B.2C.3D.4 本題考核棧與隊(duì)列的性質(zhì)以及進(jìn)棧、出棧、進(jìn)隊(duì)、出隊(duì)等基本操作方法。 6 .隊(duì)列和棧的主要區(qū)別是(A)。 A.限定插入和刪除的位置不同B.存儲(chǔ)結(jié)構(gòu)不同C.所包含的運(yùn)算個(gè)數(shù)不同D.邏輯結(jié)構(gòu)不同 本題考核棧與隊(duì)列的基本特點(diǎn)| 7 .表達(dá)式a*(b+c)-d的后綴表達(dá)式是(B)。 A.abc*d+-B.abc+*d-C.abc*+d-D.-+*abcd本題考核中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式的基本方法。 8 .棧是一種特殊的線性表，具有(B)性質(zhì)。 A.先進(jìn)先出B.先進(jìn)后出C后進(jìn)后出D.順序進(jìn)出 考核棧的基本概念 9 .對(duì)廣義表L=(a,b),(c,d),(e,f)執(zhí)行

8、操作tail(tail(L)的結(jié)果是(B) A.(e,f)B.(e,f)C.(f)D.()考核廣義表的基本操作 10 .設(shè)棧的輸入序列為(1、2、3、4),則不可能的出棧序列為(C)。 A.1243B.2134C.4312D.1432 本題考核棧的進(jìn)棧與出棧特點(diǎn)，根據(jù)先進(jìn)后出、后進(jìn)先出的特點(diǎn)，可知本題答案選Co 11 .操作系統(tǒng)的CPU管理程序?yàn)閷?shí)現(xiàn)先來(lái)先服務(wù)的作業(yè)管理，需要設(shè)置一個(gè)存儲(chǔ)區(qū)，用于記錄當(dāng)前用戶作業(yè)，這個(gè)存 儲(chǔ)區(qū)的邏輯結(jié)構(gòu)是(B)。 A.棧B.隊(duì)列C樹(shù)D.圖本題考核隊(duì)列的基本特點(diǎn)。 12 .若進(jìn)棧序列為1,2,3,4,5,6,且進(jìn)棧和出?？梢源┎暹M(jìn)行，則不可能出現(xiàn)的出棧序列是(C)

9、。 A.2,4,3,1,5,6B.4,3,2,1,5,6C.2,3,5,1,6,4D.3,2,4,1,6,5核具有先進(jìn)后出，后進(jìn)先出的特點(diǎn)，根據(jù)這個(gè)特點(diǎn)，可知本題答案為C。 13 .判定“帶頭結(jié)點(diǎn)的鏈隊(duì)列為空”的條件是(C)。 A.Q.front=NULLB.Q.rear=NULLC.Q.front=Q.rearD.Q.front!=Q.rear本題考核鏈隊(duì)列的基本概念，答案選Co 14 .關(guān)于棧和隊(duì)列的說(shuō)法中正確的是(A)。 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ì)列都是一種特殊的線性表。 15 .已知循環(huán)

10、隊(duì)列的存儲(chǔ)空間為數(shù)組data21，且當(dāng)前隊(duì)列的頭指針和尾指針的值分別為8和3,則該隊(duì)列當(dāng)前長(zhǎng)度 為(C) A.5B.6C.16D.17 考核順序循環(huán)隊(duì)列的特點(diǎn) 16 .從廣義表LS=(p,q),r,s)中分解出原子q的運(yùn)算是(B)。 A.tail(head(LS)B.head(tail(head(LS)C.head(tail(LS)D.tail(tail(head(LS)本題考核廣義表的基本操作。 17 .鏈棧與順序棧相比，比較明顯的優(yōu)點(diǎn)是(D)。 A.插入操作更加方便B.刪除操作更加方便C不會(huì)出現(xiàn)下溢的情況D.不會(huì)出現(xiàn)上溢的情況 鏈棧采用動(dòng)態(tài)內(nèi)存分配，一般不會(huì)出現(xiàn)棧滿的情況，即一般不會(huì)出現(xiàn)上

11、溢的情況。所以答案選Do 18 .將長(zhǎng)度為n的單鏈表鏈接在長(zhǎng)度為m的單鏈表之后的算法的時(shí)間復(fù)雜度為(C)。 A.O(1)B.O(n)C.O(m)D.O(m+n)本題考核單鏈表的基本特點(diǎn) 19 .在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并保持單鏈表仍然有序的時(shí)間復(fù)雜度是(B)。 A.O(1)B.O(n)C.O(n2)D.O(nlog2n) 因要保持有序，所以需要查找插入結(jié)點(diǎn)的位置，而在鏈表中查找結(jié)點(diǎn)位置的時(shí)間復(fù)雜度為O(n),所以本題選Bo 20 .下面程序段中aij=0語(yǔ)句執(zhí)行的時(shí)間復(fù)雜度是(D)。 for(i=0;in;i+) for(j=1;j0),空鏈域的個(gè)數(shù)為(B)。 A.2n-

12、1B.n+1C.n-1D.2n+1 n個(gè)結(jié)點(diǎn)的二叉樹(shù)共有n-1條邊，所以空鏈域的個(gè)數(shù)為n+1。 2 .若鄰接表中有奇數(shù)個(gè)表結(jié)點(diǎn)，則一定(D)。 A.圖中有奇數(shù)個(gè)頂點(diǎn)B.圖中有偶數(shù)個(gè)頂點(diǎn)C.圖為無(wú)向圖D.圖為有向圖 本題考核圖的鄰接表存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)。| 3 .一棵完全二叉樹(shù)有999個(gè)結(jié)點(diǎn)，它的深度為(B)。 A.9B.10C.11D.12 本題考核完全二叉樹(shù)的性質(zhì)。 4 .一棵完全二叉樹(shù)上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)為(D)。 A.250B.500C.254D.501 本題考核完全二叉樹(shù)的性質(zhì) 5 .n個(gè)頂點(diǎn)的強(qiáng)連通圖中至少含有(B)。 A.n-1條有向邊B.n條有向邊C.n(n-1)

13、/2條有向邊D.n(n-1)條有向邊 本題考核強(qiáng)連通圖的基本性質(zhì)。 6 .無(wú)向圖中一個(gè)頂點(diǎn)的度是指圖中(B)。 A.通過(guò)該頂點(diǎn)的簡(jiǎn)單路徑數(shù)B.與該頂點(diǎn)相鄰接的頂點(diǎn)數(shù)C.通過(guò)該頂點(diǎn)的回路數(shù)D.與該頂點(diǎn)連通的頂點(diǎn)數(shù) 本題考核頂點(diǎn)的度的基本概念。 7 .下列哪一個(gè)選項(xiàng)不是下圖所示有向圖的拓?fù)渑判蚪Y(jié)果(C)。 A.AFBCDEB.FABCDEC.FACBDED.FADBCE本題考核圖的拓?fù)渑判蚧舅枷搿?8 .設(shè)有一個(gè)有向圖如圖所示，請(qǐng)指出下列哪個(gè)序列不是該圖的拓?fù)渑判蛐蛄?C)。 A.EAFBGDCB.AEBCGFDC.ABCGEFDD.EABGFCD 本題考核圖的拓?fù)渑判蚧舅枷搿?9 .無(wú)向圖的

14、鄰接矩陣是一個(gè)(A) A.對(duì)稱矢I陣B.零矩陣C上三角矢I陣D.對(duì)角矩陣 由于是無(wú)向圖，所以該圖的鄰接矩陣是對(duì)稱矩陣。 10 .如果某圖的鄰接矩陣是對(duì)角線元素均為零的上三角矩陣，則此圖是(D)。 A.有向完全圖B.連通圖C強(qiáng)連通圖D.有向無(wú)環(huán)圖 本題考核圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)的基本特點(diǎn)。 11 .設(shè)有向圖的鄰接鏈表如圖所示，則該圖的邊的數(shù)目是(A)。 A.6B7C.8D.12 本題考核圖的鄰接表存儲(chǔ)結(jié)構(gòu)的基本特點(diǎn)。 12 .下列陳述中正確的是(D) A.二叉樹(shù)是度為2的有序樹(shù)B.二叉樹(shù)中結(jié)點(diǎn)只有一個(gè)孩子時(shí)無(wú)左右之分 C二叉樹(shù)中必有度為2的結(jié)點(diǎn)D.二叉樹(shù)中最多只有兩棵子樹(shù)，并且有左右之分 本題考核

15、二叉樹(shù)與度為二的樹(shù)的區(qū)別，答案選D。 13 .對(duì)于一棵具有n個(gè)節(jié)點(diǎn)，度為4的樹(shù)來(lái)說(shuō)，(A)。 A.樹(shù)的高度至多是n-3B.樹(shù)的高度至多是n-4 C第i層至多有4(i-1)個(gè)節(jié)點(diǎn)D.至少在某一層上正好有4個(gè)節(jié)點(diǎn) 本題考核樹(shù)的基本性質(zhì)。 14 .一棵含18個(gè)結(jié)點(diǎn)的二叉樹(shù)的高度至少為(C)。 A.3B.4C.5D.6 當(dāng)二叉樹(shù)為完全二叉樹(shù)時(shí)該樹(shù)具有最小高度。 本題考核二叉排序樹(shù)的基本概念。 15 .假設(shè)一個(gè)有n個(gè)頂點(diǎn)和e條弧的有向圖用鄰接表表示，則刪除與某個(gè)頂點(diǎn)vi相關(guān)的所有弧的時(shí)間復(fù)雜度是(B)。 A.O(n)B.O(e)C.O(n+e)D.O(n*e) 考核鄰接表的基本特點(diǎn) 16 .設(shè)有一棵哈夫

16、曼樹(shù)的節(jié)點(diǎn)總數(shù)為35,則該哈夫曼樹(shù)共有(A)個(gè)葉子結(jié)點(diǎn)。 A.18B.20C.35D.30 具有n個(gè)葉子結(jié)點(diǎn)(外部結(jié)點(diǎn))的哈夫曼樹(shù)具有n-1個(gè)內(nèi)部結(jié)點(diǎn)。根據(jù)這個(gè)性質(zhì)可以計(jì)算出本題的葉子結(jié)點(diǎn)數(shù)為18。 17 .深度為k的二叉樹(shù)至多有(C) A.2k個(gè)結(jié)點(diǎn)B.2k-1個(gè)結(jié)點(diǎn)C.2k-1個(gè)結(jié)點(diǎn)D.2k-1-1個(gè)結(jié)點(diǎn) 當(dāng)二叉樹(shù)為滿二叉樹(shù)時(shí)，具有最多的結(jié)點(diǎn)個(gè)數(shù)。 18 .無(wú)向圖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)。 A.a,b,e,c,d,fB.a,

17、c,f,e,b,dC.a,e,d,f,c,bD.a,e,b,c,f,d 考核深度優(yōu)先遍歷的基本思想 19 .按照二叉樹(shù)的定義，具有三個(gè)結(jié)點(diǎn)的二叉樹(shù)有（A）。 A.5種B.4種C.3種D.6種 二叉樹(shù)嚴(yán)格區(qū)分左、右子樹(shù)，根據(jù)定義易知具有三個(gè)結(jié)點(diǎn)的二叉樹(shù)共有5種。 20 .在按層次遍歷二叉樹(shù)的算法中，需要借助的輔助數(shù)據(jù)結(jié)構(gòu)是（A）。 A.隊(duì)列B.棧C線性表D.有序表 層次遍歷二叉樹(shù)需要用到隊(duì)列結(jié)構(gòu)。 21 數(shù)據(jù)結(jié)構(gòu)-階段測(cè)評(píng)4 1.在下列各棵二叉樹(shù)中，二叉排序樹(shù)是（B）。 A.AB.BC.CD.D 2 .若需在O（nlogn）的時(shí)間內(nèi)完成對(duì)數(shù)組的排序，且要求排序算法是穩(wěn)定的，則可選擇的排序方法是（

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

19、 A.2,252,401,398,330,344,397,363B.924,220,911,244,898,258,362,363 C.952,202,911,240,912,245,363D.2,399,387,219,266,382,381,278,363 本題考核二分查找的基本思想。 5 .在待排關(guān)鍵字序列基本有序的前提下，效率最高的排序方法是（A）。 A.直接插入排序B.快速排序C.直接選擇排序D歸并排序直接插入排序在序列基本有序的情況下，具有較好的排序效率。本題答案選Ao 6 .希爾排序的增量序列必須是（C）。 A.遞增的B.隨機(jī)的C.遞減的D.非遞減的希爾排序是一種改進(jìn)的插入排序，

20、要求增量序列必須遞減的。 7 .有數(shù)據(jù)53,30,37,12,45,24,96,從空二叉樹(shù)開(kāi)始逐步插入數(shù)據(jù)形成二叉排序樹(shù)，若希望高度最小，則應(yīng)該選擇下列（A）的序列輸入。 A.37,24,12,30,53,45,96B.45,24,53,12,37,96,30C.12,24,30,37,45,53,96D.30,24,12,37,45,96,53考核二叉排序樹(shù)的建立算法 8 .查找運(yùn)算主要是對(duì)關(guān)鍵字的（C）。 A.移位B.交換C比較D.定位查找運(yùn)算主要是通過(guò)比較判斷是否查找成功。 9 .已知一組關(guān)鍵字為25,48,36,72,79,82,23,40,16,35,其中每相鄰兩個(gè)為有序子序列。采用

21、歸并排序 對(duì)這些子序列進(jìn)行一趟兩兩歸并的結(jié)果是（C）。 A.25,36,48,72,16,23,35,40,79,82B.25,36,48,72,16,23,40,79,82,35 C.25,36,48,72,23,40,79,82,16,35D.16,23,25,35,36,40,48,72,79,82本題考核歸并排序的基本思想。 10 .對(duì)于哈希函數(shù)H（key）=key%13,被稱為同義詞的關(guān)鍵字是（C）。 A.35和41B.23和39C.25和51D.15和44考核散列存儲(chǔ)中同義詞的基本概念 11 .在下列算法中，（B）算法可能出現(xiàn)下列情況：在最后一趟開(kāi)始之前，所有的元素都不在其最終的位置上。 A.堆排序B.插入排序C冒泡排序D.快速排序本題考核插入排序的基本思想。 12 .適用于折半查找的表的存儲(chǔ)方式及元素排列要求為（D）。 A.鏈?zhǔn)椒绞酱鎯?chǔ)，元素?zé)o序B.鏈?zhǔn)椒绞酱鎯?chǔ)，元素有序 C順序方式存儲(chǔ)，元素?zé)o序D.順序方式存儲(chǔ)，元素有序 考核折半查找的基本概念 13 .下列說(shuō)法錯(cuò)誤的是（D）。 A.冒泡排序在數(shù)據(jù)有序的情況下具有最少的比較次數(shù)。B.直接