2014春 算法與數(shù)據(jù)結(jié)構(gòu) 期中 上機(jī)考試(開卷)

2014春算法與數(shù)據(jù)結(jié)構(gòu)期中上機(jī)考試(開卷)說(shuō)明：(1)每?jī)扇艘唤M選1題。不同的組所選擇的題目不能相同。(2)開卷考試。(3)考試時(shí)間90分鐘。(4)所有輸入輸出都是對(duì)文件操作。(5)工程構(gòu)建時(shí)界面、數(shù)據(jù)與業(yè)務(wù)處理是分離的；函數(shù)的申明、定義與實(shí)現(xiàn)分別在不同的文件中，也是分離的。1、用十字鏈表表示稀疏矩陣，并實(shí)現(xiàn)稀疏矩陣加法。2、試編寫算法求一元多項(xiàng)式Pn(x)=a0+a1x+a2x2+a3x3+…anxn的值Pn(x0)，并確定算法中的每一語(yǔ)句的執(zhí)行次數(shù)和整個(gè)算法的時(shí)間復(fù)雜度，要求時(shí)間復(fù)雜度盡可能的小，規(guī)定算法中不能使用求冪函數(shù)。3、已知線性表L遞增有序。試寫一算法，將X插入到L的適當(dāng)位置上，以保持線性表L的有序性。4、寫一算法，從順序表中刪除自第i個(gè)元素開始的k個(gè)元素。5、已知線性表中的元素（整數(shù)）以值遞增有序排列，并以單鏈表作存儲(chǔ)結(jié)構(gòu)。試寫一高效算法，刪除表中所有大于mink且小于maxk的元素（若表中存在這樣的元素），分析你的算法的時(shí)間復(fù)雜度（注意：mink和maxk是給定的兩個(gè)參變量，它們的值為任意的整數(shù)）。6、試分別以不同的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)線性表的就地逆置算法，即在原表的存儲(chǔ)空間將線性表（a1,a2...,an）逆置為（an,an-1,...,a1）。（1）以一維數(shù)組作存儲(chǔ)結(jié)構(gòu)，設(shè)線性表存于a(1:arrsize)的前elenum個(gè)分量中。（2）以單鏈表作存儲(chǔ)結(jié)構(gòu)。7、假設(shè)兩個(gè)按元素值遞增有序排列的線性表A和B，均以單鏈表作為存儲(chǔ)結(jié)構(gòu)，請(qǐng)編寫算法，將A表和B表歸并成一個(gè)按元素值遞減有序的排列的線性表C，并要求利用原表（即A表和B表的）結(jié)點(diǎn)空間存放表C.8、假設(shè)有一個(gè)循環(huán)鏈表的長(zhǎng)度大于1，且表中既無(wú)頭結(jié)點(diǎn)也無(wú)頭指針。已知s為指向鏈表某個(gè)結(jié)點(diǎn)的指針，試編寫算法在鏈表中刪除指針s所指結(jié)點(diǎn)的前趨結(jié)點(diǎn)。9、已知有單鏈表表示的線性表中含有三類字符的數(shù)據(jù)元素（如字母字符、數(shù)字字符和其它字符），試編寫算法來(lái)構(gòu)造三個(gè)以循環(huán)鏈表表示的線性表，使每個(gè)表中只含同一類的字符，且利用原表中的結(jié)點(diǎn)空間作為這三個(gè)表的結(jié)點(diǎn)空間，頭結(jié)點(diǎn)可另辟空間。10、設(shè)線性表A=(a1,a2,…,am)，B=(b1,b2,…,bn)，試寫一個(gè)按下列規(guī)則合并A、B為線性表C的算法，使得：C=(a1,b1,…,am,bm,bm+1,…,bn)當(dāng)m≤n時(shí)；或者C=(a1,b1,…,an,bn,an+1,…,am)當(dāng)m>n時(shí)。線性表A、B、C均以單鏈表作為存儲(chǔ)結(jié)構(gòu)，且C表利用A表和B表中的結(jié)點(diǎn)空間構(gòu)成。注意：?jiǎn)捂湵淼拈L(zhǎng)度值m和n均未顯式存儲(chǔ)。11、將一個(gè)用循環(huán)鏈表表示的稀疏多項(xiàng)式分解成兩個(gè)多項(xiàng)式，使這兩個(gè)多項(xiàng)式中各自僅含奇次項(xiàng)或偶次項(xiàng)，并要求利用原鏈表中的結(jié)點(diǎn)空間來(lái)構(gòu)成這兩個(gè)鏈表。12、建立一個(gè)帶頭結(jié)點(diǎn)的線性鏈表，用以存放輸入的二進(jìn)制數(shù)，鏈表中每個(gè)結(jié)點(diǎn)的data域存放一個(gè)二進(jìn)制位。并在此鏈表上實(shí)現(xiàn)對(duì)二進(jìn)制數(shù)加1的運(yùn)算。13、設(shè)多項(xiàng)式P(x)采用課本中所述鏈接方法存儲(chǔ)。寫一算法，對(duì)給定的x值，求P(x)的值。14、約瑟夫環(huán)問(wèn)題約瑟夫問(wèn)題的一種描述是：編號(hào)為1，2，…，n的n個(gè)人按順時(shí)針方向圍坐一圈，每人持有一個(gè)密碼（正整數(shù)）。一開始任選一個(gè)整數(shù)作為報(bào)數(shù)上限值m,從第一個(gè)人開始順時(shí)針自1開始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針方向上的下一個(gè)人開始重新從1報(bào)數(shù)，如此下去，直至所有的人全部出列為止。試設(shè)計(jì)一個(gè)程序，求出出列順序。利用單向循環(huán)鏈表作為存儲(chǔ)結(jié)構(gòu)模擬此過(guò)程，按照出列順序打印出各人的編號(hào)。例如m的初值為20；n=7，7個(gè)人的密碼依次是：3，1，7，2，4，8，4，出列的順序?yàn)?，1，4，7，2，3，5。15、假設(shè)表達(dá)式由單字母變量和雙目四則運(yùn)算算符構(gòu)成。試寫一個(gè)算法，將一個(gè)通常書寫形式（中綴）且書寫正確的表達(dá)式轉(zhuǎn)換為逆波蘭式（后綴）。16、假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾元素結(jié)點(diǎn)（注意不設(shè)頭指針），試編寫相應(yīng)的隊(duì)列初始化、入隊(duì)列和出隊(duì)列的算法。17、要求循環(huán)隊(duì)列不損失一個(gè)空間全部都能得到利用,設(shè)置一個(gè)標(biāo)志域tag,以tag為0或1來(lái)區(qū)分頭尾指針相同時(shí)的隊(duì)列狀態(tài)的空與滿，請(qǐng)編寫與此結(jié)構(gòu)相應(yīng)的入隊(duì)與出隊(duì)算法。18、停車場(chǎng)管理設(shè)停車場(chǎng)是一個(gè)可停放n輛車的狹長(zhǎng)通道，且只有一個(gè)大門可供汽車進(jìn)出。在停車場(chǎng)內(nèi)，汽車按到達(dá)的先后次序，由北向南依次排列（假設(shè)大門在最南端）。若車場(chǎng)內(nèi)已停滿n輛車，則后來(lái)的汽車需在門外的便道上等候，當(dāng)有車開走時(shí)，便道上的第一輛車即可開入。當(dāng)停車場(chǎng)內(nèi)某輛車要離開時(shí)，在它之后進(jìn)入的車輛必須先退出車場(chǎng)為它讓路，待該輛車開出大門后，其它車輛再按原次序返回車場(chǎng)。每輛車離開停車場(chǎng)時(shí)，應(yīng)按其停留時(shí)間的長(zhǎng)短交費(fèi)（在便道上停留的時(shí)間不收費(fèi)）。試編寫程序，模擬上述管理過(guò)程。要求以順序棧模擬停車場(chǎng)，以鏈隊(duì)列模擬便道。從終端讀入汽車到達(dá)或離去的數(shù)據(jù)，每組數(shù)據(jù)包括三項(xiàng)：①是“到達(dá)”還是“離去”；②汽車牌照號(hào)碼；③“到達(dá)”或“離去”的時(shí)刻。與每組輸入信息相應(yīng)的輸出信息為：如果是到達(dá)的車輛，則輸出其在停車場(chǎng)中或便道上的位置；如果是離去的車輛，則輸出其在停車場(chǎng)中停留的時(shí)間和應(yīng)交的費(fèi)用。19、商品貨架管理。商品貨架可以看成一個(gè)棧，棧頂商品的生產(chǎn)日期最早，棧底商品的生產(chǎn)日期最近。上貨時(shí)，需要倒貨架，以保證生產(chǎn)日期較近的商品在較下的位置。用隊(duì)列和棧作為周轉(zhuǎn)，實(shí)現(xiàn)上述管理過(guò)程。20、編寫算法，實(shí)現(xiàn)串的基本操作StrReplace(S,T,V)。21、假設(shè)以塊鏈結(jié)構(gòu)表示串，塊的大小為1，且附設(shè)頭結(jié)點(diǎn)。試編寫算法，實(shí)現(xiàn)串的下列基本操作：StrAsign(S,chars)；StrCopy(S,T)；StrCompare(S,T)；StrLength(S)；StrCat(S,T)；