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

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è)的一門統(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é)性 測(cè)試占70% 閉卷,做題時(shí)限為90分鐘.課程總成績(jī)到

2、達(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).緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C.線性結(jié)構(gòu)和非線性結(jié)構(gòu)D.內(nèi)部結(jié)構(gòu)和外部機(jī)構(gòu)2 .以下說(shuō)法中,不正確的選項(xiàng)是.A.數(shù)據(jù)元素是數(shù)據(jù)的根本單位B.數(shù)據(jù)項(xiàng)是數(shù)據(jù)中不

3、可分割的最小可標(biāo)識(shí)單位C.數(shù)據(jù)可有假設(shè)干個(gè)數(shù)據(jù)元素構(gòu)成D.數(shù)據(jù)項(xiàng)可由假設(shè)干個(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ù)類型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 .以下的表達(dá)中,不屬于算法特性的是.A有窮性B .輸入性C.可行性D.可讀性6 .算法分析的目的是.A .找出數(shù)據(jù)結(jié)構(gòu)的合理性B .研究算法中的輸入和輸出的關(guān)系C.分析算法的效率以求改良D .分析算法的易懂性和文檔性7 .數(shù)據(jù)結(jié)構(gòu)是一門研究計(jì)算機(jī)中對(duì)象及其關(guān)系的科學(xué).A.數(shù)值運(yùn)算B .非數(shù)值運(yùn)算C.集合D .非集合8.算法

4、的時(shí)間復(fù)雜度與有關(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ù)為n-i+1 Bn-i C.n-i-110.設(shè)有一個(gè)長(zhǎng)度為n的順序表,要?jiǎng)h除第i個(gè)元素移動(dòng)元素的個(gè)數(shù)為n-i+1 Bn-i Cn-i-1在一個(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ǔ)句p=q-nextB . p-next=qC . p-next=q nextD. q-next=NULL12.在一個(gè)單鏈表中所指結(jié)點(diǎn)之后插入一個(gè)s所指的結(jié)

5、點(diǎn)時(shí),可執(zhí)行A . p-next= s; snext= p nextB . p-next=s next;C. p=s-next.s-next=p-next; p-next=s;13.非空的單向循環(huán)鏈表的尾結(jié)點(diǎn)滿足設(shè)頭指針為head,指針p指向尾結(jié)點(diǎn).A. . P-next= =NULL.P=NULLC . P-next= =head.P= = head14.鏈表不具有的特點(diǎn)是A .可隨機(jī)訪問(wèn)任兀系.插入刪除不需要移動(dòng)元素C .不必事先估計(jì)存儲(chǔ)空間.所需空間與線性表長(zhǎng)度成正15 .帶頭結(jié)點(diǎn)的鏈表為空的判斷條件是設(shè)頭指針為head.A. head = =NULLB. head-next= =NUL

6、LC. head-next= =headD. head!=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ǔ)句.A. p=q-nextB. p-next=qC. p-next=q-nextD. q-next=NULL17 .在一個(gè)鏈隊(duì)中,假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針,那么刪除一個(gè)結(jié)點(diǎn) 的運(yùn)算為.A . r=f-next;B. r=r-next;C. f=f-next;D. f=r-next;18 .在一個(gè)鏈隊(duì)中,假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針,那么插入 s所指結(jié) 點(diǎn)的運(yùn)算為.A . f-next=s; f=s;B.

7、 r-next=s;r=s;C. s-next=r;r=s;D. s-next=f;f=s;19 .一個(gè)順序表第一個(gè)元素的存儲(chǔ)地址是90,每個(gè)元素的長(zhǎng)度為 2,那么第6 個(gè)元素的地址是().A. 98 B . 100 C . 102 D . 10620 .有關(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(1 wiwn+1)個(gè)元素之 前插入新元素時(shí),需向后移動(dòng) 個(gè)數(shù)據(jù)

8、元素.2 .從長(zhǎng)度為n的采用順序存儲(chǔ)結(jié)構(gòu)的線性表中刪除第i(1 MiMn+1)個(gè)元素,需向前移動(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)系稱為 結(jié)構(gòu).8 .數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)多的關(guān)系稱為 結(jié)構(gòu).9 .數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)一的關(guān)系稱為 結(jié)構(gòu).10 .要求在n個(gè)數(shù)據(jù)元素中找其中值最大的元素,設(shè)

9、根本操作為元素間的 比擬.那么比擬的次數(shù)和算法的時(shí)間復(fù)雜度分別為 和.11 .在一個(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),假設(shè) 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 .線性表具有 和

