2020年新編電大數(shù)據(jù)結(jié)構(gòu)本形成性考核冊(cè)作業(yè)4原題帶答案名師精品資料

1、電大 數(shù)據(jù)結(jié)構(gòu)（本）形成性考核 課程作業(yè) 答案 一、單項(xiàng)選擇題 ）。 B緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) D內(nèi)部結(jié)構(gòu)和外部機(jī)構(gòu) 1在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（C D ）。 A 動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) C線性結(jié)構(gòu)和非線性結(jié)構(gòu) 2下列說(shuō)法中，不正確的是（ A 數(shù)據(jù)元素是數(shù)據(jù)的基本單位 B數(shù)據(jù)項(xiàng)是數(shù)據(jù)中不可分割的最小可標(biāo)識(shí)單位 C數(shù)據(jù)可有若干個(gè)數(shù)據(jù)元素構(gòu)成 D數(shù)據(jù)項(xiàng)可由若干個(gè)數(shù)據(jù)元素構(gòu)成 3一個(gè)存儲(chǔ)結(jié)點(diǎn)存儲(chǔ)一個(gè)（B ）。 A 數(shù)據(jù)項(xiàng)B數(shù)據(jù)元素 C數(shù)據(jù)結(jié)構(gòu) D數(shù)據(jù)類型 4數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的（ A 存儲(chǔ)結(jié)構(gòu) B 物理結(jié)構(gòu) ）。 C邏輯結(jié)構(gòu) D物理和存儲(chǔ)結(jié)構(gòu) 5下列的敘述中，不屬于算

2、法特性的是（D ）。 B輸入性 A有窮性 C可行性 D可讀性 6算法分析的目的是（ C ）。 A找出數(shù)據(jù)結(jié)構(gòu)的合理性 C分析算法的效率以求改進(jìn) B研究算法中的輸入和輸出的關(guān)系 D分析算法的易懂性和文檔性 7數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究計(jì)算機(jī)中（ A 數(shù)值運(yùn)算B非數(shù)值運(yùn)算 C集合D非集合 B ）對(duì)象及其關(guān)系的科學(xué)。 8算法的時(shí)間復(fù)雜度與（ A所使用的計(jì)算機(jī) C與算法本身 9設(shè)有一個(gè)長(zhǎng)度為 C ）有關(guān)。 B與計(jì)算機(jī)的操作系統(tǒng) D與數(shù)據(jù)結(jié)構(gòu) n 的順序表，要在第 i 個(gè)元素之前（也就是插入元素作為新表的第 i 個(gè)元素），則移動(dòng)元素個(gè)數(shù)為（ A ）。 A n-i+1 Bn-i C n-i-1 Di 10設(shè)有一個(gè)

3、長(zhǎng)度為 A n-i+1 n 的順序表，要?jiǎng)h除第 i 個(gè)元素移動(dòng)元素的個(gè)數(shù)為（ B Bn-iC n-i-1 Di ）。 11在一個(gè)單鏈表中， 語(yǔ)句（ C ）。 p、q分別指向表中兩個(gè)相鄰的結(jié)點(diǎn)，且q 所指結(jié)點(diǎn)是 p 所指結(jié)點(diǎn)的直接后繼，現(xiàn)要?jiǎng)h除 q 所指結(jié)點(diǎn)，可用 A p=q-next 12在一個(gè)單鏈表中 Bp-next=q Cp-next=q next D q-next=NULL p 所指結(jié)點(diǎn)之后插入一個(gè) s 所指的結(jié)點(diǎn)時(shí)，可執(zhí)行（ D ）。 A p-next= s; s next= p next B p-next=s next; C p=s-next 13非空的單向循環(huán)鏈表的尾結(jié)點(diǎn)滿足（ D

4、 s-next=p-next; p-next=s; C ）（設(shè)頭指針為 head，指針 p 指向尾結(jié)點(diǎn)） 。 A. P-next= =NULL BP= =NULL C P-next= =head D P= = head 14鏈表不具有的特點(diǎn)是（A ）。 B插入刪除不需要移動(dòng)元素 D所需空間與線性表長(zhǎng)度成正比 B ）（設(shè)頭指針為 head）。 A可隨機(jī)訪問(wèn)任一元素 C不必事先估計(jì)存儲(chǔ)空間 15帶頭結(jié)點(diǎn)的鏈表為空的判斷條件是（ A head = =NULL B head-next= =NULL C head-next= =head D head!=NULL 16在一個(gè)單鏈表中， p、q分別指向表中

5、兩個(gè)相鄰的結(jié)點(diǎn)，且q所指結(jié)點(diǎn)是 p所指結(jié)點(diǎn)的直接后繼，現(xiàn)要?jiǎng)h除 q 所指結(jié)點(diǎn)，可用 語(yǔ)句（ C ）。 A p=q-next Bp-next=q Cp-next=q-next D q-next=NULL 17 在一個(gè)鏈隊(duì)中，假設(shè) f 和 r 分別為隊(duì)頭和隊(duì)尾指針， 則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算為（ C ）。 A r=f-next; B r=r-next; Cf=f-next; D f=r-next; 18 在一個(gè)鏈隊(duì)中，假設(shè) f 和 r 分別為隊(duì)頭和隊(duì)尾指針， 則插入 s 所指結(jié)點(diǎn)的運(yùn)算為（ B ）。 A f-next=s; f=s; B r-next=s;r=s; C s-next=r;r=s; D

6、s-next=f;f=s; 19. 一個(gè)順序表第一個(gè)元素的存儲(chǔ)地址是90，每個(gè)元素的長(zhǎng)度為 2，則第 6 個(gè)元素的地址是（ B ） A98 B100 C 102D 106 20有關(guān)線性表的正確說(shuō)法是（D ）。 A每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼 B線性表至少要求一個(gè)元素 C表中的元素必須按由小到大或由大到下排序 D除了一個(gè)和最后一個(gè)元素外，其余元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼 二、填空題 1在一個(gè)長(zhǎng)度為 n 的順序存儲(chǔ)結(jié)構(gòu)的線性表中，向第 i（1i n+1） 個(gè)元素之前插入新元素時(shí)，需向后移動(dòng)n-i+1 個(gè)數(shù)據(jù)元素 2從長(zhǎng)度為 n 的采用順序存儲(chǔ)結(jié)構(gòu)的線性表中刪除第 i（1i

7、 n+1） 個(gè)元素 ，需向前移動(dòng) n-i 個(gè)元素。 3數(shù)據(jù)結(jié)構(gòu)按結(jié)點(diǎn)間的關(guān)系，可分為 4 種邏輯結(jié)構(gòu)： 集合 、 線性結(jié)構(gòu) 、 樹(shù)形結(jié)構(gòu) 、 圖狀結(jié)構(gòu) 。 4數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示稱為 物理結(jié)構(gòu) 或 存儲(chǔ)結(jié)構(gòu) 。 5除了第 1 個(gè)和最后一個(gè)結(jié)點(diǎn)外，其余結(jié)點(diǎn)有且只有一個(gè)前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)為 線性結(jié)構(gòu) ，每個(gè)結(jié)點(diǎn)可有任意 多個(gè)前驅(qū)和后繼結(jié)點(diǎn)數(shù)的結(jié)構(gòu)為 非線性結(jié)構(gòu) 。 7數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在多對(duì)多的關(guān)系稱為 8數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)多的關(guān)系稱為 9數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)一的關(guān)系稱為 10要求在 n 個(gè)數(shù)據(jù)元素中找其中值最大的元素， 和 _ O（n）_ 。 6算法的

