1、形考作業(yè)一題目1把數(shù)據(jù)存儲(chǔ)到運(yùn)算機(jī)中，并具體表現(xiàn)數(shù)據(jù)元素間的邏輯結(jié)構(gòu)稱(chēng)為（）°選擇一項(xiàng)：C A.邏輯結(jié)構(gòu)C B.給相關(guān)變量分派存儲(chǔ)單元C C.算法的具體實(shí)現(xiàn)” D.物理結(jié)構(gòu)題目2以下說(shuō)法中，不正確的選項(xiàng)是（）0選擇一項(xiàng)：廠A.數(shù)據(jù)可有假設(shè)干個(gè)數(shù)據(jù)元素組成C B.數(shù)據(jù)元素是數(shù)據(jù)的大體單位C C.數(shù)據(jù)項(xiàng)是數(shù)據(jù)中不可分割的最小可標(biāo)識(shí)單位Q D.數(shù)據(jù)項(xiàng)可由假設(shè)干個(gè)數(shù)據(jù)元素組成題目3一個(gè)存儲(chǔ)結(jié)點(diǎn)存儲(chǔ)一個(gè)（）。選擇一項(xiàng)：廠A.數(shù)據(jù)結(jié)構(gòu)C B.數(shù)據(jù)類(lèi)型C C.數(shù)據(jù)項(xiàng)Q D.數(shù)據(jù)元素題目4數(shù)據(jù)結(jié)構(gòu)中，與所利用的運(yùn)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的（）。選擇一項(xiàng)：C A.物理結(jié)構(gòu)“ B.邏輯結(jié)構(gòu)C C.物理和存儲(chǔ)結(jié)構(gòu)

2、D.存儲(chǔ)結(jié)構(gòu)題目5以下的表達(dá)中，不屬于算法特性的是（）。選擇一項(xiàng)：C A有窮性B. 可行性C. 可讀性D. 輸入性題目6正確取得分中的分' A.研究算法中的輸入和輸出的關(guān)系C B.分析算法的易懂性和文檔性介C.分析算法的效率以求改良D.找出數(shù)據(jù)結(jié)構(gòu)的合理性題目7算法指的是（）。選擇一項(xiàng)：A.排序方式C B.解決問(wèn)題的計(jì)算方式C C.運(yùn)算機(jī)程序“ D.解決問(wèn)題的有限運(yùn)算序列題目8算法的時(shí)刻復(fù)雜度與（）有關(guān)。選擇一項(xiàng)：C A.所利用的運(yùn)算機(jī)C B.數(shù)據(jù)結(jié)構(gòu)3 C.算法本身D.運(yùn)算機(jī)的操作系統(tǒng)題冃9設(shè)有一個(gè)長(zhǎng)度為n的順序表，要在第i個(gè)元素之前（也確實(shí)是插入元素作為新表的第i個(gè) 元素），插入一

3、個(gè)元素，那么移動(dòng)元素個(gè)數(shù)為（）。選擇一項(xiàng)："A. n-i+1C B. n-i-1C C. n-iD. i題目10設(shè)有一個(gè)長(zhǎng)度為n的順序表，要?jiǎng)h除第i個(gè)元素移動(dòng)元素的個(gè)數(shù)為（）。選擇一項(xiàng):C C. n-i+1D. i題目11).選擇一項(xiàng):在一個(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. q->next=NULLCD. p->next=q題目12在一個(gè)單鏈表中P所指結(jié)點(diǎn)以后插入一個(gè)s所指的結(jié)點(diǎn)時(shí)，可執(zhí)行（）選擇一項(xiàng)：A. p=s->nextCB. p->next= s; s->next

4、= p->next CC. p->next=s->next;D. s->next=p->next: p->next=s;題目13非空的單向循環(huán)鏈表的尾結(jié)點(diǎn)知足（）（設(shè)頭指針為head,指針p指向尾結(jié)點(diǎn)）。選擇一項(xiàng)：A. p= head B. p=NULLC. p->next=head D. p->next=NULL題目14）。選擇一項(xiàng):C C 沒(méi)必要事前估量存儲(chǔ)空間C D.所需空間與線性表長(zhǎng)度成正比鏈表不具有的特點(diǎn)是（題目15帶頭結(jié)點(diǎn)的鏈表為空的判左條件是（）（設(shè)頭指針為head）.選擇一項(xiàng)：A. head->next=NULLB. hea

5、d->next=headC. head =NULLD. head!=NULL題目16在一個(gè)長(zhǎng)度為n的順序表中為了刪除第5個(gè)元素，由第6個(gè)元素開(kāi)始從后到前依次移動(dòng)了 15個(gè)元素。那么原順序表的長(zhǎng)度為（）。選擇一項(xiàng)：A. 21B. 19C. 20D. 25題目17有關(guān)線性表的正確說(shuō)法是（）。選擇一項(xiàng)：A. 表中的元素必需按由小到大或由大到下排序B. 除一個(gè)和最后一個(gè)元素外，其余元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼C. 線性表至少要求一個(gè)元素D. 每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼題目18向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素，并維持原先的順序不變，平均要移動(dòng) （）個(gè)元素。

6、選擇一項(xiàng)：A. 8B. 7C. 63D.題目19一個(gè)順序表第一個(gè)元素的存儲(chǔ)地址是90,每一個(gè)元素的長(zhǎng)度為2,那么第6個(gè)元素的地址 是（）°選擇一項(xiàng)：A. 102B. 98C. 100D. 106題目20在雙向循環(huán)鏈表中，在P所指的結(jié)點(diǎn)以后插入指針f所指的新結(jié)點(diǎn)，其操作步驟是( ).選擇一項(xiàng)：A. f->prior=p; f->next=p->next; p->next=f;p->next->prior=f;B. p->next=f;f->prior=p;p->next->prior=f;f->next=p->ne

