1.數(shù)據(jù)結(jié)構(gòu)-階段測評1計算機識別、存儲和加工處理的對象被統(tǒng)稱為(A)A.數(shù)據(jù)B.數(shù)據(jù)元素C.數(shù)據(jù)結(jié)構(gòu)D.數(shù)據(jù)類型本題考核數(shù)據(jù)的基本概念非空的循環(huán)單鏈表head的尾結(jié)點(由p所指向)滿足(C)。A.p->next==NULLB.p==NULLC.p->next==headD.p==head本題考核循環(huán)單鏈表的基本特點。若長度為n的線性表采用順序存儲結(jié)構(gòu)存儲，在第i個位置上插入一個新元素的時間復雜度為(A)。A.O(n)B.O(1)C.O(n2)D.O(n3)本題考核順序表的插入運算的時間復雜度。下面程序段中a[i][j]=O語句執(zhí)行的時間復雜度是(D)。for(i=0;i<n;i++)for(j=1;j<m;j++)a[i][j]=O；A>O(n)B.0(m+n+1)C.0(m+n)D.0(m*n)本題考核時間復雜度的計算方法在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并保持單鏈表仍然有序的時間復雜度是(B)。A.O(1)B.O(n)C.O(n2)D.O(nlog2n)因要保持有序，所以需要查找插入結(jié)點的位置，而在鏈表中查找結(jié)點位置的時間復雜度為O(n)，所以本題選Bo在一個長度為n的順序表中刪除第i個元素(1<=i<=n)時，需向前移動(A)個元素。A.n-iB.n-i+1C.n-i-1D.i考核順序表的基本操作設(shè)順序表有10個元素，則在第5個元素前插入一個元素所需移動元素的個數(shù)為(B)。A.5B.6 C.7D.9在第5個元素前插入元素需要將第5個元素開始的所有元素后移，所以本題答案為B。算法指的是(D)您答對了A.計算機程序B.解決問題的計算方法C.排序算法D.解決問題的有限運算序列考核算法的基本概念線性表采用鏈式存儲時，結(jié)點的存儲地址(B)A.必須是不連續(xù)的B.連續(xù)與否均可C.必須是連續(xù)的D.和頭結(jié)點的存儲地址相連續(xù)鏈式存儲分配的結(jié)點在內(nèi)存連續(xù)與不連續(xù)均可，所以答案選B。對于只在表的首、尾兩端進行插入操作的線性表，宜采用的存儲結(jié)構(gòu)為(C)。A.順序表B.用頭指針表示的單循環(huán)鏈表C.用尾指針表示的單循環(huán)鏈表D.單鏈表本題考核循環(huán)單鏈表的基本特點。在長度為n的順序表的第i(lWiWn+1)個位置上插入一個元素，元素的移動次數(shù)為(A)。A.n-i+1B.n-iC.iD.i-1本題考核順序表的插入運算。線性表若采用鏈式存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址(D)。A.必須是連續(xù)的B.部分地址必須是連續(xù)的C.一定是不連續(xù)的D.連續(xù)不連續(xù)都可以考核鏈式存儲結(jié)構(gòu)的特點在單鏈表中，指針p指向元素為x的結(jié)點，實現(xiàn)“刪除x的后繼”的語句是(B)。A.p=p->next;B.p->next=p->next->next;C.p->next=p;D.p=p->next->next;本題考核單鏈表結(jié)點刪除的基本操作在一個單鏈表中，若刪除p所指結(jié)點的后續(xù)結(jié)點，則執(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;考核單鏈表的刪除操作若結(jié)點的存儲地址與其關(guān)鍵字之間存在某種映射關(guān)系，則稱這種存儲結(jié)構(gòu)為(D)。A.順序存儲結(jié)構(gòu)B.鏈式存儲結(jié)構(gòu)C.索引存儲結(jié)構(gòu)D.散列存儲結(jié)構(gòu)本題考核散列存儲的基本概念若將數(shù)據(jù)結(jié)構(gòu)形式定義為二元組(K,R),其中K是數(shù)據(jù)元素的有限集合，則R是K上(D)。A.操作的有限集合B.映象的有限集合C.類型的有限集合D.關(guān)系的有限集合本題考核數(shù)據(jù)結(jié)構(gòu)的基本概念將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時間復雜度為(C)。A.O(1)B.O(n)C.O(m)D.O(m+n)本題考核單鏈表的基本特點關(guān)于棧和隊列的說法中正確的是(A)。A.棧和隊列都是線性結(jié)構(gòu)B.棧是線性結(jié)構(gòu)，隊列不是線性結(jié)構(gòu)C.棧不是線性結(jié)構(gòu)，隊列是線性結(jié)構(gòu)D.棧和隊列都不是線性結(jié)構(gòu)棧和隊列都是一種特殊的線性表。判定“帶頭結(jié)點的鏈隊列為空”的條件是(C)。A.Q.front==NULLB.Q.rear==NULLC.Q.front==Q.rearD.Q.front!=Q.rear本題考核鏈隊列的基本概念，答案選Co設(shè)棧S和隊列Q的初始狀態(tài)為空，元素a,b,c,d,e,f,g依次入棧S。若每個元素出棧后立即進入隊列Q,且7個元素出列的順序是b,d,c,f,e,a,g,則棧S的容量至少是(C)。A.1B.2C.3D.4本題考核棧與隊列的性質(zhì)以及進棧、出棧、進隊、出隊等基本操作方法。2.數(shù)據(jù)結(jié)構(gòu)-階段測評2引起循環(huán)隊列隊頭位置發(fā)生變化的操作是(A)oA.出隊B.入隊C.取隊頭元素D.取隊尾元素本題考核循環(huán)隊列的基本操作。從廣義表L=(((e),c,d))中分解得到原子c的操作為(B)。A.head(head(head(L)))B.head(tail(head(L)))C.tail(head(head(L)))D.tail(tail(head(L)))本題考核廣義表的基本操作。對矩陣壓縮存儲是為了(B)oA.方便運算B.節(jié)省空間C.方便存儲D.提高運算速度壓縮存儲就是為了節(jié)省存儲空間。順序循環(huán)隊列中(數(shù)組的大小為6),隊頭指示front和隊尾指示rear的值分別為3和0,當從隊列中刪除1個元素，再插入2個元素后，front和rear的值分別為(D)。A.5和1B.2和4C.1和5D.4和2本題考核順序循環(huán)隊列的基本特點。設(shè)棧S和隊列Q的初始狀態(tài)為空，元素a,b,c,d,e,f,g依次入棧S。若每個元素出棧后立即進入隊列Q,且7個元素出列的順序是b,d,c,f,e,a,g,則棧S的容量至少是(C)。A.1B.2C.3D.4本題考核棧與隊列的性質(zhì)以及進棧、出棧、進隊、出隊等基本操作方法。隊列和棧的主要區(qū)別是(A)。A.限定插入和刪除的位置不同B.存儲結(jié)構(gòu)不同C.所包含的運算個數(shù)不同D.邏輯結(jié)構(gòu)不同本題考核棧與隊列的基本特點表達式a*(b+c)-d的后綴表達式是(B)。A.abc*d+-B.abc+*d-C.abc*+d-D.-+*abcd本題考核中綴表達式轉(zhuǎn)后綴表達式的基本方法。& 棧是一種特殊的線性表，具有(B)性質(zhì)。A.先進先出B.先進后出C.后進后出D.順序進出考核棧的基本概念對廣義表L=((a,b),(c,d),(e,f))執(zhí)行操作tail(tail(L))的結(jié)果是(B)A.(e,f)B.((e,f))C.(f)D.()考核廣義表的基本操作設(shè)棧的輸入序列為(1、2、3、4)，則不可能的出棧序列為(C)。A.1243B.2134C.4312D.1432本題考核棧的進棧與出棧特點，根據(jù)先進后出、后進先出的特點，可知本題答案選C。操作系統(tǒng)的CPU管理程序為實現(xiàn)先來先服務(wù)的作業(yè)管理，需要設(shè)置一個存儲區(qū)，用于記錄當前用戶作業(yè)，這個存儲區(qū)的邏輯結(jié)構(gòu)是(B)。A.棧B.隊列C.樹D.圖本題考核隊列的基本特點。若進棧序列為1，2，3，4，5，6，且進棧和出棧可以穿插進行，則不可能出現(xiàn)的出棧序列是(C)。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ù)這個特點，可知本題答案為C。判定“帶頭結(jié)點的鏈隊列為空”的條件是(C)。A.Q.front==NULLB.Q.rear==NULLC.Q.front==Q.rearD.Q.front!=Q.rear本題考核鏈隊列的基本概念，答案選Co關(guān)于棧和隊列的說法中正確的是(A)。A.棧和隊列都是線性結(jié)構(gòu)B.棧是線性結(jié)構(gòu)，隊列不是線性結(jié)構(gòu)C.棧不是線性結(jié)構(gòu)，隊列是線性結(jié)構(gòu)D.棧和隊列都不是線性結(jié)構(gòu)棧和隊列都是一種特殊的線性表。已知循環(huán)隊列的存儲空間為數(shù)組data[21]，且當前隊列的頭指針和尾指針的值分別為8和3,則該隊列當前長度為(0A.5B.6C.16D.17考核順序循環(huán)隊列的特點從廣義表LS=((p,q),r,s)中分解出原子q的運算是(B)。A.tail(head(LS))B.head(tail(head(LS)))C.head(tail(⑸)D.tail(tail(head(LS)))本題考核廣義表的基本操作。鏈棧與順序棧相比，比較明顯的優(yōu)點是(D)。A.插入操作更加方便B.刪除操作更加方便C.不會出現(xiàn)下溢的情況D.不會出現(xiàn)上溢的情況鏈棧采用動態(tài)內(nèi)存分配，一般不會出現(xiàn)棧滿的情況，即一般不會出現(xiàn)上溢的情況。所以答案選Do將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時間復雜度為(C)。A.O(1)B.O(n)C.O(m)D.O(m+n)本題考核單鏈表的基本特點在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并保持單鏈表仍然有序的時間復雜度是(B)。A.0(1)B.O(n)C.O(n2)D.O(nlog2n)因要保持有序，所以需要查找插入結(jié)點的位置，而在鏈表中查找結(jié)點位置的時間復雜度為O(n)，所以本題選Bo下面程序段中a[i][j]=0語句執(zhí)行的時間復雜度是(D)。for(i=0;i<n;i++)for(j=1;j<m;j++)a[i][j]=0；A.0(n)B.0(m+n+1)C.0(m+n)D.0(m*n)本題考核時間復雜度的計算方法3.數(shù)據(jù)結(jié)構(gòu)-階段測評3以二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，有具有n個結(jié)點的二叉鏈表中(n〉0)，空鏈域的個數(shù)為(B)。A.2n-1 B.n+1C.n-1D.2n+1n個結(jié)點的二叉樹共有n-1條邊，所以空鏈域的個數(shù)為n+1。若鄰接表中有奇數(shù)個表結(jié)點，則一定(D)。A.圖中有奇數(shù)個頂點B.圖中有偶數(shù)個頂點C.圖為無向圖D.圖為有向圖本題考核圖的鄰接表存儲結(jié)構(gòu)及其特點。一棵完全二叉樹有999個結(jié)點，它的深度為(B)。A.9B.10C.11D.12本題考核完全二叉樹的性質(zhì)。一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)為(D)。A.250B.500 C.254D.501本題考核完全二叉樹的性質(zhì)n個頂點的強連通圖中至少含有(B)。A.n-1條有向邊B.n條有向邊C.n(n-1)/2條有向邊D.n(n-1)條有向邊本題考核強連通圖的基本性質(zhì)。無向圖中一個頂點的度是指圖中(B)。A.通過該頂點的簡單路徑數(shù)B.與該頂點相鄰接的頂點數(shù)C.通過該頂點的回路數(shù)D.與該頂點連通的頂點數(shù)本題考核頂點的度的基本概念。下列哪一個選項不是下圖所示有向圖的拓撲排序結(jié)果(C)。A.AFBCDEB.FABCDEC.FACBDED.FADBCE本題考核圖的拓撲排序基本思想。設(shè)有一個有向圖如圖所示，請指出下列哪個序列不是該圖的拓撲排序序列(C)。

A.EAFBGDCB.AEBCGFDC.ABCGEFDD.EABGFCD本題考核圖的拓撲排序基本思想。無向圖的鄰接矩陣是一個(A)A.對稱矩陣B.零矩陣C.上三角矩陣D.對角矩陣由于是無向圖，所以該圖的鄰接矩陣是對稱矩陣。如果某圖的鄰接矩陣是對角線元素均為零的上三角矩陣，則此圖是(D)。A.有向完全圖B.連通圖C.強連通圖D.有向無環(huán)圖本題考核圖的鄰接矩陣存儲結(jié)構(gòu)的基本特點。設(shè)有向圖的鄰接鏈表如圖所示，則該圖的邊的數(shù)目是(A)。A.6B7C.8D.12本題考核圖的鄰接表存儲結(jié)構(gòu)的基本特點。下列陳述中正確的是(D)A.二叉樹是度為2的有序樹B.二叉樹中結(jié)點只有一個孩子時無左右之分C.二叉樹中必有度為2的結(jié)點D.二叉樹中最多只有兩棵子樹，并且有左右之分本題考核二叉樹與度為二的樹的區(qū)別，答案選Do對于一棵具有n個節(jié)點，度為4的樹來說，(A)oA.樹的高度至多是n-3B.樹的高度至多是n-4C.第i層至多有4(i-1)個節(jié)點D.至少在某一層上正好有4個節(jié)點本題考核樹的基本性質(zhì)。一棵含18個結(jié)點的二叉樹的高度至少為(C)oA.3B.4C.5D.6當二叉樹為完全二叉樹時該樹具有最小高度。本題考核二叉排序樹的基本概念。假設(shè)一個有n個頂點和e條弧的有向圖用鄰接表表示，則刪除與某個頂點vi相關(guān)的所有弧的時間復雜度是(B)A.O(n)B.O(e)C.O(n+e)D.O(n*e)考核鄰接表的基本特點設(shè)有一棵哈夫曼樹的節(jié)點總數(shù)為35,則該哈夫曼樹共有(A)個葉子結(jié)點。A.18B.20 C.35D.30具有n個葉子結(jié)點(外部結(jié)點)的哈夫曼樹具有n-1個內(nèi)部結(jié)點。根據(jù)這個性質(zhì)可以計算出本題的葉子結(jié)點數(shù)為18o深度為k的二叉樹至多有(C)A.2k個結(jié)點B.2k-1個結(jié)點C.2k-1個結(jié)點D.2k-1-1個結(jié)點當二叉樹為滿二叉樹時，具有最多的結(jié)點個數(shù)。無向圖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)}，對該圖進行深度優(yōu)先遍歷，得到的頂點序列正確的是(C)o

