《c語(yǔ)言數(shù)據(jù)結(jié)構(gòu)》第一章概論自測(cè)題答案

1、第一章概論 自測(cè)題答案 姓名 班級(jí) 題號(hào)一二三四五六總分題分3315982015100得分一、填空題（每空1分，共33分）1. 一個(gè)計(jì)算機(jī)系統(tǒng)包括 硬件系統(tǒng) 和 軟件系統(tǒng) 兩大部分。2. 一臺(tái)計(jì)算機(jī)中全部程序的集合，稱為這臺(tái)計(jì)算機(jī)的 軟件資源 /（系統(tǒng)） 。3. 計(jì)算機(jī)軟件可以分為 系統(tǒng) 軟件和 應(yīng)用 軟件兩大類。科學(xué)計(jì)算程序包屬于 應(yīng)用軟件 ，診斷程序?qū)儆?系統(tǒng)軟件（工具） 。4. 一種用助憶符號(hào)來(lái)表示機(jī)器指令的操作符和操作數(shù)的語(yǔ)言是 匯編語(yǔ)言 。5. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的 操作對(duì)象 以及它們之間的 關(guān)系 和運(yùn)算等的學(xué)科。6. 數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D, R

2、），其中D是 數(shù)據(jù)元素 的有限集合，R是D上的 關(guān)系 有限集合。7. 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的 邏輯結(jié)構(gòu) 、數(shù)據(jù)的 存儲(chǔ)結(jié)構(gòu) 和數(shù)據(jù)的 運(yùn)算 這三個(gè)方面的內(nèi)容。8. 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是 線性結(jié)構(gòu) 和 非線性結(jié)構(gòu) 。9. 線性結(jié)構(gòu)中元素之間存在一對(duì)一關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對(duì)多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對(duì)多關(guān)系。10 在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn) 沒有 前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 1個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn) 沒有 后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)后續(xù)結(jié)點(diǎn)。11. 在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有 前驅(qū) 結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 1 個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有 后續(xù) 結(jié)點(diǎn)，

3、其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)數(shù)可以任意多個(gè) 。12. 在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以 任意多個(gè) 。13數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可用四種基本的存儲(chǔ)方法表示，它們分別是順序 、 鏈?zhǔn)?、 索引 和 散列 。14. 數(shù)據(jù)的運(yùn)算最常用的有5種，它們分別是插入 、 刪除、修改、 查找 、排序。15. 一個(gè)算法的效率可分為 時(shí)間 效率和 空間 效率。16. 00年省統(tǒng)考任何一個(gè)C程序都由 一個(gè)主函數(shù) 和若干個(gè)被調(diào)用的其它函數(shù)組成。17. 【00年省統(tǒng)考題】變量一經(jīng)說(shuō)明，就確定該變量的取值范圍（即存儲(chǔ)單元）及 確定變量所允許的運(yùn)算 。二、單項(xiàng)選擇題（每小題1分，共15分）（ B ） 1. 通常所說(shuō)的主機(jī)

4、是指A) CPUB) CPU和內(nèi)存C) CPU、內(nèi)存與外存D) CPU、內(nèi)存與硬盤（ C ）2. 在計(jì)算機(jī)內(nèi)部，一切信息的存取、處理和傳送的形式是A) ACSII碼 B) BCD碼 C)二進(jìn)制 D)十六進(jìn)制 （ D ）3. 軟件與程序的區(qū)別是A) 程序價(jià)格便宜、軟件價(jià)格昂貴；B) 程序是用戶自己編寫的，而軟件是由廠家提供的；C) 程序是用高級(jí)語(yǔ)言編寫的，而軟件是由機(jī)器語(yǔ)言編寫的；D) 軟件是程序以及開發(fā)、使用和維護(hù)所需要的所有文檔的總稱，而程序只是軟件的一部分。（ C ）4. 所謂“裸機(jī)”是指A) 單片機(jī)B)單板機(jī)C) 不裝備任何軟件的計(jì)算機(jī)D) 只裝備操作系統(tǒng)的計(jì)算機(jī)（ D ）5. 應(yīng)用軟件

5、是指A)所有能夠使用的軟件 B) 能被各應(yīng)用單位共同使用的某種軟件C)所有微機(jī)上都應(yīng)使用的基本軟件 D) 專門為某一應(yīng)用目的而編制的軟件（ A ）6. 00年省統(tǒng)考C語(yǔ)言中的常量可分為整型常量、實(shí)型常量、字符型常量及 (枚舉) 四種。（A） 符號(hào)常量 （B）長(zhǎng)整型常量 （C） 邏輯常量 （D）二進(jìn)制整數(shù)（ C ）7. 編譯程序的功能是A)發(fā)現(xiàn)源程序中的語(yǔ)法錯(cuò)誤 B)改正源程序中的語(yǔ)法錯(cuò)誤C)將源程序編譯成目標(biāo)程序 D)將某一高級(jí)語(yǔ)言程序翻譯成另一種高級(jí)語(yǔ)言程序（ A ）8. 系統(tǒng)軟件中最重要的是A) 操作系統(tǒng) B) 語(yǔ)言處理系統(tǒng) C) 工具軟件 D) 數(shù)據(jù)庫(kù)管理系統(tǒng)（ C ）9. 可移植性最好

