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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上計算機軟件技術(shù)基礎(chǔ)第二章 智能0801班2.1數(shù)據(jù)結(jié)構(gòu)概論一、選擇題1、數(shù)據(jù)的邏輯結(jié)構(gòu)是（ A ）。 A數(shù)據(jù)的組織形式 B數(shù)據(jù)的存儲形式 C數(shù)據(jù)的表示形式 D數(shù)據(jù)的實現(xiàn)形式2、組成數(shù)據(jù)的基本單位是（ C ）。 A數(shù)據(jù)項 B數(shù)據(jù)類型 C數(shù)據(jù)元素 D數(shù)據(jù)變量3、下面程序的時間復(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、下面程序的時間復(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、下面程序的時間復(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)可分為兩大類，它們分別是（線性）和（非線性）。2、算法的計算量的大小稱為（ 時間復(fù)雜度 ）。2.2線性表1、與順序存儲結(jié)構(gòu)相比，鏈?zhǔn)酱鎯Y(jié)構(gòu)的存儲密度（ ）。 A大 B小 C相同 D以上都不對2、對于存儲同樣一組數(shù)據(jù)元素而言，（ ）。 A順序存儲結(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個元素，用數(shù)組elem存儲，實現(xiàn)在第i個元素之前插入一個元素e的

4、操作，其主要語句為（ ）。 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個元素，設(shè)在任何位置上插入元素是等概率的，則在該表中插入一個元素時所需移動元素的平均次數(shù)為（ C ）。 A3 B2 C25 D56、設(shè)順序表有9個元素，則在第3個元素前插入一個元素所需移動元素的個數(shù)為（ C ）。 A

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

6、t;llink->rlink10、線性表采用鏈?zhǔn)酱鎯r，其地址（ D ）。 A必須是連續(xù)的 B一定是不連續(xù)的 C部分地址必須是連續(xù)的 D連續(xù)與否均可以11、線性表是（ A ）。 A一個有限序列，可以為空 B一個有限序列，不可以為空 C一個無限序列，可以為空 D一個無限序列，不可以為空12、鏈?zhǔn)酱鎯Φ木€性表中的指針指向其（ B ）。 A前趨結(jié)點 B后繼結(jié)點 C物理前趨 D物理后繼13、設(shè)在鏈?zhǔn)酱鎯Φ木€性表中，設(shè)結(jié)點結(jié)構(gòu)為 data link ，欲在p結(jié)點后插入一個結(jié)點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é)點的單鏈表，現(xiàn)將指針p指向的結(jié)點插入表中，使之成為第一個結(jié)點，其操作是（ A）（其中，p->next、head->next分別表示p、head所指結(jié)點的鏈域）。 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、順序存儲的線性表，設(shè)其長度為n，在任何位置上插入或刪除操作的時間代價基本上都是等效的。則插入一個元素大約要移動表中的（ N/2 ）個元素。2、線性表的長度是（ 數(shù)據(jù)元素個數(shù) ）。3、在帶有頭結(jié)點的雙鏈表L中，指針p所指結(jié)點是第一個元素結(jié)點的條件是（p>llink=h或h->r link=p）。4、某鏈表如下所示 若要刪除值為C的結(jié)點，應(yīng)做操作（ p->link=p->link->link ）。三、程序填空題1、設(shè)順序存儲的線性表存儲結(jié)構(gòu)定義為： struct sequnce

9、ELEMTP elemMAXSIZE； int len； /*線性表長度域*/ 將下列簡單插入算法補充完整。 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è)線性鏈表的存儲結(jié)構(gòu)如下： struct node ELEMTP data； /*數(shù)據(jù)域*/ struct node *next； /*

10、指針域*/ 試完成下列在鏈表中值為x的結(jié)點前插入一個值為y的新結(jié)點的算法。如果x不存在，則把新結(jié)點插在表尾。 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è)線性鏈表的存儲結(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é)點刪除，使所得的結(jié)果表中各結(jié)點值均不相同，試完成該算法。 void DelSameNode（LinkList L） /L是帶頭結(jié)點的單鏈表，刪除其中的值重復(fù)的結(jié)點/ ListNode * p，*q，*r； p = L->next； /p初始指向開始結(jié)點/ while（p） /處理當(dāng)前結(jié)點p/ q = p； r = q->next

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