7、xt;C. f->prior=p; f->next=p->next; p->next->prior=f; p->next=f;D. p->next=f; p->next->prior=f;f->prior=p;f->next=p->next;二、填空題(每題2分，共30分題目21在一個(gè)長(zhǎng)度為n的順序存儲(chǔ)結(jié)構(gòu)的線性表中，向第i (l£i£n+l)個(gè)元素之前插入新元素時(shí), 需向后移動(dòng)回答個(gè)數(shù)據(jù)元素。題目22從長(zhǎng)度為n的釆納順序存儲(chǔ)結(jié)構(gòu)的線性表中刪除第i (l£i£n+l)個(gè)元素，需向前移

8、動(dòng)回答I個(gè)元素。題目23數(shù)據(jù)結(jié)構(gòu)按結(jié)點(diǎn)間的關(guān)系，可分為4種邏輯結(jié)構(gòu)：集合、線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)、圖狀結(jié)構(gòu)。題目24數(shù)據(jù)的邏輯結(jié)構(gòu)在運(yùn)算機(jī)中的表示稱(chēng)為存儲(chǔ)結(jié)構(gòu)或物理結(jié)構(gòu)題目25除第1個(gè)和最后一個(gè)結(jié)點(diǎn)外,其余結(jié)點(diǎn)有且只有一個(gè)前驅(qū)結(jié)點(diǎn)和后繼年點(diǎn)的數(shù)據(jù)結(jié)構(gòu)為回 答pw麗，每一個(gè)結(jié)點(diǎn)可有任意多個(gè)前驅(qū)和后繼結(jié)點(diǎn)數(shù)的結(jié)構(gòu)為回答而1O答案：線性結(jié)構(gòu)，非線性結(jié)構(gòu)題目26數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在多對(duì)多的關(guān)系稱(chēng)為回答結(jié)構(gòu)。題目27結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)多的關(guān)系稱(chēng)為回答I樹(shù)懊線性結(jié)構(gòu)題目28結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)一的關(guān)系稱(chēng)為回答I題目29要求在n個(gè)數(shù)據(jù)元素中找其中值最大的元素，設(shè)大體操作為元素間

9、的比較。那么比較的次 數(shù)和算法的時(shí)刻復(fù)雜度別離為_(kāi) n-1和_ 0(n)o題目30在一個(gè)單鏈表中P所指結(jié)點(diǎn)以后插入一個(gè)S所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行回答s-/,ne>:t=p->next:和p->next=s;的操作o題目31設(shè)有一個(gè)頭指針為head的單向循環(huán)鏈表，p指向鏈表中的結(jié)點(diǎn)，假設(shè)p->next=回答I,那么P所指結(jié)點(diǎn)為尾結(jié)點(diǎn)。題目32在一個(gè)單向鏈表中，要?jiǎng)h除P所指結(jié)點(diǎn)，已知q指向P所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。那么能夠用正確答案是:q->next=p->next;題目33設(shè)有一個(gè)頭指針為head的單向鏈表，p指向表中某一個(gè)結(jié)點(diǎn)，且有p->next=二NULL,通

10、過(guò)操作回答，就可使該單向鏈表構(gòu)形成單向循環(huán)鏈表。正確答案是:p->next=head;題目34單向循環(huán)鏈表是單向鏈表的一種擴(kuò)充,當(dāng)單向鏈表帶有頭結(jié)點(diǎn)時(shí)，把單向鏈表中尾結(jié)點(diǎn)的 指針域由空指針改成回答：當(dāng)單向鏈表不帶頭結(jié)點(diǎn)時(shí)，那么把單向鏈表中尾結(jié)點(diǎn)的指針域由空指針改成指向回答。答案：頭結(jié)點(diǎn)的指針、指向第一個(gè)結(jié)點(diǎn)的指針題目35線性鏈表的邏借關(guān)系是通過(guò)每一個(gè)結(jié)點(diǎn)指針域中的指針來(lái)表示的。其邏輯順序和物理存儲(chǔ)順序再也不一致，而是一種回答I存儲(chǔ)結(jié)構(gòu)，又稱(chēng)為回答I。答案：鏈?zhǔn)健㈡湵砣?、?wèn)答題(第1小題7分，第2小題8分)題目36簡(jiǎn)述數(shù)據(jù)的邏借結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)的區(qū)別與聯(lián)系，它們?nèi)绾巫璧K算法的設(shè)訃與實(shí)現(xiàn)？ 答

11、：假設(shè)用結(jié)點(diǎn)表示某個(gè)數(shù)拯元素，那么結(jié)點(diǎn)與結(jié)點(diǎn)之間的邏借關(guān)系就稱(chēng)為數(shù)據(jù)的邏輯結(jié) 構(gòu)。數(shù)據(jù)在運(yùn)算機(jī)中的存儲(chǔ)表示稱(chēng)為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)Q可見(jiàn)，數(shù)據(jù)的邏輯結(jié)構(gòu)是反映數(shù)據(jù) 之間的固有關(guān)系，而數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)在運(yùn)算機(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ù)雜度等方而不同較大。題目37說(shuō)明順序存儲(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)

12、存中存儲(chǔ)單元的地址必需是持續(xù)的。優(yōu)勢(shì)：一樣情形下，存儲(chǔ)密度大，存儲(chǔ)空間利用率高。缺點(diǎn)：（1）在做插入和刪除操作時(shí)，需移動(dòng)大量元素；（2）由于無(wú)法計(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)勢(shì)：插入和刪除元素時(shí)很方便，利用靈活。缺點(diǎn)：存儲(chǔ)密度小，存儲(chǔ)空間利用率低。四、程序填空題（每空1分，共15分）題目38以下是用尾插法成立帶頭結(jié)點(diǎn)的且有n個(gè)結(jié)點(diǎn)的單向鏈表的算法，請(qǐng)?jiān)诳崭駜?nèi)填上適當(dāng)?shù)?語(yǔ)句。NODE *createl（n）/*對(duì)線性表（1

13、,2?。?，成立帶頭結(jié)點(diǎn)的單向鏈表/NODE *head, *p, *q;int i;p=(NODE *)malloc(sizeof(NODE); head=p; q=p; p_>next二NULL;for(i=l;i<=n;i+)p=(NODE *)malloc(sizeof(NODE);回答Ip_>data=i回答I q'>next=p回答IKreturn(head);題目39以下是用頭插法成立帶頭結(jié)點(diǎn)的且有n個(gè)結(jié)點(diǎn)的單向鏈表的算法，請(qǐng)?jiān)诳崭駜?nèi)填上適當(dāng)?shù)?語(yǔ)句。NODE *create2(n)/*對(duì)線性表(n, n-1 1),成立帶頭結(jié)點(diǎn)的線性鏈表*/NODE

