數(shù)據(jù)結(jié)構(gòu)復(fù)習題23480

1、一、單選題1. 下列四種基本邏輯結(jié)構(gòu)中，數(shù)據(jù)元素之間關(guān)系最弱的是 A，隊列屬于B 。A. 集合 B. 線性結(jié)構(gòu) C. 樹形結(jié)構(gòu)D. 圖形結(jié)構(gòu)2. 線性結(jié)構(gòu)各數(shù)據(jù)元素之間存在著 B 的關(guān)系，圖形結(jié)構(gòu)數(shù)據(jù)元素之間存在 D 的關(guān)系。A. 無關(guān) B. 一對一 C. 一對多 D. 多對多3. 在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成C 。A. 動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B. 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C. 線性結(jié)構(gòu)和非線性結(jié)構(gòu) D. 內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)4. 算法中的基本操作重復(fù)執(zhí)行的頻度稱為算法的 A ；除了考慮存儲數(shù)據(jù)結(jié)構(gòu)本身所占用的空間外，實現(xiàn)算法所用輔助空間的多少稱為算法的 B 。A. 時間復(fù)雜度B.空間復(fù)雜

2、度 C.硬件復(fù)雜度D.軟件復(fù)雜度5. 算法分析的目的是 C ，算法分析的兩個主要方面是 A 。A. 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B. 研究算法中的輸入和輸出的關(guān)系C. 分析算法的效率以求改進 D. 分析算法的易懂性和文檔性A. 空間復(fù)雜度和時間復(fù)雜度 B. 正確性C. 可讀性和文檔性 D. 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性6. 計算機算法指的是 C，它必具備輸入、輸出和 B等五個特性。 A. 計算方法 B. 排序方法 C. 解決問題的有限運算序列 D. 調(diào)度方法 A. 可行性、可移植性和可擴充性 B. 可行性、確定性和有窮性C. 確定性、有窮性和穩(wěn)定性7. 線性表的邏輯順序與存儲順序總是一致的，這種說法 B

3、。A正確 B. 不正確8. 線性表若采用鏈式存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址 D。A. 必須是連續(xù)的 B. 部分地址必須是連續(xù)的C. 一定是不連續(xù)的 D. 連續(xù)或不連續(xù)都可以 D. 易讀性、穩(wěn)定性和安全性二、填空題 (將正確的答案填在相應(yīng)的空中)1. 數(shù)據(jù)邏輯結(jié)構(gòu)包括集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu) 和 圖形四種類型，樹形結(jié)構(gòu)和圖形結(jié)構(gòu)統(tǒng)稱為 非線性結(jié)構(gòu) 。2. 線性結(jié)構(gòu)中，第一個結(jié)點 沒有 前驅(qū)結(jié)點，其余每個結(jié)點有且僅有 1 個直接前驅(qū)結(jié)點；最后一個結(jié)點 沒有 后繼結(jié)點，其余每個結(jié)點有且僅有 1 個直接后繼結(jié)點。3. 在樹形結(jié)構(gòu)中，樹根結(jié)點沒有 前驅(qū) 結(jié)點，其余每個結(jié)點有且只有 1 個前驅(qū)結(jié)

4、點；葉子結(jié)點沒有 后繼 結(jié)點，其余每個結(jié)點的后繼結(jié)點可以 任意多個 。4. 在圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點數(shù)和后繼結(jié)點數(shù)可以 任意多個 。5. 線性結(jié)構(gòu)中元素之間存在 一對一 關(guān)系，樹形結(jié)構(gòu)中元素之間存在 一對多關(guān)系，圖形結(jié)構(gòu)中元素之間存在 多對多 關(guān)系。6. 算法的五個重要特性是有窮性 、確定性 、可行性 、輸入 、輸出。7. 下面程序段的時間復(fù)雜度是 O（n*m) 。for(i=0;i<n;i+) for(j=0;j<m;j+)aij=0;8. 下面程序段的時間復(fù)雜度是 O() 。i=s=0;while(s<n) i+; s+=i; 9. 下面程序段的時間復(fù)雜度是O(n

5、2 ) 。s=0;for(i=0;i<n;i+) for(j=0;j<n;j+)s+=bij;sum=s;10. 下面程序段的時間復(fù)雜度是 O(log2n) 。i=1;while(i<=n) i=i*3;習 題 二一、填空題1. 在一個長度為n的向量的第i個元素(1in)之前插入一個元素時，需向后移動n-i+1 個元素。2. 在一個長度為n的向量中刪除第i個元素(1in)時，需向前移動 n-i 個元素。3. 單鏈表是線性表 的鏈接存儲表示。4. 在單鏈表中設(shè)置頭結(jié)點的作用是在插入或刪除第一個結(jié)點時不必對 表頭指針 進行處理。5. 在雙鏈表中，每個結(jié)點有兩個指針域，一個指向 前