8、5 個(gè)重要特性是 有窮性 、 確定性 、 可形性 、 有零個(gè)或多個(gè)輸入 有零個(gè)或多個(gè)輸出 。 _圖狀結(jié)構(gòu) _結(jié)構(gòu)。 _樹(shù)形結(jié)構(gòu) _結(jié)構(gòu)。 _線性結(jié)構(gòu) _結(jié)構(gòu)。 n-1 設(shè)基本操作為元素間的比較。 則比較的次數(shù)和算法的時(shí)間復(fù)雜度分別為 11在一個(gè)單鏈表中 p 所指結(jié)點(diǎn)之后插入一個(gè) s 所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行 _ s-next=p-next _和 p-next=s; 的操作。 12設(shè)有一個(gè)頭指針為 head 的單向循環(huán)鏈表， p 指向鏈表中的結(jié)點(diǎn)，若 p-next= =_ head _ ，則 p 所指結(jié)點(diǎn)為尾結(jié)點(diǎn)。 13在一個(gè)單向鏈表中，要?jiǎng)h除 p 所指結(jié)點(diǎn)，已知 q 指向 p 所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。則

9、可以用操作 _ q-next=p-next _ 。 14設(shè)有一個(gè)頭指針為 head 的單向鏈表， p 指向表中某一個(gè)結(jié)點(diǎn)，且有 p-next= =NULL, 通過(guò)操作 _ p-next=head _, 就可使該單 向鏈表構(gòu)造成單向循環(huán)鏈表。 15每個(gè)結(jié)點(diǎn)只包含一個(gè)指針域的線性表叫單鏈表 。 16線性表具有 順序存儲(chǔ) 和 鏈?zhǔn)酱鎯?chǔ) 兩種存儲(chǔ)結(jié)構(gòu)。 17數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的關(guān)系存儲(chǔ)結(jié)構(gòu) 無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的。 18在雙向循環(huán)鏈表的每個(gè)結(jié)點(diǎn)中包含兩個(gè) 指針域，其中 next 指向它的 直接后繼 ，prior 指向它的 直接前驅(qū) ，而頭 結(jié)點(diǎn)的 prior 指向 尾結(jié)點(diǎn)

10、，尾結(jié)點(diǎn)的 next 指向 頭結(jié)點(diǎn) 。 19單向循環(huán)鏈表是單向鏈表的一種擴(kuò)充，當(dāng)單向鏈表帶有頭結(jié)點(diǎn)時(shí)，把單向鏈表中尾結(jié)點(diǎn)的指針域由空指針改為頭結(jié)點(diǎn)的指 針 ；當(dāng)單向鏈表不帶頭結(jié)點(diǎn)時(shí)，則把單向鏈表中尾結(jié)點(diǎn)的指針域由空指針改為指向 指向第一個(gè)結(jié)點(diǎn)的指針 。 20線性鏈表的邏輯關(guān)系時(shí)通過(guò)每個(gè)結(jié)點(diǎn)指針域中的指針來(lái)表示的。其邏輯順序和物理存儲(chǔ)順序不再一致，而是一種鏈?zhǔn)?儲(chǔ)結(jié)構(gòu)，又稱為 鏈表 。 三、問(wèn)答題 1簡(jiǎn)述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)的區(qū)別與聯(lián)系，它們?nèi)绾斡绊懰惴ǖ脑O(shè)計(jì)與實(shí)現(xiàn)？ 答：若用結(jié)點(diǎn)表示某個(gè)數(shù)據(jù)元素，則結(jié)點(diǎn)與結(jié)點(diǎn)之間的邏輯關(guān)系就稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)表示稱為數(shù)據(jù)的 存儲(chǔ)結(jié)構(gòu)。

11、可見(jiàn)，數(shù)據(jù)的邏輯結(jié)構(gòu)是反映數(shù)據(jù)之間的固有關(guān)系，而數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)表示。盡管因采用的存儲(chǔ) 結(jié)構(gòu)不同，邏輯上相鄰的結(jié)點(diǎn)，其物理地址未必相同，但可通過(guò)結(jié)點(diǎn)的內(nèi)部信息，找到其相鄰的結(jié)點(diǎn)，從而保留了邏輯結(jié)構(gòu)的特點(diǎn)。 采用的存儲(chǔ)結(jié)構(gòu)不同，對(duì)數(shù)據(jù)的操作在靈活性，算法復(fù)雜度等方面差別較大。 2解釋順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)，并比較順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)。 答： 順序結(jié)構(gòu)存儲(chǔ)時(shí)， 相鄰數(shù)據(jù)元素的存放地址也相鄰， 即邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)是統(tǒng)一的， ，要求內(nèi)存中存儲(chǔ)單元的地址必須是連續(xù)的 優(yōu)點(diǎn)：一般情況下，存儲(chǔ)密度大，存儲(chǔ)空間利用率高。 缺點(diǎn)：( 1)在做插入和刪除操作時(shí)，需移動(dòng)

12、大量元素； (2)由于難以估計(jì)，必須預(yù)先分配較大的空間，往往使存儲(chǔ)空間不能得到 充分利用；( 3)表的容量難以擴(kuò)充。 鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)時(shí)，相鄰數(shù)據(jù)元素可隨意存放，所占空間分為兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針。 優(yōu)點(diǎn)：插入和刪除元素時(shí)很方便，使用靈活。 缺點(diǎn)：存儲(chǔ)密度小，存儲(chǔ)空間利用率低。 3什么情況下用順序表比鏈表好？ 答：順序表適于做查找這樣的靜態(tài)操作，鏈表適于做插入和刪除這樣的動(dòng)態(tài)操作。如果線性表的變化長(zhǎng)度變化不大，且其主要操 作是查找，則采用順序表；如果線性表的長(zhǎng)度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。 4頭指針、頭結(jié)點(diǎn)、第一個(gè)結(jié)點(diǎn)(或稱首元結(jié)點(diǎn))的區(qū)

13、別是什么？ 頭結(jié)點(diǎn)是在鏈表的開(kāi)始結(jié)點(diǎn)之前附加的一個(gè)結(jié)點(diǎn)；第一個(gè)結(jié)點(diǎn)(或稱首元結(jié)點(diǎn))是鏈表中存儲(chǔ)第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)；頭指針是 指向鏈表中第一個(gè)結(jié)點(diǎn)(或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn))的指針。 5解釋帶頭結(jié)點(diǎn)的單鏈表和不帶頭結(jié)點(diǎn)的單鏈表的區(qū)別。 答： 帶頭結(jié)點(diǎn)的單鏈表和不帶頭結(jié)點(diǎn)的單鏈表的區(qū)別主要體現(xiàn)在其結(jié)構(gòu)上和算法操作上。 在結(jié)構(gòu)上，帶頭結(jié)點(diǎn)的單鏈表，不管鏈表是否為空，均含有一個(gè)頭結(jié)點(diǎn)，不帶頭結(jié)點(diǎn)的單鏈表不含頭結(jié)點(diǎn)。 在操作上，帶頭結(jié)點(diǎn)的單鏈表的初始化為申請(qǐng)一個(gè)頭結(jié)點(diǎn)。無(wú)論插入或刪除的位置是地第一個(gè)結(jié)點(diǎn)還是其他結(jié)點(diǎn)，算法步驟都相 同。不帶頭結(jié)點(diǎn)的單鏈表，其算法步驟要分別考慮插入或刪除的位置是第一個(gè)結(jié)點(diǎn)還

