廈大數(shù)據(jù)結(jié)構(gòu)習題及解答

1、1. 數(shù)據(jù)元素 是數(shù)據(jù)的基本單位，有些情況下也稱為元素、結(jié)點、頂點、記錄等。2 何謂算法?它與程序有何區(qū)別?算法是解決某一特定類型問題的有限運算序列。程序數(shù)據(jù)結(jié)構(gòu)算法3. 算法分析是對一種算法所消耗的計算機資源的估算，其中包括計算機 運行時間 的長短和 占據(jù)空間 的大小。4. 何謂頻度、時間復雜度、空間復雜度？說明其含義。算法中語句的重復次數(shù)稱為該語句的頻度。時間復雜度是算法執(zhí)行所需要的時間，也就是算法中每一個語句的執(zhí)行次數(shù)乘以每一次執(zhí)行所需的時間的總和。空間復雜度是算法對空間占用的量度。（一般在考慮空間復雜度時，只估算算法所需增添的輔助空間，而對問題中原始數(shù)據(jù)所占的空間，由于與算法無關(guān)，不予

2、考慮。）5. 時間復雜度的計算：語句2的頻度為n-l，語句4的額度為(n-1)(2n+1)2n2-n-l，因此時間復雜度T(n)O(n2)。語句3的頻度為n，語句7的頻度為n2，因此時間復雜度為T(n)O(n2)?！窘狻空Z句3的頻度不僅與n有關(guān)，而且和x及數(shù)組A中各分量的值有關(guān)。這時通?？紤]最壞的情況，由于while循環(huán)的最大次數(shù)為n-1，因此時間復雜度為T(n)O(n)。i=1;while(i=n) i=i*5;【解】設(shè)語句“i=i*5;”的頻度為x，則5x=n，x=log5n，O(log5n)i=0;s=0;while(sn) i+; s+=i;【解】i=1,s=1 i=2,s=1+2 i

3、=3,s=1+2+3,s就是對等差數(shù)列求和，因此s=i(i+1)/2Next) & (L=L-Prior) 注：L-Next=L-Prior不行，因為表長為1時該條件也成立。9. 判斷對錯：順序存儲的線性表不可以隨機存取。 （ * ）10. 判斷對錯：線性表的長度是線性表所占用的存儲空間的大小。 （ * ）11. 寫出帶頭結(jié)點的單鏈表和不帶頭結(jié)點的單鏈表的插入、刪除算法，并比較。/* 帶頭結(jié)點的插入算法。將s結(jié)點插入到數(shù)據(jù)域為x的結(jié)點之前。假設(shè)鏈表中存在該結(jié)點。 */void ins(head,s,x)struct node *head, *s;int x; struct node *p; p

4、=head;while (p-next!=NULL) if (p-next-data=x) s-next=p-next; p-next=s; return; else p=p-next;/* 不帶頭結(jié)點的插入算法。返回插入后的鏈表的頭指針 */struct node *ins(head,s,x)struct node *head, *s;int x; struct node *p; if (head-data=x) /* 插在第一個結(jié)點之前 */ s-next=head; return(s);p=head;while (p-next!=NULL) if (p-next-data=x) s-ne

5、xt=p-next; p-next=s; return(head); else p=p-next;/* 帶頭結(jié)點的刪除算法。刪除數(shù)據(jù)域為x的結(jié)點。假設(shè)鏈表中存在該結(jié)點。 */void del(head,x)struct node *head;int x; struct node *p, *q; p=head; while (p-next!=NULL) if (p-next-data=x)q=p-next; p-next=q-next; free(q); return; else p=p-next;/* 不帶頭結(jié)點的刪除算法。返回刪除后的鏈表的頭指針。 */struct node *del(he

6、ad,x)struct node *head;int x; struct node *p, *q; if (head-data=x)&(head-next=NULL) /* 在僅有一個結(jié)點的表中刪第一個結(jié)點 */ free(head); return(NULL); if(head-data=x) /* 在不只一個結(jié)點的表中刪第一個結(jié)點 */ q=head-next; free(head); return(q); p=head; while (p-next!=NULL) if (p-next-data=x)q=p-next; p-next=q-next; free(q); return(head

7、); else p=p-next;12. 已知線性表(al，a2，an)中的元素值按遞增有序排列，選用順序表結(jié)構(gòu)存放，試編寫算法刪除線性表中的值介于c與d (cd)之間的元素。13. 設(shè)計算法，求帶頭結(jié)點的循環(huán)鏈表的長度，如下圖所示。帶頭結(jié)點的循環(huán)鏈表14. 設(shè)計算法，在帶頭結(jié)點的單循環(huán)鏈表的第i個結(jié)點前插入元素值為x的結(jié)點。15. 設(shè)計算法，刪除帶頭結(jié)點的單循環(huán)鏈表的第i個結(jié)點。16. 設(shè)計算法，將不帶頭結(jié)點的單鏈表(a1, a2, ., an)中的元素逆置。算法思想：另建一鏈表p（初值為空），依次刪除原鏈表頭指針head所指點結(jié)點插入到p表表頭。17. 循環(huán)隊列首尾相連的狀態(tài)是通過 取模 運算來實現(xiàn)的。18. 已知棧的輸入序列為1,2,3,n，輸出序列為a1, a2, , an, 符合a2=n的輸出序列共有 n-1 種。a1可能是1，2，n-1，每個a1對應一個輸出序列，故共有n-1種輸出序列。19. 已知循環(huán)隊列用數(shù)組data1n存儲元素值（沒有data0），用f,r分別作為頭尾指針，則當前元素個數(shù)為 (n+r-f)mod n ?？紤]rf和rf兩種情形。20. 在解決計算機主機與打印機之間速度不匹配問題時通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機則從該緩沖區(qū)中取走數(shù)據(jù)打印。該緩沖區(qū)應該是一個（ ）結(jié)構(gòu)。A.棧 B.隊 C.