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

1、1、 單項選擇1. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中,數(shù)據(jù)元素的 C 、數(shù)據(jù)信息在計算機(jī)中的 A 以及一組相關(guān)的運(yùn)算等的課程。 A操作對象計算方法邏輯結(jié)構(gòu)數(shù)據(jù)映象 A存儲結(jié)構(gòu) 關(guān)系 運(yùn)算 算法2. 以下數(shù)據(jù)結(jié)構(gòu)中, D 是線性結(jié)構(gòu)。 A廣義表二叉樹稀疏矩陣串3. 從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為 C 兩大類。 A動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) 順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu) 線性結(jié)構(gòu)和非線性結(jié)構(gòu) 初等結(jié)構(gòu)和構(gòu)造型結(jié)構(gòu)4. 以下數(shù)據(jù)結(jié)構(gòu)中, D 是非線性結(jié)構(gòu)。 A棧 二叉樹隊列 字符串5. 數(shù)據(jù)結(jié)構(gòu)DS(Data Struct)可以被形式地定義為DS=（D，R），其中D是 B 的有限集合，R是D上的 D 有限集合

2、。 A算法 數(shù)據(jù)元素 數(shù)據(jù)操作 數(shù)據(jù)對象 A操作 映象 存儲 關(guān)系6. 線性表的順序存儲結(jié)構(gòu)是一種 A 的存儲結(jié)構(gòu), 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是一種的 B 存儲結(jié)構(gòu)。A隨機(jī)存取 順序存取 索引存取 散列存取7. 線性表的邏輯順序與存儲順序總是一致的，這種說法_B _。A. 正確 B. 不正確8. 下面那一條是順序存儲結(jié)構(gòu)的優(yōu)點(diǎn)? (A)A . 存儲密度大 B. 插入運(yùn)算方便 C. 刪除運(yùn)算方便 D. 可以方便的用于各種邏輯結(jié)構(gòu)的存儲表示9. 線性表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時, 要求內(nèi)存中可用的存儲單元的地址 .A . 必須是連續(xù)的 B. 部分地址必須是連續(xù)的 C. 一定不連續(xù)D. 連續(xù)和不連續(xù)都可以10.

3、 表長為n的順序存儲的線性表, 當(dāng)在任何位置上插入和刪除一個元素的概率相等時, 插入一個元素所需要移動元素的平均次數(shù)為 E , 刪除一個元素所需要移動元素的平均次數(shù)為 A A. (n-1)/2 B.n C. n+1 D. n-1 E. n/2 F. (n+1)/2 G. (n-2)/211. 帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是_B_。A. head= =NULL B. head->next= =NULLC. head->next= =head D. head!=NULL12. 在一個單鏈表中, 若刪除p所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn), 則執(zhí)行_A_。A. p->next= p-&

4、gt;next->next B. p=p->next; p->next= p->next->nextC. p= p->next->next D. p= p->next13. 若已知一個棧的入棧序列是1，2，3，n，其輸出序列為p1，p2，p3，pn，若p1=n，則pi為_C_。 A. i B. n=i C. n-i+1 D. 不確定14. 設(shè)棧的輸入次序為: 1 , 2, 3, 4, 5, 則 不可能是其出棧序列. A. 54321 B. 45321 C. 43512 D. 1234515. 一個遞歸算法必須包括 B A. 遞歸部分 B. 終止條

5、件和遞歸部分C. 迭代部分 D. 終止條件和迭代部分16. 用鏈接方式存儲的隊列, 在進(jìn)行刪除操作時 D A 僅修改頭指針 B. 僅修改尾指針C. 頭尾指針都要修改 D. 頭尾指針可能都要修改17. 數(shù)組Am存放循環(huán)隊列的元素, 其頭尾指針分別是front和rear, 則當(dāng)前隊列的元素個數(shù)是_A_。A. (rear-front+m)%m B. (front-rear+m)%m C. front-rear+1 D. rear-front+118. 棧和隊列的共同特點(diǎn)_C_。A. 都是先進(jìn)先出 B. 都是先進(jìn)后出 C. 允許在端點(diǎn)插入和刪除元素 D. 沒有共同點(diǎn)19. 一個棧的入棧序列a，b，c，

