數(shù)據(jù)結(jié)構(gòu)試題及答案(免費(fèi))

1、一、單選題（每題2分，共20分）1. 1.對一個(gè)算法的評價(jià)，不包括如下（B ）方面的內(nèi)容。A.健壯性和可讀性B .并行性C.正確性 D.時(shí)空復(fù)雜度2. 2.在帶有頭結(jié)點(diǎn)的單鏈表HL中，要向表頭插入一個(gè)由指針 p指向的結(jié) 點(diǎn)，則執(zhí)行（）。A. p->n ext=HL->n ext; HL->n ext=p;B. p->n ext=HL; HL=p;C. p-> next=HL; p=HL;D. HL=p; p-> next=HL;3. 3.對線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？（）A.經(jīng)常需要隨機(jī)地存取元素B.經(jīng)常需要進(jìn)行插入和刪除操作C.表中元素需要占

2、據(jù)一片連續(xù)的存儲空間D.表中元素的個(gè)數(shù)不變4.4. 一個(gè)棧的輸入序列為1 2 3,則下列序列中不可能是棧的 輸出序列的是 （C ）A. 2 3 1C. 3 1 2B. 3 2 1D. 1 2 35. 5. AOV 網(wǎng)是-種（）。A.有向圖B.無向圖C.無向無環(huán)圖D .有向無環(huán)圖6. 6.采用開放定址法處理散列表的沖突時(shí)，其平均查找長度（）。A .低于鏈接法處理沖突B.高于鏈接法處理沖突C.與鏈接法處理沖突相同D .高于二分查找7. 7.若需要利用形參直接訪問實(shí)參時(shí)，應(yīng)將形參變量說明為（）參數(shù)。A .值 B.函數(shù)C.指針D .引用8. 8.在稀疏矩陣的帶行指針向量的鏈接存儲中，每個(gè)單鏈表中的結(jié)點(diǎn)

3、都具 有相同的（）。A .行號 B.列號C.元素值D .非零元素個(gè)數(shù)9. 9.快速排序在最壞情況下的時(shí)間復(fù)雜度為（）。A. O（log2n）B. 0（nlog2n）C. 0（n）D . 0（n2）10.10.從二叉搜索樹中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為（）。A. O（ n）B. O（1） C. O（log2 n）D. O（ n2）二、二、運(yùn)算題（每題6分，共24分）1. 1.數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的 當(dāng)結(jié)點(diǎn)之間存在M對N （ M : N ）的聯(lián)系時(shí)，稱這種結(jié)構(gòu)為 。2. 2.隊(duì)列的插入操作是在隊(duì)列的 _尾 行，刪除操作是在隊(duì)列的首行。3. 3.當(dāng)用長度為N的數(shù)組順序存儲一個(gè)棧時(shí)，假定

4、用top=N表示?？?，則表示棧滿的條件是top=0（要超出才為滿）。4. 4.對于一個(gè)長度為n的單鏈存儲的線性表，在表頭插入元素的時(shí)間復(fù)雜度為 在表尾插入元素的時(shí)間復(fù)雜度為 。5. 5.設(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ù)組元素 W6，3的起始 地址為。6. 6. 廣義表A= (a,(a,b),(a,b),c),則它的深度為它的長度為7. 7.二叉樹是指度為2的 寸。一棵結(jié)點(diǎn)數(shù)為N的二叉樹，其所有結(jié)點(diǎn)的度的總和是

5、 。8. 8. 對一棵二叉搜索樹進(jìn)行中序遍歷時(shí)，得到的結(jié)點(diǎn)序列是一個(gè)。對一棵由算術(shù)表達(dá)式組成的二叉語法樹進(jìn)行后序遍歷得到 的結(jié)點(diǎn)序列是該算術(shù)表達(dá)式的。9. 9.對于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，用二叉鏈表存儲時(shí)，其指針總數(shù)為個(gè)，其中個(gè)用于指向孩子，指針是空閑的。10. 10.若對一棵完全二叉樹從0開始進(jìn)行結(jié)點(diǎn)的編號，并按此編號把它順序存儲到一維數(shù)組A中，即編號為0的結(jié)點(diǎn)存儲到A0中。其余類推，貝U A i 元素的左孩子元素為 ，右孩子元素為，雙親元素為11. 11.在線性表的散列存儲中，處理沖突的常用方法有和 種。12. 12.當(dāng)待排序的記錄數(shù)較大，排序碼較隨機(jī)且對穩(wěn)定性不作要求時(shí)，宜采用 卡序；