14、是其他結(jié)點(diǎn)。因?yàn)閮煞N情況的算法步驟不同。 四、程序填空題 1下列是用尾插法建立帶頭結(jié)點(diǎn)的且有n 個(gè)結(jié)點(diǎn)的單向鏈表的算法，請(qǐng)?jiān)诳崭駜?nèi)填上適當(dāng)?shù)恼Z(yǔ)句。 NODE *create1(n) /* 對(duì)線性表 (1,2,n), 建立帶頭結(jié)點(diǎn)的單向鏈表 */ NODE *head,*p,*q; int i; p=(NODE *)malloc(sizeof(NODE); head=p; q=p; p-next=NULL; for(i=1;idata=i; ( 2) p-next=NULL ( 3) q-next=p; ( 4) q=p; return(head); 2下列是用頭插法建立帶頭結(jié)點(diǎn)的且有n 個(gè)結(jié)點(diǎn)

15、的單向鏈表的算法，請(qǐng)?jiān)诳崭駜?nèi)填上適當(dāng)?shù)恼Z(yǔ)句 NODE *create2(n) /* 對(duì)線性表 (n,n-1,1),建立帶頭結(jié)點(diǎn)的線性鏈表 */ NODE *head,*p,*q; int i; p=(NODE *)malloc(sizeof(NODE); ( 1) head=p; p-next=NULL; ( 2) q=p; for(i=1;idata=i; if(i=1) ( 3) p-next=NULL; else ( 4) p-next=q-next ; ( 5) q-next=p ; return(head); 3下列是在具有頭結(jié)點(diǎn)單向列表中刪除第i 個(gè)結(jié)點(diǎn)，請(qǐng)?jiān)诳崭駜?nèi)填上適當(dāng)?shù)恼Z(yǔ)句。

16、 int delete(NODE *head,int i) NODE *p,*q; int j; q=head; j=0; while(q!=NULL) j+; if(q=NULL) return(0); ( 1) p=q-next ; ( 2) q-next=p-next ; free（p）; return（1）; 五、完成：實(shí)驗(yàn) 1線性表 根據(jù)實(shí)驗(yàn)要求（見(jiàn)教材 P201-202）認(rèn)真完成本實(shí)驗(yàn)，并提交實(shí)驗(yàn)報(bào) 數(shù)據(jù)結(jié)構(gòu)（本）課程作業(yè) 2 本部分作業(yè)覆蓋教材第 3-5 章的內(nèi)容） 一、單項(xiàng)選擇題 1若讓元素 1，2，3 依次進(jìn)棧，則出棧順序不可能為（C ） A 3，2，1B2，1，3 C3，1

17、，2 D1，3，2 2一個(gè)隊(duì)列的入隊(duì)序列是 1，2，3，4 A4，3，2，1 B1，2，3， C1，4，3，2 D3，2，4， 3向順序棧中壓入新元素時(shí)，應(yīng)當(dāng)（ A先移動(dòng)棧頂指針，再存入元素 C先后次序無(wú)關(guān)緊要D 則隊(duì)列的輸出序列是（ B ）。 4 1 A ）。 B 先存入元素，再移動(dòng)棧頂指針 同時(shí)進(jìn)行 4在一個(gè)棧頂指針為 top 的鏈棧中，將一個(gè) p 指針?biāo)傅慕Y(jié)點(diǎn)入棧，應(yīng)執(zhí)行（ A top-next=p; B p-next=top-next; top-next=p; C p-next=top; top=p; D p-next=top-next; top=top-next; 5在一個(gè)棧頂指針

18、為 top 的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用 x保存被刪結(jié)點(diǎn)的值，則執(zhí)行（ B ） A x=top;top=top-next; B x=top-data; C top=top-next; x=top-data; D x=top-data; top=top-next; A 棧 C堆?；蜿?duì)列 B隊(duì)列 D數(shù)組 6一般情況下，將遞歸算法轉(zhuǎn)換成等價(jià)的非遞歸算法應(yīng)該設(shè)置（A ） 7表達(dá)式 a*(b+c)-d 的后綴表達(dá)式是（ A abcd*+- B abc+*d- C abc*+d- D -+*abcd 8判斷一個(gè)順序隊(duì)列 sq（最多元素為 m0）為空的條件是（ A sq-rear-sq-front= m 0

19、B sq-rear-sq-front-1= = m 0 Csq-front=sq-rear D sq-front=sq-rear+1 9判斷一個(gè)循環(huán)隊(duì)列 Q（最多元素為 m0）為空的條件是（ A Q-front=Q-rear C Q-front=(Q-rear+1)% m 0 B Q-front!=Q-rear D Q-front!= (Q-rear+1)%m 0 10判斷棧 S滿（元素個(gè)數(shù)最多 n 個(gè)）的條件是（ C ） A s-top=0 B s-top!=0 C s-top=n-1 D s-top!=n-1 11一個(gè)隊(duì)列的入隊(duì)順序是 B ）。 A a,d,cb Ba,b,c,d a,b,

20、c,d，則離隊(duì)的順序是（ C d,c,b,aD c,b,d,a C ）。 12如果以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，則退棧操作時(shí)（ A 必須判斷棧是否滿B判斷棧元素類型 C必須判斷棧是否空 D對(duì)棧不作任何判斷 13在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問(wèn)題時(shí)通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫(xiě)入緩沖區(qū)中， 而打印機(jī)則從緩沖區(qū)中取出數(shù)據(jù)打印，該緩沖區(qū)應(yīng)該是一個(gè)（ B ）結(jié)構(gòu)。 A堆棧 B 隊(duì)列 C 數(shù)組 D 先性表 14一個(gè)遞歸算法必須包括（ B ）。 A遞歸部分 B終止條件和遞歸部分 C迭代部分 D終止條件和迭代部分 15從一個(gè)棧頂指針為 top 的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用變量 x 保存

21、被刪結(jié)點(diǎn)的值， 則執(zhí)行（ A ）。 A x=top-data; top=top-next; B x=top-data; C top=top-next; x=top-data; D top=top-next; x=data; 16在一個(gè)鏈隊(duì)中，假設(shè) f 和r 分別為隊(duì)頭和隊(duì)尾指針， 則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算為（ C ）。 A r=f-next; B r=r-next; C f=f-next; D f=r-next; 17在一個(gè)鏈隊(duì)中，假設(shè) f 和r 分別為隊(duì)頭和隊(duì)尾指針， 則插入 s 所指結(jié)點(diǎn)的運(yùn)算為 B ）。 A f-next=s; f=s; r-next=s;r=s; Cs-next=r;r=s

22、; s-next=f;f=s; 18. 以下陳述中正確的是 ）。 A串是一種特殊的線性表 C串中元素只能是字母 B 串的長(zhǎng)度必須大于零 D 空串就是空白串 19設(shè)有兩個(gè)串 p 和 q ，其中 q 是 p 的子串， q 在 p 中首次出現(xiàn)的位置的算法稱為（ C ）。 A求子串B 連接 求串長(zhǎng) C 匹配 D 20 串是（ D ）。 A 不少于一個(gè)字母的序列 B 任意個(gè)字母的序列 C 不少于一個(gè)字符的序列 D 有限個(gè)字符的序列 21 串的長(zhǎng)度是指（ B ）。 A 串中所含不同字母的個(gè)數(shù) B 串中所含字符的個(gè)數(shù) C 串中所含不同字符的個(gè)數(shù) D 串中所含非空格字符的個(gè)數(shù) 22. 若串 S=“Englis