10、 兩種存儲(chǔ)結(jié)構(gòu).17 .數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù),它與數(shù)據(jù)的關(guān)系 無(wú)關(guān),是獨(dú)立于計(jì)算機(jī)的.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)和

11、存儲(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)的優(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

12、=p; q=p; p-next=NULL;for(i=1;inext=NULL;(2) ;for(i=1;idata=i;if(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) (int j;q=head;j=0;找到要?jiǎng)h除結(jié)點(diǎn)的直接前驅(qū),并使 q指向它*/while(q!=NULL)&(jnext; j+; if(q=NULL) return(0); (1);(2) ;free(p); return(1); 五、完成：實(shí)驗(yàn)1線性表根據(jù)實(shí)驗(yàn)

13、要求見(jiàn)教材P201-202認(rèn)真完本錢實(shí)驗(yàn),并提交實(shí)驗(yàn)報(bào)告.數(shù)據(jù)結(jié)構(gòu)本課程作業(yè) 2本局部作業(yè)覆蓋教材第一、單項(xiàng)選擇題3-5章的內(nèi)容3依次進(jìn)棧,那么出棧順序不可能為A. 3, 2, 1. 2, 1 ,3C. 3, 1,2D. 1 , 3, 22. 一個(gè)隊(duì)列的入隊(duì)序列是1, 2, 3, 4.那么隊(duì)列的輸出序列是A. 4, 3, 2, 1 B. 1 , 2, 3,C. 1 , 4, 3, 2 D. 3, 2, 4,3.向順序棧中壓入新元素時(shí),應(yīng)當(dāng)A.先移動(dòng)棧頂指針,再存入元素.先存入元素,再移動(dòng)棧頂指針C.先后次序無(wú)關(guān)緊要4 .在一個(gè)棧頂指針為top的鏈棧中,將一個(gè)p指針?biāo)傅慕Y(jié)點(diǎn)入棧,應(yīng)執(zhí) 行.A.

14、 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è)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí), 用x保存被刪結(jié)點(diǎn)的 值,那么執(zhí)行.A. x=top;top=top-next;B. x=top-data;C. top=top -next; x=top-data;D. x=top-data; top=top-next;6 . 一般情況下,將遞歸算法轉(zhuǎn)換成等價(jià)的非遞歸算法應(yīng)該設(shè)置.隊(duì)列D.數(shù)組A.棧C.堆棧或隊(duì)列)abc*+d- D . -+*abc

15、d.sq-rear-sq-front-1= = mi.sq-front=sq-rear+17 .表達(dá)式a*(b+c)-d的后綴表達(dá)式是(A . abcd*+- B . abc+*d- Csq 最多元素為m為空的條件是8 .判斷一個(gè)順序隊(duì)列A . sq-rear-sq-front=miBC. sq-front=sq-rearD9 .判斷一個(gè)循環(huán)隊(duì)列 Q 最多元素為m為空的條件是Q-front!=Q-rearA . Q-front=Q-rearC. Q-front=(Q-rear+1)% mD . Q-front!= (Q-rear+1)%m10 .判斷一個(gè)循環(huán)隊(duì)列 Q 最多元素為m為空的條件是.

16、A . Q-front=Q-rearB. Q-front!=Q-rearC. Q-front=Q-rear+1% m D . Q-front!= Q-rear+1% ni11 .判斷棧S滿元素個(gè)數(shù)最多n個(gè)的條件是.A . s-top=0B. s-top!=0C. s-top=n-1D. s-top!=n-112 . 一個(gè)隊(duì)列的入隊(duì)順序是a,b,c,d ,那么離隊(duì)的順序是.A . a,d,cb B . a,b,c,d C . d,c,b,a D . c,b,d,a13 .如果以鏈表作為棧的存儲(chǔ)結(jié)構(gòu),那么退棧操作時(shí).A .必須判斷棧是否滿B.判斷棧元素類型C.必須判斷棧是否空D.對(duì)棧不作任何判斷1

17、4 .在解決計(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è)遞歸算法必須包括.A.遞歸局部 B.終止條件和遞歸局部C.迭代局部 D .終止條件和迭代局部16 .從一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí),用變量 x保存被刪 結(jié)點(diǎn)的值,那么執(zhí)行.A . x=top-data; top=top-next; B . x=top-data;.top=top-next; x=data;C. top=top-next; x=to

