計算機軟件基礎習題及參考答案

上傳人：奔*** IP屬地：河北更新時間：2024-03-02 格式：doc 頁數(shù)：37 大小：633.00KB 人氣指數(shù)：12 舉報 版權(quán)申訴

已閱讀1頁，還剩36頁未讀，繼續(xù)免費閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領

文檔簡介

1、　　習題一　　1.什么是數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存儲結(jié)構(gòu)？數(shù)據(jù)結(jié)構(gòu)對算法有什么影響？請舉例說明。　　2.數(shù)據(jù)結(jié)構(gòu)的存儲方式主要有哪兩種？它們之間的本質(zhì)區(qū)別是什么？　　3.設n為正整數(shù), 分析下列各程序段中加下劃線的語句的執(zhí)行次數(shù)。

2、　　(1)for (int i = 1; i <= n; i++) 　　for (int j = 1; j <= n; j++) {　　c[i][j] = 0.0; 　　for (int k = 1; k <= n; k++)

3、c[i][j] = c[i][j] + a[i][k] * b[k][j];　　} 　　(2)x = 0; y = 0;　　for (int i = 1; i <= n; i++) 　　for (int j = 1

4、; j <= i; j++)　　for (int k = 1; k <= j; k++)　　x = x + y;　　(3)int i = 1, j = 1; 　　while (i<=n && j<=n) {

5、　　i = i + 1; j = j + i; 　　} 　　(4)*int i =1;　　do{　　for (int j = 1; j <= n; j++) <

6、/p>　　i = i + j;　　}while(i<100 + n);　　4.試編寫一個函數(shù)計算n!*2n的值，結(jié)果存放于數(shù)組A[arraySize]的第n個數(shù)組元素中，0 n arraySize。若設計算機中允許的整數(shù)的最大值為maxInt，則當n>arraySize或者對于某一個k (0 k n)，使得

7、k!*2k > maxInt時，應按出錯處理?？捎腥缦氯N不同的出錯處理方式：　　(1) 用printf顯示錯誤信息及exit(1)語句來終止執(zhí)行并報告錯誤；　　(2) 用返回整數(shù)函數(shù)值0, 1來實現(xiàn)算法，以區(qū)別是正常返回還是錯誤返回；　　(3) 在函數(shù)的參數(shù)表設置一個引用型的整型變量來區(qū)別是正常返回還是某

8、種錯誤返回。　　試討論這三種方法各自的優(yōu)缺點，并以你認為是最好的方式實現(xiàn)它。　　5.設有一個線性表 (a0, a1, …, an-2, an-1) 存放在一個一維數(shù)組A[arraySize]中的前n個數(shù)組元素位置。請編寫一個函數(shù)將這個線性表原地逆置，即將數(shù)組的前n個原址內(nèi)容置換為 (an-1, an-2, …, a1, a0)。最后分析此算法的時間復雜度

9、及空間復雜度。　　6.順序表的插入和刪除要求仍然保持各個元素原來的次序。設在等概率情形下, 對有127個元素的順序表進行插入, 平均需要移動多少個元素? 刪除一個元素, 又平均需要移動多少個元素?　　7.利用順序表的操作，實現(xiàn)以下的函數(shù)。并分析你所編制的函數(shù)的時間復雜度，并分析(2)與(3)的時間復雜度出現(xiàn)差異的原因。<p&

10、gt;　　(1) 從順序表中刪除具有給定值x的所有元素。　　(2) 從順序表中刪除其值在給定值s與t之間（要求s小于t）的所有元素。　　(3) 從有序順序表中刪除其值在給定值s與t之間（要求s小于t）的所有元素。　　(4) 將兩個有序順序表la,lb合并成一個新的有序順序表lc。<p

11、>　　(5) 從順序表中刪除所有其值重復的元素，使表中所有元素的值均不相同。　　8.線性表可用順序表或鏈表存儲。試問：　　(1) 兩種存儲表示各有哪些主要優(yōu)缺點?　　(2) 如果有n個表同時并存，并且在處理過程中各表的長度會動態(tài)發(fā)生變化，表的總數(shù)也可能自動改變、在此情況下，應選用哪種存儲表示？為什么？<

12、;/p>　　(3) 若表的總數(shù)基本穩(wěn)定，且很少進行插入和刪除，但要求以最快的速度存取表中的元素，這時，應采用哪種存儲表示？為什么？　　9.試寫出計算線性鏈表長度的算法。　　10.設有一個表頭指針為h的單鏈表。試設計一個算法，通過遍歷一趟鏈表，將鏈表中所有結(jié)點的鏈接方向逆轉(zhuǎn)，如下圖所示。要求逆轉(zhuǎn)結(jié)果鏈表的表頭指針h指向原鏈表的最

