《計(jì)算機(jī)文化基礎(chǔ)習(xí)題與答案(第3部分 數(shù)據(jù)結(jié)構(gòu)習(xí)題與答案)》由會(huì)員分享，可在線閱讀，更多相關(guān)《計(jì)算機(jī)文化基礎(chǔ)習(xí)題與答案(第3部分 數(shù)據(jù)結(jié)構(gòu)習(xí)題與答案)（57頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、 第3部分 數(shù)據(jù)結(jié)構(gòu)習(xí)題與答案 第12章 基礎(chǔ)知識(shí)及線性結(jié)構(gòu)習(xí)題 12．1 單項(xiàng)選擇題 1.以下術(shù)語(yǔ)中與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)的是 。 A）散列表 B）雙鏈表 C）棧 D）循環(huán)順序隊(duì)列 2.算法必須具備 、輸入、輸出5個(gè)特性。 A）可行性、可移植性、可擴(kuò)充性 B）可行性、確定性、有窮性 C）確定性、有窮性、穩(wěn)定性 D）易讀性、穩(wěn)定性、安全性 3.評(píng)價(jià)算法的兩個(gè)主要標(biāo)準(zhǔn)是 。 A）正確性和簡(jiǎn)明性 B）可讀性和文檔性 C）空間復(fù)雜度和時(shí)間復(fù)雜度

2、 D）數(shù)據(jù)復(fù)雜度和程序復(fù)雜度 4.在存儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值，而且還要表示出 。 A）數(shù)據(jù)的處理方法 B）數(shù)據(jù)元素之間的關(guān)系 C）數(shù)據(jù)元素的類型 D）數(shù)據(jù)的存儲(chǔ)方法 5.程序段 for(i=0;i

3、于存儲(chǔ)線性結(jié)構(gòu) B) 對(duì)二叉樹只能用鏈接方式存儲(chǔ) C) 對(duì)二維數(shù)組只能用順序方式存儲(chǔ) D) 數(shù)據(jù)運(yùn)算的實(shí)現(xiàn)與存儲(chǔ)結(jié)構(gòu)有關(guān) 7.線性表是 。 A）一個(gè)有限序列，可以為空 B）一個(gè)有限序列，不可以為空 C）一個(gè)無限序列，可以為空 D）一個(gè)無限序列，不可以為空 8.順序表的優(yōu)點(diǎn)是 。 A）所需空間隨線性表長(zhǎng)度的變化而變化 B）可隨機(jī)訪問指定下標(biāo)的元素 C）插入和刪除不需要移動(dòng)元素 D）不必事先估計(jì)存儲(chǔ)空間 9.假設(shè)對(duì)一個(gè)線性表很少進(jìn)行插入、刪除，但經(jīng)常要訪問其中指定下標(biāo)的元素。該線性表適合采用的存儲(chǔ)方

4、式是 。 A）單鏈表 B）散列表 C）順序表 D）循環(huán)鏈表 10.線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)地址 。 A）必須是不連續(xù)的 B）連續(xù)與否均可 C）必須是連續(xù)的 D）和頭結(jié)點(diǎn)的存儲(chǔ)地址相連續(xù) 11.線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，數(shù)據(jù)元素的邏輯順序與在內(nèi)存中的存儲(chǔ)順序 。 A）一致 B）也可能不一致 C）完全不一致 D）有一定的關(guān)系 12.以下存儲(chǔ)結(jié)構(gòu)中不利于線性表長(zhǎng)度變化的是 。 A）單鏈表 B）順序表 C）循環(huán)鏈表 D）雙鏈表 13.用鏈接方式存儲(chǔ)線性

5、表的優(yōu)點(diǎn)是 。 A）便于隨機(jī)存取指定下標(biāo)的元素 B）存儲(chǔ)密度高 C）插入和刪除不需要移動(dòng)元素 D）可以用元素在存儲(chǔ)器中的物理位置表示元素之間的邏輯關(guān)系 14.在一個(gè)長(zhǎng)度為n的順序表中，向第i個(gè)元素（0≤i≤n）之前插入一個(gè)新元素時(shí)，需要向后移動(dòng)的元素個(gè)數(shù)為 。 A）n-i B）n-i+1 C）n-i-1 D）i 15.在一個(gè)長(zhǎng)度為n的順序表中，刪除第i個(gè)元素（0≤i≤n-1）時(shí)，需要向前移動(dòng)的元素個(gè)數(shù)為 。 A）n-i B）n-i+1 C）n-i-1 D）i 16.設(shè)

6、指針p指向單鏈表中的結(jié)點(diǎn)m，若要?jiǎng)h除m之后的結(jié)點(diǎn)（假設(shè)其存在），則需要執(zhí)行的修改指針操作為 。 A) p->next=p B) p->next=p->next->next C) p=p->next D) p= p->next->next 17.如果對(duì)某線性表最常用的操作是取第i個(gè)結(jié)點(diǎn)及其前驅(qū)，則采用 存儲(chǔ)方式最節(jié)省時(shí)間。 A）單鏈表 B）雙鏈表 C）單循環(huán)鏈表 D）順序表 18.對(duì)某線性表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入和刪除開始結(jié)點(diǎn)，為節(jié)省運(yùn)行時(shí)間應(yīng)采用的存儲(chǔ)方式是 。 A）單鏈表 B

