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

1、數(shù)據(jù)結(jié)構(gòu)習(xí)題 一、名詞解釋 1. 數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)物理結(jié)構(gòu)、順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、 算法、時(shí)間復(fù)雜度、空間復(fù)雜度。 2. 線性表、順序表、單鏈表 、雙向鏈表、循環(huán)鏈表 、雙向循環(huán)鏈表、三個(gè)概念的區(qū)別：頭 指針、頭結(jié)點(diǎn)、首元結(jié)點(diǎn)（第1個(gè)元素結(jié)點(diǎn) ）。 3. 棧（順序棧、鏈棧）、隊(duì)列（順序隊(duì)、鏈隊(duì)）、循環(huán)隊(duì)列、遞歸、稀疏矩陣、三元組。 4. 樹(shù)、葉子結(jié)點(diǎn)、結(jié)點(diǎn)的度、樹(shù)的度、樹(shù)的高（深）度、二叉樹(shù)、遍歷、滿二叉樹(shù)、完全二叉樹(shù)、 哈夫曼樹(shù)、WPL哈夫曼編碼。 5. 圖（有向、無(wú)向）、網(wǎng)、邊、弧、度、入度、出度、完全圖（有向、無(wú)向）、（強(qiáng)）連通圖（分量）、 （最?。┥?/p>

2、成樹(shù)、鄰接矩陣、鄰接表、DFS BFS 6. 查找表、關(guān)鍵字、靜態(tài)查找、動(dòng)態(tài)查找、ASL、順序查找、折半查找、分塊查找、二叉排序樹(shù)。 7. 排序、內(nèi)（外）排序、穩(wěn)定性、插入（直接、希爾），交換（起泡、快速），選擇（直接、堆），2 路歸并。 填空題 1. 數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的 _邏輯結(jié)構(gòu)_和物理結(jié)構(gòu)_，并在這種結(jié)構(gòu)上定義相關(guān)的運(yùn)算，設(shè)計(jì)實(shí) 現(xiàn)這些運(yùn)算的算法，分析算法的效率。算法的效率包括時(shí)間和空間兩個(gè)方面，分別稱為時(shí)間 復(fù)雜度 和空間復(fù)雜度。 2. 數(shù)據(jù)的基本單位是數(shù)據(jù)元素，數(shù)據(jù)的最小單位是數(shù)據(jù)項(xiàng) 。 3. 算法是對(duì)特定問(wèn)題求解 步驟_的一種描述，是指令的有限序列。 4. 一個(gè)算法的時(shí)間復(fù)雜度為

3、 （3n3+2n 7），其數(shù)量級(jí)表示為_(kāi)0 （ n3）_。 5. 一個(gè)算法具有5個(gè)特性：_確定性、可行性_、_有窮性_、輸入和輸出。 6. 算法性能的分析和度量，可以從算法的時(shí)間復(fù)雜度一和空間復(fù)雜度來(lái)評(píng)價(jià)算法的優(yōu)劣。 7. 數(shù)據(jù)的邏輯結(jié)構(gòu)包括集合結(jié)構(gòu)、_線性結(jié)構(gòu) _、樹(shù)形結(jié)構(gòu)_和_圖型結(jié)構(gòu)四種類型。 8. 數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示稱為數(shù)據(jù)的物理結(jié)構(gòu)，它可以采用_順序存儲(chǔ)_ 或_鏈?zhǔn)酱鎯?chǔ)_ 兩種存儲(chǔ)方法。 9. 線性表有兩種存儲(chǔ)結(jié)構(gòu)，分別為_(kāi)順序存儲(chǔ) _ 和 鏈?zhǔn)酱鎯?chǔ)_。 10. 鏈?zhǔn)酱鎯?chǔ)的特點(diǎn)是利用指針來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系。 11. 若頻繁地對(duì)線性表進(jìn)行插入和刪除操作，該線性表宜采用鏈

4、式存儲(chǔ)存儲(chǔ)結(jié)構(gòu)。 12. 線性表中的數(shù)據(jù)元素之間具有_一對(duì)一_的線性關(guān)系，除第一個(gè)和最后一個(gè)元素外，其他數(shù)據(jù) 元素有且只有一個(gè)_直接后繼和直接前趨。 13. 在一個(gè)單鏈表中 p所指結(jié)點(diǎn)之后插入一個(gè)s所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行 s-next=_ p-next和 p-next=_ s的操作。 head-next=NULL 14. 在一個(gè)單鏈表中刪除 p的后繼結(jié)點(diǎn)q時(shí)，應(yīng)執(zhí)行以下操作 p-next=q-next。 15. 對(duì)帶頭結(jié)點(diǎn)head的單鏈表，則判斷其為空的條件為 16. 對(duì)帶頭結(jié)點(diǎn)head的循環(huán)單鏈表尾結(jié)點(diǎn)(由p所指向)判非空的條件為 _p-next=head 。 17. 在棧結(jié)構(gòu)中，允許插入的一端

