數(shù)據(jù)結(jié)構(gòu)習(xí)題庫匯總

1、知識點(diǎn)：01緒論02順序表03鏈表04棧05鏈隊(duì)列06循環(huán)隊(duì)列07串08數(shù)組的順序表示09稀疏矩陣10廣義表11二叉樹的基本概念12二叉樹遍歷、二叉樹性質(zhì)13樹、樹與二叉樹的轉(zhuǎn)換14赫夫曼樹15圖的定義、圖的存儲16圖的遍歷17圖的生成樹18靜態(tài)查找（順序表的查找、有序表的查找）19動(dòng)態(tài)查找（二叉排序樹、平衡樹、B樹）20哈希查找21插入排序（直接插入、折半插入、2路插入、希爾排序）22選擇排序（簡單選擇、樹形選擇、堆排序）23快速排序、歸并排序101A1（1）數(shù)據(jù)的邏輯結(jié)構(gòu)是（A）。 A數(shù)據(jù)的組織形式 B數(shù)據(jù)的存儲形式 C數(shù)據(jù)的表示形式 D數(shù)據(jù)的實(shí)現(xiàn)形式101A1（2）組成數(shù)據(jù)的基本單位是（

2、C）。 A數(shù)據(jù)項(xiàng) B數(shù)據(jù)類型 C數(shù)據(jù)元素 D數(shù)據(jù)變量101B1（3）與順序存儲結(jié)構(gòu)相比，鏈?zhǔn)酱鎯Y(jié)構(gòu)的存儲密度（B）。 A大 B小 C相同 D以上都不對101B2（4）對于存儲同樣一組數(shù)據(jù)元素而言，（D）。 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)不要求整塊空間101B2（5）下面程序的時(shí)間復(fù)雜度為（B）。 x=0； for（i=1；i<n；i+） for（j=i+1；j<=n；j+） x+； AO（） BO（n2） CO（1） DO（n）101B2（6）下面程

3、序的時(shí)間復(fù)雜度為（C）。 for（i=0；i<m；i+） for（j=0；j<n；j+） Aij=i*j； AO（m2） BO（n2） CO（m×n） DO（m+n）101C2（7）下面程序段的執(zhí)行次數(shù)為（B）。 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）101D3（8）下面程序的時(shí)間復(fù)雜度為（A）。 for（i=0；i<m；i+） for（j=0；j<t；j+） cij=0； for（i=0；i<m；i+） fo

4、r（j=0；j<t；j+） for（k=0；k<n；k+） cij=cij+aik*bkj； AO（m×n×t） BO（m+n+t） CO（m+n×t） DO（m×t+n）102A1（9）順序表的特點(diǎn)是（B）。 A表中元素的個(gè)數(shù)為表長 B按順序方式存儲數(shù)據(jù)元素 C邏輯結(jié)構(gòu)中相鄰的結(jié)點(diǎn)在存儲結(jié)構(gòu)中仍相鄰 D按表中元素的次序存儲102C2（10）設(shè)順序表共有n個(gè)元素，用數(shù)組elem存儲，實(shí)現(xiàn)在第i個(gè)元素之前插入一個(gè)元素e的操作，其主要語句為（D）。 AFOR j=n DOWNTO i DO elemj=elemj+1； elemi=e； BFOR

5、 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；102D2（11）順序表有5個(gè)元素，設(shè)在任何位置上插入元素是等概率的，則在該表中插入一個(gè)元素時(shí)所需移動(dòng)元素的平均次數(shù)為（C）。 A3 B2 C25 D5102D2（12）設(shè)順序表有9個(gè)元素，則在第3個(gè)元素前插入一個(gè)元素所需移動(dòng)元素的個(gè)數(shù)為（C）。 A9 B45 C7 D6102D3（13）設(shè)順序表有19個(gè)元素，第一個(gè)元素的地址為200，且每個(gè)元素占3個(gè)字

