電大數(shù)據(jù)結(jié)構(gòu)(本)形成性考核冊(cè)(作業(yè)14)

1、數(shù)據(jù)結(jié)構(gòu)（本）形成性考核作業(yè)冊(cè)使用說(shuō)明本作業(yè)冊(cè)是中央廣播電視大學(xué)計(jì)算機(jī)科與技術(shù)專業(yè)（本科）數(shù)據(jù)結(jié)構(gòu)（本）課程形成性考核的依據(jù)，與數(shù)據(jù)結(jié)構(gòu)（本科）教材（李偉生主編，中央電大出版社出版）配套使用。數(shù)據(jù)結(jié)構(gòu)（本）課程是中央廣播電視大學(xué)計(jì)算機(jī)科學(xué)技術(shù)專業(yè)的一門(mén)統(tǒng)設(shè)必修、學(xué)位課程，4學(xué)分，共72學(xué)時(shí)。其中實(shí)驗(yàn)24學(xué)時(shí)，開(kāi)設(shè)一學(xué)期。本課程的特點(diǎn)是綜合性、實(shí)踐性強(qiáng)，內(nèi)容抽象，在專業(yè)中具有承上啟下的作用。因此，在學(xué)習(xí)本課程時(shí)，要注意理論聯(lián)系實(shí)際，結(jié)合教學(xué)內(nèi)容進(jìn)行上機(jī)實(shí)踐，認(rèn)真完成作業(yè)和實(shí)驗(yàn)內(nèi)容。本課程的總成績(jī)按百分制記分，其中形成性考核所占的比例為30%，終結(jié)性考試占70（閉卷，答題時(shí)限為90分鐘）。課程總成

2、績(jī)達(dá)到60分及以上者為合格，可以獲得該課程的學(xué)分。本課程的學(xué)位課程學(xué)分為70分，即課程總成績(jī)達(dá)到70分及以上者有資格申請(qǐng)專業(yè)學(xué)位。本課程共設(shè)計(jì)了4次形考作業(yè)，每次形考作業(yè)均包括實(shí)驗(yàn)內(nèi)容，由各地電大根據(jù)學(xué)生對(duì)作業(yè)中各種題型練習(xí)和實(shí)驗(yàn)的完成情況進(jìn)行考核。對(duì)于實(shí)驗(yàn)內(nèi)容要求按實(shí)驗(yàn)要求認(rèn)真完成，并提交實(shí)驗(yàn)報(bào)告。數(shù)據(jù)結(jié)構(gòu)（本）課程作業(yè)作業(yè)1（本部分作業(yè)覆蓋教材第1-2章的內(nèi)容）一、單項(xiàng)選擇題1在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ ）。a動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) b緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) c線性結(jié)構(gòu)和非線性結(jié)構(gòu) d內(nèi)部結(jié)構(gòu)和外部機(jī)構(gòu)2下列說(shuō)法中，不正確的是（ ）。a數(shù)據(jù)元素是數(shù)據(jù)的基本單位 b數(shù)據(jù)項(xiàng)是數(shù)據(jù)中不

3、可分割的最小可標(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è)（ ）。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ù)的（ ）。a存儲(chǔ)結(jié)構(gòu) b物理結(jié)構(gòu)c邏輯結(jié)構(gòu) d物理和存儲(chǔ)結(jié)構(gòu)5下列的敘述中，不屬于算法特性的是（ ）。a有窮性 b輸入性 c可行性 d可讀性6算法分析的目的是（ ）。 a找出數(shù)據(jù)結(jié)構(gòu)的合理性 b研究算法中的輸入和輸出的關(guān)系 c分析算法的效率以求改進(jìn) d分析算法的易懂性和文檔性7數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究計(jì)算機(jī)中（ ）對(duì)象及其關(guān)系的科學(xué)。a數(shù)值運(yùn)算 b非數(shù)值運(yùn)算c集合 d非集合 8算法的時(shí)間復(fù)雜度與（ ）有

4、關(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ù)為（ ）。 an-i+1 bn-i cn-i-1 di10設(shè)有一個(gè)長(zhǎng)度為n的順序表，要?jiǎng)h除第i個(gè)元素移動(dòng)元素的個(gè)數(shù)為（ ）。 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ǔ)句（ ）。 ap=q-next bp-next=q cp-next=qnext dq-next=null12在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)

