計(jì)算機(jī)軟件技術(shù)基礎(chǔ)總復(fù)習(xí)(共37頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上計(jì)算機(jī)軟件技術(shù)基礎(chǔ)第二章 智能0801班2.1數(shù)據(jù)結(jié)構(gòu)概論一、選擇題1、數(shù)據(jù)的邏輯結(jié)構(gòu)是（ A ）。 A數(shù)據(jù)的組織形式 B數(shù)據(jù)的存儲(chǔ)形式 C數(shù)據(jù)的表示形式 D數(shù)據(jù)的實(shí)現(xiàn)形式2、組成數(shù)據(jù)的基本單位是（ C ）。 A數(shù)據(jù)項(xiàng) B數(shù)據(jù)類(lèi)型 C數(shù)據(jù)元素 D數(shù)據(jù)變量3、下面程序的時(shí)間復(fù)雜度為（ ）。 x=0； for（i=1；i<n；i+） for（j=i+1；j<=n；j+） x+； AO（ ） BO（n2） CO（1） DO（n）4、下面程序的時(shí)間復(fù)雜度為（ ）。 for（i=0；i<m；i+） for（j=0；j<n；j+） Aij=i*j； AO（

2、m2） BO（n2） CO（m×n） DO（m+n）5、下面程序段的執(zhí)行次數(shù)為（ ）。 for（i=0；i<n-1；i+） for（j=0；j>i；j+） state； An（n+1）/2 B（n-1）（n+2）/2 Cn（n+1）/2 D（n-1）（n+2）6、下面程序的時(shí)間復(fù)雜度為（A ）。 for（i=0；i<m；i+） for（j=0；j<t；j+） cij=0； for（i=0；i<m；i+） for（j=0；j<t；j+） for（k=0；k<n；k+） cij=cij+aik*bkj； AO（m×n×t） B

3、O（m+n+t） CO（m+n×t） DO（m×t+n）二、填空1、數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類(lèi)，它們分別是（線(xiàn)性）和（非線(xiàn)性）。2、算法的計(jì)算量的大小稱(chēng)為（ 時(shí)間復(fù)雜度 ）。2.2線(xiàn)性表1、與順序存儲(chǔ)結(jié)構(gòu)相比，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)密度（ ）。 A大 B小 C相同 D以上都不對(duì)2、對(duì)于存儲(chǔ)同樣一組數(shù)據(jù)元素而言，（ ）。 A順序存儲(chǔ)結(jié)構(gòu)比鏈接結(jié)構(gòu)多占空間 B在順序結(jié)構(gòu)中查找元素的速度比在鏈接結(jié)構(gòu)中查找要快 C與鏈接結(jié)構(gòu)相比，順序結(jié)構(gòu)便于安排數(shù)據(jù)元素 D順序結(jié)構(gòu)占用整塊空間而鏈接結(jié)構(gòu)不要求整塊空間4、設(shè)順序表共有n個(gè)元素，用數(shù)組elem存儲(chǔ)，實(shí)現(xiàn)在第i個(gè)元素之前插入一個(gè)元素e的

4、操作，其主要語(yǔ)句為（ ）。 AFOR j=n DOWNTO i DO elemj=elemj+1； elemi=e； BFOR j=i TO n DO elemj=elemj+1； elemi=e； CFOR j=i TO n DO elemj+1=elemj； elemi=e； DFOR j=n DOWNTO i DO elemj+1=elemj； elemi=e；5、順序表有5個(gè)元素，設(shè)在任何位置上插入元素是等概率的，則在該表中插入一個(gè)元素時(shí)所需移動(dòng)元素的平均次數(shù)為（ C ）。 A3 B2 C25 D56、設(shè)順序表有9個(gè)元素，則在第3個(gè)元素前插入一個(gè)元素所需移動(dòng)元素的個(gè)數(shù)為（ C ）。 A

5、9 B45 C7 D67、設(shè)順序表有19個(gè)元素，第一個(gè)元素的地址為200，且每個(gè)元素占3個(gè)字節(jié)，則第14個(gè)元素的存儲(chǔ)地址為（ B ）。 A236 B239 C242 D2458、設(shè)順序表的第5個(gè)元素的存儲(chǔ)地址為200，且每個(gè)元素占一個(gè)存儲(chǔ)單元，則第14個(gè)元素的存儲(chǔ)地址為（ B ）。 A208 B209 C210 D2149、設(shè)p為指向雙向循環(huán)鏈表中某個(gè)結(jié)點(diǎn)的指針，p所指向的結(jié)點(diǎn)的兩個(gè)鏈域分別用p->llink和p->rlink表示，則下列等式中（D ）成立。 Ap=p->llink Bp=p->rlink Cp=p->llink->llink Dp=p-&g