13、后一個結(jié)點。　　11.設有一線性鏈表，其結(jié)點值均為整數(shù)。試將該線性鏈表分解為兩個線性鏈表，其中一鏈表中的結(jié)點值均為負整數(shù)，而另一鏈表中結(jié)點的值均為正整數(shù)，并刪除結(jié)點值為零的結(jié)點。　　12．設ha和hb分別是兩個帶表頭結(jié)點的非遞減有序單鏈表的表頭指針, 試設計一個算法, 將這兩個有序鏈表合并成一個非遞減有序的單鏈表。要求結(jié)果鏈表仍使用原來兩個鏈表的存儲空間

14、, 不另外占用其它的存儲空間。表中允許有重復的數(shù)據(jù)。　　13．設ha和hb分別是兩個帶表頭結(jié)點的非遞減有序單鏈表的表頭指針, 試設計一個算法, 將這兩個有序鏈表合并成一個非遞增有序的單鏈表。要求結(jié)果鏈表仍使用原來兩個鏈表的存儲空間, 不另外占用其它的存儲空間。表中允許有重復的數(shù)據(jù)。　　14.在一個循環(huán)鏈表中尋找值為x的結(jié)點，并將該結(jié)點移到第一個結(jié)點之前。

15、　　15.對于下面的每一步，畫出棧元素和棧頂指針的示意圖：　?。?）棧初始化；　?。?）元素x入棧；　?。?）元素y入棧；<p&

16、gt;　?。?）出棧　?。?）棧初始化　?。?）元素z入棧　　16.鐵路進行列車調(diào)度時, 常把站臺設計成棧式結(jié)構(gòu)的站臺，如右圖所示。試問：　　(1) 設有編號

17、為1,2,3,4,5,6的六輛列車, 順序開入棧式結(jié)構(gòu)的站臺, 則可能的出棧序列有多少種?　　(2) 若進站的六輛列車順序如上所述, 那么是否能夠得到435612, 325641, 154623和135426的出站序列, 如果不能, 說明為什么不能; 如果能, 說明如何得到(即寫出"進棧"或"出棧"的序列)。　　1

18、7.試證明：若借助?？捎奢斎胄蛄?, 2, 3, …, n得到一個輸出序列p1, p2, p3, …, pn (它是輸入序列的某一種排列)，則在輸出序列中不可能出現(xiàn)以下情況，即存在i < j < k，使得pj < pk < pi。(提示：用反證法)　　18.將編號為0和1的兩個棧存放于一個數(shù)組空間V[m]中，棧底分別處于數(shù)組的兩端。當?shù)?號棧的棧頂指針top[0]等于-1

19、時該棧為空，當?shù)?號棧的棧頂指針top[1]等于m時該棧為空。兩個棧均從兩端向中間增長。當向第0號棧插入一個新元素時，使top[0]增1得到新的棧頂位置，當向第1號棧插入一個新元素時，使top[1]減1得到新的棧頂位置。當top[0]+1 == top[1]時或top[0] == top[1]-1時，?？臻g滿，此時不能再向任一棧加入新的元素。試定義這種雙棧(Double Stack)結(jié)構(gòu)的類定義，并實現(xiàn)判?？?、判棧滿、插入、刪除算法。&

20、lt;/p>　　19.改寫順序棧的進棧成員函數(shù)Push(x)，要求當棧滿時執(zhí)行一個stackFull( )操作進行棧滿處理。其功能是：動態(tài)創(chuàng)建一個比原來的棧數(shù)組大二倍的新數(shù)組，代替原來的棧數(shù)組，原來棧數(shù)組中的元素占據(jù)新數(shù)組的前MaxSize位置。　　20.根據(jù)教案中給出的優(yōu)先級，回答以下問題：　　(1) 在表達式求值的過程中，

21、如果表達式e含有n個運算符和分界符，問操作數(shù)棧(NS)中最多可存入多少個元素？　　(2) 如果表達式e含有n個運算符，且括號嵌套的最大深度為6層，問棧中最多可存入多少個元素？　　21.表達式的中綴表示為a * x - b / x^2，試利用棧將它改為后綴表示ax * bx2^/ -。寫出轉(zhuǎn)換過程中棧的變化。(^表示乘方運算)<

22、;p>　　22.設循環(huán)隊列的容量為70（序號從1到70），經(jīng)過一系列入隊和退隊運算后，有：　?。?）front=15，rear=46；　?。?）front=45，rear=10　　問在上述兩種情況下，循環(huán)隊列中各有多少個元素？　　23.設用鏈表表示一個雙端隊列，要求

23、可在表的兩端插入，但限制只能在表的一端刪除。試編寫基于此結(jié)構(gòu)的隊列的插入(enqueue)和刪除(dequeue)算法，并給出隊列空和隊列滿的條件。　　習題2　　1．列出右圖所示二叉樹的葉結(jié)點、分支結(jié)點和每個結(jié)點的層次。　　2．使用 (1) 順序表示和 (2) 二叉鏈表表示法