5、s所指的結(jié)點(diǎn)時(shí)，可執(zhí)行（ ）。 ap-next= s; snext= pnext bp-next=snext; cp=s-next ds-next=p-next; p-next=s;13非空的單向循環(huán)鏈表的尾結(jié)點(diǎn)滿足（ ）（設(shè)頭指針為head，指針p指向尾結(jié)點(diǎn)）。 a.p-next= =null bp= =null cp-next= =head dp= = head 14鏈表不具有的特點(diǎn)是（ ）。 a可隨機(jī)訪問(wèn)任一元素 b插入刪除不需要移動(dòng)元素 c不必事先估計(jì)存儲(chǔ)空間 d所需空間與線性表長(zhǎng)度成正比15帶頭結(jié)點(diǎn)的鏈表為空的判斷條件是（ ）（設(shè)頭指針為head）。ahead = =nullbhea

6、d-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ǔ)句（ ）。ap=q-nextbp-next=qcp-next=q-nextdq-next=null17在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算為（ ）。 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)算為（ ）。 af-next=s; f=s; br-next=s

7、;r=s; cs-next=r;r=s; ds-next=f;f=s;19.一個(gè)順序表第一個(gè)元素的存儲(chǔ)地址是90，每個(gè)元素的長(zhǎng)度為2，則第6個(gè)元素的地址是（ ）。a98 b100 c102 d10620有關(guān)線性表的正確說(shuō)法是（ ）。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(1in+1)個(gè)元素之前插入新元素時(shí)，需向后移動(dòng) 個(gè)數(shù)據(jù)元素。2從長(zhǎng)度為n的采用順序存儲(chǔ)結(jié)構(gòu)的線性表中刪除第i(1in+1)個(gè)

8、元素 ，需向前移動(dòng) 個(gè)元素。3數(shù)據(jù)結(jié)構(gòu)按結(jié)點(diǎn)間的關(guān)系，可分為4種邏輯結(jié)構(gòu)： 、 、 、 。4數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示稱為 或 。5除了第1個(gè)和最后一個(gè)結(jié)點(diǎn)外，其余結(jié)點(diǎn)有且只有一個(gè)前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)為 ，每個(gè)結(jié)點(diǎn)可有任意多個(gè)前驅(qū)和后繼結(jié)點(diǎn)數(shù)的結(jié)構(gòu)為 。6算法的5個(gè)重要特性是 、 、 、 、 。7數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在多對(duì)多的關(guān)系稱為_(kāi) _結(jié)構(gòu)。8數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)多的關(guān)系稱為_(kāi) _結(jié)構(gòu)。9數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)一的關(guān)系稱為_(kāi) _結(jié)構(gòu)。10要求在n個(gè)數(shù)據(jù)元素中找其中值最大的元素，設(shè)基本操作為元素間的比較。則比較的次數(shù)和算法的時(shí)間復(fù)雜度分別為_(kāi) _和 _ _ 。11

9、在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行_ _和p-next=s;的操作。12設(shè)有一個(gè)頭指針為head的單向循環(huán)鏈表，p指向鏈表中的結(jié)點(diǎn)，若p-next= =_ _，則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)。則可以用操作_ _。14設(shè)有一個(gè)頭指針為head的單向鏈表，p指向表中某一個(gè)結(jié)點(diǎn)，且有p-next= =null,通過(guò)操作_ _,就可使該單向鏈表構(gòu)造成單向循環(huán)鏈表。15每個(gè)結(jié)點(diǎn)只包含一個(gè)指針域的線性表叫 。16線性表具有 和 兩種存儲(chǔ)結(jié)構(gòu)。17數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的關(guān)系 無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的。

10、18在雙向循環(huán)鏈表的每個(gè)結(jié)點(diǎn)中包含 指針域，其中next指向它的 ，prior指向它的 ，而頭結(jié)點(diǎn)的prior指向 ，尾結(jié)點(diǎn)的next指向 。19單向循環(huán)鏈表是單向鏈表的一種擴(kuò)充，當(dāng)單向鏈表帶有頭結(jié)點(diǎn)時(shí)，把單向鏈表中尾結(jié)點(diǎn)的指針域由空指針改為 ；當(dāng)單向鏈表不帶頭結(jié)點(diǎn)時(shí)，則把單向鏈表中尾結(jié)點(diǎn)的指針域由空指針改為指向 。20線性鏈表的邏輯關(guān)系時(shí)通過(guò)每個(gè)結(jié)點(diǎn)指針域中的指針來(lái)表示的。其邏輯順序和物理存儲(chǔ)順序不再一致，而是一種 存儲(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)？2解釋順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)，并比較順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

