數(shù)據(jù)結(jié)構(gòu)習(xí)題庫(kù)數(shù)據(jù)結(jié)構(gòu)習(xí)題庫(kù)數(shù)據(jù)結(jié)構(gòu)習(xí)題庫(kù)數(shù)據(jù)結(jié)構(gòu)習(xí)題庫(kù)編制僅供參考審核批準(zhǔn)生效日期地址：電話：傳真:郵編:知識(shí)點(diǎn)：01．緒論02．順序表03．鏈表04．棧05．鏈隊(duì)列06．循環(huán)隊(duì)列07．串08．?dāng)?shù)組的順序表示09．稀疏矩陣10．廣義表11．二叉樹的基本概念12．二叉樹遍歷、二叉樹性質(zhì)13．樹、樹與二叉樹的轉(zhuǎn)換14．赫夫曼樹15．圖的定義、圖的存儲(chǔ)16．圖的遍歷17．圖的生成樹18．靜態(tài)查找（順序表的查找、有序表的查找）19．動(dòng)態(tài)查找（二叉排序樹、平衡樹、B樹）20．哈希查找21．插入排序（直接插入、折半插入、2路插入、希爾排序）22．選擇排序（簡(jiǎn)單選擇、樹形選擇、堆排序）23．快速排序、歸并排序