6、當(dāng)待排序的記錄數(shù)較大，存儲空間允許且要求排序 是穩(wěn)定時(shí)，宜米用 卡序。三、三、運(yùn)算題(每題6分，共24分)1. 1.已知一個(gè)6 5稀疏矩陣如下所示，0000100000011 000000025000000700試：(1) (1)寫出它的三元組線性表；(2) (2)給出三元組線性表的順序存儲表示。2. 2.設(shè)有一個(gè)輸入數(shù)據(jù)的序列是 46, 25, 78, 62, 12, 80,試畫出從空樹起, 逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉搜索樹。3. 3.對于圖6所示的有向圖若存儲它采用鄰接表，并且每個(gè)頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號從小到大的次序鏈接的，試寫出：(1) 從頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索所得到的

7、深度優(yōu)先生成樹；(2) 從頂點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹；圖64. 4.已知一個(gè)圖的頂點(diǎn)集V和邊集E分別為:V=1,2,3,4,5,6,7;E=<2,1>,v3,2>,v3,6>,v4,3>,<4,5> ,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>J若存儲它采用鄰接表，并且每個(gè)頂 點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序 號從小到大的次序鏈接的，按主教材中介紹的拓樸排序算法進(jìn)行排序，試給出得到的拓樸排序的序列四、四、閱讀算法(每題7分，共14分)

8、1. 1.int Prime(i nt n)int i=1;int x=(i nt) sqrt (n);while (+i<=x)if (n %i=0) break;if (i>x) retur n 1;else return 0;(1) (1)指出該算法的功能；(2) (2)該算法的時(shí)間復(fù)雜度是多少？2. 2.寫出下述算法的功能：void AJ(adjlist GL, int i, int n)Queue Q;Ini tQueue(Q); coutvvivv''visitedi=true;QInsert(Q,i);while(!QueueEmpty(Q) int

9、k=QDelete(Q); edgenode* p=GLk; while(p!=NULL)int j=p->adjvex;if(!visitedj)cout<<j<<' ' visitedj=true; QInsert(Q,j);p=p->next;五、 五、 算法填空(共 8 分) 如下為二分查找的非遞歸算法，試將其填寫完整。 Int Binsch(ElemType A ,int n,KeyType K) int low=0; int high=n-1; while (low<=high) int mid=；if (K=Amid.ke

10、y) return mid;/查找成功，返回元素的下標(biāo)else if (K<mid.key) ; / 在左子表上 繼續(xù)查找 else ; / 在右子表上繼續(xù)查找return -1;/查找失敗，返回 -1六、六、編寫算法（共8分）HL是單鏈表的頭指針，試寫出刪除頭結(jié)點(diǎn)的算法ElemType DeleFro nt（LNode * & HL）、單選題（每題1.B2.A3.B4.C5.D6.B7.D、填空題（每空1.1.聯(lián)系圖（或圖結(jié)構(gòu)）2.2.尾 首3.3.top=04.4.O (1)O (n)5.5.128441086.6.33參考答案2分，共20分）8.A9.D10.C1分，共26

11、分）2.3.4.四、1.2.五、65515132-145-2515637圖72.3.BFS:4.1.(2)2.如圖8所示。DFS：.1.12.有序有序序列2n n-12i+1開放定址法快速n-1后綴表達(dá)式（或逆波蘭式）n+12i+2（i-1）/2鏈接法 歸并運(yùn)算題（每題6分，共24分）1.（2）(3分)1.12（1）三兀組線性表的順序存儲表示如圖（1,5,1）,（3,2,-1）,（4,5,-2）,（5,1,5）,（6,3,7）7示。57（每題（1）判斷n是否是素?cái)?shù)（或質(zhì)數(shù)）O （ n功能為：五、拓樸排序?yàn)?四、43 6閱讀算法2 17分，共14分

12、）(low+high)/2六、六、ElemType DeleFro nt(LNode * & HL) if (HL=NULL) cerr<<"空表"<<endl; exit(1);LNode* p=HL;）從初始點(diǎn) vi出發(fā)廣度優(yōu)先搜索由鄰接表GL所表示的圖。算法填空（8分）high=mid-1編寫算法（8分）low=mid+1HL=HL-> next;ElemType temp=p->data; delete p;return temp;第一部分 選擇題(30分)一、項(xiàng)選擇題(本大題共15小題，每小題2分，共30分)在每小題列出