7、）僅有頭指針的單循環(huán)鏈表 C）雙鏈表 D）僅有尾指針的單循環(huán)鏈表 19.與單鏈表相比，雙鏈表的優(yōu)點(diǎn)之一是 。 A）向前后兩個(gè)方向順序訪問相鄰結(jié)點(diǎn)更方便 B）可以進(jìn)行隨機(jī)訪問 C）插入、刪除操作更簡(jiǎn)單 D）使用的空間更小 20.鏈表不具備的特點(diǎn)是 。 A）所需空間隨線性表長(zhǎng)度的變化而變化 B）可隨機(jī)訪問指定下標(biāo)的元素 C）插入和刪除不需要移動(dòng)元素 D）不必事先估計(jì)存儲(chǔ)空間 21.設(shè)對(duì)一組數(shù)據(jù)的處理具有“后進(jìn)先出”的特點(diǎn)，則應(yīng)采用的最佳數(shù)據(jù)結(jié)構(gòu)是 。 A）隊(duì)列 B）

8、棧 C）順序表 D）二叉樹 22.若進(jìn)棧序列為3、5、7、9，進(jìn)棧和出?？纱┎暹M(jìn)行，則不可能的出棧序列是 。 A）7，5，3，9 B）9，5，7，3 C）9，7，5，3 D）7，5，9，3 23.設(shè)用一維數(shù)組A[m]存儲(chǔ)棧，令A(yù)[m-1]為棧底，t指示當(dāng)前棧頂?shù)奈恢?。如果棧不空，則出棧時(shí)應(yīng)使 。 A）t=t+1 B）t=t-1 C）t=m-1 D）不改變t 24.設(shè)用一維數(shù)組A[m]存儲(chǔ)棧，令A(yù)[0]為棧底，top指示當(dāng)前棧頂?shù)奈恢茫?dāng)把棧清空時(shí)所要執(zhí)行的操作是 。 A）top-- B）top=0

9、 C）top=-1 D）top=m-1 25.設(shè)棧s的初始狀態(tài)為空，如果進(jìn)棧序列為1、2、3、4、5、6，出棧序列3、2、5、6、4、1，則s的容量至少是 。 A）6 B）4 C）2 D）3 26.設(shè)棧S最多能容納4個(gè)元素，現(xiàn)有A、B、C、D、E、F六個(gè)元素按順序進(jìn)棧，以下可能的出棧序列是 。 A）E、D、C、B、A、F B）B、C、E、F、A、D C）C、B、F、D、A、E D）A、D、F、E、B、C 27．鏈?zhǔn)綏Ｅc順序棧相比，一個(gè)比較明顯的優(yōu)點(diǎn)是 。 A）插入操作更加方便 B）通

10、常不會(huì)出現(xiàn)棧滿的情況 C）不會(huì)出現(xiàn)?？盏那闆r D）刪除操作更加方便 28．在完成出棧操作時(shí)， 。 A）必須判斷棧是否滿 B）要判別棧元素的類型 C）必須判斷棧是否空 D）不必做任何判斷 29.已知棧的入棧序列是1、2、3、……、n，出棧序列是e1、e2、……、en，若e1=n，則ei為 。 A）i B）n-i+1 C）n-i D）不能確定 30.在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題時(shí)，通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，打印機(jī)則從該緩沖區(qū)取出數(shù)據(jù)打印，該緩沖

11、區(qū)應(yīng)該是一個(gè) 結(jié)構(gòu)。 A）棧 B）隊(duì)列 C）線性表 D）數(shù)組 31. 不是隊(duì)的基本運(yùn)算。 A）向隊(duì)尾插入一個(gè)元素 B）讀隊(duì)頭元素 C）刪除隊(duì)中第i個(gè)元素 D）判隊(duì)是否為空 32．當(dāng)以順序方式存儲(chǔ)隊(duì)列時(shí)，解決“假溢出”較為有效的方法是采用 。 A）順序隊(duì)列 B）鏈?zhǔn)疥?duì)列 C）順序循環(huán)隊(duì)列 D）三種都可以 33.設(shè)數(shù)組Q用于存放循環(huán)隊(duì)列中的元素，同時(shí)用f指示當(dāng)前隊(duì)頭元素的位置，r指示當(dāng)前隊(duì)尾元素的下一個(gè)位置。假定隊(duì)中元素個(gè)數(shù)總小于m，則計(jì)算隊(duì)列中元素個(gè)數(shù)的公式為

12、 。 A）(m+r-f)%m B）r-f C）m-(f-r) D）(m+(f-r))%m 34.若用一個(gè)大小為10的一維數(shù)組存儲(chǔ)順序循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為4和8，當(dāng)從隊(duì)列中刪除3個(gè)元素再加入2個(gè)元素后，rear和front的值分別是 。 A）無法完成要求的操作 B）1和6 C）7和0 C）11和6 35.棧和隊(duì)列都是運(yùn)算受限的線性表，它們的共同點(diǎn)是 。 A）只允許在端點(diǎn)處插入和刪除元素 B）元素都是后進(jìn)先出 C）元素都是先進(jìn)先出 D）必須采用順序存儲(chǔ)結(jié)構(gòu) 3