24、，分別畫出上圖所示二叉樹的存儲表示。　　3．在結(jié)點個數(shù)為n (n>1)的各棵樹中，高度最小的樹的高度是多少？它有多少個葉結(jié)點？多少個分支結(jié)點？高度最大的樹的高度是多少？它有多少個葉結(jié)點？多少個分支結(jié)點？　　4．試分別畫出具有3個結(jié)點的樹和3個結(jié)點的二叉樹的所有不同形態(tài)。　　5．如果一棵樹有n1個度為1的結(jié)點

25、, 有n2個度為2的結(jié)點, … , nm個度為m的結(jié)點, 試問有多少個度為0的結(jié)點? 試推導之。　　6．若用二叉鏈表作為二叉樹的存儲表示，試針對以下問題編寫遞歸算法：　　(1) 統(tǒng)計二叉樹中葉結(jié)點的個數(shù)。　　(2) 以二叉樹為參數(shù)，交換每個結(jié)點的左子女和右子女。　　(3)

26、求二叉樹的深度。　　7．一棵高度為h的滿k叉樹有如下性質(zhì): 第h層上的結(jié)點都是葉結(jié)點, 其余各層上每個結(jié)點都有k棵非空子樹, 如果按層次自頂向下, 同一層自左向右, 順序從1開始對全部結(jié)點進行編號, 試問:　　(1) 各層的結(jié)點個數(shù)是多少?　　(2) 編號為i的結(jié)點的父結(jié)點(若存在)的編號是多少?</p&

27、gt;　　(3) 編號為i的結(jié)點的第m個孩子結(jié)點(若存在)的編號是多少?　　(4) 編號為i的結(jié)點有右兄弟的條件是什么? 其右兄弟結(jié)點的編號是多少?　　(5) 若結(jié)點個數(shù)為 n, 則高度h是n 的什么函數(shù)關系?　　8．請畫出下圖所示的樹所對應的二叉樹。

28、;　　9．已知一棵二叉樹的前序遍歷的結(jié)果是ABECDFGHIJ, 中序遍歷的結(jié)果是EBCDAFHIGJ, 試畫出這棵二叉樹。　　10．給定權(quán)值集合{15, 03, 14, 02, 06, 09, 16, 17}, 構(gòu)造相應的霍夫曼樹, 并計算它的帶權(quán)路徑長度。　　習題三　　1

29、. 設有序順序表中的元素依次為017, 094, 154, 170, 275, 503, 509, 512, 553, 612, 677, 765, 897, 908。試畫出對其進行折半查找時的二叉查找樹, 并計算查找成功的平均查找長度和查找不成功的平均查找長度。　　2. 若對有n個元素的有序順序表和無序順序表進行順序查找, 試就下列三種情況分別討論兩者在等查找概率時的平均查找長度是否相同?&l

30、t;/p>　　(1) 查找失敗;　　(2) 查找成功, 且表中只有一個關鍵碼等于給定值k的對象;　　(3) 查找成功, 且表中有若干個關鍵碼等于給定值k的對象, 要求一次查找找出所有對象。　　3. 設有10000個記錄對象, 通過分塊劃分為若干子表

31、并建立索引, 那么為了提高查找效率, 每一個子表的大小應設計為多大? 　　4. 設散列表為HT[13], 散列函數(shù)為 H (key) = key %13。用閉散列法解決沖突, 對下列關鍵碼序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。　　(1) 采用線性探測法尋找下一個空位, 畫出相應的散列表, 并計算等概率下

32、查找成功的平均查找長度和查找不成功的平均查找長度。　　(2) 采用隨機探測法尋找下一個空位, 隨機數(shù)序列為：5，4，2，7，3，6，…。畫出相應的散列表, 并計算等概率下查找成功的平均查找長度。　　5. 設有150個記錄要存儲到散列表中, 要求利用線性探查法解決沖突, 同時要求找到所需記錄的平均比較次數(shù)不超過2次。試問散列表需要設計多大？設是散列表的裝

33、載因子，則有　　6. 設有15000個記錄需放在散列文件中，文件中每個桶內(nèi)各頁塊采用鏈接方式連結(jié)，每個頁塊可存放30個記錄。若采用按桶散列，且要求查找到一個已有記錄的平均讀盤時間不超過1.5次，則該文件應設置多少個桶？已知，鏈地址法的平均查找長度ASL=1+α/2　　7. 設待排序的排序碼序列為{12, 2, 16, 30, 28, 10, 16*,

34、 20, 6, 18}, 試分別寫出使用以下排序方法每趟排序后的結(jié)果。并說明做了多少次排序碼比較。　　(1) 直接插入排序(2) 希爾排序(增量為5,2,1)(3) 冒泡排序　　(4) 快速排序(5) 直接選擇排序(6) 堆排序　　(7) 二路歸并排序<

