單選題（每題2分，共20分 ）方面的內(nèi)容健壯性和可讀 C.p->next=HL; D.HL=p;p- 對線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？( 23 B.32C.31 D.12 有向 A．低于法處理B. 高于法處理C．與法處理相同 若需要利用形參直接實參時應(yīng)將形參變量說明（ 參數(shù) D． 有相同的（A行 10.10.從二叉搜索樹中查找一個元素時，其時間復(fù)雜度大致為( )A. B. C. D. 運算題（每題6分，共24分 在M對N（M：N）的聯(lián)系時，稱這種結(jié)構(gòu)為 隊列的插入操作是在隊列的 進行，刪除操作是在隊列的 對于一個長度為n的單鏈的線性表在表頭插入元素的時間復(fù)雜度為O(1) ，在表入元素的時間復(fù)雜度為O(n) 5.設(shè)W為一個二維數(shù)組，其每個數(shù)據(jù)元素占用4個字節(jié)，行下標i從0到7，列下標j從0到3，則二維數(shù)組W的數(shù)據(jù)元素共占用＿_128＿個字節(jié)。W中第6行的元素和第4列的元素共占用＿_44 的起始地址為＿108 廣義表A=(a,(a,b),((a,b),c)),則它的深度為 ，它的長度 二叉樹是指度為2的 二叉樹，其所有結(jié)點的度的總和是n-1 對于一棵具有n個結(jié)點的二叉樹，用二叉鏈表時，其指針總數(shù) 個，其 個用于指向孩子 10.若對一棵完全二叉樹從0開始進行結(jié)點的編號，并按此編號把它順序存儲到一維數(shù)組A中，即編號為0的結(jié)點到A[0]中。其余類推，則A[i]元素的左孩子元素為_2加一 ,右孩子元素為_2加二 雙親元素為（i-1）/2 性表的散列中，處理的常用方法 開放地址 兩種12.當(dāng)待排序的記錄數(shù)較大，排序碼較隨機且對穩(wěn)定性不作要求時，宜采用 排序；當(dāng)待排序的記錄數(shù)較大，空間允許且要求 并 100 0000000000000000000 0 46,25,78,621280},試畫出從空樹起， ; 圖6 intPrime(int{intwhile(++i<=x)if(i>x)return1;elsereturn} voidAJ(adjlistGL,inti,int{QueueQ;cout<<i<<'';while(!QueueEmpty(Q)){intk=QDelete(Q);{{cout<<j<<'';}}}} {intlow=0;while{int if(K==A[mid].key) returnmid; elseif(K<[mid].key)

}

} ElemTypeDeleFront(LNode*&一 一 單選題（每題2分，共20分 2.A 二 二 填空題（每空1分，共26分 655151326551513245515637 快 歸三 三 運算題（每題6分，共24分 (3分圖 排序為： 四 四 (1)n是否是素數(shù)（或質(zhì)數(shù) 功能為：從初始點vi出發(fā)廣度優(yōu)先搜索由鄰接表GL所表示的圖。 算法填空（8分） 六 六 {if} deletep;return}一、一、單選題（每題220分1.棧和隊列的共同特點是(啊)。2.用方式的隊列，在進行插入運算時(的僅修改頭指 B.頭、尾指針都要修C.僅修改尾指 3.以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)？D)A.隊列B.棧C.線性表D.4.A[m][n]A[0][0]10進制表示。 樹最適合用來表示( )有序數(shù)據(jù)元 B.無序數(shù)據(jù)元C.元間具有分支層次關(guān)系的數(shù) D.元間無聯(lián)系的數(shù) 二叉樹的第k層的結(jié)點數(shù)最多為 D.2k- 中，現(xiàn)進行二分查找，則查找A［3］的比較序列的下標依次為( A. B.C. D. A. B. C. D. 對于線性表（7，34，55，25，64，46，20，10）進行散列時 10.設(shè)有6個結(jié)點的無向圖，該圖至少應(yīng)有(A)條邊才能確保是通 1.通常從四個方面評價算法的質(zhì)量：_正確性_、_易讀性 和高效性 。A（C，D（E，F(xiàn)，G，H（I，J，所含的結(jié)點數(shù)為9 個，樹的深度為_3 ，樹的度為 后綴算式923+-102/-的值為_- 對應(yīng)的后綴算式 34X*2Y*3/ 5.若用鏈表一棵二叉樹時，每個結(jié)點除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個指針。在這種結(jié)構(gòu)中，n個結(jié)點的二叉樹共有2n個指針域，其中有n-1 6.對于一個具有n個頂點和e條邊的有向圖和無向圖，在其對應(yīng)的鄰接表中，所含邊結(jié)點分別有e 個和2e 7.AOV網(wǎng)是一種有向無回 的圖8.在一個具有n個頂點的無向完全圖中包含有n(n-1)/2 一個具有n個頂點的有向完全圖中，包含有_n(n-1) 9.假定一個線性表為(12,23,74,55,63,40)Key4條件進行劃分，使 、 、 10.向一棵B_樹插入元素的過程中，若最終引起樹根結(jié)點的，則新樹 增加1 11.在堆排序的過程中，對任一分支結(jié)點進行篩運算的時間復(fù)雜度為（log2 12.在快速排序、堆排序、歸并排序中，_歸 排序是穩(wěn)定的 運算題（每題6分，共24分1.在如下數(shù)組A中了一個線性表，表頭指針為A[0].next，試寫

353572041 4,2,583 LinkListmynote(LinkList{//L是不結(jié)點的單鏈表的頭指q=L；L=L－>next；p=L；S1：while(p－>next)p=p－>next； } }, voidABC(BTNode*{ ABC(BT->right);}} {ifelse{ returnFind( } intCountX(LNode*HL,ElemType一 一 二 二 強壯 34X*+2Y*3/ （ 10.11. 12.三 三 11 11

鄰接矩陣：0

4422424442242452458245 235235 四 四 五 五 算法填空（每空2分，共8分 六 六 {if(P->data==x)i++;,return一、一、單選題（28分平均查找長度（x與元素的平均比較次數(shù)，假定查找每個元素的概率都相等）為(c)。 插入一個s所指的結(jié)點,則執(zhí)行(D)。 q→link=s; s→link3、3 棧 棧 任意位 指定位4、4、由權(quán)值分別為11，8，6，2，5的葉子結(jié)點生成一棵樹，它的 二 二 填空題（每空1分，共32分 、_線性 2、2、一種抽象數(shù)據(jù)類型包 數(shù)據(jù)描述 操作兩個部分 4376201 7、7、一棵高度為5的二叉樹中最少含有 個結(jié)點，最多含有一棵高度為5的理想平衡樹中，最少含有 。9、9和1010假定一棵樹的廣義表表示為A（B（C，D（E，F(xiàn)，G， 樹的度 ,結(jié)點H的雙親結(jié)點 ,孩子結(jié)點。11、11、在堆排序的過程中，對任一分支結(jié)點進行篩運算的時間復(fù)雜度為,整個堆排序過程的時間復(fù)雜度為 12、12、mB_樹插入元素的過程中，每向一個結(jié)點插入一引項數(shù)等于個，則必須把它為個結(jié)點。三 三 運算題（每小題6分，共24分1、1、已知一組記錄的排序碼為（46，79，56，38，40，80,95，24，寫（12，23，45，57，20，03，78，31，15，36HT[0..12]H（key）key%13并用線性探查法解3、3、已知一棵二叉樹的前序遍歷的結(jié)果序列是ABECKFGHIJ，中序遍歷的結(jié)果是EBCDAFHIGJ，試寫出這棵二叉樹的后序遍歷結(jié)果。V={（0，1（0，4（1，2（1，7（2，8（3，4（3，8（5，6（5，8（5，9（6，7（7，8（8，9）}圖四 四 閱讀算法，回答問題（每小題8分，共16分 #include<iostream.h>#include<stdlib.h>consstintstackmaxsize=30;typedefintelemtype;structstackinttop;#include main({stacka;intx;cinwhile(x!=-1)push(a,x);cin>>x;}while(!stackempty(a))cout}.Temte<calss type>void BinTree<Type>unknown(BinTreeNode<Type>*t){de<Type> if(p!=NULL){temp=p→leftchild;p→rightchild=temp;}}五 五 算法填空，在畫有橫線的地方填寫合適的內(nèi)容（10分對順序的有序表進行二分查找的遞歸算法intBinsch(ElemTypeA[],intlow,inthigh,KeyTypeK{if(low<={intmid=if(K==A[mid].key)returnmid;elseif(K<A[mid].key)return2}

return 六 六 編寫算法（10分元素的次序為a1，……an-1，an，則逆序后變?yōu)?an，an-1，……a1。 contrary(Lnode*&HL)1234CDAB3：（38，56，25，60，42，744HL→nextNULL；HL=HL→next；5：前一個位置；n-1；6：S.stack[S.top]; 7：5 1010、3、3、B、In12：m、m-1140]40] 2 查找成功的平均查找長度：ASLSUCC=14/10=1.44圖 五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容（10分）-{LnodeWhile{}}第一部分選擇題(30分算法指的是（ D．解決問題的有限運算序線性表采用鏈式時，結(jié)點的地址（將長度為n的單鏈表在長度為m的單鏈表之后的算法的時間復(fù)雜度（ B．節(jié)省空間，降低上溢發(fā)生的機率設(shè)數(shù)組data[m]作為循環(huán)隊列SQ的空間，front為隊頭指針，rear為隊尾指針，則執(zhí)行出隊操作后其頭指針front值為（） 7.若目標串的長度為n，模式串的長度為[n/3]，則執(zhí)行模式匹配算法時，在最 A．O（3 ） 0233502335

80080

800800

0 B.050040 3C. 3

00

0

005 4 4 0 0的結(jié)點個數(shù)為 在含n個頂點和e條邊的無向圖的鄰接矩陣中,零元素的個數(shù)為 ne條弧的有向圖用鄰接表表示,相關(guān)的所有弧的時間復(fù)雜度是 則所采用的排序方法是 C．三叉排序樹D．線性鏈表 第二部分非選擇題（70分20分）不寫解答過程，將正確的答案寫在每小題的空格內(nèi)。錯填或不填 的指針head可用p表示為head= 棧頂?shù)奈恢檬请S 操作而變化的 假設(shè)一個9階的上三角矩陣A按列優(yōu)先順序壓縮在一維數(shù)組B中，其中B[0]矩陣中第1個元素a1,1,則B[31]中存放的元素是 個葉子結(jié)點 在單鏈表上難以實現(xiàn)的排序方法 在有序表（12，24，36，48，60，72，84）中二分查找關(guān)鍵字72時所需進 文件P=（）,(x,)）x,),x)） 110頂點集為{abcde （2）ae 35，20，3348進行查找時，所需進行的比較次數(shù)各四、算法閱讀題（本大題共4小題，每小題5分，共20分） 當(dāng) 11

當(dāng)

intcomstr(LinkStrings1,LinkString } }①②③④⑤LinkListmynote(LinkList{//L是不結(jié)點的單鏈表的頭指q=L；L=L－>next；p=L；S1：while(p－>next)p=p－>next； } },，typedefintfront[2],rear[2]；下算法填空，實現(xiàn)第i個隊列的入隊操作。intEnQueue(Queue2*Q,inti,DateTypeif(i<0||i>1)return0； Q－>rear[i]=[③ }①②③typedefstructnode{DateTypedata；Structnode*next；typedefListNode*LinkList；LinkListLeafhead=NULL；VoidInorder(BinTreeT){If((!T－>lchild)&&(!TListNode))；s－>data=T－>data；s}}}intarrange(inta[],int1,inth,int{//1hinti,j,t；i=1；while(i<j&&a[j]>=x)j--；while(i<j&&a[j]>=x)i++； } returni； returni－1；}寫一個調(diào)用上述函數(shù)實現(xiàn)下列功能的算法：對一整型數(shù)組b[n]中的元素一 一 單項選擇題（本大題共15小題，每小題2分，共30分 14．Ｃ16．（或結(jié)構(gòu) 18．進棧和退 圖 圖29（１）

ASL32112 ⑤return0 31.（1）返回的線性表為32.①(i＋1)%2(GH∧DGH∧D（2）中序遍歷二叉樹，按遍歷序列中葉子結(jié)點數(shù)據(jù)域的值構(gòu)建一個以Leafhead為頭指針的逆序單鏈表（或按二叉樹中葉子結(jié)點數(shù)據(jù)自右至34（1）intf(intb[],int intf(intb[],int int int q=arrange(b,p+1,n－1,1)；q=arrange(b,0,p,0)；returnq－p； returnp－q； 組成數(shù)據(jù)的基本單位是（(A)數(shù)據(jù) (B)數(shù)據(jù)類型(C)數(shù)據(jù)元素(D)數(shù)據(jù)變<3，4>，<4，1>}，則數(shù)據(jù)結(jié)構(gòu)A是 (A)線性結(jié) (B)樹型結(jié)構(gòu)(C)圖型結(jié)構(gòu)(D)集數(shù)組的邏輯結(jié)構(gòu)不同于下列（）(A)線性 (B) (C)隊 (D)i(i≥1)層上的結(jié)點數(shù)最多有（）(A) (B) (C)2i- (D)p-SQE1、E2、E3、E4、E5E6依次通E6、E5和E1，則棧S的容量至少應(yīng)該是（(A) (B) (C) (D)將10階對稱矩陣壓縮到一維數(shù)組A中，則數(shù)組A的長度最少為（(A) (B) (C) (D)數(shù)為（(A) (B) (C) (D)根據(jù)二叉樹的定義可知二叉樹共有 (A) (B) (C) (D)10.設(shè)有以下四種排序方法，則 ）的空間復(fù)雜度最大(A)冒泡排 (B)快速排序(C)堆排 (D)排1.設(shè)順序循環(huán)隊列Q[0：m-1]的隊頭指針和隊尾指針分別為F和R，其中所在的位置，則出隊列的語句為F= 2.設(shè)線性表中有n個數(shù)據(jù)元素，則在順序結(jié)構(gòu)上實現(xiàn)順序查找的平均 ，在鏈式結(jié)構(gòu)上實現(xiàn)順序查找的平均時間復(fù) 3.設(shè)一棵二叉樹中有n個結(jié)點，則當(dāng)用二叉鏈表作為其結(jié)構(gòu)時，該二叉鏈表中共有個指針域，個空指針域。4.設(shè)指針變量p指向單鏈表中結(jié)點A，指針變量s指向入的結(jié)點B，則在結(jié)點A的后面插入結(jié)點B的操作序列為。 設(shè)無向圖G中有n個頂點和e條邊，則其對應(yīng)的鄰接表中有 關(guān)系 設(shè)一棵二叉樹的前序遍歷序列和中序遍歷序列均為ABC，則該二叉樹 21序從1開始順序編號，則編號為8的雙親結(jié)點的編號是 為8的左孩子結(jié)點的編號是 index(chars[],chart[{while(i<strlen(s)&&j<strlen(t))if(s[i]==t[j]){i=i+l;j=j+l;}else{i= }10.設(shè)通圖G中有n個頂點e條邊，則其最小生成樹上有設(shè)完全二叉樹的順序結(jié)構(gòu)中數(shù)據(jù)ABCDE，要求給出該二叉樹的鏈棵樹并計算樹的帶權(quán)路徑長度WPL。設(shè)一組初始記錄關(guān)鍵字序列為8，散列函數(shù)H(k)=kmod7，要求分別用線性探測和鏈地址法作為解決的方法設(shè)計哈希表 (F+1)% n, 10.n-

h23 3 樹略 (18,5,16,19,1,2)(534

h425h5 線性探測： 25 typedefstruct{ints[100];inttop;}sqstack;intlklistsymmetry(lklist*head){sqstack stack.top=-1;lklistfor(p=head;p!=0;p=p->next){stack.top++;stack.s[stack.top]=p->data;} } typedefchartypedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;voidcreatebitree(bitree*&bt){charch;if(ch=='#'){bt=0;return;}bt=(bitree*)malloc(sizeof(bitree));bt->data=ch;} intminnum=-typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidinorder(bitree*bt){if }一、選擇題(24分 設(shè)樹中的葉子結(jié)點總數(shù)為m，若用二叉鏈表作為結(jié)構(gòu)，則該樹中總共有（）個空指針域。(A)2m- (B) (C) (D)（(A)R- (B)F- (C)(R-F+M)％M(D)(F-設(shè)某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹 (A) (B) (C) (D)設(shè)某完全無向圖中有n個頂點，則該完全無向圖中有（）(A)n(n- (B)n(n- (C) (D)n2-2000個結(jié)點，則該二叉樹的最小高度為（(A) (B) (C) (D)設(shè)某有向圖中有n個頂點，則該有向圖對應(yīng)的鄰接表中有（）(A)n- (B) (C) (D)2n-速排序的結(jié)果為（(A) (B)(C) (D)二、填空題(24分 HASH typedefstruct{ints[100];inttop;}sqstack;voidpush(sqstack&stack,intx){else }3.中序遍歷二叉排序樹所得到的序列 4.快速排序的時間復(fù)雜度 ，平均時間復(fù)雜度為5.0的結(jié)點數(shù)為N01的結(jié)點數(shù)為N1，則該二叉樹中度數(shù)為2的結(jié)點數(shù)為；若采用二叉鏈表作為該二叉樹的結(jié)構(gòu)，則該二叉樹中共有個空指針域。 設(shè)某無向圖中頂點數(shù)和邊數(shù)分別為n和e所有頂點的度數(shù)之和為d則 v132v21v3148.設(shè)某無向圖G的鄰接表為v413，則從頂點V1開始的深度優(yōu)先遍歷 三、應(yīng)用題(36分2．設(shè)指針變量p指向雙向鏈表中結(jié)點A，指針變量q指向入結(jié)點B，要求給出在AB的操作序列（llink和rlink3．設(shè)一組有序的記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90)62時的比較次數(shù)并計4T中邊的集合為{(A，B)，(A，C)，(A，D)，(B，6(45，80，48，40，22，78)，四、算法設(shè)計題(16分，…，Kn，的時間復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個關(guān)鍵字均小于Ki，右半部分的每個關(guān)鍵字均大于等于Ki。 構(gòu)造一個好的HASH函數(shù)，確定解決的方 1.設(shè)有一組初始記錄關(guān)鍵字序列（K1，K2，…Kn），要求設(shè)計一個算法能夠在半部分的每個關(guān)鍵字均大于等于Ki。voidquickpass(intr[],ints,int{inti=s,j=t,x=r[s];while(i<j&&r[j]>x)j=j-1;if(i<j)}} typedefstructnode{intdata;structnode*next;}lklist;voidintersection(lklist*ha,lklist*hb,lklist*&hc){lklist*p,*q,*t; }}一、選擇題(30分<03，08>，<03，09>}，則數(shù)據(jù)結(jié)構(gòu)A是（(A)線性結(jié) (B)樹型結(jié) (C)物理結(jié) (D)圖型結(jié)下面程序的時間復(fù)雜為（for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++)(A) (B) (C) (D)列為（ (A) (B) (C) (D) 設(shè)二叉排序樹中有n個結(jié)點，則在二叉排序樹的平均平均查找長度為（(A) (B) (D)設(shè)無向圖Gne條邊，則其對應(yīng)的鄰接表中的表頭結(jié)點和表結(jié)點的個數(shù)分別為（(A) (B) (C) (D)設(shè)某強連通圖中有n個頂點，則該強連通圖中至少有（）(A)n(n- (B) (C) (D)鍵字，則用下列（）方法可以達到此目的。

(C)歸并排(B)冒泡排 (C)堆排

(D)(D) 設(shè)一棵完全二叉樹中有500個結(jié)點，則該二叉樹的深度為 設(shè)輸入序列為1、2、3，則經(jīng)過棧的作用后可以得到 設(shè)有向圖G用鄰接矩陣A[n][n]作為 之和等于頂點i的 ，第i列上所有元 和等于頂點i的 設(shè)樹中共有n個結(jié)點，則 個度數(shù)為1的結(jié)點 設(shè)有向圖G中有n個頂點e條有向邊，所有的頂點入度數(shù)之和為d，則e和d的 設(shè)查找表中有100個元素，如果用二分法查找方法查找數(shù)據(jù)元素X，則最多需要 次就可以斷定數(shù)據(jù)元素X是否在查找表中。 設(shè)有n個結(jié)點的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號，則第i個結(jié)點的雙親結(jié)點編號為 設(shè)有向圖G中有向邊的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}， x的關(guān)鍵字，請在下劃線處填上正確的語structrecord{intkey;intinthashsqsearch(structrecordhashtable[],int{int j=i=k%while(hashtable[j].key!=k&&hashtable[j].flag!=0){j=( )%m;if(i==j)return(-1);}if( )return(j);elsereturn(-1);} typedefstructnode{intkey;structnode*lchild;structnode*rchild;}bitree; {if(t==0) if(t- ;elseif(t->key>k)t=t->lchild; }三、算法設(shè)計題(22分3qABB的值到結(jié)點A中，最后刪除結(jié)點B。 8小題分析：二分查找的過程可以用一棵二叉樹來描述，該二叉樹稱為二叉判定樹。在有序表上進行二分查找時的查找長度不超過二叉判定樹的高度1+log2n。 typedefinttypedefstructnode{datatypedata;structnode*next;}lklist;voiddelredundant(lklist*&head){lklist*p,*q,*s;{if(q->data==p->data){s->next=q->next; else{s=q,q=q->next;}}} typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;bitree*q[20];intr=0,f=0,flag=0;voidpreorder(bitree*bt,char{if(bt!=0&&if(bt->data==x){flag=1;}{inti;for(i=f+1;i<=r;i++)if(q[i]->lchild->data==x||q[i]->rchild->data)break;if(flag==0)printf("notfoundx\n");}一、選擇題(30分設(shè)一維數(shù)組中有n個數(shù)組元素，則第i個數(shù)組元素的平均時間復(fù)雜度為（(A) (B) (C) (D)(A)2k- (B) (C)2k- (D)2k-設(shè)某無向圖中有ne條邊，則該無向圖中所有頂點的入度之和為（(A) (B) (C) (D)在二叉排序樹中插入一個結(jié)點的時間復(fù)雜度為（(A) (B) (C) (D)n個表頭結(jié)點和m個表結(jié)點，則該圖中有（）(A) (B)n- (C) (D)m-(A) (B) (C) (D)設(shè)用鏈表作為棧的結(jié)構(gòu)則退棧操作（(A)必須判別棧是否為 (B)必須判別棧是否為(C)判別棧元素的類 (D)對棧不作任何判下列四種排序中（）(A)快速排 (B)冒泡排 (C)排 (D)N2，則下列等式成立的是（(A) (B) (C) (D)超過（(A) (C) (D)二、填空題(42分1．設(shè)有n個無序的記錄關(guān)鍵字，則直接插入排序的時間復(fù)雜度為 2．設(shè)指針變量p指向雙向循環(huán)鏈表中的結(jié)點X，則刪除結(jié)點X需要執(zhí)行的語句序列 llinkrlink 4．深度為k的完全二叉樹中最少 5(K1，K2，…，Kn)，則用篩選法思想建堆必須從第6．設(shè) 樹中共有99個結(jié)點，則該樹中有 7．設(shè)有一個順序循環(huán)隊列中有M個單元則該循環(huán)隊列中最多能個隊列元素；當(dāng)前實際個隊列元素（設(shè)頭指針F指向當(dāng)前隊頭8ni個位置上插入一個數(shù)據(jù)元素需要移動表中i個位置上的數(shù)據(jù)元素需要移動表中個元素。9．設(shè)一組初始記錄關(guān)鍵字序列為(20，18，22，16，30，19)，則以20為中軸的一趟 點j互為鄰接點的條件是 12．12AAi0元素的個數(shù)i列上非0元素的個數(shù)（填等于，大于或小于。13．13．設(shè)前序遍歷某二叉樹的序列為ABCD，中序遍歷該二叉樹的序列為BADC，則后 hashtalbek的結(jié)點，成功時返回指向關(guān)鍵字的指針，不成功時返回標志0。typedefstructnode{intkey;structnode*next;}lklist;voidcreakhash(lklist*hashtable[]){int lklist {k=a[i]%p;s- }}三、算法設(shè)計題(28分 typedefchartypedefstructnode{datatypedata;structnode*next;}lklist;voidsplit(lklist*head,lklist*&ha,lklist*&hb,lklist*&hc){lklist*p;ha=0,hb=0,hc=0;{}} typedefstructnode{intdata;structnode*lchild,*rchild;}bitree;voidswapbitree(bitree*bt){bitree*p;if(bt==0)return;swapbitree(bt->lchild);swapbitree(bt->rchild);p=bt->lchild;bt->lchild=bt->rchild;bt->rchild=p;} #definentypedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidbstinsert(bitree*&bt,intkey){if(bt==0){bt=(bitree*)malloc(sizeof(bitree));bt->key=key;bt->lchild=bt->rchild=0;}elseif(bt->key>key)bstinsert(bt->lchild,key);elsebstinsert(bt->rchild,key);}{int}一、選擇題(30分數(shù)據(jù)的最小單位是（(A)數(shù)據(jù) (B)數(shù)據(jù)類 (C)數(shù)據(jù)元 (D)數(shù)據(jù)變設(shè)一組初始記錄關(guān)鍵字序列為(50，40，95，20，15，70，60，45)，則以增量d=4的一趟排序結(jié)束后前4條記錄關(guān)鍵字為（ (B)(C) (D)，其中含有 (B)(C) (D)設(shè)一個有序的單鏈表中有n個結(jié)點，現(xiàn)要求插入一個新結(jié)點后使得單鏈表仍然保持有序，則該操作的時間復(fù)雜度為（(A) (B) (C) (D)結(jié)點數(shù)為Nm，則N0=（ (D)1000個元素，則用二分查找查找元素X最多需要比較（）(A) (B) (C) (D)設(shè)連通圖G中的邊集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點序列為（(A) (B) (C) (D)序列中第i個輸出元素是（(An- (Bn-1- (Cn+1- (D)基準而得到一趟快速排序的結(jié)果是（ (B)(C) (D)二、填空題(30分 設(shè)有一個順序共享棧S[0：n-1]，其中第一個棧項指針top1的初值為-1，第二個棧頂指針top2的初值為n，則判斷共享棧滿的條件是 nA，如果按照行的順序?qū)⑾氯蔷仃囍械脑兀ò▽蔷€上元素）存放在n(n+1)個連續(xù)的單元中，則A[i][j]與A[0][0]之間有4.棧的插入和刪除只能在棧的棧頂進行，后進棧的元素必定先出棧，所以又把棧稱為先出隊列，所以又把隊列稱為表。5.設(shè)一棵完全二叉樹的順序結(jié)構(gòu)中數(shù)據(jù)元素為ABCDEF，則該二叉樹的前序遍歷序列 ，中序遍歷序列 ，后序遍歷序列。 設(shè)一棵完全二叉樹有128個結(jié)點，則該完全二叉樹的深度為 設(shè)有向圖G的結(jié)構(gòu)用鄰接矩陣A來表示則A中第i行中所有非零元素個數(shù)之和等于頂點i 設(shè)一組初始記錄關(guān)鍵字序列(k1，k2，……，kn)是堆，則對i=1，2，…，n/2而言 void {{ if(r[j]>r[j+1]){temp=r[j+1]; if(exchange==0)return；}} structrecord{intkey;intothers;};intbisearch(structrecordr[],intk){intlow=0,mid,high=n-1;{; }}三、應(yīng)用題(24分 DBEAC，前序遍歷序列為 四、算法設(shè)計題(16分 ki<=k2i&& typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;intjudgebitree(bitree*bt1,bitree*bt2){if(bt1==0&&bt2==0)elseif(bt1==0||bt2==0||bt1->data!=bt2->data)} {lklist*s=hc=0;while(ha!=0&&hb!=0)if(ha->data<hb->data){if(s==0)hc=s=ha;else{s->next=ha;s=ha;};ha=ha->next;}else{if(s==0)hc=s=hb;else{s->next=hb;s=hb;};hb=hb->next;}}一、選擇題(30分設(shè)一組權(quán)值集合W={2，3，4，5，6}，則由該權(quán)值集合構(gòu)造的樹中帶權(quán)路徑長度之和為（(A) (B) (C) (D)執(zhí)行一趟快速排序能夠得到的序列是（[45，34，12，41]55[12，27，45，41]55 (D)時間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog2n)的是（(A)堆排 (B)冒泡排 (C)排 (D)快速排設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（ (B)高度等于其結(jié)點(C)任一結(jié)點無左孩 (D)任一結(jié)點無右孩一趟排序結(jié)束后不一定能夠選出一個元素放在其最終位置上的是（(A)堆排 (B)冒泡排 (C)快速排 (D)排40個結(jié)點，則該三叉樹的最小高度為（(A) (B) (C) (D)順序查找不論在順序線性表中還是在鏈式線性表中的時間復(fù)雜度為（(A) (B) (C) (D)二路歸并排序的時間復(fù)雜度為（(A) (B) (C) (D)深度為k的完全二叉樹中最少有（） (B)2k- (C)2k- (D)2k-針變量s指向?qū)⒁腙犃械慕Y(jié)點X，則入隊列的操作序列為（ (D)s-設(shè)某無向圖中有ne條邊，則建立該圖鄰接表的時間復(fù)雜度為（(A) (B) (C) (D)設(shè)某樹中有199個結(jié)點，則該樹中有（）個葉子結(jié)點(A) (B) (C) (D)設(shè)二叉排序樹上有n個結(jié)點，則在二叉排序樹上查找結(jié)點的平均時間復(fù)雜度為（(A) (B) (C) (D)設(shè)用鄰接矩陣A表示有向圖G的結(jié)構(gòu)，則有向圖G中頂點i的入度為（第i行非0元素的個數(shù)之 (B)第i列非0元素的個數(shù)之(C)第i行0元素的個數(shù)之 (D)第i列0元素的個數(shù)之二、判斷題(20分三、填空題(30分 設(shè)指針變量p指向單鏈表中結(jié)點A，指針變量s指向入的新結(jié)點X，則進行插入操 （設(shè)結(jié)點的指針域為next。設(shè)有向圖G的二元組形式表示為G=（RD={2345}={r}r={<12>， 設(shè)無向圖G中有n個頂點，則該無向圖中每個頂點的度數(shù)最多 。設(shè)二叉樹中結(jié)點的兩個指針域分別為lchild和rchild，則判斷指針變量p所指向的結(jié)點 O(nlog2n)， structrecord{intkey;intothers;};intbisearch(structrecordr[],int{intlow=0,mid,high=n-1;{}} typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidinorder(bitree*bt){ } {lklist intif(head==0||head->next==0){for(s=head;s!=q->next;s=s->next)if(s->data>p->data)break; }}一、選擇題(30分設(shè)某無向圖有n個頂點，則該無向圖的鄰接表中有（）(A) (B) (C) 設(shè)無向圖Gn個頂點，則該無向圖的最小生成樹上有（）(A) (B)n- (C) (D)2n-而得到的一趟快速排序結(jié)果是（(A) (B)(C) (D)(A)先序遍 (B)中序遍 (C)后序遍 (D)層次遍點的左孩子結(jié)點的編號為（(A) (B) (C) (D)2i-s=i=0；doi=i+1s=s+i；}while(i<=n)；的時間復(fù)雜度為（(A) (B) (C) (D)設(shè)帶有頭結(jié)點的單向循環(huán)鏈表的頭指針變量為head，則其判空條件是（ (D)10，則該二叉樹上葉子結(jié)點最多有（(A) (B) (C) (D)用二分法查找關(guān)鍵字90需要比較的關(guān)鍵字個數(shù)為（(A) (B) (C) (D)設(shè)指針變量top指向當(dāng)前鏈式棧的棧頂，則刪除棧頂元素的操作序列為（ (C)top->next=top;(D)top=top-二、判斷題(20分設(shè)某堆中有n個結(jié)點，則在該堆中插入一個新結(jié)點的時間復(fù)雜度為O(log2n) 三、填空題(30分1.設(shè)指針變量p指向雙向鏈表中的結(jié)點A，指針變量s指向入的結(jié)點X，則在結(jié)點A的后面插入結(jié)點X的操作序列為=p；s->right=p->right；=s；p->right->left=s（leftright。2.n個頂點，則該完全有向圖中共有條有向條；設(shè)完全n個頂點，則該完全無向圖中共有條無向邊。3.設(shè)關(guān)鍵字序列為(Kl，K2，…，Kn)，則用篩選初始堆必須從第個元素開4.解決散列表的兩種方法 5.500的結(jié)點，212的結(jié)點，則該二叉樹中度3的結(jié)點數(shù)有個。6.h的完全二叉樹中最少有個結(jié)點，最多有 設(shè)一棵二叉樹的前序序列為ABC，則有 structrecord{intkey;datatypevoidquickpass(structrecordr[],ints,intt,int{intj=t;structrecordx=r[s];i=s;{ if(i<j)while ) };}四、算法設(shè)計題(20分 3． 4． 5．8． 9． 10． i<j&& {lklist*p,*q,*s; intmin,t;if(head==0||head->next==0)return;for(q=head;q!=0;q=q->next){for(p=q->next;p!=0;p=p->next)if(min>p->data){min=p->data;s=p;}if(s!=q){t=s->data;s->data=q->data;q->data=t;}}} voidsubstring(chars[],longstart,longcount,chart[{longif(start<1||start>length)printf("Thecopypositioniswrong");elseif(start+count-1>length)printf("Toocharacterstobecopied");} inttypedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidlevel(bitree*bt,intx){if }一、選擇題(30分 (B)串中不同字母的個(C)串中所含字符的個 (D)串中不同數(shù)字的個 n的有序單鏈表的時間復(fù)雜度為（(A) (B) (C) (D) 兩個字符串相等的充要條件是（ (B)兩個字符串中對應(yīng)位置上的字符相(C)同時具備(A)和(B)兩個條 (D)以上答案都不 (A) (B) (C) (D) 在二叉排序樹中插入一個關(guān)鍵字值的平均時間復(fù)雜度為（(A) (B) (C) (D) 設(shè)一個順序有序表A[1:14]中有14個元素，則采用二分法查找元素A[4]的過程中 (D)A[7]，A[5] 65個結(jié)點，則該完全二叉樹的深度為（(A) (B) (C) (D) 點，則該三叉鏈權(quán)中有（）個度數(shù)為0的結(jié)點。(A) (B) (C) (D) 設(shè)無向圖G中的邊的集合c)}a出發(fā)進行深度優(yōu)先遍歷可以得到的一種頂點序列為（(A) (B) (C) (D) 隊列是一種（）(A)先進先 (B)先進后 (C)只能插 (D)只能刪二、判斷題(20分 在的塊號，然后再在相應(yīng)的塊內(nèi)進行順序查找。（） 不論線性表采用順序結(jié)構(gòu)還是鏈式結(jié)構(gòu)，刪除值為X的結(jié)點的時間復(fù)雜度均為O(n)（） 被過。（） 三、填空題(30分1．設(shè)一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27，50)，則以d=4為增 2typedefstructnode{intdata;structnode*lchild;structnode bstinsert(bitree*&t,intk){if(t==0){ elseif(t->data>k)bstinsert(t->lchild,k);else }的后面插入結(jié)點X需要執(zhí)行的語句序列：s->next=p- 4．設(shè)指針變量head指向雙向鏈表中的頭結(jié)點，指針變量p指向雙向鏈表中的第一個結(jié)點，則指針變量p和指針變量head之間的關(guān)系是p= 和head=rlink5．設(shè)某棵二叉樹的中序遍歷序列為ABCD，后序遍歷序列為BADC，則其前序遍歷 6．完全二叉樹中第5層上最少 7．設(shè)有向圖中不存在有向邊<Vi,Vj>，則其對應(yīng)的鄰接矩陣A中的數(shù)組元素A[i][j]的 8．設(shè)一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27，50)，則第4趟直接 9．設(shè)連通圖G中有n個頂點e條邊，則對應(yīng)的最小生成樹上 條邊 們調(diào)整成初始堆只需把16與 四、算法設(shè)計題(20分 {} typedefstruct{intvertex[m];inttypedefstructnode1{intinfo;intadjvertex;structnode1*nextarc;}glinklistnode;typedefstructnode2{intvertexinfo;glinklistnode*firstarc;}glinkheadnode;voidadjmatrixtoadjlist(gadjmatrixg1[],glinkheadnodeg2[]){inti,j;glinklistnode*p;if(g1.edge[i][j]==1){p=(glinklistnode*)malloc(sizeof(glinklistnode));p->adjvertex=j;p->nextarc=g[i].firstarc;g[i].firstarc=p;p=(glinklistnode*)malloc(sizeof(glinklistnode));p->adjvertex=i;p->nextarc=g[j].firstarc;g[j].firstarc=p;}}一、選擇題(30分下列程序段的時間復(fù)雜度為（for(i=0；i<m；i++)for(j=0；j<t；j++)(A) (B) (C) (D)設(shè)順序線性表中有ni個元素需要移動（）(A)n- (B)n+l- (C)n-1- (D)FT1、T2T3三棵樹組成的森林，與F對應(yīng)的二叉樹為B，T1、T2T3的結(jié)點數(shù)分別為N1、N2和N3，則二叉樹B的根結(jié)點的左的結(jié)點數(shù)為（ (B)N2- (C) (D)利用直接插入排序法的思想建立一個有序線性表的時間復(fù)雜度為（(A) (B) (C) (D)設(shè)指針變量p指向雙向鏈表中結(jié)點A，指針變量s指向入的結(jié)點X，則在結(jié)點A的后面插入結(jié)點X的操作序列為（6．下列各種排序算法中平均時間復(fù)雜度為O(n2)是（ (A)快速排 (B)堆排 (C)歸并排 (D)冒泡排中的第i個輸出元素是（(An- (Bn-1- (Cn+l (D)設(shè)散列表中有m個單元，散列函數(shù)H(key)=key%p，則p最好選擇（ (B)小于等于m的最大素(C)小于等于m的最大偶 (D)小于等于m的最大合120的結(jié)點數(shù)有（）(A) (B) (C) (D)設(shè)完全無向圖中有n個頂點，則該完全無向圖中有（） (B)n(n- (C) (D)(n-設(shè)順序表的長度為n，則順序查找的平均比較次數(shù)為（(A) (B) (C) (D)(n-的元素需要經(jīng)過（）(A) (B) (C) (D)找長度為（(A) (B) (C) (D)該有向圖G的一種拓撲排序序列的是（(A) (B) (C) (D)成的二叉排序樹的深度為（(A) (B) (C) (D)二、填空題(30分1．設(shè)指針p指向單鏈表中結(jié)點A，指針s指向入的結(jié)點X，則在結(jié)點A的前面插入結(jié)點X時的操作序列為： 4)p- ；5)s-2．設(shè)某棵完全二叉樹中有100個結(jié)點，則該二叉樹中有 3mF指向隊頭元素的前一個位置，隊尾指針R指向隊尾元素的當(dāng)前位置，則該循環(huán)隊列中最多隊列元4．對一組初始關(guān)鍵字序列（40，50，95，20，15，70，60，45，10）進行冒泡排 需要進行趟排序才可以完成。5．在堆排序和快速排序中，如果從平均情況下排序的速度最快的角度來考慮應(yīng)最好選擇排序，如果從節(jié)省空間的角度來考慮則最好選擇排序。6．設(shè)一組初始記錄關(guān)鍵字序列為(20，12，42，31，18，14，28)，則根據(jù)這些記錄 7．設(shè)一棵二叉樹的中序遍歷序列為BDCA，后序遍歷序列為DBAC，則這棵二叉 、、、、、，根據(jù)這些頻率作為權(quán)值構(gòu)造樹，則這棵樹的高度 10．設(shè)無向圖G（如右圖所示則其最小生成樹上所有邊的 三、判斷題(20分1．有向圖的鄰接表和逆鄰接表中表結(jié)點的個數(shù)不一定相等。 2．對鏈表進行插入和刪除操作時不必移動鏈表中結(jié)點。 3．子串“ABC”在主串“AABCABCD”2。()4．若一個葉子結(jié)點是某二叉樹的中序遍歷序列的最后一個結(jié)點，則它必是該二叉樹 5．排序算法的時間復(fù)雜度為O(n2)。 6．用鄰接矩陣作為圖的結(jié)構(gòu)時，則其所占用的空間與圖中頂點數(shù)無關(guān)而與 7．中序遍歷一棵二叉排序樹可以得到一個有序的序列。 8．入棧操作和入隊列操作在鏈式結(jié)構(gòu)上實現(xiàn)時不需要考慮棧溢出的情況。 五、算法設(shè)計題(20分 2． 3．7． 8．voidsum(bitree*bt,int{}voidquickpass(intr[],ints,int{{while(i<j&&r[j]%2==0)j=j- if(i<j)while(i<j&&r[i]%2==1) }}{for(q=head,p=head->next;p!=0;q=p,p=p->next)if(q->data>p->data)return(0);}一、選擇題(24分下列程序段的時間復(fù)雜度為（i=0，s=0；while(s<n)(A) (B) (C) (D)設(shè)某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則選用下列（）方式 (B)單向循環(huán)鏈(C)雙向鏈 (D)雙向循環(huán)鏈qApA的后繼結(jié)點Bs指向入的結(jié)點X，則在結(jié)點A和結(jié)點B插入結(jié)點X的操作序列為（ (B)q->next=s；s- (A)5，3，4，6，1，2(B)(C)3，1，2，5，4，6(D)設(shè)有一個10階的下三角矩陣A（包括對角線，按照從上到下、從左到右的順序到的地址之差為（(A) (B) (C) (D)m的結(jié)點，則該樹中共有（）

mm(i

m m

m m

mm1(i二叉排序樹中左上所有結(jié)點的值均（）根結(jié)點的值(A) (B) (C) (D)夫曼樹，則這棵樹的帶權(quán)路徑長度為（(A) (B) (C) (D)表中需要做（）(A) (B) (C) (D)n(n-共有（）個結(jié)點。(A) (B) (C)2n- (D)(A) (B) (C) (D) 設(shè)需要對5個不同的記錄關(guān)鍵字進行排序，則至少需要比較 h 設(shè)在長度為20的有序表中進行二分查找，則比較一次查找成功的結(jié)點數(shù)有 設(shè)一棵m叉樹脂的結(jié)點數(shù)為n，用多重鏈表表示其結(jié)構(gòu)，則該樹中有 p指向單鏈表中結(jié)點A，則刪除結(jié)點A 數(shù)據(jù)結(jié)構(gòu)從邏輯上劃分為三種基本類型 。8.設(shè)無向圖Gne條邊，則用鄰接矩陣作為圖的結(jié)構(gòu)進行深度優(yōu)先或廣度優(yōu)先遍歷時的時間復(fù)雜度為；用鄰接表作為圖的結(jié)構(gòu)進行深度優(yōu)先或廣度優(yōu)先遍歷的時間復(fù)雜度為。9.設(shè)散列表的長度為8，散列函數(shù)H(k)=k%7，用線性探測法解決，則根據(jù)一組初始關(guān)鍵字序列(8，15，16，22，30，32)構(gòu)造出的散列表的平均查找長度是。10.設(shè)一組初始關(guān)鍵字序列為(38，65，97，76，13，27，10)，則第3趟冒泡排序結(jié)束 11.設(shè)一組初始關(guān)鍵字序列為(38，65，97，76，13，27，10)，則第3趟簡單選擇排序 設(shè)有向圖G中的有向邊的集合 typedefstructnode{intdata;structnode voidcreatebitree(bitree*&bt){ } typedefstructnode{intdata;structnode*next;}lklist;voidlklistcreate( *&head){for{if(i==1)head=q=p;else{q->next=p; }}三、算法設(shè)計題(22分2．設(shè)計在二叉排序樹上查找結(jié)點X3(k1，k2，…，kn-1)是堆，設(shè)計算法將關(guān)鍵字序列(k1，k2，…，kn- O(n2)， {lklist*s=hc=0;while(ha!=0&&hb!=0)if(ha->data<hb->data){if(s==0)hc=s=ha;else{s->next=ha;s=ha;};ha=ha->next;}else{if(s==0)hc=s=hb;else{s->next=hb;s=hb;};hb=hb->next;}} 設(shè)計在二叉排序樹上查找結(jié)點Xbitree*bstsearch1(bitree*t,int{bitreewhile(p!=0)if(p->key==key)return(p);elseif(p->key>key)p=p->lchild;elsep=p->rchild;} voidadjustheap(intr[],int{while(i>=1)if(temp>=r[i-1])break;else{r[j-1]=r[i-1];j=i;i=i/2;}} 單選題（每題2分，共20分 ）方面的內(nèi)容健壯性和可讀 C.p->next=HL; D.HL=p;p- 23 B.32C.31 D.12 有向 采用開放定址法處理散列表的時，其平均查找長度（。A．低于法處理B. 高于法處理C．與法處理相同 ）參數(shù) D． 有相同的（行 快速排序在情況下的時間復(fù)雜度為（ 10.10.從二叉搜索樹中查找一個元素時，其時間復(fù)雜度大致為 )A. B. C. D. 運算題（每題6分，共24分 當(dāng)結(jié)點之間存在 隊列的插入操作是在隊列的 進行，刪除操作是在隊列的 對于一個長度為n的單鏈的線性表在表頭插入元素的時間復(fù)雜度 W4i7j03W的數(shù)據(jù)元素共占用＿＿個字節(jié)。W64列的元素共占用＿＿個字節(jié)。若按行地址為＿＿。 廣義表A=(a,(a,b),((a,b),c)),則它的深度 ，它的長度。 二叉樹是指度為2的 對一棵二叉搜索樹進行中序遍歷時，得到的結(jié)點序列是一個 對于一棵具有n個結(jié)點的二叉樹，用二叉鏈表時，其指針總數(shù)為個，其中 個用于指向孩子，10.若對一棵完全二叉樹從0開始進行結(jié)點的編號，并按此編號把它順序存元素的左孩子元素為,右孩子元素 ，雙親元素。 兩種12.當(dāng)待排序的記錄數(shù)較大，排序碼較隨機且對穩(wěn)定性不作要求時，宜采用排序；當(dāng)待排序的記錄數(shù)較大，空間允許且要求排序 100 000 00 0 0 0 46,25,78,621280},試畫出從空樹起， ; 圖6 intPrime(int{intwhile(++i<=x)if(i>x)return1;elsereturn} voidAJ(adjlistGL,inti,int{QueueQ;cout<<i<<'';while(!QueueEmpty(Q)){intk=QDelete(Q);{{cout<<j<<'';}}}} {intlow=0;while{int if(K==A[mid].key) returnmid; elseif(K<[mid].key)

}

} ElemTypeDeleFront(LNode*&七 一 單選題（每題2分，共20分 2.A 八 二 填空題（每空1分，共26分 655151326551513245515637 快 歸九 三 運算題（每題6分，共24分 (3分圖 排序為： 十 四 (1)n是否是素數(shù)（或質(zhì)數(shù) 功能為：從初始點vi出發(fā)廣度優(yōu)先搜索由鄰接表GL所表示的圖。 算法填空（8分） 十二 六 編寫算法（8分{if} deletep;return}七、一、單選題（220分1.棧和隊列的共同特點是( 2.用方式的隊列，在進行插入運算時(僅修改頭指 B.頭、尾指針都要修C.僅修改尾指 3.以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)？()A.隊列B.棧C.線性表D.4.A[m][n]A[0][0]10 樹最適合用來表示 )有序數(shù)據(jù)元 B.無序數(shù)據(jù)元C.元間具有分支層次關(guān)系的數(shù) D.元間無聯(lián)系的數(shù) 二叉樹的第k層的結(jié)點數(shù)最多為 D.2k- A. B.C. D. A. B. C. D.9.對于線性表（7，34，55，25，64，46，20，10）進行散列時，H（K）=K%91的元素有（） 10.設(shè)有6個結(jié)點的無向圖，該圖至少應(yīng)有 )條邊才能確保是一 1.通常從四個方面評價算法的質(zhì)量： 一個算法的時間復(fù)雜度為(n3+n2log2n+14n)/n2，其數(shù)量級表示為。A（C，D（E，F(xiàn)，G，H（I，J，所含的結(jié)點數(shù)為 個，樹的深度為 ，樹的度為。 后綴算式923+-102/-的值 對應(yīng)的后綴算式 5.若用鏈表一棵二叉樹時，每個結(jié)點除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個指針。在這種結(jié)構(gòu)中，n個結(jié)點的二叉樹共有個指針域，其中有個指針域是存放了地址，有 個指6.ne條邊的有向圖和無向圖，在其對應(yīng)的鄰接表中，所含邊結(jié)點分別有個和個。 的圖8.在一個具有n個頂點的無向完全圖中，包含有 有n個頂點的有向完全圖中，包含有 9.假定一個線性表為(12,23,74,55,63,40)Key%4條件進行劃分，使得同一余數(shù)的元素成為一個子表，則得到的四個子表分別為 10.向一棵B_樹插入元素的過程中，若最終引起樹根結(jié)點的，則新樹 11.在堆排序的過程中，，整個堆排序過程的時間復(fù)雜度 12.在快速排序、堆排序、歸并排序中 排序是穩(wěn)定的 運算題（每題6分，共24分1.在如下數(shù)組A中了一個線性表，表頭指針為A[0].next，試寫3572041 3572041

4,2,583 LinkListmynote(LinkList{//L是不結(jié)點的單鏈表的頭指q=L；L=L－>next；p=L；S1：while(p－>next)p=p－>next； } }, voidABC(BTNode*{ ABC(BT->right);}} {ifelse{ returnFind( } intCountX(LNode*HL,ElemType 一 二 強壯 2. 34X*+2Y*3/ （ 10.11. 12. 三 11 11

鄰接矩陣：0

4422424442242452458245 235235 十 四 十一 五 算法填空（每空2分，共8分 十二 六 {if(P->data==x)i++;,return七、一、單選題（28分平均查找長度（x與元素的平均比較次數(shù)，假定查找每個元素的概率都相等）為()。 2、2、在一個單鏈表中,qp所指結(jié)點的前驅(qū)結(jié)點,qp之間插入一個s所指的結(jié)點,則執(zhí)行()。 q→link=s; s→link3、3、棧的插入和刪除操作在（） 棧 棧 任意位 指定位4、4、由權(quán)值分別為11，8，6，2，5的葉子結(jié)點生成一棵樹，它的帶權(quán)路徑長度為（） 八 二 填空題（每空1分，共32分1、1、數(shù)據(jù)的邏輯結(jié)構(gòu)被分為 2、2、一種抽象數(shù)據(jù)類型包 兩個部分 4376201 7、7、一棵高度為5的二叉樹中最少含有 個結(jié)點，最多含有一棵高度為5的理想平衡樹中，最少含有 。9、9和1010假定一棵樹的廣義表表示為A（B（C，D（E，F(xiàn)，G， 樹的度 ,結(jié)點H的雙親結(jié)點 ,孩子結(jié)點。11、11、在堆排序的過程中，對任一分支結(jié)點進行篩運算的時間復(fù)雜度為,整個堆排序過程的時間復(fù)雜度為 12、12、mB_樹插入元素的過程中，每向一個結(jié)點插入一引項數(shù)等于個，則必須把它為個結(jié)點。九 三 運算題（每小題6分，共24分1、1、已知一組記錄的排序碼為（46，79，56，38，40，80,95，24，寫（12，23，45，57，20，03，78，31，15，36HT[0..12]H（key）key%13并用線性探查法解3、3、已知一棵二叉樹的前序遍歷的結(jié)果序列是ABECKFGHIJ，中序遍歷的結(jié)果是EBCDAFHIGJ，試寫出這棵二叉樹的后序遍歷結(jié)果。V={（0，1（0，4（1，2（1，7（2，8（3，4（3，8（5，6（5，8（5，9（6，7（7，8（8，9）}圖十 四 閱讀算法，回答問題（每小題8分，共16分 #include<iostream.h>#include<stdlib.h>consstintstackmaxsize=30;typedefintelemtype;structstackinttop;#include main({stacka;intx;cinwhile(x!=-1)push(a,x);cin>>x;}while(!stackempty(a))cout}.Temte<calss type>void BinTree<Type>unknown(BinTreeNode<Type>*t){de<Type> if(p!=NULL){temp=p→leftchild;p→rightchild=temp;}}十一、五 算法填空，在畫有橫線的地方填寫合適的內(nèi)容（10分對順序的有序表進行二分查找的遞歸算法intBinsch(ElemTypeA[],intlow,inthigh,KeyTypeK{if(low<={intmid=if(K==A[mid].key)returnmid;elseif(K<A[mid].key)return2}

return 十二、六 編寫算法（10分元素的次序為a1，……an-1，an，則逆序后變?yōu)?an，an-1，……a1。 contrary(Lnode*&HL)1234CDAB3：（38，56，25，60，42，744HL→nextNULL；HL=HL→next；5：前一個位置；n-1；6：S.stack[S.top]; 7：5 1010、3、3、B、In12：m、m-1140]40] 2 查找成功的平均查找長度：ASLSUCC=14/10=1.44圖 五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容（10分）-{LnodeWhile{}}第一部分選擇題(30分算法指的是（ D．解決問題的有限運算序線性表采用鏈式時，結(jié)點的地址（將長度為n的單鏈表在長度為m的單鏈表之后的算法的時間復(fù)雜度（ B．節(jié)省空間，降低上溢發(fā)生的機率設(shè)數(shù)組data[m]作為循環(huán)隊列SQ的空間，front為隊頭指針，rear為隊尾指針，則執(zhí)行出隊操作后其頭指針front值為（） 7.若目標串的長度為n，模式串的長度為[n/3]，則執(zhí)行模式匹配算法時，在最 A．O（3 ） 0233502335

80080

800800

0 B.050040 3C. 3

00

0

005 4 4 0 0的結(jié)點個數(shù)為 在含n個頂點和e條邊的無向圖的鄰接矩陣中,零元素的個數(shù)為 ne條弧的有向圖用鄰接表表示,相關(guān)的所有弧的時間復(fù)雜度是 則所采用的排序方法是 C．三叉排序樹D．線性鏈表 第二部分非選擇題（70分20分）不寫解答過程，將正確的答案寫在每小題的空格內(nèi)。錯填或不填 的指針head可用p表示為head= 棧頂?shù)奈恢檬请S 操作而變化的 假設(shè)一個9階的上三角矩陣A按列優(yōu)先順序壓縮在一維數(shù)組B中，其中B[0]矩陣中第1個元素a1,1,則B[31]中存放的元素是 個葉子結(jié)點 在單鏈表上難以實現(xiàn)的排序方法 在有序表（12，24，36，48，60，72，84）中二分查找關(guān)鍵字72時所需進 文件P=（）,(x,)）x,),x)） 110頂點集為{abcde （2）ae 35，20，3348進行查找時，所需進行的比較次數(shù)各四、算法閱讀題（本大題共4小題，每小題5分，共20分） 當(dāng) 11

當(dāng)

intcomstr(LinkStrings1,LinkString } }①②③④⑤LinkListmynote(LinkList{//L是不結(jié)點的單鏈表的頭指q=L；L=L－>next；p=L；S1：while(p－>next)p=p－>next； } },，typedefintfront[2],rear[2]；下算法填空，實現(xiàn)第i個隊列的入隊操作。intEnQueue(Queue2*Q,inti,DateTypeif(i<0||i>1)return0； Q－>rear[i]=[③ }①②③typedefstructnode{DateTypedata；Structnode*next；typedefListNode*LinkList；LinkListLeafhead=NULL；VoidInorder(BinTreeT){If((!T－>lchild)&&(!TListNode))；s－>data=T－>data；s}}}intarrange(inta[],int1,inth,int{//1hinti,j,t；i=1；while(i<j&&a[j]>=x)j--；while(i<j&&a[j]>=x)i++； } returni； returni－1；}寫一個調(diào)用上述函數(shù)實現(xiàn)下列功能的算法：對一整型數(shù)組b[n]中的元素一 一 單項選擇題（本大題共15小題，每小題2分，共30分 14．Ｃ16．（或結(jié)構(gòu) 18．進棧和退 圖 圖29（１）

A