數(shù)據(jù)結(jié)構(gòu)習(xí)題參考答案

1、習(xí)題習(xí)題1參考答案參考答案1至8題答案略。9.（1）【解】該邏輯結(jié)構(gòu)為線性結(jié)構(gòu)，其圖形表示如下：SunMonTueWedThuFriSat（2）【解】該邏輯結(jié)構(gòu)為樹(shù)型結(jié)構(gòu)，其圖形表示如下：bcdefghjika（3）【解】該邏輯結(jié)構(gòu)為圖型結(jié)構(gòu)，其圖形表示如下：bcdea（4）【解】該邏輯結(jié)構(gòu)為線性結(jié)構(gòu)，其圖形表示如下：c1c2c3cn……10.【解】該圖書(shū)庫(kù)存管理系統(tǒng)所要處理的數(shù)據(jù)對(duì)象為圖書(shū)，所以該問(wèn)題中涉及的數(shù)據(jù)元素為圖書(shū)，設(shè)數(shù)據(jù)元素

2、類型為bookType類型。每個(gè)數(shù)據(jù)元素應(yīng)包含的數(shù)據(jù)項(xiàng)有圖書(shū)編號(hào)、書(shū)名、作者、出版社、出版日期等?？捎靡粋€(gè)表格（如下表）的形式表示圖書(shū)間的邏輯關(guān)系，即該問(wèn)題數(shù)學(xué)模型可采用簡(jiǎn)單的線性結(jié)構(gòu)來(lái)表示。圖書(shū)信息表編號(hào)書(shū)名作者出版社出版日期1數(shù)據(jù)結(jié)構(gòu)顧澤元北京航空航天大學(xué)出版社2011年6月2高等數(shù)學(xué)李四北京航空航天大學(xué)出版社2009年1月3計(jì)算方法張五清華大學(xué)出版社2008年12月根據(jù)問(wèn)題需求功能目標(biāo)，此模型的所需的主要處理操作有插入、刪除、查找

3、和修改等基本操作。所以，現(xiàn)用抽象數(shù)據(jù)類型bookList表示問(wèn)題模型，其邏輯結(jié)構(gòu)與基本操作的定義如下：（1）邏輯結(jié)構(gòu)bookList=(Dr)D=bi|bi為bookType類型的元素，i=123.....n，n≥0r=|i=12…n1n≥0（2）基本操作①初始化12.【解】算法（1）中有兩個(gè)并列的循環(huán)，每個(gè)循環(huán)的循環(huán)體語(yǔ)句執(zhí)行次數(shù)均為n，故該函數(shù)的語(yǔ)句頻度為2n。算法（2）只用了一個(gè)循環(huán)，其循環(huán)體語(yǔ)句執(zhí)行次數(shù)為n，即該函數(shù)的語(yǔ)句頻度為

4、n。所以算法（1）與算法（2）相比較，算法（1）的時(shí)間效率更好。但它們的時(shí)間復(fù)雜度都為O（n），這說(shuō)明：隨著n值的增大，這兩個(gè)函數(shù)執(zhí)行時(shí)間的增長(zhǎng)率相同，都是線性增長(zhǎng)的。13.【解】由題意，設(shè)計(jì)程序如下：#include#includestructstuInfointnumname[18]intscevoidinputInfo(structstuInfostus[]intn)輸入n個(gè)同學(xué)信息存于數(shù)組stus中intif(i=0istus[

5、k].sce)k=jif(k!=i)temp=stus[i]stus[i]=stus[k]stus[k]=tempvoidoutputInfo(structstuInfostus[]intn)輸出數(shù)組stus中n個(gè)同學(xué)信息報(bào)表intiprintf(“%6s%17s%6sn““學(xué)號(hào)““姓名““成績(jī)“)；f(i=0ini)printf(“%6d%17s%6dn“stus[i].numstus[i].namestus[i].sce)intma