13、6.一維數(shù)組和線性表的區(qū)別是 。 A）前者長(zhǎng)度固定，后者長(zhǎng)度可變 B）兩者長(zhǎng)度均可變 C）兩者長(zhǎng)度均固定 D）前者長(zhǎng)度可變，后者長(zhǎng)度固定 37.多維數(shù)組中元素之間的關(guān)系 。 A）是線性的 B）是樹形的 C）既是線性的，又是樹形的 D）既非線性的，也非樹形的 38.不屬于數(shù)組基本運(yùn)算的是 。 A）數(shù)組的轉(zhuǎn)置 B）數(shù)組相加 C）插入 D）數(shù)組相乘 39.設(shè)有n×n階的對(duì)稱矩陣A，為節(jié)省存儲(chǔ)空間，只將主對(duì)角線及主對(duì)角線之上的元素按行優(yōu)先順序存放到一維數(shù)組B中，則數(shù)組B的最小

14、容量是 。 A）n×n B）(n+1)/2 C）n2/2 D）n(n+1)/2 40.上題中，存儲(chǔ)矩陣A上三角中任意元素aij(0≤i≤j≤n-1)的B數(shù)組元素的下標(biāo)為 。 A）i+j B）i(i+1)/2+j C）i(2n-i-1)/2+j D）i×n+j 41.若把三對(duì)角矩陣帶狀區(qū)域中的元素按行優(yōu)先順序存放在一維數(shù)組B中，則存儲(chǔ)處于帶狀區(qū)域上的元素aij(|i-j|≤1)的數(shù)組B中的元素下標(biāo)為 。 A）3i-j B）i+j+1 C）2i+j

15、 D）i+2j-1 42.串是一種特殊的線性表，其特殊性體現(xiàn)在 。 A）可以順序存儲(chǔ) B）可以鏈接存儲(chǔ) C）數(shù)據(jù)元素是一個(gè)字符 D）數(shù)據(jù)元素可以是多個(gè)字符 43.兩個(gè)串相等的充分必要條件是 。 A）長(zhǎng)度相等 B）長(zhǎng)度相等且對(duì)應(yīng)位置的字符相同 C）長(zhǎng)度相等且前面若干個(gè)對(duì)應(yīng)位置的字符相同 D）前面若干個(gè)對(duì)應(yīng)位置的字符相同 44.串是 。 A）不少于一個(gè)字符的序列 B）任意個(gè)字符的序列 C）有限個(gè)字符的序列 D）一個(gè)字符 45.空串是 的字符串。 A）含有

16、一個(gè)空格符 B）只含空格符 C）不含任何字符 D）任意 46.一個(gè)空串的長(zhǎng)度是 。 A）0 B）1 C）沒有長(zhǎng)度 D）不確定 47.串的長(zhǎng)度是串中 。 A）字母字符的個(gè)數(shù) B）不同字符的個(gè)數(shù) C）除空格符外字符的個(gè)數(shù) D）字符的個(gè)數(shù) 答案： 1.C 2.B 3.C 4.B 5.A 6.D 7.A 8.B 9.C 10.B 11.B 12.B 13.C 14.A 15.C 16.B 17.D 18.D 19.A 20.B 21.B 22.B 23.A 24.C 25.D 2

17、6.C 27.B 28.C 29.B 30.B 31.C 32.C 33.A 34.B 35.A 36.A 37.D 38.C 39.D 40.C 41.C 42.C 43.B 44.C 45.C 46.A 47.D 12.2 簡(jiǎn)答題 1.什么是數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)?數(shù)據(jù)的邏輯結(jié)構(gòu)可以劃分為哪幾類?數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有哪四種基本存儲(chǔ)方式? 答：數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)之間所具有的邏輯關(guān)系。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)則是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的具體實(shí)現(xiàn)。數(shù)據(jù)的邏輯結(jié)構(gòu)可分為集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)四類基本類型，其中，樹形結(jié)構(gòu)和圖形結(jié)構(gòu)又合稱為非線性結(jié)構(gòu)；數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

18、有順序方式、鏈接方式、索引方式和散列方式4種基本方式。 2. 請(qǐng)說明評(píng)價(jià)排序算法的好壞的兩個(gè)標(biāo)準(zhǔn)。 答：執(zhí)行算法所需要的時(shí)間；執(zhí)行算法所需要的空間。 3. 如果一個(gè)線性表中元素的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取表中指定位置的元素，對(duì)該線性表應(yīng)選用何種存儲(chǔ)結(jié)構(gòu)？為什么？ 答：應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)。因?yàn)?，在以順序方式存?chǔ)線性表時(shí)，線性表中元素的存儲(chǔ)順序與邏輯順序相一致，根據(jù)元素的下標(biāo)可以很快地找到它的存儲(chǔ)位置。 4.一個(gè)理發(fā)店有兩名理發(fā)師，一名理發(fā)師專為年紀(jì)最大的顧客服務(wù)，另一名理發(fā)師為進(jìn)入理發(fā)店時(shí)間最長(zhǎng)的顧客服務(wù)，進(jìn)入理發(fā)店的顧客根據(jù)到達(dá)的時(shí)間先后