14、 *head, *p, *q;int i;p=(NODE *)malloc(sizeof(NODE);回答IKp->next=NULL;回答I q=Pfor(i=l;i<=n;i+)p=(NODE *)malloc(sizeof(NODE);p->data=i;辻(i=l)回答I p->next=XULLelse回答 Ireturn(head);題目40以下是在具有頭結(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

15、)&&(j<i-1)/*找到要?jiǎng)h除結(jié)點(diǎn)的直接前驅(qū)，并使q指向它*/回答Iq=q_>nextif(q二二NULL) return(0);回答帀E回答 | q->next=p->nextfree(p);return (1);題目41以下是在具有頭結(jié)點(diǎn)單向列表中在第i個(gè)結(jié)點(diǎn)之前插入新結(jié)點(diǎn)的算法，請(qǐng)?jiān)诳崭駜?nèi)填上適 當(dāng)?shù)恼Z(yǔ)句。int insert(NODE *head,int x, int i)NODE *q,*p;int j；q二head;j 二0；wh訂e(q!=NULL)&&(j<i-l)q=q->next: j 卄；if(q=N

16、ULL) return(0);-回姣p->data=x;回答Ip">next=q->ne>:t題目4正確正確答案是：p->next=q->next 取得分中的分回答Iq_>next=preturn （1）;形考任務(wù)2題目1假設(shè)讓元素1, 2, 3依次進(jìn)棧，那么出棧順序不可能為（）。選擇一項(xiàng)：A. 2, b 3B. 3, L 2C. 3, 2, 1題目2一個(gè)隊(duì)列的入隊(duì)序列是1, 2, 3, 4。那么隊(duì)列的輸出序列是（）。選擇一項(xiàng)：A. 3, 2, 4, 1B. h 2, 3, 4C. 4, 3, 2, 1D. L 4, 3, 2題目3向順序棧中

17、壓入新元素時(shí)，應(yīng)當(dāng)（）。選擇一項(xiàng)：A. 先存入元素，再移動(dòng)棧頂指針B. 先移動(dòng)棧頂指針，再存入元素C. 前后順序無(wú)關(guān)緊要D. 同時(shí)進(jìn)行在一個(gè)棧頂指針為top的鏈棧中，將一個(gè)P指針?biāo)傅慕Y(jié)點(diǎn)入棧，應(yīng)執(zhí)行（）。選擇一項(xiàng):rC. p->next=top->next;top=top->next; rD. p->next=top->next;top->next=p;(5-題目9題目5在一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用X保留被刪結(jié)點(diǎn)的值，那么執(zhí)行 （ ）.選擇一項(xiàng)："A. x=top->data;top=top->next:rB. x

18、=top->data;rC. top=top->next;x=top->data; rD. x=top;top=top->next;題目6判立一個(gè)順序隊(duì)列（最多元素為m）為空的條件是（選擇一項(xiàng)：A. rear=m-l rB. front=rear+l（iC. front=rear題目7)0選擇一項(xiàng):判左一個(gè)循環(huán)隊(duì)列Q （最多元素為m）為滿的條件是（C. Q->front=（Q->rear+1 ）%mD. Q->front=Q->rear +1題目8判定棧滿（元素個(gè)數(shù)最多n個(gè)）的條件是（選擇一項(xiàng): rA. top=0B. top!=0C. top=

19、-lD. top=n-l設(shè)有一個(gè)20階的對(duì)稱(chēng)矩陣A （第一個(gè)元素為芯,），采納緊縮存儲(chǔ)的方式，將其下三角部 份以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始），那么矩陣元素弘二在一維數(shù) 組B中的下標(biāo)是（）。選擇一項(xiàng):C. 21D. 28題目10在解決運(yùn)算機(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)。選擇一項(xiàng)：C. 數(shù)組D. 堆棧題目11一個(gè)遞歸算法必需包括（）O選擇一項(xiàng)：A. 遞歸部份B. 迭代部份C. 終止條件和迭代部份D. 終止條件和遞歸部份題目12在一個(gè)鏈隊(duì)中，假設(shè)f

20、和r別離為隊(duì)頭和隊(duì)尾指針，那么刪除一個(gè)結(jié)點(diǎn)的運(yùn)算為（）。選擇一項(xiàng)：A. f=r->next;B. r=r->next;C. r=f->next;D. f=f->next;題目13在一個(gè)鏈隊(duì)中，假設(shè)f和r別離為隊(duì)頭和隊(duì)尾指針，那么插入s所指結(jié)點(diǎn)的運(yùn)算為（ ）。選擇一項(xiàng):A. s->next=r;r=s;B. r->next=s;r=s;C. s«>next=f;f=s;D. f->ncxt=s;f=s;題目14數(shù)組3經(jīng)初始化char a = “English” ;a7中寄存的是（）°選擇一項(xiàng)：A. HhMB. 字符串的終止符C.

21、 變量hD. 字符h題目15設(shè)主串為“ABcCDABcdEFaBc” ,以下模式串能與主串成功匹配的是（）。選擇一項(xiàng)：A. BCdB. BcdC. AbeD. ABC題目16字符串 al='AEIJING a2=/zAEI a3="AEFANG", a4AEFI"中最大的是（）。選擇一項(xiàng)：A. a3B. alC. a4D. a2題目17兩個(gè)字符串相等的條件是（）。選擇一項(xiàng)：A. 兩串的長(zhǎng)度相等，而且對(duì)應(yīng)位置上的字符相同B. 兩串的長(zhǎng)度相等C. 兩串的長(zhǎng)度相等，而且兩串包括的字符相同D. 兩串包括的字符相同一維數(shù)組A采納順序存儲(chǔ)結(jié)構(gòu)，每一個(gè)元素占用6個(gè)字節(jié)，

