數(shù)據(jù)結(jié)構(gòu)及算法分析習(xí)題及參考答案

四川大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法分析》課程習(xí)題及參考答案模擬試卷一一、單選題(每題2分，共20分).以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是線性結(jié)構(gòu)？(B)A.有向圖B.隊(duì)列C.線索二叉樹(shù)D.B樹(shù).在一個(gè)單鏈表HL中，若要在當(dāng)前由指針口指向的結(jié)點(diǎn)后面插入一個(gè)由口指向的結(jié)點(diǎn)，則執(zhí)行如下(D)語(yǔ)句序列。A.p=q;p->next=q;B.p->next=q;q->next=p;C.p->next=q->next;p=q;D.q->next=p->next;p->next=q;.以下哪一個(gè)不是隊(duì)列的基本運(yùn)算？(A)A.在隊(duì)列第i個(gè)元素之后插入一個(gè)元素B.從隊(duì)頭刪除一個(gè)元素C.判斷一個(gè)隊(duì)列是否為空D.讀取隊(duì)頭元素的值.字符A、B、C依次進(jìn)入一個(gè)棧，按出棧的先后順序組成不同的字符串，至多可以組成(B)個(gè)不同的字符串？ABCACBBACBCACBAD.85.A.14 B.5 C.6D.85.由權(quán)值分別為3,8,6,2的葉子生成一棵哈夫曼樹(shù)，它的帶權(quán)路徑長(zhǎng)度為()。A．11 B.35C.19D.538*1+6*2+3*3+2*3=35以下6-8題基于圖1。該二叉樹(shù)結(jié)點(diǎn)的前序遍歷的序列為(C)。E、G、F、A、C、D、BE、A、G、C、F、B、DE、A、C、B、D、G、FE、G、A、C、D、F、B該二叉樹(shù)結(jié)點(diǎn)的中序遍歷的序列為(A)。A.A、B、C、D、E、G、FB.E、A、G、C、F、B、DC.E、A、C、B、D、G、FE.B、D、C、A、F、G、E該二叉樹(shù)的按層遍歷的序列為(C)。A．E、G、F、A、C、D、B B.E、A、C、B、D、G、FC.E、A、G、C、F、B、D D.E、G、A、C、D、F、B下面關(guān)于圖的存儲(chǔ)的敘述中正確的是(C)。A.用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)B.用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間大小與圖中邊數(shù)和結(jié)點(diǎn)個(gè)數(shù)都有關(guān)C.用鄰接矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間大小與圖中結(jié)點(diǎn)個(gè)數(shù)和邊數(shù)都有關(guān)D.用鄰接矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)10,設(shè)有關(guān)鍵碼序列(q,g,m,z,a,n,p,x,卜)，下面哪一個(gè)序列是從上述序列出發(fā)建堆的結(jié)果?(B)A,a,g,h,m,n,p,q,x,zB,a,g,m,h,q,n,p,x,zC,g,m,q,a,n,p,x,h,z D,h,g,m,p,a,n,q,x,z二、填空題(每空1分,共26分),數(shù)據(jù)的物理結(jié)構(gòu)被分為_(kāi)順序__、___列表___、 索引 和 散列___四種。.對(duì)于一個(gè)長(zhǎng)度為n的順序存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為_(kāi)__O(n) ,在表尾插入元素的時(shí)間復(fù)雜度為 O(1) 。.向一個(gè)由^指向的鏈棧中插入一個(gè)結(jié)點(diǎn)時(shí)p時(shí)，需要執(zhí)行的操作是 p->next=HS;HS=p ;刪除一個(gè)結(jié)點(diǎn)時(shí),需要執(zhí)行的操作是 HS=HS->next (假設(shè)棧不空而且無(wú)需回收被刪除結(jié)點(diǎn))。4,對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，一個(gè)結(jié)點(diǎn)的編號(hào)為i(1WiWn),若它有左孩子則左孩子結(jié)點(diǎn)的編號(hào)為 2i__,若它有右孩子,則右孩子結(jié)點(diǎn)的編號(hào)為_(kāi)__2i+1 ,若它有雙親,則雙親結(jié)點(diǎn)的編號(hào)為_(kāi)__i/2 。