19、順序都排入一個(gè)隊(duì)列。假設(shè)用程序來模擬理發(fā)店顧客隊(duì)列的變化情況，該顧客隊(duì)列在邏輯上可視為哪種數(shù)據(jù)結(jié)構(gòu)？要存儲(chǔ)相關(guān)信息應(yīng)采用哪一種存儲(chǔ)結(jié)構(gòu)？為什么？ 答：線性表，因?yàn)轭櫩统鲫?duì)沒有限定在一端；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，因?yàn)樾聛淼念櫩鸵尤腙?duì)列，接受理發(fā)師服務(wù)的顧客要離開隊(duì)列，對(duì)顧客隊(duì)列這個(gè)線性表來說，需要經(jīng)常的插入和刪除操作。 5. 單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是什么？ 答：設(shè)置頭結(jié)點(diǎn)后，由于頭指針總是指向頭結(jié)點(diǎn)，所以在實(shí)現(xiàn)對(duì)單鏈表的操作時(shí)不必區(qū)分空表和非空表，對(duì)開始結(jié)點(diǎn)的操作與對(duì)其他結(jié)點(diǎn)的操作也相同，這樣，可簡(jiǎn)化處理。 6. 設(shè)棧S的初始狀態(tài)為空，隊(duì)列Q的初始狀態(tài)為 隊(duì)頭

20、 隊(duì)尾 a1 a2 a3 a4 對(duì)棧S和隊(duì)列Q進(jìn)行以下操作： 1） Q中元素依次出隊(duì)，并壓入棧S中，直至Q為空。 2） 依次彈出S中的元素并進(jìn)入Q，直至S為空。 請(qǐng)畫出在上述操作后隊(duì)列Q的狀態(tài)。 隊(duì)頭 隊(duì)尾 a4 a3 a2 a1 答： 7.在以順序方式存儲(chǔ)隊(duì)列時(shí)，會(huì)出現(xiàn)“假溢出”現(xiàn)象，清解釋這一現(xiàn)象，并說明解決“假溢出”的方法及其原理。 答：“假溢出”是指存儲(chǔ)隊(duì)列的空間中還有空余，但不能進(jìn)行入隊(duì)操作，它是由隊(duì)列的操作方式?jīng)Q定的。 解決“假溢出”的方法有： 1）建立一個(gè)足夠大的存儲(chǔ)空間，但這樣會(huì)造成空間的浪費(fèi)

21、。 2）采用循環(huán)隊(duì)列方式。把存儲(chǔ)隊(duì)列的一維空間看成是一個(gè)首尾相接的圓環(huán)，這樣就可以實(shí)現(xiàn)對(duì)由于元素出隊(duì)而空出來的空間的循環(huán)使用。 3）采用平移元素的方法。每當(dāng)出現(xiàn)“假溢出”時(shí)，將隊(duì)列中所有元素平移，使當(dāng)前隊(duì)頭元素位于數(shù)組的最前端，并修改隊(duì)頭和隊(duì)尾指示器。此方法效率很低。 8.設(shè)用一維數(shù)組A[m]存儲(chǔ)循環(huán)隊(duì)列，只設(shè)置一個(gè)隊(duì)頭指示器front，和一個(gè)用以記錄隊(duì)列中元素個(gè)數(shù)的計(jì)數(shù)器count。在此情況下，隊(duì)空、隊(duì)滿的條件是什么？如何確定將要入隊(duì)元素的位置？ 答：1）隊(duì)空條件為：count=0 2）隊(duì)滿條件為：count=m 3）將要入隊(duì)元素的位置是：(front+count

22、)%m 9. 給出以下稀疏矩陣的三元組表。 答： 12.3 程序填空題 1.有n個(gè)人排成一排，每個(gè)人的編號(hào)為i(1≤i≤n)，現(xiàn)讓這n個(gè)人從左到右1、2、1、2、……報(bào)數(shù)，凡報(bào)“1”的人出列，報(bào)“2”的人立即站到隊(duì)的最右端，此過程反復(fù)進(jìn)行，直到n個(gè)人都已出列。設(shè)已知n個(gè)人原來在隊(duì)列中的順序，以下程序可求出他們出列的順序。例如，設(shè)n=6，初始順序?yàn)?、2、3、4、5、6，則出列順序?yàn)?、3、5、2、6、4。 算法說明:此問題可利用隊(duì)列結(jié)構(gòu)處理。設(shè)一維數(shù)組p[]存放循環(huán)隊(duì)列，f和r分別為隊(duì)列的隊(duì)頭和隊(duì)尾指示器，首先讓n個(gè)人的初始序號(hào)依次入隊(duì)，然后反復(fù)執(zhí)行

23、以下操作，直到隊(duì)列為空。 (1)輸出隊(duì)頭元素，并刪除之。 (2)若剛剛離隊(duì)的元素值在當(dāng)時(shí)的隊(duì)列中最大，則記錄下當(dāng)前隊(duì)列中最大元素值，否則將隊(duì)頭元素插入到隊(duì)尾。 程序如下: #include using std::cout; using std::endl; const int N=20; int main(){ int p[N]; int f=0,r=0，qm=N; for(int i=1;i<=N;i++){

24、 p[ (1) ]=i; r=(r+1)%N; } do{ int t=p[f]; cout<

25、 (4) ; f= (5) ; } }while(f!=r); cout<