22、第6個(gè)元素的存儲(chǔ)地址為100, 那么該數(shù)組的首地址是()oC. 28選擇一項(xiàng)：A. 64B. 90D. 70題目19一個(gè)非空廣義表的表頭()。選擇一項(xiàng)：A.能夠是子表或原子cB 只能是原子c c.不可能是原子C D只能是子表CCC題目20對(duì)稀疏矩陣進(jìn)行緊縮存儲(chǔ)，可采納三元組表，一個(gè)10行8列的稀疏矩陣A,其相應(yīng)的三元 組表共有6個(gè)元素，矩陣A共有()個(gè)零元素。選擇一項(xiàng)：A. 8B. 10C. 72(5-D. 74題目21對(duì)稀疏矩陣進(jìn)行緊縮存儲(chǔ)，可釆納三元組表，一個(gè)10行8列的稀疏矩陣A共有73個(gè)零元 素，A的右下角元素為6,其相應(yīng)的三元組表中的第7個(gè)元素是()。選擇一項(xiàng)：A. (10, 8,

23、7)B. (10, 8, 6)C. (7, 10, 8)D. (7, 8, 10)題目22對(duì)一個(gè)棧頂指針為top的鏈棧進(jìn)行入棧操作，通過(guò)指針變量p生成入棧結(jié)點(diǎn)，并給該結(jié)點(diǎn)賦值 a,那么執(zhí)行：p= (struct node *)malloc(sizeof (struct node) :p->data=a;和()。選擇一項(xiàng):A. p->next=top;p=top;B. top->next=p;p=top;C. p->nex=top;top=p;D. top=top->next:pe=top;C(5-題目23頭指針為h“d的帶頭結(jié)點(diǎn)的單向鏈表為空的判泄條件是（）為真。

24、選擇一項(xiàng)：A. head=NULLB. head->next=NULLC. head->next!=NULLD. head->next!=NULL題目24設(shè)有一個(gè)對(duì)稱(chēng)矩陣A,采納緊縮存儲(chǔ)的方式，將其下三角部份以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù) 組B中（數(shù)組下標(biāo)從1開(kāi)始），B數(shù)組共有55個(gè)元素，那么該矩陣是（）階的對(duì)稱(chēng)矩陣。選擇一項(xiàng)：A. 20B. 15C. 10D. 5題目25數(shù)組a經(jīng)初始化char a = “English” ;al中寄存的是（）°選擇一項(xiàng)：A. HnMB. 字符nC. MEMD. 字符E二、填空題（每題2分，共30分）題目26循環(huán)隊(duì)列隊(duì)頭指針在隊(duì)尾指針回答

25、位豊，隊(duì)列是“滿”狀態(tài)。題目27循環(huán)隊(duì)列的引入，目的是為了克服回答。判泄一個(gè)循環(huán)隊(duì)列LU （最多元素為m）為空的條件是回答I LU_ frOnt=LU_>rear 。題目29題干向一個(gè)棧頂指針為h的鏈棧中插入一個(gè)S所指結(jié)點(diǎn)時(shí)，可執(zhí)行回答s->next=h;和h二S；操作。 （結(jié)點(diǎn)的指針域?yàn)閚ext）題目30從一個(gè)棧頂指針為h的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用X保留被刪結(jié)點(diǎn)的值，可執(zhí)行X二h-題目31在一個(gè)鏈隊(duì)中，設(shè)f和r別離為隊(duì)頭和隊(duì)尾指針，那么插入s所指結(jié)點(diǎn)的操作為回答和 r=s; r->next=s;（結(jié)點(diǎn)的指針域?yàn)閚ext）題目32在一個(gè)鏈隊(duì)中，設(shè)f和:r別藹為隊(duì)頭和隊(duì)尾指針，

26、那么刪除一個(gè)結(jié)點(diǎn)的操作為回答f二& >next；o（結(jié)點(diǎn)的指針域?yàn)閚ext）題目33串是一種特殊的線性表，其特殊性表此刻組成串的數(shù)據(jù)元素都是回答rw題目34:空格串的長(zhǎng)度是回答空格字禰題目35設(shè)廣義表L二（），（），那么表頭是,表尾是, L的長(zhǎng)度是那么表頭是（），表尾是（），L的長(zhǎng)度是Z題目36廣義表A （ （a> b, c） ,（d, e, f）的表尾為回答（def）。題目37設(shè)有n階對(duì)稱(chēng)矩陣A,用數(shù)組s進(jìn)行緊縮存儲(chǔ)，當(dāng)j時(shí)，A的數(shù)組元素a,相應(yīng)于數(shù)組s的數(shù)組元素的下標(biāo)為回答I譏卜1）衛(wèi)幻 。（數(shù)組元素的下標(biāo)從1開(kāi)始）題目38對(duì)稀疏矩陣進(jìn)行緊縮存儲(chǔ)，矩陣中每一個(gè)非零元素對(duì)

27、應(yīng)的三元組包括該元素的、和三項(xiàng)信息。答案：行下標(biāo)、列下標(biāo)和非零元素值題目39循環(huán)隊(duì)列用a0,，乳7的一維數(shù)組寄存隊(duì)列元素，（采納少用一個(gè)元素的模式），設(shè)front和rear別離為隊(duì)頭和隊(duì)尾指針，且front和rear的值別離為2和7,當(dāng)前隊(duì)列中的元素個(gè)數(shù)是回答5。題目40循環(huán)隊(duì)列的引入，目的是為了克服回答。三、問(wèn)答題（每題5分，共20分）題目41完成總分值題干棧、隊(duì)列和線性表的區(qū)別是什么？答：棧是一種先進(jìn)后岀的線性表，棧的插入和刪除操作都只能在棧頂進(jìn)行，而一樣的線性 表能夠在線性表的任何位置進(jìn)行插入和刪除操作。隊(duì)列是一種先進(jìn)先出的線性表，隊(duì)列的插入只能在隊(duì)尾進(jìn)行，隊(duì)列的刪除只能在隊(duì)頭進(jìn)行, 而

28、一樣的線性表能夠在線性表的任何位置進(jìn)行插入和刪除操作。題目42設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素el, e2, e3, e4, e5和e6依次通過(guò)S, 個(gè)元素 出棧后即進(jìn)隊(duì)列Q,假設(shè)6個(gè)元素出隊(duì)的序列是e2, e4, e3, e6, e5, eb那么棧S的容 量至少應(yīng)該是多少？出隊(duì)序列是e2, e4, e3, e6, e5, el的進(jìn)程：(1)(2)el入棧e2入棧（棧底到棧頂元素是el ）（棧底到棧頂元素是el,e2)(3)(4)e2出棧e3入棧（棧底到棧頂元素是el）（棧底到棧頂元素是el,e3)(5)e4入棧e4出棧e3出棧（棧底到棧頂元素是el,（棧底到棧頂元素是el,（棧底到棧頂元素