18、p-data; D17 .在一個(gè)鏈隊(duì)中,假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針,那么刪除一個(gè)結(jié)點(diǎn)的運(yùn)算為.A . r=f-next; B . r=r-next; C . f=f-next; D . f=r-next;18 .在一個(gè)鏈隊(duì)中,假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針,那么插入 s所指結(jié)點(diǎn) 的運(yùn)算為.A . f-next=s; f=s;B. r-next=s;r=s;C. s-next=r;r=s;D. s-next=f;f=s;19 .以下陳述中正確的選項(xiàng)是.A.串是一種特殊的線性表 B .串的長(zhǎng)度必須大于零C.串中元素只能是字母D .空串就是空白串20 .設(shè)有兩個(gè)串p和q,其中q是p的子串,q在p

19、中首次出現(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 .假設(shè)串S= English ,其子串的個(gè)數(shù)是3624 .下面關(guān)于串的表達(dá)中,不正確的選項(xiàng)是.A串是字符的有限序列B.空串是由空格構(gòu)成的串C.模式匹配是串的一種重要運(yùn)算D.串即可以采用順序存儲(chǔ),也可以采用鏈?zhǔn)酱鎯?chǔ)25 .串與普通的線性表相比擬,它的特殊性表達(dá)在.A.順序的存儲(chǔ)結(jié)構(gòu)B.鏈接的存儲(chǔ)

20、結(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)用中,要輸入多個(gè)字符串,且長(zhǎng)度無(wú)法預(yù)定.那么應(yīng)該采用存儲(chǔ)比擬適宜.A.鏈?zhǔn)紹 .順序C.堆結(jié)構(gòu) D .無(wú)法確定29 .一維數(shù)組A采用順序存儲(chǔ)結(jié)構(gòu),每個(gè)元素占用 6個(gè)字節(jié),第6個(gè)元素的 存儲(chǔ)地址為100,那么該數(shù)組的首地址是.28A. 6490C. 7030 .稀疏矩陣采用壓縮存儲(chǔ)的目的主要是A.表達(dá)變

21、得簡(jiǎn)單.對(duì)矩陣元素的存取變得簡(jiǎn)單C.去掉矩陣中的多余元素.減少不必要的存儲(chǔ)空間的開(kāi)銷31. 一個(gè)非空廣義表的表頭A .不可能是原子.只能是子表C.只能是原子.可以是子表或原子32.常對(duì)數(shù)組進(jìn)行的兩種根本操作是A建立與刪除.索引與、和修改.查找與索引C.查找和修改33.設(shè)二維數(shù)組A56按行優(yōu)先順序存儲(chǔ)在內(nèi)存中, A00起始地址為1000,每個(gè)數(shù)組元素占用5個(gè)存儲(chǔ)單元,那么元素A44的地址為A . 1140 B . 1145 C1120 D 112534.設(shè)有一個(gè)20階的對(duì)稱矩陣A,采用壓縮存儲(chǔ)的方式,將其下三角局部以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中數(shù)組下標(biāo)從1開(kāi)始,那么矩陣中元素a9,2在一維數(shù)組B

22、中的下標(biāo)是.A. 41 B . 3235. 一個(gè)非空廣義表的表頭A.不可能是子表BC.只能是原子D二、填空題C . 18 D . 38.只能是子表.可以是子表或原子1 .棧是限定在表的一端進(jìn)行插入和刪除操作的線性表,又稱為.2 .隊(duì)列的特性是.3 .往棧中插入元素的操作方式是：先, 后.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)行 判斷,判斷條件 是;第二步是修改

23、 ;第三步是把新元素賦 給.同樣從順序棧刪除元素分為三步：第一步進(jìn)行 判 斷,判斷條件是.第二步是把;第三9 .假設(shè)以S和X分別表示入棧和出棧操作,那么對(duì)輸入序列 a,b,c,d,e 一系歹U棧操作SSXSXSSXXX后,得至J的輸出序歹U為 .10 . 一個(gè)遞歸算法必須包括 和.11 .判斷一個(gè)循環(huán)隊(duì)列LU最多元素為 m為空的條件是 .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í),可

24、執(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)的操作為 和r=s;(結(jié)點(diǎn)的指針域?yàn)閚ext)19 .在一個(gè)鏈隊(duì)中,設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針,那么刪除一個(gè)結(jié)點(diǎn)的 操作為.(結(jié)點(diǎn)的指針域?yàn)閚ext)20 .串是一種特殊的線性表,其特殊性表現(xiàn)在組成串的數(shù)據(jù)元素都21 . 串的兩種最根本的存儲(chǔ)方式是和 022 .空串的長(zhǎng)度是 ;空格串的長(zhǎng)度是 .23 .需要壓縮存儲(chǔ)的矩陣可分為 矩陣和 矩陣兩種.2

