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

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

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

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

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

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

A)n-i+1B)n-iC)iD)i-112.對于一個無向圖，下列說法正確的是A)每個頂點的入度大于出度；B)每個頂點的度等于其入度與出度之和；C)無向圖的鄰接矩陣一定是對稱矩陣；D)有向圖中所有頂點的入度之和大于所有頂點的出度之和；二、填空題（本大題共10小題，每空2分，共22分）請在答題紙相應(yīng)的位置上填寫正確答案。寫在試卷上不得分。設(shè)一哈希表表長M為100，用除留余數(shù)法構(gòu)造哈希函數(shù)，即H（K）=K%P（P<=M）,為使函數(shù)具有較好性能，P應(yīng)選97N個結(jié)點的二叉樹采用二叉鏈表存放，共有空指針域個數(shù)為N+1若一個算法中的語句頻度之和為T(n)=3720n+4nlogn，則算法的時間復(fù)雜度為_______O(nlogn)_________。已知有向圖的鄰接矩陣，要計算i號結(jié)點的入度，計算方法是：將第i列累加。深度為6（根深度為1）的二叉樹至多有63個結(jié)點。一棵具有n個葉子結(jié)點的哈夫曼樹中，結(jié)點總數(shù)為2n-1。設(shè)單鏈表結(jié)點的定義如下：structnode{intdata,structnode*next;};要在一個單鏈表中p所指結(jié)點之后插入一個子鏈表，子鏈表第一個結(jié)點的地址為s，子鏈表最后一個結(jié)點的地址為t,則應(yīng)執(zhí)行操作：t->next=p->next;________和_________p->next=s；。設(shè)單鏈表結(jié)點的定義如19題，現(xiàn)有一個含頭結(jié)點的單鏈表，頭指針為head,則判斷該單鏈表是否為空表的條件為head->next==NULL。n個頂點的連通無向圖至少有n-1條邊。在順序存儲結(jié)構(gòu)的線性表中插入一個元素，平均需要移動n/2個元素.三、應(yīng)用題：（本大題共4小題，每小題8分，共32分）請在答題紙相應(yīng)的位置上填寫正確答案。寫在試卷上不得分。23．已知有向圖如圖1所示：（1）寫出頂點B的度（2分）；（2）寫出從結(jié)點D開始的兩個廣度優(yōu)先搜索序列（2分）；（3）畫出該圖的鄰接表（4分）。圖1AC圖1ACBD解答:（1）頂點B的度:_______3________(2分)（2）_________DBCA______和_____DCBA______(2分)（3）(4分)或24.已知二叉樹的中序序列為DBGEAFC，后序序列為DGEBFCA，畫出對應(yīng)的二叉樹。解答:A/\BC/\/DEF/G圖2表示一個地區(qū)的通訊網(wǎng)，邊表示城市間的通訊線路，邊上的權(quán)值表示架設(shè)線路花費的代價，請畫出該圖的最小代價支撐樹，并計算最小代價支撐樹的權(quán)。圖2解答:（每條邊1分，畫方框的兩條邊任選一條）最小代價支撐樹的權(quán)=56（3分）26.設(shè)一個閉散列表具有10個桶，散列函數(shù)H（x）=x%7，若元素輸入順序為：{50，42，85，22，76，19，34，68}，解決沖突用線性重新散列技術(shù)，要求畫出構(gòu)造好的散列表。解答:（8分，第二行每個數(shù)字1分）01234567894250852219763468四、算法設(shè)計（本大題共2小題，第27小題10分，第28小題12分，共22分）請在答題紙相應(yīng)的位置上填寫正確答案。寫在試卷上不得分。27.二叉搜索樹T用二叉鏈表存儲結(jié)構(gòu)表示，其中各元素的值均不相同。編寫算法，按遞減順序打印T中各元素的值。結(jié)點結(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ù)放在表的右邊。請?zhí)羁胀瓿稍摮绦颉＃靠?分，共12分）#define MAXSIZE100typedefintElemType;typedefstruct{ ElemTypeelem[MAXSIZE]; intlast;/*末元素下標*/}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("請輸入線性表的長度:"); scanf("%d",&r); sq->last=⑾; printf("請輸入線性表的各元素值:\n"); for(i=0;i<=sq->last;i++)scanf("%d",&⑿); AdjustSqlist(sq);}解答:（每空1分，共12分，大小寫不能錯）⑴、_______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)考題解答單項選擇題（共12小題，每小題2分，共24分）1．用非遞歸方法實現(xiàn)遞歸算法時通常要使用A．循環(huán)隊列 B．棧 C．二叉樹 D．雙向隊列2．對于一個具有n個頂點和e條弧的賦權(quán)有向圖，如果用賦權(quán)鄰接矩陣表示這個圖，請問求單源最短路徑的Dijkstra算法的時間復(fù)雜度為A．O(n) B．O(n+e) C．O(n*n) D．O(2e)3．設(shè)語句x++的執(zhí)行時間時單位時間，以下語句的時間復(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è)只含根節(jié)點的樹的高度為1）最多有幾個節(jié)點A．2h B．2h-1 C．2h-1 D．2h5．賦權(quán)有向圖G用用賦權(quán)鄰接矩陣A存儲，則節(jié)點i的入度等于A．第i行非∞的元素之和 B．第i列非∞的元素之和C．第i行非∞且非0的元素個數(shù) D．第i列非∞且非0的元素個數(shù)6．設(shè)雙鏈表的節(jié)點類型定義如下，typedef struct node *link;typedef structnode{ ListItemelement;link left;link right;}*p,*q,*r;刪除雙鏈表中節(jié)點p(由p指向的節(jié)點)的操作是正確的做法如下圖：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反過來，結(jié)果錯了。q=p->left;r=p->right;q->left=r;r->right=q;錯誤，與B一樣，只是把p和q反過來。D．q=p->left;r=p->right;q->right=r->left;什么也沒有變化。7．會引起循環(huán)隊列隊頭位置發(fā)生變化的操作是A．出隊列 B．入隊列 C．取隊首元素 D．取隊尾元素8．如圖1所示，若從頂點1出發(fā)進行廣度優(yōu)先搜索，則得到的訪問序列是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)影響，時間復(fù)雜度為O(n*logn)的是A．堆排序 B．冒泡排序 C．直接選擇排序 D．快速排序10．用指針實現(xiàn)二叉樹，在n個節(jié)點的二叉樹中含有多少個空指針？A．n B．n-1 C．n+1 D．2n11．用一棵二叉搜索樹進行()得到的是有序序列。A．前序遍歷 B．中序遍歷 C．后序遍歷 D．層次遍歷12．合并排序算法的時間復(fù)雜度是A．O(n2) B．O(nlogn) C．O(logn) D．O(n)填空題（共7小題，每空2分，共16分）13．在一個長度為n的順序表的第i（1<=i<=n）個元素之前插入一個元素，需要后移___n-i+1____個元素。14．設(shè)某哈夫曼樹有n個葉子節(jié)點，則該哈夫曼樹的總結(jié)點數(shù)為__2n-1__。15．設(shè)有一個序列8,53,37,28，當使用直接插入排序從小到大排序時，比較次數(shù)是____5____。16．設(shè)SQ為循環(huán)隊列，存儲在數(shù)組queue[0…m-1]中，則SQ入隊操作對其隊尾指針rear的修改是___(rear+1)%m___。17．設(shè)待排序的序列中存在多個記錄具有相同的鍵值，經(jīng)過排序，這些記錄的相對次序仍然保持不變，則稱這種排序是__穩(wěn)定的____，否則稱為___不穩(wěn)定的___。18．在一個具有n個頂點的無向圖中，要連通所有的頂點至少需要__n-1____條邊。19．在有向圖中，以頂點v為起點的弧的數(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．已知散列表長度為10（散列空間0..9），使用線性重新散列技術(shù)解決沖突，現(xiàn)有一組單詞(SUN,MON,TUE,WED,THU,FRI,SAT)，其對應(yīng)的散列函數(shù)值分別為(3,2,6,3,2,5,6)，請畫出這組單詞插入后的散列表。0123456789MONSUNWEDTHUTUEFRISAT22．假設(shè)一個二叉樹的先序為EBADCFHGIKJ，中序序列是ABCDEFGHIJK，畫出二叉樹；（2）寫出后序序列。先序為EBADCFHGIKJ，中序序列是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的最小生成樹，要求畫出從頂點1開始生成的過程。解答：算法設(shè)計題（共2小題，每小題10分，共20分）24．下列程序?qū)⒓螦和集合B歸并成一個集合C，歸并前集合A和集合B中的元素按非遞減排列，歸并后集合C的元素仍按非遞減順序排列，而且C不需要新建節(jié)點空間。請完善程序。typedefstructnode{ElemTypedata;structnode*next;}*LinkList說明：*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;/*處理一個鏈表為空的情況*/}25．二叉排序（搜索）樹t以二叉表為存儲結(jié)構(gòu)，請編寫算法實現(xiàn)在該樹上查找值為x的節(jié)點。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;/*注意*，因為返回類型是BiTNode*/elseif(x<t->data)returnLocate(t->lchild,x);/*左子樹*/elsereturnLocate(t->rchild,x);/*右子樹*/}09年專升本數(shù)據(jù)結(jié)構(gòu)考題解答(共100分)單項選擇題（12小題，每小題2分，共24分）1、要表示高校校、系、班級的有關(guān)數(shù)據(jù)及其關(guān)系，選擇______比較合適。A.線性結(jié)構(gòu) B.樹結(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、已知一個棧s以及一個輸入序列(A，B，C，D，E)，每個元素按照A，B，C，D，E順序進棧一次，進棧后可立即出棧，也可在棧中停留一段時間后再出棧，則不能得到（）序列。A．A、B、C、D、EB.B、A、E、D、CC．C、B、A、D、ED.D、C、A、B、E4、平均排序效率最好的排序方法是（）。A．直接插入排序B．快速排序C．簡單選擇排序D．冒泡排序5、某鏈表中最常用的操作是在已知的一個結(jié)點之前插入一個新結(jié)點和刪除其之前一個結(jié)點，則采用（）存儲方式最節(jié)省運算時間。A．雙向鏈表 B．帶頭指針的單向鏈表C．帶尾指針的單向鏈表D．單向循環(huán)鏈表6、在邏輯結(jié)構(gòu)不變的情況下，不是導致一個圖的遍歷序列不唯一的因素是（）。A．出發(fā)點不同 B．存儲(物理)結(jié)構(gòu)不同C．遍歷方法不同 D．畫法不同7、散列函數(shù)有一個共同的要求，即函數(shù)值應(yīng)當盡量以（）取其值域的每個值。A．最大概率 B．最小概率C．正態(tài)分布概率 D．均等概率8、下面（）方法可以判斷出一個圖中是否存在環(huán)(回路)。A．排序 B．深度和廣度遍歷C．求最短路徑 D．求關(guān)鍵路徑9．最佳二叉搜索(排序)樹是（）。A．關(guān)鍵碼個數(shù)最小的二叉搜索樹B．退化為線性的二叉搜索樹，C．搜索中平均比較次數(shù)最小的二叉搜索樹D．任何結(jié)點的度數(shù)為0或2的二叉搜索樹10．（）是數(shù)據(jù)的基本單位，即數(shù)據(jù)集合(對象)中的個體。A．數(shù)據(jù)結(jié)構(gòu)B．數(shù)據(jù)項C．數(shù)據(jù)元素D．數(shù)據(jù)對象11．(線性)表是一個（）。A．有限序列，可以為空B．有限序列，不能為空C．無限序列，可以為空D．無限序列，不能為空12．樹是結(jié)點的集合，它（）