05到09年福建專升本數(shù)據(jù)結(jié)構(gòu)真題詳解

實(shí)用文檔實(shí)用文檔06年轉(zhuǎn)升本數(shù)據(jù)結(jié)構(gòu)考題單項(xiàng)選擇題（共12小題，每小題2分,共24分）1、已知單鏈表結(jié)構(gòu)為structnode{intdata;structnode*next;}*p,*q,*r;刪除單鏈表中結(jié)點(diǎn)p(由p指向的結(jié)點(diǎn))后面的結(jié)點(diǎn)的操作不正確的是__C__q=p->next;p->next=q->next;B、p->next=p->next->next;C、r=p->next;p->next=q->next;D、q=p->next;r=q->next;p->next=r;2、若待排序?qū)ο笮蛄性谂判蚯耙呀?jīng)按照關(guān)鍵字遞增排列，則采用__A__比較次數(shù)最少。A、直接插入排序O(n)B、快速排序O(n2)C、合并排序D、簡(jiǎn)單選擇排序O(n2)3、圖的深度優(yōu)先遍歷類似于樹(shù)的__C__A、后序遍歷B、層次遍歷C、前序遍歷D、中序遍歷4、求賦權(quán)有向圖的最短路徑常用的算法有___D___A、Prim算法和Kruskal算法B、Prim算法和Dijkstra算法C、Kruskal算法和Dijkstra算法D、Dijkstra算法和Floyd算法5、單鏈表中有n個(gè)結(jié)點(diǎn)，在其中查找值為x的結(jié)點(diǎn)，在查找成功時(shí)需要比較的平均次數(shù)是___D___。A、nB、(n-1)/2C、n/2D、(n+1)/2解答：查詢每個(gè)元素需要比較次數(shù)之和查詢平均復(fù)雜度=----------------------------------------------元素個(gè)數(shù)1+2+3+...+nn+1=----------------------------=--------n2思考：如果查找不成功，計(jì)算結(jié)果如何？6、線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)地址__B___A、必須是不連續(xù)的B、連續(xù)與否均可C、必須是連續(xù)的D、和頭結(jié)點(diǎn)的存儲(chǔ)地址項(xiàng)連續(xù)7、一棵非空的二叉樹(shù)中，設(shè)根結(jié)點(diǎn)在第0層，在第i層上最多有___D__個(gè)結(jié)點(diǎn)。A、2(i+1)B、2iC、2(i-1)D、2i根層01個(gè)/\AB層12個(gè)/\/\ABCD層24個(gè)8、在下列的排序算法中，算法的時(shí)間復(fù)雜度是O(n*log2n)是___D__。A、冒泡排序B、簡(jiǎn)單選擇排序C、直接插入排序D、堆排序9、使用一個(gè)棧，每次限制進(jìn)棧和出棧一個(gè)元素。假設(shè)進(jìn)棧的元素序列依次是a、b、c、d；指出不可能的出棧序列___B____。A、abcdB、adbcC、acbdD、dcba解答：push(a)、pop()、push(b)、pop()、push(c)、pop()、push(d)、pop(),沒(méi)辦法push(a)、pop()、push(b)、push(c)、pop()、pop()、push(d)、pop()push(a)、push(b)、push(c)、push(d)、pop()、pop()、pop()、pop()10、設(shè)數(shù)組queue[]作為循環(huán)隊(duì)列Q的存儲(chǔ)空間，front作為隊(duì)頭指針，rear作為隊(duì)尾指針，則執(zhí)行出隊(duì)操作后其頭指針front的值為_(kāi)_A___。A、front=(front+1)%mB、front=(front+1)%(m-1)C、front=(front-1)%mD、front=front+1解答：與方案1、2無(wú)關(guān)。11、對(duì)圖進(jìn)行廣度優(yōu)先遍歷時(shí)，通常采用__C__來(lái)實(shí)現(xiàn)A、字符串B、B樹(shù)C、隊(duì)列棧12、一個(gè)有n個(gè)結(jié)點(diǎn)k叉樹(shù)，樹(shù)中所有結(jié)點(diǎn)的度數(shù)之和是__B__。A、k+nB、n-1C、knD、n2解答：思路1：樹(shù)中結(jié)點(diǎn)的度數(shù)=結(jié)點(diǎn)的兒子數(shù)n個(gè)結(jié)點(diǎn)k叉樹(shù)，每個(gè)結(jié)點(diǎn)最多有k個(gè)兒子，葉子沒(méi)有兒子，因此答案不是k*n。思路2：正確的做法：樹(shù)中所有結(jié)點(diǎn)的度數(shù)之和=樹(shù)中所有邊條數(shù)，每一條邊指向一個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)有一條天線，指向父親結(jié)點(diǎn)，除了根結(jié)點(diǎn)之外。故答案是B，n-1填空題（共8小題，11空，每空2分,共22分）13、已知二叉樹(shù)后序列表為CEDBA，中序列表為CBEDA，則它的前序列表為_(kāi)_ABCDE__。解答：后序列表為CEDBA，因此根是A，中序列表為CBEDA，因此根只有左子樹(shù)CBED，沒(méi)有右子樹(shù)A/CEDB后序，根是BCBED中序，左子樹(shù)C，右子樹(shù)EDA/B/\CED后序ED中序A/B/\CD/E14、N個(gè)結(jié)點(diǎn)的有向圖，最多有___N*(N-1)_____條邊。15、存儲(chǔ)圖的最常用方法有兩種，它們是___鄰接矩陣____和____鄰接表____。16、設(shè)有一個(gè)閉散列表的容量為m，用線性探測(cè)法解決沖突，要插入一個(gè)鍵值，若插入成功，至多要進(jìn)行______比較。17、一棵哈夫曼樹(shù)有29個(gè)結(jié)點(diǎn)，其葉子的個(gè)數(shù)是___15____。解答：哈夫曼樹(shù)沒(méi)有度為1的結(jié)點(diǎn)，葉子數(shù)=內(nèi)結(jié)點(diǎn)數(shù)+1結(jié)點(diǎn)總數(shù)=葉子數(shù)+內(nèi)結(jié)點(diǎn)數(shù)=2*葉子數(shù)-1=2*內(nèi)結(jié)點(diǎn)數(shù)+118、已知單鏈表的結(jié)點(diǎn)定義為structnode{intdata;structnode*next;};在單鏈表中搜索結(jié)點(diǎn)p(由指向的結(jié)點(diǎn))的后繼結(jié)點(diǎn)的操作是____p=p->next___。19、已知雙鏈表結(jié)點(diǎn)定義為structnode{intdata;structnode*left,*right;};雙鏈表中結(jié)點(diǎn)的left和right分別指向前驅(qū)和后繼結(jié)點(diǎn)，在雙鏈表中刪除結(jié)點(diǎn)p(由指向的結(jié)點(diǎn))的操作是：p->left->right=___p->right______；和p->right->left=___p->left_____。20、對(duì)于隊(duì)列，只能在__隊(duì)尾___插入元素，在___隊(duì)頭____刪除元素。應(yīng)用題（共4小題，每小題8分，共32分）21、對(duì)圖1所示的樹(shù)結(jié)點(diǎn)A的度是_____3______。樹(shù)的度是______3_____。畫出其轉(zhuǎn)換成相應(yīng)二叉樹(shù)的樹(shù)形A/|\BCD/\/\EFGH/I解答：一般樹(shù)轉(zhuǎn)換成二叉樹(shù)步驟：將父親管理兒子方式改為父親管理大兒子，大兒子管理二兒子（二兒子變成大兒子的右孩子）二兒子管理三兒子（三兒子變成二兒子的右孩子）AABEFCDGIH前/EFBCIGHDA中B/\FEIHGDCBA后EC\\FD/G/\IH22、已知參加排序的正整數(shù)序列是：90、70、180、30、520、40、60、80、50、130。以第一個(gè)元素90作為基準(zhǔn)元素，根據(jù)快速排序算法，寫出完成第一趟劃分后序列重新排列的情況。60、70、50、30、80、40、90、520、180、13023、一次輸入如下序列中的各個(gè)整數(shù)，構(gòu)造其相應(yīng)的二叉搜索樹(shù)，只需要畫出最后生成的二叉搜索樹(shù)的樹(shù)形。整數(shù)序列是180、160、250、300、170、120、125、290、380。180/\250/\\120170300\/\12529038024、用Prim算法求圖2所示的無(wú)向帶權(quán)連通圖的最小生成樹(shù)。要求依次畫出從頂點(diǎn)1出發(fā)的最小生成樹(shù)的生成過(guò)程。1\41/\241/\23—41/\3—4/5算法設(shè)計(jì)（共2小題，第25小題10分，第26小題12分，共22分）25、二叉樹(shù)以二叉表為存儲(chǔ)結(jié)構(gòu)，結(jié)點(diǎn)結(jié)構(gòu)的定義如下，請(qǐng)寫出一個(gè)求二叉樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù)的算法。typedefstructbtnode*btlink;structbtnode{TreeItemelement;btlinkleft;btlinkright;}Btnode解答：與05年考題不一樣intf(指向樹(shù)根的指針){//f()計(jì)算樹(shù)中葉子節(jié)點(diǎn)的個(gè)數(shù)if(指向樹(shù)根的指針==NULL)return0;x=f(指向樹(shù)根的左孩子指針);//左子樹(shù)中葉節(jié)點(diǎn)數(shù)；y=f(指向樹(shù)根的右孩子指針);//右子樹(shù)中葉節(jié)點(diǎn)數(shù)；if(root->left==NULL&&root->right==NULL)return1;elsereturnx+y;/*或者if(x==0&&y==0)return1;elsereturnx+y;*/}intf(btlinkroot){//f()計(jì)算樹(shù)中葉子節(jié)點(diǎn)的個(gè)數(shù)if(root==NULL)return0;x=f(root->left);//左子樹(shù)中葉節(jié)點(diǎn)數(shù)；y=f(root->right);//右子樹(shù)中葉節(jié)點(diǎn)數(shù)；if(x==0&&y==0)return1;elsereturnx+y;}T(n)=1+T(n1)+T(n2)n1+n2=n=1+1+T(n11)+T(n12)+1+T(n21)+T(n22)n1=n11+n12n2=n21+n2225、二叉樹(shù)以二叉表為存儲(chǔ)結(jié)構(gòu)，結(jié)點(diǎn)結(jié)構(gòu)的定義如下，請(qǐng)寫出一個(gè)求二叉樹(shù)的高度算法。解答：inth(指向樹(shù)根的指針){//f()計(jì)算樹(shù)高度if(指向樹(shù)根的指針==NULL)return0;x=h(指向樹(shù)根的左孩子指針);//左子樹(shù)高度；y=h(指向樹(shù)根的右孩子指針);//右子樹(shù)高度；if(x>y)returnx+1;elsereturny+1;//return(x>y?x:y)+1;}26、閱讀下列程序，它是在已知的數(shù)組a中查找數(shù)值為x的元素，如果存在則輸出“found”，否則輸出“notfound”。試問(wèn)它是什么方法實(shí)現(xiàn)的？并請(qǐng)完善程序。用__________查找法。#defineN10voidbs(inta[],intx){intl,r,m;l=0;r=N-1;m=___(l+r)/2______;while((_____l<=r_______)&&(x!=a[m])){if(x>a[m])l=_____m+1______;elser=m-1;m=(l+r)/2;}if(___l<=r____)printf("notfound");elseprintf("found");}main(){inta[N]={10,20,30,40,50,60,70,80,90,100};intx;printf("inputx:=");scanf("%d",&x);bs(____a,x_______);}05專升本數(shù)據(jù)結(jié)構(gòu)考題一、單選題：（每題2分，共24分）1、雙向鏈表的一個(gè)結(jié)點(diǎn)有(B)個(gè)指針。A、1 B、2C、0D、32、在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度都是O(1)的操作是(A)。A、訪問(wèn)第i個(gè)結(jié)點(diǎn)(1≤i≤n)和求第i個(gè)結(jié)點(diǎn)的直接前趨(2≤i≤n)B、在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)(1≤i≤n)C、刪除第i個(gè)結(jié)點(diǎn)(1≤i≤n)D、將n個(gè)結(jié)點(diǎn)從小到大排序3、在隊(duì)列中存取數(shù)據(jù)的原則是(A)。A、先進(jìn)先出B、后進(jìn)后出?C、先進(jìn)后出D、不進(jìn)不出4、在棧中，出棧操作的時(shí)間復(fù)雜度為(A)。A、O(1)B、O(logn)C、O(n)D、O(n*n)5、設(shè)長(zhǎng)度為n的鏈隊(duì)列用單循環(huán)鏈表表示，若只設(shè)頭指針，則人隊(duì)操作的時(shí)間復(fù)雜度為(C)。A、O(1)B、0(logn)C、0(n)D、O(n*n)6、如果二叉樹(shù)的葉結(jié)點(diǎn)數(shù)為n0，則具有雙分支的結(jié)點(diǎn)數(shù)n2等于(D)。A、nO+lB、n0C、2*n0D、n0-17、一棵二叉樹(shù)滿足下列條件：對(duì)任一結(jié)點(diǎn)，若存在左、右子樹(shù)，則其值都小于它的左子樹(shù)上所有結(jié)點(diǎn)的值，而大于右子樹(shù)上所有結(jié)點(diǎn)的值?，F(xiàn)采用(B)遍歷方式就可以得到這棵二叉樹(shù)所有結(jié)點(diǎn)的遞增序列。A、先根B、中根C、后根D、層次8、用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時(shí)，其非遞歸算法通常采用(A)來(lái)實(shí)現(xiàn)算法。A、棧B、隊(duì)列C、樹(shù)D、圖9、廣度優(yōu)先遍歷類似于二叉樹(shù)的(D)。A、先序遍歷B、中序遍歷C、后序遍歷D、層次遍歷10、在一個(gè)有向圖中，所有頂點(diǎn)的人度之和等于所有頂點(diǎn)的出度之和的(B)。A、1／2倍 B、1倍C、2倍 D、4倍11、任何一個(gè)帶權(quán)無(wú)向連通圖的最小生成樹(shù)(B)。A、只有一棵 B、一棵或多棵C、一定有多棵 D、可能不存在12、設(shè)非空單鏈表的數(shù)據(jù)域?yàn)閐ata，指針域?yàn)閚ext，指針P指向單鏈表的第i個(gè)結(jié)點(diǎn)，s指向生成的新結(jié)點(diǎn)，現(xiàn)將s結(jié)點(diǎn)插入到單鏈表中，使其成為第i結(jié)點(diǎn)，下列算法段能正確完成上述要求的是(C)。A、s->next=p->；p->next=sB、p->next=s；s->next=p->next；C、S->next=p->next；p->next=s；交換p->data和s->dataD、p=s；s->next=p二、填空題（每空2分，共20分）1、數(shù)據(jù)的邏輯結(jié)構(gòu)反映_____成分?jǐn)?shù)據(jù)邏輯關(guān)系______。2、對(duì)于隊(duì)列，只能在___隊(duì)尾_____插入元素，在____隊(duì)頭_____刪除元素。3、算法是一運(yùn)算序列，它應(yīng)有：有限性、____確定性____、可行性、可以無(wú)任何輸入，但必須___有輸出____。4、由一棵二叉樹(shù)的前序序列和____中序序列____可唯一確定這棵二叉樹(shù)的結(jié)構(gòu)。5、如果圖的存儲(chǔ)結(jié)構(gòu)用____鄰接表/鄰接矩陣___表示，從某指定頂點(diǎn)作為初始點(diǎn)進(jìn)行廣度優(yōu)先搜索，得到的廣度優(yōu)先搜索序列唯一。6、用Dijkstra算法求某一頂點(diǎn)到其余各頂點(diǎn)間的最短路徑是按路徑長(zhǎng)度____遞增___的次序來(lái)得到最短路徑的。7、線性表(a1，a2，a3，……an)(n>=1)中，每個(gè)元素占c個(gè)存儲(chǔ)單元，m為a1首地址，則按順序存儲(chǔ)方式存儲(chǔ)線性表，ai存儲(chǔ)地址是_____m+(i-1)*c___。8、n個(gè)結(jié)點(diǎn)的無(wú)向圖，最多有___n*(n-1)/2__條邊。三、應(yīng)用題(本大題共4小題，每小題8分，共32分)1、用Prim算法求下圖連通的帶權(quán)圖的最小代價(jià)生成樹(shù)，在算法執(zhí)行的某一刻，已選取的頂點(diǎn)集合U=[1，2，3]，邊的集合TE=[(1，2)，(2，3)]，要選取下一條權(quán)值最小的邊，應(yīng)當(dāng)從哪些邊中選擇?2、若用插入排序方法對(duì)線性表(25，84，21，47，]5，27，68，35，20)進(jìn)行排序時(shí)，請(qǐng)給出前四趟排序結(jié)點(diǎn)序列的變化情況。答：252584212584212547843、已知一棵二叉樹(shù)的中序序列和后序序列分別為BDCEAFHG和DECBHGFA，請(qǐng)畫出該二叉樹(shù)。A/\BDCEFHG中DECBHGF后4、設(shè)將整數(shù)a，b，c，d依次進(jìn)棧，請(qǐng)回答：若入、出棧次序?yàn)镻ush(a)，Pop()，Push(b)，Push(c)，Pop()，Push(d)，Pop()，則出棧的字符序列是什么?答：acd四、算法設(shè)計(jì)(本大題共3小題，每小題8分，共24分)1、二叉樹(shù)以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，類型聲明如下，請(qǐng)寫出一個(gè)求二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)的算法。typedefstructnode{datatypedata；structnode*Lchild；structnode*Rchild；}BinaTree；答：intf(BinaTree*t){if(t==NULL)return;elsereturnf(t->left)+f(t->right)+1;}2、設(shè)線性表用順序結(jié)構(gòu)實(shí)現(xiàn)，聲明如下：typedefstructsqlist{chardata[maxsize]；intn；}Sqlist;請(qǐng)寫一個(gè)算法，判斷其是否回文?(順讀與倒讀一樣如：“ababbaba"為回文)答：解法1：形參和實(shí)參直接傳遞結(jié)構(gòu)變量#include<stdio.h>#defineMAXLENGTH100typedefstructsqlist{chardata[MAXLENGTH];intn;}Sqlist;voidf(Sqlista){inti;if(a.n<=0)return;for(i=0;i<(a.n)/2;i++){if(a.data[i]!=a.data[a.n-i]){printf("No");return;}printf("Yes");}}voidmain(){Sqlists;printf("輸入n:");scanf("%d",&s.n);printf("輸入字符串:");scanf("%s",s.data);f(s);}解法2：形參是指針變量，實(shí)參是結(jié)構(gòu)變量地址值voidf(Sqlist*a){inti;if(a->n<=0)return;for(i=0;i<(a->n)/2;i++)if(a->data[i]!=a->data[a->n-i-1]){ printf("No"); return;}printf("Yes");}voidmain(){Sqlists;printf("inputn:");scanf("%d",&(s.n));printf("inputdata:");scanf("%s",s.data);f(&s);}解法3：類似解法2，為指針變量定義了類型List#include<stdio.h>#defineMAXLENGTH100typedefstructsqlist*List;typedefstructsqlist{chardata[MAXLENGTH];intn;}Sqlist;voidf(Lista){inti;if(a->n<=0)return;for(i=0;i<(a->n)/2;i++)if(a->data[i]!=a->data[a->n-i-1]){ printf("No"); return;}printf("Yes");}voidmain(){Sqlists;printf("inputn:");scanf("%d",&(s.n));printf("inputdata:");scanf("%s",s.data);f(&s);}3、閱讀下列程序，判斷它是用什么方法實(shí)現(xiàn)排序(升序)的?并完善下列程序。#include<stdio.h>voidbubble(int[],int);main(){intarray[]={55，2，6，4，32，12，9，73，26，37};intsize=sizeof(array)/sizeof(int)；bubble(_array,10___)；}voidbubble(inta[]，intsize){inti，temp；intend_____=0__________；intpass=1；//=======================while(!end&&pass<size){end=1；for(i=0，i<size-pass；i++)if(—a[i]>a[i+1]—){temp=a[i]；a[i]=a[i+1]；a[i+1]=temp；end=___0__________；}__pass++__________________;}//=======================for(i=0；i<size；i++)printf("%d"，a[i])；}第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)（共100分）一、單項(xiàng)選擇題（本大題共12小題，每小題2分，共24分）在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)符合題目要求，請(qǐng)將正確答案代碼填寫在答題紙相應(yīng)的位置上。寫在試卷上不得分。1．在待排序記錄已基本有序的前提下,下述排序方法中效率最高的是：A)直接插入排序B)簡(jiǎn)單選擇排序C)快速排序D)歸并排序2．以下哪一個(gè)術(shù)語(yǔ)與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)？A)棧B)閉散列表C)線索二叉樹(shù)D)雙向鏈表3．有6個(gè)元素6,5,4,3,2,1的順序進(jìn)棧，問(wèn)下列哪一個(gè)不是合法的出棧序列：A)5,4,3,6,1,2B)4,5,3,1,2,6C)3,4,6,5,2,1D)2,3,4,1,5,64．下述哪一條是順序存儲(chǔ)方式的優(yōu)點(diǎn)？A)存儲(chǔ)密度大B)插入運(yùn)算方便C)刪除運(yùn)算方便D)可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示5．對(duì)于只在表的首、尾進(jìn)行插入操作的線性表，宜采用的存儲(chǔ)結(jié)構(gòu)為:

A)順序表B)用頭指針表示的單循環(huán)鏈表