25、4 .設(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)i4時(shí),A的數(shù)組元素a.相應(yīng)于數(shù)組s的數(shù)組元素的下標(biāo)為(數(shù)組元素的下標(biāo)從1開(kāi)始)28 .對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ),矩陣中每個(gè)非零元素對(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組成,試給出全部可能的輸出序列和不可能 的輸

26、出序列.(2)如果輸入序列由 A B, C, D組成,試給出全部可能的輸出序列和不 可能的輸出序列.5 .用S表示入棧操作,X表示出棧操作,假設(shè)元素入棧順序?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)算式(1) 3x2+x-1/x+5(2) (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)

27、隊(duì)列的入隊(duì)和出隊(duì)算法完整.define TRUE 1;define FALSE 0;define MAXSIZE 100;typedef charelemtype;typedef structElemtype queue MAXSIZE;int front,rear;sequeuetype;Sequeuetype Q;int encqueue(sequeuetype*Q,elemtype x)(if ( ( 1JJ(Printf( The cicular queue is full!n ); return(FALSE);)else(3) return(TRUE); /*encqueue*/ e

28、lemtype del_cqueue(sequeuetype *Q) (if ( (4)Printf( The queue is empty !n)return(NULL);)else(5) Return(Q- 淘u(píng)eueQ- front);) /*del_cqueue*/2.在下面空格處填寫(xiě)適當(dāng)?shù)恼Z(yǔ)句,以使下面的鏈?zhǔn)疥?duì)列取出元素的算法完整.int write(LinkQueue *q)QueueNode *p;if (q-front=q-rear)/* 隊(duì)空 */printf( aunderflow );exit(0);while (q-front-next != NULL)p=q-fron

29、t-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,假設(shè)6個(gè)元素出隊(duì)的序列是 e2,e4,e3,e6,e5,e1 ,那么 棧S的容量至少應(yīng)該是多少？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)

30、:從隊(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,單分支結(jié)點(diǎn)數(shù)為30,那么葉子結(jié)點(diǎn)數(shù)為().A 15 B . 16C .17 D . 472 .二叉樹(shù)第k層上最多有()個(gè)結(jié)點(diǎn).A . 2kB. 2k-1C . 2k-1D. 2k-13 .二

31、叉樹(shù)的深度為k,那么二叉樹(shù)最多有()個(gè)結(jié)點(diǎn).A 2kB. 2k-1C 2k-1D.2k-14 .設(shè)某一二叉樹(shù)先序遍歷為abdec,中序遍歷為 dbeac,那么該二叉樹(shù)后序遍歷的順序是().A . abdecB.debacC. debcaD . abedc5 .樹(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. a在b上方B. a在b下方C. a在b左方D. a在b右方7 .權(quán)值為1 ,2,6,8的四個(gè)結(jié)點(diǎn)構(gòu)成的哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度是A. 18 B .

32、 28 C . 19 D . 298 .將含有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)為 .A. 33 B . 34 C . 35 D . 369 .如果將給定的一組數(shù)據(jù)作為葉子數(shù)值,所構(gòu)造出的二叉樹(shù)的帶權(quán)路徑長(zhǎng)度最小,那么該樹(shù)稱為.A.哈夫曼樹(shù)B.平衡二叉樹(shù)C.二叉樹(shù)D.完全二叉樹(shù)10 .以下有關(guān)二叉樹(shù)的說(shuō)法正確的選項(xiàng)是.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或者為2D.二叉樹(shù)的度是211 .在一棵度為3的樹(shù)中,度

33、為3的結(jié)點(diǎn)個(gè)數(shù)為2,度為2的結(jié)點(diǎn)個(gè)數(shù)為1, 那么度為0的結(jié)點(diǎn)個(gè)數(shù)為.A 4 B . 5 C . 6 D . 712 .在一棵度具有5層的滿二叉樹(shù)中結(jié)點(diǎn)總數(shù)為.A. 31 B . 32 C . 33 D . 1613 .利用n個(gè)值作為葉結(jié)點(diǎn)的權(quán)生成的哈夫曼樹(shù)中共包含有個(gè)結(jié)點(diǎn).A. n B. n+1 C. 2*n D. 2*n-114. 利用n個(gè)值作為葉結(jié)點(diǎn)的權(quán)生成的哈夫曼樹(shù)中共包含有 個(gè)雙支結(jié)點(diǎn)0A. n B. n-1 C. n+1 D. 2*n-115. 利用3、6、8、12這四個(gè)值作為葉子結(jié)點(diǎn)的權(quán),生成一棵哈夫曼樹(shù), 該樹(shù)中所有葉子的最長(zhǎng)帶權(quán)路徑長(zhǎng)度為.A. 18 B. 16 C. 12 D

34、. 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ù)中,假設(shè)編號(hào)為i的結(jié)點(diǎn)存在右孩子,那么右孩子的順序編號(hào)為.A . 2iB. 2i-1 D . 2i+1 C . 2i+218 .設(shè)一棵哈夫曼樹(shù)共有 n個(gè)葉結(jié)點(diǎn),那么該樹(shù)有個(gè)非葉結(jié)點(diǎn).A nB n-1 C n+1 D 2n19 .設(shè)一棵有n個(gè)葉結(jié)點(diǎn)的二叉樹(shù),除葉結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)度數(shù)都為 2,那么 該樹(shù)共有()個(gè)結(jié)點(diǎn).A. 2nB. 2n-1 C . 2n+1 D . 2n+220 . 一棵完全二叉樹(shù)共有 5層,且第5層上有六個(gè)結(jié)點(diǎn),該樹(shù)共有()個(gè)結(jié)點(diǎn).A . 20B. 21 C . 2