13、的 四個(gè)選項(xiàng)中只有一個(gè)選項(xiàng)是符合題目要求的， 請將正確選項(xiàng)前的字母填在題 后的括號內(nèi)。1 算法指的是()A .計(jì)算機(jī)程序B.解決問題的計(jì)算方法C.排序算法D .解決問題的有限運(yùn)算序列2.線性表采用鏈?zhǔn)酱鎯r(shí)，結(jié)點(diǎn)的存儲地址()A. 必須是不連續(xù)的B. 連續(xù)與否均可C. 必須是連續(xù)的D. 和頭結(jié)點(diǎn)的存儲地址相連續(xù)3. 將長度為n的單鏈表鏈接在長度為()A. O (1)B. O (n)4. 由兩個(gè)棧共享一個(gè)向量空間的好處是:m的單鏈表之后的算法的時(shí)間復(fù)雜度為C. O (m)D. O (m+n)()A .減少存取時(shí)間，降低下溢發(fā)生的機(jī)率B. 節(jié)省存儲空間，降低上溢發(fā)生的機(jī)率C. 減少存取時(shí)間，降低上

14、溢發(fā)生的機(jī)率D. 節(jié)省存儲空間，降低下溢發(fā)生的機(jī)率5 .設(shè)數(shù)組datam作為循環(huán)隊(duì)列SQ的存儲空間，front為隊(duì)頭指針，rear為隊(duì)尾 指針，則執(zhí)行出隊(duì)操作后其頭指針front值為()A. front=fro nt+1C. front=(front-1)%m6. 如下陳述中正確的是(A.串是一種特殊的線性表C.串中元素只能是字母B. front=(front+1)%(m-1) D . front=(front+1)%m)B.串的長度必須大于零D .空串就是空白串7. 若目標(biāo)串的長度為n，模式串的長度為n/3，則執(zhí)行模式匹配算法時(shí)，在最 壞情況下的時(shí)間復(fù)雜度是()A . O ( 3) B .

15、O (n)C . O (n2)D . O (n3)8 個(gè)非空廣義表的表頭（ A 不可能是子表B只能是子表D .可以是子表或原子9.假設(shè)以帶行表的三元組表表示稀疏矩陣7 o8 qOq 6B. 0 oo 400 o3,5州cD. 0700 000 005 30 040 0C. 只能是原子1Q.在一棵度為3的樹中，度為3的結(jié)點(diǎn)個(gè)數(shù)為2,度為2的結(jié)點(diǎn)個(gè)數(shù)為1,則度為 0的結(jié)點(diǎn)個(gè)數(shù)為（）A. 4B . 5C. 6D . 711.在含n個(gè)頂點(diǎn)和e條邊的無向圖的鄰接矩陣中，零元素的個(gè)數(shù)為（）A. eB . 2eC. n2 eD. n2 2e12 .假設(shè)一個(gè)有n個(gè)頂點(diǎn)和e條弧的有向圖用鄰接表表示，則刪除與某個(gè)

16、頂點(diǎn)Vi相關(guān)的所有弧的時(shí)間復(fù)雜度是（A . O（n）B . O（e）13 .用某種排序方法對關(guān)鍵字序列（行排序時(shí)，序列的變化情況如下：27,27,35,）25,)C . O(n+e)84,21, 47,D . 0( n*e)15, 27, 68, 35, 2Q)進(jìn)20, 15, 21, 25,15, 20, 21, 25,15, 20, 21, 25,則所采用的排序方法是A.選擇排序47,35,27,68,47,47,35,68,68,848484B.希爾排序C .歸并排序14 .適于對動態(tài)查找表進(jìn)行高效率查找的組織結(jié)構(gòu)是（A .有序表 B .分塊有序表15 .不定長文件是指（）A .文件的長

17、度不固定C .字段的長度不固定C.三叉排序樹D.快速排序）D.線性鏈表B .記錄的長度不固定 D .關(guān)鍵字項(xiàng)的長度不固定第二部分非選擇題（共70分）二、填空題（本大題共10小題，每小題2分，若有兩個(gè)空格，每個(gè)空格1分， 共20分）不寫解答過程，將正確的答案寫在每小題的空格內(nèi)。錯(cuò)填或不填 均無分。16 .數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)， 它與數(shù)據(jù)的無關(guān)，是獨(dú)立于計(jì)算機(jī)的。17 .在一個(gè)帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，p指向尾結(jié)點(diǎn)的直接前驅(qū)，則指向頭結(jié)點(diǎn)的指針 head可用 p表示為 head 。18 .棧頂?shù)奈恢檬请S著 操作而變化的。19. 在串S= “structure”中，以t為首字符的子串有