23、h ”，其子串的個(gè)數(shù)是（D ）。 A 9 B 16 C 36 D 28 C ）。 鏈接的存儲(chǔ)結(jié)構(gòu) C數(shù)據(jù)元素是一個(gè)字符 數(shù)據(jù)元素可以任意 ）。 24空串與空格串（B A相同B 不相同 可能相同 D 無(wú)法確定 23串與普通的線性表相比較，它的特殊性體現(xiàn)在（ A順序的存儲(chǔ)結(jié)構(gòu) D ）。 25兩個(gè)字符串相等的條件是（ A 兩串的長(zhǎng)度相等 B兩串包含的字符相同 兩串的長(zhǎng)度相等，并且兩串包含的字符相同 兩串的長(zhǎng)度相等，并且對(duì)應(yīng)位置上的字符相同 26 在實(shí)際應(yīng)用中，要輸入多個(gè)字符串，且長(zhǎng)度無(wú)法預(yù)定。則應(yīng)該采用（ A鏈?zhǔn)?A ）存儲(chǔ)比較合適（ ）。 27. 一維數(shù)組 A64 C70 B 順序 C 堆結(jié)構(gòu) D

24、 無(wú)法確定 A 采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占用 6 個(gè)字節(jié)，第 6 個(gè)元素的存儲(chǔ)地址為 100 ，則該數(shù)組的首地址是（ C ）。 28 90 28稀疏矩陣采用壓縮存儲(chǔ)的目的主要是（D A表達(dá)變得簡(jiǎn)單 C 去掉矩陣中的多余元素 ）。 對(duì)矩陣元素的存取變得簡(jiǎn)單 減少不必要的存儲(chǔ)空間的開(kāi)銷 29一個(gè)非空廣義表的表頭（ C A 不可能是原子 ）。 只能是子表 C 只能是原子 可以是子表或原子 30常對(duì)數(shù)組進(jìn)行的兩種基本操作是 A建立與刪除B C查找和修改 C ）。 索引與、和修改 查找與索引 31. 設(shè)二維數(shù)組 A56 按行優(yōu)先順序存儲(chǔ)在內(nèi)存中，已知 A00 起始地址為 1000，每個(gè)數(shù)組元素占用 5

25、 個(gè)存儲(chǔ)單元，則元素 A44 的地址為（ ）。 A1140 B 1145 C 1120 D 1125 20 階的對(duì)稱矩陣 A，采用壓縮存儲(chǔ)的方式， 32設(shè)有一個(gè) 則矩陣中元素 a9,2 在一維數(shù)組 B 中的下標(biāo)是（ D ）。 A41 32 18 將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組 B中（數(shù)組下標(biāo)從 1 開(kāi)始）， 38 二、填空題 1棧是限定在表的一端進(jìn)行插入和刪除操作的線性表，又稱為后進(jìn)先出 。 2循環(huán)隊(duì)列隊(duì)頭指針在隊(duì)尾指針下一個(gè) 位置，隊(duì)列是“滿”狀態(tài) 3在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，當(dāng)插入一個(gè)新的隊(duì)列元素時(shí)，尾指針 增 1 ，當(dāng)刪除一個(gè)元素隊(duì)列時(shí)，頭指針 增 1 。 4循環(huán)隊(duì)列的引入，目的

26、是為了克服假上溢 。 5向順序棧插入新元素分為三步：第一步進(jìn)行棧是否滿 判斷，判斷條件是 s-top=MAXSIZE-1 ；第二步是修改 棧頂指針 ；第三步是把新元素賦給 棧頂對(duì)應(yīng)的數(shù)組元素 。同樣從順序棧刪除元素分為三步：第一步進(jìn)行 棧是否 空 判斷，判斷條件是 s-top=-1 。第二步是把 棧頂元素 ；第三步 修改棧頂指針 。 6假設(shè)以 S 和 X 分別表示入棧和出棧操作，則對(duì)輸入序列 a,b,c,d,e 一系列棧操作 SSXSXSSXXX 之后，得到的輸出序列為 bceda 。 7一個(gè)遞歸算法必須包括終止條件 和 遞歸部分 。 8判斷一個(gè)循環(huán)隊(duì)列 LU （最多元素為 m0）為空的條件是

27、LU-front=LU-rear 。 9在將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式和計(jì)算后綴表達(dá)式的算法中，都需要使用棧，對(duì)于前者，進(jìn)入棧中的元素為表達(dá)式中的 運(yùn)算符 ，而對(duì)于后者，進(jìn)入棧的元素為 操作數(shù) ，中綴表達(dá)式 （a+b）/c-（f-d/c） 所對(duì)應(yīng)的后綴表達(dá)式是ab+c/fde/-。 10向一個(gè)棧頂指針為 h 的鏈棧中插入一個(gè) s 所指結(jié)點(diǎn)時(shí)，可執(zhí)行 _ s-next=h 和 h=s;操作。 （結(jié)點(diǎn)的指針域?yàn)?next） 11從一個(gè)棧頂指針為 h 的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)， 用 x 保存被刪結(jié)點(diǎn)的值， 可執(zhí)行 x=h-data;和_ h=h-next 。（結(jié)點(diǎn)的指 針域?yàn)?next） 12在一個(gè)鏈

28、隊(duì)中， 設(shè) f 和 r 分別為隊(duì)頭和隊(duì)尾指針， 則插入 s 所指結(jié)點(diǎn)的操作為 _ r-next=s 和 r=s; （ 結(jié)點(diǎn)的指針域?yàn)?next） 13在一個(gè)鏈隊(duì)中，設(shè) f 和 r 分別為隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的操作為 _ f=f-next 。 （結(jié)點(diǎn)的指針域?yàn)?next） 14 串是一種特殊的線性表，其特殊性表現(xiàn)在組成串的數(shù)據(jù)元素都是 字符 。 15串的兩種最基本的存儲(chǔ)方式是順序存儲(chǔ)方式 和 鏈?zhǔn)酱鎯?chǔ)方式 。 16空串的長(zhǎng)度是0 ；空格串的長(zhǎng)度是 空格字符的個(gè)數(shù) 。 17需要壓縮存儲(chǔ)的矩陣可分為特殊 矩陣和 稀疏 矩陣兩種。 18設(shè)廣義表 L= （），（），則表頭是 （） ，表尾是 （

29、） ，L 的長(zhǎng)度是 2 。 19廣義表 A（a,b,c）,（d,e,f）的表尾為（ d,e,f）。 20兩個(gè)串相等的充分必要條件是 串長(zhǎng)度相等且對(duì)應(yīng)位置的字符相等_。 21設(shè)有 n階對(duì)稱矩陣 A，用數(shù)組 s 進(jìn)行壓縮存儲(chǔ)，當(dāng) i j 時(shí)，A 的數(shù)組元素 aij 相應(yīng)于數(shù)組 s的數(shù)組元素的下標(biāo)為 _ i（i-1）/2+j 。 （數(shù)組元素的下標(biāo)從 1 開(kāi)始） 22對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，矩陣中每個(gè)非零元素對(duì)應(yīng)的三元組包括該元素的_行下標(biāo) 、_列下標(biāo) _和 _非零元素值 三項(xiàng)信息。 三、問(wèn)答題 1簡(jiǎn)述棧和一般線性表的區(qū)別。 答：棧是一種先進(jìn)后出的線性表，棧的插入和刪除操作都只能在棧頂進(jìn)行，而一般的線