35、3 D . 3021 .在一個(gè)圖G中,所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)之和的()倍.A . 1/2 B . 1 C . 2 D . 422 .在一個(gè)有像圖中,所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的 ()倍.A .鄰接矩陣表示法B .鄰接表表示法C.逆鄰接表表示法D .鄰接表和逆鄰接表23 .在圖的存儲(chǔ)結(jié)構(gòu)表示中,表示形式唯一的是().A . n B . n+1C . n-1D . n/224 . 一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖包含()條邊.A . n (n-1)B . n (n+1)C . n (n-1) /2 D . n (n+1)/225 . 一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖包含()條邊.A

36、. n (n-1)B . n (n+1)C . n (n-1) /2 D . n (n+1)/226 .對(duì)于具有n個(gè)頂點(diǎn)的圖,假設(shè)采用鄰接矩陣表示,那么該矩陣的大小為A . n B . n2C . n-1D . n-1 227 .對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖,假設(shè)采用鄰接表表示,那么表 頭向量的大小為.A . n B . e C . 2n D . 2e28 .對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖,假設(shè)采用鄰接表表示,那么所 有頂點(diǎn)鄰接表中的結(jié)點(diǎn)總數(shù)為.A . n B . e C . 2n D . 2e29 .在有向圖的鄰接表中,每個(gè)頂點(diǎn)鄰接表鏈接著該頂點(diǎn)所有鄰接點(diǎn).A .入邊B. 出邊

37、C.入邊和出邊D.不是入邊也不是出邊30 .在有向圖的逆鄰接表中,每個(gè)頂點(diǎn)鄰接表鏈接著該頂點(diǎn)所有鄰接點(diǎn).出邊.不是入邊也不是出邊.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu).散列存儲(chǔ)結(jié)構(gòu)A .入邊BC.入邊和出邊D31 .鄰接表是圖的一種A .順序存儲(chǔ)結(jié)構(gòu)BC.索引存儲(chǔ)結(jié)構(gòu)D32 .如果從無(wú)向圖的任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問(wèn)所有頂點(diǎn),那么該圖一定是.A .完全圖 B .連通圖 C .有回路 D . 一棵樹(shù)33 .以下有關(guān)圖遍歷的說(shuō)法不正確的選項(xiàng)是A.連通圖的深度優(yōu)先搜索是一個(gè)遞歸過(guò)程B.圖的廣度優(yōu)先搜索中鄰接點(diǎn)的尋找具有“先進(jìn)先出的特征C.非連通圖不能用深度優(yōu)先搜索法D.圖的遍歷要求每一頂點(diǎn)僅被訪問(wèn)一次34 .