6、d，e，則棧的輸出序列是_A_。 A. edcba B. decba C. dceab D. abcde 20. 棧的特點(diǎn)是_B_，隊列的特點(diǎn)是_A_。A. 先進(jìn)先出 B. 先進(jìn)后出21. 從一個棧頂指針HS的鏈表中刪除一個結(jié)點(diǎn), 用x保存被刪除的結(jié)點(diǎn)值,執(zhí)行的語句為_C_。A. x=HS; HS=HS->next B. HS=HS->next; x=HS->dataC. x=HS->data; HS=HS->next D. HS->next=HS; x=HS->data22. 在鏈隊列Q中, 插入s所指向的結(jié)點(diǎn)執(zhí)行的語句為_B_。A. Q.front

7、->next=s; B. Q.rear->next=s; Q.rear=sC. s->next=Q.rear;Q.rear=s D. s->next=Q.front;Q.front=s23. 空串與空格串是相同的，這種說法_B_。A. 正確 B. 不正確24. 下面關(guān)于串的敘述, 哪一個是不正確的_B_。A. 串是字符的有限序列 B. 空串是由空格構(gòu)成的串C. 匹配模式是串的一種重要運(yùn)算 D. 串可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)25. 設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作_B_。A. 連接 B. 模式匹配C. 求子串 D. 求串長26. 若串s='softw

8、are', 其子串的數(shù)目為 B A. 8 B. 37 C. 36 D. 927. 二維數(shù)組A中，每個元素A的長度為3個字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按行存放時，數(shù)組元素A74的起始地址為_C_。A. SA+141 B. SA+144 C. SA+222 D. SA+22528. 對稀疏矩陣進(jìn)行壓縮存儲的目的是_C_.A. 便于進(jìn)行矩陣運(yùn)算 B. 便于輸入輸出C 節(jié)省存儲空間 D. 降低運(yùn)算的時間復(fù)雜度29. 在以下敘述中正確的是 B A. 線性表的線性存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu)B. 二維數(shù)組可以看成是其數(shù)據(jù)元素為線性表的線性表C. 棧