6、節(jié)，則第14個(gè)元素的存儲地址為（B）。 A236 B239 C242 D245102D2（14）設(shè)順序表的第5個(gè)元素的存儲地址為200，且每個(gè)元素占一個(gè)存儲單元，則第14個(gè)元素的存儲地址為（B）。 A208 B209 C210 D214103D3（15）設(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->llink->rlink103A1（16）線性表采用鏈?zhǔn)酱鎯r(shí)，

7、其地址（D）。 A必須是連續(xù)的 B一定是不連續(xù)的 C部分地址必須是連續(xù)的 D連續(xù)與否均可以103B1（17）線性表是（A）。 A一個(gè)有限序列，可以為空 B一個(gè)有限序列，不可以為空 C一個(gè)無限序列，可以為空 D一個(gè)無限序列，不可以為空103B1（18）鏈?zhǔn)酱鎯Φ木€性表中的指針指向其（B）。 A前趨結(jié)點(diǎn) B后繼結(jié)點(diǎn) C物理前趨 D物理后繼103C2（19）設(shè)在鏈?zhǔ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->link=q->link； p->l

8、ink=q； Cq->link=p->link； q->link=p； Dp->link=q->link； q->link=p；103C3（20）設(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=head； head=p； Dp-

9、>next=head； p= head；104A1（21）在棧中，下列說法正確的是（A）。 A每次插入總是在棧頂，每次刪除也總是在棧頂。 B每次插入總是在棧頂，每次刪除總是在棧底。 C每次插入總是在棧底，每次刪除總是在棧頂。 D每次插入總是在棧底，每次刪除也總是在棧底。104B2（22）設(shè)有一個(gè)棧，按A、B、C的順序進(jìn)棧，則下列（C）為不可能的出棧序列。 AABC BCBA CCAB DACB104B2（23）設(shè)有一個(gè)棧，按A、B、C、D的順序進(jìn)棧，則下列（D）為可能的出棧序列。 ADCAB BCDAB CDBAC DACDB104A2（24）順序棧的上溢是指（B）。 A棧滿時(shí)作退棧運(yùn)算

10、 B棧滿時(shí)作進(jìn)棧運(yùn)算 C棧空時(shí)作退棧運(yùn)算 D?？諘r(shí)作進(jìn)棧運(yùn)算104D3（25）順序棧S中top為棧頂指針，指向棧頂元素所在的位置，elem為存放棧的數(shù)組，則元素e進(jìn)棧操作的主要語句為（D）。 Aselemtop=e； stop=stop+1； Bselemtop+1=e； stop=stop+1； Cstop=stop+1； selemtop+1=e； Dstop=stop+1； selemtop=e；104C2（26）設(shè)有5個(gè)元素A，B，C，D，E順序進(jìn)棧（進(jìn)棧過程中可以出棧），出棧后依出棧次序進(jìn)入隊(duì)列，已知其出隊(duì)次序?yàn)镈，C，E，B，A，則該棧容量必定不小于（C）。 A2 B3 C4 D5

11、104B2（27）設(shè)棧S的初始狀態(tài)為空，現(xiàn)有五個(gè)元素組成的序列1，2，3，4，5，對該序列在棧S上依次進(jìn)行PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH操作，出棧的元素序列是（C）。 A5，4，3，2，1 B2，1 C2，3 D3，4104B2（28）在一個(gè)具有n個(gè)單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top為棧頂指針，則當(dāng)做出棧處理時(shí)，top變化為（C）。 Atop不變 Btop=0 Ctop- - Dtop+104D3（29）向一個(gè)棧頂指針為hs的鏈棧中插入一個(gè)*s結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行（B）。 Ahs->next=s； Bs->next=hs；hs=