5、稱為 _棧頂;在隊(duì)列結(jié)構(gòu)中，允許插入的一端稱為_(kāi)隊(duì)尾。 18. 隊(duì)列中元素的入隊(duì)和出隊(duì)?wèi)?yīng)遵循一先進(jìn)先出_ _原則，數(shù)據(jù)元素1，2, 3, 4，5按照次序入隊(duì) 后，第一個(gè)出隊(duì)的是 _1。 19. 在循環(huán)隊(duì)列中，存儲(chǔ)空間為0n-1。設(shè)隊(duì)頭指針front指向隊(duì)頭元素前一個(gè)空閑元素，隊(duì)尾指 針指向隊(duì)尾元素，那么其隊(duì)空標(biāo)志為rear=front ，隊(duì)滿標(biāo)志為_(kāi)(rear+1)% n=front_。 20. 設(shè)順序表有19個(gè)元素，第一個(gè)元素的地址為200,且每個(gè)元素占3個(gè)字節(jié)，則第14個(gè)元素的存 儲(chǔ)地址為_(kāi)239。 21. 在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素(K i n),需向前移動(dòng)n-i 個(gè)元素。

6、22. 在一個(gè)長(zhǎng)度為 n的順序表中第i個(gè)元素前(K i lchild=NULL 若初始記錄基本無(wú)序， 則最好選用快速排序。 99. 在對(duì)一組記錄(54,38,96,23,15,72, 60,45,83)進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄 60插入到有序表時(shí)，為尋找插入位置至少需比較_3次。 100. 設(shè)一組記錄關(guān)鍵字序列為(80, 70, 33, 65, 24, 56, 48)，則用篩選法建成的初始堆為_(kāi) ( 80, 70, 56, 65, 24, 33, 48)或 _(24 , 65, 33, 80, 70, 56, 48)。 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 1

7、1. 二、單選題 在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的基本單位是 （ ） A. 數(shù)據(jù)項(xiàng) B. 數(shù)據(jù)元素 C. 數(shù)據(jù)對(duì)象 D. 數(shù)據(jù)文件 數(shù)據(jù)結(jié)構(gòu)是（ ） A. 種數(shù)據(jù)類型B數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) C. 一組性質(zhì)相同的數(shù)據(jù)元素的集合 D.相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合 A.數(shù)據(jù)項(xiàng)B. 數(shù)據(jù)元素 C. 表元素 D. 字符 在數(shù)據(jù)結(jié)構(gòu)的討論中把數(shù)據(jù)結(jié)構(gòu)從邏輯上分為（ ）. A. 內(nèi)部結(jié)構(gòu)與外部結(jié)構(gòu) B. 靜態(tài)結(jié)構(gòu)與動(dòng)態(tài)結(jié)構(gòu) C. 線性結(jié)構(gòu)與非線性結(jié)構(gòu) D. 緊湊結(jié)構(gòu)與非緊湊結(jié)構(gòu)。 算法指的是（ ）。 A.計(jì)算機(jī)程序 B .解決問(wèn)題的計(jì)算方法 C .排序算法 D .解決問(wèn)題的有限運(yùn)算序列 算法分析的目的是（

8、A.辨別數(shù)據(jù)結(jié)構(gòu)的合理性 B .評(píng)價(jià)算法的效率 C.研究算法中輸入與輸出的關(guān)系 .鑒別算法的可讀性 某程序的時(shí)間復(fù)雜度為（ 3n+nlog 2n+n 2+8） , 其數(shù)量級(jí)表示為（ ）。 A. O（ n）B . O（ nlog 2n） C . O（ n ）D . O（ log 2n） for （ i=0 ； in ； i+ ） for （ j=0 ； jn ；j+ ） A i j =i*j ； 上述程序段的時(shí)間復(fù)雜度為 （） 2n） D.O（ 1） A.O（n2）B.O （n）C.O 以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)？ A. 隊(duì)列 B. 棧 C. 線性表 D. 二叉樹(shù) 設(shè)順序表有 9 個(gè)元素，則在第 3 個(gè)元素前插入一個(gè)元素所