9、的操作方式是先進(jìn)先出D. 隊列的操作方式是先進(jìn)后出30. 廣義表(a),a)的表頭為 C , 表尾為 C .A. () B. a C. (a) D. (a)31. 已知廣義表L=(x,y,z),a,(u,t,w), 從L中取出原子項t的運(yùn)算為_D_。 A. Head(Tail(Tail(L) B. Tail(Head(Head(Tail(L)C. Head(Tail(Head(Tail(L) D. Head(Tail(Head(Tail(Tail(L)32. 樹最適合用來表示 B A. 有序的數(shù)據(jù)元素 B. 數(shù)據(jù)之間具有分支層次關(guān)系的數(shù)據(jù)C. 無序的數(shù)據(jù)元素 D. 無太多關(guān)系的數(shù)據(jù)元素33.

10、如果某二叉樹的前根次序遍歷結(jié)果為stuwv，中序遍歷為uwtvs，那么該二叉樹的后序為_B_。 A. uwvts B. vwuts C. wuvts D. wutsv34. 某二叉樹的前序遍歷結(jié)點(diǎn)訪問順序是abdgcefh，中序遍歷的結(jié)點(diǎn)訪問順序是dgbaechf，則其后序遍歷的結(jié)點(diǎn)訪問順序是_D_。A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca35. 在一非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右邊_A_。A. 只有右子樹上的所有結(jié)點(diǎn) B. 只有右子樹上的部分結(jié)點(diǎn)C. 只有左子樹上的部分結(jié)點(diǎn) D. 只有左子樹上的所有結(jié)點(diǎn)36. 設(shè)m和n是一棵二叉樹

11、上的兩個結(jié)點(diǎn), 在中序遍歷, n在m前的條件是 C A. n在m的右方 B. n是m的祖先C. n在m的左方 D. n是m的子孫37. 深度為5的二叉樹至多有_C_個結(jié)點(diǎn)。A. 16 B. 32 C. 31 D. 1038. 由權(quán)(8,2,5,7)的四個葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹, 該樹的帶權(quán)路徑長度為 D A. 23 B. 37 C. 46 D. 4339. 利用二叉鏈表存儲樹, 則根結(jié)點(diǎn)的右指針是 C A. 指向最左孩子 B. 指向最右孩子 C. 空 D. 非空40. 下列存儲方式中, 哪一個不是樹的存儲形式? D A. 雙親表示法 B. 孩子鏈表表示法 C. 孩子兄弟表示法 D. 順序存儲

12、表示法41. 在一個無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的_C_倍。A. 1/2 B. 1 C. 2 D. 4 42. 具有n個頂點(diǎn)和多于n-1條邊的無向圖 B .A. 有可能是樹 B. 一定不是樹 C. 一定是樹 D. 以上答案都不對43. 具有6個頂點(diǎn)的無向圖至少應(yīng)有_A_條邊才能確保是一個連通圖。A. 5 B. 6 C. 7 D. 844. 無向圖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), 則對該圖進(jìn)行深度優(yōu)先遍歷, 得到的序列為: D A. abecdf B. acfebd C.

13、 aebcfd D. aedfcb45. 下述幾種排序方法中，要求內(nèi)存量最大的是_D_。A. 插入排序 B. 選擇排序 C. 快速排序 D. 歸并排序46. 排序方法中，從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為_C_。A. 希爾排序 B. 起泡排序 C. 插入排序 D. 選擇排序47. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是_A_。A. 插入排序 B. 選擇排序 C. 快速排序 D. 歸并排序48. 下列排序算法中, 哪一個是穩(wěn)定的排序算法? B A. 直接選擇排序 B. 二分法插入排序 C. 希爾排序

14、D. 快速排序49. 將兩個各有n個元素的有序表歸并成一個有序表, 其最少的比較次數(shù) A A. n B. 2n-1 C. 2n D. n-12、 填空題1. 算法的五個重要特性是 有窮性,確定性,可行性,輸入和輸出.2. 數(shù)據(jù)的樹型結(jié)構(gòu)和圖(網(wǎng))狀結(jié)構(gòu)合稱 非線性結(jié)構(gòu) .3. 抽象數(shù)據(jù)類型的定義僅取決于它的一組 邏輯特性 , 而與 數(shù)據(jù)在計算機(jī)中的表示和實現(xiàn) 無關(guān).4. 評價算法質(zhì)量的指標(biāo)是 正確性,易讀性,健壯性,高效性.5. 數(shù)據(jù)結(jié)構(gòu)中評價算法的兩個重要指標(biāo)是: 時間復(fù)雜度和空間復(fù)雜度.6. 分析下面算法（程序段），的時間復(fù)雜度是_ O (mn) _。s=0;for (i=0;i<n

15、;i+) for (j=0;j<m;j+) s+=Bij;7. 當(dāng)線性表元素的總數(shù)基本穩(wěn)定, 且很少進(jìn)行刪除和插入操作時, 但是要求以最快的速度存取線性表中的元素, 應(yīng)該采取 順序 存儲結(jié)構(gòu).8. 順序表中邏輯上相鄰的元素的物理位置 必定 相鄰, 而單鏈表中邏輯上相鄰的元素的物理位置 不一定 相鄰.9. 在各個結(jié)點(diǎn)查找概率相等的情況下, 從n個結(jié)點(diǎn)的單鏈表中查找一個結(jié)點(diǎn), 平均要訪問 n/2 個結(jié)點(diǎn).10. 在單鏈表中設(shè)置頭指針的作用是: 簡化操作, 減少邊界條件的判斷.11. 在單鏈表中, 除首元結(jié)點(diǎn)外, 任一結(jié)點(diǎn)的存儲位置由 其直接前驅(qū)的指針域 指示.12. 對于一個具有n個結(jié)點(diǎn)的單

16、鏈表, 在已知p所指向結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)的時間復(fù)雜度是 O(1) , 在值域為給定值的結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)的時間復(fù)雜度為O(n). 13. 在雙鏈表中，每個結(jié)點(diǎn)有兩個指針域，一個指向_前驅(qū)結(jié)點(diǎn)_，另一個指向_后繼結(jié)點(diǎn)_ _。14. 根據(jù)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中每一結(jié)點(diǎn)包含的指針個數(shù), 將線性表分成 單鏈表 和 多重鏈表.15. 在非空雙向鏈表中, 在結(jié)點(diǎn)q的前面插入結(jié)點(diǎn)p的過程如下, 請補(bǔ)充 p->prior=q->prior;q->prior->next=p;p->next=q;q->prior=p;16. 一般情況下, 將遞歸算法轉(zhuǎn)換成等價的非遞歸算法應(yīng)

17、該設(shè)置 棧 .17. 在解決計算機(jī)主機(jī)與打印機(jī)速度不匹配問題時, 通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū), 該緩沖區(qū)通常是一個 隊列 數(shù)據(jù)結(jié)構(gòu).18. 循環(huán)隊列的引入, 目的是為了克服 假溢出 現(xiàn)象.19. 在棧頂指針為HS的鏈棧中, 判斷棧空的條件是 HS=NULL .20. 在具有n個單元的循環(huán)隊列中, 如果不專門設(shè)置隊滿標(biāo)志, 則隊滿時共 n-1 有個元素.21. 實現(xiàn)字符串拷貝的函數(shù)如下, 請補(bǔ)足Void strcpy(char *s, char *t) while( (*s+=*t+)!='0' );22. 空格串是_由一個或多個空格字符組成的串 _，其長度等于_其包含的空格個數(shù)

18、 。23. 空串是 不包含任何字符的串 , 其長度為 0 .24. 設(shè)s='I AM A STUDENT', 其長度為: 14 .25. 組成串的元素只能是: 字符 .26. 設(shè)s1='Good', s2=' ', s3='bye!', 則s1,s2和s3連接的結(jié)果是 Good bye!27. 若廣義表中每個元素都是原子時, 廣義表便成為 線性表 .28. 廣義表的表尾是指除第一個元素外, 剩余元素組成的表 .29. 廣義表A=(a,b,c,d)的表頭為 (a,b,c,d) ,表尾為 () .30. 數(shù)組的存儲結(jié)構(gòu)采用 順序 存儲

19、方式.31. 設(shè)二維數(shù)組a0.5, 0.6, 其每個字節(jié)占5個字節(jié), 第一個元素的存儲地址為1000, 若按列存儲, 則元素a5,5存儲地址為 1175 .32. 高度為k的完全二叉樹至少有 個葉子結(jié)點(diǎn).33. 若一棵二叉樹有50個葉子結(jié)點(diǎn), 則該二叉樹的總結(jié)點(diǎn)數(shù)至少是 99.34. 有n個葉子結(jié)點(diǎn)的哈夫曼樹的結(jié)點(diǎn)總數(shù)為 2n-1 .35. 根據(jù)二叉樹的定義, 具有三個結(jié)點(diǎn)的二叉樹有 4 種.36. 某棵二叉樹的中序遍歷序列為abcdefg, 后序遍歷序列為 bdcafge, 則該二叉樹的前序遍歷序列 eacbdgf , 該二叉樹對應(yīng)的森林包含 2 棵二叉樹.37. 若二叉樹采用二叉鏈表存儲結(jié)

20、構(gòu), 要交換其所有分支結(jié)點(diǎn)的左,右子樹的位置, 利用 中序 遍歷方法最為合適.38. 線索二叉樹的左線索指向其 前驅(qū) , 右線索指向其 后繼 .39. 樹所對應(yīng)的二叉樹其根結(jié)點(diǎn)的 右 子樹一定為空.40. 利用樹的孩子兄弟表示法存儲, 可以將一棵樹轉(zhuǎn)化成 二叉樹.41. 設(shè)無向圖的頂點(diǎn)個數(shù)為n, 則該圖最多有 n(n-1)/2 條邊.42. n個頂點(diǎn)的連通圖至少有 n-1 條邊.43. 已知一個圖用領(lǐng)接矩陣表示, 計算第i個結(jié)點(diǎn)的入度的方法是 求第i列非零元素的和 .44. G是一個非連通的無向圖, 共有28條邊, 則該圖至少有 9 個頂點(diǎn).45. 一個圖的 鄰接矩陣 表示法是唯一的，而 鄰接

21、表 表示法是不唯一的。46. 從鄰接矩陣可以看出, 該圖共有 3 個頂點(diǎn), 如果是無向圖, 則共有 2 條邊.47. n個頂點(diǎn)的連通圖用鄰接矩陣表示時, 則該矩陣至少有 2(n-1) 個頂點(diǎn).48. 設(shè)圖中有n個頂點(diǎn), e條邊, 如果用鄰接表表示圖, 進(jìn)行深度優(yōu)先搜索遍歷的時間復(fù)雜度為 O(n+e) , 如果用鄰接矩陣表示圖, 時間復(fù)雜度為 49. 從平均時間性能而言, 快速排序 排序最佳.50. 堆排序是一種 選擇 排序, 堆實質(zhì)上是 一棵完全二叉樹 結(jié)點(diǎn)的層次序列. 對于含有n個元素的排序, 堆排序的時間復(fù)雜度為 . 所需附加的存儲結(jié)點(diǎn)是 O(1) .3、 用圖表回答下列問題1. 設(shè)某通信

22、系統(tǒng)使用A，B ，C，D，E，F(xiàn)，G，H個字符，出現(xiàn)的頻率w=，試構(gòu)造對應(yīng)的哈夫曼樹（請按左子樹根結(jié)點(diǎn)的權(quán)小于右子樹樹根結(jié)點(diǎn)的權(quán)的次序構(gòu)造）?答案如圖:10042F23H1119A5G38B29E14D8C71529582. 根據(jù)下面的鄰接鏈表，畫出相應(yīng)的圖，寫出每個頂點(diǎn)的度, 并用鄰接矩陣表示.v1v3v2v4v5v6v2v5v4v3v5v6v4v6v3答案如圖所示:v1v2v3v4v5V6V1: 3V2: 3V3: 3V4: 2V5: 5V6: 23. 畫出下列樹對應(yīng)的二叉樹，并寫出其先根遍歷序列：BDFCAEG先根遍歷序列： A B D E G F C 答案如圖所示:BEGDFCA 4.

23、 畫出和下列二叉樹對應(yīng)的森林：AAAABBBCCC答:AAAABBBCCC4、 閱讀下列算法，按要求做答.1. 下面是刪除單鏈表L中最大元素所在結(jié)點(diǎn)的類C語言算法, 請補(bǔ)足缺失部分使其完整.void DelMax(LinkList L)r=L; p=L->next; if(p) m=p->data; (1) ; p=p->next; while(p) if( (2) ) (3) ; m=p->data; (4) ; p=p->next;q=r->next; (5) ; free(q); 答案: (1) q=p; (2)m<p->data; (3)

24、r=q; (4) q=p; (5) r->next=q->next.2. 閱讀下列算法，說明該算法的作用。Status algorithm1(LinkQueue &Q)SqStackStack;QElemTypeElement;InitStack(Stack);while(!QueueEmpty(Q)DeQueue(Q,Element);Push(Stack,Element);while(!StackEmpty(Stack)Pop(Stack,Element);EnQueue(Q,Element);答: 利用棧實現(xiàn)隊列的逆置.3. 閱讀下列算法，說明該算法的作用。Statu

25、s algorithm2(Stack S, int e)StackT;intd;InitStack(T);while(!StackEmpty(S)Pop(S,d);if(d!=e) Push(T,d); while(!StackEmpty(T)Pop(T,d);Push(S,d);答: 利用輔助棧T, 將棧S中的元素e刪除.4. 將下面程序改寫成遞歸過程.void algorithm3(int n)inti=n; while(i>1)printf(i-);答: void algorithm4(int j)if(j>1)printf(j);algorithm4(j-1)5. 閱讀下列

26、算法，說明該算法的作用。BiTree algorithm5(ElemType Pre, ElemType In)int PreLen, InLen;int i, j;BiTree BT;ElemType *subPre, *subIn;PreLen = strlen(Pre);InLen = strlen(In);if (PreLen != InLen | PreLen = 0) return NULL;for (i=0; i<InLen && Ini!=Pre0; i+);if (i = InLen) return NULL;BT = (BiTNode *) mallo

27、c(sizeof(BiTNode);BT->data = Pre0;subPre = (ElemType *) malloc(i+1)*sizeof(ElemType);subIn = (ElemType *) malloc(i+1)*sizeof(ElemType);for (j=0; j<i; j+)subPrej = Prej+1;subInj = Inj;subPrej = '0' subInj = '0'BT->lchild = CreatBT(subPre, subIn);subPre = (ElemType *) malloc(P

28、reLen-i)*sizeof(ElemType);subIn = (ElemType *) malloc(PreLen-i)*sizeof(ElemType);for (j=i+1; j<PreLen; j+)subPrej-i-1 = Prej;subInj-i-1 = Inj;subPrej-i-1 = '0' subInj-i-1 = '0'BT->rchild = CreatBT(subPre, subIn);return BT;答: 利用一棵二叉樹的先序遍歷和中序遍歷還原該二叉樹.5、 算法設(shè)計題1. 設(shè)順序表L中的數(shù)據(jù)元素遞增有序. 試寫一個算法, 將e插入順序表中, 要求插入后保持該表的有序性.void InsertElem(SqList &L, ElemType) j=L.length-1; while(L.elemj>e)L.elemj+1