PAGE第1頁共4頁清華大學試卷（本科生專用）考場紀律學生應試時必須攜帶學生證，以備查對，學生必須按照監考老師指定的座位就坐。除答卷必須用的筆、橡皮及老師指定的考試用具外，不得攜帶任何書籍、筆記、草稿紙等。答卷時不準互借文具（包括計算器）。題紙上如有字跡不清等問題，學生應舉手請監考教師解決。學生應獨立答卷，嚴禁左顧右盼、交頭接耳、抄襲或看別人答卷等各種形式的作弊行為，如有違反，當場取消其考試資格，答卷作廢。在規定的時間內答卷，不得拖延。交卷時間到，學生須在原座位安靜地等候監考教師收卷后，方可離開考場。系別班號202級班學號姓名成績考試課程日期202年月日閱卷老師題號一二三四五六七八九十十一十二總分成績說明：請務必在每個源程序的最開頭寫上你的姓名、學號和班級。一、（20分）編寫一個程序，輸入三個正整數min，max和factor，然后對于從min到max之間的每一個整數（包括min和max），如果它能夠被factor整除的話，就把它打印出來。【5分鐘】 輸入格式：輸入只有一行，即三個正整數min、max和factor。 輸出格式：輸出有N行，每一行表示符合條件的一個整數，按照遞增順序排列。 樣例：樣例輸入樣例輸出1103369二、（20分）編寫一個程序，讀入一組整數，這組整數是按照從小到大的順序排列的，它們的個數N也是由用戶輸入的，最多不會超過20。然后程序將對這個數組進行統計，把出現次數最多的那個數組元素值打印出來。如果有兩個元素值出現的次數相同，即并列第一，那么只打印比較小的那個值。【20分鐘】 輸入格式：第一行是一個整數N，N20；接下來有N行，每一行表示一個整數，并且按照從小到大的順序排列。 輸出格式：輸出只有一行，即出現次數最多的那個元素值。 樣例：樣例輸入樣例輸出5100150150200250150三、（20分）編寫一個程序，輸入一個句子，然后統計出這個句子當中不同的單詞個數。例如：對于句子“onelittletwolittlethreelittleboys”，總共有5個不同的單詞：one,little,two,three,boys。【20分鐘】 說明：（1）由于句子當中包含有空格，所以應該用gets函數來輸入這個句子；（2）輸入的句子當中只包含英文字符和空格，單詞之間用一個空格隔開；（3）不用考慮單詞的大小寫，假設輸入的都是小寫字符；（4）句子長度不超過100個字符。 輸入格式：輸入只有一行，即一個英文句子。 輸出格式：輸出只有一行，是一個整數，表示句子中不同單詞的個數。 樣例：樣例輸入樣例輸出onelittletwolittlethreelittleboys5四、（10分）一個數如果從左往右讀和從右往左讀數字是完全相同的，則稱這個數為回文數，比如898，1221，15651都是回文數。編寫一個程序，輸入兩個整數min和max，然后對于從min到max之間的每一個整數（包括min和max），如果它既是一個回文數又是一個質數，那么就把它打印出來。【15分鐘】 輸入格式：輸入只有一行，即兩個正整數min和max。 輸出格式：輸出有N行，每一行表示符合條件的一個整數，按照遞增順序排列。如果找不到符合條件的整數，則打印字符串"none"。 樣例：樣例輸入樣例輸出500800727757787797五、（20分）采用動態鏈表來實現一個堆管理器（heapmemorymanager）。堆管理器的功能是這樣的：（1）整個堆空間的大小是固定的，在系統運行的某個時刻，整個堆空間被劃分為若干個塊，有的塊是空閑的，有的塊已經被某個程序所占用，這樣就形成了空閑塊和占用塊交錯的情形。例如，在圖1當中，整個堆空間的大小為1200個字節，總共分為5塊區域，其中，第一塊區域的起始地址為0，大小為200個字節，被程序1所占用；第二塊區域的起始地址為200，大小為200字節，被程序2占用；第三塊區域的起始地址為400，大小為400字節，現在是空閑的；第四塊區域的起始地址為800，大小為200字節，被程序3占用；第五塊區域的起始地址為1000，大小為200字節，現在是空閑的。（2）用戶程序可以用malloc函數來申請一塊堆空間，假設申請的空間大小為size，那么系統就會從左往右，對整個堆空間進行掃描，尋找一塊大小超過size的空閑區域，如果沒有找到這樣的空閑區域，那么這次內存申請就失敗了；如果能夠找到這樣的區域，那么就從這個空閑區當中切下一塊，把它分配給用戶程序，切完后的剩余部分仍然是一塊空閑區域，只不過它的大小變小了。例如，對于圖1來說，假設這時又有一個用戶程序來申請200個字節的一塊空間，那么系統就會把起始地址為400的那塊空閑區域一分為二，一部分分配給這個用戶程序，另一部分仍然是一塊空閑區域，如圖2所示。（3）當用戶程序執行完畢后，可以用free函數來釋放它所占用的空間。例如，在圖2當中，如果程序2所占用的空間被釋放了，那么對于起始地址為200、大小為200字節的這塊區域來說，它的狀態就變成了空閑塊。另外，為了提高管理效率，當某一塊內存區域被釋放后，還要去看一下它的左鄰右舍，看它們是否是空閑的，如果是的話，就要與它們進行合并，形成一個更大的空閑塊。例如，在圖2當中，如果程序4運行結束，它占用的空間被釋放了，那么就要把這塊空間和它右邊的那塊空閑塊進行合并，從而得到一塊更大的空閑塊，如圖1所示。020040080010001200