30、性表可以在線性表的任何位置進(jìn)行插入和 刪除操作。 2簡(jiǎn)述隊(duì)列和一般線性表的區(qū)別。 隊(duì)列是一種先進(jìn)先出的線性表，隊(duì)列的插入只能在隊(duì)尾進(jìn)行，隊(duì)列的刪除只能在隊(duì)頭進(jìn)行，而一般的線性表可以在線性表的任何 位置進(jìn)行插入和刪除操作。 3鏈棧中為何不設(shè)頭結(jié)點(diǎn)？ 答：因?yàn)殒湕Ｖ辉阪滎^插入和刪除結(jié)點(diǎn)，不可能在鏈表中間插入和刪除結(jié)點(diǎn)，算法實(shí)現(xiàn)很簡(jiǎn)單，所以一般不設(shè)置頭結(jié)點(diǎn)。 4利用一個(gè)棧，則： （1）如果輸入序列由 A，B，C 組成，試給出全部可能的輸出序列和不可能的輸出序列。 （2）如果輸入序列由 A ，B，C，D 組成，試給出全部可能的輸出序列和不可能的輸出序列 答： （1）棧的操作特點(diǎn)是后進(jìn)先出，因此輸出序列

31、有： A 入， A 出， B 入， B 出， C入 C出，輸出序列為 ABC 。 A 入， A 出， B 入， C 入， C 出， B 出， 輸出序列為 ACB 。 A 入， B 入， B 出， A 出， C 入， C 出， 輸出序列為 BAC 。 A 入， B 入， B 出， C 入， C 出， A 出， 輸出序列為 BCA 。 A 入， B 入， C 入， C 出， B 出， A 出， 輸出序列為 CBA 。 由 A，B，C組成的數(shù)據(jù)項(xiàng)，除上述五個(gè)不同的組合外，還有一個(gè)C，A，B 組合。但不可能先把 C出棧，再把 A出棧，（A不在 棧頂位置），最后把 B 出棧，所以序列 CAB 不可能由輸

32、入序列 A， B，C 通過(guò)棧得到。 （2）按照上述方法，可能的輸出序列有： ABCD ，ABDC ， ACBD ，ACDB ，ADCB ，BACD ，BADC ，BCAD ，BCDA ，BDCA ，CBAD ，CBDA ，CDBA ，DCBA 。 不可能的輸出序列有： DABC ，ADBC ，DACB ，DBAC ，BDAC ，DBCA ，DCAB，CDAB，CADB ，CABD 5用 S表示入棧操作， X 表示出棧操作，若元素入棧順序?yàn)?234，為了得到 1342出棧順序，相應(yīng)的 S和X 操作串是什么？ 答： 應(yīng)是 SXSSXSXX 。各操作結(jié)果如下 S 1 入棧 X 1 出棧 輸出序列：

33、1 S 2 入棧 S 3 入棧 X 3 出棧 輸出序列： 13 S 4 入棧 X 4 出棧 輸出序列： 134 X 2 出棧 輸出序列： 1342 6有 5 個(gè)元素，其入棧次序?yàn)椋?A、B、 C、D、 E，在各種可能的出棧次序中，以元素C、D 最先的次序有哪幾個(gè)？ 答：從題中可知，要使 （1）B 出棧， （2）B 出棧， （3）E 入棧， A 出棧， E 入棧， E出棧， C 第一個(gè)且 D 第二個(gè)出棧，應(yīng)是 A 入棧， B 入棧， C 入棧， E入棧， E 出棧， B 出棧， C 出棧， D 入棧。之后可以有以下幾種情況： E 出棧，輸出序列為： A 出棧，輸出序列為 A 出棧，輸出序列為 C

34、DBAE 。 CDBEA 。 CDEBA 所以可能的次序有： CDBAE ，CDBEA ，CDEBA 7寫(xiě)出以下運(yùn)算式的后綴算術(shù)運(yùn)算式 3x2+x-1/x+5 （A+B）*C-D/（E+F）+G 答；對(duì)應(yīng)的后綴算術(shù)運(yùn)算式 3x2*x+1x/-5+ AB+C*DEF+/-G+ 8 簡(jiǎn)述廣義表和線性表的區(qū)別和聯(lián)系。 答：廣義表是線性表的的推廣，它也是n（n0）個(gè)元素 a1 ,a2ai an的有限序列，其中 ai 或者是原子或者是一個(gè)廣義表。所以，廣義 表是一種遞歸數(shù)據(jù)結(jié)構(gòu)，而線性表沒(méi)有這種特性，線性表可以看成廣義表的特殊情況，當(dāng)ai 都是原子時(shí)，廣義表退化成線性表。 四、程序填空題 1在下面空格處

35、填寫(xiě)適當(dāng)?shù)恼Z(yǔ)句，以使下面的鏈?zhǔn)疥?duì)列取出元素的算法完整。 int write(LinkQueue *q) QueueNode *p; if (q-front=q-rear) /*隊(duì)空 */ printf( “underflow ”); exit(0); while (q-front-next != NULL) p=q-front-next; (1) q-front-next=p-next; printf( “%4d”,p -data); (2) free(p); ( 3) q-rear=q-front; /* 隊(duì)空時(shí)，頭尾指針指向頭結(jié)點(diǎn) */ 五、綜合題 1設(shè)棧 S和隊(duì)列 Q的初始狀態(tài)為空，元素

36、 e1,e2,e3,e4,e5和e6依次通過(guò) S，一個(gè)元素出棧后即進(jìn)隊(duì)列 Q，若 6個(gè)元素出隊(duì)的序 列是 e2,e4,e3,e6,e5,e1，則棧 S 的容量至少應(yīng)該是多少？ 答：出隊(duì)序列是 e2,e4,e3,e6,e5,e1 的過(guò)程： e1 入棧（棧底到棧頂元素是 e1 ） e2 入棧（棧底到棧頂元素是 e1,e2 ） e2 出棧（棧底到棧頂元素是 e1 ） e3 入棧（棧底到棧頂元素是 e1,e3 ） e4 入棧（棧底到棧頂元素是 e1,e3,e4 ） e4 出棧（棧底到棧頂元素是 e1,e3 ） e3 出棧（棧底到棧頂元素是 e1 ） e5 入棧（棧底到棧頂元素是 e1,e5 ） e6

37、入棧（棧底到棧頂元素是 e1,e5,e6 ） e6 出棧（棧底到棧頂元素是 e1,e5 ） e5 出棧（棧底到棧頂元素是 e1 ） e1 出棧（棧底到棧頂元素是空） 棧中最多時(shí)有 3 個(gè)元素，所以棧 S 的容量至少是 3。 2 假設(shè)用循環(huán)單鏈表實(shí)現(xiàn)循環(huán)隊(duì)列，該隊(duì)列只使用一個(gè)尾指針 rear ，其相應(yīng)的存儲(chǔ)結(jié)構(gòu)和基本算法如下； （ 1）初始化隊(duì)列 initqueue（Q）: 建立一個(gè)新的空隊(duì)列 Q。 （ 2）入隊(duì)列 enqueue（Q,x）: 將元素 x 插入到隊(duì)列 Q中。 （ 3）出隊(duì)列 delqueue（Q）: 從隊(duì)列 Q中退出一個(gè)元素。 （ 4）取隊(duì)首元素 gethead（Q）: 返回當(dāng)前

