電大數(shù)據(jù)結構(本)形成性考核冊(作業(yè)1-4)原題帶答案

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

2、有窮性 B輸入性 C可行性 D可讀性6算法分析的目的是（ C ）。 A找出數(shù)據(jù)結構的合理性 B研究算法中的輸入和輸出的關系 C分析算法的效率以求改進 D分析算法的易懂性和文檔性7數(shù)據(jù)結構是一門研究計算機中（ B  ）對象及其關系的科學。A數(shù)值運算          B非數(shù)值運算C集合              D非集合 8算法的時間復雜度與（ C ）有關。

3、A所使用的計算機 B與計算機的操作系統(tǒng) C與算法本身 D與數(shù)據(jù)結構9設有一個長度為n的順序表，要在第i個元素之前（也就是插入元素作為新表的第i個元素），則移動元素個數(shù)為（ A ）。 An-i+1 Bn-i Cn-i-1 Di10設有一個長度為n的順序表，要刪除第i個元素移動元素的個數(shù)為（ B ）。 An-i+1 Bn-i Cn-i-1 Di11在一個單鏈表中，p、q分別指向表中兩個相鄰的結點，且q所指結點是p所指結點的直接后繼，現(xiàn)要刪除q所指結點，可用語句（ C ）。 Ap=q->next Bp->next=q Cp->next=qànext Dq->next

4、=NULL12在一個單鏈表中p所指結點之后插入一個s所指的結點時，可執(zhí)行（ D ）。 Ap->next= s; sànext= pànext Bp->next=sànext; Cp=s->next Ds->next=p->next; p->next=s;13非空的單向循環(huán)鏈表的尾結點滿足（C    ）（設頭指針為head，指針p指向尾結點）。 A.P->next= =NULL BP= =NULL CP->next= =head DP= = head 14鏈表不具有的特點是（ A ）。 A

5、可隨機訪問任一元素 B插入刪除不需要移動元素 C不必事先估計存儲空間 D所需空間與線性表長度成正比15帶頭結點的鏈表為空的判斷條件是（  B   ）（設頭指針為head）。Ahead = =NULLBhead->next= =NULL  Chead->next= =head Dhead!=NULL16在一個單鏈表中，p、q分別指向表中兩個相鄰的結點，且q所指結點是p所指結點的直接后繼，現(xiàn)要刪除q所指結點，可用語句（  C ）。Ap=q->nextBp->next=q Cp->

6、next=q->nextDq->next=NULL17在一個鏈隊中，假設f和r分別為隊頭和隊尾指針，則刪除一個結點的運算為（C ）。 Ar=f->next; Br=r->next; Cf=f->next; Df=r->next;18在一個鏈隊中，假設f和r分別為隊頭和隊尾指針，則插入s所指結點的運算為（ B ）。 Af->next=s; f=s; Br->next=s;r=s; Cs->next=r;r=s; Ds->next=f;f=s;19.一個順序表第一個元素的存儲地址是90，每個元素的長度為2，則第6個元素的地址是（B ）。A

7、98 B100 C102 D10620有關線性表的正確說法是（ D ）。A每個元素都有一個直接前驅和一個直接后繼 B線性表至少要求一個元素C表中的元素必須按由小到大或由大到下排序 D除了一個和最后一個元素外，其余元素都有一個且僅有一個直接前驅和一個直接后繼二、填空題1在一個長度為n的順序存儲結構的線性表中，向第i(1£i£n+1)個元素之前插入新元素時，需向后移動 n-i+1 個數(shù)據(jù)元素。2從長度為n的采用順序存儲結構的線性表中刪除第i(1£i£n+1)個元素 ，需向前移動 n-i 個元素。3數(shù)據(jù)結構按結點間的關系，可分為4種邏輯結構： 集合 、 線性結

