東華大學(xué)計(jì)算機(jī)學(xué)院研究生復(fù)試上機(jī)考真題

1、2015年碩士學(xué)位研究生招生復(fù)試筆試試題考試科目: C語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)算法上機(jī)測(cè)試考試時(shí)間120分鐘注意事項(xiàng):1、源程序都在D:TEST文件夾下,請(qǐng)先將該“TEST”文件夾改名為“準(zhǔn)考證號(hào)_姓名”,其中準(zhǔn)考證號(hào)是初試時(shí)的15位準(zhǔn)考證號(hào);2、考試結(jié)束后,首先刪除VC+ 6.0自動(dòng)生成的debug文件夾,然后使用壓縮軟件將上述考生文件夾中所有內(nèi)容打包(包括里面所有文件,比如工程文件等。除上述debug文件夾外,不得刪除任何考試過(guò)程中產(chǎn)生的文件,文件名為“準(zhǔn)考證號(hào)_姓名.rar”,然后將該文件通過(guò)教學(xué)系統(tǒng)的學(xué)生端的“傳文件給教師”功能上傳到服務(wù)器。注意:1文件上傳后,需到監(jiān)考老師處確認(rèn)方可離開(kāi)考場(chǎng)。如

2、果未經(jīng)監(jiān)考老師確認(rèn),并且文件由于某種原因上傳未成功,考試成績(jī)以0分計(jì)。2上傳的壓縮包解壓后將立即看到所有文件,壓縮包中不得包含任何子文件夾。壓縮包被打開(kāi)后的圖示見(jiàn)附錄,其中附圖a和附圖b錯(cuò)誤,附圖c正確。3、如果已經(jīng)上傳,需要修改然后再上傳的,在壓縮包的文件名后加編號(hào)2、3、4等,形如:“考號(hào)_姓名2.rar”、“考號(hào)_姓名3.rar”。在監(jiān)考老師處確認(rèn)時(shí),請(qǐng)求監(jiān)考老師將老文件刪除。4、所有提供的文件(包括C源文件,不得更改文件名,也不得更改其內(nèi)部結(jié)構(gòu)(詳見(jiàn)題目中的紅字。5、所有程序需要在VC環(huán)境中運(yùn)行,結(jié)果正確方可。比如,程序填空,不能僅將空填好,而是需要運(yùn)行程序,進(jìn)行測(cè)試,確保正確。6、本

3、考試共包括1道程序改錯(cuò)、1道程序填空、3道程序編寫(xiě)題,分?jǐn)?shù)分別為:30、 15、 15、 20、 20。7、考試題文字描述見(jiàn)下頁(yè),C程序見(jiàn)考生文件夾下相應(yīng)文件。(1 (30分給定程序modi.c中,程序的功能是:輸出100到999之間的所有水仙花數(shù)。水仙花數(shù)的特點(diǎn)是:它的每個(gè)位上的數(shù)字的 3次冪之和等于它本身。(例如:371=33 + 73 + 13,因此371是水仙花數(shù)。請(qǐng)修改程序中的五行標(biāo)記有錯(cuò)的代碼,并注意在原程序上做盡量少的修改,使得程序能運(yùn)行出正確的結(jié)果。注意:不得更改其它程序行,不得增行或刪行,也不得更改程序的結(jié)構(gòu)!(2 (15分給定程序blank.c中已建立一個(gè)帶有頭結(jié)點(diǎn)的單向鏈

4、表,鏈表中的各結(jié)點(diǎn)數(shù)據(jù)域中的數(shù)據(jù)各不相同,并且按結(jié)點(diǎn)數(shù)據(jù)域中的數(shù)據(jù)從小到大順序鏈接。函數(shù)fun的功能是:把形參x的值放入一個(gè)新結(jié)點(diǎn)并插入到鏈表中,插入后各結(jié)點(diǎn)仍保持從小到大順序排列。如果x在鏈表中已經(jīng)存在,則不插入。鏈表已有元素為:11,12,15,18,19,22,25,29,則:如果x為20,插入后鏈表為:11,12,15,18,19,20,22,25,29如果x為30,插入后鏈表為:11,12,15,18,19,22,25,29,30如果x為12,程序執(zhí)行后鏈表保持不變請(qǐng)?jiān)诔绦虻南聞澗€處填入正確的內(nèi)容并把下劃線刪除,使程序得出正確的結(jié)果。(15分注意:不得增行或刪行,也不得更改程序的結(jié)構(gòu)

5、!(3 (15分請(qǐng)編寫(xiě)一個(gè)函數(shù)fun,它的功能是:根據(jù)以下公式求的值(要求滿足精度0.0005,即某項(xiàng)小于0.0005時(shí)停止迭代: 程序運(yùn)行后,如果輸入精度0.005,則程序輸出為3.132157,如果輸入精度0.0005,則程序輸出為3.140578。注意:部分源程序存在文件prog1.c中。請(qǐng)勿改動(dòng)主函數(shù)main和其他函數(shù)中的任何內(nèi)容,僅在函數(shù)fun的花括號(hào)中填入你編寫(xiě)的若干語(yǔ)句。(4 (20分在一個(gè)遞增有序的數(shù)組中,有數(shù)值相同的元素存在,程序的功能是去掉數(shù)值相同的元素,使數(shù)組中不再有重復(fù)的元素。例如:(7,10,10,21,30,42,42,42,51將變成(7,10,21,30,42,

6、51。主函數(shù)main中,首先輸入有序數(shù)組的元素?cái)?shù)目及各元素的值,然后將數(shù)組及元素?cái)?shù)目傳入函數(shù)fun中,函數(shù)fun完成刪除重復(fù)元素的操作。部分源程序存貯在文件prog1.c中,請(qǐng)完成fun函數(shù)。要求:盡量?jī)?yōu)化算法的時(shí)間復(fù)雜度與空間復(fù)雜度,并在prog2.c的最前面添加注釋,簡(jiǎn)要介紹自己的算法,并指出該算法具有什么樣的時(shí)間復(fù)雜度與空間復(fù)雜度。請(qǐng)勿改動(dòng)主函數(shù)main和其它函數(shù)中的任何內(nèi)容,僅在最前面添加注釋,并在函數(shù)fun的花括號(hào)中填入你編寫(xiě)的若干語(yǔ)句。(5 (20分從數(shù)據(jù)結(jié)構(gòu)中樹(shù)的定義可知,除根結(jié)點(diǎn)外,樹(shù)中的每個(gè)結(jié)點(diǎn)都有唯一的一個(gè)雙親結(jié)點(diǎn)。根據(jù)這一特性,可用一組連續(xù)的存儲(chǔ)空間(一維數(shù)組存儲(chǔ)樹(shù)中的各

7、結(jié)點(diǎn)。樹(shù)中的結(jié)點(diǎn)除保存結(jié)點(diǎn)本身的信息之外,還要保存其雙親結(jié)點(diǎn)在數(shù)組中的位置(即在數(shù)組中的下標(biāo)。雙親的信息為-1則表示該結(jié)點(diǎn)為根結(jié)點(diǎn),樹(shù)的這種表示法稱為雙親表示法。樹(shù)的每個(gè)結(jié)點(diǎn)的數(shù)據(jù)類型定義如下:struct PTNodechar data; /結(jié)點(diǎn)數(shù)據(jù)域int parent; /結(jié)點(diǎn)雙親在數(shù)組中的位置;樹(shù)的數(shù)據(jù)類型定義如下:#define MAX_TREE_SIZE 100struct PTreestruct PTNode nodesMAX_TREE_SIZE; /存儲(chǔ)樹(shù)中所有結(jié)點(diǎn)int n; /樹(shù)中共有n個(gè)結(jié)點(diǎn),n不超過(guò)100;則下圖a所示的樹(shù),按照雙親表示法存儲(chǔ)結(jié)構(gòu),存儲(chǔ)為圖b所示形式(n

8、為10。序號(hào) data parent 圖a 樹(shù)的示意圖圖b 雙親表示法存儲(chǔ)已知一棵樹(shù)已存儲(chǔ)為以上形式,請(qǐng)編寫(xiě)函數(shù)GetLeavesCount,計(jì)算葉子結(jié)點(diǎn)數(shù)目。GetLeavesCount的函數(shù)原型為:int GetLeavesCount (struct PTree T其中,形參T中保存了樹(shù)中結(jié)點(diǎn)數(shù)目及圖b所示的結(jié)點(diǎn)數(shù)組。函數(shù)返回葉子結(jié)點(diǎn)的數(shù)目。比如,對(duì)圖b的樹(shù)調(diào)用函數(shù)GetLeavesCount (T,返回結(jié)果為6(因?yàn)橛?個(gè)葉子結(jié)點(diǎn)。部分代碼在prog3.c中,請(qǐng)僅在GetLeavesCount函數(shù)中填入內(nèi)容,完成程序。要求:盡量?jī)?yōu)化算法的時(shí)間復(fù)雜度與空間復(fù)雜度,并在GetLeavesCo

9、unt函數(shù)前的注釋部分簡(jiǎn)要介紹自己的算法,同時(shí)指出該算法具有什么樣的時(shí)間復(fù)雜度與空間復(fù)雜度。請(qǐng)勿改動(dòng)主函數(shù)main和其它已有函數(shù)中的任何內(nèi)容,可以在函數(shù)GetLeavesCount的花括號(hào)中填入你編寫(xiě)的若干語(yǔ)句,允許增加自定義函數(shù)。prog3.c中,struct PTree CreateTree(函數(shù)用于從鍵盤(pán)輸入樹(shù)的雙親表示法的信息,創(chuàng)建一棵樹(shù)。輸入的第一個(gè)數(shù)n表示樹(shù)中結(jié)點(diǎn)數(shù),此后有n行輸入,每行表示一個(gè)結(jié)點(diǎn)的信息,第一個(gè)信息為結(jié)點(diǎn)的數(shù)據(jù),第二個(gè)信息為結(jié)點(diǎn)的雙親結(jié)點(diǎn)在數(shù)組中的位置。如輸入:10a -1b 0c 0d 0e 1f 1g 1h 2i 3j 3則將創(chuàng)建圖b所對(duì)應(yīng)的樹(shù)。對(duì)此樹(shù)調(diào)用函數(shù)GetLe