38、隊(duì)首元素。 （ 5）判斷隊(duì)列是否為空： emptyqueue（Q） 。 （ 6）顯示隊(duì)列中元素： dispqueue（Q） 。 算法設(shè)計(jì)如下： /* 只有一個(gè)指針 rear 的鏈?zhǔn)疥?duì)的基本操作 */ #include typedef char elemtype; struct node /* 定義鏈隊(duì)列結(jié)點(diǎn) */ elemtype data; struct node *next; ; typedef struct queue /*定義鏈隊(duì)列數(shù)據(jù)類型 */ struct node *rear; LinkQueue; void initqueue（LinkQueue *Q）/* 初始化隊(duì)列 */

39、Q=（struct queue *）malloc（sizeof（struct queue）; Q-rear=NULL; void enqueue（LinkQueue *Q,elemtype x） /* 入隊(duì)算法 */ struct node *s,*p; s=（struct node *）malloc（sizeof（struct node）; 原為空隊(duì)時(shí) */ Q-rear=s; s-next=s; else /* s-data=x; if (Q-rear=NULL) /* 原隊(duì)不為空時(shí) */ p=Q-rear-next; /*p Q-rear-next=s; /* 指向第一個(gè)結(jié)點(diǎn) */ 將

40、s 鏈接到隊(duì)尾 */ Q-rear=s; /*Q-rear 指向隊(duì)尾 */ s-next=p; void delqueue(LinkQueue *Q) /* struct node *t; if (Q-rear=NULL) 出隊(duì)算法 */ printf( 隊(duì)列為空 !n); return(0); else if (Q-rear-next=Q-rear) /* 只有一個(gè)結(jié)點(diǎn)時(shí) */ t=Q-rear; Q-rear=NULL; else /* 有多個(gè)結(jié)點(diǎn)時(shí) */ t=Q-rear-next; Q-rear-next=t-next; /*t /* 指向第一個(gè)結(jié)點(diǎn) */ 引成循環(huán)鏈 */ free(

41、t); elemtype gethead(LinkQueue *Q) if (Q-rear=NULL) printf( 隊(duì)列為空 !n); /* 取隊(duì)首元素算法 */ else return(Q-rear-next-data); int emptyqueue(LinkQueue *Q) /* if (Q-rear=NULL) return(1); /* else return(0); /*不為空 , 則返回 void dispqueue(LinkQueue *Q) 判斷隊(duì)列是否為空算法 */ 為空 , 則返回 true*/ flase*/ /* 顯示隊(duì)列中元素算法 */ struct node

42、 *p=Q-rear-next; printf( 隊(duì)列元素 :); while (p!=Q-rear) printf(%c ,p-data); p=p-next; printf(%cn,p-data); 六、完成：實(shí)驗(yàn) 2棧、隊(duì)列、遞歸程序設(shè)計(jì) 根據(jù)實(shí)驗(yàn)要求（見(jiàn)教材 P203）認(rèn)真完成本實(shí)驗(yàn)，并提交實(shí)驗(yàn)報(bào)告。 數(shù)據(jù)結(jié)構(gòu)（本）課程作業(yè) 作業(yè) 3 （本部分作業(yè)覆蓋教材第 6-7 章的內(nèi)容） 一、單項(xiàng)選擇題 1. 假定一棵二叉樹(shù)中，雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為 30，則葉子結(jié)點(diǎn)數(shù)為（ B ） A15 B 16 C 17 D 47 2二叉樹(shù)第 k 層上最多有（ B ）個(gè)結(jié)點(diǎn)。 A 2k B 2k

43、-1 C 2k-1 D 2k-1 3二叉樹(shù)的深度為 k,則二叉樹(shù)最多有（ D ）個(gè)結(jié)點(diǎn)。 A2k B 2k-1 C2k-1 D 2k-1 4. 設(shè)某一二叉樹(shù)先序遍歷為 abdec，中序遍歷為 dbeac，則該二叉樹(shù)后序遍歷的順序是（ C ）。 Aabdec B debac C debca D abedc 5將含有 150 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根這一層開(kāi)始，每一層從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為 1 ，則編號(hào)為 69 的 結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為（ B ）。 A 33 B 34C35D 36 6如果將給定的一組數(shù)據(jù)作為葉子數(shù)值，所構(gòu)造出的二叉樹(shù)的帶權(quán)路徑長(zhǎng)度最小，則該樹(shù)稱為（A ）。 A

44、哈夫曼樹(shù)B 平衡二叉樹(shù) C 二叉樹(shù) D 完全二叉樹(shù) 7下列有關(guān)二叉樹(shù)的說(shuō)法正確的是（A ）。 A二叉樹(shù)中度為 0 的結(jié)點(diǎn)的個(gè)數(shù)等于度為 2 的結(jié)點(diǎn)的個(gè)數(shù)加 1 B二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)必大于 0 C完全二叉樹(shù)中，任何一個(gè)結(jié)點(diǎn)的度，或者為0 或者為 2 D二叉樹(shù)的度是 2 8在一棵度為 3 的樹(shù)中，度為 3 的結(jié)點(diǎn)個(gè)數(shù)為 2，度為 2 的結(jié)點(diǎn)個(gè)數(shù)為 1，則度為 0 的結(jié)點(diǎn)個(gè)數(shù)為（ C ）。 A4B 5 C 6 D 7 9在一棵度具有 5 層的滿二叉樹(shù)中結(jié)點(diǎn)總數(shù)為（A ）。 A31B 32C 33D 16 10. 利用 n 個(gè)值作為葉結(jié)點(diǎn)的權(quán)生成的哈夫曼樹(shù)中共包含有（ D ） 個(gè)結(jié)點(diǎn)。 A. nB. n

45、+1C. 2*nD. 2*n-1 11. 利用 3、6、8、12 這四個(gè)值作為葉子結(jié)點(diǎn)的權(quán)，生成一棵哈夫曼樹(shù)，該樹(shù)中所有葉子的最長(zhǎng)帶權(quán)路徑長(zhǎng)度為（ A ） 。 A. 18B. 16C. 12D. 30 12在一棵樹(shù)中，（ C ）沒(méi)有前驅(qū)結(jié)點(diǎn)。 A分支結(jié)點(diǎn)B 葉結(jié)點(diǎn) C 樹(shù)根結(jié)點(diǎn) D 空結(jié)點(diǎn) 13在一棵二叉樹(shù)中，若編號(hào)為 i 的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號(hào)為（ C ） A 2iB 14設(shè)一棵哈夫曼樹(shù)共有 C 2i+2 ）個(gè)非葉結(jié)點(diǎn) 2i-1 D 2i+1 n 個(gè)葉結(jié)點(diǎn)，則該樹(shù)有（ B n-1 C n+1 D 2n 15設(shè)一棵有 n 個(gè)葉結(jié)點(diǎn)的二叉樹(shù)，除葉結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)度數(shù)都為 2，則該樹(shù)共