8、構 、 樹形結構 、 圖狀結構 。4數(shù)據(jù)的邏輯結構在計算機中的表示稱為 物理結構 或 存儲結構 。5除了第1個和最后一個結點外，其余結點有且只有一個前驅結點和后繼結點的數(shù)據(jù)結構為 線性結構 ，每個結點可有任意多個前驅和后繼結點數(shù)的結構為 非線性結構 。6算法的5個重要特性是 有窮性 、 確定性 、 可形性 、 有零個或多個輸入 、 有零個或多個輸出 。7數(shù)據(jù)結構中的數(shù)據(jù)元素存在多對多的關系稱為_圖狀結構_結構。8數(shù)據(jù)結構中的數(shù)據(jù)元素存在一對多的關系稱為_樹形結構_結構。9數(shù)據(jù)結構中的數(shù)據(jù)元素存在一對一的關系稱為_線性結構_結構。10要求在n個數(shù)據(jù)元素中找其中值最大的元素，設基本操作為元素間的比

9、較。則比較的次數(shù)和算法的時間復雜度分別為_ n-1_和 _ O(n)_ 。11在一個單鏈表中p所指結點之后插入一個s所指結點時，應執(zhí)行_ s->next=p->next _和p->next=s;的操作。12設有一個頭指針為head的單向循環(huán)鏈表，p指向鏈表中的結點，若p->next= =_ head _，則p所指結點為尾結點。13在一個單向鏈表中，要刪除p所指結點，已知q指向p所指結點的前驅結點。則可以用操作_ q->next=p->next _。14設有一個頭指針為head的單向鏈表，p指向表中某一個結點，且有p->next= =NULL,通過操作_

10、 p->next=head _,就可使該單向鏈表構造成單向循環(huán)鏈表。15每個結點只包含一個指針域的線性表叫 單鏈表 。16線性表具有 順序存儲 和 鏈式存儲 兩種存儲結構。17數(shù)據(jù)的邏輯結構是從邏輯關系上描述數(shù)據(jù)，它與數(shù)據(jù)的關系 存儲結構 無關，是獨立于計算機的。18在雙向循環(huán)鏈表的每個結點中包含 兩個 指針域，其中next指向它的 直接后繼 ，prior指向它的 直接前驅 ，而頭結點的prior指向 尾結點 ，尾結點的next指向 頭結點 。19單向循環(huán)鏈表是單向鏈表的一種擴充，當單向鏈表帶有頭結點時，把單向鏈表中尾結點的指針域由空指針改為 頭結點的指針 ；當單向鏈表不帶頭結點時，則把

11、單向鏈表中尾結點的指針域由空指針改為指向 指向第一個結點的指針 。20線性鏈表的邏輯關系時通過每個結點指針域中的指針來表示的。其邏輯順序和物理存儲順序不再一致，而是一種 鏈式 存儲結構，又稱為 鏈表 。 三、問答題1簡述數(shù)據(jù)的邏輯結構和存儲結構的區(qū)別與聯(lián)系，它們?nèi)绾斡绊懰惴ǖ脑O計與實現(xiàn)？答：若用結點表示某個數(shù)據(jù)元素，則結點與結點之間的邏輯關系就稱為數(shù)據(jù)的邏輯結構。數(shù)據(jù)在計算機中的存儲表示稱為數(shù)據(jù)的存儲結構。可見，數(shù)據(jù)的邏輯結構是反映數(shù)據(jù)之間的固有關系，而數(shù)據(jù)的存儲結構是數(shù)據(jù)在計算機中的存儲表示。盡管因采用的存儲結構不同，邏輯上相鄰的結點，其物理地址未必相同，但可通過結點的內(nèi)部信息，找到其相鄰的

