軟件技術基礎概論習題解析與上機指導（簡體書）

《普通高等教育電氣信息類應用型規劃教材:軟件技術基礎概論習題解析與上機指導》可作為高等學校工學專業和其他相關專業本科生、研究生教材，也可作為工程應用領域中應用軟件進行開發的科研和工程技術人員的參考書。

第1篇習題解析
第1章緒論
第2章線性表
第3章棧和隊列
第4章樹與二叉樹
第5章 圖
第6章查找
第7章排序
第8章軟件工程技術
第9章數據庫技術
第10章統一建模語言UML
第11章Web網頁設計
第2篇算法上機實現
第12章線性表算法
12.1順序表基本運算
12.2在表頭插入生成單鏈表
12.3在表尾插入生成單鏈表
12.4單鏈表基本運算
12.5例12.1算法實現
12.6例12.2算法實現
12.7例12.3算法實現
12.8例12.4算法實現
12.9例12.5算法實現
第13章棧和隊列算法
13.1順序棧基本運算
13.2鏈棧基本運算
13.3循環隊列基本運算
13.4鏈隊列基本運算
13.5例13.1算法實現
13.6例13.2算法實現
第14章樹與二叉樹算法
14.1二叉樹的遍歷
14.2二叉樹遍歷的應用
14.3 哈夫曼樹及哈夫曼編碼
14.4例14.1算法實現
第1 5章圖算法
15.1 建立無向圖的鄰接矩陣
15.2 圖的深度優先搜索
15.3 圖的廣度優先搜索
15.4圖的連通性
第16章查找算法
16.1順序查找
16.2折半（二分）查找
16.3分塊查找
16.4二叉排序樹建立和結點的查找
16.5哈希（Hash）查找
第17.章排序算法
17.1插入排序
17.2 冒泡排序
17.3快速排序
17.4選擇排序
17.5歸并排序
參考文獻

（2）鏈接表法為解決沖突的方法，其余均為哈希函數構造方法，故選A、B、C、E。
3.填空題。
（1）順序查找含有n個元素的順序表；若查找成功，則比較關鍵字的次數最多為___次；當使用監視哨時，若查找失敗，則比較關鍵字的次數為___。
（2）在n個記錄的有序表中進行折半查找，則最大的比較次數是___。
（3）設順序表（a1，a2，…，a500）元素的值由小到大排列，對一個給定的k值用二分法查找順序表，在查找不成功時至多需要比較___次。
（4）用二分法查找一個線性表時，該線性表必須具有的特點是___；而分塊查找法要求將待查的表均勻地分成若干塊且塊中的元素可無序存放，但塊與塊之間___。
（5）分塊查找中，若索引表對各塊內均采用順序查找，則有900個元素的線性表分成___塊最好；若分成25塊，其平均查找長度為___。
（6）二叉排序樹的查找長度不僅與___有關，也與二叉排序樹的___有關。
（7）在二叉排序樹上插入新結點時不必移動其他結點，僅需使樹葉結點的指針由指向新結點即可。
（8）假定有k個關鍵字互為同義詞，若用線性探測再散列的方法把這k個關鍵字存入散列表中，則至少需要進行___次探測。
【解析】
（1）順序查找n個元素，則查找成功時比較次數最多的是查找第n個元素，即需查找n次；若使用監視哨，則查找失敗的情況發生在查完n個元素卻仍未找到要找的元素并在遇到監視哨時終止查找，也即共查找了n+1次，所以應填：n；n+1。
（2）相當于走了一個完全二叉樹由樹根到樹葉的長度，即|log：n|+1，故應填：|log2n|+1。
（3）由log2n+1可知log2 500+1=9，故應填：9。
（4）應填：順序存儲且有序；有序。
（5）設每塊中有S個記錄，則對長度為n的表來說，當s取√n時平均查找長度為最小值：√n+1。對本題則s=√900=30，即塊數=900÷30=30為最好。設塊數為b，則平均查找長度，對本題則有故應填：30；31.5。
（6）應填：結點數n；生成過程（或形態）。
（7）二叉排序樹插入新結點時總是將該結點作為樹葉結點插入。因此，總是使原來某個樹葉結點的指針由空改為指向這個新插入的樹葉結點，故應填：空。
（8）設表長為m，關鍵字的個數為n，若發生沖突的地址為d，則依次探查d+1，d+2，…，m—1，0，1，…，d—1，直到找到一個空單元地址為止。假定沖突的單元地址d之后和之前都為空單元，則k個同義詞關鍵字依次探測存入散列表而需進行1+2+…+k次探測。如果在地址d之后或之前存在非空單元，則探測的次數必然大于，故應填。
4.判斷題。
（1）用數組或單鏈表存儲的有序表均可用折半查找方法來提高查找速度。
（2）有n個數存放在一維數組中，在進行順序查找時，這n個數的排列有序或無序決定了平均查找長度的不同。
（3）在任意一棵非空二叉排序樹中，刪除某結點后又將其插入，則所得到的二叉排序樹與刪除之前的原二叉排序樹相同。