46、有（ B ）個(gè)結(jié)點(diǎn) A 2nB 2n-1 C2n+1D 2n+2 16在一個(gè)圖 G中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)之和的（C ）倍。 A 1/2B1C2D 4 17在一個(gè)有像圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的（B ）倍 A 鄰接矩陣表示法 B 鄰接表表示法 C逆鄰接表表示法D 鄰接表和逆鄰接表 18在圖的存儲(chǔ)結(jié)構(gòu)表示中，表示形式唯一的是（ A n B n 1 C n 1 D n/2 19 一個(gè)具有 n 個(gè)頂點(diǎn)的無(wú)向完全圖包含（ A ）條邊。 A n（n 1）Bn（ n 1） C n（n 1）/2 D n（n 1）/2 20 對(duì)于具有 n 個(gè)頂點(diǎn)的圖，若采用鄰接矩陣表示， 則該矩

47、陣的大小為（ B ）。 A n B n2C n 2 1 D （ n 1） 2 21對(duì)于一個(gè)具有 n 個(gè)頂點(diǎn)和 e 條邊的無(wú)向圖，若采用鄰接表表示，則所有頂點(diǎn)鄰接表中的結(jié)點(diǎn)總數(shù)為（ D ） A nB e C 2nD 2e 22在有向圖的鄰接表中，每個(gè)頂點(diǎn)鄰接表鏈接著該頂點(diǎn)所有（B ）鄰接點(diǎn)。 A 入邊 B 出邊 C入邊和出邊 D 不是入邊也不是出邊 23鄰接表是圖的一種（ B ）。 A 順序存儲(chǔ)結(jié)構(gòu) B 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) C索引存儲(chǔ)結(jié)構(gòu) D 散列存儲(chǔ)結(jié)構(gòu) 24 如果從無(wú)向圖的任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問(wèn)所有頂點(diǎn)，則該圖一定是（ B ） A 完全圖 B 連通圖 C 有回路 D 一棵樹(shù) 25

48、下列有關(guān)圖遍歷的說(shuō)法不正確的是（C ）。 A連通圖的深度優(yōu)先搜索是一個(gè)遞歸過(guò)程 B圖的廣度優(yōu)先搜索中鄰接點(diǎn)的尋找具有“先進(jìn)先出”的特征 C非連通圖不能用深度優(yōu)先搜索法 D圖的遍歷要求每一頂點(diǎn)僅被訪問(wèn)一次 26 無(wú)向圖的鄰接矩陣是一個(gè)（ A ）。 A 對(duì)稱矩陣 B 零矩陣 C 上三角矩陣 D 對(duì)角矩陣 27圖的深度優(yōu)先遍歷算法類似于二叉樹(shù)的（A ）遍歷。 A先序B 中序 C 后序 D 層次 28已知下圖所示的一個(gè)圖，若從頂點(diǎn) V1 出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（C ） 3度大于 0 的結(jié)點(diǎn)稱作分支結(jié)點(diǎn) 或 非終端結(jié)點(diǎn) 。 4度等于 0 的結(jié)點(diǎn)稱作葉子結(jié)點(diǎn) 或 終端結(jié)

49、點(diǎn) 。 5在一棵樹(shù)中，每個(gè)結(jié)點(diǎn)的 子樹(shù)的根 或者說(shuō)每個(gè)結(jié)點(diǎn)的 后繼結(jié)點(diǎn) 稱為該結(jié)點(diǎn)的 孩子結(jié)點(diǎn) ，簡(jiǎn)稱為孩子。 6從根結(jié)點(diǎn)到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)稱為該結(jié)點(diǎn)的祖先 。 7樹(shù)的深度或高度是指 樹(shù)中結(jié)點(diǎn)的最大層數(shù) 。 8具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度是log2 n 1 。 9先序遍歷二叉樹(shù)的的操作定義為；若二叉樹(shù)為空，則為空操作，否則進(jìn)行如下操作，訪問(wèn)二叉樹(shù)的根結(jié)點(diǎn) ；先序遍歷 二叉樹(shù)的 左子樹(shù) ，先序遍歷二叉樹(shù)的 右子樹(shù) 。 10 中序遍歷二叉樹(shù)的的操作定義為；若二叉樹(shù)為空，則為空操作，否則進(jìn)行如下操作，中序遍歷二叉樹(shù)的左子樹(shù) ；訪 問(wèn)而叉樹(shù)的 根結(jié)點(diǎn) ，中序遍歷二叉樹(shù)的 右子樹(shù) 。 1

50、1后序遍歷二叉樹(shù)的的操作定義為；若二叉樹(shù)為空，則為空操作，否則進(jìn)行如下操作，后序遍歷二叉樹(shù)的左子樹(shù) ；后序 遍歷二叉樹(shù)的 右子樹(shù) ，訪問(wèn)而叉樹(shù)的 根結(jié)點(diǎn) 。 12將樹(shù)中結(jié)點(diǎn)賦上一個(gè)有著某種意義的實(shí)數(shù)，稱此實(shí)數(shù)為該結(jié)點(diǎn)的權(quán) 。 13樹(shù)的帶權(quán)路徑長(zhǎng)度為樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和 。 14哈夫曼樹(shù)又稱為最優(yōu)二叉樹(shù) ，它是 n 個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有二叉樹(shù)中帶權(quán)路徑長(zhǎng)度 WPL 最小的二叉樹(shù) 。 15若以 4，5，6，7，8 作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造哈夫曼樹(shù)，則其帶權(quán)路徑長(zhǎng)度是69 16具有 m 個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)共有2m-1 結(jié)點(diǎn)。 17在圖中，任何兩個(gè)數(shù)據(jù)元素之間都可能存在關(guān)系，因此圖的

51、數(shù)據(jù)元素之間是一種 多對(duì)多 的關(guān)系。 18圖的遍歷是從圖的某一頂點(diǎn)出發(fā)，按照一定的搜索方法對(duì)圖中所有頂點(diǎn) 各做 一次 訪問(wèn)的過(guò)程。 19圖的深度優(yōu)先搜索遍歷類似于樹(shù)的先序 遍歷。 20圖的廣度優(yōu)先搜索類似于樹(shù)的按層次 遍歷。 21具有 n 個(gè)頂點(diǎn)的有向圖的鄰接矩陣，其元素個(gè)數(shù)為n2 。 22圖常用的兩種存儲(chǔ)結(jié)構(gòu)是鄰接矩陣 和 鄰接表 。 23在有 n 個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)的度最大可達(dá)2(n-1) 。 24在一個(gè)帶權(quán)圖中，兩頂點(diǎn)之間的最段路徑最多經(jīng)過(guò)n-1 條邊。 25為了實(shí)現(xiàn)圖的深度優(yōu)先搜索遍歷，其非遞歸的算法中需要使用的一個(gè)輔助數(shù)據(jù)結(jié)構(gòu)為棧 三、綜合題 (1) 先序?yàn)椤案笥摇?，先序

52、序列為： fdbacegihl (2) 中序?yàn)椤白蟾摇?，中序序列為： abcdefghij (3) 后序?yàn)椤白笥腋?，后序序列為： acbedhjigf 2已知某二叉樹(shù)的先序遍歷結(jié)果是： A，B，D，G，C，E，H，L，I，K，M，F(xiàn) 和 J，它的中序遍歷結(jié)果是： G，D，B，A，L， H，E，K，I，M，C，F(xiàn)和 J，請(qǐng)畫(huà)出這棵二叉樹(shù)，并寫(xiě)出該二叉樹(shù)后續(xù)遍歷的結(jié)果。 1) 二叉樹(shù)圖形表示如下： A BC DEF GHIJ L K M （ 2）該二叉樹(shù)后序遍歷的結(jié)果是： G、D、B、L、H、K、M、I、E、J、F、C和 A 3已知一棵完全二叉樹(shù)共有 892 個(gè)結(jié)點(diǎn)，求 樹(shù)的高度 葉子結(jié)點(diǎn)