12、結點，從而保留了邏輯結構的特點。采用的存儲結構不同，對數(shù)據(jù)的操作在靈活性，算法復雜度等方面差別較大。2解釋順序存儲結構和鏈式存儲結構的特點，并比較順序存儲結構和鏈式存儲結構的優(yōu)缺點。答：順序結構存儲時，相鄰數(shù)據(jù)元素的存放地址也相鄰，即邏輯結構和存儲結構是統(tǒng)一的，要求內(nèi)存中存儲單元的地址必須是連續(xù)的。優(yōu)點：一般情況下，存儲密度大，存儲空間利用率高。缺點：（1）在做插入和刪除操作時，需移動大量元素；（2）由于難以估計，必須預先分配較大的空間，往往使存儲空間不能得到充分利用；（3）表的容量難以擴充。鏈式結構存儲時，相鄰數(shù)據(jù)元素可隨意存放，所占空間分為兩部分，一部分存放結點值，另一部分存放表示結點間關

13、系的指針。優(yōu)點：插入和刪除元素時很方便，使用靈活。缺點：存儲密度小，存儲空間利用率低。3什么情況下用順序表比鏈表好？答：順序表適于做查找這樣的靜態(tài)操作，鏈表適于做插入和刪除這樣的動態(tài)操作。如果線性表的變化長度變化不大，且其主要操作是查找，則采用順序表；如果線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。4頭指針、頭結點、第一個結點（或稱首元結點）的區(qū)別是什么？頭結點是在鏈表的開始結點之前附加的一個結點；第一個結點（或稱首元結點）是鏈表中存儲第一個數(shù)據(jù)元素的結點；頭指針是指向鏈表中第一個結點（或為頭結點或為首元結點）的指針。5解釋帶頭結點的單鏈表和不帶頭結點的單鏈表的區(qū)別。答：帶

14、頭結點的單鏈表和不帶頭結點的單鏈表的區(qū)別主要體現(xiàn)在其結構上和算法操作上。在結構上，帶頭結點的單鏈表，不管鏈表是否為空，均含有一個頭結點，不帶頭結點的單鏈表不含頭結點。在操作上，帶頭結點的單鏈表的初始化為申請一個頭結點。無論插入或刪除的位置是地第一個結點還是其他結點，算法步驟都相同。不帶頭結點的單鏈表，其算法步驟要分別考慮插入或刪除的位置是第一個結點還是其他結點。因為兩種情況的算法步驟不同。四、程序填空題1下列是用尾插法建立帶頭結點的且有n個結點的單向鏈表的算法，請在空格內(nèi)填上適當?shù)恼Z句。NODE *create1(n)/* 對線性表(1,2,.,n),建立帶頭結點的單向鏈表 */ NODE *