A.a,b,e,c,d,fB.a,c,f,e,b,dC.a,e,d,f,c,bD.a,e,b,c,f,d考核深度優(yōu)先遍歷的基本思想按照二叉樹的定義，具有三個結(jié)點的二叉樹有（A）。A.5種B.4種C.3種D.6種二叉樹嚴格區(qū)分左、右子樹，根據(jù)定義易知具有三個結(jié)點的二叉樹共有5種。在按層次遍歷二叉樹的算法中，需要借助的輔助數(shù)據(jù)結(jié)構(gòu)是（A）。A.隊列B.棧C.線性表D.有序表層次遍歷二叉樹需要用到隊列結(jié)構(gòu)。4.數(shù)據(jù)結(jié)構(gòu)-階段測評41.在下列各棵二叉樹中，二叉排序樹是（B）。A.AB.BC.CD.D若需在O（nlogn）的時間內(nèi)完成對數(shù)組的排序，且要求排序算法是穩(wěn)定的，則可選擇的排序方法是（B）。A.堆排序B.歸并排序C.快速排序D.直接插入排序考核各種排序算法的穩(wěn)定性與時間復雜度對關(guān)鍵字序列（56,23，78，92，88，67,19,34）進行增量為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）本題考核希爾排序的基本思想。設(shè)二叉排序樹中關(guān)鍵字由1至1000的整數(shù)構(gòu)成，現(xiàn)要檢索關(guān)鍵字為363的結(jié)點，下述關(guān)鍵字序列哪一個不可能是二叉排序樹上搜索到的序列（C）。A.2， 252， 401， 398， 330， 344， 397， 363B.924， 220， 911， 244， 898， 258， 362， 363C.952, 202, 911, 240, 912, 245, 363D.2, 399, 387, 219, 266, 382, 381, 278, 363本題考核二分查找的基本思想。在待排關(guān)鍵字序列基本有序的前提下，效率最高的排序方法是（A）。A.直接插入排序B.快速排序C.直接選擇排序D.歸并排序直接插入排序在序列基本有序的情況下，具有較好的排序效率。本題答案選A。希爾排序的增量序列必須是（C）。A.遞增的B.隨機的C.遞減的D.非遞減的希爾排序是一種改進的插入排序，要求增量序列必須遞減的。有數(shù)據(jù)｛53，30，37，12，45，24，96｝，從空二叉樹開始逐步插入數(shù)據(jù)形成二叉排序樹，若希望高度最小，則應該選擇下列（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考核二叉排序樹的建立算法&查找運算主要是對關(guān)鍵字的（C）。A.移位B.交換C.比較D.定位

查找運算主要是通過比較判斷是否查找成功。已知一組關(guān)鍵字為{[25,48],[36,72],[79,82],[23,40],[16,35]}，其中每相鄰兩個為有序子序列。采用歸并排序?qū)@些子序列進行一趟兩兩歸并的結(jié)果是（C）。A.{25,36,48,72,16,23,35,40,79,82}B.{25,36,48,72,16,23,40,79,82,35}C.{25,36,48,72,23,40,79,82,16,35}D.{16,23,25,35,36,40,48,72,79,82}本題考核歸并排序的基本思想。對于哈希函數(shù)H（key）二key%13，被稱為同義詞的關(guān)鍵字是（C）。A.35和41B.23和39C.25和51D.15和44考核散列存儲中同義詞的基本概念在下列算法中，（B）算法可能出現(xiàn)下列情況：在最后一趟開始之前，所有的元素都不在其最終的位置上。A.堆排序B.插入排序C.冒泡排序D.快速排序本題考核插入排序的基本思想。適用于折半查找的表的存儲方式及元素排列要求為（D）。A.鏈式方式存儲，元