11、的優(yōu)缺點(diǎn)。3什么情況下用順序表比鏈表好？4頭指針、頭結(jié)點(diǎn)、第一個(gè)結(jié)點(diǎn)（或稱首元結(jié)點(diǎn)）的區(qū)別是什么？5解釋帶頭結(jié)點(diǎn)的單鏈表和不帶頭結(jié)點(diǎn)的單鏈表的區(qū)別。四、程序填空題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;inext=null; （2） ; for(i=1;idata=i; if(

12、i=1) （3） ; else（4） ;（5） ; 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） ; （2） ; 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若讓元

13、素1，2，3依次進(jìn)棧，則出棧順序不可能為（ ）。a3，2，1 b2，1，3 c3，1，2 d1，3，22一個(gè)隊(duì)列的入隊(duì)序列是1，2，3，4。則隊(duì)列的輸出序列是（ ）。a4，3，2，1 b1，2，3，4 c1，4，3，2 d3，2，4，13向順序棧中壓入新元素時(shí)，應(yīng)當(dāng)（ ）。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í)行（ ）。atop-next=p; bp-next=top-next; top-next=p;cp-next=top; top=p; dp-next=top-next;

14、top=top-next;5在一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用 x保存被刪結(jié)點(diǎn)的值，則執(zhí)行（ ）。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棧 b隊(duì)列c堆?；蜿?duì)列 d數(shù)組7表達(dá)式a*(b+c)-d的后綴表達(dá)式是（ ）。 aabcd*+- babc+*d- cabc*+d- d-+*abcd8判斷一個(gè)順序隊(duì)列sq（最多元素為m0）為空的條件是（ ）。 asq-rear-sq-front= m

15、0 bsq-rear-sq-front-1= = m0 csq-front=sq-rear dsq-front=sq-rear+19判斷一個(gè)循環(huán)隊(duì)列q（最多元素為m0）為空的條件是（ ）。 aq-front=q-rear bq-front!=q-rear cq-front=(q-rear+1)% m0 dq-front!= (q-rear+1)%m0 10判斷一個(gè)循環(huán)隊(duì)列q（最多元素為m0）為空的條件是（ ）。 aq-front=q-rear bq-front!=q-rear cq-front=(q-rear+1)% m0 dq-front!= (q-rear+1)% m0 11判斷棧s滿（元

16、素個(gè)數(shù)最多n個(gè)）的條件是（ ）。 as-top=0 bs-top!=0 cs-top=n-1 ds-top!=n-1 12一個(gè)隊(duì)列的入隊(duì)順序是a,b,c,d，則離隊(duì)的順序是（ ）。 aa,d,cb ba,b,c,d cd,c,b,a dc,b,d,a13如果以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，則退棧操作時(shí)（ ）。 a必須判斷棧是否滿 b判斷棧元素類(lèi)型 c必須判斷棧是否空 d對(duì)棧不作任何判斷14在解決計(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è)（ ）結(jié)構(gòu)。a堆棧 b隊(duì)列 c數(shù)組 d先性表15一個(gè)遞歸

17、算法必須包括（ ）。a遞歸部分b終止條件和遞歸部分 c迭代部分 d終止條件和迭代部分16從一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用變量x保存被刪結(jié)點(diǎn)的值，則執(zhí)行（ ）。 ax=top-data; top=top-next; bx=top-data; ctop=top-next; x=top-data; dtop=top-next; x=data;17在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算為（ ）。 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)算為（

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