15、head,*p,*q; int i; p=(NODE *)malloc(sizeof(NODE); head=p; q=p; p->next=NULL; for(i=1;i<=n;i+) p=(NODE *)malloc(sizeof(NODE); （1）p->data=i ; （2）p->next=NULL ; （3）q->next=p ; （4） q=p ; return(head);2下列是用頭插法建立帶頭結點的且有n個結點的單向鏈表的算法，請在空格內(nèi)填上適當?shù)恼Z句。NODE *create2(n)/*對線性表(n,n-1,.,1),建立帶頭結點的線性鏈表

16、*/ NODE *head,*p,*q; int i; p=(NODE *)malloc(sizeof(NODE); （1） head=p ; p->next=NULL; （2） q=p ; for(i=1;i<=n;i+) p=(NODE *)malloc(sizeof(NODE); p->data=i; if(i=1) （3） p->next=NULL ; else（4） p->next=q->next ;（5） q->next=p ; return(head);3下列是在具有頭結點單向列表中刪除第i個結點，請在空格內(nèi)填上適當?shù)恼Z句。int del

17、ete(NODE *head,int i)NODE *p,*q; int j; q=head;j=0; while(q!=NULL)&&(j<i-1) /*找到要刪除結點的直接前驅，并使q指向它*/ q=q->next;j+; if(q=NULL) return(0);（1） p=q->next ; （2） q->next=p->next ; free(p); return(1);五、完成：實驗1線性表根據(jù)實驗要求（見教材P201-202）認真完成本實驗，并提交實驗報數(shù)據(jù)結構（本）課程作業(yè)2（本部分作業(yè)覆蓋教材第3-5章的內(nèi)容）一、單項選擇題1若讓

18、元素1，2，3依次進棧，則出棧順序不可能為（ C ）。A3，2，1 B2，1，3 C3，1，2 D1，3，22一個隊列的入隊序列是1，2，3，4。則隊列的輸出序列是（ B ）。A4，3，2，1 B1，2，3，4 C1，4，3，2 D3，2，4，13向順序棧中壓入新元素時，應當（ A ）。A先移動棧頂指針，再存入元素 B先存入元素，再移動棧頂指針 C先后次序無關緊要 D同時進行4在一個棧頂指針為top的鏈棧中，將一個p指針所指的結點入棧，應執(zhí)行（ C ）。Atop->next=p; Bp->next=top->next; top->next=p;Cp->next=t

19、op; top=p; Dp->next=top->next; top=top->next;5在一個棧頂指針為top的鏈棧中刪除一個結點時，用 x保存被刪結點的值，則執(zhí)行（ B ）。Ax=top;top=top->next; Bx=top->data;Ctop=top->next; x=top->data; Dx=top->data; top=top->next;6一般情況下，將遞歸算法轉換成等價的非遞歸算法應該設置（ A ）。A棧 B隊列C堆?；蜿犃?D數(shù)組7表達式a*(b+c)-d的后綴表達式是（ B ）。 Aabcd*+- Babc+*

20、d- Cabc*+d- D-+*abcd8判斷一個順序隊列sq（最多元素為m0）為空的條件是（ C ）。 Asq->rear-sq->front= m0 Bsq->rear-sq->front-1= = m0 Csq->front=sq->rear Dsq->front=sq->rear+19判斷一個循環(huán)隊列Q（最多元素為m0）為空的條件是（ A ）。 AQ->front=Q->rear BQ->front!=Q->rear CQ->front=(Q->rear+1)% m0 DQ->front!= (Q

21、->rear+1)%m0 10判斷棧S滿（元素個數(shù)最多n個）的條件是（C ）。 As->top=0 Bs->top!=0 Cs->top=n-1 Ds->top!=n-1 11一個隊列的入隊順序是a,b,c,d，則離隊的順序是（ B ）。 Aa,d,cb Ba,b,c,d Cd,c,b,a Dc,b,d,a12如果以鏈表作為棧的存儲結構，則退棧操作時（ C ）。 A必須判斷棧是否滿 B判斷棧元素類型 C必須判斷棧是否空 D對棧不作任何判斷13在解決計算機主機與打印機之間速度不匹配問題時通常設置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入緩沖區(qū)中，而打印機則從緩沖

22、區(qū)中取出數(shù)據(jù)打印，該緩沖區(qū)應該是一個（ B ）結構。A堆棧 B隊列 C數(shù)組 D先性表14一個遞歸算法必須包括（ B ）。A遞歸部分B終止條件和遞歸部分 C迭代部分 D終止條件和迭代部分15從一個棧頂指針為top的鏈棧中刪除一個結點時，用變量x保存被刪結點的值，則執(zhí)行（ A ）。 Ax=top->data; top=top->next; Bx=top->data; Ctop=top->next; x=top->data; Dtop=top->next; x=data;16在一個鏈隊中，假設f和r分別為隊頭和隊尾指針，則刪除一個結點的運算為（C ）。 Ar=f-

23、>next; Br=r->next; Cf=f->next; Df=r->next;17在一個鏈隊中，假設f和r分別為隊頭和隊尾指針，則插入s所指結點的運算為（B ）。 Af->next=s; f=s; Br->next=s;r=s; Cs->next=r;r=s; Ds->next=f;f=s;18.以下陳述中正確的是（ A ）。A串是一種特殊的線性表 B串的長度必須大于零C串中元素只能是字母 D空串就是空白串19設有兩個串p和q，其中q是p的子串，q在p中首次出現(xiàn)的位置的算法稱為（ C ）。A求子串 B連接 C匹配 D求串長 20串是（ D

24、）。 A不少于一個字母的序列 B任意個字母的序列 C不少于一個字符的序列 D有限個字符的序列 21串的長度是指（ B ）。A串中所含不同字母的個數(shù) B串中所含字符的個數(shù)C串中所含不同字符的個數(shù) D串中所含非空格字符的個數(shù)22. 若串S=“English”，其子串的個數(shù)是（ D ）。 A9 B16 C 36 D2823串與普通的線性表相比較，它的特殊性體現(xiàn)在（ C ）。A順序的存儲結構 B鏈接的存儲結構 C數(shù)據(jù)元素是一個字符 D數(shù)據(jù)元素可以任意24空串與空格串（ B ）。A相同 B不相同 C可能相同 D無法確定25兩個字符串相等的條件是（ D）。 A兩串的長度相等 B兩串包含的字符相同 C兩串的

25、長度相等，并且兩串包含的字符相同 D兩串的長度相等，并且對應位置上的字符相同26在實際應用中，要輸入多個字符串，且長度無法預定。則應該采用（A ）存儲比較合適（ ）。A鏈式 B 順序 C堆結構 D無法確定 27.一維數(shù)組A采用順序存儲結構，每個元素占用6個字節(jié)，第6個元素的存儲地址為100，則該數(shù)組的首地址是（ C ）。A64 B28C70 D9028稀疏矩陣采用壓縮存儲的目的主要是（D ）。A表達變得簡單 B對矩陣元素的存取變得簡單 C去掉矩陣中的多余元素 D減少不必要的存儲空間的開銷29一個非空廣義表的表頭（ C ）。 A不可能是原子 B只能是子表 C只能是原子 D可以是子表或原子 30常

26、對數(shù)組進行的兩種基本操作是（ C ）。A建立與刪除 B索引與、和修改C查找和修改 D查找與索引31. 設二維數(shù)組A56按行優(yōu)先順序存儲在內(nèi)存中，已知A00 起始地址為1000，每個數(shù)組元素占用5個存儲單元，則元素A44的地址為（ A ）。 A1140 B1145 C 1120 D112532設有一個20階的對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標從1開始），則矩陣中元素a9,2在一維數(shù)組B中的下標是（ D ）。A41 B32 C18 D38二、填空題1棧是限定在表的一端進行插入和刪除操作的線性表，又稱為 后進先出 。2循環(huán)隊列隊頭指針在隊尾指針 下

27、一個 位置，隊列是“滿”狀態(tài)3在隊列的順序存儲結構中，當插入一個新的隊列元素時，尾指針 增1 ，當刪除一個元素隊列時，頭指針 增1 。4循環(huán)隊列的引入，目的是為了克服 假上溢 。5向順序棧插入新元素分為三步：第一步進行 棧是否滿 判斷，判斷條件是 s->top=MAXSIZE-1 ；第二步是修改 棧頂指針 ；第三步是把新元素賦給 棧頂對應的數(shù)組元素 。同樣從順序棧刪除元素分為三步：第一步進行 棧是否空 判斷，判斷條件是 s->top=-1 。第二步是把 棧頂元素 ；第三步 修改棧頂指針 。6假設以S和X分別表示入棧和出棧操作，則對輸入序列a,b,c,d,e一系列棧操作SSXSXSS

28、XXX之后，得到的輸出序列為 bceda 。7一個遞歸算法必須包括 終止條件 和 遞歸部分 。8判斷一個循環(huán)隊列LU（最多元素為m0）為空的條件是 LU->front=LU->rear 。9在將中綴表達式轉換成后綴表達式和計算后綴表達式的算法中，都需要使用棧，對于前者，進入棧中的元素為表達式中的 運算符 ，而對于后者，進入棧的元素為 操作數(shù) ，中綴表達式(a+b)/c-(f-d/c)所對應的后綴表達式是 ab+c/fde/- 。 10向一個棧頂指針為h的鏈棧中插入一個s所指結點時，可執(zhí)行_ s->next=h _和h=s;操作。(結點的指針域為next)11從一個棧頂指針為h

29、的鏈棧中刪除一個結點時，用x保存被刪結點的值，可執(zhí)行x=h->data;和_ h=h->next _。(結點的指針域為next)12在一個鏈隊中，設f和r分別為隊頭和隊尾指針，則插入s所指結點的操作為_ r->next=s _和r=s; (結點的指針域為next)13在一個鏈隊中，設f和r分別為隊頭和隊尾指針，則刪除一個結點的操作為_ f=f->next _。 (結點的指針域為next) 14串是一種特殊的線性表，其特殊性表現(xiàn)在組成串的數(shù)據(jù)元素都是 字符 。15串的兩種最基本的存儲方式是 順序存儲方式 和 鏈式存儲方式 。16空串的長度是 0 ；空格串的長度是 空格字符

30、的個數(shù) 。17需要壓縮存儲的矩陣可分為 特殊 矩陣和 稀疏 矩陣兩種。18設廣義表L=（），（），則表頭是 （） ，表尾是 （） ，L的長度是 2 。19廣義表A（a,b,c）,(d,e,f)）的表尾為 （d,e,f） 。20兩個串相等的充分必要條件是_串長度相等且對應位置的字符相等 _。21設有n階對稱矩陣A，用數(shù)組s進行壓縮存儲，當i³j時，A的數(shù)組元素aij相應于數(shù)組s的數(shù)組元素的下標為_ i(i-1)/2+j _。（數(shù)組元素的下標從1開始）22對稀疏矩陣進行壓縮存儲，矩陣中每個非零元素對應的三元組包括該元素的_行下標_、_列下標_和_非零元素值_三項信息。三、問答題1簡述棧和

31、一般線性表的區(qū)別。答：棧是一種先進后出的線性表，棧的插入和刪除操作都只能在棧頂進行，而一般的線性表可以在線性表的任何位置進行插入和刪除操作。2簡述隊列和一般線性表的區(qū)別。隊列是一種先進先出的線性表，隊列的插入只能在隊尾進行，隊列的刪除只能在隊頭進行，而一般的線性表可以在線性表的任何位置進行插入和刪除操作。3鏈棧中為何不設頭結點？答：因為鏈棧只在鏈頭插入和刪除結點，不可能在鏈表中間插入和刪除結點，算法實現(xiàn)很簡單，所以一般不設置頭結點。4利用一個棧，則：（1）如果輸入序列由A，B，C組成，試給出全部可能的輸出序列和不可能的輸出序列。（2）如果輸入序列由A，B，C，D組成，試給出全部可能的輸出序列和

32、不可能的輸出序列。答：（1）棧的操作特點是后進先出，因此輸出序列有：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ù)項，除上述五個不同的組合外，還有一個C，A，B組合。但不可能先把C出棧，再把A出棧，（A不在棧頂位置），最后把B出棧，所以序列CAB不可能由輸入序列A，B，C 通過棧得到。（2）按照上述方法，可能的輸出序列有：ABCD，ABDC，ACBD，A

33、CDB，ADCB，BACD，BADC，BCAD，BCDA，BDCA，CBAD，CBDA，CDBA，DCBA。不可能的輸出序列有：DABC，ADBC，DACB，DBAC，BDAC，DBCA，DCAB，CDAB，CADB，CABD5用S表示入棧操作，X表示出棧操作，若元素入棧順序為1234，為了得到1342出棧順序，相應的S和X操作串是什么？答：應是SXSSXSXX。各操作結果如下：S 1入棧X 1出棧 輸出序列：1S 2入棧S 3入棧X 3出棧 輸出序列：13S 4入棧 X 4出棧 輸出序列：134X 2出棧 輸出序列：1342 6有5個元素，其入棧次序為：A、B、C、D、E，在各種可能的出棧次

34、序中，以元素C、D最先的次序有哪幾個？答：從題中可知，要使C第一個且D第二個出棧，應是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寫出以下運算式的后綴算術運算式 3x2+x-1/x+5 (A+B)*C-D/(E+F)+G答；對應的后綴算術運算式 3x2*x+1x/-5+ AB+C*DEF+/-G+8 簡述廣義表和線性表的區(qū)別和聯(lián)系。答：廣義表

35、是線性表的的推廣，它也是n(n>0)個元素a1 ,a2ai an的有限序列，其中ai或者是原子或者是一個廣義表。所以，廣義表是一種遞歸數(shù)據(jù)結構，而線性表沒有這種特性，線性表可以看成廣義表的特殊情況，當ai都是原子時，廣義表退化成線性表。 四、程序填空題1在下面空格處填寫適當?shù)恼Z句，以使下面的鏈式隊列取出元素的算法完整。 int write(LinkQueue *q) QueueNode *p; if (q->front=q->rear) /*隊空*/ printf(“underflow”); exit(0); while (q->front->next != NU

36、LL) p=q->front->next; (1) q->front->next=p->next; printf(“%4d”,p->data); (2) free(p); （3） q->rear=q->front ; /*隊空時，頭尾指針指向頭結點*/ 五、綜合題 1設棧S和隊列Q的初始狀態(tài)為空，元素e1,e2,e3,e4,e5和e6依次通過S，一個元素出棧后即進隊列Q，若6個元素出隊的序列是e2,e4,e3,e6,e5,e1，則棧S的容量至少應該是多少？答：出隊序列是e2,e4,e3,e6,e5,e1的過程： e1入棧（棧底到棧頂元素是e1）