18、 個(gè)。20. 假設(shè)一個(gè)9階的上三角矩陣A按列優(yōu)先順序壓縮存儲在一維數(shù)組 B中，其中B0存儲矩陣中第1個(gè)元素ai,i,則B31中存放的元素是。21. 已知一棵完全二叉樹中共有768結(jié)點(diǎn)，則該樹中共有 個(gè)葉子結(jié)點(diǎn)。22. 已知一個(gè)圖的廣度優(yōu)先生成樹如右圖所示，貝U與此相 應(yīng)的廣度優(yōu)先遍歷序列為 。23. 在單鏈表上難以實(shí)現(xiàn)的排序方法有 和。24. 在有序表(12, 24, 36, 48, 60, 72, 84)中二分查找關(guān)鍵字72時(shí)所需進(jìn) 行的關(guān)鍵字比較次數(shù)為。25. 多重表文件和倒排文件都?xì)w屬于文件。三、解答題(本大題共4小題，每小題5分，共20分)26. 畫出下列廣義表的共享結(jié)構(gòu)圖形表示P=

19、(z) ,(x,y) ,(x,y),x),(z)27. 請畫出與下列二叉樹對應(yīng)的森林。0001128. 已知一個(gè)無向圖的頂點(diǎn)集為a, b, c, d, e，其鄰接矩陣如下所示a 10110b (1)畫出該圖的圖形；c(2)根據(jù)鄰接矩陣從頂點(diǎn) a出發(fā)進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷,12d寫出相應(yīng)的遍歷序列。29.已知一個(gè)散列表如下圖所示:352033485901234567891011其散列函數(shù)為h(key)=key%13,處理沖突的方法為雙重散列法，探查序列為:hi=(h(key)+i *h1(key)%m i =0,1，,m 1其中h1(key)=key%11+1回答下列問題：(1) 對表中

20、關(guān)鍵字35, 20, 33和48進(jìn)行查找時(shí)，所需進(jìn)行的比較次數(shù)各 為多少？(2) 該散列表在等概率查找時(shí)查找成功的平均查找長度為多少？四、算法閱讀題(本大題共4小題，每小題5分，共20分)30 下列算法的功能是比較兩個(gè)鏈串的大小S2其返回值為：1當(dāng) S| S2comstr(si,s2)=請?jiān)诳瞻滋幪钊脒m當(dāng)?shù)膬?nèi)容。in t comstr(Li nkStri ng s1,Li nkStri ng s2)/si和s2為兩個(gè)鏈串的頭指針while(s1 &&s2)if(s1 >date<s2 >date)retur n 1 ；if(s1 >date>s2

21、>date)retur n1；_®；if( )return 1 ；if( )return1 ； ：31 閱讀下面的算法Lin kList myno te(L in kList L)/L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針if(L&&L- >n ext)q=L ； L=L >next； p=L ；S1:while(p >n ext) p=p >n ext；S2:p >next=q； q >next=NULL ；return L ；請回答下列問題：(1) 說明語句S1的功能；(2) 說明語句組S2的功能；(3) 設(shè)鏈表表示的線性表為(a1

22、,a2,an),寫出算法執(zhí)行后的返回值所 表示的線性表。32. 假設(shè)兩個(gè)隊(duì)列共享一個(gè)循環(huán)向量空間(參見右 下圖)，其類型Queue2定義如下：typedef structDateType dataMaxSize;int front2,rear2；Queue2；對于i=0或1, fronti和reari分別為第i個(gè)隊(duì)列的頭指針和尾指針。請對以 下算法填空，實(shí)現(xiàn)第i個(gè)隊(duì)列的入隊(duì)操作。int En Queue (Queue2*Q,i nt i,DateType x)/若第i個(gè)隊(duì)列不滿，則元素x入隊(duì)列，并返回1;否則返回0if(i<0|i>1)return 0 ；if(Q >rear

23、i=Q >fron t return0 ；Q >data =x ；Q >reari=;return1；33. 已知二叉樹的存儲結(jié)構(gòu)為二叉鏈表，閱讀下面算法。typedef struct node DateType dataStruct node * n ext；ListNode ；typedef ListNode * Lin kList ；LinkList Leafhead=NULL ；Void Ino rder (Bi nTree T)LinkList s ；If(T)Inorder(T >lchild)；If (!T >lchild)&&(!T

24、 >rchild) s=(ListNode*)malloc(sizeof(ListNode)； s >data=T >data；s >n ext=Leafhead;Leafhead=sInorder(T >rchild)；對于如下所示的二叉樹(1畫出執(zhí)行上述算法后所建立的結(jié)構(gòu)；(2)說明該算法的功能。五、算法設(shè)計(jì)題(本題共10分)34. 閱讀下列函數(shù)arrange()int arran ge(i nt a,i nt 1,i nt h,i nt x)/1和h分別為數(shù)據(jù)區(qū)的下界和上界int i,j,t ;i=1 ； j=h ； while(i<j) while(

25、i<j && aj>=x)j-； while(i<j && aj>=x)i+；if(i<j) t=aj ； aj=ai ； ai=t ； if(ai<x) return i ； else return i 1 ；(1) 寫出該函數(shù)的功能；(2) 寫一個(gè)調(diào)用上述函數(shù)實(shí)現(xiàn)下列功能的算法：對一整型數(shù)組bn中的元素進(jìn) 行重新排列，將所有負(fù)數(shù)均調(diào)整到數(shù)組的低下標(biāo)端，將所有正數(shù)均調(diào)整到數(shù)組的高下標(biāo)端，若有零值，則置于兩者之間，并返回?cái)?shù)組中零元素的個(gè) 數(shù)。數(shù)據(jù)結(jié)構(gòu)試題參考答案1. D 2.B3.C6.A7.C8,D11.D12.C1、填空題

26、（本大題共10小題,每小題單項(xiàng)選擇題（本大題共16存儲（或存儲結(jié)構(gòu)）18.進(jìn)棧和退棧4.B5.D9,A10.C13.D14.C 15.B2分，共20分）17.p> n ext-> n ext19. 1220. a4,821. 38422. abefcdg15小題，每小題2分，共30 分）23.快速排序、堆排序、希爾排序24.2、解答題（本大題共4小題，每小題26.25多關(guān)鍵字5分，共20分）圖127.28.該圖的圖形為:深度優(yōu)先遍歷序列為：abdce廣度優(yōu)先遍歷序列為：abedc29. (1)對關(guān)鍵字35、20、33和48進(jìn)行查找的比較次數(shù)為3、2、1、1；人乩 32112 9(2

27、)平均查找長度55四、算法閱讀題(本大題共4小題，每小題5分，共20分)30. S1=S1- >next s2=s2 >next s2(或 s2!=NULL 或 s2&&!s1) s1(或 s1!=NULL 或 s1&&!s2) return 031. (1)查詢鏈表的尾結(jié)點(diǎn)(2) 將第一個(gè)結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)點(diǎn)(3) 返回的線性表為(a2,a3,an,a1)32. (i + 1)%2(或 1 i) Q >reari(Q >reari + )%Maxsize33.(1) LeafheadFHGDAint f(int b,in

28、t n)in t p,q ；p=arra nge(b,0,n- 1,1)； q= arran ge(b,0,p,0);return p q；(2)中序遍歷二叉樹，按遍歷序列中葉子結(jié)點(diǎn)數(shù)據(jù)域的值構(gòu)建一個(gè)以Leafhead為頭指針的逆序單鏈表(或按二叉樹中葉子結(jié)點(diǎn)數(shù)據(jù)自右至 左鏈接成一個(gè)鏈表)。五、算法設(shè)計(jì)題(本題共10分)34. (1)該函數(shù)的功能是：調(diào)整整數(shù)數(shù)組 a中的元素并返回分界值i，使所 有vx的元素均落在a1.i上，使所有x的元素均落在ai + 1.h上。(2) int f(int b,int n)或in t p,q；p=arra nge(b,0,n-1,0)；q= arran ge(

29、b,p+1,n-1,1)； return q p；一、選擇題(20分)1 .組成數(shù)據(jù)的基本單位是()。(D)數(shù)據(jù)變量(A)數(shù)據(jù)項(xiàng) (B)數(shù)據(jù)類型(C)數(shù)據(jù)元素2設(shè)數(shù)據(jù)結(jié)構(gòu) A=(D , R)，其中 D=1 , 2, 3, 4 , R=r , r=<1 , 2>, <2, 3>, <3， 4>， <4， 1>，則數(shù)據(jù)結(jié)構(gòu) A 是( )。(A) 線性結(jié)構(gòu)(B) 樹型結(jié)構(gòu)(C) 圖型結(jié)構(gòu)(D) 集合3數(shù)組的邏輯結(jié)構(gòu)不同于下列()的邏輯結(jié)構(gòu)。(A) 線性表(B) 棧(C) 隊(duì)列(D) 樹4. 二叉樹中第i(i羽層上的結(jié)點(diǎn)數(shù)最多有()個(gè)。ii-1(A) 2

30、i(B) 2i(C) 2i-1(D) 2i-15. 設(shè)指針變量p指向單鏈表結(jié)點(diǎn)A ,則刪除結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B需要的操作為( )。(B) p=p->next(D) p->next=p(A) p->next=p->next->next(C) p=p->next->next6. 設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素 E1、E2、E3、E4、E5和E6依次通 過棧S, 個(gè)元素出棧后即進(jìn)入隊(duì)列 Q,若6個(gè)元素出列的順序?yàn)镋2、E4、E3、E6、E5和E1,則棧S的容量至少應(yīng)該是()。(A) 6(B) 4(C) 3(D) 27. 將 10階對稱矩陣壓縮存儲到一維數(shù)組