19、“english”，其子串的個(gè)數(shù)是（ ）。 a9 b16 c 36 d2824下面關(guān)于串的敘述中，不正確的是（ ）。a串是字符的有限序列 b空串是由空格構(gòu)成的串 c模式匹配是串的一種重要運(yùn)算 d串即可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ) 25串與普通的線性表相比較，它的特殊性體現(xiàn)在（ ）。a順序的存儲(chǔ)結(jié)構(gòu) b鏈接的存儲(chǔ)結(jié)構(gòu) c數(shù)據(jù)元素是一個(gè)字符 d數(shù)據(jù)元素可以任意26空串與空格串（ ）。a相同 b不相同 c可能相同 d無(wú)法確定27兩個(gè)字符串相等的條件是（ ）。 a兩串的長(zhǎng)度相等 b兩串包含的字符相同 c兩串的長(zhǎng)度相等，并且兩串包含的字符相同 d兩串的長(zhǎng)度相等，并且對(duì)應(yīng)位置上的字符相同28在實(shí)際應(yīng)

20、用中，要輸入多個(gè)字符串，且長(zhǎng)度無(wú)法預(yù)定。則應(yīng)該采用（ ）存儲(chǔ)比較合適（ ）。a鏈?zhǔn)?b 順序 c堆結(jié)構(gòu) d無(wú)法確定 29.一維數(shù)組a采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占用6個(gè)字節(jié)，第6個(gè)元素的存儲(chǔ)地址為100，則該數(shù)組的首地址是（ ）。a64 b28c70 d9030稀疏矩陣采用壓縮存儲(chǔ)的目的主要是（ ）。a表達(dá)變得簡(jiǎn)單 b對(duì)矩陣元素的存取變得簡(jiǎn)單 c去掉矩陣中的多余元素 d減少不必要的存儲(chǔ)空間的開(kāi)銷(xiāo)31一個(gè)非空廣義表的表頭（ ）。 a不可能是原子 b只能是子表 c只能是原子 d可以是子表或原子 32常對(duì)數(shù)組進(jìn)行的兩種基本操作是（ ）。a建立與刪除 b索引與、和修改c查找和修改 d查找與索引33. 設(shè)

21、二維數(shù)組a56按行優(yōu)先順序存儲(chǔ)在內(nèi)存中，已知a00 起始地址為1000，每個(gè)數(shù)組元素占用5個(gè)存儲(chǔ)單元，則元素a44的地址為（ ）。 a1140 b1145 c 1120 d112534設(shè)有一個(gè)20階的對(duì)稱矩陣a，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組b中（數(shù)組下標(biāo)從1開(kāi)始），則矩陣中元素a9,2在一維數(shù)組b中的下標(biāo)是（ ）。a41 b32 c18 d3835一個(gè)非空廣義表的表頭（ ）。a不可能是子表 b只能是子表 c只能是原子 d可以是子表或原子二、填空題1棧是限定在表的一端進(jìn)行插入和刪除操作的線性表，又稱為 。2隊(duì)列的特性是 。3往棧中插入元素的操作方式是：先 ，后 。

22、4刪除棧中元素的操作方式是：先 ，后 。5循環(huán)隊(duì)列隊(duì)頭指針在隊(duì)尾指針 位置，隊(duì)列是“滿”狀態(tài)6在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，當(dāng)插入一個(gè)新的隊(duì)列元素時(shí)，尾指針 ，當(dāng)刪除一個(gè)元素隊(duì)列時(shí)，頭指針 。7循環(huán)隊(duì)列的引入，目的是為了克服 。8向順序棧插入新元素分為三步：第一步進(jìn)行 判斷，判斷條件是 ；第二步是修改 ；第三步是把新元素賦給 。同樣從順序棧刪除元素分為三步：第一步進(jìn)行 判斷，判斷條件是 。第二步是把 ；第三步 。9假設(shè)以s和x分別表示入棧和出棧操作，則對(duì)輸入序列a,b,c,d,e一系列棧操作ssxsxssxxx之后，得到的輸出序列為 。10一個(gè)遞歸算法必須包括 和 。11判斷一個(gè)循環(huán)隊(duì)列l(wèi)u（最多元