6、t;llink->rlink10、線(xiàn)性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址（ D ）。 A必須是連續(xù)的 B一定是不連續(xù)的 C部分地址必須是連續(xù)的 D連續(xù)與否均可以11、線(xiàn)性表是（ A ）。 A一個(gè)有限序列，可以為空 B一個(gè)有限序列，不可以為空 C一個(gè)無(wú)限序列，可以為空 D一個(gè)無(wú)限序列，不可以為空12、鏈?zhǔn)酱鎯?chǔ)的線(xiàn)性表中的指針指向其（ B ）。 A前趨結(jié)點(diǎn) B后繼結(jié)點(diǎn) C物理前趨 D物理后繼13、設(shè)在鏈?zhǔn)酱鎯?chǔ)的線(xiàn)性表中，設(shè)結(jié)點(diǎn)結(jié)構(gòu)為 data link ，欲在p結(jié)點(diǎn)后插入一個(gè)結(jié)點(diǎn)q的關(guān)鍵步驟為（ A ）。 Aq->link=p->link； p->link=q； Bp->lin

7、k=q->link； p->link=q； Cq->link=p->link； q->link=p； Dp->link=q->link； q->link=p；14、設(shè)有指針head指向的帶表頭結(jié)點(diǎn)的單鏈表，現(xiàn)將指針p指向的結(jié)點(diǎn)插入表中，使之成為第一個(gè)結(jié)點(diǎn)，其操作是（ A）（其中，p->next、head->next分別表示p、head所指結(jié)點(diǎn)的鏈域）。 Ap->next=head->next； head->next=p； Bp->next=head->next； head=p； Cp->next=h

8、ead； head=p； Dp->next=head； p= head；二、填空1、順序存儲(chǔ)的線(xiàn)性表，設(shè)其長(zhǎng)度為n，在任何位置上插入或刪除操作的時(shí)間代價(jià)基本上都是等效的。則插入一個(gè)元素大約要移動(dòng)表中的（ N/2 ）個(gè)元素。2、線(xiàn)性表的長(zhǎng)度是（ 數(shù)據(jù)元素個(gè)數(shù) ）。3、在帶有頭結(jié)點(diǎn)的雙鏈表L中，指針p所指結(jié)點(diǎn)是第一個(gè)元素結(jié)點(diǎn)的條件是（p>llink=h或h->r link=p）。4、某鏈表如下所示 若要?jiǎng)h除值為C的結(jié)點(diǎn)，應(yīng)做操作（ p->link=p->link->link ）。三、程序填空題1、設(shè)順序存儲(chǔ)的線(xiàn)性表存儲(chǔ)結(jié)構(gòu)定義為： struct sequnce

9、ELEMTP elemMAXSIZE； int len； /*線(xiàn)性表長(zhǎng)度域*/ 將下列簡(jiǎn)單插入算法補(bǔ)充完整。 void insert（struct sequnce *p，int i，ELEMTP x） v=*p； if（i<1）|（i>v.len+1） printf（“Overflow“）； else for（j=v.len；j>=i；j- -） v.elemj+1=v.elemj； v.elemi= x ；v.len=v.len+1； 2、設(shè)線(xiàn)性鏈表的存儲(chǔ)結(jié)構(gòu)如下： struct node ELEMTP data； /*數(shù)據(jù)域*/ struct node *next； /*

10、指針域*/ 試完成下列在鏈表中值為x的結(jié)點(diǎn)前插入一個(gè)值為y的新結(jié)點(diǎn)的算法。如果x不存在，則把新結(jié)點(diǎn)插在表尾。 void inserty（struct node *head，ELEMTP x，ELEMTP y） s=（struct node *）malloc（sizeof（struct node）； s->data=y； if（head->data= =x）s->next=head；head=s； else q=head；p=q->next； while（p->data!=x && p->next!=NULL）q=p；p=p->next；

11、 if（p->data= = x）q->next=s；s->next=p； else p->next=s；s->next=NULL； 3、設(shè)線(xiàn)性鏈表的存儲(chǔ)結(jié)構(gòu)如下： struct node ELEMTP data； /*數(shù)據(jù)域*/ struct node *next； /*指針域*/ 試完成下列建立單鏈表的算法。 creat（） char var； head=（struct node *）malloc（sizeof（struct node）； head->next= NULL ； while ( (var =getchar ( ) )!= n) ptr=（