37、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出棧（棧底到棧頂元素是空）棧中最多時有3個元素，所以棧S的容量至少是3。 2假設用循環(huán)單鏈表實現(xiàn)循環(huán)隊列，該隊列只使用一個尾指針rear，其相應的存儲結構和基本算法如下；（1）初始化隊列initqueu

38、e(Q):建立一個新的空隊列Q。（2）入隊列enqueue(Q,x):將元素x插入到隊列Q中。（3）出隊列delqueue(Q):從隊列Q中退出一個元素。（4）取隊首元素gethead(Q):返回當前隊首元素。（5）判斷隊列是否為空：emptyqueue(Q)。（6）顯示隊列中元素：dispqueue(Q)。算法設計如下：/*只有一個指針rear的鏈式隊的基本操作*/#include <stdio.h>typedef char elemtype;struct node /*定義鏈隊列結點*/elemtype data;struct node *next;typedef struct

39、 queue /*定義鏈隊列數(shù)據(jù)類型*/struct node *rear; LinkQueue;void initqueue(LinkQueue *Q)/*初始化隊列*/ Q=(struct queue *)malloc(sizeof(struct queue); Q->rear=NULL; void enqueue(LinkQueue *Q,elemtype x) /*入隊算法*/ struct node *s,*p; s=(struct node *)malloc(sizeof(struct node); s->data=x; if (Q->rear=NULL) /*原

40、為空隊時*/ Q->rear=s;s->next=s; else /*原隊不為空時*/ p=Q->rear->next; /*p指向第一個結點*/Q->rear->next=s; /*將s鏈接到隊尾*/Q->rear=s; /*Q->rear指向隊尾*/s->next=p; void delqueue(LinkQueue *Q) /*出隊算法*/ struct node *t; if (Q->rear=NULL) printf("隊列為空!n");return(0); else if (Q->rear->

41、;next=Q->rear) /*只有一個結點時*/ t=Q->rear;Q->rear=NULL; else /*有多個結點時*/ t=Q->rear->next; /*t指向第一個結點*/Q->rear->next=t->next; /*引成循環(huán)鏈*/ free(t); elemtype gethead(LinkQueue *Q) /*取隊首元素算法*/ if (Q->rear=NULL) printf("隊列為空!n"); else return(Q->rear->next->data); int

42、 emptyqueue(LinkQueue *Q) /*判斷隊列是否為空算法*/ if (Q->rear=NULL) return(1); /*為空,則返回true*/ else return(0); /*不為空,則返回flase*/ void dispqueue(LinkQueue *Q) /*顯示隊列中元素算法*/ struct node *p=Q->rear->next; printf("隊列元素:"); while (p!=Q->rear) printf("%c ",p->data);p=p->next; pr

43、intf("%cn",p->data);六、完成：實驗2棧、隊列、遞歸程序設計根據(jù)實驗要求（見教材P203）認真完成本實驗，并提交實驗報告。數(shù)據(jù)結構（本）課程作業(yè)作業(yè)3（本部分作業(yè)覆蓋教材第6-7章的內(nèi)容）一、單項選擇題1.假定一棵二叉樹中，雙分支結點數(shù)為15，單分支結點數(shù)為30，則葉子結點數(shù)為（ B ）。A15 B16 C17 D472二叉樹第k層上最多有（ B ）個結點。 A2k B2k-1 C2k-1 D2k-1 3二叉樹的深度為k,則二叉樹最多有（ D ）個結點。A2k B2k-1C2k-1 D2k-14. 設某一二叉樹先序遍歷為abdec，中序遍歷為dbea

44、c，則該二叉樹后序遍歷的順序是（ C ）。 Aabdec Bdebac Cdebca Dabedc5將含有150個結點的完全二叉樹從根這一層開始，每一層從左到右依次對結點進行編號，根結點的編號為1，則編號為69的結點的雙親結點的編號為（ B ）。A33 B34 C35 D366如果將給定的一組數(shù)據(jù)作為葉子數(shù)值，所構造出的二叉樹的帶權路徑長度最小，則該樹稱為（ A ）。A哈夫曼樹 B平衡二叉樹 C二叉樹 D完全二叉樹7下列有關二叉樹的說法正確的是（ A ）。A二叉樹中度為0的結點的個數(shù)等于度為2的結點的個數(shù)加1B二叉樹中結點個數(shù)必大于0C完全二叉樹中，任何一個結點的度，或者為0或者為2 D二叉樹

45、的度是28在一棵度為3的樹中，度為3的結點個數(shù)為2，度為2的結點個數(shù)為1，則度為0的結點個數(shù)為（ C ）。A4 B5 C6 D79在一棵度具有5層的滿二叉樹中結點總數(shù)為（ A ）。A31 B32 C33 D1610. 利用n個值作為葉結點的權生成的哈夫曼樹中共包含有( D )個結點。 A. n B. n+1 C. 2*n D. 2*n-1 11. 利用3、6、8、12這四個值作為葉子結點的權，生成一棵哈夫曼樹，該樹中所有葉子的最長帶權路徑長度為( A )。 A. 18 B. 16 C. 12 D. 3012在一棵樹中，（ C ）沒有前驅結點。A分支結點 B葉結點 C樹根結點 D空結點13在一棵二叉樹中，若編號為i的結點存在右孩子，則右孩子的順序編號為（ C ）。 A2i B2i-1 D2i+1 C2i+2 14設一棵哈夫曼樹共有n個葉結點，則該樹有（ B ）個非葉結點。 An Bn-1 Cn+1 D2n15設一棵有n個葉結點的二叉樹，除葉結點外每個結點度數(shù)都為2，則該樹共有（ B ）個結點。 A2n B2n-1 C2n+1 D2n+2 16在一個圖G中，所有頂點的度數(shù)之和等于所有邊數(shù)之和的（ C ）倍。 A1/2 B1 C2 D4 17在一個有像圖中，所有頂點的入度之和等于所有頂點的出度之和的（ B ）倍。 A鄰接矩陣表示法 B鄰接表表示法 C逆鄰接表表