數據結構復習資料

B.B.單鏈表A.數據的邏輯結構B.數據的存儲結構C.數據的邏輯結構和存儲結構D.數據的邏輯結構、存儲結構及其基本操作2.下面程序段的時間復雜度是()。for(i=0;ivm;i++)for(j=0;jvn;j++)a[i][j]=i*j；A.O(m2) B.O(n2)C.O(m*n)D.O(m+n)3.若一個線性表中最常用的操作是取第i個元素和找第i個元素的前趨元素，則采用()存儲方式最節(jié)省時間。A.順序表C.雙鏈表 D.單循環(huán)鏈表一個棧的輸入序列為：a，b，c，d，e,則棧的不可能輸出的序列是()。A.a,b,c,d,e B.d,e,c,b,aC.d,c,e,a,b D.e,d,c,b,a判斷一個循環(huán)隊列Q(最多n個元素)為滿的條件是()。A.Q->rear==Q->front B.Q->rear==Q->front+lC.Q->front==(Q->rear+1)%n D.Q->front==(Q->rear-1)%n串與普通的線性表相比較，它的特殊性體現在()。A.順序的存儲結構 B.鏈式存儲結構C.數據元素是一個字符 D.數據元素任意TOC\o"1-5"\h\z設廣義表L=((a，b，c))，貝此的長度和深度分別為( )。A.1和1 B.1和3 C.1和2 D.2和3設a,b為一棵二叉樹上的兩個結點，在中序遍歷時，a在b前面的條件是( )。A.a在b的右方 B.a在b的左方C.a是b的祖先 D.a是b的子孫12、對于具有n個頂點的圖，若采用鄰接矩陣表示，則該矩陣的大小為( )。A.n B.n2 C.n-1 D.(n-1)2在散列查找中，平均查找長度主要與( )有關。A.散列表長度 B.散列元素個數C.裝填因子 D.處理沖突方法()1.非空的雙向循環(huán)鏈表中任何結點的前驅指針均不為空。()2.線性表簡稱為“順序表”。()3.棧的特點是后進先出。()4.在有向圖G中，vV2,V]>和vV],V2>是兩條不同的邊。()5.圖G由兩個集合V(G)和R(G)所組成，其中頂點集V(G)和邊集R(G)都可以為空集。()6.完全二叉樹中的葉子結點只可能在最后兩層中出現。()7.圖的最小生成樹是唯一的。()8.中序遍歷二叉排序樹可以得到一個有序的序列。()9.向二叉排序樹中插入一個新結點時，新結點一定成為二叉排序樹的一個葉子結點。()10.堆排序是交換排序的一種。)的有限集合，R是D上數據結構被形式地定義為()的有限集合，R是D上的關系有限集合。（ ）被限定為只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表。設s='IAMATEACHER'其長度是（ ）。設一棵完全二叉樹有700個結點，則共有（ ）個葉子結點。29條邊的無向連通圖，至少有（）個頂點。假設有6行8列的二維數組A,每個元素占用6個字節(jié)，存儲器按字節(jié)編址。已知A的基地址為1000，計算：（10分）（1） 數組A共占用多少字節(jié)；（2） 數組A的最后一個元素的地址；⑶按行存儲時，元素A[3][6]的地址；⑷按列存儲時，元素A[3][6]的地址；已知一顆二叉樹的先序遍歷為：ABDGEHCF,中序遍歷為：GDBEHACF（1） 請畫出該二叉樹（3分）（2） 寫出該二叉樹的后序遍歷（3分）（3） 畫出該二叉樹的后序線索樹（4分）采用普里姆算法對下圖所示連通圖構造最小生成樹（10分）算法分析的兩個主要方面是（A.空間復雜度和時間復雜度C.可讀性和文檔性下面程序段的時間復雜度為（i=1;while（iv=n）

i=i*3;A.O（n） B.O（3n））。）。算法分析的兩個主要方面是（A.空間復雜度和時間復雜度C.可讀性和文檔性下面程序段的時間復雜度為（i=1;while（iv=n）