14、棧底，每次刪除也總是在棧底。2、設(shè)有一個棧，按A、B、C的順序進棧，則下列（ C ）為不可能的出棧序列。 AABC BCBA CCAB DACB3、設(shè)有一個棧，按A、B、C、D的順序進棧，則下列（D ）為可能的出棧序列。 ADCAB BCDAB CDBAC DACDB4、順序棧的上溢是指（ B ）。 A棧滿時作退棧運算 B棧滿時作進棧運算 C?？諘r作退棧運算 D棧空時作進棧運算5、順序棧S中top為棧頂指針，指向棧頂元素所在的位置，elem為存放棧的數(shù)組，則元素e進棧操作的主要語句為（ 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個元素A，B，C，D，E順序進棧（進棧過程中可以出棧），出棧后依出棧次序進入隊列，已知其出隊次序為D，C，E，B，A，則該棧容量必定不小于（C ）。 A2 B3 C4 D57、設(shè)棧S的初始狀態(tài)為空，現(xiàn)有五個元素組成的序列1，2，3，4，5，對該序列在棧S上依次進行PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH操作，出棧的元素序列是（ C）。 A5，4，3，2，1 B2，1 C2，3 D3，48、在一個具有n個單元的順序棧中，假定以地址低端（即0單元）作

16、為棧底，以top為棧頂指針，則當(dāng)做出棧處理時，top變化為（ ）。 Atop不變 Btop=0 Ctop- - Dtop+9、向一個棧頂指針為hs的鏈棧中插入一個*s結(jié)點時，應(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、在隊列中，下列說法正確的是（A ）。 A每次插入總是在隊尾，每次刪除總是在隊頭。 B每次插入總是在隊尾，每次刪除也總是在隊尾。 C每次插入總是在隊頭，每次刪除也總是在隊頭。 D每次插入總是在

17、隊頭，每次刪除總是在隊尾。11、在帶頭結(jié)點的鏈隊列q中，用qfront表示隊頭指針，qrear表示隊尾指針，結(jié)點結(jié)構(gòu)為data next ，刪除鏈隊列的隊頭結(jié)點的主要語句為（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)隊列sq中，用數(shù)組elem存放數(shù)據(jù)元素，sqfront指示隊頭元素的前一個位置，sqrear指示隊尾元素的當(dāng)前位置，隊列

18、的最大容量為MAXSIZE，則隊列滿的條件為（ D ）。 Asqfront= sqrear Bsqfront= sqrear+1 C（sqfront +1）mod MAXSIZE= sqrear D（sqrear+1）mod MAXSIZE= sqfront13、循環(huán)隊列sq中，用數(shù)組elem存放數(shù)據(jù)元素，sqfront指示隊頭元素的前一個位置，sqrear指示隊尾元素的當(dāng)前位置，隊列的最大容量為MAXSIZE，則在隊列未滿時元素x入隊列的主要操作為（ 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)隊列sq中，用數(shù)組elem025存放數(shù)據(jù)元素，sqfront指示隊頭元素的前一個位置，sqrear指示隊尾元素的當(dāng)前位置，設(shè)當(dāng)前sqfront為20，sqrear為12，則當(dāng)前隊列中的元素個數(shù)為（ ）。 A8 B16 C17 D1815、設(shè)循環(huán)隊列的元素存放在一維數(shù)組Q030中，隊列非空時，front指示隊頭元素的前一個位置，rear指示隊尾元素。如果

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