12、struct node *）malloc（sizeof（struct node）； ptr->data= var ； ptr->next = head->next； head->next= ptr ； 4、下列算法將單鏈表中值重復(fù)的結(jié)點(diǎn)刪除，使所得的結(jié)果表中各結(jié)點(diǎn)值均不相同，試完成該算法。 void DelSameNode（LinkList L） /L是帶頭結(jié)點(diǎn)的單鏈表，刪除其中的值重復(fù)的結(jié)點(diǎn)/ ListNode * p，*q，*r； p = L->next； /p初始指向開(kāi)始結(jié)點(diǎn)/ while（p） /處理當(dāng)前結(jié)點(diǎn)p/ q = p； r = q->next

13、； do /刪除與結(jié)點(diǎn)*p的值相同的結(jié)點(diǎn)/ while（r&&r->data!=p->data） q = r； r = r->next； if（r） /結(jié)點(diǎn)*r的值與*p的值相同，刪除*r/ q->next = r->next； free（r）； r = q->next； while（ r ）； p = p->next； 2.3棧、隊(duì)列、串一、填空題1、在棧中，下列說(shuō)法正確的是（A ）。 A每次插入總是在棧頂，每次刪除也總是在棧頂。 B每次插入總是在棧頂，每次刪除總是在棧底。 C每次插入總是在棧底，每次刪除總是在棧頂。 D每次插入總是在

14、棧底，每次刪除也總是在棧底。2、設(shè)有一個(gè)棧，按A、B、C的順序進(jìn)棧，則下列（ C ）為不可能的出棧序列。 AABC BCBA CCAB DACB3、設(shè)有一個(gè)棧，按A、B、C、D的順序進(jìn)棧，則下列（D ）為可能的出棧序列。 ADCAB BCDAB CDBAC DACDB4、順序棧的上溢是指（ B ）。 A棧滿(mǎn)時(shí)作退棧運(yùn)算 B棧滿(mǎn)時(shí)作進(jìn)棧運(yùn)算 C棧空時(shí)作退棧運(yùn)算 D?？諘r(shí)作進(jìn)棧運(yùn)算5、順序棧S中top為棧頂指針，指向棧頂元素所在的位置，elem為存放棧的數(shù)組，則元素e進(jìn)棧操作的主要語(yǔ)句為（ D）。 Aselemtop=e； stop=stop+1； Bselemtop+1=e； stop=stop

15、+1； Cstop=stop+1； selemtop+1=e； Dstop=stop+1； selemtop=e； 6、設(shè)有5個(gè)元素A，B，C，D，E順序進(jìn)棧（進(jìn)棧過(guò)程中可以出棧），出棧后依出棧次序進(jìn)入隊(duì)列，已知其出隊(duì)次序?yàn)镈，C，E，B，A，則該棧容量必定不小于（C ）。 A2 B3 C4 D57、設(shè)棧S的初始狀態(tài)為空，現(xiàn)有五個(gè)元素組成的序列1，2，3，4，5，對(duì)該序列在棧S上依次進(jìn)行PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH操作，出棧的元素序列是（ C）。 A5，4，3，2，1 B2，1 C2，3 D3，48、在一個(gè)具有n個(gè)單元的順序棧中，假定以地址低端（即0單元）作

16、為棧底，以top為棧頂指針，則當(dāng)做出棧處理時(shí)，top變化為（ ）。 Atop不變 Btop=0 Ctop- - Dtop+9、向一個(gè)棧頂指針為hs的鏈棧中插入一個(gè)*s結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行（ B）。 Ahs->next=s； Bs->next=hs；hs=s； Cs->next=hs->next；hs->next=s； Ds->next=hs；hs=hs->next；10、在隊(duì)列中，下列說(shuō)法正確的是（A ）。 A每次插入總是在隊(duì)尾，每次刪除總是在隊(duì)頭。 B每次插入總是在隊(duì)尾，每次刪除也總是在隊(duì)尾。 C每次插入總是在隊(duì)頭，每次刪除也總是在隊(duì)頭。 D每次插入總是在

17、隊(duì)頭，每次刪除總是在隊(duì)尾。11、在帶頭結(jié)點(diǎn)的鏈隊(duì)列q中，用qfront表示隊(duì)頭指針，qrear表示隊(duì)尾指針，結(jié)點(diǎn)結(jié)構(gòu)為data next ，刪除鏈隊(duì)列的隊(duì)頭結(jié)點(diǎn)的主要語(yǔ)句為（B ）。 As=qfront； qfront->next= snext； Bs=qfront->next； qfront->next= snext； Cs=qfront->next； qfront= snext； Ds=q； qfront->next= snext；12、循環(huán)隊(duì)列sq中，用數(shù)組elem存放數(shù)據(jù)元素，sqfront指示隊(duì)頭元素的前一個(gè)位置，sqrear指示隊(duì)尾元素的當(dāng)前位置，隊(duì)列