12、s； Cs->next=hs->next；hs->next=s； Ds->next=hs；hs=hs->next；105A1（30）在隊(duì)列中，下列說法正確的是（A）。A每次插入總是在隊(duì)尾，每次刪除總是在隊(duì)頭。 B每次插入總是在隊(duì)尾，每次刪除也總是在隊(duì)尾。C每次插入總是在隊(duì)頭，每次刪除也總是在隊(duì)頭。 D每次插入總是在隊(duì)頭，每次刪除總是在隊(duì)尾。105D3（31）在帶頭結(jié)點(diǎn)的鏈隊(duì)列q中，用qfront表示隊(duì)頭指針，qrear表示隊(duì)尾指針，結(jié)點(diǎn)結(jié)構(gòu)為data next ，刪除鏈隊(duì)列的隊(duì)頭結(jié)點(diǎn)的主要語句為（B）。 As=qfront； qfront->next= sn

13、ext； Bs=qfront->next； qfront->next= snext； Cs=qfront->next； qfront= snext； Ds=q； qfront->next= snext；106C3（32）循環(huán)隊(duì)列sq中，用數(shù)組elem存放數(shù)據(jù)元素，sqfront指示隊(duì)頭元素的前一個(gè)位置，sqrear指示隊(duì)尾元素的當(dāng)前位置，隊(duì)列的最大容量為MAXSIZE，則隊(duì)列滿的條件為（D）。 Asqfront= sqrear Bsqfront= sqrear+1 C（sqfront +1）mod MAXSIZE= sqrear D（sqrear+1）mod MAXSI

14、ZE= sqfront106C2（33）循環(huán)隊(duì)列sq中，用數(shù)組elem存放數(shù)據(jù)元素，sqfront指示隊(duì)頭元素的前一個(gè)位置，sqrear指示隊(duì)尾元素的當(dāng)前位置，隊(duì)列的最大容量為MAXSIZE，則在隊(duì)列未滿時(shí)元素x入隊(duì)列的主要操作為（A）。 Asqrear= （sqrear+1）mod MAXSIZE； sqelemsqrear=x； Bsqelemsqrear=x； sqrear= （sqrear+1）mod MAXSIZE； Csqfront= （sqfront+1）mod MAXSIZE； sqelemsqfront=x； Dsqelemsqfront=x； sqfront= sqfron

15、t+1；106B2（34）循環(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ù)為（D）。 A8 B16 C17 D18106B2（35）設(shè)循環(huán)隊(duì)列的元素存放在一維數(shù)組Q030中，隊(duì)列非空時(shí)，front指示隊(duì)頭元素的前一個(gè)位置，rear指示隊(duì)尾元素。如果隊(duì)列中元素的個(gè)數(shù)為11，front的值為25，則rear應(yīng)指向（B）元素。 AQ4 BQ5 CQ14 DQ15105A1（36）隊(duì)列操作的原則是（A）。 A先進(jìn)先出 B后進(jìn)先出 C只能進(jìn)行插入 D只能進(jìn)行

16、刪除105B2（37）一個(gè)隊(duì)列的入列序列是1234，則隊(duì)列的輸出序列是（B）。 A4321 B1234 C1432 D3241108C2（38）設(shè)6行8列的二維數(shù)組A6×8=（aij）按行優(yōu)先順序存儲，若第一個(gè)元素的存儲位置為200，且每個(gè)元素占3個(gè)存儲單元，則元素a54的存儲位置為（B）。 A308 B305 C266 D269109C2（39）設(shè)有一個(gè)10階的對稱矩陣A，采用壓縮存儲方式，以行序?yàn)橹鞔鎯Γ琣11為第一個(gè)元素，其存儲地址為1，每元素占1個(gè)地址空間，則a85的地址為（B）。 A13 B33 C18 D40108A1（40）設(shè)二個(gè)數(shù)組為A07、B-52，38，則這兩個(gè)數(shù)