23、素為m0）為空的條件是 。12在將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式和計(jì)算后綴表達(dá)式的算法中，都需要使用棧，對(duì)于前者，進(jìn)入棧中的元素為表達(dá)式中的 ，而對(duì)于后者，進(jìn)入棧的元素為 ，中綴表達(dá)式(a+b)/c-(f-d/c)所對(duì)應(yīng)的后綴表達(dá)式是 。 16向一個(gè)棧頂指針為h的鏈棧中插入一個(gè)s所指結(jié)點(diǎn)時(shí)，可執(zhí)行_和h=s;操作。(結(jié)點(diǎn)的指針域?yàn)閚ext)17從一個(gè)棧頂指針為h的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪結(jié)點(diǎn)的值，可執(zhí)行x=h-data;和_。(結(jié)點(diǎn)的指針域?yàn)閚ext)18在一個(gè)鏈隊(duì)中，設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的操作為_(kāi)和r=s; (結(jié)點(diǎn)的指針域?yàn)閚ext)19在一個(gè)鏈隊(duì)中，設(shè)f和r

24、分別為隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的操作為_(kāi)。 (結(jié)點(diǎn)的指針域?yàn)閚ext) 20串是一種特殊的線性表，其特殊性表現(xiàn)在組成串的數(shù)據(jù)元素都是 。21串的兩種最基本的存儲(chǔ)方式是 和 。22空串的長(zhǎng)度是 ；空格串的長(zhǎng)度是 。23需要壓縮存儲(chǔ)的矩陣可分為 矩陣和 矩陣兩種。24設(shè)廣義表l=（），（），則表頭是 ，表尾是 ，l的長(zhǎng)度是 。25廣義表a（a,b,c）,(d,e,f)）的表尾為 。26兩個(gè)串相等的充分必要條件是_ _。27設(shè)有n階對(duì)稱矩陣a，用數(shù)組s進(jìn)行壓縮存儲(chǔ)，當(dāng)ij時(shí)，a的數(shù)組元素aij相應(yīng)于數(shù)組s的數(shù)組元素的下標(biāo)為_(kāi) _。（數(shù)組元素的下標(biāo)從1開(kāi)始）28對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，矩陣中每個(gè)

25、非零元素對(duì)應(yīng)的三元組包括該元素的_、_和_三項(xiàng)信息。三、問(wèn)答題1簡(jiǎn)述棧和一般線性表的區(qū)別。2簡(jiǎn)述隊(duì)列和一般線性表的區(qū)別。3鏈棧中為何不設(shè)頭結(jié)點(diǎn)？4利用一個(gè)棧，則：（1）如果輸入序列由a，b，c組成，試給出全部可能的輸出序列和不可能的輸出序列。（2）如果輸入序列由a，b，c，d組成，試給出全部可能的輸出序列和不可能的輸出序列。5用s表示入棧操作，x表示出棧操作，若元素入棧順序?yàn)?234，為了得到1342出棧順序，相應(yīng)的s和x操作串是什么？6有5個(gè)元素，其入棧次序?yàn)椋篴、b、c、d、e，在各種可能的出棧次序中，以元素c、d最先的次序有哪幾個(gè)？7寫(xiě)出以下運(yùn)算式的后綴算術(shù)運(yùn)算式 3x2+x-1/x+5

26、 (a+b)*c-d/(e+f)+g8在什么情況下可以用遞歸解決問(wèn)題？在寫(xiě)遞歸程序時(shí)應(yīng)注意什么？9 簡(jiǎn)述廣義表和線性表的區(qū)別和聯(lián)系。四、程序填空題1在下面空格處填寫(xiě)適當(dāng)?shù)恼Z(yǔ)句，以使下面的循環(huán)隊(duì)列的入隊(duì)和出隊(duì)算法完整。define true 1;define false 0;define maxsize 100;typedef charelemtype;typedef struct elemtype queue maxsize; int front,rear; sequeuetype;sequeuetype q;int encqueue(sequeuetype*q,elemtype x)if (

27、 ( 1 ) )printf(the cicular queue is full!n);return(false);else (2) (3) return(true); /*encqueue*/elemtype del_cqueue(sequeuetype *q) if ( (4) ) printf(the queue is empty !n) return(null); else (5) return(q-queueq-front); /*del_cqueue*/ 2.在下面空格處填寫(xiě)適當(dāng)?shù)恼Z(yǔ)句，以使下面的鏈?zhǔn)疥?duì)列取出元素的算法完整。 int write(linkqueue *q) queu