18、的最大容量為MAXSIZE，則隊(duì)列滿(mǎn)的條件為（ D ）。 Asqfront= sqrear Bsqfront= sqrear+1 C（sqfront +1）mod MAXSIZE= sqrear D（sqrear+1）mod MAXSIZE= sqfront13、循環(huán)隊(duì)列sq中，用數(shù)組elem存放數(shù)據(jù)元素，sqfront指示隊(duì)頭元素的前一個(gè)位置，sqrear指示隊(duì)尾元素的當(dāng)前位置，隊(duì)列的最大容量為MAXSIZE，則在隊(duì)列未滿(mǎn)時(shí)元素x入隊(duì)列的主要操作為（ A ）。 Asqrear= （sqrear+1）mod MAXSIZE； sqelemsqrear=x； Bsqelemsqrear=x； s

19、qrear= （sqrear+1）mod MAXSIZE； Csqfront= （sqfront+1）mod MAXSIZE； sqelemsqfront=x； Dsqelemsqfront=x； sqfront= sqfront+1；14、循環(huán)隊(duì)列sq中，用數(shù)組elem025存放數(shù)據(jù)元素，sqfront指示隊(duì)頭元素的前一個(gè)位置，sqrear指示隊(duì)尾元素的當(dāng)前位置，設(shè)當(dāng)前sqfront為20，sqrear為12，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為（ ）。 A8 B16 C17 D1815、設(shè)循環(huán)隊(duì)列的元素存放在一維數(shù)組Q030中，隊(duì)列非空時(shí)，front指示隊(duì)頭元素的前一個(gè)位置，rear指示隊(duì)尾元素。如果

20、隊(duì)列中元素的個(gè)數(shù)為11，front的值為25，則rear應(yīng)指向（ ）元素。 AQ4 BQ5 CQ14 DQ1516、隊(duì)列操作的原則是（A ）。 A先進(jìn)先出 B后進(jìn)先出 C只能進(jìn)行插入 D只能進(jìn)行刪除17、一個(gè)隊(duì)列的入列序列是1234，則隊(duì)列的輸出序列是（ B）。 A4321 B1234 C1432 D324118、下列關(guān)于串的敘述中，不正確的是（ ）。 A串是字符的有限序列 B空串是由空格構(gòu)成的串 C模式匹配是串的一種重要運(yùn)算 D串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)二、填空題1、對(duì)于棧只能在（棧頂 ）插入和刪除元素。2、設(shè)有一空棧，現(xiàn)有輸入序列1，2，3，4，5，6，經(jīng)過(guò)push，push

21、，pop，push，pop，push，push后，輸出序列是（ 2，3 ）。、有一個(gè)循環(huán)隊(duì)列如下圖，其隊(duì)滿(mǎn)條件是（front=(rear+1)%n），隊(duì)列空的條件是（rear=front）。三、程序填空題1、鏈隊(duì)列的存儲(chǔ)結(jié)構(gòu)為： struct nodetype ELEMTP data； struct nodetype *next； struct linkqueue struct nodetype *front，*rear； /*front和rear分別為隊(duì)列的頭指針和尾指針*/完成下列刪除隊(duì)頭元素的算法。 delq（struct linkqueue *r，ELEMTP *x） q=*r； if

22、（q.front= =q.rear）printf（“QUEUE IS EMPTYn“）； elsep=q.front->next； q.front->next=p->next； if（p->next= =NULL）q.rear=q.front； *x=p->data；free（p）； 2.4數(shù)組1、設(shè)6行8列的二維數(shù)組A6×8=（aij）按行優(yōu)先順序存儲(chǔ)，若第一個(gè)元素的存儲(chǔ)位置為200，且每個(gè)元素占3個(gè)存儲(chǔ)單元，則元素a54的存儲(chǔ)位置為（B ）。 A308 B305 C266 D2692、設(shè)有一個(gè)10階的對(duì)稱(chēng)矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a1