35、;p>　　8. 在起泡排序過程中，什么情況下排序碼會朝向與排序相反的方向移動，試舉例說明。在快速排序過程中有這種現(xiàn)象嗎？　　9. 試設計一個算法, 使得在O(n)的時間內(nèi)重排數(shù)組, 將所有取負值的排序碼排在所有取正值(非負值)的排序碼之前。　　提示：對比快速排序的第一趟排序，此處，以0為控制關鍵字。　　10

36、. 手工跟蹤對以下各序列進行堆排序的過程。給出形成初始堆及每選出一個排序碼后堆的變化。　　(1) 按字母順序排序：Tim, Dot, Eva, Rom, Kim, Guy, Ann, Jim, Kay, Ron, Jan 　　(2) 按數(shù)值遞增順序排序：26, 33, 35, 29, 19, 12, 22 　　(

37、3) 同樣7個數(shù)字，換一個初始排列，再按數(shù)值的遞增順序排序：12, 19, 33, 26, 29, 35, 22　　11. 希爾排序、簡單選擇排序、快速排序和堆排序是不穩(wěn)定的排序方法, 試舉例說明。　　12. 在已排好序的序列中，一個對象所處的位置取決于具有更小排序碼的對象的個數(shù)。基于這個思想，可得計數(shù)排序方法。該方法在聲明對象時為每個對象增加一個計數(shù)域

38、count，用于存放在已排好序的序列中該對象前面的對象數(shù)目，最后依count域的值，將序列重新排列，就可完成排序。試編寫一個算法，實現(xiàn)計數(shù)排序。并說明對于一個有n個對象的序列，為確定所有對象的count值，最多需要做n(n-1)/2次排序碼比較。　　習題解答　　3.設n為正整數(shù), 分析下列各程序段中加下劃線的語句的執(zhí)

39、行次數(shù)。　　(1)for (int i = 1; i <= n; i++) 　　for (int j = 1; j <= n; j++) {　　c[i][j] = 0.0; 　　for (int k = 1; k <= n; k++)

40、;　　c[i][j] = c[i][j] + a[i][k] * b[k][j];　　} 　　(2)x = 0; y = 0;　　for (int i = 1; i <= n; i++)

41、for (int j = 1; j <= i; j++)　　for (int k = 1; k <= j; k++)　　x = x + y;　　(3)int i = 1, j = 1; 　　while (i<=n && j<=n

42、) {　　i = i + 1; j = j + i; 　　} 　　(4)*int i =1;　　do{　　for (int j = 1; j <

43、= n; j++) 　　i = i + j;　　}while(i<100 + n);　　【解答】　　(1) 　　(2) </

44、b>　　(3)i = 1時，i = 2，j = j + i = 1 + 2 = 2 + 1，　　i = 2時，i = 3，j = j + i = ( 2 + 1 ) + 3 = 3 + 1 + 2，　　i = 3時，i = 4，j = j + i = ( 3 + 1 + 2 ) + 4 = 4 + 1 +

45、2 + 3，　　i = 4時，i = 5，j = j + i = ( 4 + 1 + 2 + 3 ) + 5 = 5 + 1 + 2 + 3 + 4，　　……　　i = k時，i = k + 1，j = j + i = ( k + 1 ) + ( 1 + 2 + 3 + 4

46、+ … + k )，　　解出滿足上述不等式的k值，即為語句i = i + 1的程序步數(shù)。 (4) for語句每執(zhí)行一次，語句i=i+j將執(zhí)行n次，而i的值會增加　　因此，當for語句執(zhí)行k次后，i的值將變?yōu)?lt;/p>　　故最終for語句的執(zhí)行次數(shù)k為滿足　　的最小整數(shù)k，語句i

47、= i + j的程序步數(shù)為n*k。　　4.試編寫一個函數(shù)計算n!*2n的值，結(jié)果存放于數(shù)組A[arraySize]的第n個數(shù)組元素中，0 n arraySize。若設計算機中允許的整數(shù)的最大值為maxInt，則當n>arraySize或者對于某一個k (0 k n)，使得k!*2k > maxInt時，應按出錯處理?？捎腥缦氯N不同的出錯處理方式：&l

48、t;p>　　(1) 用printf顯示錯誤信息及exit(1)語句來終止執(zhí)行并報告錯誤；　　(2) 用返回整數(shù)函數(shù)值0, 1來實現(xiàn)算法，以區(qū)別是正常返回還是錯誤返回；　　(3) 在函數(shù)的參數(shù)表設置一個引用型的整型變量來區(qū)別是正常返回還是某種錯誤返回。　　試討論這三種方法各自的優(yōu)缺點，并以你認為是最好的方式實

49、現(xiàn)它。　　【解答】　　#include <stdio.h>const int arraySize = 100;　　const int MaxInt = 0x7fffffff;int calc( int T[ ], int n ) {int i, value