TOC\o"1-5"\h\z當(dāng)向一個(gè)大根堆插入一個(gè)具有最大值的元素時(shí)，需要逐層 向上 調(diào)整，直到被調(diào)整到 根___位置為止。以二分查找方法從長(zhǎng)度為10的有序表中查找一個(gè)元素時(shí)，平均查找長(zhǎng)度為 2.9 。表示圖的三種常用的存儲(chǔ)結(jié)構(gòu)為 鄰接矩陣 、 鄰接表 和 邊集數(shù)組 。對(duì)于線性表(70，34，55，23，65，41，20)進(jìn)行散列存儲(chǔ)時(shí)，若選用H(K)=K%7作為散列函數(shù)，則散列地址為0的元素有1 個(gè)，散列地址為6的有__4 個(gè)。在歸并排序中，進(jìn)行每趟歸并的時(shí)間復(fù)雜度為_(kāi)_O(n) ，整個(gè)排序過(guò)程的時(shí)間復(fù)雜度為 O(nlog2n) ，空間復(fù)雜度為 O(n) 。10.(m/2)-1 個(gè)，最多為_(kāi)__m-1 個(gè)其子樹(shù)數(shù)目最少為在一棵m10.(m/2)-1 個(gè)，最多為_(kāi)__m-1 個(gè)其子樹(shù)數(shù)目最少為m/2 ，最多為_(kāi)__m三、運(yùn)算題(每題6分，共24分)1.寫(xiě)出下列中綴表達(dá)式的后綴形式:(1)3X/(Y-2)+1⑵2+X*(Y+3)三、運(yùn)算題(每題6分，共24分)1.寫(xiě)出下列中綴表達(dá)式的后綴形式:(1)3X/(Y-2)+1⑵2+X*(Y+3)2.試對(duì)圖2中的二叉樹(shù)畫(huà)出其:(1)順序存儲(chǔ)表示的示意圖；(2)二叉鏈表存儲(chǔ)表示的示意圖。3.判斷以下序列是否是小根堆?如果不是,將它調(diào)整為小根堆。(1){12, 70, 33,65,24,56, 48, 92,86,33}(2){05, 23, 20,28,40,38, 29, 61,35,76,47, 100}4,已知一個(gè)圖的頂點(diǎn)集V和邊集E分別為：V={1,2,3,4,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};按照普里姆算法從頂點(diǎn)1出發(fā)得到最小生成樹(shù)，試寫(xiě)出在最小生成樹(shù)中依次得到的各條邊。閱讀算法(每題7分，共14分)voidAE(Stack&S){InitStack(S);Push(S,3);Push(S,4);intx=Pop(S)+2*Pop(S);Push(S,x);inti,a[5]={1,5,8,12,15};for(i=0;i<5;i++)Push(S,2*a[i]);while(!StackEmpty(S))cout<<Pop(S)<<'';該算法被調(diào)用后得到的輸出結(jié)果為：voidABC(BTNode*BT,int&c1,int&c2){if(BT!=NULL){ABC(BT->left,c1,c2);c1++;if(BT->left==NULL&&BT->right==NULL)c2++;ABC(BT->right,c1,c2);}//if}該函數(shù)執(zhí)行的功能是什么？算法填空(共8分)向單鏈表的末尾添加一個(gè)元素的算法。VoidInsertRear(LNode*&HL,constElemType&item){LNode*newptr;newptr=newLNode;If( ){cerr<<"Memoryallocationfailare!"<<endl;exit(1);} =item;newptr->next=NULL;if(HL=二NULL)HL= else{LNode*P=HL;While(P->next!=NULL) ,p->next=newptr;}編寫(xiě)算法（共8分）（假編寫(xiě)從類(lèi)型為L(zhǎng)ist的線性表L中將第i個(gè)元素刪除的算法，（假定不需要對(duì)i的值進(jìn)行有效性檢查,也不用判別L是否為空表。）voidDelete（List&L,inti）模擬試卷一參考答案單選題（每題2分，共20分）1.B2.D3.A4.B5.B6.C7.A8.C9.B10.B填空題（每空1分，共26分）順序鏈表索引散列O（n）O（1）p->next=HS;HS=pHS=HS->next2i2i+1 i/2（或i/2）

圖3向上根圖32.9鄰接矩陣鄰接表邊集數(shù)組TOC\o"1-5"\h\z1 4O(n) O(nlogn) O(n)八 2m/2-1 m-1 m/2 m三、運(yùn)算題(每題6分，共24分)(1)3X*Y2-/1+⑵2XY3+*+2.⑴0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16123456789(2)見(jiàn)圖3所示：.(1)不是小根堆。調(diào)整為:{12,65,33,70,24,56,48,92,86,33}⑵是小根堆。.普里姆算法從頂點(diǎn)1出發(fā)得到最小生成樹(shù)為：(1,3)5, (1,4)8, (4,6)4, (2,5)10, (4,7)20四、閱讀算法(每題7分，共14分)1.302416102102,該函數(shù)的功能是：統(tǒng)計(jì)出BT所指向的二叉樹(shù)的結(jié)點(diǎn)總數(shù)和葉子總數(shù)五、算法填空(共8分，每一空2分)newptr二二NULL newptr—〉二data newptr

p=p->next六、編寫(xiě)算法（8分）voidDelete（List&L,inti）{for（intj=i-1;j<L.size-1;j++）L.listj]=L.listj+1];//第i個(gè)元素的下標(biāo)為i-1L.size--;}模擬試卷二一:在單選帶有;題￡晨二中,若要向表頭插入一個(gè)由指針口指向的結(jié)點(diǎn)，則執(zhí)行（B）。A.HL=p;p->next=HL;B.p->next=HL->next;HL->next=p;C.p->next=HL;p=HL;D.p->next=HL;HL=p;2,若順序存儲(chǔ)的循環(huán)隊(duì)列的QueueMaxSize二n,則該隊(duì)列最多可存儲(chǔ)（B）個(gè)元素.A,n B,n-1C.n+1D.不確定3,下述哪一條是順序存儲(chǔ)方式的優(yōu)點(diǎn)？（A）A.存儲(chǔ)密度大 8.插入和刪除運(yùn)算方便C.獲取符合某種條件的元素方便C.獲取符合某種條件的元素方便D.查找運(yùn)算速度4,設(shè)有一個(gè)二維數(shù)組A[m][n],假設(shè)A[0][0]存放位置在600(⑹，A[3][3]存放位置在678(10),每個(gè)元素占一個(gè)空間，問(wèn)A[2][3](⑹存放在什么位置？(腳注(10)表示用10進(jìn)制表示,m>3)CA．658 B．648 C．633 D．6535,下列關(guān)于二叉樹(shù)遍歷的敘述中，正確的是(D)。A.若一個(gè)樹(shù)葉是某二叉樹(shù)的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹(shù)的前序遍歷最后一個(gè)結(jié)點(diǎn)B.若一個(gè)點(diǎn)是某二叉樹(shù)的前序遍歷最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹(shù)的中序遍歷的最后一個(gè)結(jié)點(diǎn)C.若一個(gè)結(jié)點(diǎn)是某二叉樹(shù)的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹(shù)的前序最后一個(gè)結(jié)點(diǎn)D.若一個(gè)樹(shù)葉是某二叉樹(shù)的前序最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹(shù)的中序遍歷最后一個(gè)結(jié)點(diǎn)6,卜層二叉樹(shù)的結(jié)點(diǎn)總數(shù)最多為(A).A．2k-1 B,2K+1 C,2K-1D,2k-17,對(duì)線性表進(jìn)行二分法查找，其前提條件是(C),A,線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值排好序B,線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序C,線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值排好序D,線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序8,對(duì)n個(gè)記錄進(jìn)行堆排序，所需要的輔助存儲(chǔ)空間為CA,O(1ogn)B,O(n) C,O(1)D,O(n2)29.對(duì)于線性表（7，34，77，25，64，49，20，14）進(jìn)行散列存儲(chǔ)時(shí)，若選用H（K）=K%7作為散列函數(shù)，則散列地址為0的元素有（D）個(gè)，A．1 B．2 C．3 D．410.下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的是（D）.A.數(shù)組是不同類(lèi)型值的集合B.遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為精煉C.樹(shù)是一種線性結(jié)構(gòu)D.用一維數(shù)組存儲(chǔ)一棵完全二叉樹(shù)是有效的存儲(chǔ)方法二、填空題（每空1分，共26分）數(shù)據(jù)的邏輯結(jié)構(gòu)被分為 、 、 和 四種。一個(gè)算法的時(shí)間復(fù)雜度為（3n3+2000nlog2n+90）/"，其數(shù)量級(jí)表示為 。對(duì)于一個(gè)長(zhǎng)度為n的單鏈存儲(chǔ)的隊(duì)列，在表頭插入元素的時(shí)間復(fù)雜度為 ，在表尾插入元素的時(shí)間復(fù)雜度為4,假定一棵樹(shù)的廣義表表示為A（D（E，G），H（I，J）），則樹(shù)中所含的結(jié)點(diǎn)數(shù)為 個(gè)，樹(shù)的深度為 ，樹(shù)的度為.后綴算式79230+-42/*的值為 。中綴算式（3+X*Y） -2Y/3對(duì)應(yīng)的后綴算式為.在一棵高度為5的理想平衡樹(shù)中，最少含有個(gè)結(jié)點(diǎn)，最多含有個(gè)結(jié)點(diǎn)。.在樹(shù)中，一個(gè)結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)稱(chēng)為該結(jié)點(diǎn)的。一個(gè)結(jié)點(diǎn)的直接前趨結(jié)點(diǎn)稱(chēng)為該結(jié)點(diǎn)的。.在一個(gè)具有10個(gè)頂點(diǎn)的無(wú)向完全圖中，包含有條邊，在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，包含有條邊。.假定一個(gè)線性表為(12,17,74,5,63,49,82,36)，若按Key%4條件進(jìn)行劃分，使得同一余數(shù)的元素成為一個(gè)子表，則得到的四個(gè)子表分別為、.對(duì)一棵B_樹(shù)進(jìn)行刪除元素的過(guò)程中，若最終引起樹(shù)根結(jié)點(diǎn)的合并時(shí)，會(huì)使新樹(shù)的高度比原樹(shù)的高度。.在堆排序的過(guò)程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為，整個(gè)堆排序過(guò)程的時(shí)間復(fù)雜度為。.在線性表的散列存儲(chǔ)中，裝填因子又稱(chēng)為裝填系數(shù)，若用m表示散列表的長(zhǎng)度，n表示待散列存儲(chǔ)的元素的個(gè)數(shù)，則 等于運(yùn)算題(每題6分，共24分).在如下數(shù)組A中鏈接存儲(chǔ)了一個(gè)線性表，表頭指針存放在 A[0].next,試寫(xiě)出該線性表。A0 1 2 3 4 5 66050789034404052713datanext.已知一棵二叉樹(shù)的前序遍歷的結(jié)果是ABKCDFGHJ,中序遍歷的結(jié)果是KBCDAFHIGJ,試畫(huà)出這棵二叉樹(shù)。.已知一個(gè)圖的頂點(diǎn)集V為：V={1,2,3,4,5,6,7};其共有10條邊。該圖用如下邊集數(shù)組存儲(chǔ)：起點(diǎn)1225522613終點(diǎn)6454767775權(quán)1122233457試用克魯斯卡爾算法依次求出該圖的最小生成樹(shù)中所得到的各條邊及權(quán)值。.畫(huà)出向小根堆中加入數(shù)據(jù)4,2,5,8,3,6,10,1時(shí)，每加入一個(gè)數(shù)據(jù)后堆的變化。閱讀算法（每題7分，共14分）.在下面的每個(gè)程序段中，假定線性表La的類(lèi)型為L(zhǎng)ist,元素類(lèi)型ElemType為int,并假定每個(gè)程序段是連續(xù)執(zhí)行的。試寫(xiě)出每個(gè)程序段執(zhí)行后所得到的線性表La。(1)InitList(La);Inta[]={100,26,57,34,79};For(i=0;i<5;i++)Insert(La,a[i]);TraverseList(La);(2)DeleteFront(La);InsertRear(La,DeleteFront(La));TraverseList(La);(3)ClearList(La);For(i=0;i<5;i++)InsertFront(La,a[i]);TraverseList(La);.現(xiàn)面算法的功能是什么？voidABC(BTNode*BT){ifBT{cout<<BT->data<<'';ABC(BT->left);ABC(BT->right);}}算法填空(共8分)二分查找的遞歸算法。IntBinsch(ElemTypeA[],intlow,inthigh,KeyTypeK){if {intmid=(low+high)/2;if( )returnmid;//查找成功，返回元素的下標(biāo)elseif(K<A[mid].key)returnBinsch(A,low,mid-1,K); //在左子表上繼續(xù)查找elsereturn ；//在右子表上繼續(xù)查找}else ； //查找失敗，返回-1}編寫(xiě)算法(共8分)HL為單鏈表的表頭指針，試寫(xiě)出在該單鏈表中查找具有給定的元素item的算法。boolFind(LNode*HL,ElemType&item)模擬試卷二參考答案單選題(每題2分，共20分)1.B2.B3.A4.C5.D6.A7.C 8.C 9.D 10.D填空題(每空1分，共26分)集合結(jié)構(gòu)線性結(jié)構(gòu)樹(shù)結(jié)構(gòu)圖結(jié)構(gòu)O(n)O(1)O(1)72294 3XY*+2Y*3/-

1631孩子（或子）結(jié)點(diǎn)雙親（或父）結(jié)點(diǎn)45 n（n-1）（12，36） （17,5,49） （74，82） （63）減少1（或減少）O（logn）O（nlogn）.2 2n/m運(yùn)算題（每題6分，共24分）.線性表為：（90，40，78，50，34，60）.當(dāng)前序序列為ABKCDFGHJ,中序序列為KBCDAFHIGJ時(shí)，逐步形成二叉樹(shù)的過(guò)程如下圖4所示：3.用克魯斯卡爾算法得到的最小生成樹(shù)為：3.用克魯斯卡爾算法得到的最小生成樹(shù)為：(1,6)1,(2,4)1,(2,5)2,(5,7)2,(2,6)3,(3,5)7(1,6)1,(2,4)1,(2,5)2,(5,7)2,(2,6)3,(3,5)74.

4.圖5閱讀算法(每題7分，共14分)(1)La=(26,34,57,79,100)(2)La=(57,79,100,34)(3)La=(79,34,57,26,100)前序遍歷鏈?zhǔn)酱鎯?chǔ)的二叉樹(shù)。算法填空(每空2分，共8分)(low<=high)K==A[mid].keyBinsch(A,mid+1,hight,K)return-1編寫(xiě)算法(8分)boolFind(LNode*HL,ElemType&item){LNode*p=HL;whilepif(p->data==item){returntrue;}elsep=p->next;returnfalse;模擬試卷三單選題（每題模擬試卷三單選題（每題2分，共20分）▲1,對(duì)一個(gè)算法的評(píng)價(jià)，不包括如下(B)方面的內(nèi)容。A.健壯性和可讀性 B.并行性C.正確性口.時(shí)空復(fù)雜度2.在帶有頭結(jié)點(diǎn)的單鏈表HL中，要向表頭插入一個(gè)由指針口指向的結(jié)點(diǎn)，則執(zhí)行(A)。A.p->next=HL->next;HL->next=p;B.p->next=HL;HL=p;C.p->next=HL;p=HL;D.HL=p;p->next=HL;對(duì)線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？(B)A.經(jīng)常需要隨機(jī)地存取元素B.經(jīng)常需要進(jìn)行插入和刪除操作C.表中元素需要占據(jù)一片連續(xù)的存儲(chǔ)空間 D.表中元素的個(gè)數(shù)不變一個(gè)棧的輸入序列為123，則下列序列中不可能是棧的輸出序列的是(C)A.231 B.321C.312 D.123AOV網(wǎng)是一種(D)。人.有向圖8.無(wú)向圖。無(wú)向無(wú)環(huán)圖 D.有向無(wú)環(huán)圖采用開(kāi)放定址法處理散列表的沖突時(shí)，其平均查找長(zhǎng)度(B)。A.低于鏈接法處理沖突 B.高于鏈接法處理沖突C.與鏈接法處理沖突相同 D.高于二分查找若需要利用形參直接訪問(wèn)實(shí)參時(shí)，應(yīng)將形參變量說(shuō)明為(D)參數(shù)。A.值B.函數(shù)C指針 D.引用在稀疏矩陣的帶行指針向量的鏈接存儲(chǔ)中，每個(gè)單鏈表中的結(jié)點(diǎn)都具有相同的(A)。A.行號(hào)B.列號(hào)C.元素值D.非零元素個(gè)數(shù)快速排序在最壞情況下的時(shí)間復(fù)雜度為(D)。A.O(logn)B.O(nlogn)C.0(n) D.0(n2)22從二叉搜索樹(shù)中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為(C)。A.O(n)B.O(1)C.O(log2n) D.O(n2)運(yùn)算題(每題6分，共24分).數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的 。當(dāng)結(jié)點(diǎn)之間存在M對(duì)N(M：N)的聯(lián)系時(shí)，稱(chēng)這種結(jié)構(gòu)為.隊(duì)列的插入操作是在隊(duì)列的 進(jìn)行，刪除操作是在隊(duì)列的 進(jìn)行。3,當(dāng)用長(zhǎng)度為N的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top==N表示棧空,則表示棧滿的條件是 。.對(duì)于一個(gè)長(zhǎng)度為n的單鏈存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為 ，在表尾插入元素的時(shí)間復(fù)雜度為.設(shè)W為一個(gè)二維數(shù)組，其每個(gè)數(shù)據(jù)元素占用4個(gè)字節(jié)，行下標(biāo)i

從0到7,列下標(biāo)j從0到3,則二維數(shù)組W的數(shù)據(jù)元素共占用個(gè)字節(jié)。W中第6行的元素和第4列的元素共占用—個(gè)字節(jié)。若按行順序存放二維數(shù)組W,其起始地址為100,則二維數(shù)組元素W[6,3]的起始地址為。TOC\o"1-5"\h\z.廣義表A二(a,(a,b),((a,b),c)),則它的深度為,它的長(zhǎng)度為 。.二叉樹(shù)是指度為2的樹(shù)。一棵結(jié)點(diǎn)數(shù)為N的二叉樹(shù)，其所有結(jié)點(diǎn)的度的總和是 。.對(duì)一棵二叉搜索樹(shù)進(jìn)行中序遍歷時(shí)，得到的結(jié)點(diǎn)序列是一個(gè) 。對(duì)一棵由算術(shù)表達(dá)式組成的二叉語(yǔ)法樹(shù)進(jìn)行后序遍歷得到的結(jié)點(diǎn)序列是該算術(shù)表達(dá)式的 。.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，用二叉鏈表存儲(chǔ)時(shí)，其指針總數(shù)為 個(gè)，其中 個(gè)用于指向孩子， 個(gè)指針是空閑的。.若對(duì)一棵完全二叉樹(shù)從0開(kāi)始進(jìn)行結(jié)點(diǎn)的編號(hào)，并按此編號(hào)把它順序存儲(chǔ)到一維數(shù)組A中，即編號(hào)為0的結(jié)點(diǎn)存儲(chǔ)到A[0]中。其余類(lèi)推，則A[i]元素的左孩子元素為 ,右孩子元素為T(mén)OC\o"1-5"\h\z ，雙親元素為 。.在線性表的散列存儲(chǔ)中，處理沖突的常用方法有 和 兩種。12.當(dāng)待排序的記錄數(shù)較大，排序碼較隨機(jī)且對(duì)穩(wěn)0 0 0 012.當(dāng)待排序的記錄數(shù)較大，排序碼較隨機(jī)且對(duì)穩(wěn)0 0 0 0 00 —1 0 0 00000—25 0 0 0 00 0 7 0 0

定性不作要求時(shí)，宜采用排序；當(dāng)待排序的記錄數(shù)較大，存儲(chǔ)空間允許且要求排序是穩(wěn)定時(shí)，宜采用 排序。運(yùn)算題(每題6分，共24分)1,已知一個(gè)65稀疏矩陣如右所示，試：(1)寫(xiě)出它的三元組線性表；⑵給出三元組線性表的順序存儲(chǔ)表示。2,設(shè)有一個(gè)輸入數(shù)據(jù)的序列是{46,25,78,62,12,80},試畫(huà)出從空樹(shù)起，逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉搜索樹(shù)。3.對(duì)于圖6所示的有向圖若存儲(chǔ)它采用鄰接表，并且每個(gè)頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號(hào)從小到大的次序鏈接的，試寫(xiě)出：(1)從頂點(diǎn)①出發(fā)進(jìn)行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹(shù)；(2)從頂點(diǎn)②出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹(shù)；4,已知一個(gè)圖的頂點(diǎn)集V和邊集E分別為：圖6V二{1,2,3,4,5,6,7};圖6E={<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>};若存儲(chǔ)它采用鄰接表，并且每個(gè)頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號(hào)從小到大的次序鏈接的，按主教材中介紹的拓樸排序算法進(jìn)行排序，試給出得到的拓樸排序的序列。四、閱讀算法(每題7分，共14分)intPrime(intn)inti=1;intx=(int)sqrt(n);while(++i<=x)if(n%i==0)break;if(i>x)return1;elsereturn0;(1)指出該算法的功能；(2)該算法的時(shí)間復(fù)雜度是多少？寫(xiě)出下述算法的功能：voidAJ(adjlistGL,inti,intn)QueueQ;InitQueue(Q);cout<<i<<'';visited[i]=true;QInsert(Q,i);while(!QueueEmpty(Q)){intk=QDelete(Q);edgenode*p=GL[k];while(p!=NULL){intj=p->adjvex;if(!visited[j]){cout<<j<<'';visited[j]=true;QInsert(Q,j);}p=p->next;}算法填空（共8分）如下為二分查找的非遞歸算法，試將其填寫(xiě)完整。IntBinsch(ElemTypeA[],intn,KeyTypeK){intlow=0;inthigh=n-1;while(low<=high){TOC\o"1-5"\h\zintmid= ；if（K==A[mid].key）returnmid;//查找成功，返回元素的下標(biāo)elseif（K<[mid].key） ; //在左子表上繼續(xù)查找else ; //在右子表上繼續(xù)查找}return-1;//查找失敗，返回-1}編寫(xiě)算法（共8分）HL是單鏈表的頭指針，試寫(xiě)出刪除頭結(jié)點(diǎn)的算法。ElemTypeDeleFront（LNode*&HL）模擬試卷三參考答案單選題（每題2分，共20分）1.B2.A3.B4.C5.D6.B7.D 8.A 9.D 10.C填空題（每空1分，共26分）聯(lián)系圖（或圖結(jié)構(gòu)）尾首top==0O（1）O（n）5.128 44 1086.7.有序n-18.有序序列后綴表達(dá)式（或逆波蘭式）9.2nn-1n+165515132-145-2515637圖710.2i+12i+2(i-1)/211.開(kāi)放定址法鏈接法12.快速歸并三、運(yùn)算題（每題6分，共24分）1.(1)((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7)) (3分)（2） 三元組線性表的順序存儲(chǔ)表示如圖7示。（頓(C?2.如圖8所示。3.DFS：BFS：4.拓樸排序?yàn)椋?365四、閱讀算法（每題7分，共14分）1.（1）判斷n是否是素?cái)?shù)（或質(zhì)數(shù)）（2）o（vn）2.功能為：從初始點(diǎn)vi出發(fā)廣度優(yōu)先搜索由鄰接表61所表示的圖。算法填空(8分)(low+high)/2high=mid-1low=mid+1編寫(xiě)算法(8分)ElemTypeDeleFront(LNode*&HL){if(HL==NULL){cerr<<"空表"<<endl;exit(1);}LNode*p=HL;HL=HL->next;ElemTypetemp=p->data;deletep;returntemp;}模擬試卷四一、單選題(每題2分，共20分)以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是線性結(jié)構(gòu)？(B)A.有向圖B.棧C.二叉樹(shù)D.B樹(shù)若某鏈表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除最后一個(gè)結(jié)點(diǎn)，則采用(C)存儲(chǔ)方式最節(jié)省時(shí)間。

B.雙鏈表A.單鏈表B.雙鏈表A.單鏈表C.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表以下哪一個(gè)不是隊(duì)列的基本運(yùn)算？(A)A.在隊(duì)列第i個(gè)元素之后插入一個(gè)元素B.從隊(duì)頭刪除一個(gè)元素C.判斷一個(gè)隊(duì)列是否為空 D.讀取隊(duì)頭元素的值字符A、B、C、D依次進(jìn)入一個(gè)棧，按出棧的先后順序組成不同的字符串，至多可以組成(B)個(gè)不同的字符串？A.15 B.14 C.16 D.21由權(quán)值分別為4,7,6,2的葉子生成一棵哈夫曼樹(shù)，它的帶權(quán)路徑長(zhǎng)度為(B)。A．11 B.37C.19D.53以下6-8題基于下面的敘述：若某二叉樹(shù)結(jié)點(diǎn)的中序遍歷的序列為A、B、C、D、E、F、G，后序遍歷的序列為B、D、C、A、F、G、E。A.E、G、F、A、C、D、BC、F、B、DC.E、A、C、B、D、G、FC、D、F、B該二叉樹(shù)有(A)個(gè)葉子。A.E、G、F、A、C、D、BC、F、B、DC.E、A、C、B、D、G、FC、D、F、B該二叉樹(shù)有(A)個(gè)葉子。A．3 B.2 C.5E、A、G、D.E、G、A、D.4該二叉樹(shù)的按層遍歷的序列為(C)A．E、G、F、A、C、D、B B.E、A、C、B、D、G、FC.E、A、G、C、F、B、D D.E、G、A、C、D、F、B下面的二叉樹(shù)中，（C）不是完全二叉樹(shù)。10,設(shè)有關(guān)鍵碼序列（q,g,m,z,就，下面哪一個(gè)序列是從上述序列出發(fā)建的小根堆的結(jié)果?（C）A.a,g,m,q,z B.a,g,m,z,qC.g,m,q,a,z D.g,m,a,q,z二、填空題（每空1分,共26分）數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的 。當(dāng)結(jié)點(diǎn)之間存在1對(duì)N（1：N）的聯(lián)系時(shí)，稱(chēng)這種結(jié)構(gòu)為一個(gè)廣義表中的元素分為 元素和 元素兩類(lèi)。對(duì)于一個(gè)長(zhǎng)度為n的順序存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為 ,在表尾插入元素的時(shí)間復(fù)雜度為4,向一個(gè)由HS指向的鏈棧中插入一個(gè)結(jié)點(diǎn)時(shí)p時(shí)，需要執(zhí)行的操作是 ;刪除一個(gè)結(jié)點(diǎn)時(shí),需要執(zhí)行的操作是 （假設(shè)棧不空而且無(wú)需回收被刪除結(jié)點(diǎn)）。棧又稱(chēng)為 表，隊(duì)列又稱(chēng)為 表。在稀疏矩陣所對(duì)應(yīng)的三元組線性表中，每個(gè)三元組元素按 為主序、 為輔序的次序排列。若一棵二叉樹(shù)中只有葉子結(jié)點(diǎn)和左、右子樹(shù)皆非空的結(jié)點(diǎn)，設(shè)葉結(jié)點(diǎn)的個(gè)數(shù)為K,則左、右子樹(shù)皆非空的結(jié)點(diǎn)個(gè)數(shù)是。TOC\o"1-5"\h\z以折半(或二分)查找方法從長(zhǎng)度為8的有序表中查找一個(gè)元素時(shí)，平均查找長(zhǎng)度為 。表示圖的三種常用的存儲(chǔ)結(jié)構(gòu)為 、 和 。對(duì)于線性表(78,4,56,30,65)進(jìn)行散列存儲(chǔ)時(shí)，若選用H(K)=K%5作為散列函數(shù)，則散列地址為0的元素有 個(gè)，散列地址為4的有 個(gè)。在歸并排序中,進(jìn)行每趟歸并的時(shí)間復(fù)雜度為 ,整個(gè)排序過(guò)程的時(shí)間復(fù)雜度為 ,空間復(fù)雜度為 。在n個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)造出的所有二叉樹(shù)中，帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)稱(chēng)為。WPL稱(chēng)為。在索引表中,若一個(gè)索引項(xiàng)對(duì)應(yīng)主表的一個(gè)記錄,則此索引為 索引,若對(duì)應(yīng)主表的若干條記錄,則稱(chēng)此索引為 索引。三、運(yùn)算題(每題6分,共24分)寫(xiě)出下列中綴表達(dá)式的后綴形式：3X/(Y-2H)+12+X*(Y+3)2,假定一棵二叉樹(shù)廣義表表示為a(b(c),d(e,f)),分別寫(xiě)出對(duì)它進(jìn)行先序、中序、后序、按層遍歷的結(jié)果。先序：中序：后序：按層：3,已知一個(gè)無(wú)向圖的頂點(diǎn)集為{a,b,c,d,e},其鄰接a矩陣如下所示b01001c10010d0001101101e10110(1)畫(huà)出該圖的圖形；(2)根據(jù)鄰接矩陣從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫(xiě)出相應(yīng)的遍歷序列。4,已知一個(gè)圖的頂點(diǎn)集V和邊集E分別為：V={0,1,2,3,4,5,6,7};E={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10,(4,6)4,(5,7)20};按照普里姆算法從頂點(diǎn)0出發(fā)得到最小生成樹(shù)，試寫(xiě)出在最小生成樹(shù)中依次得到的各條邊。四、閱讀算法(每題7分，共14分)voidAE(Stack&S){InitStack(S);Push(S,3);Push(S,4);intx=Pop(S)+2*Pop(S);Push(S,x);inti,a[5]={2,5,8,22,15};for(i=0;i<5;i++)Push(S,a[i]);while(!StackEmpty(S))cout<<Pop(S)<<'';}該算法被調(diào)用后得到的輸出結(jié)果為：intakm(unsignedm,unsignedn){if(m==0)returnn+1;elseif(n==0)returnakm(m-1,1);elsereturnakm(m-1,akm(m,n-1));}該函數(shù)執(zhí)行的功能是什么？五、算法填空（共8分）

二叉搜索樹(shù)的查找——非遞歸算法boolFind(BTreeNode*BST,ElemType&item){while(BST(!=NULL){TOC\o"1-5"\h\zif(item== ){item=BST->data;//查找成功returntrue;}elseif(item<BST->data)BST=BST-> ;elseBST=BST-> ;}//whilereturn;//查找失敗return六、編寫(xiě)算法（共8分）六、編寫(xiě)算法（共8分）用遞歸的算法編寫(xiě)出對(duì)存入在a[n+1]數(shù)組中的n個(gè)有序元素進(jìn)行二分（又稱(chēng)折半）查找（假定a[0]單元不用）的程序。inthalfsearch(SSTable*a,KeyTypek,intlow,inthigh)int模擬試卷四參考答案一、單選題（每題2分，共20分）1.B2.C3.A4.B5.B6.C7.A8.C9.C10.B二、填空題（每空1分，共26分）1.聯(lián)系樹(shù)（或樹(shù)結(jié)構(gòu)）2.單（子）表一、單選題（每題2分，共20分）1.B2.C3.A4.B5.B6.C7.A8.C9.C10.B二、填空題（每空1分，共26分）1.聯(lián)系樹(shù)（或樹(shù)結(jié)構(gòu)）2.單（子）表O(n)O(1)4.p->next=HS;HS=pHS=HS->next4.p->next=HS;HS=pHS=HS->next先進(jìn)后出先進(jìn)先出行列k-12.625鄰接矩陣鄰接表邊集數(shù)組21O(n)O(nlogn)O(n)2哈夫曼樹(shù)帶權(quán)路徑長(zhǎng)度稠密稀疏運(yùn)算題(每題6分，共24分)TOC\o"1-5"\h\z1. ⑴3X*Y2H*-/1+ f?)2XY3+*+ :工、。先序：a,b,c,d,e,f 出中序：c,b,a,e,d,f后序：c,b,e,f,d,a按層：a,b,d,c,e,f 圖9(1)該圖的圖形如圖9示：(2)深度優(yōu)先遍歷序列為：abdce廣度優(yōu)先遍歷序列為：abedc普里姆：(0,3)2,(0,2)5,(0,1)8,(1,5)6,(3,6)10,(6,4)4,

(5,7)20四、閱讀算法（每題7分，共14分）152285210該函數(shù)的功能是：n+1 當(dāng)m=0時(shí)求：akmmn)=<akm(m一1,1) 當(dāng)m豐0,n=0時(shí)akm(m一1,akm(mn-1))當(dāng)m豐0,n牛0時(shí)五、算法填空（共8分，每一空2分）BST->dataleftrightfalse六、編寫(xiě)算法（8分）五、算法填空（共8分，每一空2分）BST->dataleftrightfalse六、編寫(xiě)算法（8分）遞歸算法：inthalfsearch(SSTable*a,KeyTypek,intlow,inthigh){if(low>high)return0;else{intmid=(low+high)/2ifEQ(k,a[mid].key)returnmid;else if LT(k,a[mid].key) returnhalfsearch(a,k,low,mid-1);elsereturnhalfsearch(a,k,mid+1,high);}模擬試卷五單選題(每題2分，共20分).棧和隊(duì)列的共同特點(diǎn)是(A)。A.只允許在端點(diǎn)處插入和刪除元素B.都是先進(jìn)后出C.都是先進(jìn)先出D.沒(méi)有共同點(diǎn).用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)(D).A.僅修改頭指針 B.頭、尾指針都要修改C.僅修改尾指針 D.頭、尾指針可能都要修改.以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)？(D)A.隊(duì)列B.棧C.線性表D.二叉樹(shù)4,設(shè)有一個(gè)二維數(shù)組A[m][n]，假設(shè)A[0][0]存放位置在644(⑹，A[2][2]存放位置在676(10)，每個(gè)元素占一個(gè)空間，問(wèn)A[3][3](⑹存放在什么位置？腳注(助表示用10進(jìn)制表示。CA．688 B．678 C．692 D．696樹(shù)最適合用來(lái)表示(C)。A.有序數(shù)據(jù)元素B.無(wú)序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù) D.元素之間無(wú)聯(lián)系的數(shù)據(jù)二叉樹(shù)的第k層的結(jié)點(diǎn)數(shù)最多為(A).A．2k-1 B.2K+1 C.2K-1D.2k-17,若有18個(gè)元素的有序表存放在一維數(shù)組A[19]中，第一個(gè)元素放A[1]中，現(xiàn)進(jìn)行二分查找，則查找A[3]的比較序列的下標(biāo)依次為（D）A.1，2，3 B.9，5，2，3C.9，5，3 D.9，4，2，38,對(duì)n個(gè)記錄的文件進(jìn)行快速排序，所需要的輔助存儲(chǔ)空間大致為AA.O（1）B.O（n） C.O（1ogn）D.O（n2）29,對(duì)于線性表（7，34，55，25，64，46，20，10）進(jìn)行散列存儲(chǔ)時(shí)，若選用H（K）=K%9作為散列函數(shù)，則散列地址為1的元素有（C）個(gè)，TOC\o"1-5"\h\zA．1 B．2 C．3 D．410.設(shè)有6個(gè)結(jié)點(diǎn)的無(wú)向圖，該圖至少應(yīng)有（A）條邊才能確保是一個(gè)連通圖。A,5 B,6 C,7 D,8二、填空題（每空1分，共26分）通常從四個(gè)方面評(píng)價(jià)算法的質(zhì)量： 、 、 和 。一個(gè)算法的時(shí)間復(fù)雜度為（m+n2log2n+14n）/n2,其數(shù)量級(jí)表示為3,假定一棵樹(shù)的廣義表表示為A（C,D（E,F,G）,H（I,J））,則樹(shù)中所含的結(jié)點(diǎn)數(shù)為 個(gè)，樹(shù)的深度為 ，樹(shù)的度為 。4,后綴算式923+-102/-的值為。中綴算式（3+4X）

-2Y/3對(duì)應(yīng)的后綴算式為。5.若用鏈表存儲(chǔ)一棵二叉樹(shù)時(shí)，每個(gè)結(jié)點(diǎn)除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個(gè)指針。在這種存儲(chǔ)結(jié)構(gòu)中，n個(gè)結(jié)點(diǎn)的二叉樹(shù)共有 個(gè)指針域，其中有 個(gè)指針域是存放了地址，有 個(gè)指針是空指針。TOC\o"1-5"\h\z6,對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖和無(wú)向圖，在其對(duì)應(yīng)的鄰接表中，所含邊結(jié)點(diǎn)分別有 個(gè)和 個(gè)。.AOV網(wǎng)是一種的圖。.在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖中，包含有條邊，在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，包含有條邊。.假定一個(gè)線性表為（12,23,74,55,63,40），若按Key%4條件進(jìn)行劃分，使得同一余數(shù)的元素成為一個(gè)子表，則得到的四個(gè)子表分別為 、 、 和 。.向一棵B_樹(shù)插入元素的過(guò)程中，若最終引起樹(shù)根結(jié)點(diǎn)的分裂，則新樹(shù)比原樹(shù)的高度 。.在堆排序的過(guò)程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為 ，整個(gè)堆排序過(guò)程的時(shí)間復(fù)雜度為 。.在快速排序、堆排序、歸并排序中， 排序是穩(wěn)定的。三、運(yùn)算題（每題6分，共24分）1.在如下數(shù)組A中鏈接存儲(chǔ)了一個(gè)線性表，表頭指針為A[0].next，

試寫(xiě)出該線性表。A0 1 2 3 4 5 62.請(qǐng)畫(huà)出圖10的鄰接矩陣和鄰接表。3.已知一個(gè)圖的頂點(diǎn)集V和邊集E分別為:2.請(qǐng)畫(huà)出圖10的鄰接矩陣和鄰接表。3.已知一個(gè)圖的頂點(diǎn)集V和邊集E分別為:V二{1,2,3,4,5,6,7};6050789034403572041datanextE={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};用克魯斯卡爾算法得到最小生成樹(shù)，試寫(xiě)出在最小生成樹(shù)中依次得到的各條邊。4.畫(huà)出向小根堆中加入數(shù)據(jù)4,2,5,8,3時(shí)，每加入一個(gè)數(shù)據(jù)后堆的變化。四、閱讀算法（每題7分，共14分）四、閱讀算法（每題7分，共14分）LinkListmynote(LinkListL){//L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針if(L&&L-＞next){q=L；L=L－＞next；p=L；S1：while(p－＞next)p=p－＞next；S1：S2：p－＞next=q；q－＞next=NULL；returnL；請(qǐng)回答下列問(wèn)題：(1)說(shuō)明語(yǔ)句S1的功能;,寫(xiě)出算法執(zhí)行(2)說(shuō)明語(yǔ)句組S2的功能;,寫(xiě)出算法執(zhí)行(3)設(shè)鏈表表示的線性表為(a1,a2,…，an)后的返回值所表示的線性表。voidABC(BTNode*BT)ifBT{ABC(BT->left);ABC(BT->right);cout<<BT->data<<'';該算法的功能是：五、算法填空(共8分)五、算法填空(共8分)二叉搜索樹(shù)的查找——遞歸算法:boolFind(BTreeNode*BST,ElemType&item)if(BST==NULL)returnfalse;//查找失敗else{if(item==BST->data){item=BST->data;//查找成功return ;}elseif(item<BST->data)returnFind( ,item);elsereturnFind( ,item);}//if六、編寫(xiě)算法（共8分）六、編寫(xiě)算法（共8分）統(tǒng)計(jì)出單鏈表HL中結(jié)點(diǎn)的值等于給定值X的結(jié)點(diǎn)數(shù)。intCountX(LNode*HL,ElemTypex)模擬試卷五參考答案一、 單選題(每題2分，共20分)1.A2.D3.D4.C5.C6.D7.D 8.C 9.D 10.A二 填空題(每空1分，共26分)、正確性易讀性強(qiáng)壯性高效率O(n)TOC\o"1-5"\h\z9 3 3-1 34X*+2Y*3/-2n n-1 n+1e 2e7.有向無(wú)回路8.n(n-1)/2n(n-1)9.（12，40）（） （74） （23,55，63）10.增加111.O(log2n)O(nlogn)212.歸并運(yùn)算題（每題6分，共24分）1.線性表為：2.鄰接矩陣：0111010101110111010101110鄰接表如圖11所示：圖113.用克魯斯卡爾算法得到的最小生成樹(shù)為：(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)204.見(jiàn)圖124224245245245四、圖12閱讀算法（每題7分共14分）（1）查詢(xún)鏈表的尾結(jié)點(diǎn)（2）將第一個(gè)結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)點(diǎn)(3)返回的線性表為(a2，a3,…,an,a1)遞歸地后序遍歷鏈?zhǔn)酱鎯?chǔ)的二叉樹(shù)。算法填空(每空2分，共8分)trueBST->left BST->right編寫(xiě)算法(8分)intCountX(LNode*HL,ElemTypex){inti=0;LNode*p=HL;//i為計(jì)數(shù)器while(p!=NULL){if(P->data==x)i++;p=p->next;}//while,出循環(huán)時(shí)i中的值即為x結(jié)點(diǎn)個(gè)數(shù)returni;}//CountX模擬試卷六一、單項(xiàng)選擇題（在每小題的四個(gè)備選答案中，選出一個(gè)正確的答案，并將其號(hào)碼填在題干后的括號(hào)內(nèi)。每小題1分，共10分）1．下面程序段for(i=1;i<=n;i++)for(j=1;j<=i;j++)x=x+1;的時(shí)間復(fù)雜度為(B)。A)O(n) B)O(n2)C)O(n*i) D)O(n+i)2.設(shè)一個(gè)棧的入棧序列是ABCD,則借助于一個(gè)棧所得到的出棧序列不可能是(D)。A)ABCD B)DCBAC)ACDB D)DABC3．當(dāng)求鏈表的直接后繼與求直接前驅(qū)的時(shí)間復(fù)雜度都相同時(shí)，此鏈表應(yīng)為(B)。A)單鏈表 8)雙向鏈表。單向循環(huán)鏈表 口)前面都不正確.已知串s二'BBABBABBA'，t='AB'，c='A'，執(zhí)行置換操作REPLACE(s,t,c)后，s應(yīng)為(A)。A)'BBABABA'B)'BBAABA'C)'BBAAA' D)'BBABABBA'.對(duì)于下圖所示的二叉樹(shù)，后序遍歷結(jié)果序列為)。

HG，C）D，F(xiàn)C，G，ED)HD，B，G，E，C，關(guān)鍵路徑長(zhǎng)度為）。（A6．A)16B)135面AOE網(wǎng)中，C)10D)97．用Dijkstra算法求從源點(diǎn)到其它各頂點(diǎn)的最短路徑的時(shí)間復(fù)雜度為（B）。A)O(n)B)O(n2)C)O(n3)HG，C）D，F(xiàn)C，G，ED)HD，B，G，E，C，關(guān)鍵路徑長(zhǎng)度為）。（A6．A)16B)135面AOE網(wǎng)中，C)10D)97．用Dijkstra算法求從源點(diǎn)到其它各頂點(diǎn)的最短路徑的時(shí)間復(fù)雜度為（B）。A)O(n)B)O(n2)C)O(n3)D)O(nlogn)8．在下列查找方法中平均查找速度最快的是（B）。A）順序查找B）折半查找C）分塊查找口）二叉排序樹(shù)查找9.哈希表的地址區(qū)間為0~17,哈希函數(shù)為H（K）=K%17。采用線性探測(cè)法處理沖突，并將關(guān)鍵字序列26，25，72，38，8，18，59依

