數(shù)據(jù)結(jié)構(gòu)(第二版)模擬測(cè)試題4套及答案

試卷B一、選擇題（本題共20分,每題2分）1．在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（）。A．動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.線性結(jié)構(gòu)和非線性結(jié)構(gòu)C.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)2.下列程序段的時(shí)間復(fù)雜度是（）count=0;for(k=1;k<=n;k*=2)for(j=1;j<=n;j++)count++;A.O(nlog2n)B.O(n)C.O(log2n)D.O(n2)3.以下描述錯(cuò)誤的是：（） A.線性表是n個(gè)數(shù)據(jù)元素的有限非空集合。 B.棧和隊(duì)列都是操作受限的線性表。 C.串（或字符串）是由零個(gè)或多個(gè)字符組成的有限序列。 D.非空棧中的棧頂指針top始終指向棧頂元素的下一個(gè)位置。4.若采用少用一個(gè)隊(duì)列空間的方法來區(qū)分隊(duì)滿隊(duì)空兩種狀態(tài)，則判定一個(gè)順序循環(huán)隊(duì)列Q（最大隊(duì)列長度MAXSIZE）為滿隊(duì)列的條件是()。A.Q.front=Q.rearB.Q.front!=Q.rearC.Q.front=(Q.rear+1)%MAXSIZED.Q.front!=(Q.rear+1)%MAXSIZE5.按照二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹有（）種。A.3B.4C.5D.66.設(shè)矩陣A（如下圖所示）是一個(gè)對(duì)稱矩陣，為了節(jié)省存儲(chǔ)，將其下三角（包括對(duì)角線）部分按行序存放在一維數(shù)組B[n(n+1)/2]中，對(duì)下三角部分中任一元素ai,j(i≥j)，在一維數(shù)組B的下標(biāo)位置k的值是（）。A.i(i-1)/2+j-1B.i(i-1)/2+jC.i(i+1)/2+j-1D.i(i+1)/2+j7.有一個(gè)有序表為｛5,18，23,33,42,54,56,78｝，當(dāng)折半查找56時(shí)，經(jīng)過（）次比較后查找成功。A.1B.2C.3D.88.一組記錄的排序關(guān)鍵字為（39，19，36，68，35，84），則利用快速排序方法進(jìn)行正序排列時(shí)，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為（）。A.35，36，19，39，68，84B.19，35，36，39，68，84C.35，19，36，39，84，68D.35，19，36，39，68，849.若對(duì)下圖a中的二叉樹進(jìn)行先序線索化，則結(jié)點(diǎn)x的左、右線索指向的結(jié)點(diǎn)分別是（）A.e,cB.e,aC.d,cD.b,abdbdxeac(a)(b)10.已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如上圖b所示，根據(jù)有向圖的廣度優(yōu)先遍歷算法，從頂點(diǎn)v1出發(fā)，所得到的頂點(diǎn)序列是（）。A.v1，v2，v3，v5，v4B.v1，v3，v2，v4，v5C.v1，v3，v4，v5，v2D.v1，v4，v3，v5，v2二、填空題（本題共20分，每題2分）1.設(shè)無向圖G中頂點(diǎn)數(shù)為n，則圖G最多有_____條邊2.在一個(gè)長度為n（n≥1）的順序表中的第i個(gè)元素（1≤i≤n）之前插入一個(gè)元素時(shí)，需向后移動(dòng)_____個(gè)元素。3.在一個(gè)雙向鏈表中，要?jiǎng)h除p所指結(jié)點(diǎn)，應(yīng)執(zhí)行的操作序列為_____。4.有一棵樹如右圖所示，回答下面問題：樹的度：_____；樹的深度：_____；結(jié)點(diǎn)C的孩子結(jié)點(diǎn)：_____；結(jié)點(diǎn)F的祖先結(jié)點(diǎn)：_____。5.一棵完全二叉樹的第5層有5個(gè)結(jié)點(diǎn)，則這棵完全二叉樹共有_____個(gè)結(jié)點(diǎn)。01010101010101010101010111010001100ABCDE7.在一棵平衡二叉樹中，每個(gè)結(jié)點(diǎn)的左子樹深度與右子樹深度之差可以是。8．若一組記錄的關(guān)鍵字序列為（50，40，95，20，15，70，60，45，80），要對(duì)其按關(guān)鍵字從小到大進(jìn)行堆排序時(shí)，則創(chuàng)建的初始堆序列為_____________________。9.對(duì)n個(gè)不同的關(guān)鍵字從小到大進(jìn)行冒泡排序，最好情況下，需要經(jīng)過比較____________次將其排好；最壞情況下，需要經(jīng)過比較____________次排好。10.已知一個(gè)有向圖的邊集為{<a,b>,<a,c>,<b,d>,<b,e>,<c,b><d,e>}，則由該圖產(chǎn)生的一種可能的拓?fù)湫蛄袨開_____________________。三、應(yīng)用題（本題共40分，1-4每小題5分，5-6題每小題10分）1.利用普里姆算法，對(duì)于下面所示的連通圖，從結(jié)點(diǎn)a出發(fā)，構(gòu)造最小生成樹。2.設(shè)給定權(quán)集w={2，4，3，7，8，9}，試構(gòu)造關(guān)于w的一棵Huffman樹，并計(jì)算所構(gòu)造Huffman樹的帶權(quán)路徑長度WPL。3.已知一棵二叉樹的中序序列為CBEDAHGIJF，后序序列為CEDBHJIGFA，畫出該二叉樹。4.設(shè)數(shù)據(jù)集合D={24，13，53，37，90，48}，依次取D中各數(shù)據(jù)，構(gòu)造一棵平衡二叉樹，畫出構(gòu)造過程（說明平衡旋轉(zhuǎn)的類型）及結(jié)果。5.假設(shè)有一組關(guān)鍵字{32，01，23，14，55，20，84，27，68}，要求：（1）散列函數(shù)為H(key)=key%13，計(jì)算這組關(guān)鍵字的散列地址并填入下表：Key320123145520842768H（key）沖突次數(shù)（2）采用線性探測(cè)法解決沖突，在0-12的散列地址空間中對(duì)該關(guān)鍵字序列構(gòu)造散列表，將各關(guān)鍵字填入下表：地址0123456789101112關(guān)鍵字（3）計(jì)算成功查找時(shí)的平均查找長度ASLS，要求寫出計(jì)算過程和結(jié)果：ASLS=6.下圖是一個(gè)有7個(gè)頂點(diǎn)的網(wǎng)圖，邊上的權(quán)值為相鄰兩頂點(diǎn)的距離。使用Dijkstra算法，計(jì)算頂點(diǎn)a到所有其余頂點(diǎn)的最短路徑。計(jì)算過程和結(jié)果填入下表，要求：(1)從第1步至第6步，每步選擇的頂點(diǎn)填入表格倒數(shù)第二行；（4分）(2)表格中D值在填寫時(shí)，請(qǐng)注意存儲(chǔ)兩部分信息：頂點(diǎn)a至其余頂點(diǎn)的“當(dāng)前最短距離”，以及相應(yīng)的路徑頂點(diǎn)信息。將每一步的計(jì)算過程填入相應(yīng)的位置。（6分）終點(diǎn)從a到各個(gè)終點(diǎn)的D值和最短路徑的求解過程步驟1步驟2步驟3步驟4步驟5步驟6b距離值頂點(diǎn)序列c距離值頂點(diǎn)序列d距離值頂點(diǎn)序列e距離值頂點(diǎn)序列f距離值頂點(diǎn)序列g(shù)距離值頂點(diǎn)序列篩選頂點(diǎn)終點(diǎn)集S四、算法設(shè)計(jì)題（本題共20分）1.編寫算法，實(shí)現(xiàn)將值為e的元素插入到單鏈表L的第i個(gè)結(jié)點(diǎn)的位置上。(本題10分)單鏈表結(jié)構(gòu)定義如下：typedefstructLNode{ElemTypedata;StructLnode*next;}Lnode,*LinkList;2.試寫一個(gè)判別給定二叉樹是否為二叉排序樹的算法，設(shè)此二叉樹以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，且樹中結(jié)點(diǎn)的關(guān)鍵字均不同。（本題10分）參考答案一、選擇題答案（本題共20分，每小題2分）1.B2.A3.A4.C5.C6.D7.C8.D9.A10.B二、填空題答案（本體共20分，每小題2分）n(n-1)/2。n-i+1。p->prior->next=p->next;p->next->prior=p->prior;free(p);3_;4，G;A,B20連通圖;20,1,-115,20,60,45,40,70,95,50,80(小頂堆)/95,80,70,45,15,50,60,40,20（大頂堆）n-1;n(n-1)/2a,c,b,d,e三、應(yīng)用題答案要點(diǎn)（本題共40分，1-4每小題5分，5-6題每小題10分）1.最小生成樹2.解：哈夫曼樹如圖其帶權(quán)路徑長度WPL=7×2+8×2+4×3+2×4+3×4+9×2=803.二叉樹的結(jié)構(gòu)為：4.平衡二叉樹的構(gòu)造過程及結(jié)果：RL24375390RL2437539048131324539037485.（1）關(guān)鍵字的散列地址并填入下表：（4分）key320123145520842768H(Key)6110137613沖突次數(shù)000100232（2）采用線性探測(cè)法解決沖突，在0-12的散列地址空間列構(gòu)造散列表，（3分）地址0123456789101112關(guān)鍵字011455276832208423（3）計(jì)算成功查找時(shí)的平均查找長度ASLS，要求寫出計(jì)算過程和結(jié)果：（3分）ASLS=(1×5+2×1+3×2+4×1)/9=17/96.最短路徑：（10分）終點(diǎn)從a到各個(gè)終點(diǎn)的D值和最短路徑的求解過程步驟1步驟2步驟3步驟4步驟5步驟6b距離值151515151515頂點(diǎn)序列（a,b）（a,b）（a,b）（a,b）（a,b）（a,b）c距離值2頂點(diǎn)序列(a,c)d距離值12121111頂點(diǎn)序列(a,d)(a,d)(a,c,f,d)(a,c,f,d)e距離值1010頂點(diǎn)序列(a,c,e)(a,c,e)f距離值6頂點(diǎn)序列(a,c,f)g距離值161614頂點(diǎn)序列(a,c,f,g)(a,c,f,g)(a,c,f,d,g)篩選頂點(diǎn)cfedgb終點(diǎn)集S{a,c}{a,c,f}{a,c,f,e}{a,c,f,e,d}{a,c,f,e,d,g}{a,c,fe,d,g,b算法設(shè)計(jì)題（只列出答案要點(diǎn)，可以有不同的答案，酌情給分）1、參考代碼如下：（10分）statusListInsert(LinkList&L,inti,ElemTypee){//在帶頭結(jié)點(diǎn)的單鏈表L中第i個(gè)位置插入值為e的新結(jié)點(diǎn)p=L;j=0;while(p&&j<i-1){p=p->next;++j;}if(!p||j>i-1)returnERROR;s=(LinkList)malloc(sizeof(LNode));s->data=e;p->next=s;s->next=p->next;}2.主要代碼如下：（10分）算法思路：對(duì)二叉排序樹來說，其中序遍歷序列為一個(gè)遞增有序序列，因此，對(duì)給定的二叉樹進(jìn)行中序遍歷，如果始終能保持前一個(gè)值比后一個(gè)值小，則說明該二叉樹是一棵二叉排序樹。中序遍歷整棵二叉樹，訪問根結(jié)點(diǎn)時(shí)將根結(jié)點(diǎn)信息存入一個(gè)數(shù)組中，以用來比較中序遍歷后序列是否為空。比較數(shù)組元素時(shí)，從下標(biāo)為0的數(shù)組元素開始比較，先將下標(biāo)為i=0的a[i]與下標(biāo)為1的a[i+1]比較，如果a[i]>a[i+1]，則結(jié)束比較，即該二叉樹不是二叉排序樹，否則繼續(xù)比較，直至比較完整個(gè)數(shù)組元素。int

IsSearchTree(struct

Bitree

*root){

if(!root)

{

return

1;

}

else

if(!(root->lChild)

&&

!(root->rChild))

//左,右子樹都沒有

{return

1;

}

else

if((root->lChild)

&&

!(root->rChild))

//只有左子樹

{

if(root->lChild->data

>

root->data)

{

return

0;

//

0:不是二叉排序樹}

else

{

return

IsSearchTree(root->lChild);

}

}

else

if((root->rChild)

&&

!(root->lChild))

//只有右子樹

{if(root->rChild->data

<

root->data)

{return

0;

//

0:不是二叉排序樹

}

else

{

return

IsSearchTree(root->rChild);

}

}

else

//左,右子樹都有

{

if((root->lChild->data

>

root->data)

||

(root->rChild->data

<

root->data))

{

return

0;

//

0:不是二叉排序樹

}

else

{

return

(

IsSearchTree(root->lChild)

&&

IsSearchTree(root->rChild)

);

}

}}試卷一一、選擇題（本題共30分,每題2分）1.計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的對(duì)象被統(tǒng)稱為________。A.數(shù)據(jù)B.數(shù)據(jù)元素C.數(shù)據(jù)結(jié)構(gòu)D.數(shù)據(jù)類型2.已知一棧的進(jìn)棧序列為：1234，則下列哪個(gè)序列為不可能的出棧序列________。A．1234 B．4321C．2143 D．41233.鏈表不具有的特點(diǎn)是________。A.隨機(jī)訪問B.不必事先估計(jì)所需存儲(chǔ)空間大小C.插入與刪除時(shí)不必移動(dòng)元素D.所需空間與線性表長度成正比4.設(shè)InitQueue(Q)、EnQueue(Q,e)、DeQueue(Q,e)分別表示隊(duì)列初始化、入隊(duì)和出隊(duì)的操作。經(jīng)過以下隊(duì)列操作后，隊(duì)頭的值是________InitQueue(Q);EnQueue(Q,a);EnQueue(Q,b);EnQueue(Q,c);DeQueue(Q,x)A.aB.bC.NULLD.x5.在一個(gè)單鏈表HL中，若要?jiǎng)h除由指針q所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行________。A．p=q->next;p->next=q->next;free(p);B．p=q->next;q->next=p;free(p);C．p=q->next;q->next=p->next;free(p);D．q->next=q->next->next;q->next=q;free(p);6.一個(gè)順序表第一個(gè)元素的存儲(chǔ)地址是100,每個(gè)元素占2個(gè)存儲(chǔ)單元，則第5個(gè)元素的地址是________。A．110B．108C．100D．1207.在一個(gè)長度為n的順序存儲(chǔ)的線性表中，在其第i個(gè)位置插入一個(gè)新元素時(shí)，需要移動(dòng)元素的次數(shù)是________。A.n-iB.n-i+1C.n-i-1D.i8．下面關(guān)于線性表的敘述錯(cuò)誤的是________。 A.線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)空間 B.線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)空間C.線性表采用鏈?zhǔn)酱鎯?chǔ)便于插入和刪除操作的實(shí)現(xiàn)D.線性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn)9.Push(e)表示e進(jìn)棧，Pop(e)表示退棧并將棧頂元素存入e。下面的程序段可以將A,B的值交換的操作序列是________。A.Push(A)Push(B)Pop(A)Pop(B)B.Push(A)Push(B)Pop(B)Pop(A)C.Push(A)Pop(B)Push(B)Pop(A)D.Push(B)Pop(A)Push(A)Pop(B)10.下列查找方法中哪一種不適合元素的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)________。A．順序查找B．分塊查找C．二分查找D．散列查找11.下列排序算法中，不能保證每趟排序至少能將一個(gè)元素放到其最終的位置上的算法是________?？焖倥判駼.希爾排序C.堆排序D.冒泡排序12.設(shè)一棵二叉樹的深度為k，則該二叉樹中最多有________個(gè)結(jié)點(diǎn)。 A．2k-1 B.2k C.2k-1 D.2k-113.下列四個(gè)選項(xiàng)中，能構(gòu)成堆的是________。A.75,65,30,15,25,45,20,10B.75,65,45,10,30,25,20,15C.75,45,65,30,15,25,20,10D.75,45,65,10,25,30,20,1514.在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要多少條邊________。A．n(n-1)/2B．n-1C．nD．n+115.棧和隊(duì)列的共同特點(diǎn)是________。A.都是操作受限的線性表B.都是先進(jìn)后出C.都是后進(jìn)先出D.無共同點(diǎn)二、填空題（本題共10分，每空1分）若經(jīng)常需要對(duì)線性表進(jìn)行查找操作，則最好采用________存儲(chǔ)結(jié)構(gòu)。某帶頭結(jié)點(diǎn)單鏈表的頭指針為L，判定該單鏈表非空的條件________________。數(shù)據(jù)的邏輯結(jié)構(gòu)包括集合、________、________和圖狀結(jié)構(gòu)四種類型。圖的兩種遍歷方式為：廣度優(yōu)先遍歷和_______________。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中的結(jié)點(diǎn)包含________域和________域。向一棵二叉搜索樹中插入一個(gè)元素時(shí)，若元素的值小于根結(jié)點(diǎn)的值，則應(yīng)把它插入到根結(jié)點(diǎn)的_______上。下面程序段的功能實(shí)現(xiàn)數(shù)據(jù)x進(jìn)棧，要求在下劃線處填上正確的語句。typedefstruct{intstack[100];inttop;}seqstack;voidpush(seqstack*s,intx){if(s->top==99)printf(“overflow”);else{_____(1)_______________;__(2)_______________;}}三、應(yīng)用題（本題共40分）1．設(shè)散列表長度為11，散列函數(shù)h(key)=key%11。給定的關(guān)鍵字為1，13，12，34，38，33，2，22。試畫出用線性探查法解決沖突時(shí)所構(gòu)造的散列表。并計(jì)算在查找成功時(shí)候的平均查找長度。（6分）2．有一組權(quán)值14、21、32、15、28，畫出哈夫曼樹，并計(jì)算其WPL。（6分）3．已知圖G=(V,E)，其中V={1,2,3,4,5},E={(1,2),(1,3),(1,4),(2,3),(2,5),(3,4),(4,5)}。要求完成如下操作：（6分）（1）寫出圖的鄰接矩陣（2）寫出采用鄰接矩陣存儲(chǔ)時(shí)，從頂點(diǎn)1出發(fā)的廣度優(yōu)先搜索遍歷序列。4．已知序列{503，87，512，61，908，170，897，275，653，462}，分別寫出執(zhí)行下列排序算法的各趟排序結(jié)束時(shí)，關(guān)鍵字序列的狀態(tài)：（10分）（1）直接插入排序（2）基數(shù)排序5．對(duì)于下面所示的連通圖，寫出由Prim算法生成的最小生成樹。（5分）6.將下面的樹轉(zhuǎn)化為一棵二叉樹,并寫出對(duì)二叉樹進(jìn)行層序遍歷的序列。（7分）AABCDEFGH四、算法題（本題共20分）1．完成中序遍歷二叉樹。Typedefstructnode{Chardata;Structnode*lchild;Structnode*rchild;}BTreeNode,*LinkBtree;VoidInOrder(LinkBtreeBt_pointer){If(Bt_pointer!=NULL){_________(1)_____________;__________(2)_____________;__________(3)____________;}}2.完成二分查找算法：#Definen10typedefintKeyType;typedefstruct{KeyTypekey;}NodeType;TypedefNodeTypeSeqList[n+1];intBinSearch(SeqListR,KeyTypek){intlow=1,high=n,mid;while(_____（4）_______){mid=(low+high)/2;if(R[mid].key==k)returnmid;if(R[mid].key>k)_____（5）_____;else________（6）_______;}return0;}3.編寫算法實(shí)現(xiàn)直接插入排序。（8分）參考答案一、選擇題（本題共30分,每題2分）123456789101112131415ADABCBBDACBDCBA二、填空題（本題共10分，每空1分）1）順序2）L->next!=NULL3）線性結(jié)構(gòu)樹形結(jié)構(gòu)4）深度優(yōu)先遍歷5）數(shù)據(jù)指針6）左子樹7）s->top++s->stack[s->top]=x三、應(yīng)用題（本題共40分）1、（6分）H(1)=1H(13)=2H(12)=1沖突，H1=2沖突，H2=3H(34)=1沖突，H1=2沖突，H2=3沖突，H3=4H(38)=5H(33)=0H(2)=2沖突，H1=3沖突，H2=4沖突，H3=5沖突，H4=6H(22)=0沖突，H1=1沖突，H2=2沖突，H3=3沖突，H4=4沖突，H5=5沖突，H6=6沖突，H7=7ASL=(1+1+3+4+1+1+5+8)/8=24/8=32、（6分）1101104961212829321415Wpl=2493、圖的鄰接矩陣：（3分）廣度優(yōu)先序列：12345（3分）01110101011101010101010104、1）（503）8751261908170897275653462（5分）（87503）51261908170897275653462（87503512）61908170897275653462（6187503512）908170897275653462（6187503512908）170897275653462（6187170503512908）897275653462（6187170503512897908）275653462（6187170275503512897908）653462（6187170275503512653897908）462（6187170275462503512653897908）2）第一趟：1706151246250365327587897908（5分）第二趟：5039085126536146217027587897第三趟：61871702754625035126538979085、（5分）ABDABDEFGHC層序遍歷序列:ABECFDGH四、算法題（本題共20分）1、（1）InOrder(Bt_pointer->lchild);（2分）(2)printf(“%c”,Bt_pointer->data);（2分）(3)InOrder(Bt_pointer->rchild);（2分）2、（4）low<=high（5）high=mid-1;（6）low=mid+1;（6分）3、voidInsertSort(inta[],intn)（8分）{inti,j;for(i=2;i<=n;i++){a[0]=a[i];j=i-1;while(a[0]<a[j]){a[j+1]=a[j];j--;}a[j+1]=a[0];}}試卷一一、選擇題（本題共30分,每題2分）1.計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的對(duì)象被統(tǒng)稱為________。A.數(shù)據(jù)B.數(shù)據(jù)元素C.數(shù)據(jù)結(jié)構(gòu)D.數(shù)據(jù)類型2.已知一棧的進(jìn)棧序列為：1234，則下列哪個(gè)序列為不可能的出棧序列________。A．1234 B．4321C．2143 D．41233.鏈表不具有的特點(diǎn)是________。A.隨機(jī)訪問B.不必事先估計(jì)所需存儲(chǔ)空間大小C.插入與刪除時(shí)不必移動(dòng)元素D.所需空間與線性表長度成正比4.設(shè)InitQueue(Q)、EnQueue(Q,e)、DeQueue(Q,e)分別表示隊(duì)列初始化、入隊(duì)和出隊(duì)的操作。經(jīng)過以下隊(duì)列操作后，隊(duì)頭的值是________InitQueue(Q);EnQueue(Q,a);EnQueue(Q,b);EnQueue(Q,c);DeQueue(Q,x)A.aB.bC.NULLD.x5.在一個(gè)單鏈表HL中，若要?jiǎng)h除由指針q所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行________。A．p=q->next;p->next=q->next;free(p);B．p=q->next;q->next=p;free(p);C．p=q->next;q->next=p->next;free(p);D．q->next=q->next->next;q->next=q;free(p);6.一個(gè)順序表第一個(gè)元素的存儲(chǔ)地址是100,每個(gè)元素占2個(gè)存儲(chǔ)單元，則第5個(gè)元素的地址是________。A．110B．108C．100D．1207.在一個(gè)長度為n的順序存儲(chǔ)的線性表中，在其第i個(gè)位置插入一個(gè)新元素時(shí)，需要移動(dòng)元素的次數(shù)是________。A.n-iB.n-i+1C.n-i-1D.i8．下面關(guān)于線性表的敘述錯(cuò)誤的是________。 A.線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)空間 B.線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)空間C.線性表采用鏈?zhǔn)酱鎯?chǔ)便于插入和刪除操作的實(shí)現(xiàn)D.線性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn)9.Push(e)表示e進(jìn)棧，Pop(e)表示退棧并將棧頂元素存入e。下面的程序段可以將A,B的值交換的操作序列是________。A.Push(A)Push(B)Pop(A)Pop(B)B.Push(A)Push(B)Pop(B)Pop(A)C.Push(A)Pop(B)Push(B)Pop(A)D.Push(B)Pop(A)Push(A)Pop(B)10.下列查找方法中哪一種不適合元素的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)________。A．順序查找B．分塊查找C．二分查找D．散列查找11.下列排序算法中，不能保證每趟排序至少能將一個(gè)元素放到其最終的位置上的算法是________。快速排序B.希爾排序C.堆排序D.冒泡排序12.設(shè)一棵二叉樹的深度為k，則該二叉樹中最多有________個(gè)結(jié)點(diǎn)。 A．2k-1 B.2k C.2k-1 D.2k-113.下列四個(gè)選項(xiàng)中，能構(gòu)成堆的是________。A.75,65,30,15,25,45,20,10B.75,65,45,10,30,25,20,15C.75,45,65,30,15,25,20,10D.75,45,65,10,25,30,20,1514.在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要多少條邊________。A．n(n-1)/2B．n-1C．nD．n+115.棧和隊(duì)列的共同特點(diǎn)是________。A.都是操作受限的線性表B.都是先進(jìn)后出C.都是后進(jìn)先出D.無共同點(diǎn)二、填空題（本題共10分，每空1分）若經(jīng)常需要對(duì)線性表進(jìn)行查找操作，則最好采用________存儲(chǔ)結(jié)構(gòu)。某帶頭結(jié)點(diǎn)單鏈表的頭指針為L，判定該單鏈表非空的條件________________。數(shù)據(jù)的邏輯結(jié)構(gòu)包括集合、________、________和圖狀結(jié)構(gòu)四種類型。圖的兩種遍歷方式為：廣度優(yōu)先遍歷和_______________。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中的結(jié)點(diǎn)包含________域和________域。向一棵二叉搜索樹中插入一個(gè)元素時(shí)，若元素的值小于根結(jié)點(diǎn)的值，則應(yīng)把它插入到根結(jié)點(diǎn)的_______上。下面程序段的功能實(shí)現(xiàn)數(shù)據(jù)x進(jìn)棧，要求在下劃線處填上正確的語句。typedefstruct{intstack[100];inttop;}seqstack;voidpush(seqstack*s,intx){if(s->top==99)printf(“overflow”);else{_____(1)_______________;__(2)_______________;}}三、應(yīng)用題（本題共40分）1．設(shè)散列表長度為11，散列函數(shù)h(key)=key%11。給定的關(guān)鍵字為1，13，12，34，38，33，2，22。試畫出用線性探查法解決沖突時(shí)所構(gòu)造的散列表。并計(jì)算在查找成功時(shí)候的平均查找長度。（6分）2．有一組權(quán)值14、21、32、15、28，畫出哈夫曼樹，并計(jì)算其WPL。（6分）3．已知圖G=(V,E)，其中V={1,2,3,4,5},E={(1,2),(1,3),(1,4),(2,3),(2,5),(3,4),(4,5)}。要求完成如下操作：（6分）（1）寫出圖的鄰接矩陣（2）寫出采用鄰接矩陣存儲(chǔ)時(shí)，從頂點(diǎn)1出發(fā)的廣度優(yōu)先搜索遍歷序列。4．已知序列{503，87，512，61，908，170，897，275，653，462}，分別寫出執(zhí)行下列排序算法的各趟排序結(jié)束時(shí)，關(guān)鍵字序列的狀態(tài)：（10分）（1）直接插入排序（2）基數(shù)排序5．對(duì)于下面所示的連通圖，寫出由Prim算法生成的最小生成樹。（5分）6.將下面的樹轉(zhuǎn)化為一棵二叉樹,并寫出對(duì)二叉樹進(jìn)行層序遍歷的序列。（7分）AABCDEFGH四、算法題（本題共20分）1．完成中序遍歷二叉樹。Typedefstructnode{Chardata;Structnode*lchild;Structnode*rchild;}BTreeNode,*LinkBtree;VoidInOrder(LinkBtreeBt_pointer){If(Bt_pointer!=NULL){_________(1)_____________;__________(2)_____________;__________(3)____________;}}2.完成二分查找算法：#Definen10typedefintKeyType;typedefstruct{KeyTypekey;}NodeType;TypedefNodeTypeSeqList[n+1];intBinSearch(SeqListR,KeyTypek){intlow=1,high=n,mid;while(_____（4）_______){mid=(low+high)/2;if(R[mid].key==k)returnmid;if(R[mid].key>k)_____（5）_____;else________（6）_______;}return0;}3.編寫算法實(shí)現(xiàn)直接插入排序。（8分）參考答案一、選擇題（本題共30分,每題2分）123456789101112131415ADABCBBDACBDCBA二、填空題（本題共10分，每空1分）1）順序2）L->next!=NULL3）線性結(jié)構(gòu)樹形結(jié)構(gòu)4）深度優(yōu)先遍歷5）數(shù)據(jù)指針6）左子樹7）s->top++s->stack[s->top]=x三、應(yīng)用題（本題共40分）1、（6分）H(1)=1H(13)=2H(12)=1沖突，H1=2沖突，H2=3H(34)=1沖突，H1=2沖突，H2=3沖突，H3=4H(38)=5H(33)=0H(2)=2沖突，H1=3沖突，H2=4沖突，H3=5沖突，H4=6H(22)=0沖突，H1=1沖突，H2=2沖突，H3=3沖突，H4=4沖突，H5=5沖突，H6=6沖突，H7=7ASL=(1+1+3+4+1+1+5+8)/8=24/8=32、（6分）1101104961212829321415Wpl=2493、圖的鄰接矩陣：（3分）廣度優(yōu)先序列：12345（3分）01110101011101010101010104、1）（503）8751261908170897275653462（5分）（87503）51261908170897275653462（87503512）61908170897275653462（6187503512）908170897275653462（6187503512908）170897275653462（6187170503512908）897275653462（6187170503512897908）275653462（6187170275503512897908）653462（6187170275503512653897908）462（6187170275462503512653897908）2）第一趟：1706151246250365327587897908（5分）第二趟：5039085126536146217027587897第三趟：61871702754625035126538979085、（5分）ABDABDEFGHC層序遍歷序列:ABECFDGH四、算法題（本題共20分）1、（1）InOrder(Bt_pointer->lchild);（2分）(2)printf(“%c”,Bt_pointer->data);（2分）(3)InOrder(Bt_pointer->rchild);（2分）2、（4）low<=high（5）high=mid-1;（6）low=mid+1;（6分）3、voidInsertSort(inta[],intn)（8分）{inti,j;for(i=2;i<=n;i++){a[0]=a[i];j=i-1;while(a[0]<a[j]){a[j+1]=a[j];j--;}a[j+1]=a[0];}}試卷二一、選擇題（本題共20分,每題2分）1.下面程序段的時(shí)間復(fù)雜度為（）。for(i=1;i<=n;i++)for(j=1;j<=n;j++)s++;A.O(n)B.O(n2)C.O(2*n)D.O（i*j）2.線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)地址（）。A．必須是不連續(xù)的B．部分地址必須是連續(xù)的C．連續(xù)與否均可D．和頭結(jié)點(diǎn)的存儲(chǔ)地址相連續(xù)3.若讓元素1，2，3依次進(jìn)棧，則出棧時(shí)的序列不可能出現(xiàn)的是（）。A．3，2，1B．1，2，3C．3，1，2D．2，1，34.下面說法不正確的是()A．串S1=“this_is_a_string”的長度是16。B．串S2=“this”是串S1的子串。C．串S3=“thisis”在串S1中的位置是1。D．串S4=“a”在串S1中的位置是9。5.一個(gè)非空廣義表的表頭（）。A．不可能是子表B．只能是子表C．只能是原子D．可以是子表或原子6.完全二叉樹()滿二叉樹A．不一定是B．一定不是C．一定是D．不能確定關(guān)系7.用鏈表表示線性表的優(yōu)點(diǎn)是（）便于隨機(jī)存取便于插入和刪除操作花費(fèi)的存儲(chǔ)空間較順序存儲(chǔ)少元素的物理順序與邏輯順序相同8.在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要多少條邊()。A．n(n-1)/2B．n-1C．nD．n+19.下列查找方法中哪一種不適合元素的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)()A．順序查找B．分塊查找C．二分查找D．散列查找10.下面哪種排序方法穩(wěn)定性最好()。A．希爾排序B．冒泡排序C．快速排序D．堆排序二、填空題（本題共20分）1.數(shù)據(jù)的邏輯結(jié)構(gòu)可以分為兩大類：_________和________。2.在二叉樹的第i層上最多有___________個(gè)結(jié)點(diǎn)。3.無向圖中恰好有__________條邊，才稱為無向完全圖。4.用單鏈表方式存儲(chǔ)的線性表，存儲(chǔ)每個(gè)結(jié)點(diǎn)需要有兩個(gè)域，一個(gè)是_________，另一個(gè)是________。5.設(shè)二維數(shù)組A5×6的每個(gè)元素占4個(gè)字節(jié)，已知LOC（a00）=1000，則A一共占用_______字節(jié)。如果按行優(yōu)先存儲(chǔ)時(shí)，a25的起始地址是_________。6.3個(gè)結(jié)點(diǎn)的樹有_______種形態(tài)，3個(gè)結(jié)點(diǎn)的二叉樹有________種形態(tài)。7.一個(gè)廣義表為（a，（a，b），d，e，（（i，j），k）），則該廣義表的深度為________。8.棧的插入操作在_______進(jìn)行，刪除操作在_______進(jìn)行。9.在二叉樹中，結(jié)點(diǎn)的最大度數(shù)是_______。10.判定一個(gè)有向圖中是否存在回路，即是否含有環(huán)，可以使用_________方法。11.二分查找的效率較高，但是要求查找表中的關(guān)鍵字_______，并且要求表的存儲(chǔ)為________。12.在構(gòu)造散列表的過程中，不可避免會(huì)出現(xiàn)沖突，通常解決它的方法有_______和_______。13．從任何一個(gè)結(jié)點(diǎn)開始都能成功查找其他結(jié)點(diǎn)的單鏈表是表。三、應(yīng)用題（本題共50分，