50、 = 1;if ( n != 0 ) {　　int edge = MaxInt / n / 2;　　for ( i = 1; i < n; i++ ) {　　value *= i*2;　　if ( value > edge ) return 0;</

51、p>　　}　　value *= n * 2;　　}　　T[n] = value;　　printf("A[ %d ]= %d\n”,n,T[n]);</p

52、>　　return 1;　　}　　void main ( ) {int A[arraySize];　　int i;　　for

53、 ( i = 0; i < arraySize; i++ )　　if ( !calc ( A, i ) ) {　　printf("failed at %d .\n", i );　　break;

54、;　　}　　}　　/*---------順序表結(jié)構(gòu)的定義.為簡化起見，表元素我們使用整型數(shù)據(jù)-----------　　-----------數(shù)據(jù)元素從data[0]處開始存儲---------------------------------*/</p

55、>　　typedef struct /*注意typedef的使用*/　　{ 　　int data[MAXSIZE]; /*數(shù)據(jù)域*/　　int length; /*表長*/　　}li

56、sttype;　　5.設有一個線性表 (a0, a1, …, an-2, an-1) 存放在一個一維數(shù)組A[arraySize]中的前n個數(shù)組元素位置。請編寫一個函數(shù)將這個線性表原地逆置，即將數(shù)組的前n個原址內(nèi)容置換為 (an-1, an-2, …, a1, a0)。最后分析此算法的時間復雜度及空間復雜度。　　【解答】

57、;　　void inverse (listtype * A) {　　int tmp;　　int n= A->length;　　for( int i = 0; i <= ( n-1 ) / 2; i++ ){</p&g

58、t;　　tmp = A->data[i]; A->data[i] = A->data[n-i-1]; A->data[n-i-1] = tmp;　　}　　}　　時間復雜度：需進行n/2次循

59、環(huán)，因此時間復雜度為O(n)；　　空間復雜度：使用一個整形輔助存儲單元tmp，因此空間復雜度為O(1)。　　6.順序表的插入和刪除要求仍然保持各個元素原來的次序。設在等概率情形下, 對有127個元素的順序表進行插入, 平均需要移動多少個元素? 刪除一個元素, 又平均需要移動多少個元素?　　【解答

60、】　　若設順序表中已有n個元素。又設插入或刪除表中各個元素的概率相等，則在插入時因有n+1個插入位置(可以在表中最后一個表項后面追加)，每個元素位置插入的概率為1/(n+1)，但在刪除時只能在已有n個表項范圍內(nèi)刪除，所以每個元素位置刪除的概率為1/n。　　插入時平均移動元素個數(shù)AMN(Averagy Moving Number )為&

61、lt;/p>　　刪除時平均移動元素個數(shù)AMN為　　7.利用順序表的操作，實現(xiàn)以下的函數(shù)。并分析你所編制的函數(shù)的時間復雜度，并分析(2)與(3)的時間復雜度出現(xiàn)差異的原因。　　(1) 從順序表中刪除具有給定值x的所有元素。　　(2) 從順序表中刪除其值在給定值s與t之間（要求s小于t）的

62、所有元素。　　(3) 從有序順序表中刪除其值在給定值s與t之間（要求s小于t）的所有元素。　　(4) 將兩個有序順序表la,lb合并成一個新的有序順序表lc。　　(5) 從順序表中刪除所有其值重復的元素，使表中所有元素的值均不相同。　　【解答】</

63、b>　　(1) 從順序表中刪除具有給定值x的所有元素。　　void DelValue(listtype * L, int x ){　　int i = 0, j;　　while ( i < L->length )/*循環(huán), 尋找具有值x的元素并刪除

64、它*/　　if (L->data[i] == x ) { /*刪除具有值x的元素, 后續(xù)元素前移*/　　for (j = i;j < L->length-1; j++ ) L->data[j] = L->data[j+1];　　L-length--; /*表長減1*/

65、　　}　　else i++;　　}　　(2) 實現(xiàn)刪除其值在給定值s與t之間（要求s小于t）的所有元素的函數(shù)如下：

66、　void DelValue_s_to_t (listtype *L,int s, int t){　　int i,j;　　if ( L->length == 0 || s >= t ) {　　printf(“List is empty or parameters

67、are illegal!\n”); exit(1); }　　i = 0;　　while ( i < L->length)/*循環(huán), 尋找具有值x的元素并刪除它*/　　if (L->data[i]>=s &&L->data

68、[i]<= t){　　/*刪除滿足條件的元素, 后續(xù)元素前移*/　　for ( j = i; j < L->length-1; j++ ) L->data[j] = L->data[j+1];　　L->length--; /*表長減1*/&l

69、t;p>　　}　　else i++;　　}　　(3) 實現(xiàn)從有序順序表中刪除其值在給定值s與t之間的所有元素的函數(shù)如下：　　void DelValue_

