軟件結(jié)構(gòu)復(fù)習(xí)提綱以及復(fù)習(xí)題

軟件技術(shù)基礎(chǔ)以及數(shù)據(jù)的復(fù)習(xí)提綱：1. 語句頻度和時(shí)間復(fù)雜度的求法，要求會(huì)計(jì)算兩重循環(huán)的語句頻度。2. 堆棧的出棧進(jìn)棧的操作序列。6個(gè)元素的進(jìn)棧出棧過程。3. 稀疏矩陣的存儲(chǔ)矩陣的求解4. 單鏈表中節(jié)點(diǎn)的插入和刪除算法。5. 二叉樹的性質(zhì)，三種遍歷，排序二叉樹的生成，利用某兩種遍歷序列構(gòu)建原二叉樹6. 能夠根據(jù)給出的先根，中根，或者后根，中根序列，能夠構(gòu)建一個(gè)樹7. 圖的性質(zhì)，圖的存儲(chǔ)。兩種遍歷結(jié)果8. 掌握四種排序算法的算方法思想，能夠?qū)懗龈鞣N排序的輸出序列。9. 冒泡算法10. 順序查找算法1. 已知某算法有如下的代碼:m=0;for i = 0; i n ; i + for j = 2*i; j n ; j+ m:=m+1;，試計(jì)算出該算法的關(guān)鍵語句的語句頻度F（n）和時(shí)間復(fù)雜度T（n） = ？2. 已知某算法有如下的代碼:m=0;for i = 0; i n ; i + for j = i; j n ; j+ m:=m+1;，試計(jì)算出該算法的關(guān)鍵語句的語句頻度F（n）和時(shí)間復(fù)雜度T（n） = ？3. 如果輸入序列為1 2 3 4 5 6, 允許中間出棧，但是每個(gè)元素只能入棧，出棧一次，試問能否通過棧結(jié)構(gòu)得到以下兩個(gè)出棧序列:4 3 5 6 1 2和1 3 5 4 2 6;請(qǐng)說明為什么不能或如何才能得到。4. 如果輸入序列為6，5，4，3，2，1,允許中間出棧，但是每個(gè)元素只能入棧，出棧一次，試問能否通過棧結(jié)構(gòu)得到以下兩個(gè)出棧序列:4 3 5 6 1 2和1 3 5 4 2 6;請(qǐng)說明為什么不能或如何才能得到。5. 設(shè)矩陣0 0 0 20 0 8 00 4 0 01 0 5 0 A= 若將A視為稀疏矩陣寫出對(duì)其壓縮存儲(chǔ)的存儲(chǔ)矩陣?并計(jì)算出這樣存儲(chǔ)的效率？6. 設(shè)矩陣4 0 0 00 3 0 00 0 3 02 0 0 4 A= 若將A視為稀疏矩陣寫出對(duì)其壓縮存儲(chǔ)的存儲(chǔ)矩陣?7. 已知某有頭結(jié)點(diǎn)的單鏈表L（鏈上節(jié)點(diǎn)的數(shù)據(jù)元素是a1,a2, ai, an），試寫出刪除第i個(gè)節(jié)點(diǎn)的算法void DeleteNode(Node* l, int i)：8. 已知有以下多項(xiàng)式:，請(qǐng)根據(jù)自己學(xué)習(xí)的數(shù)據(jù)結(jié)構(gòu)的知識(shí)，將該多項(xiàng)式存儲(chǔ)到內(nèi)存中，以便后續(xù)數(shù)學(xué)處理。 void DeleteNode(Node* l, int i)9. 由下圖給出的二叉樹，求出先序，中序，后序遍歷結(jié)點(diǎn)的序列10. 由下圖給出的二叉樹，求出先序，中序，后序遍歷結(jié)點(diǎn)的序列11. 假設(shè)以行序?yàn)橹餍虼鎯?chǔ)二維數(shù)組A=array1.100，1.100，設(shè)每個(gè)數(shù)據(jù)元素占2個(gè)存儲(chǔ)單元，基地址為10，則LOC5,5=？12. 假設(shè)一個(gè)二叉樹的兩種遍歷如下先根：ABHFDECKG，中根：HBDFAEKCG試畫出該二叉樹，并給出后根遍歷序列？13. 已知有如下的圖：試寫出從節(jié)點(diǎn)C開始的深度遍歷序列和廣度遍歷序列？14. 已知，有一數(shù)組iarray = 23，14，56，34，92，19，77，35，80請(qǐng)分別寫出一趟冒泡排序，二趟快速后的輸出序列，15. 學(xué)生成績(jī)分別為75、65、56、88、67、90、87、70、77、72、91試以該順序建立一棵二叉排序樹，并寫出該樹的中序遍歷序列？16. 1）已知用于排序的順序表結(jié)構(gòu)體采用如下的定義：typedef struct keytype key; / 關(guān)鍵值 elemtype;typedef struct elemtype dataMAXNUM; /最大容量 int length; / 實(shí)際存放的數(shù)據(jù)元素個(gè)數(shù)。 tabletype;tabletype *table; / 實(shí)際使用的待排數(shù)據(jù)表指針請(qǐng)寫出采用該順序表的冒泡算法的C語言程序來？算法原型聲明如下：void bubble_sort( tabletype * table);2）已知某待排序的序列的關(guān)鍵字如下 34,67,21,67,89,65,78,12,66經(jīng)過一趟冒泡算法的處理，得到的結(jié)果序列是什么？17. 已知待查找的順序表的結(jié)構(gòu)體定義如下：typedef struct keytype key; / 關(guān)鍵值 elemtype;typedef struct elemtype dataMAXNUM; /最大容量 int length; / 實(shí)際存放的數(shù)據(jù)元素個(gè)數(shù)。 tabletype;tabletype *table; / 實(shí)際使用的待檢索數(shù)據(jù)表指針試寫出書序查找關(guān)鍵字aK