23、1為第一個(gè)元素，其存儲(chǔ)地址為1，每元素占1個(gè)地址空間，則a85的地址為（B ）。 A13 B33 C18 D403、設(shè)二個(gè)數(shù)組為A07、B-52，38，則這兩個(gè)數(shù)組分別能存放的字符的最大個(gè)數(shù)是（ C ）。 A7和35 B1和5 C8和48 D1和64、二維數(shù)組Mi，j的元素是4個(gè)字符（每個(gè)字符占一個(gè)存儲(chǔ)單元）組成的串，行下標(biāo)i的范圍從0到4，列下列j的范圍從0到5。M按行存儲(chǔ)時(shí)元素M3，5的起始地址與M按列存儲(chǔ)時(shí)元素（ B）的起始地址下同。AM2，4 BM3，4 CM3，5 DM4，45、設(shè)二維數(shù)組為M08，010，每個(gè)元素占2L個(gè)存儲(chǔ)單元，以行序?yàn)橹餍虼鎯?chǔ)，第一個(gè)元素的存儲(chǔ)位置為P。存儲(chǔ)位置

24、為P+50L的元素為（ A ）。AM2，3 BM2，2 CM3，3 DM3，46、設(shè)二維數(shù)組A的維數(shù)界偶定義為18，010，起始地址為L(zhǎng)OC，每個(gè)元素占2L個(gè)存儲(chǔ)單元，以行序?yàn)橹餍虼鎯?chǔ)方式下，某數(shù)據(jù)元素的地址為L(zhǎng)OC+50L，則在列序?yàn)橹餍虼鎯?chǔ)方式下，該元素的存儲(chǔ)地址為（D）。ALOC+28L BLOC+36L CLOC+50L DLOC+52L7、數(shù)組A140，130采用三元組表示，設(shè)數(shù)組元素與下標(biāo)均為整型，則在非零元素個(gè)數(shù)小于（ D ）時(shí)，才能節(jié)省存儲(chǔ)空間。 A1200 B401 C399 D4008、一維數(shù)組通常采用順序存儲(chǔ)結(jié)構(gòu)，這是因?yàn)椋– ）。 A一維數(shù)組是一種線(xiàn)性數(shù)據(jù)結(jié)構(gòu) B一維數(shù)

25、組是一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu) C一旦建立了數(shù)組，則數(shù)組中的數(shù)據(jù)元素之間的關(guān)系不再變動(dòng) D一維數(shù)組只能采用順序存儲(chǔ)結(jié)構(gòu)9、對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)的目的是（B ）。 A方便存儲(chǔ) B節(jié)省存儲(chǔ)空間 C方便運(yùn)算 D節(jié)省運(yùn)算時(shí)間10、設(shè)二維數(shù)組a05，06按行存儲(chǔ)，每個(gè)元素占d個(gè)存儲(chǔ)單元，如果每個(gè)元素改為2d個(gè)存儲(chǔ)單元，起始地址不變，則元素a2，6的存儲(chǔ)地址將要增加（ A）個(gè)存儲(chǔ)單元。 A20d B21d C38d D39d11、一維數(shù)組與線(xiàn)性表的區(qū)別是（ ）。 A前者長(zhǎng)度固定，后者長(zhǎng)度可變 B后者長(zhǎng)度固定，前者長(zhǎng)度可變 C兩者長(zhǎng)度均固定 D兩者長(zhǎng)度均可變二、填空1、一個(gè)稀疏矩陣為， 則對(duì)應(yīng)的三元組線(xiàn)性表為（0，

26、2，2），（1，0，3），（2，2，-1），（2，3，5）。2、設(shè)有二維數(shù)組A09，019，其每個(gè)元素占兩個(gè)字節(jié)，數(shù)組按列優(yōu)先順序存儲(chǔ)，第一個(gè)元素的存儲(chǔ)地址為100，那么元素A6，6的存儲(chǔ)地址為（232）。2.5樹(shù)和二叉樹(shù)一、選擇題1、下列樹(shù)的度為（ ）。 A2 B3 C5 D8 2、含10個(gè)結(jié)點(diǎn)的二叉樹(shù)中，度為0的結(jié)點(diǎn)有4個(gè)，則度為2的結(jié)點(diǎn)有（ ）個(gè)。 A3 B4 C5 D63、對(duì)一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)按層編號(hào)，則編號(hào)為49的結(jié)點(diǎn)，它的左孩子的編號(hào)為（ ）。 A98 B99 C97 D504、一棵深度為8（根的層次號(hào)為1）的滿(mǎn)二叉樹(shù)有（ ）個(gè)結(jié)點(diǎn)。 A256 B255 C128 D1