6、驅(qū)結(jié)點 ，另一個指向 后繼結(jié)點 。6. 在一個單鏈表中p所指結(jié)點之后插入一個s所指結(jié)點時，應(yīng)執(zhí)行s->next= p->next 和p->next =s 的操作。7. 非空的循環(huán)單鏈表head的尾結(jié)點(由p所指向)滿足條件p->next=head二、單選題1. 不帶頭結(jié)點的單鏈表head為空的判定條件是 A 。A. head=NULL B. head->next=NULL C. head->next=head D. head!=NULL2. 帶頭結(jié)點的單鏈表head為空的判定條件是 B 。A. head=NULL B. head->next=NULLC

7、. head->next=head D. head!=NULL3. 非空的循環(huán)單鏈表head的尾結(jié)點(由p所指向)滿足 C 。A. p->next=NULLB. p=NULLC. p->next=headD. p=head4. 在循環(huán)雙鏈表的p所指結(jié)點之后插入s所指結(jié)點的操作是 D 。A. p->next=s; s->prior=p;p->next->prio=s; s->next=p->next;B. p->next=s; p->next->prior=s; s->prior=p; s->next=p->

8、;next;C. s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;D. s->prior=p; s->next=p->next; p->next->prior=s; p->next=s;5. 在一個單鏈表中，已知q所指結(jié)點是p所指結(jié)點的前驅(qū)結(jié)點，若在q和p之間插入s結(jié)點，則執(zhí)行 C。A. s->next=p->next; p->next=s;B. p->next=s->next; s->next=p;C. q->ne

9、xt=s; s->next=p;D. p->next=s; s->next=q; 6. 一個單鏈表中，若p所指結(jié)點不是最后結(jié)點，在p之后插入s所指結(jié)點，則執(zhí)行 B 。A. s->next=p; p->next=s;B. s->next=p->next; p->next=;C. s->next=p->next; p=s;D. p->next=s; s->next=p;7. 在一個單鏈表中，若刪除p所指結(jié)點的后繼結(jié)點，則執(zhí)行 A 。A. p->next=p->next->next;B. p=p->nex

10、t; p->next=p->next->next;C. p->next=p->nextD. p=p->next->next習 題 三一、填空題1. 棧是限定僅在表尾進行 插入和刪除 操作的線性表，表頭端稱為 棧底 ，表尾端稱為 棧頂 ，棧的操作特性是 后進先出 。2. 隊列是限定僅在表尾進行 插入 和在表頭端進行 刪除 的線性表，隊列的操作特性是 先進先出 。3. 以下定義了一個順序棧： #define MAXSTACK 500 typedef struct char dataMAXSTACK; int top; sqstack; sqstack ss

11、;?？盏臈l件是：ss.top<0 ，棧滿的條件是：ss.top=MAXSTACK-1 ；棧頂元素的表達式是：ss.datass.top ，棧底元素的表達式是：ss.data0 。二、簡答題1. 設(shè)將整數(shù)1，2，3，4依次進棧，但只要出棧時棧非空，則可將出棧操作按任何次序插入在入棧操作之間，請回答下述問題：(1) 若入、出棧次序為Push(1), Pop(), Push(2), Push(3), Pop(), Pop( ), Push(4), Pop( )，則出棧的數(shù)字序列是什么(這里Push(i)表示i進棧，Pop( )表示出棧)?1324(2) 能否得到出棧序列1423和1432?并說