26、A[i]為偶數(shù)，A[j]為奇數(shù)，則交換A[i]和A[j]。當(dāng)i和j重合時(shí)，算法結(jié)束。 void oddbefore(int A[],int n){ int i,j,t; i=0; j=n-1; while(i

27、} } 答：（1）(i void delall(T A[],int &n,T x,T y){ int i=0,k=0; while(i

28、[i]; //前移k個(gè)位置 i++; } n= （3） ; } 答：（1）A[i]>=x&&A[i]<=y （2）i-k （3）n-k 4.假定一維數(shù)組A中有多個(gè)零元素，以下函數(shù)可以實(shí)現(xiàn)將A中所有非零元素依次移到數(shù)組的前端，并保持它們的相對(duì)位置不變。下面是用兩種方法實(shí)現(xiàn)上述功能的函數(shù)。 方法一 算法說明:依次考查數(shù)組中的各個(gè)元素，若發(fā)現(xiàn)一個(gè)零元素，則將此元素之后的所有元素依次前移一個(gè)位置。 程序如下: void mov1(int A[],int n){ //n為數(shù)組A中包含的元素個(gè)數(shù)

29、 int i,j,k; i=0;k=n-1; while(i<=k) if(A[i]==0){ for(j=i+1; (1) ;j++) (2) =A[j]; A[k]=0; (3) ; } else (4) ; } 答：(1)j<=k (2)A[j-1] (

30、3)k-- (4)i++ 方法二 算法說明:在數(shù)組中找到第一個(gè)為零的元素A[i]，然后找出該元素后面的第一個(gè)非零元素A[j]，將A[j]存入A[i]，再將A[j]置為0，使i增1，繼續(xù)以上過程。 程序如下: void mov2(int A[]，int n){ //n為數(shù)組A中包含的元素個(gè)數(shù) int i=0,j; while( (1) )i++; (2) ; while(j

31、 if( (3) ){ A[i]=A[j]; A[j]=0; i++; } (4) ; } } 答： (1)i

32、x; for(i=0; （1） ;i++){ x=a[n-1]; for( （2） ;j>0;j--) a[j]=a[j-1]; （3） ; } } 答：（1）i

33、(1) ){ if(A[k]!=A[i]){ k++; A[k]=A[i]; } (2) ; } return (3) ; } 答：(1)i void Chain::Rev