101A1（1）．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)是（A）。A．?dāng)?shù)據(jù)的組織形式B．?dāng)?shù)據(jù)的存儲(chǔ)形式C．?dāng)?shù)據(jù)的表示形式D．?dāng)?shù)據(jù)的實(shí)現(xiàn)形式101A1（2）．組成數(shù)據(jù)的基本單位是（C）。A．?dāng)?shù)據(jù)項(xiàng)B．?dāng)?shù)據(jù)類型C．?dāng)?shù)據(jù)元素D．?dāng)?shù)據(jù)變量101B1（3）．與順序存儲(chǔ)結(jié)構(gòu)相比，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)密度（B）。A．大B．小C．相同D．以上都不對(duì)101B2（4）．對(duì)于存儲(chǔ)同樣一組數(shù)據(jù)元素而言，（D）。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)不要求整塊空間101B2（5）．下面程序的時(shí)間復(fù)雜度為（B）。x=0；for（i=1；i<n；i++）for（j=i+1；j<=n；j++）x++；A．O（）B．O（n2）C．O（1）D．O（n）101B2（6）．下面程序的時(shí)間復(fù)雜度為（C）。for（i=0；i<m；i++）for（j=0；j<n；j++）A[i][j]=i*j；A．O（m2）B．O（n2）C．O（m×n）D．O（m+n）101C2（7）．下面程序段的執(zhí)行次數(shù)為（B）。for（i=0；i<n-1；i++）for（j=0；j>i；j++）state；A．n（n+1）/2B．（n-1）（n+2）/2C．n（n+1）/2D．（n-1）（n+2）101D3（8）．下面程序的時(shí)間復(fù)雜度為（A）。for（i=0；i<m；i++）for（j=0；j<t；j++）c[i][j]=0；for（i=0；i<m；i++）for（j=0；j<t；j++）for（k=0；k<n；k++）c[i][j]=c[i][j]+a[i][k]*b[k][j]；A．O（m×n×t）B．O（m+n+t）C．O（m+n×t）D．O（m×t+n）102A1（9）．順序表的特點(diǎn)是（B）。A．表中元素的個(gè)數(shù)為表長(zhǎng)B．按順序方式存儲(chǔ)數(shù)據(jù)元素C．邏輯結(jié)構(gòu)中相鄰的結(jié)點(diǎn)在存儲(chǔ)結(jié)構(gòu)中仍相鄰D．按表中元素的次序存儲(chǔ)102C2（10）．設(shè)順序表共有n個(gè)元素，用數(shù)組elem存儲(chǔ)，實(shí)現(xiàn)在第i個(gè)元素之前插入一個(gè)元素e的操作，其主要語(yǔ)句為（D）。A．FORj=nDOWNTOiDOelem[j]=elem[j+1]；elem[i]=e；B．FORj=iTOnDOelem[j]=elem[j+1]；elem[i]=e；C．FORj=iTOnDOelem[j+1]=elem[j]；elem[i]=e；D．FORj=nDOWNTOiDOelem[j+1]=elem[j]；elem[i]=e；102D2（11）．順序表有5個(gè)元素，設(shè)在任何位置上插入元素是等概率的，則在該表中插入一個(gè)元素時(shí)所需移動(dòng)元素的平均次數(shù)為（C）。A．3B．2C．2．5D．5102D2（12）．設(shè)順序表有9個(gè)元素，則在第3個(gè)元素前插入一個(gè)元素所需移動(dòng)元素的個(gè)數(shù)為（C）。A．9B．4．5C．7D．6102D3（13）．設(shè)順序表有19個(gè)元素，第一個(gè)元素的地址為200，且每個(gè)元素占3個(gè)字節(jié)，則第14個(gè)元素的存儲(chǔ)地址為（B）。A．236B．239C．242D．245102D2（14）．設(shè)順序表的第5個(gè)元素的存儲(chǔ)地址為200，且每個(gè)元素占一個(gè)存儲(chǔ)單元，則第14個(gè)元素的存儲(chǔ)地址為（B）。A．208B．209C．210D．214103D3（15）．設(shè)p為指向雙向循環(huán)鏈表中某個(gè)結(jié)點(diǎn)的指針，p所指向的結(jié)點(diǎn)的兩個(gè)鏈域分別用p->llink和p->rlink表示，則下列等式中（D）成立。A．p=p->llinkB．p=p->rlinkC．p=p->llink->llinkD．p=p->llink->rlink103A1（16）．線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址（D）。A．必須是連續(xù)的B．一定是不連續(xù)的C．部分地址必須是連續(xù)的D．連續(xù)與否均可以103B1（17）．線性表是（A）。A．一個(gè)有限序列，可以為空B．一個(gè)有限序列，不可以為空C．一個(gè)無(wú)限序列，可以為空D．一個(gè)無(wú)限序列，不可以為空103B1（18）．鏈?zhǔn)酱鎯?chǔ)的線性表中的指針指向其（B）。A．前趨結(jié)點(diǎn)B．后繼結(jié)點(diǎn)C．物理前趨D．物理后繼103C2（19）．設(shè)在鏈?zhǔn)酱鎯?chǔ)的線性表中，設(shè)結(jié)點(diǎn)結(jié)構(gòu)為datalink，欲在p結(jié)點(diǎn)后插入一個(gè)結(jié)點(diǎn)q的關(guān)鍵步驟為（A）。A．q->link=p->link；p->link=q；B．p->link=q->link；p->link=q；C．q->link=p->link；q->link=p；D．p->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)的鏈域）。A．p->next=head->next；head->next=p；B．p->next=head->next；head=p；C．p->next=head；head=p；D．p->next=head；p=head；104A1（21）．在棧中，下列說(shuō)法正確的是（A）。A．每次插入總是在棧頂，每次刪除也總是在棧頂。B．每次插入總是在棧頂，每次刪除總是在棧底。C．每次插入總是在棧底，每次刪除總是在棧頂。D．每次插入總是在棧底，每次刪除也總是在棧底。104B2（22）．設(shè)有一個(gè)棧，按A、B、C的順序進(jìn)棧，則下列（C）為不可能的出棧序列。A．ABCB．CBAC．CABD．ACB104B2（23）．設(shè)有一個(gè)棧，按A、B、C、D的順序進(jìn)棧，則下列（D）為可能的出棧序列。A．DCABB．CDABC．DBACD．ACDB104A2（24）．順序棧的上溢是指（B）。A．棧滿時(shí)作退棧運(yùn)算B．棧滿時(shí)作進(jìn)棧運(yùn)算C．?？諘r(shí)作退棧運(yùn)算D．?？諘r(shí)作進(jìn)棧運(yùn)算104D3（25）．順序棧S中top為棧頂指針，指向棧頂元素所在的位置，elem為存放棧的數(shù)組，則元素e進(jìn)棧操作的主要語(yǔ)句為（D）。A．s．elem[top]=e；s．top=s．top+1；B．s．elem[top+1]=e；s．top=s．top+1；C．s．top=s．top+1；s．elem[top+1]=e；D．s．top=s．top+1；s．elem[top]=e；104C2（26）．設(shè)有5個(gè)元素A，B，C，D，E順序進(jìn)棧（進(jìn)棧過(guò)程中可以出棧），出棧后依出棧次序進(jìn)入隊(duì)列，已知其出隊(duì)次序?yàn)镈，C，E，B，A，則該棧容量必定不小于（C）。A．2B．3C．4D．5104B2（27）．設(shè)棧S的初始狀態(tài)為空，現(xiàn)有五個(gè)元素組成的序列1，2，3，4，5，對(duì)該序列在棧S上依次進(jìn)行PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH操作，出棧的元素序列是（C）。A．5，4，3，2，1B．2，1C．2，3D．3，4104B2（28）．在一個(gè)具有n個(gè)單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top為棧頂指針，則當(dāng)做出棧處理時(shí)，top變化為（C）。A．top不變B．top=0C．top--D．top++104D3（29）．向一個(gè)棧頂指針為hs的鏈棧中插入一個(gè)*s結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行（B）。A．hs->next=s；B．s->next=hs；hs=s；C．s->next=hs->next；hs->next=s；D．s->next=hs；hs=hs->next；105A1（30）．在隊(duì)列中，下列說(shuō)法正確的是（A）。A．每次插入總是在隊(duì)尾，每次刪除總是在隊(duì)頭。B．每次插入總是在隊(duì)尾，每次刪除也總是在隊(duì)尾。C．每次插入總是在隊(duì)頭，每次刪除也總是在隊(duì)頭。D．每次插入總是在隊(duì)頭，每次刪除總是在隊(duì)尾。105D3（31）．在帶頭結(jié)點(diǎn)的鏈隊(duì)列q中，用q．front表示隊(duì)頭指針，q．rear表示隊(duì)尾指針，結(jié)點(diǎn)結(jié)構(gòu)為datanext，刪除鏈隊(duì)列的隊(duì)頭結(jié)點(diǎn)的主要語(yǔ)句為（B）。A．s=q．front；q．front->next=s．next；B．s=q．front->next；q．front->next=s．next；C．s=q．front->next；q．front=s．next；D．s=q；q．front->next=s．next；106C3（32）．循環(huán)隊(duì)列sq中，用數(shù)組elem存放數(shù)據(jù)元素，sq．front指示隊(duì)頭元素的前一個(gè)位置，sq．rear指示隊(duì)尾元素的當(dāng)前位置，隊(duì)列的最大容量為MAXSIZE，則隊(duì)列滿的條件為（D）。A．sq．front=sq．rearB．sq．front=sq．rear+1C．（sq．front+1）modMAXSIZE=sq．rearD．（sq．rear+1）modMAXSIZE=sq．front106C2（33）．循環(huán)隊(duì)列sq中，用數(shù)組elem存放數(shù)據(jù)元素，sq．front指示隊(duì)頭元素的前一個(gè)位置，sq．rear指示隊(duì)尾元素的當(dāng)前位置，隊(duì)列的最大容量為MAXSIZE，則在隊(duì)列未滿時(shí)元素x入隊(duì)列的主要操作為（A）。A．sq．rear=（sq．rear+1）modMAXSIZE；sq．elem[sq．rear]=x；B．sq．elem[sq．rear]=x；sq．rear=（sq．rear+1）modMAXSIZE；C．sq．front=（sq．front+1）modMAXSIZE；sq．elem[sq．front]=x；D．sq．elem[sq．front]=x；sq．front=sq．front+1；106B2（34）．循環(huán)隊(duì)列sq中，用數(shù)組elem[0‥25]存放數(shù)據(jù)元素，sq．front指示隊(duì)頭元素的前一個(gè)位置，sq．rear指示隊(duì)尾元素的當(dāng)前位置，設(shè)當(dāng)前sq．front為20，sq．rear為12，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為（D）。A．8B．16C．17D．18106B2（35）．設(shè)循環(huán)隊(duì)列的元素存放在一維數(shù)組Q[0‥30]中，隊(duì)列非空時(shí)，front指示隊(duì)頭元素的前一個(gè)位置，rear指示隊(duì)尾元素。如果隊(duì)列中元素的個(gè)數(shù)為11，front的值為25，則rear應(yīng)指向（B）元素。A．Q[4]B．Q[5]C．Q[14]D．Q[15]105A1（36）．隊(duì)列操作的原則是（A）。A．先進(jìn)先出B．后進(jìn)先出C．只能進(jìn)行插入D．只能進(jìn)行刪除105B2（37）．一個(gè)隊(duì)列的入列序列是1234，則隊(duì)列的輸出序列是（B）。A．4321B．1234C．1432D．3241108C2（38）．設(shè)6行8列的二維數(shù)組A6×8=（aij）按行優(yōu)先順序存儲(chǔ)，若第一個(gè)元素的存儲(chǔ)位置為200，且每個(gè)元素占3個(gè)存儲(chǔ)單元，則元素a54的存儲(chǔ)位置為（B）。A．308B．305C．266D．269109C2（39）．設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第一個(gè)元素，其存儲(chǔ)地址為1，每元素占1個(gè)地址空間，則a85的地址為（B）。A．13B．33C．18D．40108A1（40）．設(shè)二個(gè)數(shù)組為A[0‥7]、B[-5‥2，3‥8]，則這兩個(gè)數(shù)組分別能存放的字符的最大個(gè)數(shù)是（C）。A．7和35B．1和5C．8和48D．1和6108C3（41）．二維數(shù)組M[i，j]的元素是4個(gè)字符（每個(gè)字符占一個(gè)存儲(chǔ)單元）組成的串，行下標(biāo)i的范圍從0到4，列下列j的范圍從0到5。M按行存儲(chǔ)時(shí)元素M[3，5]的起始地址與M按列存儲(chǔ)時(shí)元素（B）的起始地址下同。A．M[2，4]B．M[3，4]C．M[3，5]D．M[4，4]108C2（42）．設(shè)二維數(shù)組為M[0‥8，0‥10]，每個(gè)元素占2L個(gè)存儲(chǔ)單元，以行序?yàn)橹餍虼鎯?chǔ)，第一個(gè)元素的存儲(chǔ)位置為P。存儲(chǔ)位置為P+50L的元素為（A）。A．M[2，3]B．M[2，2]C．M[3，3]D．M[3，4]108C2（43）．設(shè)二維數(shù)組A的維數(shù)界偶定義為[1‥8，0‥10]，起始地址為L(zhǎng)OC，每個(gè)元素占2L個(gè)存儲(chǔ)單元，以行序?yàn)橹餍虼鎯?chǔ)方式下，某數(shù)據(jù)元素的地址為L(zhǎng)OC+50L，則在列序?yàn)橹餍虼鎯?chǔ)方式下，該元素的存儲(chǔ)地址為（D）。A．LOC+28LB．LOC+36LC．LOC+50LD．LOC+52L109B2（44）．?dāng)?shù)組A[1‥40，1‥30]采用三元組表示，設(shè)數(shù)組元素與下標(biāo)均為整型，則在非零元素個(gè)數(shù)小于（D）時(shí)，才能節(jié)省存儲(chǔ)空間。A．1200B．401C．399D．400108A1（45）．一維數(shù)組通常采用順序存儲(chǔ)結(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ù)組只能采用順序存儲(chǔ)結(jié)構(gòu)109A1（46）．對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)的目的是（B）。A．方便存儲(chǔ)B．節(jié)省存儲(chǔ)空間C．方便運(yùn)算D．節(jié)省運(yùn)算時(shí)間108D3（47）．設(shè)二維數(shù)組a[0‥5，0‥6]按行存儲(chǔ)，每個(gè)元素占d個(gè)存儲(chǔ)單元，如果每個(gè)元素改為2d個(gè)存儲(chǔ)單元，起始地址不變，則元素a[2，6]的存儲(chǔ)地址將要增加（A）個(gè)存儲(chǔ)單元。A．20dB．21dC．38dD．39d108B2（48）．一維數(shù)組與線性表的區(qū)別是（A）。A．前者長(zhǎng)度固定，后者長(zhǎng)度可變B．后者長(zhǎng)度固定，前者長(zhǎng)度可變C．兩者長(zhǎng)度均固定D．兩者長(zhǎng)度均可變107A1（49）．下列關(guān)于串的敘述中，不正確的是（B）。A．串是字符的有限序列B．空串是由空格構(gòu)成的串C．模式匹配是串的一種重要運(yùn)算D．串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)107B2（50）．以下論斷正確的是（A）。A．“”是空串，“”是空白串B．“BEIJING”是“BEIJING”的子串C．“something”<“Somethig”D．”BIT”=”BITE”107B2（51）．字符串“VARTYPEunsignedint”若采用動(dòng)態(tài)分配的順序存儲(chǔ)方法需要（C）個(gè)字節(jié)（假設(shè)每種數(shù)據(jù)均占用2個(gè)字節(jié)）。A．38B．動(dòng)態(tài)產(chǎn)生，視情況而定C．40D．42111A1（52）．由3個(gè)結(jié)點(diǎn)可以構(gòu)造出（A）種不同形態(tài)的有向樹。A．2B．3C．4D．5111A1（53）．下列樹的度為（B）。A．2B．3C．5D．8112C2（54）．含10個(gè)結(jié)點(diǎn)的二叉樹中，度為0的結(jié)點(diǎn)有4個(gè)，則度為2的結(jié)點(diǎn)有（A）個(gè)。A．3B．4C．5D．6111B2（55）．對(duì)一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹按層編號(hào)，則編號(hào)為49的結(jié)點(diǎn)，它的左孩子的編號(hào)為（A）。A．98B．99C．97D．50112B2（56）．一棵深度為8（根的層次號(hào)為1）的滿二叉樹有（B）個(gè)結(jié)點(diǎn)。A．256B．255C．128D．127112C3（57）．設(shè)二叉樹根結(jié)點(diǎn)的層數(shù)為1，若一棵高（深）度為h的二叉樹只有度為0與度為2的結(jié)點(diǎn)，則其結(jié)點(diǎn)數(shù)至少為（B）。A．hB．2h-1C．2hD．2h+1112C2（58）．對(duì)下列二叉樹進(jìn)行先根次序遍歷，所得次序?yàn)椋ˋ）。A．ABCDEFB．ADCBFEC．BCDAFED．DCBFEA112D3（59）．一棵二叉樹的前（先）序序列為ABCDEFG，則它的中序序列不可能為（C）。A．CBDAFEGB．DCBAEFGC．CDBAGEFD．BDCAFGE112A1（60）．若先序遍歷二叉樹的結(jié)果為結(jié)點(diǎn)序列A，B，C，則有（C）棵不同的二叉樹可以得到這一結(jié)果。A．3B．4C．5D．6111B2（61）．具有n個(gè)結(jié)點(diǎn)的二叉樹，有（B）條邊。A．nB．n-1C．n+1D．2n112C2（62）．在具有n個(gè)結(jié)點(diǎn)的二叉樹的二叉鏈表表示中，2n個(gè)孩子指針域中，只用到（B）個(gè)域。A．nB．n-1C．n+1D．2n114B2（63）．對(duì)哈夫曼樹，下列說(shuō)法錯(cuò)誤的是（B）。A．哈夫曼樹是一類帶樹路徑長(zhǎng)度最短的樹。B．給出一組數(shù)，構(gòu)造的哈夫曼樹唯一。C．給出一組數(shù)，構(gòu)造的哈夫曼樹的帶樹路徑長(zhǎng)度不變。D．哈夫曼樹的帶權(quán)路徑長(zhǎng)度為每個(gè)葉子的路徑長(zhǎng)度與該葉子權(quán)值乘積之和。111D3（64）．假定在一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15個(gè)，單分支結(jié)點(diǎn)數(shù)為30個(gè)，則葉子結(jié)點(diǎn)數(shù)為（B）。A．15B．16C．17D．47113C3（65）．假定一棵三叉樹的結(jié)點(diǎn)數(shù)為50，則它的最小高度為（C）。A．3B．4C．5D．6114B2（66）．由帶權(quán)為9，2，5，7的四個(gè)葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長(zhǎng)度為（D）。A．23B．37C．46D．44112C2（67）．二叉樹的先序遍歷為EFHIGJK，中序遍歷為HFIEJKG，則該二叉樹根的右子樹的根是（C）。A．EB．FC．GD．H111A1（68）．在完全二叉樹中，若一個(gè)結(jié)點(diǎn)是葉結(jié)點(diǎn)，則它沒(méi)有（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)無(wú)左孩子B．根結(jié)點(diǎn)無(wú)右孩子C．根據(jù)結(jié)點(diǎn)有兩個(gè)孩子D．沒(méi)有一棵111C2（70）．具有65個(gè)結(jié)點(diǎn)的完全二叉樹其深度為（B）。A．8B．7C．6D．5112C2（71）．某二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是（B）的二叉樹。A．空或只有一個(gè)結(jié)點(diǎn)B．高度等于其結(jié)點(diǎn)數(shù)C．任一結(jié)點(diǎn)無(wú)左孩子D．任一結(jié)點(diǎn)無(wú)右孩子113A1（72）．下面敘述中，不正確的是（C）。A．線性表中除第一個(gè)元素和最后一個(gè)元素外，其他每個(gè)元素都有且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼B．樹中有且僅有一個(gè)結(jié)點(diǎn)沒(méi)有前驅(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）。A．2mB．2m+1C．2m-1D．2（m+1）115A1（74）．設(shè)圖的鄰接矩陣為，則該圖有（A）個(gè)頂點(diǎn)。A．3B．4C．6D．9115B2（75）．設(shè)圖的鄰接矩陣為，則該圖為（A）。A．有向圖B．無(wú)向圖C．強(qiáng)連通圖D．完全圖115B2（76）．設(shè)圖的鄰接鏈表如下圖所示，則該圖有（B）條邊。1V1234^2V2134^3V312^4V412^A．4B．5C．10D．20115C2（77）．設(shè)有6個(gè)結(jié)點(diǎn)的無(wú)向圖，該圖至少應(yīng)有（B）條邊才能確保是一個(gè)連通圖。A．5B．6C．7D．8116D3（78）．已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下，則根據(jù)有向圖的深度優(yōu)先遍歷算法，從頂點(diǎn)V1出發(fā)，不能得到的頂點(diǎn)序列是（C）。1324^2^345^4^524^A．V1V2V3V5V4B．V1V3V4V5V2C．V1V2V4V5V3D．V1V4V3V5V2119C3（79）．下列圖的深度優(yōu)先遍歷序列為（B）。ABCDEFGABCDEFGH115B1（80）．對(duì)一個(gè)具有n個(gè)頂點(diǎn)的圖，采用鄰接矩陣表示則該矩陣的大小為（D）。A．nB．（n-1）2C．（n+1）2D．n2118B2（81）．對(duì)含n個(gè)記錄的順序表進(jìn)行順序查找，在最壞情況下需要比較（B）次。A．n-1B．nC．（n+1）/2D．n（n-1）/2118B2（82）．對(duì)含n個(gè)記錄的有序表進(jìn)行折半查找，設(shè)每個(gè)記錄的查找概率相等，則平均查找長(zhǎng)度的數(shù)量級(jí)為（C）。A．O（n）B．O（n2）C．O（）D．O（1）119B2（83）．有一棵二叉樹如下圖，該樹是（B）。5020951030557085A．二叉平衡樹B．二叉排序樹C．堆的形狀D．以上都不是119C3（84）．已知10個(gè)數(shù)據(jù)元素（50，30，15，35，70，65，95，60，25，40），按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹后，在查找成功的情況下，查找每個(gè)元素的平均比較次數(shù)（又稱平均查找長(zhǎng)度）為（C）。A．B．C．D．118C3（85）．在順序存儲(chǔ)的線性表R[0‥29]上進(jìn)行分塊查找（設(shè)分為5塊）的平均查找長(zhǎng)度為（D）。A．6B．11C．5D．120D3（86）．已知一個(gè)線性表（38，25，74，63，52，48），假定采用h（k）=k%7計(jì)算散列地址進(jìn)行散列存儲(chǔ)，若引用線性探測(cè)的開放定地址法解決沖突，則在該散列表上進(jìn)行查找的平均查找長(zhǎng)度為（C）。A．B．C．2D．119A1（87）．在一個(gè)3階的B-樹上，每個(gè)結(jié)點(diǎn)包含的子樹相同，最多為（C）。A．1B．2C．3D．4120B2（88）．設(shè)散列地址空間為0~m-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è)散列表表長(zhǎng)m=14，散列函數(shù)為h（k）=k%11，表中已有4個(gè)記錄，如果用二次探測(cè)再散列處理沖突，關(guān)鍵字為49的記錄的存儲(chǔ)地址是（D）。01234567891011121315386184A．8B．3C．5D．9119C3（90）．已知8個(gè)元素（34，76，45，18，26，54，92，65），按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹，該樹的深度為（C）。A．4B．5C．6D．7121B1（91）．直接插入排序算法的時(shí)間復(fù)雜度為（B）。A．O（n）B．O（n2）C．O（）D．O（1）121B2（92）．設(shè)記錄關(guān)鍵字序列為（84，67，21，50，33，79），采用對(duì)半插入排序方法自小到大進(jìn)行排序時(shí)，記錄的移動(dòng)次數(shù)為（C）。A．9B．10C．19D．25123D3（93）．下列四個(gè)序列中，（D）不是快速排序第一趟的可能結(jié)果。A．[68，11，69，23，18，70，73]93B．11[68，69，23，18，70，73，93]C．[68，11，69，23，18]70[93，73]D．[18，11，23]93[68，70，69，73]122C3（94）．下列四個(gè)關(guān)鍵字序列中，（C）不是堆。A．{05，23，16，68，94，72，71，73}B．{05，16，23，68，94，72，71，73}C．{05，23，16，73，94，72，71，68}D．{05，23，16，68，73，71，72，94}123B2（95）．從未排序序列中依次取出元素與已排序序列中的元素作比較，將其放入已排序序列中的正確位置上，此方法稱為（D）。A．歸并排序B．選擇排序C．交換排序D．插入排序123B2（96）．在所有排序方法中，關(guān)鍵字的比較次數(shù)與記錄的初始排列無(wú)關(guān)的是（D）。A．Shell排序B．冒泡排序C．直接插入排序D．直接選擇排序123B2（97）．下列排序算法中，第一趟排序后，任一元素都不能確定其最終位置的算法是（B）。A．選擇B．插入C．冒泡D．快速123C2（98）．采用下列排序算法對(duì)n個(gè)元素進(jìn)行排序，其排序趟數(shù)肯定為n-1趟的排序方法有（A）。A．選擇和插入B．冒泡和快速C．插入和快速D．選擇和冒泡123D3（99）．若用冒泡排序方法對(duì)序列{10，14，26，29，41，52}從大到小進(jìn)行排序，需要進(jìn)行（C）次比較。A．5B．10C．15D．25121C3（100）．用直接插入排序方法對(duì)下面四個(gè)序列進(jìn)行排序（由小到大），元素比較次數(shù)最少的是（C）。A．94，32，40，90，80，46，21，69B．32，40，21，46，69，94，90，80C．21，32，46，40，80，69，90，94D．90，69，80，46，21，32，94，40