12、明為什么不能得到或者如何得到。不能得到1423序列，因為要得到14的出棧序列，則應(yīng)做到push(1),pop(),push(2),push(3),push(4),pop()這樣，3在棧頂，2在棧底，所以不能得到23的出棧序列。 能得到1432的出棧序列，具體操作為：push(1),pop(),push(2),push(3),push(4),pop(),pop(),pop()(3) 請分析1，2，3，4的24種排列中，哪些序列可以通過相應(yīng)的入、出棧操作得到。在1234的24種排列中，可以通過相應(yīng)入出棧的操作得到的序列是：1234，1243，1324，1342，1432，2134，2143，231

13、4，2341，2431，3214，3241，3421，4321不能得到的序列為：1423，2413，3124，3142，3412，4123，4132，4213，4231，43122. 循環(huán)隊列的優(yōu)點是什么? 如何判別它的空和滿?優(yōu)點：克服”假上溢“,能是空間得到充分的利用。判斷空和滿的方法：1。設(shè)置布爾變量來區(qū)分空和滿 2.少用一個元素的空間變量， 3.設(shè)置一個計數(shù)器習 題 四一、填空題1. 已知二維數(shù)組Amn采用行序為主方式存儲，每個元素占k個存儲單元，并且第一個元素的存儲地址是Loc(A00)，則Aij的地址是 Loc(A(0)(0) +(n*i+j)*k 。2. 二維數(shù)組A1020采用列

14、序為主方式存儲，每個元素占一個存儲單元，并且A00的存儲地址是200，則A612的地址是 326 。二、單選題1. 常對數(shù)組進行的兩種基本操作是 C 。A. 建立與刪除 B. 索引和修改C. 查找和修改 D. 查找與索引2. 數(shù)組A中，每個元素的長度為3個字節(jié)，行下標i從1到8，列下標j從1到10，存放該數(shù)組至少需要的單元數(shù)是 C 。A. 80 B.100 C. 240 D. 2703. 數(shù)組A中，每個元素的長度為3個字節(jié)，行下標i從1到8，列下標j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按行存放時，元素A85的起始地址為 C 。A. SA +141 B. SA +144 C.

15、SA + 222 D. SA + 2254. 稀疏矩陣一般的壓縮存儲方法有兩種，即 C 。A. 二維數(shù)組和三維數(shù)組 B. 三元組表和散列C. 三元組表和十字鏈表 D. 散列和十字鏈表習 題 五一、簡答題1. 設(shè)S="I AM A STUDENT"，T="GOOD"，Q="WORKER"。求：STRLEN(s)=14，STRLEN(t)=4，SUBSTR(s，8，7)="STUDENT"，SUBSTR(t，2，1)="O"，INDEX(s，"A")=3，INDEX(s，t)=0

16、，REPLACT(s，"STUDENT"，q)="I AM A WORKER"。2. 已知下列字串：A="THIS"，f="S A MPLE"，c="GOOD"，d="NE"，b="V"，g="IS"S= CONCAT(a，CONCAT(CONCAT (b，SUBSTR(a，3，2)，SUBSTR(f，2，6)T=REPLACE(f，SUBSTR(f，3，5)，c)U= CONCAT (SUBSTR(c，3，1)，d)V= CONCAT

17、(s，CONCAT(b，CONCAT(t，CONCAT(b，u)問s="THIS IS SMPLE"，t="A GOOD"，v="THIS IS SMPLE A GOOD ONE"，STRLEN(s)=13，INDEX(v,g)=3，INDEX(u,g)各是什么=0？3. 簡述下列每對術(shù)語的區(qū)別：空串和空格串 空串是不包含任何字符的串，長度為0，空格串指包含一個或者多個空格的串，空格也是字符串變量和串常量 串常量是指在程序中只可引用但不可改變其值的串，串變量時可以再運行中改變其值的。主串和子串是相對的，一個串中任意個連續(xù)的字符組成的串

18、就是這個串的子串，而包含子串的串就稱為主串4. 兩個字符串相等的充要條件是什么？串長度相等，并且各對應(yīng)位置上的字符也相等5. 設(shè)已知兩個串為：S1=“bc cad cabcadf”；S2=“abc”。試求兩個串長度，并判斷S2串是否是S1的子串。如果S2是S1的子串，指出S2在S1中的起始位置。S1的長度是14，S2的長度是3，S2是S1的子串，S2在S1的起始位置為9習 題 六一、判斷題1. 二叉樹是樹的特殊情形。( 錯 )2. 二叉樹的先序遍歷序列中，任意結(jié)點均處在其孩子結(jié)點之前。( 對 )3. 二叉鏈表是一種邏輯結(jié)構(gòu)。( 錯 )4. 由二叉樹的先序序列和后序序列可以唯一確定一棵二叉樹。(

19、 錯 )5. n個結(jié)點的完全二叉樹不唯一。( 錯 )6. 樹的后序遍歷序列與其對應(yīng)的二叉樹的后序遍歷序列相同。( 錯 )7. 完全二叉樹的某結(jié)點若無左孩子，則它必是葉子結(jié)點。( 對 )二、選擇題 1. 將一棵樹t轉(zhuǎn)換為孩子兄弟鏈表表示的二叉樹h，則t的后序遍歷是h的( B )A. 先序遍歷 B. 中序遍歷 C. 后序遍歷 D. 層次遍歷2. 對二叉樹從1開始進行連續(xù)編號，要求每個結(jié)點的編號大于其左右孩子的編號，同一結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編號，則可采用( C)次序的遍歷實現(xiàn)編號。A. 先序 B. 中序 C. 后序 D. 從根開始的層次遍歷3. 已知一棵完全二叉樹中共有76

20、8個結(jié)點，則該樹中共有( B )個葉子結(jié)點。A. 383 B. 384 C. 385 D. 3864. 先序遍歷和中序遍歷相同的二叉樹為( D )。A 只有根結(jié)點的二叉樹 B. 根結(jié)點無左孩子的二叉樹C 一般二叉樹 D. 只有根結(jié)點的二叉樹和所有結(jié)點只有右子樹的二叉樹三、簡答題1. 一棵樹的邊集為(a,b)，(b,e)，(a,c)，(c,g)，(a,d)，(d,i)，(c,f)，(c,h)，(d,j)，(i,k),請畫出此棵樹的形態(tài)，并回答下列問題：(1) 樹的根是哪個結(jié)點？A 哪些是葉子結(jié)點？ efghjk 哪些是分支結(jié)點？ abcdi(2) 各結(jié)點的度分別是多少？樹的度是多少？4 結(jié)點 a

21、 b c d e f g h i j k 度 3 1 3 2 0 0 0 0 1 0 0 層次 1 2 2 2 3 3 3 3 3 3 4(3) 各結(jié)點的層次分別是多少？樹的深度是多少？3以d為根的子樹深度是多少？3(4) 結(jié)點i的雙親是哪個結(jié)點？d 祖先是哪個結(jié)點？A 孩子是哪些結(jié)點？K 兄弟是哪些結(jié)點？j2. 樹和二叉樹有哪些區(qū)別？樹是無序樹，而二叉樹是有序樹，二叉樹的度不能大于2，它的兩個分支是有先后順序的。3. 已知二叉樹的后序和中序序列如下，構(gòu)造出該二叉樹，寫出它的前序遍歷序列。 后序序列：ABCDEFG 中序序列：ACBGDFE GCABFDE4. 假設(shè)用于通信的電文由字符集a,b

22、,c,d,e,f,g中的字母構(gòu)成，它們在電文中出現(xiàn)的頻度分別為0.31, 0.16, 0.10, 0.08, 0.11, 0.20, 0.04(1) 為這7個字母設(shè)計哈夫曼編碼。 a,b,c,d,e,f,g的編碼分別為：11，102，010，1001，011，00，1000，(2) 對這7個字母進行等長編碼，至少需要幾位二進制數(shù)？哈夫曼編碼與等長編碼相比，能使電文總長壓縮多少？WPL=2.61等長編碼需要3bit，則壓縮了（3-2.61）、3=13%習 題 七一、單項選擇題1. 一個有n個頂點的無向圖最多有_C_條邊。A. n B. n(n-1) C. n(n-1)/2 D. 2n2. 一個有

23、4個頂點的無向完全圖有_A_條邊。A. 6 B. 12 C. 16 D. 203. 一個有5個頂點的連通圖至少有_B_條邊。A. 3 B. 4 C. 5 D. 64. _B_的鄰接矩陣是對稱矩陣。A. 有向圖 B. 無向圖 C. AOV網(wǎng)5. 鄰接表是圖的一種_B_。A. 順序存儲結(jié)構(gòu) B. 鏈接存儲結(jié)構(gòu)C. 索引存儲結(jié)構(gòu) D. 散列存儲結(jié)構(gòu)6. 采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的_A_。A. 前序遍歷 B. 中序遍歷 C. 后序遍歷 D. 按層遍歷7. 采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于二叉樹的_D_。A. 前序遍歷 B. 中序遍歷 C. 后序遍歷 D. 按層遍歷8.

24、 任何一個無向連通圖_B_最小生成樹。 .只有一棵 B. 有一棵或多棵 C. 一定有多棵 D. 可能不存在9. 一個圖的_B_表示法是唯一的，而_C_表示法是不唯一的。A. 三元組 B. 鄰接矩陣 C. 鄰接表 D. 索引二、簡答題1. 對圖7.23所示有向圖，回答下列問題：(1) 該圖是強連通圖嗎？若不是，則給出其強連通分量。(2) 請給出從頂點1到頂點3的所有的簡單路徑。(3) 請給出頂點1的度、入度和出度。(4) 請給出其鄰接矩陣、鄰接表及逆鄰接表。習 題 八一、單選題1. 對線性表進行二分查找時,要求線性表必須 C 。A. 以順序方式存儲 B. 以鏈接方式存儲C. 以順序方式存儲且結(jié)點

25、按關(guān)鍵字有序排列D. 以鏈接方式存儲且結(jié)點按關(guān)鍵字有序排列2. 采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為 C 。A. n B. n/2C. (n+1)/2 D. (n-1)/23采用二分查找長度為n的線性時，每個元素的平均查找長度為 D 。A. O(n2) B.O(nlog2n)C. O(n) D. O(log2n)4. 有一個有序表為(5，7，8，22，32，40，45，62，70，77，82，97，100)，當二分查找值為82的結(jié)點時， C 次比較后查找成功。A. 1 B. 3 C. 4 D. 85. 從一個具有n個結(jié)點的單鏈表中查找其值等于x結(jié)點時，查找成功的情況

26、下，需平均比較 D 個結(jié)點。A. n B. n/2 C. (n1)/ 2 D. (n+1)/2二、填空題1. 假設(shè)在有序線性表A1，A20上進行二分查找，則比較一次查找成功的結(jié)點數(shù)為 1 ，則比較二次查找成功的結(jié)點數(shù)為 2 ，則比較三次查找成功的結(jié)點數(shù)為 4 ，則比較四次查找成功的結(jié)點數(shù)為 8 ，則比較五次查找成功的結(jié)點數(shù)為 5 ，平均查找長度為 3.7 。2. 在散列存儲中，裝填因子的值越大，存取數(shù)據(jù)元素時發(fā)生沖突的可能性 越大 ；的值越小，則發(fā)生沖突的可能性 越小 。三、簡答題設(shè)有一組關(guān)鍵字(19，01，23，14，55，20，84，27，68，11，10，77)，采用哈希函數(shù)H(key)

27、 = key % 13采用開放地址法的線性探測再散列方法解決沖突，試在012的散列地址空間中對該關(guān)鍵字序列構(gòu)造哈希表。0 1 2 3 4 5 6 7 8 9 10 11 1277 1 14 55 27 68 19 20 84 23 11 102. 對上題中的關(guān)鍵字序列，采用鏈地址法，畫出相應(yīng)的哈希表。3. 對有序表(5，8，27，36，45，48，57，72，89，95)，采用二分查找，畫出二分查找過程的二叉判定樹，并計算其平均查找長度。習 題 九一、單選題1. 在所有排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是 D 。A. 希爾排序 B. 冒泡排序 C. 直接插入排序 D. 直接選擇排序2. 設(shè)有1000個無序的元素，希望用最快的速度挑選出其中前10個最大的元素，最好選用 B 排序