38、無(wú)向圖的鄰接矩陣是一個(gè).A.對(duì)稱矩陣 B .零矩陣 C .上三角矩陣D .對(duì)角矩陣35 .圖的深度優(yōu)先遍歷算法類似于二叉樹(shù)的遍歷.A.先序 B .中序 C .后序 D .層次36 .以下圖所示的一個(gè)圖,假設(shè)從頂點(diǎn) Vi出發(fā),按深度優(yōu)先搜索法進(jìn)行遍歷,那么可能得到的一種頂點(diǎn)序列為.A . MMV4V8V3MV6V7B . VMMV5VV3VV75 .在一棵樹(shù)中,每個(gè)結(jié)點(diǎn)的 或者說(shuō)每個(gè)結(jié)點(diǎn)的稱為該結(jié)點(diǎn)的 ,簡(jiǎn)稱為孩子.6 . 一個(gè)結(jié)點(diǎn)稱為其后繼結(jié)點(diǎn)的 o7 .具有 的結(jié)點(diǎn)互稱為兄弟結(jié)點(diǎn),簡(jiǎn)稱為兄弟.8 .每個(gè)結(jié)點(diǎn)的所有子樹(shù)中的結(jié)點(diǎn)被稱為該結(jié)點(diǎn)的 .9 .從根結(jié)點(diǎn)到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)稱為該結(jié)

39、點(diǎn)的 o10 .樹(shù)的深度或高度是指 .11 . m(m0)棵互不相交的樹(shù)的集合稱為 .12 .度為k的樹(shù)中的第i層上最多有 結(jié)點(diǎn).13 .深度為k的二叉樹(shù)最多有 結(jié)點(diǎn).14 .在一棵二叉樹(shù)中,如果樹(shù)中的每一層都是滿的,那么稱此樹(shù) 為;但如果出最后一層外,其余層都是滿的,并且最后一層 是滿的,或者是在缺少假設(shè)干連續(xù)個(gè)結(jié)點(diǎn),那么稱此二叉樹(shù) 為.15 .具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度是 .16 .先序遍歷二叉樹(shù)的的操作定義為；假設(shè)二叉樹(shù)為空,那么為空操作,否那么 進(jìn)行如下操作,訪問(wèn)二叉樹(shù)的 ;先序遍歷二叉樹(shù)的 , 先序遍歷二叉樹(shù)的1 7.中序遍歷二叉樹(shù)的的操作定義為；假設(shè)二叉樹(shù)為空,那么為空操作,否

40、那么進(jìn)行如下操作,中序遍歷二叉樹(shù)的 ;訪問(wèn)而叉樹(shù)的 中序遍歷二叉樹(shù)的 18 .后序遍歷二叉樹(shù)的的操作定義為；假設(shè)二叉樹(shù)為空,那么為空操作,否那么進(jìn)行如下操作,后序遍歷二叉樹(shù)的;后序遍歷二叉樹(shù)的,訪問(wèn)而叉樹(shù)的19 .將樹(shù)中結(jié)點(diǎn)賦上一個(gè)有著某種意義的實(shí)數(shù),稱此實(shí)數(shù)為該結(jié)點(diǎn) 的.20 . 樹(shù)的帶權(quán)路徑長(zhǎng)度為樹(shù)中所有葉子結(jié)點(diǎn) 的.21 .哈夫曼樹(shù)又稱為 ,它是n個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有 二叉樹(shù)中帶權(quán)路徑長(zhǎng)度 WPL.22 .假設(shè)以4, 5, 6, 7, 8作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造哈夫曼樹(shù),那么其帶權(quán)路 徑長(zhǎng)度是.23 .具有m個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)共有 結(jié)點(diǎn).24 .在圖中,任何兩個(gè)數(shù)據(jù)元素之間都可能存在

41、關(guān)系,因此圖的數(shù)據(jù)元素之間是一種_的關(guān)系.25 .圖的鄰接矩陣表示法是用一個(gè) 來(lái)表示圖中頂點(diǎn)之間的相 鄰關(guān)系.26 .鄰接表是圖中的每個(gè)頂點(diǎn)建立一個(gè)鄰接關(guān)系的 .27 .圖的遍歷是從圖的某一頂點(diǎn)出發(fā),根據(jù)一定的搜索方法對(duì)圖中 各做一訪問(wèn)的過(guò)程.28 .圖的深度優(yōu)先搜索遍歷類似于樹(shù)的 遍歷.29 .圖的廣度優(yōu)先搜索類似于樹(shù)的 遍歷.30 .具有n個(gè)頂點(diǎn)的有向圖的鄰接矩陣,其元素個(gè)數(shù)為 .30 .具有n個(gè)頂點(diǎn)的無(wú)向圖至少有 條邊,才能保證其為一個(gè)連 通圖.31 .圖常用的兩種存儲(chǔ)結(jié)構(gòu)是 和.32 . 一個(gè)AOV網(wǎng)頂點(diǎn)活動(dòng)圖應(yīng)該是一個(gè) .即不應(yīng)該帶有 回路,否那么回路上的所有活動(dòng)都 .33 .用鄰接