17、組分別能存放的字符的最大個(gè)數(shù)是（C）。 A7和35 B1和5 C8和48 D1和6108C3（41）二維數(shù)組Mi，j的元素是4個(gè)字符（每個(gè)字符占一個(gè)存儲單元）組成的串，行下標(biāo)i的范圍從0到4，列下列j的范圍從0到5。M按行存儲時(shí)元素M3，5的起始地址與M按列存儲時(shí)元素（B）的起始地址下同。 AM2，4 BM3，4 CM3，5 DM4，4108C2（42）設(shè)二維數(shù)組為M08，010，每個(gè)元素占2L個(gè)存儲單元，以行序?yàn)橹餍虼鎯?，第一個(gè)元素的存儲位置為P。存儲位置為P+50L的元素為（A）。 AM2，3 BM2，2 CM3，3 DM3，4108C2（43）設(shè)二維數(shù)組A的維數(shù)界偶定義為18，010，起

18、始地址為LOC，每個(gè)元素占2L個(gè)存儲單元，以行序?yàn)橹餍虼鎯Ψ绞较拢硵?shù)據(jù)元素的地址為LOC+50L，則在列序?yàn)橹餍虼鎯Ψ绞较?，該元素的存儲地址為（D）。 ALOC+28L BLOC+36L CLOC+50L DLOC+52L109B2（44）數(shù)組A140，130采用三元組表示，設(shè)數(shù)組元素與下標(biāo)均為整型，則在非零元素個(gè)數(shù)小于（D）時(shí)，才能節(jié)省存儲空間。 A1200 B401 C399 D400108A1（45）一維數(shù)組通常采用順序存儲結(jié)構(gòu)，這是因?yàn)椋–）。A一維數(shù)組是一種線性數(shù)據(jù)結(jié)構(gòu) B一維數(shù)組是一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)C一旦建立了數(shù)組，則數(shù)組中的數(shù)據(jù)元素之間的關(guān)系不再變動(dòng) D一維數(shù)組只能采用順序存儲結(jié)

19、構(gòu)109A1（46）對稀疏矩陣進(jìn)行壓縮存儲的目的是（B）。 A方便存儲 B節(jié)省存儲空間 C方便運(yùn)算 D節(jié)省運(yùn)算時(shí)間108D3（47）設(shè)二維數(shù)組a05，06按行存儲，每個(gè)元素占d個(gè)存儲單元，如果每個(gè)元素改為2d個(gè)存儲單元，起始地址不變，則元素a2，6的存儲地址將要增加（A）個(gè)存儲單元。 A20d B21d C38d D39d108B2（48）一維數(shù)組與線性表的區(qū)別是（A）。 A前者長度固定，后者長度可變 B后者長度固定，前者長度可變 C兩者長度均固定 D兩者長度均可變107A1（49）下列關(guān)于串的敘述中，不正確的是（B）。 A串是字符的有限序列 B空串是由空格構(gòu)成的串 C模式匹配是串的一種重要運(yùn)

20、算 D串既可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯?07B2（50）以下論斷正確的是（A）。 A“”是空串，“ ”是空白串 B“BEIJING”是“BEI JING”的子串 C“something”<“Somethig” D”BIT”=”BITE”107B2（51）字符串“VARTYPE unsignedint”若采用動(dòng)態(tài)分配的順序存儲方法需要（C）個(gè)字節(jié)（假設(shè)每種數(shù)據(jù)均占用2個(gè)字節(jié)）。 A38 B動(dòng)態(tài)產(chǎn)生，視情況而定 C40 D42111A1（52）由3個(gè)結(jié)點(diǎn)可以構(gòu)造出（A）種不同形態(tài)的有向樹。 A2 B3 C4 D5111A1（53）下列樹的度為（B）。 A2 B3 C5 D8 112C

21、2（54）含10個(gè)結(jié)點(diǎn)的二叉樹中，度為0的結(jié)點(diǎn)有4個(gè)，則度為2的結(jié)點(diǎn)有（A）個(gè)。 A3 B4 C5 D6111B2（55）對一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹按層編號，則編號為49的結(jié)點(diǎn)，它的左孩子的編號為（A）。 A98 B99 C97 D50112B2（56）一棵深度為8（根的層次號為1）的滿二叉樹有（B）個(gè)結(jié)點(diǎn)。 A256 B255 C128 D127112C3（57）設(shè)二叉樹根結(jié)點(diǎn)的層數(shù)為1，若一棵高（深）度為h的二叉樹只有度為0與度為2的結(jié)點(diǎn)，則其結(jié)點(diǎn)數(shù)至少為（B）。 Ah B2h-1 C2h D2h+1112C2（58）對下列二叉樹進(jìn)行先根次序遍歷，所得次序?yàn)椋ˋ）。 AABCDEF