70、s_to_t_1 (listtype *L,int s int t){　　int i,j,k;　　if ( L->length == 0 || s >= t ){ 　　printf(“List is empty or parameters are illegal!\n”); exit(1); }&l

71、t;/p>　　for (i = 0; i < L->length; i++ ) /*循環(huán), 尋找值 ≥s 的第一個元素*/　　if ( L->data[i] >= s ) break; /*退出循環(huán)時, i指向該元素*/　　if ( i < L->length ) {</p&g

72、t;　　for (j = 1; i + j < L->length; j++ )/*循環(huán), 尋找值 > t 的第一個元素*/　　if (L->data[i+j] > t ) break;/*退出循環(huán)時, i+j指向該元素*/　　for (k = i+j; k < L->length; k

73、++ ) /*刪除滿足條件的元素, 后續(xù)元素前移*/　　L->data[k-j] = L->data[k]; 　　L->length-= j; /*表長減j*/　　}　　}</b

74、>　　(4) 實現(xiàn)將兩個有序順序表合并成一個新的有序順序表的函數(shù)如下：　　listtype * Merge(listtype *LA,listtype *LB ){　　/*合并有序順序表LA與LB成為一個新的有序順序表并由函數(shù)返回　　listtype *LC;<

75、;/p>　　int value1,value2;　　int i,j,k;　　initiatelist(LC);　　if (LA->length + LB->length > MAXSIZE) { 　　printf(“表上溢/n

76、”; exit(1); 　　}　　i = 0, j = 0, k = 0;　　value1 = LA->data[i];　　value2 = LB->data[j];　　whil

77、e (i < LA->length && j < LB->length ) {　　/*循環(huán), 兩兩比較, 小者存入結(jié)果表*/　　if (value1 <= value2){　　LC->data[k] = value1; i++; value1=LA->d

78、ata[i];}　　else { 　　LC->data[k] = value2; j++; value2=LB->data[j];}　　k++;　　} </

79、b>　　while( i < LA->length){/*當LA表未檢測完, 繼續(xù)向結(jié)果表傳送*/　　LC->data[k] = value1; i++; k++; value1 = LA->data[i]; 　　}</p

80、>　　while( j < LB->length){/*當LB表未檢測完, 繼續(xù)向結(jié)果表傳送*/　　LC->data[k] = value2; j++; k++; value2 = LB->data[j];　　}