C)用尾指針表示的單循環(huán)鏈表D)單鏈表6．對(duì)包含n個(gè)元素的散列表進(jìn)行查找，平均查找長(zhǎng)度A)為O(log2n)B)為O(n)C)為O(nlog2n)D)不直接依賴于n7．下列哪一種圖的鄰接矩陣是對(duì)稱矩陣？A)有向圖B)無(wú)向圖C)AOV網(wǎng)D)AOE網(wǎng)8.設(shè)表(a1,a2,a3,......,a32)中的元素已經(jīng)按遞增順序排好序，用二分法檢索與一個(gè)給定的值k相等的元素，若a1<k<a2，則在檢索過(guò)程中比較的次數(shù)是：

A)3B)4C)5D)6

9.具有3個(gè)結(jié)點(diǎn)的二叉樹(shù)最多可有多少種不同的形態(tài)。A）2 B）3 C）4 D）510．對(duì)二叉樹(shù)從1開(kāi)始編號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左右孩子的編號(hào)，同一個(gè)結(jié)點(diǎn)的左右孩子中，其左孩子的編號(hào)小于其右孩子的編號(hào)，則可采用的編號(hào)方法是：A、先序遍歷 B、中序遍歷 C、后序遍歷 D、從根開(kāi)始進(jìn)行層次遍歷11.在長(zhǎng)度為n的順序表的第i(1≤i≤n+1)個(gè)位置上插入一個(gè)元素，元素的移動(dòng)次數(shù)為：