22、BADCBFE CBCDAFE DDCBFEA112D3（59）一棵二叉樹的前（先）序序列為ABCDEFG，則它的中序序列不可能為（C）。 ACBDAFEG BDCBAEFG CCDBAGEF DBDCAFGE112A1（60）若先序遍歷二叉樹的結(jié)果為結(jié)點(diǎn)序列A，B，C，則有（C）棵不同的二叉樹可以得到這一結(jié)果。 A3 B4 C5 D6111B2（61）具有n個(gè)結(jié)點(diǎn)的二叉樹，有（B）條邊。 An Bn-1 Cn+1 D2n112C2（62）在具有n個(gè)結(jié)點(diǎn)的二叉樹的二叉鏈表表示中，2n個(gè)孩子指針域中，只用到（B）個(gè)域。 An Bn-1 Cn+1 D2n114B2（63）對哈夫曼樹，下列說法錯(cuò)誤的

23、是（B）。 A哈夫曼樹是一類帶樹路徑長度最短的樹。 B給出一組數(shù)，構(gòu)造的哈夫曼樹唯一。 C給出一組數(shù)，構(gòu)造的哈夫曼樹的帶樹路徑長度不變。 D哈夫曼樹的帶權(quán)路徑長度為每個(gè)葉子的路徑長度與該葉子權(quán)值乘積之和。111D3（64）假定在一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15個(gè)，單分支結(jié)點(diǎn)數(shù)為30個(gè)，則葉子結(jié)點(diǎn)數(shù)為（B）。 A15 B16 C17 D47113C3（65）假定一棵三叉樹的結(jié)點(diǎn)數(shù)為50，則它的最小高度為（C）。 A3 B4 C5 D6114B2（66）由帶權(quán)為9，2，5，7的四個(gè)葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長度為（D）。 A23 B37 C46 D44112C2（67）二叉樹的先序遍

24、歷為EFHIGJK，中序遍歷為HFIEJKG，則該二叉樹根的右子樹的根是（C）。 AE BF CG DH111A1（68）在完全二叉樹中，若一個(gè)結(jié)點(diǎn)是葉結(jié)點(diǎn)，則它沒有（C）。A左孩子結(jié)點(diǎn) B右孩子結(jié)點(diǎn) C左孩子和右孩子結(jié)點(diǎn) D左孩子結(jié)點(diǎn)，右孩子結(jié)點(diǎn)和兄弟結(jié)點(diǎn)113B2（69）（B）二叉樹，可以唯一地轉(zhuǎn)化成一棵一般樹。 A根結(jié)點(diǎn)無左孩子 B根結(jié)點(diǎn)無右孩子 C根據(jù)結(jié)點(diǎn)有兩個(gè)孩子 D沒有一棵111C2（70）具有65個(gè)結(jié)點(diǎn)的完全二叉樹其深度為（B）。 A8 B7 C6 D5112C2（71）某二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是（B）的二叉樹。 A空或只有一個(gè)結(jié)點(diǎn) B高度等于其結(jié)點(diǎn)數(shù)

25、 C任一結(jié)點(diǎn)無左孩子 D任一結(jié)點(diǎn)無右孩子113A1（72）下面敘述中，不正確的是（C）。 A線性表中除第一個(gè)元素和最后一個(gè)元素外，其他每個(gè)元素都有且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼 B樹中有且僅有一個(gè)結(jié)點(diǎn)沒有前驅(qū) C環(huán)形隊(duì)列中任何一個(gè)元素都有且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼 D在樹中，一個(gè)結(jié)點(diǎn)可以有多個(gè)直接后繼114B2（73）有m個(gè)葉子結(jié)點(diǎn)的哈夫曼樹，其結(jié)點(diǎn)總數(shù)是（C）。 A2m B2m+1 C2m-1 D2（m+1）115A1（74）設(shè)圖的鄰接矩陣為，則該圖有（A）個(gè)頂點(diǎn)。 A3 B4 C6 D9115B2（75）設(shè)圖的鄰接矩陣為，則該圖為（A）。 A有向圖 B無向圖 C強(qiáng)連通圖 D完全圖1