21、，pop，push，pop，push，push后，輸出序列是（ 2，3 ）。、有一個循環(huán)隊列如下圖，其隊滿條件是（front=(rear+1)%n），隊列空的條件是（rear=front）。三、程序填空題1、鏈隊列的存儲結(jié)構(gòu)為： struct nodetype ELEMTP data； struct nodetype *next； struct linkqueue struct nodetype *front，*rear； /*front和rear分別為隊列的頭指針和尾指針*/完成下列刪除隊頭元素的算法。 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)先順序存儲，若第一個元素的存儲位置為200，且每個元素占3個存儲單元，則元素a54的存儲位置為（B ）。 A308 B305 C266 D2692、設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a1

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

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

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

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

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

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

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

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

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

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

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

35、de的記錄類開，每個結(jié)點有兩個域：adj和link。若指針p指向node類型的結(jié)點，則對該結(jié)點的adj、link域的引用表示為：p->adj、p->link。void Convert（c，g） /*c是鄰接矩陣，n為階數(shù)。g是上圖所示的鄰接表*/ /*p、q是指向node類型結(jié)點的指針*/ /*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、對含n個記錄的順序表進行順序查找，在最壞情況下需要比較（ ）次。 An-1 Bn C（n+1）/2 Dn（n-1）/22、對含n個記錄的有序表進行折半查找，設(shè)每個記錄的查找概率相等，則平均查找長度的數(shù)量級為（ ）。 AO（n） BO（n2） CO（log2n） DO（1）3、有一棵二叉樹如下圖，該樹是（ ）。A二叉平衡樹 B二叉排序樹 C堆的形狀 D以上都不是4、已知10個數(shù)據(jù)元素（50，30，15，35，70，65，95，60，25，40

37、），按照依次插入結(jié)點的方法生成一棵二叉排序樹后，在查找成功的情況下，查找每個元素的平均比較次數(shù)（又稱平均查找長度）為（ ）。 A2.5 B3.2 C2.9 D2.75、在順序存儲的線性表R029上進行分塊查找（設(shè)分為5塊）的平均查找長度為（ ）。 A6 B11 C5 D6.56、已知一個線性表（38，25，74，63，52，48），假定采用h（k）=k%7計算散列地址進行散列存儲，若引用線性探測的開放定地址法解決沖突，則在該散列表上進行查找的平均查找長度為（ ）。 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的最大素數(shù) C小于m的最大偶數(shù) D小于m的最大合數(shù)8、設(shè)散列表表長m=14，散列函數(shù)為h（k）=k%11，表中已有4個記錄，如果用二次探測再散列處理沖突，關(guān)鍵字為49的記錄的存儲地址是（ ）。A8 B3 C5 D9二、填空1、設(shè)有兩個散列函數(shù)H1（K）=K mod 13和H2（K）=K mod 11+1，散列表為T012，用雙重散列法（又稱二次散列法）解決沖突。函數(shù)H1用來計算散列地址，當(dāng)發(fā)生沖突時，H2作為計算下一個探測地址的地址增量。假定某一時刻散列表T的狀態(tài)為：下一個被插入的關(guān)鍵碼為42，其插入位置是（ ）。2

39、.8排序一、選擇1、已知8個元素（34，76，45，18，26，54，92，65），按照依次插入結(jié)點的方法生成一棵二叉排序樹，該樹的深度為（C）。 A4 B5 C6 D72、直接插入排序算法的時間復(fù)雜度為（ ）。 AO（n） BO（n2） CO（） DO（1）3、設(shè)記錄關(guān)鍵字序列為（84，67，21，50，33，79），采用對半插入排序方法自小到大進行排序時，記錄的移動次數(shù)為（ ）。 A9 B10 C19 D254、下列四個序列中，（ ）不是快速排序第一趟的可能結(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、下列四個關(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、從未排序序列中依次取出元素與已排序序列中的元素作比較，將其放入已排序序列中的正確位置上，此方法稱為（ ）。 A歸并排序 B選擇排序 C交換排序 D插入排序7、在所有排序方法中，關(guān)鍵字的比較次數(shù)與記錄的初始排列無關(guān)的是（ ）。 AShell排序 B冒泡排序 C直接插入排序 D直接選擇排序 8、下列排序算法中，第