A)n-i+1B)n-iC)iD)i-112.對(duì)于一個(gè)無(wú)向圖，下列說(shuō)法正確的是A)每個(gè)頂點(diǎn)的入度大于出度；B)每個(gè)頂點(diǎn)的度等于其入度與出度之和；C)無(wú)向圖的鄰接矩陣一定是對(duì)稱矩陣；D)有向圖中所有頂點(diǎn)的入度之和大于所有頂點(diǎn)的出度之和；二、填空題（本大題共10小題，每空2分，共22分）請(qǐng)?jiān)诖痤}紙相應(yīng)的位置上填寫正確答案。寫在試卷上不得分。設(shè)一哈希表表長(zhǎng)M為100，用除留余數(shù)法構(gòu)造哈希函數(shù)，即H（K）=K%P（P<=M）,為使函數(shù)具有較好性能，P應(yīng)選97N個(gè)結(jié)點(diǎn)的二叉樹(shù)采用二叉鏈表存放，共有空指針域個(gè)數(shù)為N+1若一個(gè)算法中的語(yǔ)句頻度之和為T(n)=3720n+4nlogn，則算法的時(shí)間復(fù)雜度為_(kāi)______O(nlogn)_________。已知有向圖的鄰接矩陣，要計(jì)算i號(hào)結(jié)點(diǎn)的入度，計(jì)算方法是：將第i列累加。深度為6（根深度為1）的二叉樹(shù)至多有63個(gè)結(jié)點(diǎn)。一棵具有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)中，結(jié)點(diǎn)總數(shù)為2n-1。設(shè)單鏈表結(jié)點(diǎn)的定義如下：structnode{intdata,structnode*next;};要在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)子鏈表，子鏈表第一個(gè)結(jié)點(diǎn)的地址為s，子鏈表最后一個(gè)結(jié)點(diǎn)的地址為t,則應(yīng)執(zhí)行操作：t->next=p->next;________和_________p->next=s；。設(shè)單鏈表結(jié)點(diǎn)的定義如19題，現(xiàn)有一個(gè)含頭結(jié)點(diǎn)的單鏈表，頭指針為head,則判斷該單鏈表是否為空表的條件為head->next==NULL。n個(gè)頂點(diǎn)的連通無(wú)向圖至少有n-1條邊。在順序存儲(chǔ)結(jié)構(gòu)的線性表中插入一個(gè)元素，平均需要移動(dòng)n/2個(gè)元素.三、應(yīng)用題：（本大題共4小題，每小題8分，共32分）請(qǐng)?jiān)诖痤}紙相應(yīng)的位置上填寫正確答案。寫在試卷上不得分。23．已知有向圖如圖1所示：（1）寫出頂點(diǎn)B的度（2分）；（2）寫出從結(jié)點(diǎn)D開(kāi)始的兩個(gè)廣度優(yōu)先搜索序列（2分）；（3）畫出該圖的鄰接表（4分）。圖1AC圖1ACBD解答:（1）頂點(diǎn)B的度:_______3________(2分)（2）_________DBCA______和_____DCBA______(2分)（3）(4分)或24.已知二叉樹(shù)的中序序列為DBGEAFC，后序序列為DGEBFCA，畫出對(duì)應(yīng)的二叉樹(shù)。解答:A/\BC/\/DEF/G圖2表示一個(gè)地區(qū)的通訊網(wǎng)，邊表示城市間的通訊線路，邊上的權(quán)值表示架設(shè)線路花費(fèi)的代價(jià)，請(qǐng)畫出該圖的最小代價(jià)支撐樹(shù)，并計(jì)算最小代價(jià)支撐樹(shù)的權(quán)。圖2解答:（每條邊1分，畫方框的兩條邊任選一條）最小代價(jià)支撐樹(shù)的權(quán)=56（3分）26.設(shè)一個(gè)閉散列表具有10個(gè)桶，散列函數(shù)H（x）=x%7，若元素輸入順序?yàn)椋簕50，42，85，22，76，19，34，68}，解決沖突用線性重新散列技術(shù)，要求畫出構(gòu)造好的散列表。解答:（8分，第二行每個(gè)數(shù)字1分）01234567894250852219763468四、算法設(shè)計(jì)（本大題共2小題，第27小題10分，第28小題12分，共22分）請(qǐng)?jiān)诖痤}紙相應(yīng)的位置上填寫正確答案。寫在試卷上不得分。27.二叉搜索樹(shù)T用二叉鏈表存儲(chǔ)結(jié)構(gòu)表示，其中各元素的值均不相同。編寫算法，按遞減順序打印T中各元素的值。結(jié)點(diǎn)結(jié)構(gòu)定義如下：typedef intTreeItem;typedefstructbtnode*btlink;typedefstructbtnode{TreeItemdata;btlinkleft,right;}BTNODE;解答:voidf(btlinkt){//或voidf(BTNODE*t)if(t){f(t->right);printf("%d",t->data);f(t->left);}}28.閱讀下面程序，其功能是調(diào)整線性表中的元素，將所有奇數(shù)放在表的左邊，將所有偶數(shù)放在表的右邊。請(qǐng)?zhí)羁胀瓿稍摮绦?。（每?分，共12分）#define MAXSIZE100typedefintElemType;typedefstruct{ ElemTypeelem[MAXSIZE]; intlast;/*末元素下標(biāo)*/}SeqList;voidAdjustSqlist(SeqList*L){ ElemTypetemp; inti=0,j=⑴; while(i<j){ while(L->elem[⑵]%2!=0&&⑶) i++; while(L->elem[⑷]%2==0&&⑸) j--; if(⑹)break; temp=L->elem[i]; L->elem[i]=⑺; L->elem[j]=⑻; }}voidmain(){ SeqList⑼; intr,i; sq=(⑽)malloc(sizeof(SeqList)); printf("請(qǐng)輸入線性表的長(zhǎng)度:"); scanf("%d",&r); sq->last=⑾; printf("請(qǐng)輸入線性表的各元素值:\n"); for(i=0;i<=sq->last;i++)scanf("%d",&⑿); AdjustSqlist(sq);}解答:（每空1分，共12分，大小寫不能錯(cuò)）⑴、_______L->last_____________ ⑵、_______i______________________⑶、_______i<L->last或i<j______ ⑷、_______j______________________⑸、_______j>0或i<j_____________ ⑹、_______i>=j___________________⑺、_______L->elem[j]__________ ⑻、______temp__________________⑼、_______*sq_________________ ⑽、_______SeqList*_____________⑾、_______r-1_________________ ⑿、_______sq->elem[i]____________08專升本數(shù)據(jù)結(jié)構(gòu)考題解答單項(xiàng)選擇題（共12小題，每小題2分，共24分）1．用非遞歸方法實(shí)現(xiàn)遞歸算法時(shí)通常要使用A．循環(huán)隊(duì)列 B．棧 C．二叉樹(shù) D．雙向隊(duì)列2．對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條弧的賦權(quán)有向圖，如果用賦權(quán)鄰接矩陣表示這個(gè)圖，請(qǐng)問(wèn)求單源最短路徑的Dijkstra算法的時(shí)間復(fù)雜度為A．O(n) B．O(n+e) C．O(n*n) D．O(2e)3．設(shè)語(yǔ)句x++的執(zhí)行時(shí)間時(shí)單位時(shí)間，以下語(yǔ)句的時(shí)間復(fù)雜度是 for(i=1;i<=n;i++)for(j=1;j<=n;j++) x++;A．O(1) B．O(n) C．O(n*n*n) D．O(n*n)4．一高度為h的非空二叉樹(shù)（假設(shè)只含根節(jié)點(diǎn)的樹(shù)的高度為1）最多有幾個(gè)節(jié)點(diǎn)A．2h B．2h-1 C．2h-1 D．2h5．賦權(quán)有向圖G用用賦權(quán)鄰接矩陣A存儲(chǔ)，則節(jié)點(diǎn)i的入度等于A．第i行非∞的元素之和 B．第i列非∞的元素之和C．第i行非∞且非0的元素個(gè)數(shù) D．第i列非∞且非0的元素個(gè)數(shù)6．設(shè)雙鏈表的節(jié)點(diǎn)類型定義如下，typedef struct node *link;typedef structnode{ ListItemelement;link left;link right;}*p,*q,*r;刪除雙鏈表中節(jié)點(diǎn)p(由p指向的節(jié)點(diǎn))的操作是正確的做法如下圖：q=p->left;r=p->right;q->right=r;r->left=q;正確的q=p->right;r=p->left;q->right=r;r->left=q;把A的p和q反過(guò)來(lái)，結(jié)果錯(cuò)了。q=p->left;r=p->right;q->left=r;r->right=q;錯(cuò)誤，與B一樣，只是把p和q反過(guò)來(lái)。D．q=p->left;r=p->right;q->right=r->left;什么也沒(méi)有變化。7．會(huì)引起循環(huán)隊(duì)列隊(duì)頭位置發(fā)生變化的操作是A．出隊(duì)列 B．入隊(duì)列 C．取隊(duì)首元素 D．取隊(duì)尾元素8．如圖1所示，若從頂點(diǎn)1出發(fā)進(jìn)行廣度優(yōu)先搜索，則得到的訪問(wèn)序列是1,8,3,4,5,6,7,21,2,3,7,5,6,4,81,2,5,4,3,6,7,8D．1,2,3,4,5,6,7,89．下列排序算法中，不受數(shù)據(jù)初始狀態(tài)影響，時(shí)間復(fù)雜度為O(n*logn)的是A．堆排序 B．冒泡排序 C．直接選擇排序 D．快速排序10．用指針實(shí)現(xiàn)二叉樹(shù)，在n個(gè)節(jié)點(diǎn)的二叉樹(shù)中含有多少個(gè)空指針？A．n B．n-1 C．n+1 D．2n11．用一棵二叉搜索樹(shù)進(jìn)行()得到的是有序序列。A．前序遍歷 B．中序遍歷 C．后序遍歷 D．層次遍歷12．合并排序算法的時(shí)間復(fù)雜度是A．O(n2) B．O(nlogn) C．O(logn) D．O(n)填空題（共7小題，每空2分，共16分）13．在一個(gè)長(zhǎng)度為n的順序表的第i（1<=i<=n）個(gè)元素之前插入一個(gè)元素，需要后移___n-i+1____個(gè)元素。14．設(shè)某哈夫曼樹(shù)有n個(gè)葉子節(jié)點(diǎn)，則該哈夫曼樹(shù)的總結(jié)點(diǎn)數(shù)為_(kāi)_2n-1__。15．設(shè)有一個(gè)序列8,53,37,28，當(dāng)使用直接插入排序從小到大排序時(shí)，比較次數(shù)是____5____。16．設(shè)SQ為循環(huán)隊(duì)列，存儲(chǔ)在數(shù)組queue[0…m-1]中，則SQ入隊(duì)操作對(duì)其隊(duì)尾指針rear的修改是___(rear+1)%m___。17．設(shè)待排序的序列中存在多個(gè)記錄具有相同的鍵值，經(jīng)過(guò)排序，這些記錄的相對(duì)次序仍然保持不變，則稱這種排序是__穩(wěn)定的____，否則稱為_(kāi)__不穩(wěn)定的___。18．在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，要連通所有的頂點(diǎn)至少需要__n-1____條邊。19．在有向圖中，以頂點(diǎn)v為起點(diǎn)的弧的數(shù)目稱為v的___出度__。應(yīng)用題（共4小題，每小題10分，共40分）20．已知關(guān)鍵字序列(12,77,21,65,38,7,40,53)，采用直接插入排序按遞增排序，給出每一趟的結(jié)果。12,77,21,65,38,7,40,5312,21,77,65,38,7,40,5312,21,65,77,38,7,40,5312,21,38,65,77,7,40,537,12,21,38,65,77,40,537,12,21,38,40,65,77,537,12,21,38,40,53,65,7721．已知散列表長(zhǎng)度為10（散列空間0..9），使用線性重新散列技術(shù)解決沖突，現(xiàn)有一組單詞(SUN,MON,TUE,WED,THU,FRI,SAT)，其對(duì)應(yīng)的散列函數(shù)值分別為(3,2,6,3,2,5,6)，請(qǐng)畫出這組單詞插入后的散列表。0123456789MONSUNWEDTHUTUEFRISAT22．假設(shè)一個(gè)二叉樹(shù)的先序?yàn)镋BADCFHGIKJ，中序序列是ABCDEFGHIJK，畫出二叉樹(shù)；（2）寫出后序序列。先序?yàn)镋BADCFHGIKJ，中序序列是ABCDEFGHIJK，根是EE/\ABCDFGHIJK中BADCFHGIKJ先序根B根F/\/\ACDGHIJK中ADCHGIKJ先序根D根H//\CGIJK中IKJ先根I\JK中KJ先根K/J最后結(jié)果：E/\BF/\\ADH//\CGI\K/J后序是：ACDBGJKIHFE23．根據(jù)PRIM算法畫出圖2的最小生成樹(shù)，要求畫出從頂點(diǎn)1開(kāi)始生成的過(guò)程。解答：算法設(shè)計(jì)題（共2小題，每小題10分，共20分）24．下列程序?qū)⒓螦和集合B歸并成一個(gè)集合C，歸并前集合A和集合B中的元素按非遞減排列，歸并后集合C的元素仍按非遞減順序排列，而且C不需要新建節(jié)點(diǎn)空間。請(qǐng)完善程序。typedefstructnode{ElemTypedata;structnode*next;}*LinkList說(shuō)明：*LinkList是指針類型，基類型是LNode。voidMergeSet(LinkListLa,LinkListLb){ LinkListpa,pb,pc,p;pa=La;pb=Lb;pc=NULL;while(_____pa!=NULL&&pb!=NULL__________){if(pa->data<=pb->data){if(pc!=NULL){______p->next=pa;________________p=p->next;}else{pc=pa;p=pc;}//if_____pa=pa->next_______________;}else{if(pc!=NULL){____p->next=pb;_______________p=p->next;}else{pc=pb;p=pc;}//if____pb=pb->next_____________;}//if}//whilep->next=(pa!=NULL)?pa:pb;/*處理一個(gè)鏈表為空的情況*/}25．二叉排序（搜索）樹(shù)t以二叉表為存儲(chǔ)結(jié)構(gòu)，請(qǐng)編寫算法實(shí)現(xiàn)在該樹(shù)上查找值為x的節(jié)點(diǎn)。typedefintTreeItem;typedefstructbtnode*btlink;typedefstructbtnode{TreeItemdata;Btlinklchild,rchild;/*左右孩子指針*/}BiTNode算法函數(shù)原型BiTNodeLocate(BiTNode*t,TreeItemx)解答：BiTNodeLocate(BiTNode*t,TreeItemx){if(t==NULL)returnNULL:if(x==t->data)return*t;/*注意*，因?yàn)榉祷仡愋褪荁iTNode*/elseif(x<t->data)returnLocate(t->lchild,x);/*左子樹(shù)*/elsereturnLocate(t->rchild,x);/*右子樹(shù)*/}09年專升本數(shù)據(jù)結(jié)構(gòu)考題解答(共100分)單項(xiàng)選擇題（12小題，每小題2分，共24分）1、要表示高校校、系、班級(jí)的有關(guān)數(shù)據(jù)及其關(guān)系，選擇______比較合適。A.線性結(jié)構(gòu) B.樹(shù)結(jié)構(gòu)C.圖結(jié)構(gòu) D.集合結(jié)構(gòu)2、下列函數(shù)中復(fù)雜度最小的是A.T(n)=nlog2n+5000nB.T(n)=n2-8000nC.T(n)=nlog22n-6000nD.T(n)=2nlog22n-7000nnlog22n=nlog22+log2n=n1+log2n=n*nlog2n3、已知一個(gè)棧s以及一個(gè)輸入序列(A，B，C，D，E)，每個(gè)元素按照A，B，C，D，E順序進(jìn)棧一次，進(jìn)棧后可立即出棧，也可在棧中停留一段時(shí)間后再出棧，則不能得到（）序列。A．A、B、C、D、EB.B、A、E、D、CC．C、B、A、D、ED.D、C、A、B、E4、平均排序效率最好的排序方法是（）。A．直接插入排序B．快速排序C．簡(jiǎn)單選擇排序D．冒泡排序5、某鏈表中最常用的操作是在已知的一個(gè)結(jié)點(diǎn)之前插入一個(gè)新結(jié)點(diǎn)和刪除其之前一個(gè)結(jié)點(diǎn)，則采用（）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A．雙向鏈表 B．帶頭指針的單向鏈表C．帶尾指針的單向鏈表D．單向循環(huán)鏈表6、在邏輯結(jié)構(gòu)不變的情況下，不是導(dǎo)致一個(gè)圖的遍歷序列不唯一的因素是（）。A．出發(fā)點(diǎn)不同 B．存儲(chǔ)(物理)結(jié)構(gòu)不同C．遍歷方法不同 D．畫法不同7、散列函數(shù)有一個(gè)共同的要求，即函數(shù)值應(yīng)當(dāng)盡量以（）取其值域的每個(gè)值。A．最大概率 B．最小概率C．正態(tài)分布概率 D．均等概率8、下面（）方法可以判斷出一個(gè)圖中是否存在環(huán)(回路)。A．排序 B．深度和廣度遍歷C．求最短路徑 D．求關(guān)鍵路徑9．最佳二叉搜索(排序)樹(shù)是（）。A．關(guān)鍵碼個(gè)數(shù)最小的二叉搜索樹(shù)B．退化為線性的二叉搜索樹(shù)，C．搜索中平均比較次數(shù)最小的二叉搜索樹(shù)D．任何結(jié)點(diǎn)的度數(shù)為0或2的二叉搜索樹(shù)10．（）是數(shù)據(jù)的基本單位，即數(shù)據(jù)集合(對(duì)象)中的個(gè)體。A．?dāng)?shù)據(jù)結(jié)構(gòu)B．?dāng)?shù)據(jù)項(xiàng)C．?dāng)?shù)據(jù)元素D．?dāng)?shù)據(jù)對(duì)象11．(線性)表是一個(gè)（）。A．有限序列，可以為空B．有限序列，不能為空C．無(wú)限序列，可以為空D．無(wú)限序列，不能為空12．樹(shù)是結(jié)點(diǎn)的集合，它（）