26、15B2（76）設(shè)圖的鄰接鏈表如下圖所示，則該圖有（B）條邊。 1 V1 2 3 4 2 V2 1 3 4 3 V3 1 2 4 V4 1 2 A4 B5 C10 D20115C2（77）設(shè)有6個(gè)結(jié)點(diǎn)的無向圖，該圖至少應(yīng)有（B）條邊才能確保是一個(gè)連通圖。 A5 B6 C7 D8116D3（78）已知一有向圖的鄰接表存儲結(jié)構(gòu)如下，則根據(jù)有向圖的深度優(yōu)先遍歷算法，從頂點(diǎn)V1出發(fā)，不能得到的頂點(diǎn)序列是（C）。 1 3 2 4 2 3 4 5 4 5 2 4 AV1V2V3V5V4 BV1 V3 V4V5V2 CV1V2V4V5V3 DV1 V4V3V5V2 119C3（79）下列圖的深度優(yōu)先遍歷序列

27、為（B）。 A B CD E F G H AABCDEFGH BABDHECFG CABEDHCFG DABCFGEDH115B1（80）對一個(gè)具有n個(gè)頂點(diǎn)的圖，采用鄰接矩陣表示則該矩陣的大小為（D）。 An B（n-1）2 C（n+1）2 Dn2 118B2（81）對含n個(gè)記錄的順序表進(jìn)行順序查找，在最壞情況下需要比較（B）次。 An-1 Bn C（n+1）/2 Dn（n-1）/2118B2（82）對含n個(gè)記錄的有序表進(jìn)行折半查找，設(shè)每個(gè)記錄的查找概率相等，則平均查找長度的數(shù)量級為（C）。 AO（n） BO（n2） CO（） DO（1）119B2（83）有一棵二叉樹如下圖，該樹是（B）。 5

28、0 20 95 10 30 55 70 85 A二叉平衡樹 B二叉排序樹 C堆的形狀 D以上都不是119C3（84）已知10個(gè)數(shù)據(jù)元素（50，30，15，35，70，65，95，60，25，40），按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹后，在查找成功的情況下，查找每個(gè)元素的平均比較次數(shù)（又稱平均查找長度）為（C）。 A2.5 B3.2 C2.9 D2.7118C3（85）在順序存儲的線性表R029上進(jìn)行分塊查找（設(shè)分為5塊）的平均查找長度為（D）。 A6 B11 C5 D6.5120D3（86）已知一個(gè)線性表（38，25，74，63，52，48），假定采用h（k）=k%7計(jì)算散列地址進(jìn)行散列

29、存儲，若引用線性探測的開放定地址法解決沖突，則在該散列表上進(jìn)行查找的平均查找長度為（C）。 A1.5 B1.7 C2 D2.3119A1（87）在一個(gè)3階的B-樹上，每個(gè)結(jié)點(diǎn)包含的子樹相同，最多為（C）。 A1 B2 C3 D4120B2（88）設(shè)散列地址空間為0m-1，k為關(guān)鍵字，用P去除k，將余數(shù)作為k的散列地址，即：h（k）=k%P，為了減少發(fā)生沖突的可能性，一般取P為（B）。A小于m的最大奇數(shù) B小于m的最大素?cái)?shù) C小于m的最大偶數(shù) D小于m的最大合數(shù)120C3（89）設(shè)散列表表長m=14，散列函數(shù)為h（k）=k%11，表中已有4個(gè)記錄，如果用二次探測再散列處理沖突，關(guān)鍵字為49的記錄

