寧波大學數據結構試題庫

《寧波大學數據結構試題庫》由會員分享，可在線閱讀，更多相關《寧波大學數據結構試題庫（103頁珍藏版）》請在裝配圖網上搜索。

1、精選優(yōu)質文檔-----傾情為你奉上 一、?????????????????? 單選題（每題 2 分，共20分） 1. 1.???? 對一個算法的評價，不包括如下（B ）方面的內容。 A．健壯性和可讀性 B．并行性 C．正確性 D．時空復雜度 2. 2.???? 在帶有頭結點的單鏈表HL中，要向表頭插入一個由指針p指向的結點，則執(zhí)行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL;

2、 D. HL=p; p->next=HL; 3. 3.???? 對線性表，在下列哪種情況下應當采用鏈表表示？( ) A.經常需要隨機地存取元素 B.經常需要進行插入和刪除操作 C.表中元素需要占據一片連續(xù)的存儲空間 D.表中元素的個數不變 4. 4.???? 一個棧的輸入序列為1 2 3，則下列序列中不可能是棧的輸出序列的是( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.???? AOV網是一種（ ）。

3、 A．有向圖 B．無向圖 C．無向無環(huán)圖 D．有向無環(huán)圖 6. 6.???? 采用開放定址法處理散列表的沖突時，其平均查找長度（ ）。 A．低于鏈接法處理沖突 B. 高于鏈接法處理沖突 C．與鏈接法處理沖突相同 D．高于二分查找 7. 7.???? 若需要利用形參直接訪問實參時，應將形參變量說明為（ ）參數。 A．值 B．函數 C．指針 D．引用 8. 8.???? 在稀疏矩陣的帶行指針向量的鏈接存儲中，每個單鏈表中的結點都具有相同的（ ）。 A．行號

4、 B．列號 C．元素值 D．非零元素個數 9. 9.???? 快速排序在最壞情況下的時間復雜度為（ ）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10. 10. 從二叉搜索樹中查找一個元素時，其時間復雜度大致為( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) ? 二、 二、?????????????????? 運算題（每題 6 分，共24分） 1. 1.??????? 數據結構是指數據及其相互之間的

5、______________。當結點之間存在M對N（M：N）的聯系時，稱這種結構為_____________________。 2. 2.??????? 隊列的插入操作是在隊列的___尾______進行，刪除操作是在隊列的____首______進行。 3. 3.??????? 當用長度為N的數組順序存儲一個棧時，假定用top==N表示?？?，則表示棧滿的條件是___top==0___(要超出才為滿)_______________。 4. 4.??????? 對于一個長度為n的單鏈存儲的線性表，在表頭插入元素的時間復雜度為_________，在表尾插入元素的時間復雜度為___________

6、_。 5. 5.??????? 設W為一個二維數組，其每個數據元素占用4個字節(jié)，行下標i從0到7 ，列下標j從0到3 ，則二維數組W的數據元素共占用＿_____＿個字節(jié)。W中第6 行的元素和第4 列的元素共占用＿_______＿個字節(jié)。若按行順序存放二維數組W，其起始地址為100，則二維數組元素W[6，3]的起始地址為＿________＿。 6. 6.??????? 廣義表A= (a,(a,b),((a,b),c)),則它的深度為____________，它的長度為____________。 7. 7.??????? 二叉樹是指度為2的____________________樹。一棵結點

7、數為N的二叉樹，其所有結點的度的總和是_____________。 8. 8.??????? 對一棵二叉搜索樹進行中序遍歷時，得到的結點序列是一個______________。對一棵由算術表達式組成的二叉語法樹進行后序遍歷得到的結點序列是該算術表達式的__________________。 9. 9.??????? 對于一棵具有n個結點的二叉樹，用二叉鏈表存儲時，其指針總數為_____________個，其中_______________個用于指向孩子，_________________個指針是空閑的。 10. 10.??? 若對一棵完全二叉樹從0開始進行結點的編號，并按此編號把它順序存

8、儲到一維數組A中，即編號為0的結點存儲到A[0]中。其余類推，則A[ i ]元素的左孩子元素為________,右孩子元素為_______________，雙親元素為____________。 11. 11.??? 在線性表的散列存儲中，處理沖突的常用方法有________________________和_____________________________兩種。 12. 12.??? 當待排序的記錄數較大，排序碼較隨機且對穩(wěn)定性不作要求時，宜采用_______________排序；當待排序的記錄數較大，存儲空間允許且要求排序是穩(wěn)定時，宜采用_____________________

9、___排序。 ? 三、 三、?????????????????? 運算題（每題6分，共24分） 1. 1.??????? 已知一個6′5稀疏矩陣如下所示， ? ? ? 試： （1） （1）??????? 寫出它的三元組線性表； （2） （2）??????? 給出三元組線性表的順序存儲表示。 2. 2.??????? 設有一個輸入數據的序列是 { 46, 25, 78, 62, 12, 80 }, 試畫出從空樹起，逐個輸入各個數據而生成的二叉搜索樹。 3. 3.??????? 對于圖6所示的有向圖若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結點都是按照終點序號從

10、小到大的次序鏈接的，試寫出： (1) 從頂點①出發(fā)進行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹； (2) 從頂點②出發(fā)進行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹； 4. 4.??????? 已知一個圖的頂點集V和邊集E分別為： 圖6 V={1,2,3,4,5,6,7}; E={<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>}; 若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結點都是按照終點序號從小到大的次序鏈接的，按主教材中介紹的拓樸排序算法進行排序，試給出得到的拓樸排序的序列。 ?

11、 四、 四、?????????????????? 閱讀算法（每題7分，共14分） 1. 1.???????????????????? int Prime(int n) { int i=1; int x=(int) sqrt(n); while (++i<=x) if (n%i==0) break; if (i>x) return 1; else return 0; } (1) (1)???? 指出該算法的功能； (2) (2)???? 該算法的時間復雜度是多少？ 2. 2.??????????????????

12、?? 寫出下述算法的功能： void AJ(adjlist GL, int i, int n) { Queue Q; InitQueue(Q); cout<

13、 { int j=p->adjvex; if(!visited[j]) { cout<next; } } } ? 五、 五、?????????????????? 算法填空（共8分） 如下為二分查找的非遞歸算法，試將

14、其填寫完整。 Int Binsch(ElemType A[ ],int n,KeyType K) { int low=0; int high=n-1; while (low<=high) { int mid=_______________________________； if (K==A[mid].key) return mid; //查找成功，返回元素的下標 else if (K<[mid].key) ______________________________________; //在左子表上繼續(xù)查找 else _

15、_________________________________; //在右子表上繼續(xù)查找 } return -1; //查找失敗，返回-1 } ? 六、 六、?????????????????? 編寫算法（共8分） HL是單鏈表的頭指針，試寫出刪除頭結點的算法。 ElemType DeleFront(LNode * & HL) ? ? 參考答案 一、 一、???????????????????? 單選題（每題2分，共20分） 1.B 2.A 3.B 4.C 5.D 6.B 7.D 8.A 9.D 10.C 二、

16、 二、???????????????????? 填空題（每空1分，共26分） 1. 1.???????? 聯系 圖（或圖結構） 2. 2.???????? 尾 首 3. 3.???????? top==0 4. 4.???????? O（1） O（n） 5. 5.???????? 128 44 108 6. 6.???????? 3 3 7. 7.???????? 6 5 5 1 5 1 3 2 -1 4 5 -2 5 1 5 6 3 7 圖7 有序 n-1 8. 8.????????

17、 有序序列 后綴表達式（或逆波蘭式） 9. 9.???????? 2n n-1 n+1 10. 10.???? 2i+1 2i+2 (i-1)/2 11. 11.???? 開放定址法 鏈接法 12. 12.???? 快速 歸并 三、 三、???????????????????? 運算題（每題6分，共24分） 1. 1.???????? （1） ((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7)) (3分) （2） 三元組線性表的順序存儲表示如圖7示。 2. 2.??

18、?????? 圖8 如圖8所示。 3. 3.???????? DFS：????… BFS：???…? 4. 4.???????? 拓樸排序為： 4 3 6 5 7 2 1 四、 四、????????????????????? 閱讀算法（每題7分，共14分） 1. 1.???????? (1) 判斷n是否是素數（或質數） （2）O（） 2. 2.???????? 功能為：從初始點vi出發(fā)廣度優(yōu)先搜索由鄰接表GL所表示的圖。 五、 五、????????????????????? 算法填空（8 分） (low+high

19、)/2 high=mid-1 low=mid+1 六、 六、????????????????????? 編寫算法（8分） ElemType DeleFront(LNode * & HL) { if (HL==NULL){ cerr<<"空表"<next; ElemType temp=p->data; delete p; return temp; } ? ? 一、 一、?????????????????? 單選題（每題

20、2 分，共20分） 1. 1.???? 棧和隊列的共同特點是( )。 A.只允許在端點處插入和刪除元素 B.都是先進后出 C.都是先進先出 D.沒有共同點 2. 2.???? 用鏈接方式存儲的隊列，在進行插入運算時( ). A. 僅修改頭指針 　 B. 頭、尾指針都要修改 C. 僅修改尾指針 D.頭、尾指針可能都要修改 3. 3.???? 以下數據結構中哪一個是非線性結構？( ) A. 隊列 　　 B. 棧 C. 線性表 　　 D

21、. 二叉樹 4. 4.???? 設有一個二維數組A[m][n]，假設A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每個元素占一個空間，問A[3][3](10)存放在什么位置？腳注(10)表示用10進制表示。 A．688 B．678 C．692 D．696 5. 5.???? 樹最適合用來表示( )。 A.有序數據元素 B.無序數據元素 C.元素之間具有分支層次關系的數據 D.元素之間無聯系的數據 6. 6.???

22、? 二叉樹的第k層的結點數最多為( ). A．2k-1 B.2K+1 C.2K-1 　　　D. 2k-1 7. 7.???? 若有18個元素的有序表存放在一維數組A[19]中，第一個元素放A[1]中，現進行二分查找，則查找A［3］的比較序列的下標依次為( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 8. 8.???? 對n個記錄的文件進行快速排序，所需要的輔助存儲空間大致為 A. O（1） 　　B. O（n）　　 C. O（1og2

23、n） D. O（n2） 9. 9.???? 對于線性表（7，34，55，25，64，46，20，10）進行散列存儲時，若選用H（K）=K %9作為散列函數，則散列地址為1的元素有（ ）個， A．1 B．2 C．3 D．4 10. 10. 設有6個結點的無向圖，該圖至少應有( )條邊才能確保是一個連通圖。 A.5 B.6 C.7 D.8 ? 二、 二、?????????????????? 填空題（每空1分，共26分） 1. 1.??????? 通常

24、從四個方面評價算法的質量：_________、_________、_________和_________。 2. 2.??????? 一個算法的時間復雜度為(n3+n2log2n+14n)/n2，其數量級表示為________。 3. 3.??????? 假定一棵樹的廣義表表示為A（C，D（E，F，G），H（I，J）），則樹中所含的結點數為__________個，樹的深度為___________，樹的度為_________。 4. 4.??????? 后綴算式9 2 3 +- 10 2 / -的值為__________。中綴算式（3+4X）-2Y/3對應的后綴算式為_______

25、________________________。 5. 5.??????? 若用鏈表存儲一棵二叉樹時，每個結點除數據域外，還有指向左孩子和右孩子的兩個指針。在這種存儲結構中，n個結點的二叉樹共有________個指針域，其中有________個指針域是存放了地址，有________________個指針是空指針。 6. 6.??????? 對于一個具有n個頂點和e條邊的有向圖和無向圖，在其對應的鄰接表中，所含邊結點分別有_______個和________個。 7. 7.??????? AOV網是一種___________________的圖。 8. 8.??????? 在一個具有n個

26、頂點的無向完全圖中，包含有________條邊，在一個具有n個頂點的有向完全圖中，包含有________條邊。 9. 9.??????? 假定一個線性表為(12,23,74,55,63,40)，若按Key % 4條件進行劃分，使得同一余數的元素成為一個子表，則得到的四個子表分別為____________________________、___________________、_______________________和__________________________。 10. 10.??? 向一棵B_樹插入元素的過程中，若最終引起樹根結點的分裂，則新樹比原樹的高度_________

27、__。 11. 11.??? 在堆排序的過程中，對任一分支結點進行篩運算的時間復雜度為________，整個堆排序過程的時間復雜度為________。 12. 12.??? 在快速排序、堆排序、歸并排序中，_________排序是穩(wěn)定的。 ? 三、 三、?????????????????? 運算題（每題 6 分，共24分） 1. 1.??????? 在如下數組A中鏈接存儲了一個線性表，表頭指針為A [0].next，試寫出該線性表。 A 0 1 2 3 4 5 6 7 data ?

28、 60 50 78 90 34 ? 40 next 3 5 7 2 0 4 ? 1 2. 2.??????? 圖10 請畫出圖10的鄰接矩陣和鄰接表。 3. 3.??????? 已知一個圖的頂點集V和邊集E分別為： V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15, (3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}; 用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條

29、邊。 4. 4.??????? 畫出向小根堆中加入數據4, 2, 5, 8, 3時，每加入一個數據后堆的變化。 ? 四、 四、?????????????????? 閱讀算法（每題7分，共14分） 1. 1.???? LinkList mynote(LinkList L) {//L是不帶頭結點的單鏈表的頭指針 if(L&&L->next){ q=L；L=L－>next；p=L； S1： while(p－>next) p=p－>next； S2： p

30、－>next=q；q－>next=NULL； } return L； } 請回答下列問題： （1）說明語句S1的功能； （2）說明語句組S2的功能； （3）設鏈表表示的線性表為（a1,a2, …,an）,寫出算法執(zhí)行后的返回值所表示的線性表。 2. 2.???? void ABC(BTNode * BT) { if BT { ABC (BT->left); ABC (BT->right);

31、 cout<data<<' '; } } 該算法的功能是： ? 五、 五、?????????????????? 算法填空（共8分） 二叉搜索樹的查找——遞歸算法: bool Find(BTreeNode* BST,ElemType& item) { if (BST==NULL) return false; //查找失敗 else { if (item==BST->data){ item=BST->data;//查找成功

32、 return ___________;} else if(itemdata) return Find(______________,item); else return Find(_______________,item); }//if } ? 六、 六、?????????????????? 編寫算法（共8分） 統(tǒng)計出單鏈表HL中結點的值等于給定值X的結點數。 int CountX(LNode* HL,ElemType x) ?

33、? 參考答案 一、 一、????????????????????? 單選題（每題2分，共20分） 1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A 二、 二、????????????????????? 填空題（每空1分，共26分） 1. 1.???? 正確性 易讀性 強壯性 高效率 2. 2.???? O(n) 3. 3.???? 9 3 3 4. 4.???? -1 3 4 X * + 2 Y * 3 / - 5. 5.???? 2n n-1 n+1 6. 6.?

34、??? e 2e 7. 7.???? 有向無回路 8. 8.???? n(n-1)/2 n(n-1) 9. 9.???? （12，40） （ ） （74） （23,55，63） 10. 10.? 增加1 11. 11.? O(log2n) O(nlog2n) 12. 12.? 歸并 三、 三、????????????????????? 運算題（每題6分，共24分） 1. 1.???? 線性表為：（78，50，40，60，34，90） 2. 2.???? 鄰接矩陣： 鄰接表如圖11所示： 圖11 3. 3.???? 用克魯

35、斯卡爾算法得到的最小生成樹為： (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20 4. 4.???? 見圖12 4 4 4 4 4 2 2 2 5 5 2 8 5 2 8 3 4 5 2 8 4 3 ? ? ? ? ? ? ? ? ? ? 圖12 四、 四、????????????????????? 閱讀算法（每題7分，共14分） 1. 1.???? （1）查詢鏈

36、表的尾結點 （2）將第一個結點鏈接到鏈表的尾部，作為新的尾結點 （3）返回的線性表為（a2,a3,…,an,a1） 2. 2.???? 遞歸地后序遍歷鏈式存儲的二叉樹。 五、 五、????????????????????? 算法填空（每空2分，共8 分） true BST->left BST->right 六、 六、????????????????????? 編寫算法（8分） int CountX(LNode* HL,ElemType x) { int i=0; LNode* p=HL;//i為計數器 while(p!=N

37、ULL) { if (P->data==x) i++; p=p->next; }//while, 出循環(huán)時i中的值即為x結點個數 return i; }//CountX ? ? ? 一、 一、??????????? 單選題（每小題2分，共8分） 1、 1、在一個長度為n的順序線性表中順序查找值為x的元素時，查找成功時的平均查找長度（即x與元素的平均比較次數，假定查找每個元素的概

38、率都相等）為 ( )。 A n B n/2 C (n+1)/2 D (n-1)/2 2、 2、在一個單鏈表中,若q所指結點是p所指結點的前驅結點,若在q與p之間插入一個s所指的結點,則執(zhí)行( )。 A s→link=p→link; p→link=s; B p→link=s; s→link=q; C p→link=s→link; s→link=p; D q →link=s; s→link =p; 3、 3、????? 棧的插入和刪除操作在（ ）進行。 A 棧頂

39、 B 棧底 C 任意位置 D 指定位置 4、 4、????? 由權值分別為11，8，6，2，5的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為（ ） A 24 B 71 C 48 D 53 二、 二、??????????? 填空題（每空1分，共32分） 1、 1、數據的邏輯結構被分為__________、 ___________ 、________和________四種。 2、 2、一種抽象數據類型包括______________和_____________兩個部分。 3、 3、在下面的數組a

40、中鏈接存儲著一個線性表，表頭指針為a[o].next，則該線性表為_________________________________________________。 a 0 1 2 3 4 5 6 7 8 ? 60 56 42 38 ? 74 25 ? 4 3 7 6 2 0 1 ? data next ? 4、 4、在以HL為表頭指針的帶表頭附加結點的單鏈表和循環(huán)單鏈表中，判斷鏈表為空的條件

41、分別為________________和____________________。 5、 5、用具有n個元素的一維數組存儲一個循環(huán)隊列，則其隊首指針總是指向隊首元素的___________，該循環(huán)隊列的最大長度為__________。 6、 6、當堆棧采用順序存儲結構時，棧頂元素的值可用———————表示；當堆棧采用鏈接存儲結構時，棧頂元素的值可用_______________表示。 7、 7、一棵高度為5的二叉樹中最少含有_________個結點，最多含有________個結點； 一棵高度為5的理想平衡樹中，最少含有_________個結點，最多含有_________個結點。 8、

42、 8、在圖的鄰接表中，每個結點被稱為____________，通常它包含三個域：一是_____________；二是___________；三是_____________。 9、 9、在一個索引文件的索引表中，每個索引項包含對應記錄的_________和___________兩項數據。 10、 10、??????????? 假定一棵樹的廣義表表示為A（B（C，D（E，F，G），H（I，J））），則樹中所含的結點數為_________個，樹的深度為_________,樹的度為________, 結點H的雙親結點為________,孩子結點為_______________ 。 11、 11、

43、??????????? 在堆排序的過程中，對任一分支結點進行篩運算的時間復雜度為_________,整個堆排序過程的時間復雜度為________________。 12、 12、??????????? 在對m階的B_樹插入元素的過程中，每向一個結點插入一個索引項（葉子結點中的索引項為關鍵字和空指針）后，若該結點的索引項數等于______個，則必須把它分裂為_______個結點。 ? 三、 三、??????????? 運算題（每小題6分，共24分） 1、 1、已知一組記錄的排序碼為（46，79，56，38，40，80, 95，24），寫出對其進行快速排序的每一次劃分結果。 ? 2、

44、 2、一個線性表為B=（12，23，45，57，20，03，78，31，15，36），設散列表為HT[0..12]，散列函數為H（key）= key % 13并用線性探查法解決沖突，請畫出散列表，并計算等概率情況下查找成功的平均查找長度。 ? 3、 3、已知一棵二叉樹的前序遍歷的結果序列是ABECKFGHIJ，中序遍歷的結果是EBCDAFHIGJ，試寫出這棵二叉樹的后序遍歷結果。 ? ? 4、 4、已知一個圖的頂點集V各邊集G如下： V = {0，1，2，3，4，5，6，7，8，9}； E = {（0，1），（0，4），（1，2），（1，7），（2，8），（3，4），（3 ，8）

45、，（5，6），（5，8），（5，9），（6，7），（7，8），（8，9）} 當它用鄰接矩陣表示和鄰接表表示時，分別寫出從頂點V0出發(fā)按深度優(yōu)先搜索遍歷得到的頂點序列和按廣度優(yōu)先搜索遍歷等到的頂點序列。 假定每個頂點鄰接表中的結點是按頂點序號從大到小的次序鏈接的。 圖 深度優(yōu)先序列 廣度優(yōu)先序列 鄰接矩陣表示時 ? ? 鄰接表表示時 ? ? ? ? ? ? 四、 四、??????????? 閱讀算法，回答問題（每小題8分，共16分） ? 1、假定從鍵盤上輸入一批整數，依次為

46、：78 63 45 30 91 34 –1，請寫出輸出結果。 # include < iostream.h> # include < stdlib.h > consst int stackmaxsize = 30; typedef int elemtype; struct stack { elemtype stack [stackmaxsize]; int top; }; # include “stack.h” Void main ( ) { stack a; initstack(a); int x; cin >>x;

47、while (x! = -1) { push (a, x ); cin >>x; } while (!stackempty (a)) cout <

48、e > void BinTree ：： unknown (BinTreeNode*t) { BinTreeNode< Type> *p =t, *temp; if (p!=NULL) { temp = p→leftchild; p→leftchild = p→rightchild; p→rightchild = temp; unknown(p→leftchild); undnown(p→rightchild); } } 該算法的功能

49、是：________________________________ ? 五、 五、??????????? 算法填空，在畫有橫線的地方填寫合適的內容（10分） ? 對順序存儲的有序表進行二分查找的遞歸算法 。 int Binsch( ElemType A[ ],int low ,int high,KeyType K ) { if (low <= high) { int mid = 1 if ( K= = A[ mid ].key ) return mid; else if

50、 ( K < A[mid].key) return 2 else return 3 } else return 4 ? 六、 六、??????????? 編寫算法（10分） ? 編寫算法，將一個結點類型為Lnode的單鏈表按逆序鏈接，即若原單鏈表中存儲元素的次序為a1，……an-1，an，則逆序鏈接后變?yōu)? an，an-1，……a1。 Void contrary (Lnode * & HL) ? ? 數據結構試題（答案）

51、 一、單選題（每小題2分，共8分） 題 號 1 2 3 4 答 案 C D A B 二、填空題（每空1分，共32分） 1： 集合、線性、樹、圖； 2： 數據描述、操作聲名； 3： （38，56，25，60，42，74）； 4： HL→next =NULL； HL=HL→next； 5： 前一個位置； n-1； 6： S.stack [S.top]; HS→data; 7： 5 31 8： 邊結點、鄰接點域、權域、鏈域； 9： 索引值域、開始位置域； 10：

52、10、3、3、B、I和J； 11： O（log2n）、O(nlog2n); 12： m 、 m - 1 三、運算題（每小題6分，共24分） 1、 劃分次序 劃分結果 第一次 [38 24 40] 46 [56 80 95 79] 第二次 24 [38 40] 46 [56 80 95 79] 第三次 24 38 40 46 [56 80 95 79] 第四次 24 38 40 46 56 [80 95 79] 第五次 24 38 40 46 56 79 [80 95] 第六次 24 38

53、 40 46 56 79 80 95 ? 2、 0 1 2 3 4 5 6 7 8 9 10 11 12 ? ? 78 ? 15 03 ? 57 45 20 31 ? 23 36 12 ? 查找成功的平均查找長度：ASL SUCC=14/10= 1.4 3、此二叉樹的后序遍歷結果是：EDCBIHJGFA 4、 圖 深度優(yōu)先序列 廣度優(yōu)先序列 鄰接矩陣表示時 0，1，2，8，3，4，5，6，7，9 0，1，4，2，7，3，8，6，5

54、，9 鄰接表表示時 0，4，3，8，9，5，6，7，1，2 0，4，1，3，7，2，8，6，9，5 四、閱讀算法，回答問題（每小題8分，共16分） 1、 1、? 該算法的輸入結果是：34 91 30 45 63 78 2、 2、? 該算法的功能是：交換二叉樹的左右子樹的遞歸算法。 五、算法填空，在畫有橫線的地方填寫合適的內容（10分） 1、1是：（low + high）/2; 2是： Binsch(A,low,mid–1,K); 3是： Binsch(A,mid+1,high,K); 4是： -1； 六、編寫算法（10分） 根據編程情況，酌

55、情給分。 { Lnode *P=HL; HL=NULL; While (p!=null) { Lnode*q=p; P=p→next; q→next=HL; HL=q; } } 第一部分 選擇題(30分) ? 一、 一、項選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的四個選項中只有一個選項是符合題目要求的，請將正確選項前的字母填在題后的括號內。 1．算法指的是（ ） A．計算機程序 B．解決問題的計算方法 C．排

56、序算法 D．解決問題的有限運算序列 2．線性表采用鏈式存儲時，結點的存儲地址（ ） A．必須是不連續(xù)的 B．連續(xù)與否均可 C．必須是連續(xù)的 D．和頭結點的存儲地址相連續(xù) 3．將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時間復雜度為（ ） A．O（1） B．O（n） C．O（m） D．O（m+n） 4．由兩個棧共享一個向量空間的好處是：（ ） A．減少存取時間，降低下溢發(fā)生的機率 B．節(jié)省存儲空間，降低上溢發(fā)生的機率 C．減少存取時間，降低

57、上溢發(fā)生的機率 D．節(jié)省存儲空間，降低下溢發(fā)生的機率 5．設數組data[m]作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，則執(zhí)行出隊操作后其頭指針front值為（ ） A．front=front+1 B．front=(front+1)%(m-1) C．front=(front-1)%m D．front=(front+1)%m 6．如下陳述中正確的是（ ） A．串是一種特殊的線性表 B．串的長度必須大于零 C．串中元素只能是字母

58、D．空串就是空白串 7．若目標串的長度為n，模式串的長度為[n/3]，則執(zhí)行模式匹配算法時，在最壞情況下的時間復雜度是（ ） A．O（） B．O（n） C．O（n2） D．O（n3） 8．一個非空廣義表的表頭（ ） A．不可能是子表 B．只能是子表 C．只能是原子 D．可以是子表或原子 9．假設以帶行表的三元組表表示稀疏矩陣，則和下列行表 0 2 3 3 5 對應的稀疏矩陣是（ ）

59、 10．在一棵度為3的樹中,度為3的結點個數為2,度為2 的結點個數為1,則度為0的結點個數為( ) A．4 B．5 C．6 D．7 11．在含n個頂點和e條邊的無向圖的鄰接矩陣中,零元素的個數為( ) A．e B．2e C．n2－e D．n2－2e 12．假設一個有n個頂點和e條弧的有向圖用鄰接表表示,則刪除與某個頂點vi相關的所有弧的時間復雜度是( ) A．O(n) B．O(e)

60、 C．O(n+e) D．O(n*e) 13．用某種排序方法對關鍵字序列（25，84，21，47，15，27，68，35，20）進行排序時，序列的變化情況如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 則所采用的排序方法是（ ） A．選擇排序 B．希爾排序 C．歸并排序 D．快速排序 14．適于對動態(tài)查找表進行高效率查找的組織結構是（ ） A．有序

61、表 B．分塊有序表 C．三叉排序樹 D．線性鏈表 15．不定長文件是指（ ） A．文件的長度不固定 B．記錄的長度不固定 C．字段的長度不固定 D．關鍵字項的長度不固定 ? 第二部分 非選擇題（共70分） 二、填空題（本大題共10小題，每小題2分，若有兩個空格，每個空格1分，共20分）不寫解答過程，將正確的答案寫在每小題的空格內。錯填或不填均無分。 16．數據的邏輯結構是從邏輯關系上描述數據，它與數據的 無關，是獨立于計算機的。 17．在一個帶頭結點的單循環(huán)鏈表中，p指向尾結點的直接前驅，則指向

62、頭結點的指針head可用p表示為head= 。 18．棧頂的位置是隨著 操作而變化的。 19．在串S=“structure”中，以t為首字符的子串有 個。 20．假設一個9階的上三角矩陣A按列優(yōu)先順序壓縮存儲在一維數組B中，其中B[0]存儲矩陣中第1個元素a1,1,則B[31]中存放的元素是 。 21．已知一棵完全二叉樹中共有768結點，則該樹中共有 個葉子結點。 22．已知一個圖的廣度優(yōu)先生成樹如右圖所示，則與此相

63、 應的廣度優(yōu)先遍歷序列為 。 ? ? 23．在單鏈表上難以實現的排序方法有 和 。 24．在有序表（12，24，36，48，60，72，84）中二分查找關鍵字72時所需進行的關鍵字比較次數為 。 25．多重表文件

64、和倒排文件都歸屬于 文件。 三、解答題（本大題共4小題，每小題5分，共20分） 26．畫出下列廣義表的共享結構圖形表示 P=（（（z）,(x,y)）,((x,y),x),(z)） 27．請畫出與下列二叉樹對應的森林。 ? ? ? ? ? ? 28．已知一個無向圖的頂點集為{a, b, c, d, e} ,其鄰接矩陣如下

65、所示 a b c d e (1)畫出該圖的圖形； （2）根據鄰接矩陣從頂點a出發(fā)進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫出相應的遍歷序列。 ? 29．已知一個散列表如下圖所示： ? ? 35 ? 20 ? ? 33 ? 48 ? ? 59 0 1 2 3 4 5 6 7 8 9 10 11 12 其散列函數為h(key)=key%13, 處理沖突的方法為雙重散列法，探查序列為： hi=(h(key)+*h1(key))%m =0,1,…

66、，m－1 其中 h1(key)=key%11+1 回答下列問題： （1）對表中關鍵字35，20，33和48進行查找時，所需進行的比較次數各為多少？ （2）該散列表在等概率查找時查找成功的平均查找長度為多少？ 四、算法閱讀題（本大題共4小題，每小題5分，共20分） 30．下列算法的功能是比較兩個鏈串的大小，其返回值為： comstr(s1,s2)= 請在空白處填入適當的內容。 int comstr(LinkString s1,LinkString s2) {//s1和s2為兩個鏈串的頭指針 while(s1&&s2){ if(s1－>datedate)return－1； if(s1－>date>s2－>date)return1； ① ； ② ； } if( ③ )return－1； if( ④ )return1； ⑤ ；