29、是el ）e3, e4)e3)(8)(9)e5入棧e6入棧（棧底到棧頂元素是el,（棧底到棧頂元素是el.e5)e5, e6)（10）e6出棧（棧底到棧頂元素是el, e5）（11）e5出棧（棧底到棧頂元素是el）（12）el出棧（棧底到棧頂元素是空）棧中最多時(shí)有3個(gè)元素，因此棧S的容量至少是3。題目43有5個(gè)元素，英入棧順序?yàn)椋篈. B、C、D、E,在各類(lèi)可能的出棧順序中，以元素C、D最 先的順序有哪幾個(gè)？從題中可知，要使C第一個(gè)且D第二個(gè)出棧，應(yīng)是A入棧，B入棧，C入棧，C出棧，D入 棧。以后能夠有以下幾種情形：(1) B出棧，A出棧，E入棧，E出棧，輸岀序列為：CDBAE。(2) B出棧

30、，E入棧，E出棧，A岀棧，輸出序列為CDBEA.(3) E入棧，E出棧，B出棧，A出棧，輸岀序列為CDEBA因此可能的順序有：CDBAE, CDBEA, CDEBA題目44簡(jiǎn)述廣義表和線性表的區(qū)別和聯(lián)系。廣義表是線性表的的推行，它也是n (n>0)個(gè)元素加，比，“ /,，比的有限序列，其 中直或是原子或是一個(gè)廣義表。因此，廣義表是一種遞歸數(shù)據(jù)結(jié)構(gòu)，而線性表沒(méi)有這種特 性，線性表能夠看成廣義表的特殊情形，當(dāng)加都是原子時(shí)，廣義表退化成線性表。形考任務(wù)三一、單項(xiàng)選擇題(每題2分，共32分)題目1假泄一棵二叉樹(shù)中，雙分支結(jié)點(diǎn)數(shù)為15,單分支結(jié)點(diǎn)數(shù)為30,那么葉子結(jié)點(diǎn)數(shù)為( )。選擇一項(xiàng)：A. 1

31、7B. 16C. 15D. 47題目2二叉樹(shù)第k層上最多有()個(gè)結(jié)點(diǎn)。選擇一項(xiàng)：C. 2k-ID. 2k題目3設(shè)某一二叉樹(shù)先序遍歷為abdec,中序遍歷為dbeac,那么該二叉樹(shù)后序遍歷的順序是 ( ).選擇一項(xiàng):A. abedcB. abdecC. debacD. debca題目4將含有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)為（）。選擇一項(xiàng)：A. 35B. 33C. 34D. 36題目5若是將給左的一組數(shù)據(jù)作為葉子數(shù)值，所構(gòu)造岀的二叉樹(shù)的帶權(quán)途徑長(zhǎng)度最小，那么該樹(shù) 稱(chēng)為（）。選擇一項(xiàng)：A. 平穩(wěn)二叉樹(shù)

32、B. 完全二叉樹(shù)C. 二叉樹(shù)D. 哈夫曼樹(shù)題目6在一棵度為3的樹(shù)中，度為3的結(jié)點(diǎn)個(gè)數(shù)為2,度為2的結(jié)點(diǎn)個(gè)數(shù)為1,那么度為0的結(jié)點(diǎn) 個(gè)數(shù)為（）。選擇一項(xiàng)：A. 5B. 4C. 7D. 6題目7在一棵度具有5層的滿二叉樹(shù)中結(jié)點(diǎn)總數(shù)為（）。選擇一項(xiàng)：A. 31B. 32C. 16D. 33題目8利用n個(gè)值作為葉結(jié)點(diǎn)的權(quán)生成的哈夫曼樹(shù)中共包括有（）個(gè)結(jié)點(diǎn)。選擇一項(xiàng)：A. n+1B. 2*nC. nD. 2*n-l題目9利用3、六、八、12這四個(gè)值作為葉子結(jié)點(diǎn)的權(quán)，生成一棵哈夫曼樹(shù)，該樹(shù)中所有葉子結(jié) 點(diǎn)中的最長(zhǎng)帶權(quán)途徑長(zhǎng)度為（）。選擇一項(xiàng)：A. 16B. 30C. 12D. 18題目10在一棵樹(shù)中，（）

33、沒(méi)有前驅(qū)結(jié)點(diǎn)。選擇一項(xiàng)：A. 葉結(jié)點(diǎn)B. 空結(jié)點(diǎn)C. 樹(shù)根結(jié)點(diǎn)D. 分支結(jié)點(diǎn)題目11設(shè)一棵有n個(gè)葉結(jié)點(diǎn)的二叉樹(shù)，除葉結(jié)點(diǎn)外每一個(gè)結(jié)點(diǎn)度數(shù)都為2,那么該樹(shù)共有（）個(gè)結(jié)點(diǎn)。選擇一項(xiàng)：A. 2n-lB. 2n+2C. 2n+lD. 2n題目12在一個(gè)圖G中，所有極點(diǎn)的度數(shù)之和等于所有邊數(shù)之和的（）倍。選擇一項(xiàng)：A. 1B. 1/2C. 2C D.4題目13鄰接表是圖的一種（）。選擇一項(xiàng)：C A.索引存儲(chǔ)結(jié)構(gòu)C B.順序存儲(chǔ)結(jié)構(gòu)C C.散列存儲(chǔ)結(jié)構(gòu)® D.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)題目14若是從無(wú)向圖的任一極點(diǎn)動(dòng)身進(jìn)行一次深度優(yōu)先搜索即可訪問(wèn)所有極點(diǎn)，那么該圖必然是 （ ）。選擇一項(xiàng)： C A.棵樹(shù) B.