27、275、設(shè)二叉樹(shù)根結(jié)點(diǎn)的層數(shù)為1，若一棵高（深）度為h的二叉樹(shù)只有度為0與度為2的結(jié)點(diǎn)，則其結(jié)點(diǎn)數(shù)至少為（ ）。 Ah B2h-1 C2h D2h+16、對(duì)下列二叉樹(shù)進(jìn)行先根次序遍歷，所得次序?yàn)椋?）。 AABCDEF BADCBFE CBCDAFE DDCBFEA7、一棵二叉樹(shù)的前（先）序序列為ABCDEFG，則它的中序序列不可能為（ ）。 ACBDAFEG BDCBAEFG CCDBAGEF DBDCAFGE8、若先序遍歷二叉樹(shù)的結(jié)果為結(jié)點(diǎn)序列A，B，C，則有（ ）棵不同的二叉樹(shù)可以得到這一結(jié)果。 A3 B4 C5 D69、具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，有（ ）條邊。 An Bn-1 Cn+1 D

28、2n10、在具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)的二叉鏈表表示中，2n個(gè)孩子指針域中，只用到（ ）個(gè)域。 An Bn-1 Cn+1 D2n11、對(duì)哈夫曼樹(shù)，下列說(shuō)法錯(cuò)誤的是（ ）。 A哈夫曼樹(shù)是一類(lèi)帶樹(shù)路徑長(zhǎng)度最短的樹(shù)。 B給出一組數(shù)，構(gòu)造的哈夫曼樹(shù)唯一。 C給出一組數(shù)，構(gòu)造的哈夫曼樹(shù)的帶樹(shù)路徑長(zhǎng)度不變。 D哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度為每個(gè)葉子的路徑長(zhǎng)度與該葉子權(quán)值乘積之和。12、假定在一棵二叉樹(shù)中，雙分支結(jié)點(diǎn)數(shù)為15個(gè)，單分支結(jié)點(diǎn)數(shù)為30個(gè)，則葉子結(jié)點(diǎn)數(shù)為（ ）。 A15 B16 C17 D4713、假定一棵三叉樹(shù)的結(jié)點(diǎn)數(shù)為50，則它的最小高度為（ ）。 A3 B4 C5 D614、由帶權(quán)為9，2，5，7的四個(gè)

29、葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹(shù)，該樹(shù)的帶權(quán)路徑長(zhǎng)度為（ ）。 A23 B37 C46 D4415、二叉樹(shù)的先序遍歷為EFHIGJK，中序遍歷為HFIEJKG，則該二叉樹(shù)根的右子樹(shù)的根是（ ）。 AE BF CG DH16、在完全二叉樹(shù)中，若一個(gè)結(jié)點(diǎn)是葉結(jié)點(diǎn)，則它沒(méi)有（ ）。 A左孩子結(jié)點(diǎn) B右孩子結(jié)點(diǎn) C左孩子和右孩子結(jié)點(diǎn) D左孩子結(jié)點(diǎn)，右孩子結(jié)點(diǎn)和兄弟結(jié)點(diǎn)17、（ ）二叉樹(shù)，可以唯一地轉(zhuǎn)化成一棵一般樹(shù)。 A根結(jié)點(diǎn)無(wú)左孩子 B根結(jié)點(diǎn)無(wú)右孩子 C根據(jù)結(jié)點(diǎn)有兩個(gè)孩子 D沒(méi)有一棵18、具有65個(gè)結(jié)點(diǎn)的完全二叉樹(shù)其深度為（ ）。 A8 B7 C6 D519、某二叉樹(shù)的先序序列和后序序列正好相反，則該二叉樹(shù)一

30、定是（ ）的二叉樹(shù)。 A空或只有一個(gè)結(jié)點(diǎn) B高度等于其結(jié)點(diǎn)數(shù) C任一結(jié)點(diǎn)無(wú)左孩子 D任一結(jié)點(diǎn)無(wú)右孩子20、下面敘述中，不正確的是（ ）。 A線(xiàn)性表中除第一個(gè)元素和最后一個(gè)元素外，其他每個(gè)元素都有且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼 B樹(shù)中有且僅有一個(gè)結(jié)點(diǎn)沒(méi)有前驅(qū) C環(huán)形隊(duì)列中任何一個(gè)元素都有且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼 D在樹(shù)中，一個(gè)結(jié)點(diǎn)可以有多個(gè)直接后繼21、有m個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)，其結(jié)點(diǎn)總數(shù)是（ ）。 A2m B2m+1 C2m-1 D2（m+1）二、填空題1、在一棵二叉排序樹(shù)上按（ ）遍歷得到的結(jié)點(diǎn)序列是一個(gè)有序序列。2、對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)進(jìn)行鏈接存儲(chǔ)時(shí)，其二叉鏈表中的指