53、數(shù) 單支結(jié)點(diǎn)數(shù) 最后一個(gè)非終端結(jié)點(diǎn)的序號(hào) 答 已知深度為 k 的二叉樹(shù)最多有 2k-1 個(gè)結(jié)點(diǎn) （K 1）， 29-1892data=X) return 1; /*根結(jié)點(diǎn)的層號(hào)為 1*/ /* 向子樹(shù)中查找 X 結(jié)點(diǎn) */ else int c1=NodeLevel(BT-left,X); if(c1=1) _(1) return c1+1; int c2=(2) NodeLevel(BT-right,X) _; if _(3)_ (c2=1) return c2+1; / 若樹(shù)中不存在 X 結(jié)點(diǎn)則返回 0 else return 0; 2. 下面函數(shù)的功能是按照?qǐng)D的深度優(yōu)先搜索遍歷的方法，

54、輸出得到該圖的生成樹(shù)中的各條邊， 請(qǐng)?jiān)趧澯袡M線的地方填寫(xiě)合適內(nèi)容。 void dfstree(adjmatrix GA, int i, int n) int j; visitedi=1; (1) for(j=0; jdata=p-data; t-lchild=CopyTree(p-lchild); t-rchild=CopyTree(p-rchild); return(t); else return(NULL); /*CopyTree*/ 2 根據(jù)下面函數(shù)聲明編寫(xiě)出求一棵二叉樹(shù)中葉子結(jié)點(diǎn)總數(shù)的算法，該總數(shù)值由函數(shù)返回。假定參數(shù)BT 初始指向二叉樹(shù)的根結(jié)點(diǎn) int BTreeLeafCount(

55、struct BTreeNode* BT); int BTreeLeafCount(struct BTreeNode* BT) if(BT=NULL) return 0; else if(BT-left=NULL else return BTreeLeafCount(BT-left)+BTreeLeafCount(BT-right); 六、完成：實(shí)驗(yàn) 3棧、隊(duì)列、遞歸程序設(shè)計(jì) 實(shí)驗(yàn) 4圖的存儲(chǔ)方式和應(yīng)用 根據(jù)實(shí)驗(yàn)要求(見(jiàn)教材 P203)認(rèn)真完成本實(shí)驗(yàn)，并提交實(shí)驗(yàn)報(bào)告。 本部分作業(yè)覆蓋教材第 8-9 章的內(nèi)容） 數(shù)據(jù)結(jié)構(gòu)（本）課程作業(yè)（ 4 ） 一、單項(xiàng)選擇題 1. 順序查找方法適合于存儲(chǔ)結(jié)構(gòu)為

56、（ D ）的線性表。 A散列存儲(chǔ)B 索引存儲(chǔ) C散列存儲(chǔ)或索引存儲(chǔ)D 順序存儲(chǔ)或鏈接存儲(chǔ) 2對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須（C ）。 A 以順序存儲(chǔ)方式 B以鏈接存儲(chǔ)方式 C 以順序存儲(chǔ)方式 ，且數(shù)據(jù)元素有序 D以鏈接存儲(chǔ)方式，且數(shù)據(jù)元素有序 3. 對(duì)于一個(gè)線性表， 若要求既能進(jìn)行較快地插入和刪除， 又要求存儲(chǔ)結(jié)構(gòu)能夠反映數(shù)據(jù)元素之間的邏輯關(guān)系， 則應(yīng)該 （ B ） A以順序存儲(chǔ)方式B 以鏈接存儲(chǔ)方式 C以索引存儲(chǔ)方式D 以散列存儲(chǔ)方式 C ）。 4采用順序查找方法查找長(zhǎng)度為 n 的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為（ C (n+1)/2 D (n-1)/2 An B n/2 5哈希函

57、數(shù)有一個(gè)共同的性質(zhì)，即函數(shù)值應(yīng)當(dāng)以（D ）取其值域的每個(gè)值。 A最大概率B 最小概率 C 平均概率 D 同等概率 6有一個(gè)長(zhǎng)度為 10 的有序表，按折半查找對(duì)該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（ A ） A29/10B31/10 C 26/10 D 29/9 7已知一個(gè)有序表為 11,22,33,44,55,66,77,88,99 ，則順序查找元素 55 需要比較（ C ）次。 A 3B 4C 5 D 6 8順序查找法與二分查找法對(duì)存儲(chǔ)結(jié)構(gòu)的要求是（D ） A順序查找與二分查找均只是適用于順序表 B順序查找與二分查找均既適用于順序表，也適用于鏈表 C順序查找只是適用于順序表

58、D二分查找適用于順序表 9有數(shù)據(jù) 53,30,37,12,45,24,96 B )。 A 45,24,53,12,37,96,30B ，從空二叉樹(shù)開(kāi)始逐個(gè)插入數(shù)據(jù)來(lái)形成二叉排序樹(shù)，若希望高度最小，應(yīng)該選擇的序列是 37,24,12,30,53,45,96 C 12,24,30,37,45,53,96D 30,24,12,37,45,96,53 10對(duì)有 18 個(gè)元素的有序表作二分（折半）查找，則查找 A1、 2、3B9、5、 2、3 C9、 5、3D9、4、 2、3 A3 的比較序列的下標(biāo)可能為（ D ） 11. 對(duì)于順序存儲(chǔ)的有序表 5，12，20，26，37，42，46，50，64，若采用

59、折半查找，則查找元素 26 的比較次數(shù)是 A.3 B. 3 C. 4 D.5 12. 在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄初始排列秩序無(wú)關(guān)的是（ C ）。 A. 冒泡排序 B. 希爾排序 C. 直接選擇排序 D. 直接插入排序 13. 從未排序序列中依次取出元素與已經(jīng)排好序的序列中的元素作比較。將其放入已排序序列的正確的位置上，此方法稱為 （ A ） A. 插入排序 B. 選擇排序 C. 交換排序 D. 歸并排序 14. 從未排序序列中挑選元素， 并將其放入已排序序列的一端， 此方法稱為（ C ） A. 插入排序 B. 交換排序 C. 選擇排序 D. 歸并排序 15. 依次將每?jī)蓚€(gè)相鄰的

60、有序表合并成一個(gè)有序表的排序方法稱為（ D ）。 A. 插入排序B.交換排序C.選擇排序D.歸并排序 16. 當(dāng)兩個(gè)元素出現(xiàn)逆序的時(shí)候就交換位置，這種排序方法稱為（ B ）。 A. 插入排序B.交換排序C.選擇排序D.歸并排序 17. 每次把待排序的區(qū)間劃分為左、右兩個(gè)子區(qū)間，其中左區(qū)間中記錄的關(guān)鍵字均小于等于基準(zhǔn)記錄的關(guān)鍵字，右區(qū)間中記錄的關(guān) 鍵字均大于等于基準(zhǔn)記錄的關(guān)鍵字，這種排序稱為（ B ）。 A. 插入排序 B. 快速排序 C. 堆排序 D. 歸并排序 18. 在正常情況下，直接插入排序的時(shí)間復(fù)雜度為（ D ）。 A. O(log2n) B. O(n)C. O(n log 2n) D