《數(shù)據(jù)結(jié)構(gòu)》第一次上機練習(xí)題班級：通信1105,1106,地點：南一樓東203，

時間：第3,7,10周周一晚上第9至第12節(jié)課2.

班級：通信中英班地點：南一樓東208

時間：第3，7，10周周四早晨第1節(jié)至第4節(jié)課上機要求：上機內(nèi)容為設(shè)計一些算法，編譯經(jīng)過。考評方式是對每一個算法，利用計算機屏幕截屏方式，截取兩張圖，一張是程序本身圖，一張是程序運行結(jié)果圖。圖片命名方式為：學(xué)號_姓名_算法01_1.jpg,學(xué)號_姓名_算法01_2.jpg。學(xué)生程序設(shè)計截屏圖，將自行保留，依據(jù)需要抽查一些學(xué)生截屏圖。每個同學(xué)需要在程序和程序結(jié)果中間突出地顯示出學(xué)生信息，學(xué)號，姓名，班級，以及適當(dāng)注釋和輸出結(jié)果說明。1/71《數(shù)據(jù)結(jié)構(gòu)》第一次上機練習(xí)題練習(xí)題劃分：每位同學(xué)上機完成6道題練習(xí)，出12張截屏圖（截屏圖為JPG格式，自行保留至U盤，晚上上課時帶到課堂）。練習(xí)題12道和應(yīng)用題2道。學(xué)號最終一位為奇數(shù)做奇數(shù)練習(xí)題，即學(xué)號位數(shù)為1,3,5,7,9做練習(xí)題1,3,5,7,9,11。學(xué)號最終一位為偶數(shù)做偶數(shù)練習(xí)題，即學(xué)號位數(shù)為0,2,4,6,8做練習(xí)題2,4,6,8,10,12。注意：全部算法必須事先在上機前在初稿本上完成，上機只是為了進(jìn)行測試。全部算法均生成EXE可執(zhí)行文件，上機測試后請保留這些文件，等候抽查。2/72【問題01】(遞歸，鏈表)假設(shè)一個不帶頭結(jié)點單鏈表h中全部結(jié)點數(shù)據(jù)域都為整數(shù)，設(shè)計一個遞歸算法求其中最大值？【問題02】(次序表)設(shè)將n(n>1)個整數(shù)存放到一維數(shù)組R中。設(shè)計一個時間和空間兩方面盡可能高效算法，將R中整數(shù)序列循環(huán)左移p(0<p<n)個位置，即將R中數(shù)據(jù)序列(X0,X1,…,Xn-1)變換為(Xp,Xp+1,…,Xn-1,X1,…,Xp-1)，要求依據(jù)設(shè)計思想，設(shè)計算法，關(guān)鍵之處給出注釋。3/73【問題03】（次序表）設(shè)有一個次序表L，其元素為整型數(shù)據(jù)，設(shè)計一個算法將L中全部小于0整數(shù)放在前半部分，大于等于0整數(shù)放在后半部分。【問題04】（單鏈表）設(shè)C={a1,b1,a2,b2,…,an,bn}為一線性表，采取帶頭結(jié)點hc單鏈表存放，設(shè)計一個就地算法，將其拆分為兩個線性表A={a1,a2,…,an},B={b1,b2,…,bn}，拆分后線性表分別用帶頭結(jié)點單鏈表存放。【問題05】（單鏈表）設(shè)C={a1,b1,a2,b2,…,an,bn}為一線性表，采取帶頭結(jié)點hc單鏈表存放，設(shè)計一個就地算法，將其拆分為兩個線性表A={a1,a2,…,an},B={bn,bn-1,…,b1}，拆分后線性表分別用帶頭結(jié)點單鏈表存放。4/74【問題06】（單鏈表）用單鏈表表示集合，設(shè)計一個算法求兩集合交集，并將結(jié)果存放入另一個單鏈表中。13^4A【問題07】（單鏈表）用單鏈表表示集合，設(shè)計一個算法求兩集合并集，并將結(jié)果存放入另一個單鏈表中。15^3B1…^3A∩B13A∪B4^55/75【問題8】（單鏈表）已知一個帶表頭結(jié)點單鏈表只給出了頭指針list。在不改變鏈表前提下，設(shè)計一個盡可能高效算法，查找鏈表中倒數(shù)第k個位置上結(jié)點(k為正整數(shù))。若查找成功，算法輸出該結(jié)點data域值；不然，返回0。要求：依據(jù)設(shè)計思想和步驟，給出算法，關(guān)鍵之處給出注釋。【問題9】（雙鏈表）設(shè)有一個帶頭結(jié)點雙鏈表L，設(shè)計一個算法用于刪除全部值為x結(jié)點，假設(shè)這么結(jié)點不唯一。6/76【問題10】（循環(huán)雙鏈表）設(shè)有一個帶頭結(jié)點循環(huán)雙鏈表L=(a1,a2,…,an-1,an)。設(shè)計一個時間復(fù)雜度為O(n)算法，將L改造成L=(a1,a3,a5,…,an,…,a6,a4,a2)。【問題11】（棧）