i=i*3;A.O（n） B.O（3n））。）。B.正確性和簡單性D.數據復雜性和程序復雜性C.O(log3n) D.O(n3)若長度為n的線性表采用順序存儲結構，在其第i個位置插入一個新元素算法的時間復雜度（A.O（log2n） B.O（1）一個棧的輸入序列為：a，b,A.a,b,c,d,e）。c,d，C.O（n） D.O（n2）e,則棧的不可能輸出的序列是（B.d,e,c,b,a）。C.e,d,c,a,b D.e,d,c,b,a5.設計一個判別表達式中括號是否配對的算法，采用（）數據結構最佳。A.順序表 B.鏈表 C.隊列 D.棧6.廣義表（（a）,a）的表尾是（ ）。A.a B.(a) C.() D.((a))二叉樹的深度為k,則二叉樹最多有( )個結點。A.2k B.2k-i C.2k-1 D.2k-1如果從無向圖的任一頂點出發(fā)進行一次深度優(yōu)先搜索即可訪問所有頂點，則該圖一定是()。A.完全圖 B.連通圖 C.有回路 D.—棵樹已知一個有序表為(1,2, 3, 4, 5,6, 7, 8, 9, 10，11)，則折半查找6需要比較( )次。A.1 B.2 C.3 D.4若需要在O(nlog2n)的時間內完成對數組的排序，且要求排序是穩(wěn)定的，則可選擇的排序方法是()。A.快速排序 B.堆排序 C.歸并排序 D.直接插入排序()1.線性表中的所有元素都有一個前驅元素和后繼元素。()2.對線性表進行插入和刪除操作時，不必移動結點。()3.不論是入隊列操作還是入棧操作，在順序存儲結構上都需要考慮“溢出”情況。()4.將插入和刪除限定在表的同一端進行的線性表稱為隊列。()5.稀疏矩陣的壓縮存儲可以用一個三元組表來表示稀疏矩陣中的非0元素。()6.哈夫曼樹中沒有度數為1的結點。()7.如果某個有向圖的鄰接表中第i條單鏈表為空，則第i個頂點的出度為零。()8.有向圖的鄰接表和逆鄰接表中表結點的個數不一定相等。()9.二分查找法必需在有序表上進行。()10.直接插入排序是穩(wěn)定的。數據結構被形式地定義為(D,R)，其中D是數據元素的有限集合，R是D上的( ，有限集合。棧是一種特殊的線性表，允許插入和刪除運算的一端稱為( )不允許插入和刪除運算的一端稱為棧底。設s='IAMASTUDENT'其長度是( )。設一棵完全二叉樹有500個結點，則共有( )個葉子結點。38條邊的無向連通圖，至少有( )個頂點。假設有6行7列的二維數組A,每個元素占用6個字節(jié)，存儲器按字節(jié)編址。已知A的基地址為1000，計算：(10分)數組A共占用多少字節(jié)；數組A的最后一個元素的地址；⑶按行存儲時，元素A[4][6]的地址；⑷按列存儲時，元素A[4][6]的地址；已知一顆二叉樹的先序遍歷為：ABDGECFH,中序遍歷為：DGBEACHF請畫出該二叉樹(3分)寫出該二叉樹的后序遍歷(3分)畫出該二叉樹的后序線索樹(4分)采用普里姆算法對下圖所示連通圖構造最小生成樹(10分)

具有線性結構的數據結構是(A.圖 B.樹 C.廣義表在下面的程序段中，對x的賦值語句的頻度為(for具有線性結構的數據結構是(A.圖 B.樹 C.廣義表在下面的程序段中，對x的賦值語句的頻度為(for(i=l;i>=n; i++)for(j=1；j>=n;j++)x:=x+1;A.O(2n) B.O(n) C.O(n2))。)。D.棧D.O(log2n)在表長為n的順序表中，當在任何位置刪除一個元素的概率相同時，刪除一個元素所需移動的平均個數為(A.(n-1)/2)。B.n/2一個棧的輸入序列為：a，b,A.a,b,c,d,eC.e,d,c,b,ac,d,(n+1)/2 D.ne,則棧的不可能輸出的序列是(B.d,e,c,b,ad,e,c,a,b)。)。一個隊列的入隊序列是1,2,3,4,則隊列的出隊序列是()。A.1,2,3,4 B.4,3,2,1C.1,4,3,2 D.3,4,1,2對廣義表L=((a,b),((c,d),(e,f)))執(zhí)行head(tail(head(tail(L))))操作的結果是( )。A.() B.e C.(e) D.(e,f)用順序存儲的方法，將完全二叉樹中所有結點按層逐個從左到右的順序存放在一維數組R[1..N]中，若結點R[i]有右孩子，貝I」其右孩子是( )。A.R⑵-1] B. R[2i+1]C.R[2i] D. R[2/i]采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于二叉樹的()。A.先序遍歷 B.中序遍歷C.后序遍歷 D.按層次遍歷已知一個有序表為(1,2,3,4,5,6,7,8,9,10,11),則折半查找3需要比較( )次。A.1 B.2 C.3 D.4下列排序方法中()方法是不穩(wěn)定的。A.冒泡排序 B.選擇排序C.堆排序 D.直接插入排序()1.線性表是由n(n〉0個相同類型元素組成的有限序列。()2.棧是一種后進先出的線性表。()3.二維數組是一種樹型結構。()4.二叉樹是樹的特殊形式。()5.對連通圖進行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點。()6.對于同一組待輸入的關鍵字集合，雖然各關鍵字的輸入次序不同，但得到的二叉排序樹都是相同的。（）7.冒泡排序算法是穩(wěn)定的排序。（）8.順序查找指的是在順序存儲結構上進行查找。（）9.從循環(huán)鏈表的任一結點出發(fā)，可以找到表中的所有結點。（）10.已知一棵二叉樹的前序序列和中序序列可以唯一地構造出該二叉樹。數據結構按邏輯結構可分為兩大類，它們分別是（ ）和樹狀結構和圖狀結構。棧是一種特殊的線性表，允許插入和刪除運算的一端稱為棧頂。不允許插入和刪除運算的一端稱為（ ）。設s='IAMAWORKER'其長度是（）。設一棵完全二叉樹有530個結點，則共有（ ）個葉子結點。40條邊的無向連通圖，至少有（）個頂點。假設有8行6列的二維數組A,每個元素占用4個字節(jié)，存儲器按字節(jié)編址。已知A的基地址為1000，計算：（10分）（1） 數組A共占用多少字節(jié)；（2） 數組A的最后一個元素的地址；⑶按行存儲時，元素A[3][4]的地址；⑷按列存儲時，元素A[3][4]的地址；已知一顆二叉樹的先序遍歷為：ABDGHCEF，中序遍歷為：GDHBAECF（1） 請畫出該二叉樹（3分）（2） 寫出該二叉樹的后序遍歷（3分）（3） 畫出該二叉樹的后序線索樹（4分）采用普里姆算法對下圖所示連通圖構造最小生成樹（10分）TOC\o"1-5"\h\z計算機中的算法指的是解決某一個問題的有限運算序列，它必須具備輸入、輸出、（ ）等5個特性。A.可執(zhí)行性、可移植性和可擴充性 B.可執(zhí)行性、有窮性和確定性C.確定性、有窮性和穩(wěn)定性 D.易讀性、穩(wěn)定性和確定性某算法的語句執(zhí)行頻度為（3n+nlog2n+n2+8），其時間復雜度表示（ ）。A.O（n） B.O（nlog2n） C.O（n2） D.O（log2n）在一個長度為n的順序表中，在第i個元素之前插入一個新元素時，需向后移動（）個元素。A.n-i B.n-i+1 C.n-i-1 D.i一個棧的輸入序列為：a，b，c，d，e,則棧的不可能輸出的序列是（ ）。A.a,b,c,d,e B.c,d,a,b,eC.e,d,c,b,a D.d,e,c,b,a隊列的插入操作是在（）。A.隊尾 B.隊頭 C.隊列任意位置D.隊頭元素后稀疏矩陣的常見壓縮存儲方法有（ ）兩種。A.二維數組和三維數組 B.三元組和散列表C.三元組和十字鏈表 D.散列表和十字鏈表在一棵具有5層的滿二叉樹中結點總數為（）。A.31 B.32 C.33D.16關鍵路徑是事件結點網絡中（）。A.從源點到匯點的最長路徑 B.從源點到匯點的最短路徑C.最長的回路 D.最短的回路已知一個有序表為（1,2,3,4,5,6,7,8,9,10,11）,則折半查找7需要比較（ ）次。A.1 B.2 C.3 D.4一個序列中有10000個元素，若只想得到其中前10個最小元素，則最好采用（）方法。A.快速排序 B.堆排序 C.插入排序 D.歸并排序（）1.調用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點。（）2.當向二叉排序樹中插入一個結點，則該結點一定成為葉子結點。（）3.線性表中的所有元素都有一個前驅元素和后繼元素。（）4.滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。（）5.設一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。（）6.鄰接表只能用于有向圖的存儲，鄰接矩陣對于有向圖和無向圖的存儲都適用。（）7.設一棵樹T可以轉化成二叉樹BT,則二叉樹BT中一定沒有右子樹。（）8.線性表的順序存儲結構比鏈式存儲結構更好。（）9.中序遍歷二叉排序樹可以得到一個有序的序列。（）10.快速排序是排序算法中平均性能最好的一種排序。數據結構按邏輯結構可分為兩大類，它們分別是線性結構和（ ）和圖狀結構。數據的存儲結構可用四種基本的存儲方法表示，它們分別是（ ）、鏈式、索引和散列。設s='IAMAGOODWORKER',其長度是（ ）。設一棵完全二叉樹有510個結點，則共有（ ）個葉子結點。20條邊的無向連通圖，至少有（）個頂點。假設有8行7列的二維數組A,每個元素占用4個字節(jié)，存儲器按字節(jié)編址。已知A的基地址為1000，計算：（10分）（1） 數組A共占用多少字節(jié)；（2） 數組A的最后一個元素的地址；⑶按行存儲時，元素A[4][5]的地址；⑷按列存儲時，元素A[4][5]的地址；已知一顆二叉樹的先序遍歷為：ABDGEHCF,中序遍歷為：GDBHEAFC（1） 請畫出該二叉樹（3分）（2） 寫出該二叉樹的后序遍歷（3分）（3） 畫出該二叉樹的后序線索樹（4分）采用普里姆算法對下圖所示連通圖構造最小生成樹（10分）算法是()。A.計算機程序 B.解決問題的計算方法C.排序算法 D.解決問題的有限運算序列某算法的語句執(zhí)行頻度為(3n+nlog2n+8)，其時間復雜度表示()。A.0(n) B.O(nlog2n) C.O(n2) D.O(log2n)將長度為n的單鏈表連接在長度為m的單鏈表之后的算法的時間復雜度為()。A.0(1) B.O(n) C.O(m) D.O(m+n)一個棧的輸入序列為：a，b,c,d,e,則棧的不可能輸出的序列是()。A.c,a,b,d,e B.a,b,c,d,eC.e,d,c,b,a D.d,e,c,b,a將遞歸算法轉換成對應的非遞歸算法時，通常需要使用()來保存中間結果。A.隊列B.棧C.鏈表D.樹6.空串和空格串。A.相同B.不相同C.可能相同D.無法確定7.在一棵具有10層的滿二叉樹中結點總數為()。A.1024B.1023C.10D.10008.無向圖的鄰接矩陣是一個()。A.對稱矩陣B.零矩陣C.上三角矩陣D.對角矩陣已知一個有序表為(1,2,3,4,5,6,7,8,9,10，11)，則折半查找8需要比較( )次。A.1 B.2 C.3 D.4排序時掃描待排序記錄序列，順次比較相鄰的兩個元素的大小，逆序時就交換位置，這是()排序的基本思想。A.堆排序 B.直接插入排序C.快速排序 D.冒泡排序()1.完全二叉樹中的葉子結點只可能在最后兩層中出現。()2.已知一棵二叉樹的前序序列和中序序列可以唯一地構造出該二叉樹。()3.哈夫曼樹中沒有度數為1的結點。()4.對于同一組待輸入的關鍵字集合，雖然各關鍵字的輸入次序不同，但得到的二叉排序樹都是相同的。()5.如果某個有向圖的鄰接表中第i條單鏈表為空，則第i個頂點的出度為丿一I二零。()6.稀疏矩陣的壓縮存儲可以用一個三元組表來表示稀疏矩陣中的非0元素。()7.直接插入排序是穩(wěn)定的。

（）8.對連通圖進行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點。（）9.二維數組和多維數組均不是特殊的線性結構。（）10.堆排序是交換排序的一種。數據結構按邏輯結構可分為兩大類，它們分別是線性結構和樹狀結構和（數據的存儲結構可用四種基本的存儲方法表示，它們分別是順序、（和散列。設s='IAMAGOODTEACHER',其長度是（ ）。設一棵完全二叉樹有520個結點，則共有（ ）個葉子結點。5.6條邊的無向連通圖，至少有（ ）個頂點。假設有7行6列的二維數組A,每個元素占用6個字節(jié)，存儲器按字節(jié)編址?；刂窞?000，計算：（10分）（1） 數組A共占用多少字節(jié)；（2） 數組A的最后一個元素的地址；⑶按行存儲時，元素A[5][4]的地址；⑷按列存儲時，元素A[5][4]的地址；已知一顆二叉樹的先序遍歷為：ABDECFGH，中序遍歷為：DBEACGFH（1） 請畫出該二叉樹（3分）（2） 寫出該二叉樹的后序遍歷（3分）（3） 畫出該二叉樹的后序線索樹（4分））。）、索引已知A的采用普里姆算法對下圖所示連通圖構造最小生成樹（）。）、索引已知A的C.數C.數()。抽象數據類型的三個組成部分分別為（ ）。A.數據對象、數據關系和基本操作 B.數據元素、邏輯結構和存儲結構據項、數據元素和數據類型 D.數據元素、數據結構和數據類型某算法的語句執(zhí)行頻度為（3n+log2n+8），其時間復雜度表示（）。A.O（n） B.O（nlog2n） C.O（n2） D.O（log2n）非空的循環(huán)單鏈表head的尾結點p滿足（）。A.p->next==head B.p->next==NULLC.p==NULL D.p==head一個棧的輸入序列為：a，b，c，d，e,則棧的不可能輸出的序列是（）。A.e,d,c,b,a B.a,b,c,d,eC.c,d,e,a,b D.d,e,c,b,a循環(huán)隊列的隊頭和隊尾指針分別為front和rear，貝U判斷循環(huán)隊列為空的條件是A.front==rear B.front==0C.rear==0D.front=rear+lC.rear==0一個非空廣義表的表頭（）。不可能是子表 B.只能是子表C.只能是原子 D.可以是子表或原子在一棵具有8層的滿二叉樹中結點總數為()。TOC\o"1-5"\h\zA.256 B.255 C.253 D.8下面()可以判斷出一個有向圖中是否有環(huán)(回路)。A.廣度優(yōu)先遍歷 B.拓撲排序C.求最短路徑 D.求關鍵路徑已知一個有序表為(1, 2, 3,4, 5, 6, 7,8,9, 10, 11),則折半查找11需要比較( )次。\o"CurrentDocument"A.1 B.2 C.3 D.4在對n個元素的序列進行排序時，堆排序所需要的附加存儲空間是( )。A.O(log2n) B.0(1) C.O(n) D.O(nlog2n)( )1.鏈表的每個結點中都恰好包含一個指針。( )2.鏈表的物理存儲結構具有同鏈表一樣的順序。( )3.線性表的每個結點只能是一個簡單類型,而鏈表的每個結點可以是一個復雜類型。( )4.在表結構中最常用的是線性表，棧和隊列不太常用。( )5.若二叉樹用二叉鏈表作存貯結構，則在n個結點的二叉樹鏈表中只有n—1個非空指針域。( )6.二叉樹中每個結點的兩棵子樹的高度差等于1。( )7.折半查找只適用于有序表，包括有序的順序表和鏈表。( )8. 一個圖的鄰接矩陣表示是惟一的。( )9.無向圖的鄰接矩陣一定是對稱矩陣。( )10.有向圖用鄰接表表示，頂點vi的度是對應頂點vj鏈表中結點個數。若以｛4,5,6,7,8｝作為權值構造哈夫曼樹，則該樹的帶權路徑長度為( )。數據的存儲結構可用四種基本的存儲方法表示，它們分別是順序、鏈式、( )和散列。設s='IAMAGOODREADER'其長度是()。設一棵完全二叉樹有521個結點，則共有( )個葉子結點。8條邊的無向連通圖，至少有( )個頂點。假設有5行8列的二維數組A,每個元素占用2個字節(jié)，存儲器按字節(jié)編址。已知A的基地址為1000，計算：(10分)數組A共占用多少字節(jié)；數組A的最后一個元素的地址；⑶按行存儲時，元素A[4][6]的地址；⑷按列存儲時，元素A[4][6]的地址；已知一顆二叉樹的先序遍歷為：ABCEFHDG,中序遍歷為：AECHFBGD請畫出該二叉樹(3分)寫出該二叉樹的后序遍歷(3分)畫出該二叉樹的后序線索樹(4分)采用普里姆算法對下圖所示連通圖構造最小生成樹(10分)

健壯性、高效性等4個方面評價算法的質量，以下解釋錯誤的是(A.(A.B.C.正確性算法應能正確地實現預定的功能易讀性算法應易于閱讀和理解，以便調試、修改和擴充健壯性當環(huán)境發(fā)生變化時，算法能適當地做出反應或進行處理，不會產生不需要的運行結果高效性即達到所需要的時間性能)。某算法的語句執(zhí)行頻度為(n+nlog2n+8)，其時間復雜度表示()。A.0(n) B.O(nlog2n) C.O(n2) D.O(log2n))。p->next=q;q->prior=p;p->next->prior=q;q->next=q;p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;q->next=p->next;q->prior=p;p->next=q;p->next=q;一個棧的輸入序列為：a，b，A.e,d,c,b,a B.a,b,c,d,e棧的插入和刪除操作在(A.棧底 B.棧頂廣義表G=(a,b(c,d,(e,f)),g)的長度是A.3 )。p->next=q;q->prior=p;p->next->prior=q;q->next=q;p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;q->next=p->next;q->prior=p;p->next=q;p->next=q;一個棧的輸入序列為：a，b，A.e,d,c,b,a B.a,b,c,d,e棧的插入和刪除操作在(A.棧底 B.棧頂廣義表G=(a,b(c,d,(e,f)),g)的長度是A.3 B.4c,d,)。e,則棧的不可能輸出的序列是(C.c,a,b,e,dD.d,e,c,b,a)。C.任意位置D.指定位置）。C.7D.8在一棵具有9層的滿二叉樹中結點總數為(A.512 B.511 C.513采用鄰接表存儲的圖，其深度優(yōu)先遍歷類似于二叉樹的A.中序遍歷 B.先序遍歷 C.后序遍歷已知一個有序表為(1，2,3,4,5,6,7,8,9,10，11)，則折半查找1需次。A.1 B.2 C.3 D.4在各種查找方法中，平均查找承擔與結點個數n無關的查找方法是(A.順序查找 B.折半查找 C.哈希查找 D.分塊查找( )1.鏈表的刪除算法很簡單，因為當刪除鏈中某個結點后，計算機會自動地將后續(xù)的)。)。D.9D.按層次遍歷■'需要比較( ))。各個單元向前移動。( )2.線性表的每個結點只能是一個簡單類型,而鏈表的每個結點可以是一個復雜類型。( )3.棧是一種對所有插入、刪除操作限于在表的一端進行的線性表，是一種后進先出型結構。( )4.對于不同的使用者，一個表結構既可以是棧，也可以是隊列，也可以是線性表。

（ ）5.二叉樹中每個結點的兩棵子樹是有序的。（ ）6.二叉樹中每個結點有兩棵非空子樹或有兩棵空子樹。（ ）7.二叉排序樹的任意一棵子樹中，關鍵字最小的結點必無左孩子，關鍵字最大的結點必無右孩子。（ ）8.一個圖的鄰接表表示是惟一的。（ ）9.有向圖的鄰接矩陣一定是對稱矩陣。（ ）10.有向圖用鄰接表表示，頂點vi的出度是對應頂點vj鏈表中結點個數。若以｛2,4,5,7,8｝作為權值構造哈夫曼樹，則該樹的帶權路徑長度為（ ）。數據的存儲結構可用四種基本的存儲方法表示，它們分別是順序、鏈式、索引和（）。設s='IAMAREADER'其長度是（ ）。設一棵完全二叉樹有501個結點，則共有（）個葉子結點。15條邊的無向連通圖，至少有（ ）個頂點。假設有5行7列的二維數組A,每個元素占用2個字節(jié)，存儲器按字節(jié)編址。已知A的基地址為1000，計算：（10分）（1） 數組A共占用多少字節(jié)；（2） 數組A的最后一個元素的地址；⑶按行存儲時，元素A[3][5]的地址；⑷按列存儲時，元素A[3][5]的地址；已知一顆二叉樹的先序遍歷為：ABDCEGFH,中序遍歷為：DBAEGCFH（1） 請畫出該二叉樹（3分）（2） 寫出該二叉樹的后序遍歷（3分）（3） 畫出該二叉樹的后序線索樹（4分）采用普里姆算法對下圖所示連通圖構造最小生成樹（10分）數據結構是一門研究非數值計算的程序設計問題中計算機的數據元素以及它們之間的（）和運算等的學科。A.結構 B.關系 C.運算D.算法下列程序段的時間復雜度為（ ）。x=n;y=0;while（x>=（y+l）*（y+l））y=y+l;A.O(n)B.A.O(n)B.OQn) C.O(1)D.O(n2)鏈表不具有的特點是（）。B.插入刪除不需要移動元素B.插入刪除不需要移動元素C.不必事先估計存儲空間 D.所需空間與線性表長度成正比一個棧的輸入序列為：a，b,c,d,e,則棧的不可能輸出的序列是（）。D.d,e,c,b,aD.S->top!=nD.(c)D.d,e,c,b,aD.S->top!=nD.(c)D.7D.散列存儲結構判定一個順序棧S（棧空間大小為n）為空的條件是（）。A.S->top==0 B.S->top!=0 C.S->top==n廣義表（a,b,c）的表尾是（ ）。A.b,c B.（b,c） C.c在一棵具有7層的滿二叉樹中結點總數為（）。A.126 B.127 C.128鄰接表是圖的一種（）。順序存儲結構B.鏈式存儲結構 C.索引存儲結構TOC\o"1-5"\h\z已知一個有序表為（1,2,3,4,5,6,7,8,9,10，11），則折半查找4需要比較（ ）次。\o"CurrentDocument"A.1 B.2 C.3 D.410.用某種排序方法對線性表（25,84,21,47,15,27,68,35,20）進行排序時，元素序列的變化情況如下：⑴25,84,21,47,15,27,68,35,20⑵20,15,21,25,47,27,68,35,84⑶15,20,21,25,35,27,47,68,84⑷15,20,21,25,27,35,47,68,84TOC\o"1-5"\h\z則所采用的排序方法是（ ）。A.選擇排序 B.希爾排序 C.歸并排序D.快速排序（ ）1.順序表結構適宜于進行順序存取，而鏈表適宜于進行隨機存取。（ ）2.順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。（ ）3.棧和鏈表是兩種不同的數據結構。（ ）4.棧和隊列是一種非線性數據結構。（ ）5.二叉樹中每個結點的關鍵字值大于其左非空子樹（若存在的話）所有結點的關鍵字值，且小于其右非空子樹（若存在的話）所有結點的關鍵字值。（ ）6.二叉樹中所有結點個數是2k-11，其中k是樹的深度。（ ）7.哈希表的查找效率主要取決于哈希表造表時所選取的哈希函數和處理沖突的方法。（ ）8.有向圖用鄰接矩陣表示，刪除所有從頂點i出發(fā)的弧的方法是，將鄰接矩陣的i行全部元素置為0。（ ）9.若從無向圖中任一頂點出發(fā)，進行一次深度優(yōu)先搜索，就可以訪問圖中所有頂點，則該圖一定是連通的。（ ）10.在非連通圖的遍歷過程中，調用深度優(yōu)先搜索算法的次數等于圖中連通分量的個數。若以｛2,3,4,5,6｝作為權值構造哈夫曼樹，則該樹的帶權路徑長度為（）。數據結構包括數據的（ ）、數據的存儲結構和數據的運算這三個方面的內容。設s='IAMACHINA',長度是（ ）。設一棵完全二叉樹有490個結點，則共有（ ）個葉子結點。18條邊的無向連通圖，至少有（ ）個頂點。假設有8行5列的二維數組A,每個元素占用2個字節(jié)，存儲器按字節(jié)編址。已知A的基地址為1000，計算：（10分）

（1） 數組A共占用多少字節(jié)；（2） 數組A的最后一個元素的地址；⑶按行存儲時，元素A[3][4]的地址；⑷按列存儲時，元素A[3][4]的地址；已知一顆二叉樹的先序遍歷為：ABDEGHCF,中序遍歷為：DBGEHAFC（1） 請畫出該二叉樹（3分）（2） 寫出該二叉樹的后序遍歷（3分）（3） 畫出該二叉樹的后序線索樹（4分）采用普里姆算法對下圖所示連通圖構造最小生成樹（10分）1.下面程序段的時間復雜度為( )。i=1；while(iv=n)i=i*3;A.O(n) B.O(3n) C.O(log3n) D.O(n3)(1)2.程序段如下：sum=0；for(i=1;iv=n;i++)for(j=1;jv=n;j++)sum++；其中n為正整數，則最后一行的語句頻度在最壞情況下是（ ）。A.O（n） B.O（nlogn）C.O（n3） D.O（n2）線性表L=（al,a2, ,an）下列說法正確的是（）。每個元素都有一個直接前驅和一個直接后繼線性表中至少要有一個元素表中諸元素的排列順序必須是由小到大或由大到小除第一個和最后一個元素外，其余每個元素都由一個且僅有一個直接前驅和直接后繼一個棧的輸入序列為：a，b，c，d，e,則棧的不可能輸出的序列是（）。A.e,d,c,b,a B.a,b,c,d,eC.d,e,b,c,a D.d,e,c,b,a正常情況下，刪除非空的順序存儲結構的堆棧的棧頂元素，棧頂指針top的變化是（）。D.top=top-1D.查找與索引A.top不變 B.top=0 C.top=top+1D.top=top-1D.查找與索引A.建立和刪除 B.A.建立和刪除 B.索引和修改C.查找和修改在一棵具有6層的滿二叉樹中結點總數為（）。A.62 A.62 B.63 C.64D.68?任一個有向圖的拓撲序列（）。A.不存在 B.有一個 C.一定有多個 D.有一個或多個已知一個有序表為（1,2, 3, 4, 5, 6, 7, 8, 9, 10, 11）,則折半查找9需要比較（ ）次。A.1 B.2 C.3 D.4快速排序方法在（）情況下最不利于發(fā)揮其長處。A.要排序的數據量太大 B.要排序的數據中有多個相同值C.要排序的數據已基本有序 D.要排序的數據個數為奇數（ ）1.線性表在物理存儲空間中也一定是連續(xù)的。（ ）2.線性表在順序存儲時，邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰。（ ）3.棧和隊列的存儲方式既可是順序方式，也可是鏈接方式。（ ）4.兩個棧共享一片連續(xù)內存空間時，為提高內存利用率，減少溢出機會，應把兩個棧的棧底分別設在這片內存空間的兩端。（ ）5.二叉樹中所有結點，如果不存在非空左子樹，則不存在非空右子樹。（ ）6.對于一棵非空二叉樹，它的根結點作為第一層，則它的第i層上最多能有2—1個結點。（ ）7.平衡二叉樹是指左右子樹的高度差的絕對值不大于1的二叉樹。（ ）8.一個連通圖的生成樹是一個極小連通子圖。（ ）9.在AOE網中僅存在一條關鍵路徑。（ ）10.若圖C的鄰接表表示時，表中有奇數個邊結點，則該圖一定是有向圖。若以｛2,3,6,7,9｝作為權值構造哈夫曼樹，則該樹的帶權路徑長度為（ ）。數據結構包括數據的邏輯結構、數據的（ ）和數據的運算這三個方面的內容。設s='IAMTOM'其長度是（ ）。設一棵完全二叉樹有492個結點，則共有（ ）個葉子結點。23條邊的無向連通圖，至少有（ ）個頂點。假設有5行6列的二維數組A,每個元素占用4個字節(jié)，存儲器按字節(jié)編址。已知A的基地址為1000，計算：（10分）（1） 數組A共占用多少字節(jié)；（2） 數組A的最后一個元素的地址；⑶按行存儲時，元素A[4][3]的地址；⑷按列存儲時，元素A[4][3]的地址；已知一顆二叉樹的先序遍歷為：ABDEGHCF,中序遍歷為：DBGEHAFC（1） 請畫出該二叉樹（3分）（2） 寫出該二叉樹的后序遍歷（3分）（3）