020040080010001200程序1占用程序2占用空閑區程序3占用空閑區 圖1.占用區與空閑區交錯020040060080010001200

020040060080010001200程序1占用程序2占用程序4占用空閑區程序3占用空閑區 圖2.程序4申請一塊200個字節的堆空間

現在要求用動態鏈表的方法來實現這個堆管理器。即對于每一塊區域來說，用一個鏈表結點來描述，包括這塊區域的起始地址、大小、狀態（占用或空閑）等信息，這樣，整個堆空間就可以用一條線性鏈表來表示。任務描述：編寫一個程序，首先輸入內存空間的初始狀態，從而建立相應的鏈表。然后再輸入一些內存申請或釋放的操作，并根據這些操作來修改鏈表，如增加、刪除或合并鏈表結點；最后把更新以后的內存空間狀態打印出來。輸入格式：第一行是一個整數N，表示在初始狀態，堆空間被劃分為多少個塊。接下來有N行，每一行是三個整數si，ti，fi，其中，si表示第i塊區域的起始地址，ti表示第i塊區域的大小，fi表示第i塊區域的狀態（0表示空閑，1表示被占用）。接下來的一行是一個整數M，表示有多少個內存請求需要處理，再接下來有M行，每一行是兩個整數di和wi，其中，di表示內存請求的類型，如果di等于，表示申請一塊內存區域，因此wi中存放的是需要申請的空間大小；如果di等于，表示釋放一塊內存區域，因此wi中存放的是需要釋放的這塊空間的起始地址。 輸出格式：系統在處理完上述的M個內存請求之后，會得到一個新的狀態，現在需要把這個狀態打印出來。第一行是一個整數K，表示內存中有多少個塊，接下來有K行，每一行是三個整數si，ti，fi，其中，si表示第i塊區域的起始地址，ti表示第i塊區域的大小，fi表示第i塊區域的狀態（0表示空閑，1表示被占用） 樣例：下面這個樣例描述的是：初始狀態為圖，然后有兩個內存請求，一是申請個字節的空間，這樣就得到了圖；二是再把剛剛申請的這塊區域釋放，這樣又回到了圖。樣例輸入樣例輸出5020012002001400400080020011000200021200040050200120020014004000800200110002000六、（10分）小張是一家餐館的采購人員，一天他去市場上買魚。在魚攤上總共有N條魚，每條魚的重量為ti。出于成本考慮，小張最多只能買T公斤的魚，而為了攜帶方便，他又希望買的魚的條數越少越好。所以他必須從這N條魚當中選擇若干條，使得這些魚的總重量L盡可能地大（L≤T），并且在此前提下，魚的條數又盡可能地少。 參數限制：0