81、LC->length = k;　　return LC;　　}　　(5) 實現(xiàn)從表中刪除所有其值重復的元素的函數(shù)如下：　　void DelDouble(listtype *L){　　int

82、 i,j,k;　　int tmp;　　if(L->length == 0 ){ 　　printf(“表空\n”; exit(1); 　　}<

83、b>　　i=0;　　while ( i < L->length ) {/*循環(huán)檢測*/　　j = i + 1; 　　tmp = L->data[i];　　while( j < L->length ) {/*對

84、于每一個i, 重復檢測一遍后續(xù)元素*/　　if( tmp == L->data[j]) {/*如果相等,刪除此結(jié)點，后續(xù)元素前移*/　　for( k = j+1; k < L->length; k++ ) L->data[k-1] = L->data[k];　　L->leng

85、th--; /*表最后元素位置減1*/　　}　　else j++;　　} 　　i++;/*檢測完L->data[i], 檢測下一個*/

86、　　}　　}　　8.線性表可用順序表或鏈表存儲。試問：　　(1) 兩種存儲表示各有哪些主要優(yōu)缺點?　　(2) 如果有n個表同時并存，并且在處理過程中各表的

87、長度會動態(tài)發(fā)生變化，表的總數(shù)也可能自動改變、在此情況下，應選用哪種存儲表示？為什么？　　(3) 若表的總數(shù)基本穩(wěn)定，且很少進行插入和刪除，但要求以最快的速度存取表中的元素，這時，應采用哪種存儲表示？為什么？　　【解答】　　(1) 順序存儲表示是將數(shù)據(jù)元素存放于一個連續(xù)的存儲空

88、間中，實現(xiàn)順序存取或(按下標)直接存取。它的存儲效率高，存取速度快。但它的空間大小一經(jīng)定義，在程序整個運行期間不會發(fā)生改變，因此，不易擴充。同時，由于在插入或刪除時，為保持原有次序，平均需要移動一半(或近一半)元素，修改效率不高。　　鏈接存儲表示的存儲空間一般在程序的運行過程中動態(tài)分配和釋放，且只要存儲器中還有空間，就不會產(chǎn)生存儲溢出的問題。同時在插入和刪除時不需要保持數(shù)據(jù)元素原來的物理順序，只

89、需要保持原來的邏輯順序，因此不必移動數(shù)據(jù)，只需修改它們的鏈接指針，修改效率較高。但存取表中的數(shù)據(jù)元素時，只能循鏈順序訪問，因此存取效率不高。　　(2) 如果有n個表同時并存，并且在處理過程中各表的長度會動態(tài)發(fā)生變化，表的總數(shù)也可能自動改變、在此情況下，應選用鏈接存儲表示。　　如果采用順序存儲表示，必須在一個連續(xù)的可用空間中為這n個表分配空間。初始時因不知

90、道哪個表增長得快，必須平均分配空間。在程序運行過程中，有的表占用的空間增長得快，有的表占用的空間增長得慢；有的表很快就用完了分配給它的空間，有的表才用了少量的空間，在進行元素的插入時就必須成片地移動其他的表的空間，以空出位置進行插入；在元素刪除時，為填補空白，也可能移動許多元素。這個處理過程極其繁瑣和低效。　　如果采用鏈接存儲表示，一個表的存儲空間可以連續(xù)，可以不連續(xù)。表的增長通過動態(tài)存儲分配解

91、決，只要存儲器未滿，就不會有表溢出的問題；表的收縮可以通過動態(tài)存儲釋放實現(xiàn)，釋放的空間還可以在以后動態(tài)分配給其他的存儲申請要求，非常靈活方便。對于n個表(包括表的總數(shù)可能變化)共存的情形，處理十分簡便和快捷。所以選用鏈接存儲表示較好。　　(3) 應采用順序存儲表示。因為順序存儲表示的存取速度快，但修改效率低。若表的總數(shù)基本穩(wěn)定，且很少進行插入和刪除，但要求以最快的速度存取表中的元素，這時采用順序

92、存儲表示較好。　　/*---------鏈表結(jié)構(gòu)的定義.為簡化起見，表元素我們使用整型數(shù)據(jù)-----------　　-----------此鏈表帶頭結(jié)點--------------------------------------------*/　　typedef struct mynode{

93、　　int data; /*數(shù)據(jù)域：整型*/　　struct mynode *next; /*指針域*/　　} node, linklisttype;　　9.試寫出計算線性鏈表長度的算法。　　int lengthsl(

94、linklisttype *L){　　linklisttype * p;　　int len;　　if(L == NULL){return –1;}　　p = L->next;/* p指向鏈表L的頭結(jié)點*/</p&

95、gt;　　len = 0;　　while(p != NULL){　　len++;　　p = p->next;　　}</p&g

96、t;　　return len;　　}　　10.設有一個表頭指針為h的單鏈表。試設計一個算法，通過遍歷一趟鏈表，將鏈表中所有結(jié)點的鏈接方向逆轉(zhuǎn)，如下圖所示。要求逆轉(zhuǎn)結(jié)果鏈表的表頭指針h指向原鏈表的最后一個結(jié)點。　　【解答】</b&g

97、t;　　void LinkListInverse(linklisttype *L){　　linklisttype *p, *pre, *next;　　if(L == NULL || L->next == NULL ) return; /*表未初始化，或為空表*/

98、p = L->next;　　pre = L;　　while( p != NULL ) {/*循環(huán)修改鏈表中所有結(jié)點的后繼指針的指向*/　　next = p->next;/*取當前結(jié)點的后繼指針*/　　p-&g

99、t;next = pre;/*當前結(jié)點的后繼改為指向其原來的前驅(qū)*/　　pre = p , p=next;/*指針后移*/　　}　　L->next->next = NULL;/*原第一個結(jié)點改為最后一個結(jié)點*/<p

100、>　　L->next = pre;/*鏈表的頭結(jié)點指向原最后一個結(jié)點*/　　}　　11.設有一線性鏈表，其結(jié)點值均為整數(shù)。試將該線性鏈表分解為兩個線性鏈表，其中一鏈表中的結(jié)點值均為負整數(shù)，而另一鏈表中結(jié)點的值均為正整數(shù)，并刪除結(jié)點值為零的結(jié)點。<b

101、>　　【解答】　　void LinkListDispose(linklisttype * L,linklisttype * LA,linklisttype * LB){　　/*　　將鏈表L分解為LA、LB兩個鏈表，其中LA中結(jié)點值均為正，LB中結(jié)點值

102、均為負，　　并刪除結(jié)點值為零的結(jié)點,最后釋放L的頭結(jié)點。　　*/　　linklisttype *p , *pt , *pa, * pb;　　LA = initiatesl();　　pa = L

103、A;/*指向LA中的最后一個結(jié)點*/　　LB = initiatesl();　　pb = LB;/*指向LB中的最后一個結(jié)點*/　　If(L == NULL || L->next == NUUL) return;/*L為空指針或L為空表*/<p&

104、gt;　　p = L->next;/*p指向鏈表L的第一個結(jié)點*/　　while(p != NULL)/*遍歷鏈表L*/　　if(p->data > 0){/*將p鏈入鏈表LA的pa后*/　　pa->next = p;

105、　　pa = p;　　p = p->next;　　}　　elseif(p->data < 0){/*將p鏈入鏈表LB的pb后*/　　pb->next = p;<

106、/p>　　pb = p;　　p = p->next;　　}　　else{/*刪除值為0的結(jié)點*/　　pt = p->next;/*記錄

107、當前結(jié)點的后繼，以便刪除當前結(jié)點*/　　free(p);　　p = pt;　　}　　pa->next = NULL;<p&

108、gt;　　pb->next = NULL;　　free(L);　　}　　12．設ha和hb分別是兩個帶表頭結(jié)點的非遞減有序單鏈表的表頭指針, 試設計一個算法, 將這兩個有序鏈表合并成一個非遞減有序的單鏈表。要求結(jié)果鏈表仍使用原來兩個

109、鏈表的存儲空間, 不另外占用其它的存儲空間。表中允許有重復的數(shù)據(jù)。　　【解答】　　void linklistMerge(linklisttype *LA,linklisttype *LB ){　　/*合并有序鏈表LA與LB,結(jié)果存入LA中，并釋放LB的頭結(jié)點 */</p

110、>　　linklisttype *pa, *pb , *pre ,*pn;　　if(LA == NULL || LB == NULL ||) return;　　if(LA->next == NULL){/*LA為空表，則直接將LB鏈入LA即可*/　　LA->next

111、 = LB->next;　　free(LB);　　retrun;　　}　　if(LB->next == NULL) return;/*LB為

112、空表，則直接返回即可*/　　pa = LA->next, pb = LB->next ,pre=LA;　　while (pa != NULL && pb != NULL)/*循環(huán), 兩兩比較, 小者存入結(jié)果表*/　　if(pa->data > pb->next){

113、/*將pb鏈入LA，然后pb指針后移*/　　pre->next = pb;　　pn = pb->next;　　pb->next = pa;　　pb = pn;　　pre

114、 = pre->next　　}　　else{/*pa指針后移*/　　pa = pa->next;　　pre = pre->next;　　}&

115、lt;/b>　　if(pb != NULL)/*將pb剩余結(jié)點鏈入LA*/　　pre->next = pb;　　free(LB);　　}<p

116、>　　13．設ha和hb分別是兩個帶表頭結(jié)點的非遞減有序單鏈表的表頭指針, 試設計一個算法, 將這兩個有序鏈表合并成一個非遞增有序的單鏈表。要求結(jié)果鏈表仍使用原來兩個鏈表的存儲空間, 不另外占用其它的存儲空間。表中允許有重復的數(shù)據(jù)。　　【解答】　　Linklisttype * linklistMerge_inv

117、erse(linklisttype *LA,linklisttype *LB ){　　/*合并有序鏈表LA與LB,結(jié)果存入LC中，并釋放LA、LB的頭結(jié)點 ,函數(shù)返回LC*/　　linklisttype *pa, *pb , *p;　　if(LA == NULL || LB == NULL ||) return;

118、　　LC = initiatesl();　　pa = LA->next, pb = LB->next;　　while (pa != NULL && pb != NULL)/*循環(huán), 兩兩比較, 大者存入LC*/　　if(pa->dat

119、a > pb->next){/*將pa鏈為LC的第一個結(jié)點*/　　p = pa->next;　　pa->next = LC->next;　　LC->next = pa;　　pa = p;<

120、;/p>　　}　　else{/*將pa鏈為LC的第一個結(jié)點*/　　p = pb->next;　　pb->next = LC->next;　　LC->next = pb

121、;　　pb = p;　　}　　while(pa != NULL){/*將pa剩余結(jié)點鏈入LC*/　　p = pa->next;　　pa

122、->next = LC->next;　　LC->next = pa;　　pa = p;　　}　　while(pb != NULL){/*將pb剩余結(jié)點鏈入LC*/&

123、lt;/p>　　p = pb->next;　　pb->next = LC->next;　　LC->next = pb;　　pb = p;　　}&

124、lt;/p>　　free(LA);　　free(LB);　　}　　14.在一個循環(huán)鏈表中尋找值為x的結(jié)點，并將該結(jié)點移到第一個結(jié)點之前。<p&

125、gt;　　【解答】設此循環(huán)鏈表為單鏈表，則其類型定義與一般單鏈表相同　　typedef struct mynode cyclelisttype;　　void search_movefirst(cyclelisttype *CL, int x){　　cyclelisttype * p , *pre;</p&g

126、t;　　if(CL == NULL) return;　　p = CL->next;　　pre = CL;　　while(p != CL)　　/*查找x，注意與普通單鏈表在判斷是否到表尾上的不同*/</

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
6. 下載文件中如有侵權(quán)或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

計算機軟件基礎習題及參考答案

文檔簡介

溫馨提示

最新文檔

評論

計算機軟件基礎習題及參考答案

文檔簡介

溫馨提示

最新文檔

評論

免費下載