版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
試卷一一、選擇題(本題共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];}}試卷二一、選擇題(本題共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分,每題10分)1.一棵二叉樹如右面的圖所示,要求:(1)寫出對(duì)此二叉樹進(jìn)行中序遍歷時(shí)得到的結(jié)點(diǎn)序列。(2)畫出由此二叉樹轉(zhuǎn)換得到的森林。2.已知圖G的鄰接表如下,寫出從頂點(diǎn)O出發(fā)的深度優(yōu)先和廣度優(yōu)先遍歷的頂點(diǎn)序列。0021310022030130203.對(duì)于下面所示的連通圖,寫出由Prim算法生成的最小生成樹。4.下圖所示為AOE網(wǎng),求其關(guān)鍵路徑和關(guān)鍵活動(dòng)。四、算法填空題(本題共10分)下列兩個(gè)算法分別為二分查找算法和冒泡排序算法,閱讀下面程序代碼,填充空白位置,使算法完整。#Definen10typedefintKeyType;typedefstruct{KeyTypekey;}NodeType;typedefNodeTypeSeqList[n+1];1.intBinSearch(SeqListR,KeyTypek){intlow=1,high=n,mid;while(low<=high){mid=(low+high)/2;if(R[mid].key==k)returnmid;if(R[mid].key>k)______1_____;else________2_______;}return0;}2.voidBubbleSort(SeqListR){inti,jBooleanexchange;For(i=1;i<n;i++){exchange=false;for(j=1;j<=n-I;j++)if(R[j+1].key<R[j].key){_______3_____;______4______;R[j]=R[0];________5__________}if(!exchange)return;}}參考答案一、選擇題(本題共20分,每題2分)12345678910BCCCDAbBCB二、填空題(本題共20分,每空1分)1)線性結(jié)構(gòu),非線性結(jié)構(gòu)2)2i-13)n(n-1)/24)數(shù)據(jù)域,指針域5)1120,10686)2,57)58)棧頂,棧頂9)210)拓?fù)渑判?1)有序,順序存儲(chǔ)12)開放定址法,拉鏈法13)單循環(huán)鏈表三、應(yīng)用題(本題共50分)1)DEFBAC--------8分―――――――8分2)深度優(yōu)先遍歷:0231―――――6分廣度優(yōu)先遍歷:0213――――6分3)--------12分4)頂點(diǎn)vevl活動(dòng)ell-eV100a1011V234a2000V322a3341V466a4341V567a5220V688a6253a7660a8671---------6分關(guān)鍵路徑是:V1-V3-V4-V6---------2分關(guān)鍵活動(dòng)是:a2,a5,a7---------2分四、算法填空題(本題共10分,每空2分)1)high=mid-1;---------2分2)low=mid+1;---------2分3)R[0]=R[j+1];---------2分4)R[j+1]=R[j];---------2分5)exchange=true;---------2分試卷三一、單項(xiàng)選擇題(在下列每小題四個(gè)備選答案中選出一個(gè)正確答案,并將其字母標(biāo)號(hào)填入題干的括號(hào)內(nèi)。每小題2分,共30分)1.?dāng)?shù)據(jù)結(jié)構(gòu)可以形式化地定義為(S,△),其中S指某種邏輯結(jié)構(gòu),△是指()A.S上的算法 B.S的存儲(chǔ)結(jié)構(gòu)C.在S上的一個(gè)基本運(yùn)算集 D.在S上的所有數(shù)據(jù)元素2.下列說法正確的是()A.線性表的邏輯順序與存儲(chǔ)順序總是一致的B.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中,要求內(nèi)存中可用的存儲(chǔ)單元可以是連續(xù)的,也可以不連續(xù)C.線性表的線性存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D.每種數(shù)據(jù)結(jié)構(gòu)都具有插入、刪除和查找三種基本運(yùn)算3.稀疏矩陣一般采用()方法壓縮存儲(chǔ)。A.三維數(shù)組 B.單鏈表C.三元組表 D.散列表4.在一個(gè)單鏈表中,若p↑結(jié)點(diǎn)不是最后結(jié)點(diǎn),在p↑之后插入s↑結(jié)點(diǎn),則實(shí)行()。A.s↑.next:=p;p↑.next=s;B.s↑.next:=p↑.next;p↑.next:=s;C.s↑.next:=p↑.next;p:=s;D.p↑.next:=s;s↑.next=p;5.某個(gè)向量第一元素的存儲(chǔ)地址為100,每個(gè)元素的長度為2,則第五個(gè)元素的地址是()。A.110B.108C.100D.1206.下面的二叉樹中,()不是完全二叉樹。7.一組記錄的排序碼為(47、78、61、33、39、80),則利用堆排序的方法建立的初始堆為()。A.78、47、61、33、39、80B.80、78、61、33、39、47C.80、78、61、47、39、33D.80、61、78、39、47、338.假設(shè)left和right為雙向鏈表中指向直接前趨結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)的指針域,現(xiàn)要把一個(gè)指針s所指的新結(jié)點(diǎn)作為非空雙鏈表中q所指地點(diǎn)(中間結(jié)點(diǎn))的直接后繼結(jié)點(diǎn)插入到該雙向鏈表中,則下列算法段能正確完成上述要求的是()A.q->right=s;s->left=q;q->right->left=s;s->right=q->right;B.s->left=q;q->right=s;q->right->left=s;s->right=q->right;C.s->left=q;s->right=q->right;q->right->left=s;q->right=s;D.以上都不對(duì)9.由下列三棵樹組成轉(zhuǎn)的森林換成一棵二叉樹為()10.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];上列程序的時(shí)間復(fù)雜度為()A.O(m+n×t) B.O(m+n+t)C.O(m×n×t) D.O(m×t+n)11.設(shè)循環(huán)隊(duì)列的元素存放在一維數(shù)組Q[0‥30]中,隊(duì)列非空時(shí),front指示隊(duì)頭元素的前一個(gè)位置,rear指示隊(duì)尾元素。如果隊(duì)列中元素的個(gè)數(shù)為11,front的值為25,則rear應(yīng)指向的元素是()A.Q[4] B.Q[5] C.Q[14] D.Q[15]12.定義二維數(shù)組A[1‥8,0‥10],起始地址為LOC,每個(gè)元素占2L個(gè)存儲(chǔ)單元,在以行序?yàn)橹餍虻拇鎯?chǔ)方式下,某數(shù)據(jù)元素的地址為LOC+50L,則在以列序?yàn)橹餍虻拇鎯?chǔ)方式下,該元素的存儲(chǔ)地址為()A.LOC+28L B.LOC+36L C.LOC+50L D.LOC+52L13.采用排序算法對(duì)n個(gè)元素進(jìn)行排序,其排序趟數(shù)肯定為n-1趟的排序方法是()A.插入和快速 B.冒泡和快速 C.選擇和插入 D.選擇和冒泡14.設(shè)h是指向非空帶表頭結(jié)點(diǎn)的循環(huán)鏈表的頭指針,p是輔助指針。執(zhí)行程序段p=h;while(p->next->next!=h)p=p->next;p->next=h;后(其中,p->next為p指向結(jié)點(diǎn)的指針域),則()A.p->next指針指向鏈尾結(jié)點(diǎn) B.h指向鏈尾結(jié)點(diǎn)C.刪除鏈尾前面的結(jié)點(diǎn) D.刪除鏈尾結(jié)點(diǎn)15.某二叉樹的先根遍歷序列和后根遍歷序列正好相反,則該二叉樹具有的特征是()A.高度等于其結(jié)點(diǎn)數(shù) B.任一結(jié)點(diǎn)無左孩子C.任一結(jié)點(diǎn)無右孩子 D.空或只有一個(gè)結(jié)點(diǎn)二、填空題(本大題共13小題,每小題2分,共26分)請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無分。16.數(shù)據(jù)的邏輯結(jié)構(gòu)通常包括集合、線性結(jié)構(gòu)、____________和圖狀結(jié)構(gòu)。17.給定n個(gè)值構(gòu)造哈夫曼樹。根據(jù)哈夫曼算法,初始森林中共有n棵二叉樹,經(jīng)過次合并后才能使森林中的二叉樹的數(shù)目由n棵減少到只剩下一棵最終的哈夫曼樹。18.樹型結(jié)構(gòu)結(jié)點(diǎn)間通過“父子”關(guān)系相互關(guān)聯(lián),這種相互關(guān)聯(lián)構(gòu)成了數(shù)據(jù)間的關(guān)系。19.在一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找值為m的某結(jié)點(diǎn),若查找成功,則需平均比較的結(jié)點(diǎn)數(shù)為____________。20.數(shù)據(jù)表示和________________是程序設(shè)計(jì)者所要考慮的兩項(xiàng)基本任務(wù)。21.在循環(huán)隊(duì)列中,存儲(chǔ)空間為0~n-1。設(shè)隊(duì)頭指針front指向隊(duì)頭元素前一個(gè)空閑元素,隊(duì)尾指針指向隊(duì)尾元素,那么其隊(duì)空標(biāo)志為rear=front,隊(duì)滿標(biāo)志為_________。22.深度為k的二叉樹至多有_________個(gè)結(jié)點(diǎn),最少有_________個(gè)結(jié)點(diǎn)。23.在堆排序和快速排序中,若原始記錄已基本有序,則較適合選用。24.在一棵二叉排序樹上按____________遍歷得到的結(jié)點(diǎn)序列是一個(gè)有序序列。25.實(shí)現(xiàn)二分查找的存儲(chǔ)結(jié)構(gòu)僅限于順序存儲(chǔ)結(jié)構(gòu),且其中元素排列必須是____________的。26.三個(gè)結(jié)點(diǎn)可構(gòu)成________種不同形態(tài)的二叉樹。27.設(shè)需將一組數(shù)據(jù)按升序排序。在無序區(qū)中依次比較相鄰兩個(gè)元素ai和ai+1的值,若ai的值大于ai+1的值,則交換ai和ai+1。如此反復(fù),直到某一趟中沒有記錄需要交換為止,該排序方法被稱為_________。28.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹,當(dāng)進(jìn)行鏈接存儲(chǔ)時(shí),其二叉鏈表中的指針域的總數(shù)為2n個(gè),其中________個(gè)用于鏈接孩子結(jié)點(diǎn)。三、應(yīng)用題(本大題共5小題,每小題6分,共30分)29.已知一棵二叉樹的前序序列是ABCDEFG,中序序列是CBDAEGF。請(qǐng)構(gòu)造出該二叉樹,并給出該二叉樹的后序序列。30.有一字符串序列為5*-x-y/x+2,利用棧的運(yùn)算將其輸出結(jié)果變?yōu)?x-*yx+/-2,試寫出該操作的入棧和出棧過程(采用push(a)表示a入棧,pop(a)表示a出棧)。31.已知某二叉樹的順序存儲(chǔ)結(jié)構(gòu)如圖所示,試畫出該二叉樹,并畫出其二叉鏈表表示。ABCDEFG32.已知一組鍵值序列為(38,64,73,52,40,37,56,43),試采用快速排序法對(duì)該組序列作升序排序,并給出每一趟的排序結(jié)果。33.請(qǐng)按照數(shù)列{28,45,33,12,37,20,18,55}的先后插入次序,生成一棵二叉排序樹。四、算法設(shè)計(jì)題(本大題共3小題,共14分)34.試編寫一算法,以完成在帶頭結(jié)點(diǎn)單鏈表L中第i個(gè)位置前插入元素X的操作。(4分)35.某帶頭結(jié)點(diǎn)的單鏈表的結(jié)點(diǎn)結(jié)構(gòu)說明如下:(6分)typedefstructnode1{intdata;structnode1*next}node;試設(shè)計(jì)一個(gè)算法intcopy(node*head1,node*head2),將以head1為頭指針的單鏈表復(fù)制到一個(gè)不帶頭結(jié)點(diǎn)且以head2為頭指針的單鏈表中。36.若二叉樹存儲(chǔ)結(jié)構(gòu)采用二叉鏈表表示,試編寫一算法,計(jì)算一棵二叉樹的所有結(jié)點(diǎn)數(shù)。(4分)參考答案一、選擇題(本題共30分,每題2分)1、C2、B3、C4、B5、B6、C7、B8、C9、A10、C11、B12、D13、C14、D15、A二、填空題(本題共26分,每小題2分)16、樹狀結(jié)構(gòu)17、n-118、邏輯19、n/220、數(shù)據(jù)處理21、front==(rear+1)%n22、2k-1,k23、堆排序24、中序25、有序26、527、冒泡排序28、n-1三、應(yīng)用題(本題共30分,每小題6分)29、ABABCDGFEFE30、push(5);pop(5);push(*);push(-);push(x);pop(x);pop(-);pop(*);push(-);push(y);pop(y);push(/);push(x);pop(x);push(+);pop(+);pop(/);pop(-);push(2);pop(2);ACACDEFG第1趟:[37]38[735240645643]第2趟:3738[4352406456]73第3趟:3738[40]43[526456]73第4趟:3738404352[6456]73第5趟:3738404352[56]6473第6趟:373840435256647331、BACBACDEFGAB∧NULL∧C∧ROOT∧DE∧F∧∧G∧33、282812452018335537四、算法設(shè)計(jì)題(本題共14分)34、(4分)typedefstructnode*pointer;structnode{datatypedata;pointernext;};typedefpointerlklist;voidinsert_lklist(lklisthead,datatypex,inti){pointer*p,*s;p=head;j=0;while((p->next!=NULL)&&(j<i-1)){p=p->next;j++;}if(j!=i-1){printf("不存在第i個(gè)位置");break();}else{s=malloc(size);s->data=x;s->next=p->next;p->next=s;}}35、(6分)intcopy(node*head1,node*head2){Node*p,*s;P=head1->next;If(p!=NULL){*r=malloc(size);r->data=p->data;head2=r;p=p->next;}
else{head2=NULL;Return(0);}While(p!=NULL){*s=malloc(size);s->data=p->data;r->next=s;r=s;p=p->next;}r->next=NULL;return(1);}36、(4分)typedefcharDataType;
typedefstructnode
{
DataTypedata;
structnode*lchild,*rchild;
}BinTNode;
typedefBinTNode*BinTree;
intnodes(BinTreeT)
{
intnum1,num2;
if(T==NULL)return(0);
elseif(T->lchild==NULL&&T->rchild==NULL)return(1);
else
{
num1=nodes(T->lchild);
num2=nodes(T->rchild);
return(num1+num2+1);
}
}試卷A一、選擇題(本題共20分,每小題1分)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.線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí),要求內(nèi)存中可用存儲(chǔ)單元的地址()。A.必須是連續(xù)的B.部分地址必須是連續(xù)的C.一定是不連續(xù)的D.連續(xù)不連續(xù)都可以3.不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是()。A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL4.在一個(gè)單鏈表中,已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn),若在q和p之間插入s結(jié)點(diǎn),則執(zhí)行()。A.s-next=p-next;p-next=s;B.p->next=s->next;s-next=p;C.q->next=s;s->next=p;D.p-next=s;s->next=q;5.從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x結(jié)點(diǎn)時(shí),在查找成功的情況下,需平均比較()個(gè)結(jié)點(diǎn)。A.nB.n/2C.(n-1)/2D.(n+1)/26.一個(gè)棧的入棧序列是a,b,c,d,e,則棧的不可能的輸出序列是()。A.edcbaB.decbaC.dceabD.abcde7.判定一個(gè)循環(huán)隊(duì)列QU(最多元素為m0)為滿隊(duì)列的條件是()。A.QU->front==QU->rearB.QU->front!=QU->rearC.QU->front==(QU->rear+1)%m0D.QU->front!=(QU->rear+1)%m08.棧和隊(duì)列的共同點(diǎn)是()。A.都是先進(jìn)后出B.都是先進(jìn)先出C.只允許在端點(diǎn)處插入和刪除元素D.沒有共同點(diǎn)9.?dāng)?shù)組A中,每個(gè)元素A的長度為3個(gè)字節(jié),行下標(biāo)i從1到8,列下標(biāo)j從1到10,從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi),該數(shù)組按行存放時(shí),元素A[8][5]的起始地址為()。A.SA+141B.SA+144C.SA+222D.SA+22510.廣義表((a,b),c,d)的表尾是()。A.aB.bC.(a,b)D.(c,d)11.設(shè)矩陣A是一個(gè)對(duì)稱矩陣,為了節(jié)省存儲(chǔ),將其下三角部分(如下圖所示)按行序存放在一維數(shù)組B[1,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+j13.已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷序列是()。A.acbedB.decabC.deabcD.cedba12.如下圖所示的4棵二叉樹中,()不是完全二叉樹。14.按照二叉樹的定義,具有3個(gè)結(jié)點(diǎn)的二叉樹有()種。A.3B.4C.5D.615.設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn),則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為()。A.2hB.2h-1C.2h+1D.h+116.在一個(gè)有向圖中,所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的()倍。A.1/2B.1C.2D.417.在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中,要連通全部頂點(diǎn)至少需要()條邊。A.nB.n+1C.n-1D.n/218.已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下圖所示,根據(jù)有向圖的深度優(yōu)先遍歷算法,從頂點(diǎn)v1出發(fā),所得到的頂點(diǎn)序列是()。A.v1,v2,v3,v5,v4B.v1,v2,v3,v4,v5C.v1,v3,v4,v5,v2D.v1,v4,v3,v5,v219.采用順序查找方法查找長度為n的線性表時(shí),每個(gè)元素的平均查找長度為()。A.nB.n/2C.(n+1)/2D.(n-1)/220.快速排序方法在()情況下最不利于發(fā)揮其長處。A.要排序的數(shù)據(jù)量太大B.要排序的數(shù)據(jù)中含有多個(gè)相同值C.要排序的數(shù)據(jù)已基本有序D.要排序的數(shù)據(jù)個(gè)數(shù)為奇數(shù)二、填空題(本題共20分,每空1分)1.根據(jù)數(shù)據(jù)元素之間的不同特征,通常有四類基本結(jié)構(gòu):_____、______、______和______。2.下面程序段的時(shí)間復(fù)雜度是:______。for(i=0;i<n;i++)for(j=0;j<m;j++)A[i][j]=0;3.向一個(gè)長度為n的線性表中的第i個(gè)元素(1≤i≤n)之前插入一個(gè)元素時(shí),需向后移動(dòng)______個(gè)元素。4.在一個(gè)單鏈表中的p所指結(jié)點(diǎn)之前插入一個(gè)s所指結(jié)點(diǎn)時(shí),可執(zhí)行如下操作:(1)s->next=______;(2)p-next=s;(3)t=p->data;(4)p->data=______;(5)s->data=______;5.深度為k的完全二叉樹至少有個(gè)結(jié)點(diǎn),至多有個(gè)結(jié)點(diǎn),若按自上而下,從左到右次序給結(jié)點(diǎn)編號(hào)(從1開始),則編號(hào)最小的葉子結(jié)點(diǎn)的編號(hào)是。6.一個(gè)廣義表為(a,(a,b),d,e,((i,j),k)),則該廣義表的深度為________。7.有一棵樹如下圖所示,回答下面的問題:結(jié)點(diǎn)k3的度是;這棵樹的度為;這棵樹的深度是。8.在對(duì)一組記錄(54,38,96,23,15,72,60,45,83)進(jìn)行直接插入排序時(shí),當(dāng)把第七個(gè)記錄60插入到有序表時(shí),為尋找插入位置需比較______次。9.隊(duì)列的插入操作在_______進(jìn)行,刪除操作在_______進(jìn)行。10.判定一個(gè)有向圖中是否存在回路,即是否含有環(huán),可以使用_________方法。三、閱讀程序?qū)懡Y(jié)果(本題共20分,每小題5分)單鏈表中,指針p指向某結(jié)點(diǎn),執(zhí)行以下操作后,請(qǐng)用一句話描述程序執(zhí)行的結(jié)果是什么?q=p->next;p->data=p->next->data;p->next=p->next->next;free(q);閱讀下面二分查找程序代碼,填充空白位置,使算法完整。intBinSearch(SeqListR,KeyTypek){intlow=1,high=n,mid;while(low<=high){mid=(low+high)/2;if(R[mid].key==k)returnmid;if(R[mid].key>k)____①____;else______②_____;}return0;}如下圖所示給出了圖G及對(duì)應(yīng)的鄰接表,根據(jù)給定的dfs算法,從頂點(diǎn)8出發(fā),寫出其搜索序列。Adjlistgl;voiddfs(intv){structvexnode*p;printf("%d",v);visited[v]=1;p=gl[v]->link;/*gl是該圖的鄰接表的表頭指針數(shù)組*/while(p!=NULL){if(visited[p->adjvex]==0)dfs(p->adjvex);p=p->next;}}二叉樹采用二叉鏈表存儲(chǔ)結(jié)構(gòu),將第四題綜合題3中的二叉樹,運(yùn)行下面的遞歸算法,請(qǐng)寫出最后的返回結(jié)果是什么?intcount(btree*b){intnum1,num2;if(b==NULL)return(0);elseif(b->left==NULL&&b->right==NULL)return(1);else{num1=count(b->left);num2=count(b->right);return(num1+num2);}}四、綜合題(本題共30分,每小題5分)1.有一份電文中共使用五個(gè)字符:a、b、c、d、e,它們的出現(xiàn)頻率依次為{4、7、5、2、9},試畫出
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 【中考考點(diǎn)基礎(chǔ)練】第15章 從指南針到磁浮列車 電能從哪里來 2025年物理中考總復(fù)習(xí)(福建)(含答案)
- 基于MCGS的鍋爐汽包水位計(jì)算機(jī)控制系統(tǒng)設(shè)計(jì)終稿
- 財(cái)經(jīng)法規(guī)與會(huì)計(jì)職業(yè)道德模擬試卷第一套有答案1
- 2024至2030年中國六火眼烤箱灶數(shù)據(jù)監(jiān)測研究報(bào)告
- 2024年中國高導(dǎo)磁芯繞線市場調(diào)查研究報(bào)告
- 2024年中國虎杖甙市場調(diào)查研究報(bào)告
- 2024年中國百葉窗式管道風(fēng)機(jī)市場調(diào)查研究報(bào)告
- 2024年中國機(jī)房漏水監(jiān)測系統(tǒng)市場調(diào)查研究報(bào)告
- 2024年中國顯微激光拉曼光譜儀市場調(diào)查研究報(bào)告
- 2024年中國區(qū)界牌市場調(diào)查研究報(bào)告
- 云數(shù)據(jù)中心遷移解決方案
- 江蘇省揚(yáng)州市四年級(jí)上學(xué)期語文期中試卷A(含答案)
- 初中化學(xué)項(xiàng)目式教學(xué)的實(shí)施策略探究
- 遼寧省重點(diǎn)高中沈陽市郊聯(lián)體2023-2024學(xué)年高一上學(xué)期10月月考地理試題
- 第四屆全國大學(xué)生計(jì)算機(jī)能力挑戰(zhàn)賽真題及答案
- (2023版)小學(xué)語文三年級(jí)上冊(cè)全冊(cè)單元同步訓(xùn)練及期中期末測試合集(含答案)【可編輯修改】
- 云計(jì)算管理項(xiàng)目驗(yàn)收方案
- 赤峰介紹-赤峰簡介PPT(經(jīng)典版)
- 戴海崎心理與教育測量第4版課后習(xí)題答案
- 肛門直腸疾病()課件
- 精神分裂癥臨床路徑
評(píng)論
0/150
提交評(píng)論