電大數(shù)據(jù)結(jié)構(gòu)本形成性考核冊(cè)作業(yè)1-4原題帶答案.doc

數(shù)據(jù)結(jié)構(gòu)（本）課程作業(yè)作業(yè)1（本部分作業(yè)覆蓋教材第1-2章的內(nèi)容）14一、單項(xiàng)選擇題1在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（C ）。A動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) C線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu) D內(nèi)部結(jié)構(gòu)和外部機(jī)構(gòu)2下列說(shuō)法中，不正確的是（ D ）。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ù)類(lèi)型4數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的（ C ）。A存儲(chǔ)結(jié)構(gòu) B物理結(jié)構(gòu)C邏輯結(jié)構(gòu) D物理和存儲(chǔ)結(jié)構(gòu)5下列的敘述中，不屬于算法特性的是（ D ）。A有窮性 B輸入性 C可行性 D可讀性6算法分析的目的是（ C ）。 A找出數(shù)據(jù)結(jié)構(gòu)的合理性 B研究算法中的輸入和輸出的關(guān)系 C分析算法的效率以求改進(jìn) D分析算法的易懂性和文檔性7數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究計(jì)算機(jī)中（B ）對(duì)象及其關(guān)系的科學(xué)。A數(shù)值運(yùn)算 B非數(shù)值運(yùn)算C集合 D非集合 8算法的時(shí)間復(fù)雜度與（ C ）有關(guān)。 A所使用的計(jì)算機(jī) B與計(jì)算機(jī)的操作系統(tǒng) C與算法本身 D與數(shù)據(jù)結(jié)構(gòu)9設(shè)有一個(gè)長(zhǎng)度為n的順序表，要在第i個(gè)元素之前（也就是插入元素作為新表的第i個(gè)元素），則移動(dòng)元素個(gè)數(shù)為（ A ）。 An-i+1 Bn-i Cn-i-1 Di10設(shè)有一個(gè)長(zhǎng)度為n的順序表，要?jiǎng)h除第i個(gè)元素移動(dòng)元素的個(gè)數(shù)為（ B ）。 An-i+1 Bn-i Cn-i-1 Di11在一個(gè)單鏈表中，p、q分別指向表中兩個(gè)相鄰的結(jié)點(diǎn)，且q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接后繼，現(xiàn)要?jiǎng)h除q所指結(jié)點(diǎn)，可用語(yǔ)句（ C ）。 Ap=q-next Bp-next=q Cp-next=qnext Dq-next=NULL12在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指的結(jié)點(diǎn)時(shí)，可執(zhí)行（ D ）。 Ap-next= s; snext= pnext Bp-next=snext; Cp=s-next Ds-next=p-next; p-next=s;13非空的單向循環(huán)鏈表的尾結(jié)點(diǎn)滿(mǎn)足（C ）（設(shè)頭指針為head，指針p指向尾結(jié)點(diǎn)）。 A.P-next= =NULL BP= =NULL CP-next= =head DP= = head 14鏈表不具有的特點(diǎn)是（ A ）。 A可隨機(jī)訪(fǎng)問(wèn)任一元素 B插入刪除不需要移動(dòng)元素 C不必事先估計(jì)存儲(chǔ)空間 D所需空間與線(xiàn)性表長(zhǎng)度成正比15帶頭結(jié)點(diǎn)的鏈表為空的判斷條件是（B ）（設(shè)頭指針為head）。Ahead = =NULLBhead-next= =NULL Chead-next= =headDhead!=NULL16在一個(gè)單鏈表中，p、q分別指向表中兩個(gè)相鄰的結(jié)點(diǎn)，且q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接后繼，現(xiàn)要?jiǎng)h除q所指結(jié)點(diǎn)，可用語(yǔ)句（C ）。Ap=q-nextBp-next=qCp-next=q-nextDq-next=NULL17在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算為（C ）。 Ar=f-next; Br=r-next; Cf=f-next; Df=r-next;18在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的運(yùn)算為（ B ）。 Af-next=s; f=s; Br-next=s;r=s; Cs-next=r;r=s; Ds-next=f;f=s;19.一個(gè)順序表第一個(gè)元素的存儲(chǔ)地址是90，每個(gè)元素的長(zhǎng)度為2，則第6個(gè)元素的地址是（B ）。A98 B100 C102 D10620有關(guān)線(xiàn)性表的正確說(shuō)法是（ D ）。A每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼 B線(xiàn)性表至少要求一個(gè)元素C表中的元素必須按由小到大或由大到下排序 D除了一個(gè)和最后一個(gè)元素外，其余元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼二、填空題1在一個(gè)長(zhǎng)度為n的順序存儲(chǔ)結(jié)構(gòu)的線(xiàn)性表中，向第i(1in+1)個(gè)元素之前插入新元素時(shí)，需向后移動(dòng) n-i+1 個(gè)數(shù)據(jù)元素。2從長(zhǎng)度為n的采用順序存儲(chǔ)結(jié)構(gòu)的線(xiàn)性表中刪除第i(1in+1)個(gè)元素 ，需向前移動(dòng) n-i 個(gè)元素。3數(shù)據(jù)結(jié)構(gòu)按結(jié)點(diǎn)間的關(guān)系，可分為4種邏輯結(jié)構(gòu)： 集合 、 線(xiàn)性結(jié)構(gòu) 、 樹(shù)形結(jié)構(gòu) 、 圖狀結(jié)構(gòu) 。4數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示稱(chēng)為 物理結(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)為 線(xiàn)性結(jié)構(gòu) ，每個(gè)結(jié)點(diǎn)可有任意多個(gè)前驅(qū)和后繼結(jié)點(diǎn)數(shù)的結(jié)構(gòu)為 非線(xiàn)性結(jié)構(gòu) 。6算法的5個(gè)重要特性是 有窮性 、 確定性 、 可形性 、 有零個(gè)或多個(gè)輸入 、 有零個(gè)或多個(gè)輸出 。7數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在多對(duì)多的關(guān)系稱(chēng)為_(kāi)圖狀結(jié)構(gòu)_結(jié)構(gòu)。8數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)多的關(guān)系稱(chēng)為_(kāi)樹(shù)形結(jié)構(gòu)_結(jié)構(gòu)。9數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)一的關(guān)系稱(chēng)為_(kāi)線(xiàn)性結(jié)構(gòu)_結(jié)構(gòu)。10要求在n個(gè)數(shù)據(jù)元素中找其中值最大的元素，設(shè)基本操作為元素間的比較。則比較的次數(shù)和算法的時(shí)間復(fù)雜度分別為_(kāi) n-1_和 _ O(n)_ 。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)。則可以用操作_ 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è)指針域的線(xiàn)性表叫 單鏈表 。16線(xiàn)性表具有 順序存儲(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) ，尾結(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線(xiàn)性鏈表的邏輯關(guān)系時(shí)通過(guò)每個(gè)結(jié)點(diǎn)指針域中的指針來(lái)表示的。其邏輯順序和物理存儲(chǔ)順序不再一致，而是一種 鏈?zhǔn)?存儲(chǔ)結(jié)構(gòu)，又稱(chēng)為 鏈表 。 三、問(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)系就稱(chēng)為數(shù)據(jù)的邏輯結(jié)構(gòu)。數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)表示稱(chēng)為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)?？梢?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)大量元素；（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)操作。如果線(xiàn)性表的變化長(zhǎng)度變化不大，且其主要操作是查找，則采用順序表；如果線(xiàn)性表的長(zhǎng)度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。4頭指針、頭結(jié)點(diǎn)、第一個(gè)結(jié)點(diǎn)（或稱(chēng)首元結(jié)點(diǎn)）的區(qū)別是什么？頭結(jié)點(diǎn)是在鏈表的開(kāi)始結(jié)點(diǎn)之前附加的一個(gè)結(jié)點(diǎn)；第一個(gè)結(jié)點(diǎn)（或稱(chēng)首元結(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)還是其他結(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ì)線(xiàn)性表(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)的單向鏈表的算法，請(qǐng)?jiān)诳崭駜?nèi)填上適當(dāng)?shù)恼Z(yǔ)句。NODE *create2(n)/*對(duì)線(xiàn)性表(n,n-1,.,1),建立帶頭結(jié)點(diǎn)的線(xià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ǔ)句。int delete(NODE *head,int i)NODE *p,*q; int j; q=head;j=0; while(q!=NULL)&(jnext;j+; if(q=NULL) return(0);（1） p=q-next ; （2） q-next=p-next ; free(p); return(1);五、完成：實(shí)驗(yàn)1線(xiàn)性表根據(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 ）。A3，2，1 B2，1，3 C3，1，2 D1，3，22一個(gè)隊(duì)列的入隊(duì)序列是1，2，3，4。則隊(duì)列的輸出序列是（ B ）。A4，3，2，1 B1，2，3，4 C1，4，3，2 D3，2，4，13向順序棧中壓入新元素時(shí)，應(yīng)當(dāng)（ A ）。A先移動(dòng)棧頂指針，再存入元素 B先存入元素，再移動(dòng)棧頂指針 C先后次序無(wú)關(guān)緊要 D同時(shí)進(jìn)行4在一個(gè)棧頂指針為top的鏈棧中，將一個(gè)p指針?biāo)傅慕Y(jié)點(diǎn)入棧，應(yīng)執(zhí)行（ C ）。Atop-next=p; Bp-next=top-next; top-next=p;Cp-next=top; top=p; Dp-next=top-next; top=top-next;5在一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用 x保存被刪結(jié)點(diǎn)的值，則執(zhí)行（ B ）。Ax=top;top=top-next; Bx=top-data;Ctop=top-next; x=top-data; Dx=top-data; top=top-next;6一般情況下，將遞歸算法轉(zhuǎn)換成等價(jià)的非遞歸算法應(yīng)該設(shè)置（ A ）。A棧 B隊(duì)列C堆?；蜿?duì)列 D數(shù)組7表達(dá)式a*(b+c)-d的后綴表達(dá)式是（ B ）。 Aabcd*+- Babc+*d- Cabc*+d- D-+*abcd8判斷一個(gè)順序隊(duì)列sq（最多元素為m0）為空的條件是（ C ）。 Asq-rear-sq-front= m0 Bsq-rear-sq-front-1= = m0 Csq-front=sq-rear Dsq-front=sq-rear+19判斷一個(gè)循環(huán)隊(duì)列Q（最多元素為m0）為空的條件是（ A ）。 AQ-front=Q-rear BQ-front!=Q-rear CQ-front=(Q-rear+1)% m0 DQ-front!= (Q-rear+1)%m0 10判斷棧S滿(mǎn)（元素個(gè)數(shù)最多n個(gè)）的條件是（C ）。 As-top=0 Bs-top!=0 Cs-top=n-1 Ds-top!=n-1 11一個(gè)隊(duì)列的入隊(duì)順序是a,b,c,d，則離隊(duì)的順序是（ B ）。 Aa,d,cb Ba,b,c,d Cd,c,b,a Dc,b,d,a12如果以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，則退棧操作時(shí)（ C ）。 A必須判斷棧是否滿(mǎn) B判斷棧元素類(lèi)型 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保存被刪結(jié)點(diǎn)的值，則執(zhí)行（ A ）。 Ax=top-data; top=top-next; Bx=top-data; Ctop=top-next; x=top-data; Dtop=top-next; x=data;16在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算為（C ）。 Ar=f-next; Br=r-next; Cf=f-next; Df=r-next;17在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的運(yùn)算為（B ）。 Af-next=s; f=s; Br-next=s;r=s; Cs-next=r;r=s; Ds-next=f;f=s;18.以下陳述中正確的是（ A ）。A串是一種特殊的線(xiàn)性表 B串的長(zhǎng)度必須大于零C串中元素只能是字母 D空串就是空白串19設(shè)有兩個(gè)串p和q，其中q是p的子串，q在p中首次出現(xiàn)的位置的算法稱(chēng)為（ C ）。A求子串 B連接 C匹配 D求串長(zhǎng) 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=“English”，其子串的個(gè)數(shù)是（ D ）。 A9 B16 C 36 D2823串與普通的線(xiàn)性表相比較，它的特殊性體現(xiàn)在（ C ）。A順序的存儲(chǔ)結(jié)構(gòu) B鏈接的存儲(chǔ)結(jié)構(gòu) C數(shù)據(jù)元素是一個(gè)字符 D數(shù)據(jù)元素可以任意24空串與空格串（ B ）。A相同 B不相同 C可能相同 D無(wú)法確定25兩個(gè)字符串相等的條件是（ D）。 A兩串的長(zhǎng)度相等 B兩串包含的字符相同 C兩串的長(zhǎng)度相等，并且兩串包含的字符相同 D兩串的長(zhǎng)度相等，并且對(duì)應(yīng)位置上的字符相同26在實(shí)際應(yīng)用中，要輸入多個(gè)字符串，且長(zhǎng)度無(wú)法預(yù)定。則應(yīng)該采用（A ）存儲(chǔ)比較合適（ ）。A鏈?zhǔn)?B 順序 C堆結(jié)構(gòu) D無(wú)法確定 27.一維數(shù)組A采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占用6個(gè)字節(jié)，第6個(gè)元素的存儲(chǔ)地址為100，則該數(shù)組的首地址是（ C ）。A64 B28C70 D9028稀疏矩陣采用壓縮存儲(chǔ)的目的主要是（D ）。A表達(dá)變得簡(jiǎn)單 B對(duì)矩陣元素的存取變得簡(jiǎn)單 C去掉矩陣中的多余元素 D減少不必要的存儲(chǔ)空間的開(kāi)銷(xiāo)29一個(gè)非空廣義表的表頭（ C ）。 A不可能是原子 B只能是子表 C只能是原子 D可以是子表或原子 30常對(duì)數(shù)組進(jìn)行的兩種基本操作是（ C ）。A建立與刪除 B索引與、和修改C查找和修改 D查找與索引31. 設(shè)二維數(shù)組A56按行優(yōu)先順序存儲(chǔ)在內(nèi)存中，已知A00 起始地址為1000，每個(gè)數(shù)組元素占用5個(gè)存儲(chǔ)單元，則元素A44的地址為（ A ）。 A1140 B1145 C 1120 D112532設(shè)有一個(gè)20階的對(duì)稱(chēng)矩陣A，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始），則矩陣中元素a9,2在一維數(shù)組B中的下標(biāo)是（ D ）。A41 B32 C18 D38二、填空題1棧是限定在表的一端進(jìn)行插入和刪除操作的線(xiàn)性表，又稱(chēng)為 后進(jìn)先出 。2循環(huán)隊(duì)列隊(duì)頭指針在隊(duì)尾指針 下一個(gè) 位置，隊(duì)列是“滿(mǎn)”狀態(tài)3在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，當(dāng)插入一個(gè)新的隊(duì)列元素時(shí)，尾指針 增1 ，當(dāng)刪除一個(gè)元素隊(duì)列時(shí)，頭指針 增1 。4循環(huán)隊(duì)列的引入，目的是為了克服 假上溢 。5向順序棧插入新元素分為三步：第一步進(jìn)行 棧是否滿(mǎ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）為空的條件是 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)閚ext)11從一個(gè)棧頂指針為h的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪結(jié)點(diǎn)的值，可執(zhí)行x=h-data;和_ h=h-next _。(結(jié)點(diǎn)的指針域?yàn)閚ext)12在一個(gè)鏈隊(duì)中，設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的操作為_(kāi) r-next=s _和r=s; (結(jié)點(diǎn)的指針域?yàn)閚ext)13在一個(gè)鏈隊(duì)中，設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的操作為_(kāi) f=f-next _。 (結(jié)點(diǎn)的指針域?yàn)閚ext) 14串是一種特殊的線(xiàn)性表，其特殊性表現(xiàn)在組成串的數(shù)據(jù)元素都是 字符 。15串的兩種最基本的存儲(chǔ)方式是 順序存儲(chǔ)方式 和 鏈?zhǔn)酱鎯?chǔ)方式 。16空串的長(zhǎng)度是 0 ；空格串的長(zhǎng)度是 空格字符的個(gè)數(shù) 。17需要壓縮存儲(chǔ)的矩陣可分為 特殊 矩陣和 稀疏 矩陣兩種。18設(shè)廣義表L=（），（），則表頭是 （） ，表尾是 （） ，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ì)稱(chēng)矩陣A，用數(shù)組s進(jìn)行壓縮存儲(chǔ)，當(dāng)ij時(shí)，A的數(shù)組元素aij相應(yīng)于數(shù)組s的數(shù)組元素的下標(biāo)為_(kāi) 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)述棧和一般線(xiàn)性表的區(qū)別。答：棧是一種先進(jìn)后出的線(xiàn)性表，棧的插入和刪除操作都只能在棧頂進(jìn)行，而一般的線(xiàn)性表可以在線(xiàn)性表的任何位置進(jìn)行插入和刪除操作。2簡(jiǎn)述隊(duì)列和一般線(xiàn)性表的區(qū)別。隊(duì)列是一種先進(jìn)先出的線(xiàn)性表，隊(duì)列的插入只能在隊(duì)尾進(jìn)行，隊(duì)列的刪除只能在隊(duì)頭進(jìn)行，而一般的線(xiàn)性表可以在線(xià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)先出，因此輸出序列有：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不可能由輸入序列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，CABD5用S表示入棧操作，X表示出棧操作，若元素入棧順序?yàn)?234，為了得到1342出棧順序，相應(yīng)的S和X操作串是什么？答：應(yīng)是SXSSXSXX。各操作結(jié)果如下：S 1入棧X 1出棧 輸出序列：1S 2入棧S 3入棧X 3出棧 輸出序列：13S 4入棧 X 4出棧 輸出序列：134X 2出棧 輸出序列：1342 6有5個(gè)元素，其入棧次序?yàn)椋篈、B、C、D、E，在各種可能的出棧次序中，以元素C、D最先的次序有哪幾個(gè)？答：從題中可知，要使C第一個(gè)且D第二個(gè)出棧，應(yīng)是A入棧，B入棧，C入棧，C出棧，D入棧。之后可以有以下幾種情況：（1）B出棧，A出棧，E入棧，E出棧，輸出序列為：CDBAE。（2）B出棧，E入棧，E出棧，A 出棧，輸出序列為CDBEA。（3）E入棧，E出棧，B出棧，A出棧，輸出序列為CDEBA所以可能的次序有：CDBAE，CDBEA，CDEBA7寫(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)述廣義表和線(xiàn)性表的區(qū)別和聯(lián)系。答：廣義表是線(xiàn)性表的的推廣，它也是n(n0)個(gè)元素a1 ,a2ai an的有限序列，其中ai或者是原子或者是一個(gè)廣義表。所以，廣義表是一種遞歸數(shù)據(jù)結(jié)構(gòu)，而線(xiàn)性表沒(méi)有這種特性，線(xiàn)性表可以看成廣義表的特殊情況，當(dāng)ai都是原子時(shí)，廣義表退化成線(xiàn)性表。 四、程序填空題1在下面空格處填寫(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)為空，元素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入棧（棧底到棧頂元素是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)前隊(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ù)類(lèi)型*/struct node *rear; LinkQueue;void initqueue(LinkQueue *Q)/*初始化隊(duì)列*/ 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); s-data=x; if (Q-rear=NULL) /*原為空隊(duì)時(shí)*/ Q-rear=s;s-next=s; else /*原隊(duì)不為空時(shí)*/ p=Q-rear-next; /*p指向第一個(gè)結(jié)點(diǎn)*/Q-rear-next=s; /*將s鏈接到隊(duì)尾*/Q-rear=s; /*Q-rear指向隊(duì)尾*/s-next=p; void delqueue(LinkQueue *Q) /*出隊(duì)算法*/ struct node *t; if (Q-rear=NULL) 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; /*t指向第一個(gè)結(jié)點(diǎn)*/Q-rear-next=t-next; /*引成循環(huán)鏈*/ free(t); elemtype gethead(LinkQueue *Q) /*取隊(duì)首元素算法*/ if (Q-rear=NULL) printf(隊(duì)列為空!n); else return(Q-rear-next-data); int emptyqueue(LinkQueue *Q) /*判斷隊(duì)列是否為空算法*/ if (Q-rear=NULL) return(1); /*為空,則返回true*/ else return(0); /*不為空,則返回flase*/ void dispqueue(LinkQueue *Q) /*顯示隊(duì)列中元素算法*/ struct node *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 B16 C17 D472二叉樹(shù)第k層上最多有（ B ）個(gè)結(jié)點(diǎn)。 A2k B2k-1 C2k-1 D2k-1 3二叉樹(shù)的深度為k,則二叉樹(shù)最多有（ D ）個(gè)結(jié)點(diǎn)。A2k B2k-1C2k-1 D2k-14. 設(shè)某一二叉樹(shù)先序遍歷為abdec，中序遍歷為dbeac，則該二叉樹(shù)后序遍歷的順序是（ C ）。 Aabdec Bdebac Cdebca Dabedc5將含有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 ）。A33 B34 C35 D366如果將給定的一組數(shù)據(jù)作為葉子數(shù)值，所構(gòu)造出的二叉樹(shù)的帶權(quán)路徑長(zhǎng)度最小，則該樹(shù)稱(chēng)為（ A ）。A哈夫曼樹(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ù)加1B二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)必大于0C完全二叉樹(shù)中，任何一個(gè)結(jié)點(diǎn)的度，或者為0或者為2 D二叉樹(shù)的度是28在一棵度為3的樹(shù)中，度為3的結(jié)點(diǎn)個(gè)數(shù)為2，度為2的結(jié)點(diǎn)個(gè)數(shù)為1，則度為0的結(jié)點(diǎn)個(gè)數(shù)為（ C ）。A4 B5 C6 D79在一棵度具有5層的滿(mǎn)二叉樹(shù)中結(jié)點(diǎn)總數(shù)為（ A ）。A31 B32 C33 D1610. 利用n個(gè)值作為葉結(jié)點(diǎn)的權(quán)生成的哈夫曼樹(shù)中共包含有( D )個(gè)結(jié)點(diǎn)。 A. n B. n+1 C. 2*n D. 2*n-111. 利用3、6、8、12這四個(gè)值作為葉子結(jié)點(diǎn)的權(quán)，生成一棵哈夫曼樹(shù)，該樹(shù)中所有葉子的最長(zhǎng)帶權(quán)路徑長(zhǎng)度為( A )。 A. 18 B. 16 C. 12 D. 3012在一棵樹(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 ）。 A2i B2i-1 D2i+1 C2i+2 14設(shè)一棵哈夫曼樹(shù)共有n個(gè)葉結(jié)點(diǎn)，則該樹(shù)有（ B ）個(gè)非葉結(jié)點(diǎn)。 An Bn-1 Cn+1 D2n15設(shè)一棵有n個(gè)葉結(jié)點(diǎn)的二叉樹(shù)，除葉結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)度數(shù)都為2，則該樹(shù)共有（ B ）個(gè)結(jié)點(diǎn)。 A2n B2n-1 C2n+1 D2n+2 16在一個(gè)圖G中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)之和的（ C ）倍。 A1/2 B1 C2 D4 17在一個(gè)有像圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的（ B ）倍。 A鄰接矩陣表示法 B鄰接表表示法 C逆鄰接表表示法 D鄰接表和逆鄰接表 18在圖的存儲(chǔ)結(jié)構(gòu)表示中，表示形式唯一的是（ C ）。 An Bn+1 Cn-1 Dn/219一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖包含（ A ）條邊。 An（n-1） Bn（n+1） C n（n-1）/2 D n（n+1）/220對(duì)于具有n個(gè)頂點(diǎn)的圖，若采用鄰接矩陣表示，則該矩陣的大小為（ B ）。 An Bn2 Cn-1 D（n-1）221對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，若采用鄰接表表示，則所有頂點(diǎn)鄰接表中的結(jié)點(diǎn)總數(shù)為（ D ）。 An Be C2n D2e22在有向圖的鄰接表中，每個(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)先搜索即可訪(fǎng)問(wèn)所有頂點(diǎn)，則該圖一定是（ B ）。 A完全圖 B連通圖 C有回路 D一棵樹(shù)25下列有關(guān)圖遍歷的說(shuō)法不正確的是（ C ）。A連通圖的深度優(yōu)先搜索是一個(gè)遞歸過(guò)程B圖的廣度優(yōu)先搜索中鄰接點(diǎn)的尋找具有“先進(jìn)先出”的特征C非連通圖不能用深度優(yōu)先搜索法D圖的遍歷要求每一頂點(diǎn)僅被訪(fǎng)問(wèn)一次 26無(wú)向圖的鄰接矩陣是一個(gè)（ A ）。 A對(duì)稱(chēng)矩陣 B 零矩陣 C上三角矩陣 D對(duì)角矩陣27圖的深度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的（ A ）遍歷。A先序 B 中序 C后序 D層次28已知下圖所示的一個(gè)圖，若從頂點(diǎn)V1出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（ C ）。 AV1V2V4V8V3V5V6V7 BV1V2V4V5V8V3V6V7 CV1V2V4V8V5V3V6V7 DV1V3V6V7V2V4V5V8V6V7V1V2V3V8V4V5二、填空題1結(jié)點(diǎn)的度是指結(jié)點(diǎn)所擁有的 子樹(shù)樹(shù)木或后繼結(jié)點(diǎn)數(shù) 。2樹(shù)的度是指 樹(shù)中所有結(jié)點(diǎn)的度的最大值 。3度大于0的結(jié)點(diǎn)稱(chēng)作 分支結(jié)點(diǎn) 或 非終端結(jié)點(diǎn) 。4度等于0的結(jié)點(diǎn)稱(chēng)作 葉子結(jié)點(diǎn) 或 終端結(jié)點(diǎn) 。5在一棵樹(shù)中，每個(gè)結(jié)點(diǎn)的 子樹(shù)的根 或者說(shuō)每個(gè)結(jié)點(diǎn)的 后繼結(jié)點(diǎn) 稱(chēng)為該結(jié)點(diǎn)的 孩子結(jié)點(diǎn) ，簡(jiǎn)稱(chēng)為孩子。6從根結(jié)點(diǎn)到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)稱(chēng)為該結(jié)點(diǎn)的 祖先 。7樹(shù)的深度或高度是指 樹(shù)中結(jié)點(diǎn)的最大層數(shù) 。8具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度是 。9先序遍歷二叉樹(shù)的的操作定義為；若二叉樹(shù)為空，則為空操作，否則進(jìn)行如下操作，訪(fǎng)問(wèn)二叉樹(shù)的 根結(jié)點(diǎn) ；先序遍歷二叉樹(shù)的 左子樹(shù) ，先序遍歷二叉樹(shù)的 右子樹(shù) 。 10中序遍歷二叉樹(shù)的的操作定義為；若二叉樹(shù)為空，則為空操作，否則進(jìn)行如下操作，中序遍歷二叉樹(shù)的 左子樹(shù) ；訪(fǎng)問(wèn)而叉樹(shù)的 根結(jié)點(diǎn) ，中序遍歷二叉樹(shù)的 右子樹(shù) 。11后序遍歷二叉樹(shù)的的操作定義為；若二叉樹(shù)為空，則為空操作，否則進(jìn)行如下操作，后序遍歷二叉樹(shù)的 左子樹(shù) ；后序遍歷二叉樹(shù)的 右子樹(shù) ，訪(fǎng)問(wèn)而叉樹(shù)的 根結(jié)點(diǎn) 。12將樹(shù)中結(jié)點(diǎn)賦上一個(gè)有著某種意義的實(shí)數(shù)，稱(chēng)此實(shí)數(shù)為該結(jié)點(diǎn)的 權(quán) 。13樹(shù)的帶權(quán)路徑長(zhǎng)度為樹(shù)中所有葉子結(jié)點(diǎn)的 帶權(quán)路徑長(zhǎng)度之和 。14哈夫曼樹(shù)又稱(chēng)為 最優(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)系，因此圖的數(shù)據(jù)元素之間是一種 多對(duì)多 的關(guān)系。18圖的遍歷是從圖的某一頂點(diǎn)出發(fā)，按照一定的搜索方法對(duì)圖中 所有頂點(diǎn) 各做 一次 訪(fǎng)問(wèn)的過(guò)程。19圖的深度優(yōu)先搜索遍歷類(lèi)似于樹(shù)的 先序 遍歷。20圖的廣度優(yōu)先搜索類(lèi)似于樹(shù)的 按層次 遍歷。21具有n個(gè)頂點(diǎn)的有向圖的鄰接矩陣，其元素個(gè)數(shù)為 n2 。22圖常用的兩種存儲(chǔ)結(jié)構(gòu)是 鄰接矩陣 和 鄰接表 。23在有n