31、針域的總數(shù)為2n個(gè)，其中（ ）個(gè)用于鏈接孩子結(jié)點(diǎn)。3、對(duì)于下面的二叉樹(shù)，按后序遍歷得到的結(jié)點(diǎn)序列為（ ）。三、程序填空題1、下面算法實(shí)現(xiàn)，用一棵二叉樹(shù)中的結(jié)點(diǎn)建立一個(gè)按關(guān)鍵字值從小到大次序排列的帶表頭結(jié)點(diǎn)的雙向循環(huán)鏈表。二叉樹(shù)的結(jié)點(diǎn)結(jié)構(gòu)如下所示：其中，p是指向結(jié)點(diǎn)的指針；p->key表示結(jié)點(diǎn)的關(guān)鍵字域，p->left和p->right分別表示結(jié)點(diǎn)的左、右孩子的指針域。void fromtreetolist（p，l） /*p，h是指向二叉樹(shù)中結(jié)點(diǎn)的指針，*/ /*l是指向雙向循環(huán)鏈表表頭結(jié)點(diǎn)的指針*/ if (p!=NULL) fromtreetolist（p->left

32、，l）； fromtreetolist（p-> right，l）； h=l； while （h->right!=l）&&（h->right->key<p->key） h=h->right； p->right=h->right； p->left=h； h->right->left=p； h->rihght=p； void buildlisttree（root，l） /*root是指向二叉樹(shù)根結(jié)點(diǎn)的指針，*/ /*l是指向雙向循環(huán)鏈表表頭結(jié)點(diǎn)的指針*/ l=（struct nodetype *）mallo

33、c（sizeof（struct nodetype）； l->left=l； l->right=l； fromtreetolist（root，l）； 2.6、圖1、設(shè)圖的鄰接矩陣為 ，則該圖有（ ）個(gè)頂點(diǎn)。 A3 B4 C6 D92、設(shè)圖的鄰接矩陣為 ，則該圖為（ ）。 A有向圖 B無(wú)向圖 C強(qiáng)連通圖 D完全圖3、設(shè)圖的鄰接鏈表如下圖所示，則該圖有（ ）條邊。 A4 B5 C10 D204、設(shè)有6個(gè)結(jié)點(diǎn)的無(wú)向圖，該圖至少應(yīng)有（B）條邊才能確保是一個(gè)連通圖。 A5 B6 C7 D85、已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下，則根據(jù)有向圖的深度優(yōu)先遍歷算法，從頂點(diǎn)V1出發(fā)，不能得到的頂點(diǎn)序列是

34、（ ）。 AV1V2V3V5V4 BV1 V3 V4V5V2 CV1V2V4V5V3 DV1 V4V3V5V2 6、下列圖的深度優(yōu)先遍歷序列為（ ）。 AABCDEFGH BABDHECFG CABEDHCFG DABCFGEDH7、對(duì)一個(gè)具有n個(gè)頂點(diǎn)的圖，采用鄰接矩陣表示則該矩陣的大小為（D）。 An B（n-1）2 C（n+1）2 Dn2 二、填空題1、設(shè)無(wú)向圖G的頂點(diǎn)數(shù)為n，圖G最少有（ ）邊。2、對(duì)下列圖它的生成樹(shù)有（ ）棵。三、程序填空題1、下列算法將圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)轉(zhuǎn)換為如下圖所示的鄰接表存儲(chǔ)結(jié)構(gòu)。圖中左側(cè)的記錄數(shù)組的每個(gè)結(jié)點(diǎn)有兩個(gè)域：el和fst；右側(cè)鏈表中的結(jié)點(diǎn)是類(lèi)型為no

35、de的記錄類(lèi)開(kāi)，每個(gè)結(jié)點(diǎn)有兩個(gè)域：adj和link。若指針p指向node類(lèi)型的結(jié)點(diǎn)，則對(duì)該結(jié)點(diǎn)的adj、link域的引用表示為：p->adj、p->link。void Convert（c，g） /*c是鄰接矩陣，n為階數(shù)。g是上圖所示的鄰接表*/ /*p、q是指向node類(lèi)型結(jié)點(diǎn)的指針*/ /*i，j為整型*/ for（i=1；i<=n；i+） gi.fst=NULL； for（j=1；j<=n ；j+） if（ci，j!=0） q=（struct nodetype *）malloc（sizeof（struct nodetype）； q->link=NULL； q