31、 A 中,則數(shù)組 A 的長度最少為( )。(A) 100(B) 40(C) 55(D) 808. 設(shè)結(jié)點(diǎn) A 有 3 個(gè)兄弟結(jié)點(diǎn)且結(jié)點(diǎn) B 為結(jié)點(diǎn) A 的雙親結(jié)點(diǎn),則結(jié)點(diǎn) B 的度數(shù) 數(shù)為( )。(A) 3(B) 4(C) 5(D) 19. 根據(jù)二叉樹的定義可知二叉樹共有()種不同的形態(tài)(C) 6(D) 7)的空間復(fù)雜度最大。(C) 堆排序(D) 希爾排序(A) 4(B) 510.10. 設(shè)有以下四種排序方法,則(A) 冒泡排序(B) 快速排序 二、填空題 (30 分)1. 1.設(shè)順序循環(huán)隊(duì)列Q0: m-1的隊(duì)頭指針和隊(duì)尾指針分別為 F和R,其中隊(duì)頭指針F指向當(dāng)前隊(duì)頭元素的前一個(gè)位置，隊(duì)尾指針

32、R指向當(dāng)前隊(duì)尾元素 所在的位置,則出隊(duì)列的語句為 F =;。2. 2.設(shè)線性表中有n個(gè)數(shù)據(jù)元素，則在順序存儲結(jié)構(gòu)上實(shí)現(xiàn)順序查找的平均時(shí)間復(fù)雜度為 ,在鏈?zhǔn)酱鎯Y(jié)構(gòu)上實(shí)現(xiàn)順序查找的平均時(shí)間復(fù)雜度為 。3. 3.設(shè)一棵二叉樹中有n個(gè)結(jié)點(diǎn)，則當(dāng)用二叉鏈表作為其存儲結(jié)構(gòu)時(shí)，該二叉鏈表中共有 個(gè)指針域, 個(gè)空指針域。4. 4.設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)B, 則 在 結(jié) 點(diǎn) A 的 后 面 插 入 結(jié) 點(diǎn) B 的 操 作 序 列 為5. 5.設(shè)無向圖G中有n個(gè)頂點(diǎn)和e條邊，則其對應(yīng)的鄰接表中有 個(gè)表頭結(jié)點(diǎn)和表結(jié)點(diǎn)。6. 6.設(shè)無向圖G中有n個(gè)頂點(diǎn)e條邊，所有頂點(diǎn)的度數(shù)之和為