42、矩陣存儲(chǔ)有向圖G,其第i行的所有元素之和等于頂點(diǎn)i的.34 .在有n個(gè)頂點(diǎn)的有向圖中,每個(gè)頂點(diǎn)的度最大可達(dá) .35 .在一個(gè)帶權(quán)圖中,兩頂點(diǎn)之間的最段路徑最多經(jīng)過(guò) 條邊.36 .為了實(shí)現(xiàn)圖的深度優(yōu)先搜索遍歷,其非遞歸的算法中需要使用的一個(gè)輔助數(shù)據(jù)結(jié)構(gòu)為.三、綜合題1 .寫(xiě)出如以下圖所示的二叉樹(shù)的先序、中序和后序遍歷序列.f2 .某二叉樹(shù)的先序和蘋(píng)果是:A,B, D, G, C, E, H, L, I , K, M, F和J,它的中序遍野璘龔：Jg、D, B, AL H, E, K, I , M C F和J,請(qǐng) 畫(huà)出這棵二叉樹(shù),并寫(xiě)bH該二叉樹(shù)卮續(xù)遍歷的結(jié)惠3 .1媒2全二般b有 892個(gè)色,廣

43、1樹(shù)的高度葉子結(jié)點(diǎn)數(shù)單支結(jié)點(diǎn)數(shù)最后一個(gè)非終端結(jié)點(diǎn)的序號(hào)4 .給出滿足以下條件的所有二叉樹(shù).(1)先序和中序相同(2)中序和后序相同(3)先序和后序相同5 .假設(shè)通信用的報(bào)文由 9個(gè)字母A、B、C D、E、F、G H和I組成,它 們出現(xiàn)的頻率分別是：10、20、5、15、8、2、3、7和30.請(qǐng)請(qǐng)用這9個(gè)字母 出現(xiàn)的頻率作為權(quán)值求：(1)設(shè)計(jì)一棵哈夫曼樹(shù)；(2)計(jì)算其帶權(quán)路徑長(zhǎng)度 WPL(3)寫(xiě)出每個(gè)字符的哈夫曼編碼.6 .請(qǐng)根據(jù)以下帶權(quán)有向圖 G(1)給出從結(jié)點(diǎn)v1出發(fā)分別按深度優(yōu)先搜索遍歷 G和廣度優(yōu)先搜索遍歷G 所得的結(jié)點(diǎn)序列；(2)給出G的一個(gè)拓?fù)湫蛄校?3)給出從結(jié)點(diǎn)v1到結(jié)點(diǎn)v8的最

44、短路徑.7 .無(wú)向圖G描述如下：G=(V, E)V=V1, V2, V3, V4, V5E= (V1, V2), (V1, V4), (V2, V4), (V3, V4) , (V2, V5), (V3, V4) , (V3,V5) (1)畫(huà)出G的圖示;(2)然后給出G的鄰接矩陣和鄰接表；(3)寫(xiě)出每個(gè)頂點(diǎn)的度.8.答復(fù)以下問(wèn)題：對(duì)于存儲(chǔ)結(jié)構(gòu)采用鄰接矩陣的無(wú)向圖,如何判斷以下有關(guān)問(wèn)題？圖中有多少條邊？任意兩頂點(diǎn)間是否有邊相連？任意一個(gè)頂點(diǎn)的度是多少？對(duì)于存儲(chǔ)結(jié)構(gòu)采用鄰接表的有向圖,如何判斷以下有關(guān)問(wèn)題？圖中有多少條邊？圖中是否存在從V到V的邊？如何求頂點(diǎn)V的入度和出度？四、程序填空題1 .下面