二、填空題101A1（1）．?dāng)?shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是（線性結(jié)構(gòu)和非線性結(jié)構(gòu)）。101A1（2）．算法的計(jì)算量的大小稱為（計(jì)算的復(fù)雜度）。102B2（3）．順序存儲(chǔ)的線性表，設(shè)其長(zhǎng)度為n，在任何位置上插入或刪除操作的時(shí)間代價(jià)基本上都是等效的。則插入一個(gè)元素大約要移動(dòng)表中的（n/2）個(gè)元素。103A2（4）．順序表相對(duì)于鏈表的優(yōu)點(diǎn)有（節(jié)省存儲(chǔ)）和（隨機(jī)存?。?03B2（5）．線性表的長(zhǎng)度是（表中數(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）．某鏈表如下所示infolinkpABCDE^若要?jiǎng)h除值為C的結(jié)點(diǎn)，應(yīng)做操作（p->link=p->link->link）。104A1（8）．對(duì)于棧只能在（棧頂）插入和刪除元素。104C2（9）．設(shè)有一空棧，現(xiàn)有輸入序列1，2，3，4，5，6，經(jīng)過(guò)push，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è)稀疏矩陣為，則對(duì)應(yīng)的三元組線性表為（（（0，2，2），（1，0，3），（2，2，-1），（2，3，5）））。108C2（12）．設(shè)有二維數(shù)組A[0‥9，0‥19]，其每個(gè)元素占兩個(gè)字節(jié)，數(shù)組按列優(yōu)先順序存儲(chǔ)，第一個(gè)元素的存儲(chǔ)地址為100，那么元素A[6，6]的存儲(chǔ)地址為（232）。112B1（13）．在一棵二叉排序樹上按（中序）遍歷得到的結(jié)點(diǎn)序列是一個(gè)有序序列。111C3（14）．對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)進(jìn)行鏈接存儲(chǔ)時(shí)，其二叉鏈表中的指針域的總數(shù)為2n個(gè)，其中（n-1）個(gè)用于鏈接孩子結(jié)點(diǎn)。112B2（15）．對(duì)于下面的二叉樹，按后序遍歷得到的結(jié)點(diǎn)序列為（4，2，5，6，3，1）。123456115B1（16）．設(shè)無(wú)向圖G的頂點(diǎn)數(shù)為n，圖G最少有（0）邊。117C3（17）．對(duì)下列圖162534它的生成樹有（6）棵。118C3（18）．假定在有序表R[0‥19]上進(jìn)行二分查找，則比較三次查找成功的結(jié)點(diǎn)數(shù)為（4）。120D3（19）．設(shè)有兩個(gè)散列函數(shù)H1（K）=Kmod13和H2（K）=Kmod11+1，散列表為T[0‥12]，用雙重散列法（又稱二次散列法）解決沖突。函數(shù)H1用來(lái)計(jì)算散列地址，當(dāng)發(fā)生沖突時(shí)，H2作為計(jì)算下一個(gè)探測(cè)地址的地址增量。假定某一時(shí)刻散列表T的狀態(tài)為：0123456789101112T：805534下一個(gè)被插入的關(guān)鍵碼為42，其插入位置是（0）。122C3（20）．已知一棵二叉排序樹如下圖所示，則在查找成功的情況下查找每個(gè)元素的平均查找長(zhǎng)度為（）。80509040701006075