30、的存儲地址是（D）。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 15 38 61 84 A8 B3 C5 D9119C3（90）已知8個(gè)元素（34，76，45，18，26，54，92，65），按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹，該樹的深度為（C）。 A4 B5 C6 D7121B1（91）直接插入排序算法的時(shí)間復(fù)雜度為（B）。 AO（n） BO（n2） CO（） DO（1）121B2（92）設(shè)記錄關(guān)鍵字序列為（84，67，21，50，33，79），采用對半插入排序方法自小到大進(jìn)行排序時(shí)，記錄的移動(dòng)次數(shù)為（C）。 A9 B10 C19 D25123D3（93）下列四個(gè)

31、序列中，（D）不是快速排序第一趟的可能結(jié)果。 A68，11，69，23，18，70，73 93 B11 68，69，23，18，70，73，93 C68，11，69，23，18 70 93，73 D18，11，23 93 68，70，69，73122C3（94）下列四個(gè)關(guān)鍵字序列中，（C）不是堆。 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，94123B2（95）從未排序序列中依次取出元素與已排序序列中的元素作比較，將其放入已排序序列中的正確位置

32、上，此方法稱為（D）。 A歸并排序 B選擇排序 C交換排序 D插入排序123B2（96）在所有排序方法中，關(guān)鍵字的比較次數(shù)與記錄的初始排列無關(guān)的是（D）。 AShell排序 B冒泡排序 C直接插入排序 D直接選擇排序123B2（97）下列排序算法中，第一趟排序后，任一元素都不能確定其最終位置的算法是（B）。 A選擇 B插入 C冒泡 D快速123C2（98）采用下列排序算法對n個(gè)元素進(jìn)行排序，其排序趟數(shù)肯定為n-1趟的排序方法有（A）。 A選擇和插入 B冒泡和快速 C插入和快速 D選擇和冒泡123D3（99）若用冒泡排序方法對序列10，14，26，29，41，52從大到小進(jìn)行排序，需要進(jìn)行（C）

33、次比較。 A5 B10 C15 D25121C3（100）用直接插入排序方法對下面四個(gè)序列進(jìn)行排序（由小到大），元素比較次數(shù)最少的是（C）。 A94，32，40，90，80，46，21，69 B32，40，21，46，69，94，90，80 C21，32，46，40，80，69，90，94 D90，69，80，46，21，32，94，40二、填空題101A1（1）數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是（線性結(jié)構(gòu)和非線性結(jié)構(gòu)）。101A1（2）算法的計(jì)算量的大小稱為（計(jì)算的復(fù)雜度）。102B2（3）順序存儲的線性表，設(shè)其長度為n，在任何位置上插入或刪除操作的時(shí)間代價(jià)基本上都是等效的。則插入一

34、個(gè)元素大約要移動(dòng)表中的（n/2）個(gè)元素。103A2（4）順序表相對于鏈表的優(yōu)點(diǎn)有（節(jié)省存儲）和（隨機(jī)存取）。103B2（5）線性表的長度是（表中數(shù)據(jù)元素的個(gè)數(shù)）。103D3（6）在帶有頭結(jié)點(diǎn)的雙鏈表L中，指針p所指結(jié)點(diǎn)是第一個(gè)元素結(jié)點(diǎn)的條件是（p=L->next；或L->next=p；）。103C3（7）某鏈表如下所示 info link p A B C D E 若要?jiǎng)h除值為C的結(jié)點(diǎn)，應(yīng)做操作（p->link=p->link->link）。104A1（8）對于棧只能在（棧頂）插入和刪除元素。104C2（9）設(shè)有一空棧，現(xiàn)有輸入序列1，2，3，4，5，6，經(jīng)過pus