6、的計(jì)算機(jī)語(yǔ)言是A) 機(jī)器語(yǔ)言B)匯編語(yǔ)言C) 高級(jí)語(yǔ)言D) 自然語(yǔ)言（ B ）10. 非線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種：A）一對(duì)多關(guān)系 B）多對(duì)多關(guān)系 C）多對(duì)一關(guān)系 D）一對(duì)一關(guān)系（ C ）11. 數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的 結(jié)構(gòu)；A) 存儲(chǔ) B) 物理 C) 邏輯 D) 物理和存儲(chǔ)（ C ）12. 算法分析的目的是：A) 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B) 研究算法中的輸入和輸出的關(guān)系C) 分析算法的效率以求改進(jìn) D) 分析算法的易懂性和文檔性（ A ）13. 算法分析的兩個(gè)主要方面是：A) 空間復(fù)雜性和時(shí)間復(fù)雜性 B) 正確性和簡(jiǎn)明性C) 可讀性和文檔性 D) 數(shù)據(jù)復(fù)雜性和程序復(fù)

7、雜性（ C ）14. 計(jì)算機(jī)算法指的是：A) 計(jì)算方法 B) 排序方法 C) 解決問題的有限運(yùn)算序列 D) 調(diào)度方法（ B ）15. 計(jì)算機(jī)算法必須具備輸入、輸出和 等5個(gè)特性。A) 可行性、可移植性和可擴(kuò)充性 B) 可行性、確定性和有窮性C) 確定性、有窮性和穩(wěn)定性 D) 易讀性、穩(wěn)定性和安全性三、簡(jiǎn)答題（每小題3分,共9分）1我們知道計(jì)算機(jī)只能執(zhí)行機(jī)器指令，為什么它能運(yùn)行用匯編語(yǔ)言和高級(jí)語(yǔ)言編寫的程序？答：靠匯編程序?qū)R編語(yǔ)言或高級(jí)語(yǔ)言翻譯轉(zhuǎn)換為目標(biāo)程序（即機(jī)器語(yǔ)言）。2.【嚴(yán)題集1.2】數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型兩個(gè)概念之間有區(qū)別嗎？答：簡(jiǎn)單地說(shuō)，數(shù)據(jù)結(jié)構(gòu)定義了一組按某些關(guān)系結(jié)合在一起的數(shù)組元素

8、。數(shù)據(jù)類型不僅定義了一組帶結(jié)構(gòu)的數(shù)據(jù)元素，而且還在其上定義了一組操作。3. 簡(jiǎn)述線性結(jié)構(gòu)與非線性結(jié)構(gòu)的不同點(diǎn)。答：線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是 一對(duì)一的，非線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是多對(duì)多的。四、00年統(tǒng)考題閱讀下列C程序段，寫出相應(yīng)的執(zhí)行結(jié)果（每小題4分，共8分）2. long int fact(n)int n;long f;if(n>1)f=n*fact(n-1); else f=1;return(f);main()int n;long y;n=5;y=fact(n);printf(“%d,%ldn”,n,y);答：運(yùn)行結(jié)果為： 5，120 此題為遞歸運(yùn)算1. printf(“

9、Input x”);scanf(“%d”,&x);if (x<=30) if(x>20) y=x;else if (x>10) y=2*x;if (x>0&&x<30)printf(“x=%d,y=%d”,x,y);else printf(“輸入數(shù)據(jù)錯(cuò)！”);試寫出當(dāng)x分別為18，8時(shí)的執(zhí)行結(jié)果。答：運(yùn)行結(jié)果為：x=18，y=36 x=8，y=運(yùn)行前的值， 且從x30開始為數(shù)據(jù)錯(cuò)五、【嚴(yán)題集1.8】分析下面各程序段的時(shí)間復(fù)雜度（每小題5分，共20分）2. s=0; for i=0; i<n; i+)for(j=0; j<n; j

10、+) s+=Bij;sum=s;答：O（n2）1. for (i=0; i<n; i+)for (j=0; j<m; j+)Aij=0;答：O（m*n）3. x=0;for(i=1; i<n; i+) for (j=1; j<=n-i; j+)x+;解：因?yàn)閤+共執(zhí)行了n-1+n-2+1= n(n-1)/2，所以執(zhí)行時(shí)間為O（n2）4. i=1; while(i<=n) i=i*3;答：O（log3n）六、設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)S=（D,R），試按各小題所給條件畫出這些邏輯結(jié)構(gòu)的圖示，并確定相對(duì)于關(guān)系R，哪些結(jié)點(diǎn)是開始結(jié)點(diǎn)，哪些結(jié)點(diǎn)是終端結(jié)點(diǎn)？（每小題5分，共15分）1. 【嚴(yán)蔚敏習(xí)題集P7 1.3】D=d1,d2,d3,d4 R=(d1,d2),(d2,d3),(d3,d4) 答： d1d2d3d4 d1無(wú)直接前驅(qū)，是首結(jié)點(diǎn) d4無(wú)直接后繼是尾結(jié)點(diǎn)2. D=d1,d2,d9 R=(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5), (d6,d7),(d8,d9) 答： 此圖為樹形結(jié)構(gòu) d1無(wú)直接前驅(qū)，是根結(jié)點(diǎn) d2,d5,d7,d9無(wú)直接后繼是葉子結(jié)點(diǎn)3. D=d1,d2,d9 R=(d1,d3),(d1,d8)