34、有回路 C C.完全圖Q D.連通圖題目15圖的深度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的（）遍歷。選擇一項(xiàng)：C. 中序D. 后序題目16已知以下圖所示的一個(gè)圖，假設(shè)從極點(diǎn)V；動(dòng)身，按深度優(yōu)先搜索法進(jìn)行遍歷，那么可能取 得的一種極點(diǎn)序列為（）。選擇一項(xiàng)：A. V1V2V4V5VMV6V7B. VIV2V4V8V5V3V6V7C. V1V2VMV3V5V6V7D. V1V3V6V7V2V4V5V8二、填空題（每題1分，共20分）題目17結(jié)點(diǎn)的度是指結(jié)點(diǎn)所擁有的回答|子樹(shù)樹(shù)木或后繼録。正確答案是：子樹(shù)樹(shù)木或后繼結(jié)點(diǎn)數(shù)題目18樹(shù)的度是指回正確答案是：樹(shù)中所有結(jié)點(diǎn)的度的最大值題目19度大于0的結(jié)點(diǎn)稱(chēng)作或O分支結(jié)點(diǎn)

35、、非終端結(jié)點(diǎn)鹿目20度等于0的結(jié)點(diǎn)稱(chēng)作或O葉子結(jié)點(diǎn)、終端結(jié)點(diǎn)題目21在一棵樹(shù)中，每一個(gè)結(jié)點(diǎn)的或說(shuō)每一個(gè)結(jié)點(diǎn)的稱(chēng)為該結(jié)點(diǎn)的,簡(jiǎn)稱(chēng)為小孩。子樹(shù)的根、后繼結(jié)點(diǎn)、小孩結(jié)點(diǎn)題目22從根結(jié)點(diǎn)到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)稱(chēng)為該結(jié)點(diǎn)的回答I川尢正確答案是：先人題目23正確答案是：樹(shù)中結(jié)點(diǎn)的最大層數(shù)題目24具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度是題目25先序遍歷二叉樹(shù)的的操作概念為：假設(shè)二叉樹(shù)為空，那么為空操作，不然進(jìn)行如卜操作, 訪問(wèn)二叉樹(shù)的回答I用絡(luò)用:先序遍歷二叉樹(shù)的回答I左子",先序遍歷二叉樹(shù)的回答O根結(jié)點(diǎn)、左子樹(shù)、右子樹(shù)題目26中序遍歷二叉樹(shù)的的操作概念為：假設(shè)二叉樹(shù)為空，那么為空操作，不然進(jìn)行如卜

36、操作,:訪問(wèn)而叉樹(shù)的回答根乘,中序遍歷二叉樹(shù)的回答I左子樹(shù)、根結(jié)點(diǎn)、右子樹(shù)題目27后序遍歷二叉樹(shù)的的操作概念為：假設(shè)二叉樹(shù)為空，那么為空操作，不然進(jìn)行如下操作, 后序遍歷二叉樹(shù)的回答I左辦；后序遍歷二叉樹(shù)的回答I右子",訪問(wèn)而叉樹(shù)的回答簡(jiǎn)左子樹(shù)、右子樹(shù)、根結(jié)點(diǎn)題目28將樹(shù)中結(jié)點(diǎn)賦上一個(gè)有著某種意義的實(shí)數(shù)，稱(chēng)此實(shí)數(shù)為該結(jié)點(diǎn)的回答卩O正確答案是：權(quán)題目29樹(shù)的帶權(quán)途徑長(zhǎng)度為樹(shù)中所有葉子結(jié)點(diǎn)的回正確答案是：帶權(quán)途徑長(zhǎng)度之和題目30哈夫曼樹(shù)又稱(chēng)為回答I最優(yōu)二叉，它是n個(gè)帶權(quán)葉子結(jié)點(diǎn)組成的所有二叉樹(shù)中帶權(quán)途徑長(zhǎng)度WPL回答I最小的二答案：最優(yōu)二叉樹(shù)，最小的二叉樹(shù)題目31假設(shè)以4, 5, 6,

37、7, 8作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造哈夫曼樹(shù)，那么其帶權(quán)途徑長(zhǎng)度是回答69正確答案是：69題目32具有m個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)共有回答I 231_1結(jié)點(diǎn)。正確答案是：2m-1題目33圖的遍歷是從圖的某一極點(diǎn)動(dòng)身，依照必然的搜索方式對(duì)圖中回答I聽(tīng)熱各做回答I i次訪問(wèn)的進(jìn)程。答案：所有極點(diǎn)；一次題目34圖的深度優(yōu)先搜索遍歷類(lèi)似于樹(shù)的回答遍歷。正確答案是：先序題目35圖的廣度優(yōu)先搜索類(lèi)似于樹(shù)的回答遍歷。正確答案是：按層次題目36圖經(jīng)常使用的兩種存儲(chǔ)結(jié)構(gòu)是和o鄰接矩陣、鄰接表三. 綜合題（每題8分,共40分）題目37寫(xiě)出如以下圖所示的二叉樹(shù)的先序、中序和后序遍歷序列。答：二叉樹(shù)的概念是遞歸的，因此，一棵二叉

38、樹(shù)可看做由根結(jié)點(diǎn)，左子樹(shù)和右子樹(shù)這三個(gè) 大體部份組成，即依次遍歷整個(gè)二叉樹(shù)，又左子樹(shù)或右子樹(shù)又可看做一棵二叉樹(shù)并繼續(xù)分 為根結(jié)點(diǎn)、左子樹(shù)和右子樹(shù)三個(gè)部份,如此劃分一直進(jìn)行到樹(shù)葉結(jié)點(diǎn)。（1）先序?yàn)椤案笥摇?，先序序列為：fdbacegihl（2）中序?yàn)椤白蟾摇?，中序序列為：abcdefghij（3）后序?yàn)椤白笥腋?后序序列為：acbedhjigf題目38已知某二叉樹(shù)的先序遍歷結(jié)果是：A, B, D, G, C, E,乩L, L K, M, F和J,它的中序 遍歷結(jié)果是：G, D, B, A, L, H, E, K, I, M, C, F和J,請(qǐng)畫(huà)出這棵二叉樹(shù)，并寫(xiě)岀該 二叉樹(shù)后續(xù)適歷的結(jié)果。