35、h，push，pop，push，pop，push，push后，輸出序列是（2、3）。106B2（10）有一個(gè)循環(huán)隊(duì)列如下圖，其隊(duì)滿條件是（front=(rear+1)%n），隊(duì)列空的條件是（rear=front）。 front 隊(duì)頭指針 rear 隊(duì)尾指針109B2（11）一個(gè)稀疏矩陣為，則對應(yīng)的三元組線性表為（0，2，2），（1，0，3），（2，2，-1），（2，3，5）。108C2（12）設(shè)有二維數(shù)組A09，019，其每個(gè)元素占兩個(gè)字節(jié)，數(shù)組按列優(yōu)先順序存儲，第一個(gè)元素的存儲地址為100，那么元素A6，6的存儲地址為（232）。112B1（13）在一棵二叉排序樹上按（中序）遍歷得到的結(jié)點(diǎn)序

36、列是一個(gè)有序序列。111C3（14）對于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)進(jìn)行鏈接存儲時(shí)，其二叉鏈表中的指針域的總數(shù)為2n個(gè)，其中（n-1）個(gè)用于鏈接孩子結(jié)點(diǎn)。112B2（15）對于下面的二叉樹，按后序遍歷得到的結(jié)點(diǎn)序列為（4，2，5，6，3，1）。 1 2 3 4 5 6115B1（16）設(shè)無向圖G的頂點(diǎn)數(shù)為n，圖G最少有（0）邊。117C3（17）對下列圖 1 6 2 5 3 4它的生成樹有（6）棵。118C3（18）假定在有序表R019上進(jìn)行二分查找，則比較三次查找成功的結(jié)點(diǎn)數(shù)為（4）。120D3（19）設(shè)有兩個(gè)散列函數(shù)H1（K）=K mod 13和H2（K）=K mod 11+1，散列表為T

37、012，用雙重散列法（又稱二次散列法）解決沖突。函數(shù)H1用來計(jì)算散列地址，當(dāng)發(fā)生沖突時(shí)，H2作為計(jì)算下一個(gè)探測地址的地址增量。假定某一時(shí)刻散列表T的狀態(tài)為： 0 1 2 3 4 5 6 7 8 9 10 11 12 T： 80 55 34下一個(gè)被插入的關(guān)鍵碼為42，其插入位置是（0）。122C3（20）已知一棵二叉排序樹如下圖所示，則在查找成功的情況下查找每個(gè)元素的平均查找長度為（2.75）。 80 50 90 40 70 100 60 75三、完形填空題102D2（1）設(shè)順序存儲的線性表存儲結(jié)構(gòu)定義為： struct sequnce ELEMTP elemMAXSIZE； int len；

38、/*線性表長度域*/ 將下列簡單插入算法補(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； 103D3（2）設(shè)線性鏈表的存儲結(jié)構(gòu)如下： struct node ELEMTP data； /*數(shù)據(jù)域*/ struct node *next； /*指針域*/ 試完成下列在鏈表中值為x的結(jié)點(diǎn)前插入一

39、個(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->nexr=head；head=s； else q=head；p=q->next； while（p->dqta!=x&&p->next!=NULL）q=p；p=p->next； if（p->data= = x）q->

40、next=s；s->next=p； elsep->next=s；s->next=NULL； 103D3（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=（ struct node *）malloc（sizeof（st

41、ruct node）； ptr->data= var ；ptr->next=head->next； head->next= ptr ； 103D3（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初始指向開始結(jié)點(diǎn)/ while（p） /處理當(dāng)前結(jié)點(diǎn)p/ q=p； r=q->next； do /刪除與結(jié)點(diǎn)*p的值相同的結(jié)點(diǎn)/ while（r&

42、;&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； 106D3（5）假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針R指向隊(duì)尾元素結(jié)點(diǎn)（注意不設(shè)頭指針），下列為出隊(duì)一個(gè)元素的算法。DeList（R，e）LinkList *R，p；ElemType e；p=R->next->next；e=p->data；R->next->next=p->next；if（p= =R）R=R->next；free（p）； 105D3（6）鏈隊(duì)列的存儲結(jié)構(gòu)為： struct nodetype ELEMTP data； struct nodetype *next； struct linkqueue struct nod