34、erse(){ Node *current = head->next, //指向當(dāng)前處理的結(jié)點(diǎn) *next, // 指向當(dāng)前結(jié)點(diǎn)的直接后繼 *last = 0; // 指向反轉(zhuǎn)后當(dāng)前結(jié)點(diǎn)的直接后繼 while (current) { next = current->next; current->next = last; （1） = current; current = next; } （2） = last;

35、 //last指向反轉(zhuǎn)后鏈表的開始結(jié)點(diǎn) } 答：（1）last （2）head->next 8．IsSorted是在單鏈表類Chain中增加的成員函數(shù)，它的功能是檢查單鏈表中元素是否為非遞減順序，如果是，返回true，否則返回false。 template bool Chain::IsSorted() const{ if (length==0) return true; // 表空 Node *current = head->next, //指向當(dāng)前處理的結(jié)點(diǎn) *nex

36、t = current->next; //指向當(dāng)前結(jié)點(diǎn)的直接后繼 while ( （1） ) { if (current->data > next->data) （2） ; current = next; next = （3） ; } return true; } 答：（1）next （2）return false （3）current->next 9.Del是在單鏈表類Chain中增加的成員函數(shù)，其功能是刪除單鏈表中值相同的重復(fù)結(jié)點(diǎn)。 template<

37、class T> void Chain::Del(){ Node *p,*pre,*q; p=head->next; while( （1） ){ pre=p; q=p->next; while(q!=NULL){ while(q!=NULL && （2） ){ pre=q; q=q->next; } if(q!=NULL){ pre->next=q->next; delete q; q=pre->next; } } p=p->n

38、ext; } } 答：（1）p!=NULL （2）q->data!=p->data 10.已知A，B和C為三個(gè)遞增有序的線性表，現(xiàn)對(duì)A表進(jìn)行如下操作：刪去那些既在B表又在C表中出現(xiàn)的元素。在以下實(shí)現(xiàn)上述操作的函數(shù)中，假定線性表以順序方式存儲(chǔ)。 template void SeqList_Delete(SeqList &A,SeqList &B,SeqList &C){ int i,j,k; i=j=k=0; T a,b,c,x; while(i

39、ngth()){ B.Find(j,b); C.Find(k,c); if(b

40、 A.Delete(i,a); //刪除等于x的元素 } } } 答：（1）j++ （2）b>c 11.以下函數(shù)用于檢驗(yàn)一個(gè)表達(dá)式中括號(hào)是否匹配。如果匹配返回1，否則返回0。設(shè)表達(dá)式中只使用了括號(hào)()和方括號(hào)[]，表達(dá)式在一維數(shù)組exp[]中。 算法說明:為檢查表達(dá)式中括號(hào)的匹配情況，可設(shè)置一個(gè)棧s。從左到右掃描表達(dá)式，若當(dāng)前字符為左括號(hào)，則將其壓入棧s中。若當(dāng)前字符為右括號(hào)，則檢查它是否與棧頂?shù)淖罄ㄌ?hào)相匹配。若相匹配，則刪去這一對(duì)括號(hào);不相匹配，則表示表達(dá)式中括號(hào)不匹配。若掃描完表達(dá)式時(shí)棧為空，則說明表達(dá)式中括號(hào)是匹配的，否則是不匹配的。函數(shù)中使用變量

41、flag作為括號(hào)匹配的標(biāo)志，flag為1表示匹配，flag為0表示不匹配。 程序如下: const int MaxSize 100 int matching(char exp[MaxSize]){ char s[MaxSize]; int top=-1; //s作為順序棧，top為棧頂指示器 int flag,i; flag=1;i=0; while(exp[i]!=′′&&flag){ switch

42、(exp[i]&&flag){ case′(′: case′[′: (1) =exp[i];break; case′)′: if( (2) )top--; else flag=0; break; case′]′: if( (3

43、) )top--; else flag=0; break; } (4) ; } if( (5) )return 1; else return 0; } 答：(1)s[++top] (2)top!=-1 && s[top]==′(′ (3)top!=-1 && s[top]==′[′ (4)i++ (5)flag && top==

44、-1 12.編寫一個(gè)函數(shù)，利用隊(duì)列和棧的基本運(yùn)算將指定隊(duì)列中的元素進(jìn)行逆轉(zhuǎn)。 算法說明：利用一個(gè)臨時(shí)棧tempst，將指定隊(duì)列que中所有元素出隊(duì)并入棧到tempst，然后再將棧tempst中的所有元素出棧并入隊(duì)到que，此時(shí)，隊(duì)列que中的元素已發(fā)生逆轉(zhuǎn)。在以下函數(shù)中使用了STL的容器適配器定義隊(duì)列和棧。 程序如下： #include #include using namespace std; template void reverse_que(queue &que){ T x; stack

45、 tempst; while( （1） ){ x=que.front(); //取隊(duì)頭元素到x tempst.push(x); //x入棧 （2） ; } while(!tempst.empty()){ //當(dāng)棧不為空時(shí) x=tempst.top(); //取棧頂元素到x （3） ; tempst.pop(); //出棧 } } 答：（1）!que.empty() （2）que.pop() （3）que.push(x) 13.以下函數(shù)在字符串s中尋找是否存

46、在與字符串t相同的子串，是，則返回子串的起始位置，否則返回-1。(若有多個(gè)匹配的子串，只返回第一個(gè)子串的位置)。 int IndexBF(char s[],char t[]){ int i=0，j=0; while(s[i+j]!=′\0′&&t[j]!=′\0′) if(s[i+j]==t[j]) (1) ; else{ i++; (2) ; } if( (3) )ret

47、urn i; else return -1; } 答：(1) j++ (2) j=0 (3) t[j]==′\0′ 14.以下函數(shù)計(jì)算一個(gè)子串t在一個(gè)字符串s中出現(xiàn)的次數(shù)，如果子串不出現(xiàn)則為0。 int substr_count(char t[],char s[]){ int i,j,k,count=0; for(i=0; （1） ;i++){ for(j=i,k=0; （2） ;j++,k++); if(t[k]==0)count++; } （3） ; } 答：（1）

48、s[i]!='\0' （2）s[j]==t[k]&&t[k]!=0 （3）return count 15.如果矩陣A中元素A[i][j]滿足以下條件：它是第i行中值最大的元素，同時(shí)又是第j列中值最小的元素，則稱該元素為矩陣的一個(gè)鞍點(diǎn)。編寫函數(shù)求出m×n階矩陣A的所有鞍點(diǎn)。為簡(jiǎn)單起見，這里假定每行和每列中的元素各不相同。 算法說明：先求出每行值最小的元素，放入一維數(shù)組min之中，再求出每列值最大的元素，放入一維數(shù)組max之中，比較min和max中的元素，如果min[i]和max[j]相等，則說明A[i][j]是一個(gè)鞍點(diǎn)。 #include

49、 using std::cout; using std::endl; const int m=3,n=4; void minmax(int A[m][n]){ int min[m],max[n]; int i,j,have=0; for(i=0;imax

50、[j])max[j]=A[i][j]; } for(i=0;i

51、說明：在稀疏矩陣的三元組表示中，非0元素按行優(yōu)先順序存放。為保證轉(zhuǎn)置后的矩陣在B中按行優(yōu)先順序存放，需要在A中首先找出下標(biāo)為0列的所有元素（它們是轉(zhuǎn)置矩陣下標(biāo)為0行的非0元素），將它們依次存放在B中。按此方法逐列處理即可。 程序如下： template void transpose(T A[][3],T B[][3]){ int m,n,t; m=A[0][0]; //稀疏矩陣的行數(shù) n=A[0][1]; //稀疏矩陣的列數(shù) t=A[0][2]; //稀疏矩陣中非0元素的個(gè)數(shù) B[0][0]= （1） ; B[0][1]=

52、（2）; B[0][2]=t; int p,q,col; if(t>0){ q=1; for(col=0;col

53、寫函數(shù)計(jì)算C=A×B，要求C也采用三元組表示。 算法說明：為通過給定的行下標(biāo)i和列下標(biāo)j找出原矩陣的對(duì)應(yīng)元素，這里設(shè)計(jì)了一個(gè)函數(shù)value，如果在三元組中找到該元素，則返回其值，否則，返回0。 template T value(T x[][3],int i,int j){ int k=1; while(k<=x[0][2] && x[k][0]!=i && x[k][1]!=j) k++; if(k<=x[0][2]) （1） ; else return 0; } template void mat

54、mul(T A[][3],T B[][3],T C[][3],int m,int n,int l){ int i,j,k,p,s; p=1; for(i=0;i

55、2]= (3) ; } 答：（1）return x[k][2] （2）s=0 (3) p-1 第13章 非線性結(jié)構(gòu) 13.1 單項(xiàng)選擇題 1.樹的深度是指 。 A）樹中結(jié)點(diǎn)的個(gè)數(shù) B）結(jié)點(diǎn)子樹的個(gè)數(shù) C）樹中結(jié)點(diǎn)的最大層數(shù) D）結(jié)點(diǎn)子樹的最多個(gè)數(shù) 2.設(shè)二叉樹根結(jié)點(diǎn)的層數(shù)為0，一棵高度為h的滿二叉樹中結(jié)點(diǎn)的個(gè)數(shù)是 。 A）2h B）2h-1 C）2h-1 D）2h+1-1 3.某二叉樹的先序遍歷序列為abdgcefh，中序遍歷序列為dgbaechf，則其后序遍歷序列為

56、 。 A）bdgcefha B）gdbecfha C）bdgaechf D）gdbehfca 4.任何一棵二叉樹的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序 。 A）都不相同 B）完全相同 C）有時(shí)相同有時(shí)不同 D）先序和中序相同，而與后序不同 5.二叉樹的先序遍歷序列等同于該二叉樹對(duì)應(yīng)森林的 。 A）層次遍歷序列 B）先根遍歷序列 C）后根遍歷序列 D）以上都不是 6.對(duì)圖5.1所示的表達(dá)式二叉樹按中序遍歷得到的結(jié)點(diǎn)序列是 。 A）c-d*b+a-e/f

57、 B）a+b*c-d-e/f C）a+c-d*b/e-f D）abcd+-*/ef 7. 前序遍歷序列與中序遍歷序列相同的二叉樹為 。 A)根結(jié)點(diǎn)無左子樹的二叉樹 B)根結(jié)點(diǎn)無右子樹的二叉樹 C)只有根結(jié)點(diǎn)的二叉樹或非葉子結(jié)點(diǎn)只有左子樹的二叉樹 D)只有根結(jié)點(diǎn)的二叉樹或非葉子結(jié)點(diǎn)只有右子樹的二叉樹 8.前序遍歷序列與后序遍歷序列相同的二叉樹為 。 A)非葉子結(jié)點(diǎn)只有左子樹的二叉樹 B)只有根結(jié)點(diǎn)的二叉樹 C)根結(jié)點(diǎn)無右子樹的二叉樹 D)非葉子結(jié)點(diǎn)只有右子樹的二叉樹 9.設(shè)a、b為一棵二叉樹上

58、的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，a在b前的條件是 。 A）a是b的祖先 B）a是b的子孫 C）a在b的右方 D）a在b的左方 10．設(shè)結(jié)點(diǎn)x和結(jié)點(diǎn)y是二叉樹T中的任意兩個(gè)結(jié)點(diǎn)，若在先根序列中x在y之前，而在后根序列中x在y之后，則x和y的關(guān)系是 。 　　　 A）x是y的左兄弟　　 B）x是y的右兄弟 　　　 C）x是y的祖先　　　 D）x是y的后代 11.如果F是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點(diǎn)的前序序列就是F中結(jié)點(diǎn)的 。 A）中序序列 B）先序序列 C）后序序列 D）層次序列 12.

59、設(shè)二叉樹根結(jié)點(diǎn)的層數(shù)為0，一棵高度為h(h>0)的完全二叉樹中，第h-1層上包含的結(jié)點(diǎn)個(gè)數(shù)為 。 A）不確定 B）2h C）2h-1 D）2h-1+1 13.對(duì)于一個(gè)有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)它為一棵 時(shí)高度最小。 A）單支樹 B）完全二叉樹 C）二叉排序樹 D）哈夫曼樹 14.把一棵含70個(gè)結(jié)點(diǎn)的完全二叉樹以順序方式存儲(chǔ)在一維數(shù)組A中，該完全二叉樹中編號(hào)為26的結(jié)點(diǎn)的左子女存放在中 。 A）A[53] B）A[54] C.A[52] D）該結(jié)點(diǎn)設(shè)有

60、左子女 15.在以鏈接方式存儲(chǔ)一棵具有n個(gè)結(jié)點(diǎn)的二叉樹時(shí)，對(duì)應(yīng)二叉鏈表中指針域的總數(shù)是 。 A）2n個(gè) B）n個(gè) C）n-1個(gè) D）n+1個(gè) 16.設(shè)F是由T1、T2、T3三棵樹組成的森林，與F對(duì)應(yīng)的二叉樹為B。已知T1、T2、T3中包含的結(jié)點(diǎn)個(gè)數(shù)分別是m1、m2和m3，則B的根結(jié)點(diǎn)左子樹中結(jié)點(diǎn)的個(gè)數(shù)是 。 A）m1 B）m2 C）m3-1 D）m1-1 17.在上題中，二叉樹根結(jié)點(diǎn)右子樹中結(jié)點(diǎn)的個(gè)數(shù)是 。 A）m1+m2 B）m3 C）m2+m3

61、 D）m2+m3-1 18.設(shè)森林F對(duì)應(yīng)的二叉樹為B，它有m個(gè)結(jié)點(diǎn)，B的根為P，P的右子樹有n個(gè)結(jié)點(diǎn)，則F中第一棵樹的結(jié)點(diǎn)數(shù)目是 。 A）m-n-1 B）n+1 C）m-n+1 D）m-n 19.樹T的度為4，其中度為1、2、3、4的結(jié)點(diǎn)個(gè)數(shù)分別是4、2、1、1，則T中葉結(jié)點(diǎn)的個(gè)數(shù)為 。 A）5 B）6 C）7 D）8 20.由三個(gè)結(jié)點(diǎn)可以構(gòu)造出種不同的形態(tài)的樹 。 A）2 B）3 C）4 D）5 21.由三個(gè)結(jié)點(diǎn)可以構(gòu)造出種不同的形態(tài)

62、的二叉樹 。 A）2 B）3 C）4 D）5 22.設(shè)二叉樹B中度為2的結(jié)點(diǎn)個(gè)數(shù)是n2，則B中葉結(jié)點(diǎn)的個(gè)數(shù)是 。 A）n2 B）n2-1 C）n2+2 D）n2+1 23.n個(gè)葉結(jié)點(diǎn)的哈夫曼樹的結(jié)點(diǎn)總數(shù)是 。 A）2n+1 B）2(n+1) C）無法確定 D）2n-1 24.由權(quán)值{9，2，5，7}構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長(zhǎng)度是 。 A）23 B）37 C）46 D）44 25.有關(guān)二叉樹的下列說法中正確的是

63、 。 A）二叉樹的度為2 B）二叉樹的度可以小于2 C）二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為2 D）一棵二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2 26.在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的 倍。 A）1/2 B）4 C）1 D）2 27.在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的 倍。 A）1/2 B）4 C）1 D）2 28.設(shè)無向圖G的頂點(diǎn)數(shù)為n，圖G可能具有的最少邊數(shù)和最多邊數(shù)分別是 。 A）0和n(n-1)/2 B)0和n C)n和n(n-

64、1)/2 D）1和n(n-1)/2 29.具有4個(gè)頂點(diǎn)的完全無向圖應(yīng)有 條邊。 A）12 B）16 C）20 D）6 30.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無向圖，如果采用鄰接矩陣表示，則相應(yīng)的矩陣大小是 。 A）n(n+1) B）(n-1)(n-1) C) n2 D) n(n-1) 31.在一個(gè)圖G的鄰接表表示中，每個(gè)頂點(diǎn)的鄰接表中包含的結(jié)點(diǎn)數(shù)，對(duì)于有向圖和無向圖而言分別等于該頂點(diǎn)的 。 A）入度數(shù)和度數(shù) B）出度數(shù)和度數(shù) C）均為度數(shù) D）與頂點(diǎn)無關(guān) 32.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)e條邊的無