33、 m,則e和m有 系。7. 7.設(shè)一棵二叉樹的前序遍歷序列和中序遍歷序列均為ABC，則該二叉樹的后序遍歷序歹寸為。8. 8.設(shè)一棵完全二叉樹中有 21個(gè)結(jié)點(diǎn)，如果按照從上到下、從左到右的順序從1開始順序編號，則編號為8的雙親結(jié)點(diǎn)的編號是,編號為8的左孩子結(jié)點(diǎn)的編號是 。9. 9.下列程序段的功能實(shí)現(xiàn)子串t在主串s中位置的算法，要求在下劃線處 填上正確語句。int in dex(char s , char t)i=j=O；while(i<strlen(s) && jvstrlen(t) if(si=tj)i=i+l; j=j+l;elsei=;j=;if (j=strle

34、n( t)return(i-strle n( t);else return (-1);10. 10.設(shè)一個(gè)連通圖G中有n個(gè)頂點(diǎn)e條邊，則其最小生成樹上有 條邊。、應(yīng)用題(30 分)1. 設(shè)完全二叉樹的順序存儲結(jié)構(gòu)中存儲數(shù)據(jù)ABCDE，要求給出該二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)并給出該二叉樹的前序、中序和后序遍歷序列。2. 設(shè)給定一個(gè)權(quán)值集合 W=(3，5, 7, 9, 11)，要求根據(jù)給定的權(quán)值集合構(gòu)造 棵哈夫曼樹并計(jì)算哈夫曼樹的帶權(quán)路徑長度 WPL。3. 設(shè)一組初始記錄關(guān)鍵字序列為(19, 21, 16, 5, 18, 23), 要求給出以19為基準(zhǔn)的一趟快速排序結(jié)果以及第 2趟直接 選擇排序后的結(jié)果。

35、4. 設(shè)一組初始記錄關(guān)鍵字集合為(25, 10, 8, 27, 32, 68), 散列表的長度為8,散列函數(shù)H(k)=k mod 7 ,要求分別 用線性探測和鏈地址法作為解決沖突的方法設(shè)計(jì)哈希表。5. 設(shè)無向圖G (所右圖所示)，要求給出該圖的深度優(yōu)先 和廣度優(yōu)先遍歷的序列并給出該圖的最小生成樹。四、算法設(shè)計(jì)題(20分)1. 1.設(shè)計(jì)判斷單鏈表中結(jié)點(diǎn)是否關(guān)于中心對稱算法2. 2. 設(shè)計(jì)在鏈?zhǔn)酱鎯Y(jié)構(gòu)上建立一棵二叉樹的算法。3. 3. 設(shè)計(jì)判斷一棵二叉樹是否是二叉排序樹的算法。數(shù)據(jù)結(jié)構(gòu)試卷參考答案一、選擇題1.C2.C3.D4.C5.A6.C7.C8.B9.B10.B二、填空題1. 1. (F+

36、1) % m2. 2. O(n)，O(n)3. 3. 2n，n+14. 4. s->next=p->next; s->next=s5. 5. n, 2e6. 6. m=2e7. 7. CBA8. 8. 4，169. 9. i-j+1 ，0h010. 10. n-1 0h1 8三、應(yīng)用題h11. 1.鏈?zhǔn)酱鎯Y(jié)構(gòu)略，前序 ABDEC，中序DBEAC，后序dEbCA02. 2.哈夫曼樹略， WPL=78h425323. 3.(18,5,16,19,201,213)， 2(5，316，4 215，196，178，23)h5684. 4.線性探測： 810 25 322768鏈地址法