45、函數(shù)的功能是返回二叉樹(shù) BT中值為X的結(jié)點(diǎn)所在的層號(hào),請(qǐng)?jiān)趧澯袡M線的地方填寫(xiě)適宜內(nèi)容.int NodeLevel(struct BinTreeNode* BT, char X)(if(BT=NULL) return 0;/*空樹(shù)的層號(hào)為 0*/else if(BT-data=X) return 1; /*根結(jié)點(diǎn)的層號(hào)為 1*/* 向子樹(shù)中查找X結(jié)點(diǎn)*/else (int c1=NodeLevel(BT-left,X);if(c1=1);int c2=(2) if (3)；/假設(shè)樹(shù)中不存在 X結(jié)點(diǎn)那么返回0else return 0;)2 .下面函數(shù)的功能是根據(jù)圖的深度優(yōu)先搜索遍歷的方法,輸出得

46、到該圖的生成樹(shù)中的各條邊,請(qǐng)?jiān)趧澯袡M線的地方填寫(xiě)適宜內(nèi)容.void dfstree(adjmatrix GA, int i, int n) (int j;visitedi=1;(1) if(GAij!=0 & GAij!=MaxValue & !visitedj) (printf(%d,%d)%d,i,j,GAij);(2) 五、算法設(shè)計(jì)題1 .寫(xiě)一個(gè)將一棵二叉樹(shù)復(fù)制給另一棵二叉樹(shù)的算法.2 .根據(jù)下面函數(shù)聲明編寫(xiě)出求一棵二叉樹(shù)中葉子結(jié)點(diǎn)總數(shù)的算法,該總數(shù)值由函數(shù)返回.假定參數(shù)BT初始指向二叉樹(shù)的根結(jié)點(diǎn).int BTreeLeafCount(struct BTreeNode* BT);3 .有

47、n個(gè)頂點(diǎn)的有向圖鄰接表,設(shè)計(jì)算法分別實(shí)現(xiàn)以下功能：(1)求出圖G中每個(gè)頂點(diǎn)的出度、入度.(2)計(jì)算圖中度為0的頂點(diǎn)數(shù).六、完成：實(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)告.數(shù)據(jù)結(jié)構(gòu)(本)課程作業(yè)(4)(本局部作業(yè)覆蓋教材第8-9章的內(nèi)容)一、單項(xiàng)選擇題1 .順序查找方法適合于存儲(chǔ)結(jié)構(gòu)為()的線性表.索引存儲(chǔ)A.散列存儲(chǔ)C.散列存儲(chǔ)或索引存儲(chǔ)D.順序存儲(chǔ)或鏈接存儲(chǔ)2 .對(duì)線性表進(jìn)行二分查找時(shí),要求線性表必須.A .以順序存儲(chǔ)方式B.以鏈接存儲(chǔ)方式C .以順序存儲(chǔ)方式,且數(shù)據(jù)元素有序D.以鏈接存儲(chǔ)方式,且數(shù)據(jù)元素有序3 .如果

48、要求一個(gè)線性表既能較快地查找,又能動(dòng)態(tài)適應(yīng)變化要求,可以采用查找方法.A.順序B.分塊C.折半D.散列4 .對(duì)于一個(gè)線性表,假設(shè)要求既能進(jìn)行較快地插入和刪除,又要求存儲(chǔ)結(jié)構(gòu)能夠反映數(shù)據(jù)元素之間的邏輯關(guān)系,那么應(yīng)該.A .以順序存儲(chǔ)方式B .以鏈接存儲(chǔ)方式C.以索引存儲(chǔ)方式D .以散列存儲(chǔ)方式5 .采用順序查找方法查找長(zhǎng)度為n的線性表時(shí),每個(gè)元素的平均查找長(zhǎng)度為.A. nB. n/2C. n+1/2 D. n-1/26 .采用折半查找方法查找長(zhǎng)度為n的線性表時(shí),每個(gè)元素的平均查找長(zhǎng)度為.A. On*nB. Onlog 2nC. O(n)s(log 2n)取其值域的每個(gè)7 .哈希函數(shù)有一個(gè)共同的性

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

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

51、素 26的比擬次數(shù)是.A.3 B. 3 C. 4D.514 .關(guān)于哈希查找的說(shuō)法正確的選項(xiàng)是.A.除留余數(shù)法是最好的B.哈希函數(shù)的好壞要根據(jù)具體情況而定C.刪除一個(gè)元素后,不管用哪種方法處理沖突,都只需簡(jiǎn)單地把該元素刪除掉D.由于沖突是不可防止的,所以裝填因子越小越好15 .在所有的排序方法中,關(guān)鍵字比擬的次數(shù)與記錄初始排列秩序無(wú)關(guān)的是 .A.冒泡排序B. 希爾排序 C. 直接選擇排序 D.直接插入排序16 .從未排序序列中依次取出元素與已經(jīng)排好序的序列中的元素作比擬.將其放入已排序序列的正確的位置上,此方法稱為A.插入排序B. 選擇排序 C.交換排序D. 歸并排序17 .從未排序序列中挑選元素