39、（1）二叉樹(shù)圖形表示如下:（2）該二叉樹(shù)后序遍歷的結(jié)果是：G. D、B、L、H. K、I、E、J、F、C和A。題目39假設(shè)通信譽(yù)的報(bào)文由9個(gè)字母A、B、C、D、E. F、G、H和I組成，它們顯現(xiàn)的頻率別離是:10、20、五、1五.八.二.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è)字符的哈夫曼編碼。1）哈夫曼樹(shù)如圖B-4所示。（2）其帶權(quán)途徑長(zhǎng)度WPL值為270。（3）每一個(gè)字符的哈夫曼編碼為：A:100, B:U, C:1010, D:000, E:0010, F:10110, G:10111, H:0011, 1

40、:01題目40請(qǐng)依照以下帶權(quán)有向圖G（1）給出從結(jié)點(diǎn)V,動(dòng)身別離按深度優(yōu)先搜索遍歷G和廣度優(yōu)先搜索遍歷G所得的結(jié)點(diǎn)序 列：（2）給出G的一個(gè)拓?fù)湫蛄?；?）給出從結(jié)點(diǎn)v,到結(jié)點(diǎn)vs的最短途徑。（1）深度優(yōu)先遍歷：Vit V" V3, V3, V5, V" Vi, V6廣度優(yōu)先遍歷：Vlt V” Vu V6, Vs，V5, V-, VS（2） G的拓?fù)湫蛄袨?Vi, g（3）最短途徑為：vx, v：, v5, V" v3題目41已知無(wú)向圖G描述如下:G= (V, E)V=V1, V2, V3, V4, V5E= (Vb V2) , (VI, V4) ,(V2, V4

41、) ,(V3, V4) ,(V2, V5) ,(V3, V4) ,(V3,V5 ) （1）畫(huà)出G的圖示：（2）然后給岀G的鄰接矩陣和鄰接表:（3）寫(xiě)出每一個(gè)極點(diǎn)的度。 gl的圖示和圖gl的鄰接表如以下圖所示。 圖G的鄰接矩陣如以下圖所示:圖G的鄰接矩陣vlv2v3v4f 2 | 円 4T 4 | 円門(mén)八EhOZZHZE12 I HMM圖G的鄰接表 V、V 二、V3、V4、V5 的度別離為：2, 3, 2, 3, 2四. 程序填空題（每空2分，共8分）題目42部份正確取得分中的分 題干以下是中序遍歷二叉樹(shù)的遞歸算法的程序，完成程序中空格部份（樹(shù)結(jié)構(gòu)中左、右指針域 別離為left和right,數(shù)據(jù)

42、域血ta為字符型,BT指向根結(jié)點(diǎn)）。void Inorder (struct BTreeNode *BT)if(BT!=NULL)回答回答Inorder(BT->right);答案：(1) Inorder(BT->left)(2) printfBT->data)題目43以下程序是后序遍歷二叉樹(shù)的遞歸算法的程序，完成程序中空格部份(樹(shù)結(jié)構(gòu)中左、右指 針域別藹為left和right,數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn))。void Inorder (struct BTreeNode *BT)if(BT!二NULL)回答Inorder(BT->right);回答:(1) I

43、norder(BT->left)(2) printf BT->data)形考任務(wù)四一、單項(xiàng)選擇題（每題2分，共42分）題目1對(duì)線性表進(jìn)行二分査找時(shí)，要求線性表必需（）。選擇一項(xiàng):A. 切勵(lì)存儲(chǔ)方式B. 以順序存儲(chǔ)方式,且數(shù)據(jù)元素有序C. 以鏈接存儲(chǔ)方式,且數(shù)據(jù)元素有序D. 以瓏存儲(chǔ)方式題目2采納順序査找方式查找長(zhǎng)度為n的線性表時(shí)，每一個(gè)元素的平均査找長(zhǎng)度為（）。選擇一項(xiàng):A. （n-l ）/2B. （n+l）/2C. nD. n/2題目3有一個(gè)長(zhǎng)度為10的有序表，按折半查找對(duì)該表進(jìn)行查找，在等概率情形下査找成功的平均 比較次數(shù)為（）。選擇一項(xiàng):A. 29/9B. 26/10C. 3

44、1/10D. 29/10題目4已知一個(gè)有序表為11, 22, 33, 44, 55, 66, 77, 8& 99,那么順序查找元素55需要比較 （）次。選擇一項(xiàng):C. 4D. 3題目5有數(shù)據(jù)53, 30, 37, 12, 45, 24, 96，從空二叉樹(shù)開(kāi)始逐個(gè)插入數(shù)據(jù)來(lái)形成二叉排序樹(shù)，假設(shè) 希望髙度最小，應(yīng)該選擇的序列是（）。選擇一項(xiàng):A. 12,24,30,37,45,53,96B. 30,24,12,37,45,96,53題目6關(guān)于順序存儲(chǔ)的有序表5, 12, 20, 26, 37, 42, 46, 50, 64,假設(shè)采納折半査找，那么査找元 素26的比較次數(shù)是（）.選擇一項(xiàng):A

45、. 6D. 3題目7在所有的排序方式中，關(guān)鍵字比較的次數(shù)與記錄初始排列秩序無(wú)關(guān)的是（）。選擇一項(xiàng):A. 冒泡排序B. 直接插入排序C. 希爾排序D. 直點(diǎn)擇排序題目8從未排序序列中依次掏岀元素與已經(jīng)排好序的序列中的元素作比較。將英放入已排序序列 的正確的位置上，此方式稱(chēng)為（）。選擇一項(xiàng):A. 插入排序B. 歸并排序C. 選擇排序D. 互側(cè)序題目9依次將每?jī)蓚€(gè)相鄰的有序表歸并成一個(gè)有序表的排序方式稱(chēng)為（）。選擇一項(xiàng):A. 選擇排序B. 插入排序C. 歸并排序D. 互換排序題目10當(dāng)兩個(gè)元素顯現(xiàn)逆序的時(shí)候就互換位置，這種排序方式稱(chēng)為（）。選擇一項(xiàng):A. 選擇排序B. 歸并排序C. 插入排序D. 互

