2014春 算法與數(shù)據(jù)結構 期中 上機考試(開卷)

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