37、： h6275. 5. 深度：125364，廣度：123456，最小生成樹 T 的邊集為 E=(1 ， 4)， (1，3)， (3， 5)， (5， 6)， (5,6)四、算法設(shè)計(jì)題1. 1. 設(shè)計(jì)判斷單鏈表中結(jié)點(diǎn)是否關(guān)于中心對稱算法。typedef struct int s100; int top; sqstack;int lklistsymmetry(lklist *head)sqstack stack; stack.top= -1; lklist *p;for(p=head;p!=0;p=p->next) stack.top+; stack.sstack.top=p->dat

38、a;for(p=head;p!=0;p=p->next) if (p->data=stack.sstack.top) stack.top=stack.top-1; else return(0);return(1);2. 2. 設(shè)計(jì)在鏈?zhǔn)酱鎯Y(jié)構(gòu)上建立一棵二叉樹的算法。typedef char datatype;typedef struct node datatype data; struct node *lchild,*rchild; bitree; void createbitree(bitree *&bt)char ch; scanf("%c",&a

39、mp;ch);if(ch='#') bt=0; return; bt=(bitree*)malloc(sizeof(bitree); bt->data=ch; createbitree(bt->lchild); createbitree(bt->rchild);3. 設(shè)計(jì)判斷一棵二叉樹是否是二叉排序樹的算法。int minnum=-32768,flag=1;typedef struct nodeint key; struct node *lchild,*rchild;bitree;void inorder(bitree *bt)if (bt!=0)inorde

40、r(bt->lchild); if(minnum>bt->key)flag=0; minnum=bt->key; inorder(bt->rchild);一、單選題(每小題 2 分，共 8 分)1、1、在一個(gè)長度為 n 的順序線性表中順序查找值為 x 的元素時(shí)，查找成功時(shí)的 平均查找長度（即 x 與元素的平均比較次數(shù)，假定查找每個(gè)元素的概率 都相等）為 （ ）。A n B n/2 C （n+1）/2 D （n-1）/22、 2、在一個(gè)單鏈表中，若q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q與p之間 插入一個(gè)s所指的結(jié)點(diǎn)，則執(zhí)行（）。As link=p f link;p

41、link=s ；Bp link=s;slink=q;Cplink=slink;slink=p;Dq link=s;slink =p;3、3、 棧的插入和刪除操作在（ ）進(jìn)行。A 棧頂 B 棧底 C 任意位置 D 指定位置4、4、 由權(quán)值分別為 11，8，6，2，5 的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的 帶權(quán)路徑長度為（ ）A 24 B 71 C 48D 53二、二、 填空題（每空 1 分，共 32 分）1、 1、數(shù)據(jù)的邏輯結(jié)構(gòu)被分為 、 、 和四種。2、 2、一種抽象數(shù)據(jù)類型包括 和兩個(gè)部分。3、 3、在下面的數(shù)組a中鏈接存儲著一個(gè)線性表，表頭指針為ao.next，則該線性表為 。_a 01234

42、 5 6 7 86056423874254376201data n ext4、4、在以HL為表頭指針的帶表頭附加結(jié)點(diǎn)的單鏈表和循環(huán)單鏈表中，判斷鏈表為空的條件分別為和。5、5、用具有n個(gè)元素的一維數(shù)組存儲一個(gè)循環(huán)隊(duì)列，則其隊(duì)首指針總是指向隊(duì)首元素的 該循環(huán)隊(duì)列的最大長度為 。6、 6、當(dāng)堆棧采用順序存儲結(jié)構(gòu)時(shí)，棧頂元素的值可用表示；當(dāng)堆棧采用鏈接存儲結(jié)構(gòu)時(shí)，棧頂元素的值可用 示。7、 7、一棵高度為 5的二叉樹中最少含有 結(jié)點(diǎn)，最多含有結(jié)點(diǎn)；一棵高度為5的理想平衡樹中，最少含有 結(jié)點(diǎn)，最多含有結(jié)點(diǎn)。8 8在圖的鄰接表中，每個(gè)結(jié)點(diǎn)被稱為 ，通常它包含三個(gè)域：_k日 一日一日疋；二二二是 三疋 0

43、9、9、在一個(gè)索引文件的索引表中，每個(gè)索引項(xiàng)包含對應(yīng)記錄的 和項(xiàng)數(shù)據(jù)。10、10、假定一棵樹的廣義表表示為 A （B （C，D （ E，F(xiàn)，G），H（I，J），則樹中所含的結(jié)點(diǎn)數(shù)為 ，樹的深度為,樹的度為,結(jié)點(diǎn)H的雙親結(jié)點(diǎn)為，孩子結(jié)點(diǎn)為11、11、在堆排序的過程中，對任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為，整個(gè)堆排序過程的時(shí)間復(fù)雜度為 012、12、在對m階的B_樹插入元素的過程中，每向一個(gè)結(jié)點(diǎn)插入一個(gè)索引項(xiàng)（葉子結(jié)點(diǎn)中的索引項(xiàng)為關(guān)鍵字和空指針）后，若該結(jié)點(diǎn)的索 引項(xiàng)數(shù)等于 ，則必須把它分裂為 結(jié)點(diǎn)。三、運(yùn)算題（每小題6分，共24分）1、1、已知一組記錄的排序碼為（46, 79，56，38, 4

44、0，80, 95，24），寫 出對其進(jìn)行快速排序的每一次劃分結(jié)果。2、2、一個(gè)線性表為B= （12，23，45，57，20，03，78，31，15，36），設(shè)散列表為HT0.12，散列函數(shù)為H （key） = key % 13并用線性探查法解 決沖突，請畫出散列表，并計(jì)算等概率情況下查找成功的平均查找長度。3、3、已知一棵二叉樹的前序遍歷的結(jié)果序列是ABECKFGHIJ，中序遍歷的結(jié)果是EBCDAFHIGJ，試寫出這棵二叉樹的后序遍歷結(jié)果。4、4、已知一個(gè)圖的頂點(diǎn)集 V各邊集G如下：V = 0,1, 2, 3, 4, 5, 6, 7, 8, 9;E = (0 ,1),(0 ,4),(1,2)

45、,(1 ,7) ,(2 ,8),(3 , 4),(3 , 8), (5 , 6),(5 ,8),(5 ,9),(6 ,7),(7 ,8),(8 ,9) 當(dāng)它用鄰接矩陣表示和鄰接表表示時(shí)，分別寫出從頂點(diǎn)Vo出發(fā)按深度優(yōu)先搜索遍歷得到的頂點(diǎn)序列和按廣度優(yōu)先搜索遍歷等到的頂點(diǎn)序列。假定每個(gè)頂點(diǎn)鄰接表中的結(jié)點(diǎn)是按頂點(diǎn)序號從大到小的次序鏈接的。圖深度優(yōu)先序列廣度優(yōu)先序列鄰接矩陣表示時(shí)鄰接表表示時(shí)四、四、閱讀算法，回答問題(每小題8分，共16分)1、假定從鍵盤上輸入一批整數(shù),依次為：78 63 45 30 91 34- 1，請寫出輸出結(jié)果。# in elude < iostream.h># i

46、n elude < stdlib.h >con sst int staekmaxsize = 30;typedef int elemtype;struct stack elemtype stack stackmaxsize;int top;；# in clude “ stack.h”Void ma in ()stack a;in itstack(a);int x;cin >>x;while (x! = -1) push (a, x );cin >>x;while (!stackempty (a) cout <<pop (a) <<” cout <<end1; 該算法的輸出結(jié)果為：2、閱讀以下二叉樹操作算法，指出該算法的功能。 Template <calss t