計(jì)算機(jī)軟件基礎(chǔ)復(fù)習(xí)

1、5有一線(xiàn)性表存儲(chǔ)在一個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表L中，寫(xiě)岀計(jì)算線(xiàn)性表元素個(gè)數(shù)的算法。P44intlength(NODE*head)NODE*p;intj;p=head-next;j=0；while(p!=head)p=p-next;j+;returnj;7.已知指針ha和hb分別指向兩個(gè)單鏈表的頭結(jié)點(diǎn)，且頭結(jié)點(diǎn)的數(shù)據(jù)域中存放鏈表的長(zhǎng)度，試寫(xiě)一算法將這兩個(gè)鏈表連接在一起(即令其中一個(gè)表的首元結(jié)點(diǎn)在另一個(gè)表的最后一個(gè)節(jié)點(diǎn)之后)，he指向連接后的鏈表的頭結(jié)點(diǎn)，并要求算法以盡可能短的時(shí)間完成連接運(yùn)算。請(qǐng)分析你的算法的時(shí)間復(fù)雜度。voidmerge(NODE*ha,NODE*hb)NODE*p,*longli

2、nk,*shortlink;he=(NODE*)malloc(sizeof(NODE);if(ha-datadata)shortlink=ha;longlink=hb;elseshortlink=hb;longlink=ha;he-data=ha-data+hb-data;he-next=shortlink-next;p=he;while(p-next!=null)p=p-next;p-next=longlink-next;free(ha);free(hb);時(shí)間復(fù)雜度為O(n)時(shí)間復(fù)雜度的概念定義：一般情況下，算法的基本操作重復(fù)執(zhí)行的次數(shù)是模塊n的某一個(gè)函數(shù)f(n),因此，算法的時(shí)間復(fù)雜度記

3、做：T(n)=0(f(n)。在實(shí)際分析中，關(guān)注的是頻度的數(shù)量級(jí)，即按重復(fù)執(zhí)行次數(shù)最多的語(yǔ)句確定算法的時(shí)間復(fù)雜度。分析：隨著模塊n的增大，算法執(zhí)行的時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率成正比，所以f(n)越小，算法的時(shí)間復(fù)雜度越低，算法的效率越高。方法：在計(jì)算時(shí)間復(fù)雜度的時(shí)候，先找岀算法的基本操作，然后根據(jù)相應(yīng)的各語(yǔ)句確定它的執(zhí)行次數(shù)，再找岀T(n)的同數(shù)量級(jí)(它的同數(shù)量級(jí)有以下：1，Log2n，n，nLog2n，n的平方，n的三次方，2的n次方，n!)，找出后，f(n)=該數(shù)量級(jí)，若T(n)/f(n)求極限可得到一常數(shù)c，則時(shí)間復(fù)雜度T(n)=0(f(n)時(shí)間復(fù)雜度的概念例：算法：for(i=1;i

4、=n;+i)for(j=1;j=n;+j)cij=0;/該步驟屬于基本操作執(zhí)行次數(shù)：n的平方次for(k=1;kdata=x;p-next=rear-next;rear-next=p;rear=p;11.假設(shè)以帶頭節(jié)點(diǎn)的循環(huán)單鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向?qū)ξ苍毓?jié)點(diǎn)(不設(shè)頭指針)，試編寫(xiě)相應(yīng)的入列和岀列算法。P44structqnode/出列操作intdata;structqnode*next;typedefstructqnodeQNODE;QNODE*rear;voiddelqueue()intx;QNODE*p;if（rear=rear-next）printf（鏈隊(duì)列已空，即下溢。n

5、”）;exit（1）;elsep=rear-next-next;rear-next-next=p-next;x=p-data;free（p）;13.試將下列稀疏矩陣A用三元組形式來(lái)表示。P45r0300-700000A=8000020000000-1300r0300-700000A=8000020000000-1300（5,5，5）一（I，J,K）（1,2，3）1表示總行數(shù)（1,5，-7）J表示總列數(shù)（3，1，8）K表示非零元（4，1，20）素個(gè)數(shù)（5,3，-13）行號(hào)列號(hào)值域05551123215-7331844120553-13已知一棵樹(shù)邊的集合為（I，M），（I，N），（E，I），（B，

6、E），（B，D），（A，B），（G，J），（G，K），（C，G），（C，F(xiàn)），（H，L），（C，H），（A，C），畫(huà)出這棵樹(shù)，并回答下列問(wèn)題：（1）哪個(gè)是根結(jié)點(diǎn)？哪些是葉子結(jié)點(diǎn)？哪些是結(jié)點(diǎn)G的雙親？哪些是結(jié)點(diǎn)G的孩子？（3）哪些是結(jié)點(diǎn)E的兄弟？哪些是結(jié)點(diǎn)F的兄弟？（4）結(jié)點(diǎn)B和N的層次號(hào)分別是什么？（5）樹(shù)的深度是多少？以結(jié)點(diǎn)C為根的子樹(shù)的深度是多少？P72A是根節(jié)點(diǎn)，D、F、J、K、L、M、N為葉子節(jié)點(diǎn)C是G的雙親節(jié)點(diǎn)，J、K是G的孩子節(jié)點(diǎn)D是E的兄弟節(jié)點(diǎn)，G、H是F的兄弟B的層次號(hào)為2，N的層次號(hào)為5A數(shù)的深度為5，以節(jié)點(diǎn)C為根的子樹(shù)的深度為3O二叉樹(shù)11.將題圖3-3中的森林轉(zhuǎn)化為相應(yīng)的

7、二叉樹(shù)，并將得到的二叉樹(shù)分別按先序、中序、后序序列進(jìn)行遍歷，寫(xiě)岀遍歷的結(jié)點(diǎn)序列。P73答：具有最小帶權(quán)路徑長(zhǎng)度的二叉樹(shù)叫作霍夫曼樹(shù)。題圖3-3森林先序遍歷1,2,3,4,6,5,7,8,9,10,11,12,14,13中序遍歷3,6,4,7,8,5,2,1,10,9,14,12,13,11后序遍歷6,8,7,5,4,3,2,10,14,13,12,11,9,1什么叫霍夫曼樹(shù)？按給出的一組權(quán)值4,2，3，5，7，8，建立一棵霍夫曼樹(shù)。P7315.畫(huà)出對(duì)題圖3-5的深度優(yōu)先生成樹(shù)和廣度優(yōu)先生成樹(shù)。P73用以下關(guān)鍵字序列構(gòu)造兩個(gè)哈希表(每個(gè)哈希表的地址空間為016):(Jan,Feb,Mar,Apr

8、,May,June,July,Aug,Sep,Oct,Nov,Dec)。H(x)=iDIV2，其中i為關(guān)鍵字x中第一個(gè)字母在字母表中的序號(hào)。用線(xiàn)性探測(cè)再散列法處理沖突；用鏈地址法處理沖突。并分別求這兩個(gè)哈希表在等概率情況下查找成功的平均查找長(zhǎng)度。P97abcdefghjklm12345678910111213noPqrstuvwxyz14151617181920212223242526Hj=(H(key)+d)MODm=(H(x)+di)MOD17i=1,2,16JanFebMarAprMayJuneJulyAugSepOctNovDeci10613113101011915144H(x)536

9、065509772Hi7891101112AprAugDecFebJanMarMayJunjJulySepOctNovJanFebMarAprMayJuneJulyAugSepOctNovDeci10613113101011915144H(x)53606550977201a3-A56-78-9AprDecFebJanMarOctSepAAAJuly有一組待排序的記錄，其關(guān)鍵字為18，5,20，30，9，27,6，14,45,22。寫(xiě)出用下列方法進(jìn)行排序時(shí)，每一趟排序后的結(jié)果及關(guān)鍵字比較次數(shù)。直接插入排序；簡(jiǎn)單選擇排序；冒泡排序；快速排序；歸并排序。P97直接插入排序初始狀態(tài)1852030927

10、6144522第一趟51820309(276144522第二趟51820309276144522第三趟51820309276144522第四趟59182030276144522第五趟59182027306144522第六趟5691820(2730144522第七趟56914182027304522第八趟56914182022273045第九趟56914182022273045簡(jiǎn)單選擇排序初始狀態(tài)18520309276144522第一趟51820309276144522第二趟56203092718144522第三趟56930202718144522第四趟56914202718304522第五趟5

11、6914182720304522第六趟56914182027304522第七趟56914182022304527第八趟56914182022274530第九趟56914182022273045初始狀態(tài)18520309276144522第一趟51820927614302245第二趟51892061427223045第三趟59186142022273045第四趟59614182022273045第五趟56914182022273045第六趟56914182022273045第七趟56914182022273045第八趟56914182022273045第九趟56914182022273045冒泡排

12、序快速排序初始狀態(tài)18520309276144522第一趟14569182730204522第二趟95614182220274530第三趟65914182022273045第四趟56914182022273045第五趟第六趟第七趟第八趟第九趟歸并排序初始狀態(tài)18520309276144522第一趟51820309276142245第二趟51820306914272245第三趟56914182027302245第四趟56914182022273045第五趟第六趟第七趟第八趟第九趟針對(duì)下圖所示的學(xué)生一課程數(shù)據(jù)庫(kù)，試用關(guān)系代數(shù)完成如下查詢(xún)求選修了數(shù)據(jù)庫(kù)”課程的學(xué)生學(xué)號(hào)；求選修了全部課程的學(xué)生學(xué)號(hào)；求

13、選修了操作系統(tǒng)”課程的學(xué)生學(xué)號(hào)，姓名及成績(jī)。求學(xué)生李勇”選修的課程號(hào)，課程名及成績(jī)。WgES11TgemSO.If.HIPT5-JJWTO?ZIP1*力ftISL1AMjHCu-Mm15331.I彳KfTFKCi4S74I7PAECALilS*解：(1)Sno(Cname數(shù)據(jù)庫(kù)(Course)SC)(2)Sno,Cno(SC)Cno(Course)(3)Sno,Sname,Gade(Cname操作系統(tǒng)(Course)SCSno,Sname(Student)(4)cno,cname,Grade(snoSname李勇(Student)CourseSC)10.設(shè)有一個(gè)SPJ數(shù)據(jù)庫(kù)，包括S,P,J，S

14、P同個(gè)關(guān)系模式：S(SNO,SNAME，CITY)；P(PNO，PNAME，COLOR，WEIGHT)；J(JNO，JNAME，CITY)；SPJ(SNO,PNO，JNO，QTY)；P206供應(yīng)商表S由供應(yīng)商代碼(SNO)、供應(yīng)商姓名(SNAME)、供應(yīng)商所在城市(CITY)組成；零件表P由零件代碼(PNO)、零件名(PNAME)、顏色(COLOR)、重量(WEIGHT)組成；工程項(xiàng)目表J由工程項(xiàng)目代碼(JNO)、工程項(xiàng)目名(JNAME)、工程項(xiàng)目所在城市(CITY)組成；供應(yīng)情況表SPJ由供應(yīng)商代碼(SNO)、零件代碼(PNO)、工程項(xiàng)目代碼(JNO)、供應(yīng)數(shù)量(QTY)組成，表示某供應(yīng)商供

15、應(yīng)某種零件給某工程項(xiàng)目的數(shù)量為QTYo針對(duì)上題的四個(gè)表，請(qǐng)用SQL語(yǔ)言完成以下各項(xiàng)操作：JAtCTTTFT4TI沖易IFrYMiHCnJNOrnrKMCFSI3幻事才Pl12：PI=：tJLhP1Jl.ZOO艸ITjq-ft艙爵PInS?曙赴14X!PSJL顧網(wǎng)i+覽皈廠(chǎng)眄122P4W幻ftJMkicIriJIJw請(qǐng)用SQL語(yǔ)言建立這四個(gè)表。N4治i朋7DO(1)找出所有供應(yīng)商的姓名和所在城市；找岀所有零件的名稱(chēng)、顏色、重量；找出使用供應(yīng)商S1所供零件的工程號(hào)碼；找出工程項(xiàng)目J2使用的各種零件的名稱(chēng)及其數(shù)量；找岀上海廠(chǎng)商供應(yīng)的所有零件號(hào)碼；找岀使用上海產(chǎn)的零件的工程名稱(chēng)；把全部紅色零件的顏色改

16、成藍(lán)色；從供應(yīng)商關(guān)系中刪除S2的記錄，并從供應(yīng)情況關(guān)系中刪除相應(yīng)的記錄；將(S2,J6,P4,500)插入供應(yīng)情況關(guān)系。創(chuàng)建四個(gè)表創(chuàng)建S表CREATETABLES(SNOCHAR(20)NOTNULLUNIQUE,SNAMECHAR(10),CITYCHAR(10);創(chuàng)建P表CREATETABLEP(PNOCHAR(20)NOTNULLUNIQUE,PNAMECHAR(10),COLORCHAR(10),WEIGHTINT);創(chuàng)建J表CREATETABLEJ(JNOCHAR(20)NOTNULLUNIQUE,JNAMECHAR(10),CITYCHAR(10);創(chuàng)建SPJ表CREATETABL

17、ESPJ(SNOCHAR(20)NOTNULL,PNOCHAR(20),JNOCHAR(20),QTYINT);(1)找出所有供應(yīng)商的姓名和所在城市;SELECTSNAMEQTYFROMS;找岀所有零件的名稱(chēng)、顏色、重量；SELECTPNAME,COLOR,WEIGHTFROMP;找出使用供應(yīng)商S1所供零件的工程號(hào)碼；SELECTJNOFROMSPJWHERESNO=S1找出工程項(xiàng)目J2使用的各種零件的名稱(chēng)及其數(shù)量；SELECTPNAME,QTYFROMP,SPJWHEREP.PNO=SPJ.PNOANDJNO=J2;找岀上海廠(chǎng)商供應(yīng)的所有零件號(hào)碼；SELECTPNOFROMS,SPJWHERES.SNO=SPJ.SNOANDCITY=上海；找岀使用上海產(chǎn)的零件的工