36、->adj=j； if（qi.fst=NULL） qi.fst=q ； p=q else p->link=q； p=q； 2.7查找一、選擇1、對(duì)含n個(gè)記錄的順序表進(jìn)行順序查找，在最壞情況下需要比較（ ）次。 An-1 Bn C（n+1）/2 Dn（n-1）/22、對(duì)含n個(gè)記錄的有序表進(jìn)行折半查找，設(shè)每個(gè)記錄的查找概率相等，則平均查找長(zhǎng)度的數(shù)量級(jí)為（ ）。 AO（n） BO（n2） CO（log2n） DO（1）3、有一棵二叉樹(shù)如下圖，該樹(shù)是（ ）。A二叉平衡樹(shù) B二叉排序樹(shù) C堆的形狀 D以上都不是4、已知10個(gè)數(shù)據(jù)元素（50，30，15，35，70，65，95，60，25，40

37、），按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹(shù)后，在查找成功的情況下，查找每個(gè)元素的平均比較次數(shù)（又稱(chēng)平均查找長(zhǎng)度）為（ ）。 A2.5 B3.2 C2.9 D2.75、在順序存儲(chǔ)的線(xiàn)性表R029上進(jìn)行分塊查找（設(shè)分為5塊）的平均查找長(zhǎng)度為（ ）。 A6 B11 C5 D6.56、已知一個(gè)線(xiàn)性表（38，25，74，63，52，48），假定采用h（k）=k%7計(jì)算散列地址進(jìn)行散列存儲(chǔ)，若引用線(xiàn)性探測(cè)的開(kāi)放定地址法解決沖突，則在該散列表上進(jìn)行查找的平均查找長(zhǎng)度為（ ）。 A1.5 B1.7 C2 D2.37、設(shè)散列地址空間為0m-1，k為關(guān)鍵字，用P去除k，將余數(shù)作為k的散列地址，即：h（k）=k%

38、P，為了減少發(fā)生沖突的可能性，一般取P為（ ）。 A小于m的最大奇數(shù) B小于m的最大素?cái)?shù) C小于m的最大偶數(shù) D小于m的最大合數(shù)8、設(shè)散列表表長(zhǎng)m=14，散列函數(shù)為h（k）=k%11，表中已有4個(gè)記錄，如果用二次探測(cè)再散列處理沖突，關(guān)鍵字為49的記錄的存儲(chǔ)地址是（ ）。A8 B3 C5 D9二、填空1、設(shè)有兩個(gè)散列函數(shù)H1（K）=K mod 13和H2（K）=K mod 11+1，散列表為T(mén)012，用雙重散列法（又稱(chēng)二次散列法）解決沖突。函數(shù)H1用來(lái)計(jì)算散列地址，當(dāng)發(fā)生沖突時(shí)，H2作為計(jì)算下一個(gè)探測(cè)地址的地址增量。假定某一時(shí)刻散列表T的狀態(tài)為：下一個(gè)被插入的關(guān)鍵碼為42，其插入位置是（ ）。2

39、.8排序一、選擇1、已知8個(gè)元素（34，76，45，18，26，54，92，65），按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹(shù)，該樹(shù)的深度為（C）。 A4 B5 C6 D72、直接插入排序算法的時(shí)間復(fù)雜度為（ ）。 AO（n） BO（n2） CO（） DO（1）3、設(shè)記錄關(guān)鍵字序列為（84，67，21，50，33，79），采用對(duì)半插入排序方法自小到大進(jìn)行排序時(shí)，記錄的移動(dòng)次數(shù)為（ ）。 A9 B10 C19 D254、下列四個(gè)序列中，（ ）不是快速排序第一趟的可能結(jié)果。 A68，11，69，23，18，70，73 93 B11 68，69，23，18，70，73，93 C68，11，69，23，

40、18 70 93，73 D18，11，23 93 68，70，69，735、下列四個(gè)關(guān)鍵字序列中，（ ）不是堆。 A05，23，16，68，94，72，71，73 B05，16，23，68，94，72，71，73 C05，23，16，73，94，72，71，68 D05，23，16，68，73，71，72，946、從未排序序列中依次取出元素與已排序序列中的元素作比較，將其放入已排序序列中的正確位置上，此方法稱(chēng)為（ ）。 A歸并排序 B選擇排序 C交換排序 D插入排序7、在所有排序方法中，關(guān)鍵字的比較次數(shù)與記錄的初始排列無(wú)關(guān)的是（ ）。 AShell排序 B冒泡排序 C直接插入排序 D直接選擇排序 8、下列排序算法中，第