65、向圖，若采用鄰接表表示，則頂點(diǎn)表的大小為 。 A）n B) n+1 C) n-1 D) n+e 33.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)e條邊的無向圖，若采用鄰接表表示，則所有邊表中邊結(jié)點(diǎn)的總數(shù)為 。 A）e/2 B) e C) 2e D) n+e 34.在圖5.2所示的有向圖中，頂點(diǎn)V2的入度是 。 圖5.2 A）6 B）4 C）2 D）1 35.對(duì)某個(gè)無向圖的鄰接矩陣來說， 。 A） 矩陣中非零元素的個(gè)數(shù)等于圖中的邊數(shù) B） 矩陣中零元素的

66、個(gè)數(shù)等于圖中的邊數(shù) C） 第i行上非零元素的個(gè)數(shù)等于第i列上非零元素的個(gè)數(shù) D） 矩陣中非全零行的行數(shù)等于圖中頂點(diǎn)數(shù) 36.設(shè)對(duì)有向圖G采用鄰接矩陣法存儲(chǔ)，則頂點(diǎn)i的入度等于鄰接矩陣中 。 A）第i行非0元素的和 B）第i行0元素的個(gè)數(shù) C）第i列非0元素的和 D）第i列0元素的個(gè)數(shù) 37．若有向圖中頂點(diǎn)數(shù)為100，則該圖最多可能有 _______ 條邊。 A）10000 B）9900 C）9999 D）20001 38.在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要 條邊。 A）n B) n/2 C) n+1 D) n-1 39.任何一個(gè)帶權(quán)無向連通圖的最小生成樹 。 A）可能不存在 B）只有一棵 C）一定有多棵 D）有一棵或多棵 40.在AOV網(wǎng)的拓?fù)湫蛄兄?，如果頂點(diǎn)Vi在Vj之前，則下列情況中不可能出現(xiàn)的是 。 A）〈Vi，Vj〉是圖中的邊 B）圖中有一條從Vi到Vj的路徑