28、enode *p; if (q-front=q-rear) /*隊(duì)空*/ printf(“underflow”); exit(0); while (q-front-next != null) p=q-front-next; (1) printf(“%4d”,p-data); (2) （3） ; /*隊(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)該是多少？ 2假設(shè)用循環(huán)單鏈表實(shí)現(xiàn)循環(huán)隊(duì)列，該隊(duì)列只使用一個(gè)尾指針rea

29、r，其相應(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í)驗(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，

30、單分支結(jié)點(diǎn)數(shù)為30，則葉子結(jié)點(diǎn)數(shù)為（ ）。a15 b16 c17 d472二叉樹(shù)第k層上最多有（ ）個(gè)結(jié)點(diǎn)。 a2k b2k-1 c2k-1 d2k-1 3二叉樹(shù)的深度為k,則二叉樹(shù)最多有（ ）個(gè)結(jié)點(diǎn)。a2k b2k-1c2k-1 d2k-14. 設(shè)某一二叉樹(shù)先序遍歷為abdec，中序遍歷為dbeac，則該二叉樹(shù)后序遍歷的順序是（ ）。 aabdec bdebac cdebca dabedc5樹(shù)最適合于用來(lái)表示（ ）。a線性結(jié)構(gòu)的數(shù)據(jù) b順序結(jié)構(gòu)的數(shù)據(jù) c元素之間無(wú)前驅(qū)和后繼關(guān)系的數(shù)據(jù) d元素之間有包含和層次關(guān)系的數(shù)據(jù) 6設(shè)a,b為一棵二叉樹(shù)的兩個(gè)結(jié)點(diǎn)，在后續(xù)遍歷中，a在b前的條件是（ ）。a

31、a在b上方 ba在b下方 ca在b左方 da在b右方7權(quán)值為1，2，6，8的四個(gè)結(jié)點(diǎn)構(gòu)成的哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度是（ ）。a18 b28 c19 d298將含有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)為（ ）。a33 b34 c35 d369如果將給定的一組數(shù)據(jù)作為葉子數(shù)值，所構(gòu)造出的二叉樹(shù)的帶權(quán)路徑長(zhǎng)度最小，則該樹(shù)稱為（ ）。a哈夫曼樹(shù) b平衡二叉樹(shù) c二叉樹(shù) d完全二叉樹(shù)10下列有關(guān)二叉樹(shù)的說(shuō)法正確的是（ ）。a二叉樹(shù)中度為0的結(jié)點(diǎn)的個(gè)數(shù)等于度為2的結(jié)點(diǎn)的個(gè)數(shù)加1b二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)必大于0c完全二叉樹(shù)中，

32、任何一個(gè)結(jié)點(diǎn)的度，或者為0或者為2 d二叉樹(shù)的度是211在一棵度為3的樹(shù)中，度為3的結(jié)點(diǎn)個(gè)數(shù)為2，度為2的結(jié)點(diǎn)個(gè)數(shù)為1，則度為0的結(jié)點(diǎn)個(gè)數(shù)為（ ）。a4 b5 c6 d712在一棵度具有5層的滿二叉樹(shù)中結(jié)點(diǎn)總數(shù)為（ ）。a31 b32 c33 d1613. 利用n個(gè)值作為葉結(jié)點(diǎn)的權(quán)生成的哈夫曼樹(shù)中共包含有( )個(gè)結(jié)點(diǎn)。 a. n b. n+1 c. 2*n d. 2*n-1 14. 利用n個(gè)值作為葉結(jié)點(diǎn)的權(quán)生成的哈夫曼樹(shù)中共包含有( )個(gè)雙支結(jié)點(diǎn)。 a. n b. n-1 c. n+1 d. 2*n-1 15. 利用3、6、8、12這四個(gè)值作為葉子結(jié)點(diǎn)的權(quán)，生成一棵哈夫曼樹(shù)，該樹(shù)中所有葉子的最

33、長(zhǎng)帶權(quán)路徑長(zhǎng)度為( )。 a. 18 b. 16 c. 12 d. 3016在一棵樹(shù)中，（ ）沒(méi)有前驅(qū)結(jié)點(diǎn)。a分支結(jié)點(diǎn) b葉結(jié)點(diǎn) c樹(shù)根結(jié)點(diǎn) d空結(jié)點(diǎn)17在一棵二叉樹(shù)中，若編號(hào)為i的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號(hào)為（ ）。 a2i b2i-1 d2i+1 c2i+2 18設(shè)一棵哈夫曼樹(shù)共有n個(gè)葉結(jié)點(diǎn)，則該樹(shù)有（ ）個(gè)非葉結(jié)點(diǎn)。 an bn-1 cn+1 d2n19設(shè)一棵有n個(gè)葉結(jié)點(diǎn)的二叉樹(shù)，除葉結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)度數(shù)都為2，則該樹(shù)共有（ ）個(gè)結(jié)點(diǎn)。 a2n b2n-1 c2n+1 d2n+2 20一棵完全二叉樹(shù)共有5層，且第5層上有六個(gè)結(jié)點(diǎn)，該樹(shù)共有（ ）個(gè)結(jié)點(diǎn)。 a20 b21 c23 d3

34、021在一個(gè)圖g中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)之和的（ ）倍。 a1/2 b1 c2 d4 22在一個(gè)有像圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的（ ）倍。 a鄰接矩陣表示法 b鄰接表表示法 c逆鄰接表表示法 d鄰接表和逆鄰接表 23在圖的存儲(chǔ)結(jié)構(gòu)表示中，表示形式唯一的是（ ）。 an bn+1 cn-1 dn/224一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖包含（ ）條邊。 an（n-1） bn（n+1） c n（n-1）/2 d n（n+1）/225一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖包含（ ）條邊。 an（n-1） bn（n+1） c n（n-1）/2 d n（n+1）/226對(duì)于具有n個(gè)頂點(diǎn)的圖

35、，若采用鄰接矩陣表示，則該矩陣的大小為（ ）。 an bn2 cn-1 d（n-1）227對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，若采用鄰接表表示，則表頭向量的大小為（ ）。 an be c2n d2e28對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，若采用鄰接表表示，則所有頂點(diǎn)鄰接表中的結(jié)點(diǎn)總數(shù)為（ ）。 an be c2n d2e29在有向圖的鄰接表中，每個(gè)頂點(diǎn)鄰接表鏈接著該頂點(diǎn)所有（ ）鄰接點(diǎn)。 a入邊 b 出邊 c入邊和出邊 d 不是入邊也不是出邊 30在有向圖的逆鄰接表中，每個(gè)頂點(diǎn)鄰接表鏈接著該頂點(diǎn)所有（ ）鄰接點(diǎn)。 a入邊 b出邊 c入邊和出邊 d不是入邊也不是出邊31鄰接表是圖的一種（ ）

36、。 a順序存儲(chǔ)結(jié)構(gòu) b鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) c索引存儲(chǔ)結(jié)構(gòu) d散列存儲(chǔ)結(jié)構(gòu) 32如果從無(wú)向圖的任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問(wèn)所有頂點(diǎn)，則該圖一定是（ ）。 a完全圖 b連通圖 c有回路 d一棵樹(shù)33下列有關(guān)圖遍歷的說(shuō)法不正確的是（ ）。a連通圖的深度優(yōu)先搜索是一個(gè)遞歸過(guò)程b圖的廣度優(yōu)先搜索中鄰接點(diǎn)的尋找具有“先進(jìn)先出”的特征c非連通圖不能用深度優(yōu)先搜索法d圖的遍歷要求每一頂點(diǎn)僅被訪問(wèn)一次 34無(wú)向圖的鄰接矩陣是一個(gè)（ ）。 a對(duì)稱矩陣 b 零矩陣 c上三角矩陣 d對(duì)角矩陣35圖的深度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的（ ）遍歷。a先序 b 中序 c后序 d層次36已知下圖所示的一個(gè)圖，若從頂點(diǎn)v1出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（ ）。 av1v2v4v8v3v5v6v7 bv1v2v4v5v8v3v6v7 cv1v2v4v8v5v3v6v7 dv1v3v6v7v2v4v5v8v6v7v1v2v3v8v4v5二、填空題1結(jié)點(diǎn)的度是指結(jié)點(diǎn)所擁有的 。2樹(shù)的度是指 。3度大于0的結(jié)點(diǎn)稱作 或 。4度等于0的結(jié)點(diǎn)稱作 或 。5在一棵樹(shù)中，每個(gè)結(jié)點(diǎn)的 或者說(shuō)每個(gè)結(jié)點(diǎn)的 稱為該結(jié)點(diǎn)的 ，簡(jiǎn)稱為孩子。6一個(gè)結(jié)點(diǎn)稱為其