次存儲(chǔ)到哈希表中。則59存放在哈希表中的地址是()。次存儲(chǔ)到哈希表中。則59存放在哈希表中的地址是()。TOC\o"1-5"\h\zA)8 B)9C)10 D)1110．快速排序算法的平均時(shí)間復(fù)雜度是(C )。A)O(n) B)O(n2)C)O(nlogn) D)O(logn)22二、填空題(每空1分，共15分)TOC\o"1-5"\h\z.設(shè)有一個(gè)記錄r,設(shè)其類(lèi)型為L(zhǎng)Node,則r實(shí)際所占用的存儲(chǔ)空間的大小為( )。.一個(gè)算法的時(shí)間復(fù)雜度為(5m-3nlogn+7n-9)/(6n),其數(shù)量級(jí)2表示為( )。.如將nXn的對(duì)稱(chēng)矩陣壓縮存儲(chǔ)于sa[k]中，則k等于( )。.如一二維數(shù)組A[1..m,1..n]按行排列，設(shè)A[1,1]的相對(duì)位置為0,每個(gè)元素的大小為1,則任一元素A[i,j]的地址為( )。.線性表的順序存儲(chǔ)結(jié)構(gòu)中存取元素的時(shí)間復(fù)雜度為是( )。.隊(duì)列的插入操作在( )進(jìn)行,刪除操作在( )進(jìn)行。.后綴表達(dá)式“45*32++”的值為( )。.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的樹(shù),此樹(shù)中所有結(jié)點(diǎn)的度數(shù)之和為（ ），設(shè)葉子結(jié)點(diǎn)數(shù)為n0,度為二的結(jié)點(diǎn)數(shù)為n2,則它們TOC\o"1-5"\h\z之間的關(guān)系為（ ）。9．在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（ ）倍。10.在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖中，包含有（ ）條邊；在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，包含有（ ）條弧。11．每次從無(wú)序表中取一個(gè)最小或最大元素，把它們交換到有序表的一端，此種排序方法稱(chēng)為（）排序。12．一種抽象數(shù)據(jù)類(lèi)型應(yīng)包括數(shù)據(jù)和（）兩大部分。三、判斷改錯(cuò)題（判斷正誤,將正確的劃上“，”,錯(cuò)誤的劃上“X”,每小題1分，共10分）1．從邏輯關(guān)系上講,數(shù)據(jù)結(jié)構(gòu)主要分為兩大類(lèi)：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。 （ ）2．?dāng)?shù)組可看成線性結(jié)構(gòu)的一種推廣,所以可對(duì)數(shù)組進(jìn)行插入與刪除操作。 （ ）3．在刪除鏈表結(jié)點(diǎn)時(shí),計(jì)算機(jī)能自動(dòng)地將其后繼的各個(gè)結(jié)點(diǎn)向前移動(dòng)。（）.利用棧求表達(dá)式的值時(shí)，設(shè)立操作數(shù)棧OPND,設(shè)OPND只有2個(gè)存儲(chǔ)單元，則表達(dá)式（A-B）*C+D將不會(huì)發(fā)生發(fā)生上溢現(xiàn)象。（）.串是n個(gè)字母的有限序列（n>=0）。.n階下三角矩陣的非零元素的個(gè)數(shù)最多為n（^D。2（）.二叉樹(shù)只能采用二叉鏈表來(lái)存儲(chǔ)。（）.圖G的某一最小生成樹(shù)的代價(jià)一定小于其它生成樹(shù)的代價(jià)。（）.B+樹(shù)是一種特殊的二叉樹(shù)。（ ）10.所有的簡(jiǎn)單排序（即時(shí)間復(fù)雜度為O（n2）的排序）都是穩(wěn)定排序。（ ）四、簡(jiǎn)答題（每小題4分，共20分）.對(duì)于下列雙向鏈表，設(shè)結(jié)構(gòu)為（prior,data,next）,結(jié)點(diǎn)類(lèi)型為Inode,試寫(xiě)出在p所指結(jié)點(diǎn)之前插入元素x的語(yǔ)句序列。.對(duì)于下圖，用Prim算法從結(jié)點(diǎn)1出發(fā)構(gòu)造出一棵最小生成樹(shù)，要求圖示出每一步的變化情況。3.已知一棵二叉樹(shù)的先序序列與中序序列分別如下，試畫(huà)出此二叉樹(shù)。先序序列：ABCDEFGHIJ中序序列：CBEDAGHFJI4．給定一組權(quán)值{3，4，7，14，15，20}，試畫(huà)出相應(yīng)的哈夫曼樹(shù)，并計(jì)算帶樹(shù)路徑長(zhǎng)度WPL的值。5.有關(guān)鍵字序列{7,23,6,9,17,19,21,22,5},Hash函數(shù)為H(key)=key%5，采用鏈地址法處理沖突，試構(gòu)造哈希表。五、算法題(共25分)1.程序填空題(每空2分，共8分)下面程序的功能是二叉樹(shù)的中序遍歷的非遞歸算法，其中二叉樹(shù)的結(jié)點(diǎn)結(jié)構(gòu)為(lchild,data,rchild),棧的常用方法有：入棧Push,出棧P。P，判空StackEmpty；試將程序補(bǔ)充完整。template<classType>BiTreeNode*BiTree<Type>::GoFarLeft(BiTreeNode<Type>*T,Stack<BiTreeNode<Type>*>&S){if(!T)returnNULL;while(T->lchild){Push(S,T);T=;}returnT;}template<classType>voidBiTree<Type>::Inorder(BiTreeNode<Type>*T,void(*visit)(Type&e)){Stack<BiTreeNode<Type>*>&S;t=GoFarLeft(T,S);//找到最左下的結(jié)點(diǎn)while(t){visit(t->data);if(t->rchild)t=GoFarLeft(,S);elseif(!StackEmpty(S))t=;elset=;//?？毡砻鞅闅v結(jié)束}//while}//Inorder2．程序填空題(每空2分，共8分)下面程序的功能是用線性探測(cè)再散列處理沖突(即Hi=(H(key)+i)%m),哈希函數(shù)為H(key)二key%m,進(jìn)行哈希表的插入算法。(如表中已存在關(guān)鍵字相同的記錄或無(wú)插入位置，則不進(jìn)行插入)，試將程序補(bǔ)充完整。typedefenum{SUCCESS,UNSUCCESS,OVERFLOW}Status;template<classType>typedefstruct{Type*elem;intm;}HashTable;template<classType>StatusSerchHashTable(HashTable<Type>H,Typee){inti=0,k=；//i為沖突的次數(shù),k為哈希函數(shù)的值while(i<m&&H.elem[k].key!=NULLKEY&&p->elem.key!=e.key){;p=(p+i)%m;}//whileif(i>=m)returnOVERFLOW;elseif(p->elem.key!=e.key)return;else{H.elem[p].elem=;returnSUCCESS;}//if}//SerchHashTable3．(9分)閱讀下面算法，試回答：(1)根據(jù)鄰接表畫(huà)出對(duì)應(yīng)的圖；(2)當(dāng)圖的鄰接表如下時(shí)，執(zhí)行算法T(g,1)時(shí)，輸出的結(jié)果是什么？（3）函數(shù)T的功能是什么？圖的鄰接表為：template<classType>voidAdjGraph<Type>::T(AdjGraph<Type>g;inti){ArcNode<Type>*p;cout<<g[i].vertex;Visited[i]=true;p=g[i].link;while(p){if(!Visited[p->adjvex])T(p->adjvex);p=p->next;}//while}//T六、寫(xiě)算法(共20分)1．(12分)以單鏈表為存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)簡(jiǎn)單選擇排序，排序的結(jié)果是單鏈表按關(guān)鍵字值升序排序，試編寫(xiě)此算法。算法申明如下：template<classType>voidLinkList<Type>::SimpleSelectSort(Lnode<Type>*la)2．(8分)下面是一個(gè)二叉樹(shù)的中序遍歷的遞歸算法，試改寫(xiě)此算法，消去第二個(gè)遞歸調(diào)用MidOrder(T->rchild,visit)。template<classType>voidBiTree<Type>::PreOrder(BiTreeNode<Type>*T,void(*Visit)(Type&e)){if(T){MidOrder(T->lchild,Visit);Visit(T->data);MidOrder(T->rchild,Visit);}//if}//MidOrder模擬試卷六參考答案一、單項(xiàng)選擇題(在每小題的四個(gè)備選答案中，選出一個(gè)正確的答案，并將其號(hào)碼填在題干后的括號(hào)內(nèi)。每小題1分，共10分)1．B)2．D)3．B) 4．A) 5．D)6．A) 7．B) 8．B) 9．D) 10．C)二、填空題(每空1分，共15分).參考答案：sizeof(LNode).參考答案：O(n2).參考答案：n(n1)2.參考答案：(i-1)*n+j-1.參考答案：0(1)6．參考答案：隊(duì)尾隊(duì)頭7．參考答案：25.參考答案：n-1 n0=n2T9．參考答案：210.參考答案：n(nT)/2 n(n—1)11．參考答案：選擇(直接選擇排序或堆排序)12．參考答案：操作三、判斷改錯(cuò)題(判斷正誤，將正確的劃上“，”,錯(cuò)誤的劃上“X”,每小題1分，共10分).參考答案：J.參考答案：X.參考答案：X.參考答案：J.參考答案：X.參考答案：J.參考答案：X.參考答案：X.參考答案：X.參考答案：X四、簡(jiǎn)答題(每小題4分，共20分)1．參考答案：

s=newlnode;s->data=x;p->prior->next=s;s-prior=p->prior;s->next=p;p->prior=s;2.參考答案：本題用Prim算法構(gòu)造出最小生成樹(shù)共需四步，具每一步的變化情況如如：3．參考答案：4．參考答案：哈夫曼樹(shù)如下圖所示：

WPL=20*2+15*2+14*2+7*3+3*4+4*4=1475．參考答案：哈希表如下圖所示：五、算法題(共25分).參考答案：T->lchild t->rchildPop(S)NULL.參考答案：e.key%m++iUNSUCCESSe3．(1)參考答案：(2)參考答案：V1V2V4V3(3)參考答案：從頂點(diǎn)Vi出發(fā)進(jìn)行深度優(yōu)先搜索圖。六、寫(xiě)算法(共20分)1．參考答案：template<classType>voidLinkList<Type>::SimpleSelectSort(Lnode<Type>*la)//用單鏈表為存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)選擇排序Lnode<Type>*p,q;Typex;if(la->next){p=la->next;while(p->next){minp=p;q=p->next;while(q){if(minp->data>q\.data)minp=q;q=q->next;}//whileif(minp!=p{x=p->data;p->data=minp->data;minp->data:=x;}//ifp=p->next;}//while}//if}//SimpleSelectSort2．參考答案：template<classType>voidBiTree<Type>::MidOrder(BiTreeNode<Type>*T,void(*Visit)(Type&e)){while(T){MidOrder(T->lchild,Visit);Visit(T->data);T=T->rchild;}//while}//MidOrder模擬試卷七一、單項(xiàng)選擇題(在每小題的四個(gè)備選答案中，選出一個(gè)正確的答案，并將其號(hào)碼填在題干后的括號(hào)內(nèi)。每小題1分，共10分)1.假設(shè)執(zhí)行語(yǔ)句S的時(shí)間為O(1),則執(zhí)行下列程序段for(i=1;i<=n;i++)for(j=i;j<=n;j++)S;的時(shí)間為(B)A)O(n) B)O(n2)C)O(n*i) D)O(n+i)2．設(shè)棧最大長(zhǎng)度為3，入棧序列為1，2，3，4，5，6，則不可能的出棧序列是(D)。A)1，2，3，4，5，6 B)2，1，3，4，5，6

C)3，4，2，1，5，6D)4，3，2，1，5，6C)3，4，2，1，5，6D)4，3，2，1，5，6.設(shè)單鏈表的結(jié)點(diǎn)結(jié)構(gòu)為(data,next),已知指針q所指結(jié)點(diǎn)是指針p所指結(jié)點(diǎn)的直接前驅(qū)，如在*q與*p之間插入結(jié)點(diǎn)*s,則應(yīng)執(zhí)行的操作為(B)。A)s->next=p->next;p->next=s;B)q->next=s;s->next=p;C)p->next=s-next;s->next=p;D)p->next=s;s-next=q;TOC\o"1-5"\h\z.串S='ABCDEF'的串長(zhǎng)為( C)。A)3 B)4C)7 D)8.下面二叉樹(shù)按(C)遍歷得到的序列是FEDBIHGCA。A)先序 B)中序C)后序 D)層次6．用Floyd算法求每一對(duì)頂點(diǎn)之間的最短路徑的時(shí)間復(fù)雜度為(C)。A)O(n) B)O(n2)C)O(n3) D)O(nlogn)7．具有n個(gè)頂點(diǎn)的無(wú)向圖，它可能具有的邊數(shù)的最大值為)。A)(n2+n)/2 B)n2C)(n2-n)/2 D)n8．二分查找法要求被查找的表是(C)。A)順序表 8)鏈接表C)順序表且是按值遞增或遞減次序排列 D)不受上述的任何限制9．在一待散列存儲(chǔ)的線性表(18，25，63，50，42，32，90)，若選用h(k)=k%7作為散列函數(shù)，則與元素18沖突的元素有(C)個(gè)。TOC\o"1-5"\h\zA)0 B)1C)2 D)310．在下列排序算法中，不穩(wěn)定的是(D )。A)直接插入排序 B)折半插入排序C)歸并排序 口)直接選擇排序二、填空題(每空1分，共15分)1．當(dāng)一個(gè)傳值型形式參數(shù)所占空間較大時(shí)，最好說(shuō)明為( )，以節(jié)省參數(shù)值傳輸時(shí)間和存儲(chǔ)參數(shù)的空間。.一個(gè)算法的時(shí)間復(fù)雜度為(5n6-3mlog2n+7n-9)/(3n2+1),其數(shù)量級(jí)表示為( )。.有一矩陣為a[-3：1,2:6],每個(gè)元素占一個(gè)存儲(chǔ)單元，存儲(chǔ)的)。首地址為100,以行序?yàn)橹?，則元素a(-1,4)的地址為()。4．一維數(shù)組的邏輯結(jié)構(gòu)是()。TOC\o"1-5"\h\z5．在有n個(gè)結(jié)點(diǎn)的單鏈表la中，刪除指定結(jié)點(diǎn)p的操作delete(la,p)的時(shí)間復(fù)雜度為( )。6．棧的插入與刪除操作在()進(jìn)行，出棧操作時(shí)，需要修改( )。7.表達(dá)式3*(x+2)-5的后綴表達(dá)式為()。8．對(duì)于一個(gè)具有9個(gè)結(jié)點(diǎn)的二叉樹(shù)的最小深度為( )，最大深度為( )。.在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，要連通所有頂點(diǎn)則至少需要( )條邊。.表示圖的最常用兩種存儲(chǔ)結(jié)構(gòu)是( )與( )。.每次從無(wú)序表中取一個(gè)元素，把它插入到有序表中的適當(dāng)位置，此種排序方法稱(chēng)為()排序。12.已知一有序表(13，20，25，37，48，58，61，78，83，90，128)，當(dāng)二分查找值48的元素時(shí)，經(jīng)過(guò)( )次比較后查找成功。三、判斷改錯(cuò)題(判斷正誤,將正確的劃上“J”,錯(cuò)誤的劃上“X”,每小題1分，共10分).數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系。().數(shù)組不是一種隨機(jī)存取結(jié)構(gòu)。()3．順序表在物理存儲(chǔ)空間中一定是連續(xù)的。()4.設(shè)一個(gè)棧的入棧序列是ABCD,則借助于一個(gè)棧能得出棧序列ACDB。( )5．串的長(zhǎng)度是指串中不同字符的個(gè)數(shù)。()6．矩陣壓縮存儲(chǔ)的方法都是用三元組表存儲(chǔ)矩陣元素。()7.結(jié)點(diǎn)數(shù)為n的完全二叉樹(shù)的深度為log9n+1。( )28．在一個(gè)有向圖的鄰接表中，如果某個(gè)頂點(diǎn)的鏈表為空，則此頂點(diǎn)的度一定為零。().在順序表中取出第i個(gè)元素所花費(fèi)時(shí)間與i成正比。 ().在快速排序算法中，取待排序的n個(gè)記錄中的某個(gè)記錄(如第一個(gè)記錄)的鍵值為基準(zhǔn)，將所有記錄分為兩組，此記錄就排在這兩組的中間，這也是此記錄的最終位置。()四、簡(jiǎn)答題(每小題4分，共20分).在雙向循環(huán)鏈表中p所指結(jié)點(diǎn)之后插入$所指結(jié)點(diǎn)，設(shè)結(jié)點(diǎn)結(jié)構(gòu)為(priou,data,next),試給出語(yǔ)句序列。.對(duì)于下圖，用Kruskal算法構(gòu)造出一棵最小生成樹(shù)，要求圖示出每一步的變化情況。.已知一棵二叉樹(shù)的后序序列與中序序列分別為DBECA與BDAEC,試畫(huà)出此二叉樹(shù)。.對(duì)于權(quán)值序列w={1,10,8,5,3,1,3},試畫(huà)出它對(duì)應(yīng)的哈夫曼樹(shù)。5．已知關(guān)鍵字序列{12,26,38,89,56}，試構(gòu)造平衡二叉樹(shù)。五、算法題(共25分)1．程序填空題(每空2分，共8分)下面程序的功能是二叉樹(shù)的層次遍歷的非遞歸算法，其中二叉樹(shù)的結(jié)點(diǎn)結(jié)構(gòu)為(lchild,data,rchild),隊(duì)列的常用方法有：入隊(duì)EnQueue,出隊(duì)DlQueue,判空QueueEmpty；試將程序補(bǔ)充完整。template<classType>voidBiTree<Type>::levelorder(BiTreeNode<Type>*T,void(*Visit)(Type&e)){Queue<BiTreeNode<Type>*>&Q;BiTreeNode<Type>*pEnQueue(Q,T);;while(!){if(p->lchild){EnQueue(Q,p->lchild);visit(p->lchild->data)}if(){EnQueue(Q,p->rchild);visit(p->rchild->data)}}//while}//levelorder2．程序填空題(每空2分，共8分)下面程序的功能是用鏈地址法處理沖突，哈希函數(shù)為H(key)二key%m,進(jìn)行哈希表的插入算法。(如表中已存在關(guān)鍵字相同的記錄，則不進(jìn)行插入)，試將程序補(bǔ)充完整。typedefenum{SUCCESS,UNSUCCESS}Status;template<classType>typedefstructNode{Typeelem;structNode*next;}Node,*LinkList;template<classType>typedefstruct{LinkList<Type>*head;intm;}HashTable;template<classType>StatusSerchHashTable(HashTable<Type>H,Typee){intk=e.key%m;Node<Type>*pre=NULL,*p=H[k].head;while(p&&p->elem.key!=e.key){pre=p;p=;}//whileif(!p){Node<Type>*q=newNode;q->elem=;pre->next=;q->next=NULL; 〃將q追加在相應(yīng)鏈表的末尾returnSUCCESS;}elsereturn;}//SerchHashTable3．(9分)閱讀下面的算法，試回答：(1)此算法的功能是什么？(2)變量c的結(jié)果表明什么？(3)對(duì)于如下的有向圖，執(zhí)行此算法后c的值是多少？template<classType>intMGraph<Type>::cid(MGraph<Type>g){//g是有向圖的鄰接數(shù)組存儲(chǔ)結(jié)構(gòu)inti,j,c=0;for(j=0;j<g.vexnum;j++){i=0;while(g.arcs[i,j]==0&&i<g.vexnum)i++;if(i>=g.vexnum)c++}//forreturnc;}//cid六、寫(xiě)算法（共20分）1．（12分）以單鏈表為存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)直接插入排序，排序的結(jié)果是單鏈表按關(guān)鍵字值升序排序，試編寫(xiě)此算法。算法申明如下：template<classType>voidLinkList<Type>::StraitInsertSort(Lnode<Type>*la)2．（8分）下面是一個(gè)二叉樹(shù)的前序遍歷的遞歸算法，試改寫(xiě)此算法，消去第二個(gè)遞歸調(diào)用PreOrder（T->rchild,Visit）。template<classType>voidBiTree<Type>::PreOrder(BiTreeNode<Type>*T,void(*Visit)(Type&e)){if(T){Visit(T->data);PreOrder(T->lchild,Visit);PreOrder(T->rchild,Visit);}//if}//PreOrder模擬試卷七參考答案一、單項(xiàng)選擇題(在每小題的四個(gè)備選答案中，選出一個(gè)正確的答案，并將其號(hào)碼填在題干后的括號(hào)內(nèi)。每小題1分，共10分)1．B)2．D)3．B) 4．C) 5．C)6．C) 7．C) 8．C) 9．C)10．D)二、填空題(每空1分，共15分)1．參考答案：引用型2.參考答案：O(n4)3．參考答案：1124．參考答案：線性結(jié)構(gòu)5.參考答案：O(n)6．參考答案：棧頂棧頂指針7．參考答案：3x2+*5-9.參考答案：n-110．參考答案：鄰接知陣鄰接表11．參考答案：插入12．參考答案：4三、判斷改錯(cuò)題（判斷正誤，將正確的劃上“J”,錯(cuò)誤的劃上“X”,每小題1分，共10分）.參考答案：J.參考答案：X.參考答案：J.參考答案：J.參考答案：X.參考答案：X.參考答案：X.參考答案：X.參考答案：X.參考答案：J四、簡(jiǎn)答題（每小題4分，共20分）.參考答案：在雙向循環(huán)鏈表中p所指結(jié)點(diǎn)之后插入$所指結(jié)點(diǎn)的指針變化圖示如下：出語(yǔ)句序列如下：p->next->priou=s;s->next=p->next;s->priou=p;p->next=s;2．參考答案：（只要考生正確寫(xiě)出其中任四步即給滿分）本題用Kruskal算法構(gòu)造出最小生成樹(shù)共需五步，具每一步的變化情況如如:參考答案：3．Kruskal算法構(gòu)造出最小生成樹(shù)共需五步，具每一步的變化情況如如:參考答案：3．參考答案1參考答案1Visit（T->data）QueueEmpty（Q）DlQueue（Q,p）p->rchild.參考答案：p->nexteqUNSUCCESS3．（1）參考答案：求圖中入度為零的頂點(diǎn)數(shù)。（2）參考答案：圖中入度為零的頂點(diǎn)數(shù)。（3）參考答案：2六、寫(xiě)算法（共20分）1．參考答案：template<classType>voidLinkList<Type>::StraitInsertSort(Lnode<Type>*la)//用單鏈表實(shí)現(xiàn)直接插入排序Lnode<Type>*p,*q,*pre,*t;Typex;if(la->next){q=la->next->next;la->next->next=NULL;while(q){pre=la;p=la->next;x=q->data;while(p&&x>=p->data){pre=p;p=p->next;}//whilet=q;q=q->next;pre->next=t;t->next=p;}//while}//if}//StraitInsertSort2．參考答案：template<classType>voidBiTree<Type>::PreOrder(BiTreeNode<Type>*T,void(*Visit)(Type&e)){while(T){visit(T