46、換fiE序題目11每次把待排序的區(qū)間劃分為左、右兩個(gè)子區(qū)間，其中左區(qū)間中記錄的關(guān)鍵字均小于等于基 準(zhǔn)記錄的關(guān)鍵字，右區(qū)間中記錄的關(guān)鍵字均大于等于基準(zhǔn)記錄的關(guān)鍵字，這種排序稱(chēng)為（ ）。選擇一項(xiàng):A. 堆排序B. 插入排序C. 快速排序D. 歸并排序題目12在待排序元素大體有序的情形下，效率最高的排序方式是（）。選擇一項(xiàng):A. 歸并排序B. 快速排序題目13對(duì)數(shù)據(jù)元素序列（49,72,68,13,38,50, 97,27）進(jìn)行排序，前三趟排序結(jié)果時(shí)的結(jié)果依次為第一趟：49,72,68,13,38,50, 97,27；第二趟：49, 68, 72, 13, 38, 50,97, 27；第三趟：13,

47、49,68,72,38,50, 97,27。該排序采納的方式是（）。選擇一項(xiàng):A. 選擇排序法B. 冒泡排序法c.插AAE序法D.堆積序法題目14對(duì)具有n個(gè)元素的任意序列采納插入排序法進(jìn)行排序，排序趟數(shù)為（）。選擇一項(xiàng):A. n-1B. Iog2nC. nD. n+1題目15對(duì)序列（49, 38, 65, 97, 76. 13, 47, 50）采納直接插入排序法進(jìn)行排序，要把第七個(gè) 元素47插入到已排序中，為尋覓插入的適合位置需要進(jìn)行（）次元素間的比較。選擇一項(xiàng):A. 4B. 6C. 5D. 3反題目16排序方式中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始為空）的一端 的方式，稱(chēng)

48、為（）排序。選擇一項(xiàng):A. 插入B. 快速C. 選擇D. 歸并題目17一組記錄的關(guān)鍵字序列為（40, 80, 65, 100, 14, 30, 55, 50）,利用堆排序的方式成立 的初始小根堆為（）。選擇一項(xiàng):A. 40 r 14 , 30 . 50 , 80,65,55 , 100B. 40,80 f 65,50 f 14,30 f 55 , 100C. 14,40，30 , 50 , 80 , 65，55 , 100D. 40 r 80 , 30 r 50 , 14,65 z 55 , 100題目18一組記錄的關(guān)鍵字序列為(25, 48, 16, 35, 79. 82, 23, 40,

49、36, 72),其中.含有5個(gè)長(zhǎng)度為2的有序表，按歸并排序的方式對(duì)該序列進(jìn)行一趟歸并后的結(jié)果為()。選擇一項(xiàng):A. 16 . 25 , 35，48,79 , 82，23 , 36，40 , 72B. 16 , 25，35,48，79 , 23，36,40，82 , 72C. 16,25 # 48,35 f 79 , 82 f 23 r 36 f 40,72D. 16 . 25 , 35，48,23,40,79 , 82 z 36 . 72題目19已知10個(gè)數(shù)據(jù)元素為(54, 28, 16, 34, 73, 62, 95, 60, 26, 43),對(duì)該數(shù)列從小到大 排序，通過(guò)一趟冒泡排序后的序列

50、為()。選擇一項(xiàng):D. 16 , 28 , 34 , 54 , 62 , 60 # 73 , 26 z 43 , 95題目20一組記錄的關(guān)鍵字序列為(56, 30, 89, 66, 48, 50, 94, 87, 100),利用快速排序，以 第一個(gè)關(guān)鍵字為分割元素，通過(guò)一次劃分后結(jié)果為()。選擇一項(xiàng):A. 48 r30 ,50 r56 ,66 ,89f 94r87 f100B. 30 r50 f48 r56 f66 r89f 94r100f 87C. 50 f30 #48 r66 f56 r89f 94r87 z100D. 50 r30,48 r56 ,66 f89f 94,87 f100題目

51、21）查找方若是要求一個(gè)線性表既能較快地查找，又能動(dòng)態(tài)適應(yīng)轉(zhuǎn)變要求，能夠采納（ 式。選擇一項(xiàng)：A.散列B.折半C. 分塊D. 順序二.填空題（每題1分，共16分）題目22在各類(lèi)查找方式中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無(wú)關(guān)的查找方式是回答 |哈希表査找法）O正確答案是:哈希表查找法題目23關(guān)鍵字是記錄某個(gè)回答I數(shù)據(jù)項(xiàng)I,用它能夠識(shí)別、確信個(gè)回答記錄答案：數(shù)據(jù)項(xiàng)的值、記錄題目24在一個(gè)查找表中，能夠唯一地確信一個(gè)記錄的關(guān)鍵字稱(chēng)為回答I 1;7:正確答案是:主關(guān)鍵字題目25平均查找長(zhǎng)度是指為確信記錄在查找表中的位置，需要與給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的回答。題目26回答I順"査找是一種最簡(jiǎn)單的查

52、找方式。題目27折半查找又稱(chēng)為回答I二分產(chǎn)。禾IJ用該查找算法的前提條件是，查找表中記錄相應(yīng)的關(guān)鍵字值必需按回答I八,'或陽(yáng)答案：二分査找.升序或降序排列題目28的有序表。折半查找只適用于回答I順序砂結(jié)構(gòu)正確答案是：順序存儲(chǔ)結(jié)構(gòu)題目29分塊查找又稱(chēng)為回答I劑順"它是一種介于回答順序查和折半查找之間的查找方式。答案：索引順序查找.順序査找題目30二叉排序樹(shù)或是一棵空樹(shù)，或是具有以下性質(zhì)的一棵二叉樹(shù):(1) 假設(shè)左子數(shù)不空，那么左子樹(shù)所有結(jié)點(diǎn)的值回答I均小*根結(jié)（2）假設(shè)右子數(shù)不空，那么右子樹(shù)所有結(jié)點(diǎn)的值回答I珂大卅兇（3）左右子樹(shù)又別離是回答廠曲答案：均小于根結(jié)點(diǎn)的值、均大于根結(jié)點(diǎn)的值、二叉排序樹(shù)題目31哈希表是用來(lái)寄存査找表中記錄序列的表，每一個(gè)記錄的存儲(chǔ)位置是以該記錄取得關(guān)鍵字 為回答I門(mén)變,由相應(yīng)哈希函數(shù)計(jì)算所取得的回答面o答案：自變量、函數(shù)值題目32冒泡排序是一種比較簡(jiǎn)單的回答方式。題目33在對(duì)一組記錄（50, 40, 95, 20, 1