三、完形填空題102D2（1）．設(shè)順序存儲(chǔ)的線性表存儲(chǔ)結(jié)構(gòu)定義為：structsequnce{ELEMTPelem[MAXSIZE]；intlen；/*線性表長(zhǎng)度域*/}將下列簡(jiǎn)單插入算法補(bǔ)充完整。voidinsert（structsequnce*p，inti，ELEMTPx）{v=*p；if（i<1）||（i>+1）printf（“Overflow“）；else{for（j=；j>=i；j--）[j+1]=[j]；[i]=x；=+1；}}103D3（2）．設(shè)線性鏈表的存儲(chǔ)結(jié)構(gòu)如下：structnode{ELEMTPdata；/*數(shù)據(jù)域*/structnode*next；/*指針域*/}試完成下列在鏈表中值為x的結(jié)點(diǎn)前插入一個(gè)值為y的新結(jié)點(diǎn)。如果x值不存在，則把新結(jié)點(diǎn)插在表尾的算法。voidinserty（structnode*head，ELEMTPx，ELEMTPy）{s=（structnode*）malloc（sizeof（structnode））；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->next=s；s->next=p；}else{p->next=s；s->next=NULL；}}}103D3（3）．設(shè)線性鏈表的存儲(chǔ)結(jié)構(gòu)如下：structnode{ELEMTPdata；/*數(shù)據(jù)域*/structnode*next；/*指針域*/}試完成下列建立單鏈表的算法。creat（）{charvar；head=（structnode*）malloc（sizeof（structnode））；head->next=NULL；