數據結構(c語言版)測試題答案(已修改)

　

【正文】 62第一章概論 自測題答案 姓名 班級 題號一二三四五六總分題分3315982015100得分一、填空題（每空1分，共33分）1. 一個計算機系統包括 硬件系統 和 軟件系統 兩大部分。2. 一臺計算機中全部程序的集合，稱為這臺計算機的 軟件資源 /（系統） 。3. 計算機軟件可以分為 系統 軟件和 應用 軟件兩大類。科學計算程序包屬于 應用軟件 ，診斷程序屬于 系統軟件（工具） 。4. 一種用助憶符號來表示機器指令的操作符和操作數的語言是 匯編語言 。5. 數據結構是一門研究非數值計算的程序設計問題中計算機的 操作對象 以及它們之間的 關系 和運算等的學科。6. 數據結構被形式地定義為（D, R），其中D是 數據元素 的有限集合，R是D上的 關系 有限集合。7. 數據結構包括數據的 邏輯結構 、數據的 存儲結構 和數據的 運算 這三個方面的內容。8. 數據結構按邏輯結構可分為兩大類，它們分別是 線性結構 和 非線性結構 。9. 線性結構中元素之間存在一對一關系，樹形結構中元素之間存在一對多關系，圖形結構中元素之間存在多對多關系。10． 在線性結構中，第一個結點 沒有 前驅結點，其余每個結點有且只有 1個前驅結點；最后一個結點 沒有 后續結點，其余每個結點有且只有1個后續結點。11. 在樹形結構中，樹根結點沒有 前驅 結點，其余每個結點有且只有 1 個前驅結點；葉子結點沒有 后續 結點，其余每個結點的后續結點數可以任意多個 。12. 在圖形結構中，每個結點的前驅結點數和后續結點數可以 任意多個 。13．數據的存儲結構可用四種基本的存儲方法表示，它們分別是順序 、 鏈式 、 索引 和 散列 。14. 數據的運算最常用的有5種，它們分別是插入 、 刪除、修改、 查找 、排序。15. 一個算法的效率可分為 時間 效率和 空間 效率。16. 〖00年省統考〗任何一個C程序都由 一個主函數 和若干個被調用的其它函數組成。17. 【00年省統考題】變量一經說明，就確定該變量的取值范圍（即存儲單元）及 確定變量所允許的運算 。二、單項選擇題（每小題1分，共15分）（ B ） 1. 通常所說的主機是指∶A) CPU B) CPU和內存 C) CPU、內存與外存 D) CPU、內存與硬盤（ C ）2. 在計算機內部，一切信息的存取、處理和傳送的形式是∶A) ACSII碼 B) BCD碼 C)二進制 D)十六進制 （ D ）3. 軟件與程序的區別是∶A) 程序價格便宜、軟件價格昂貴； B) 程序是用戶自己編寫的，而軟件是由廠家提供的；C) 程序是用高級語言編寫的，而軟件是由機器語言編寫的；D) 軟件是程序以及開發、使用和維護所需要的所有文檔的總稱，而程序只是軟件的一部分。（ C ）4. 所謂“裸機”是指∶A) 單片機 B)單板機 C) 不裝備任何軟件的計算機 D) 只裝備操作系統的計算機（ D ）5. 應用軟件是指∶A)所有能夠使用的軟件 B) 能被各應用單位共同使用的某種軟件C)所有微機上都應使用的基本軟件 D) 專門為某一應用目的而編制的軟件（ ＊A ）6. 〖00年省統考〗C語言中的常量可分為整型常量、實型常量、字符型常量及 (枚舉) 四種。（A） 符號常量 （B）長整型常量 （C） 邏輯常量 （D）二進制整數（ ＊C ）7. 編譯程序的功能是∶A)發現源程序中的語法錯誤 B)改正源程序中的語法錯誤C)將源程序編譯成目標程序 D)將某一高級語言程序翻譯成另一種高級語言程序（ A ）8. 系統軟件中最重要的是∶A) 操作系統 B) 語言處理系統 C) 工具軟件 D) 數據庫管理系統（ C ）9. 可移植性最好的計算機語言是∶A) 機器語言 B)匯編語言 C) 高級語言 D) 自然語言（ B ）10. 非線性結構是數據元素之間存在一種：A）一對多關系 B）多對多關系 C）多對一關系 D）一對一關系（ C ）11. 數據結構中，與所使用的計算機無關的是數據的 結構；A) 存儲 B) 物理 C) 邏輯 D) 物理和存儲（ C ）12. 算法分析的目的是：A) 找出數據結構的合理性 B) 研究算法中的輸入和輸出的關系C) 分析算法的效率以求改進 D) 分析算法的易懂性和文檔性（ A ）13. 算法分析的兩個主要方面是：A) 空間復雜性和時間復雜性 B) 正確性和簡明性C) 可讀性和文檔性 D) 數據復雜性和程序復雜性（ C ）14. 計算機算法指的是：A) 計算方法 B) 排序方法 C) 解決問題的有限運算序列 D) 調度方法（ B ）15. 計算機算法必須具備輸入、輸出和 等5個特性。A) 可行性、可移植性和可擴充性 B) 可行性、確定性和有窮性C) 確定性、有窮性和穩定性 D) 易讀性、穩定性和安全性三、簡答題（每小題3分,共9分）1．我們知道計算機只能執行機器指令，為什么它能運行用匯編語言和高級語言編寫的程序？答：靠匯編程序將匯編語言或高級語言翻譯轉換為目標程序（即機器語言）。2.【②】數據結構和數據類型兩個概念之間有區別嗎？答：簡單地說，數據結構定義了一組按某些關系結合在一起的數組元素。數據類型不僅定義了一組帶結構的數據元素，而且還在其上定義了一組操作。3. 簡述線性結構與非線性結構的不同點。答：線性結構反映結點間的邏輯關系是 一對一的，非線性結構反映結點間的邏輯關系是多對多的。四、〖00年統考題〗閱讀下列C程序段，寫出相應的執行結果（每小題4分，共8分）2. long int fact(n)int n。{long f。if(n1)f=n*fact(n1)。 else f=1。return(f)。}main(){int n。long y。n=5。y=fact(n)。printf(“%d,%ld\n”,n,y)。}答：運行結果為： 5，120 此題為遞歸運算1. printf(“Input x”)。scanf(“%d”,amp。x)。if (x=30) if(x20) y=x。else if (x10) y=2*x。 if (x0amp。amp。x30)printf(“x=%d,y=%d”,x,y)。 else printf(“輸入數據錯！”)。試寫出當x分別為18，8時的執行結果。答：運行結果為：x=18，y=36 x=8，y=運行前的值， 且從x＝30開始為數據錯五、【④】分析下面各程序段的時間復雜度（每小題5分，共20分）2. s=0。 for i=0。 in。 i++)for(j=0。 jn。 j++) s+=B[i][j]。sum=s。答：O（n2）1. for (i=0。 in。 i++)for (j=0。 jm。 j++)A[i][j]=0。答：O（m*n）3. x=0。for(i=1。 in。 i++) for (j=1。 j=ni。 j++)x++。解：因為x++共執行了n1+n2+……＋1= n(n1)/2，所以執行時間為O（n2）4. i=1。 while(i=n) i=i*3。答：O（log3n）六、設有數據邏輯結構S=（D,R），試按各小題所給條件畫出這些邏輯結構的圖示，并確定相對于關系R，哪些結點是開始結點，哪些結點是終端結點？（每小題5分，共15分）1. 【嚴蔚敏習題集P7 ②】D={d1,d2,d3,d4} R={(d1,d2),(d2,d3),(d3,d4) }答： d1→d2→d3→d4 d1—無直接前驅，是首結點 d4—無直接后繼是尾結點2. D={d1,d2,…,d9} R={(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5), (d6,d7),(d8,d9) }答： 此圖為樹形結構 d1—無直接前驅，是根結點 d2,d5,d7,d9—無直接后繼是葉子結點3. D={d1,d2,…,d9} R={(d1,d3),(d1,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d9), (d5,d6),(d8,d9),(d9,d7), (d4,d7), (d4,d6)}答： 此圖為圖形結構 d1，d2—無直接前驅，是開始結點 d6,d7—無直接后繼是終端結點 (2) (3)第2章 自測卷答案 姓名 班級 題號一二三四五六七總分題分1310101071040100得分一、填空（每空1分，共13分）1. 【①】在順序表中插入或刪除一個元素，需要平均移動 表中一半元素，具體移動的元素個數與 表長和該元素在表中的位置 有關。2. 線性表中結點的集合是 有限 的，結點間的關系是 一對一 的。3. 向一個長度為n的向量的第i個元素(1≤i≤n+1)之前插入一個元素時，需向后移動 ni+1 個元素。4. 向一個長度為n的向量中刪除第i個元素(1≤i≤n)時，需向前移動 ni 個元素。5. 在順序表中訪問任意一結點的時間復雜度均為 O(1) ，因此，順序表也稱為 隨機存取 的數據結構。6. 【①】順序表中邏輯上相鄰的元素的物理位置 必定相鄰。單鏈表中邏輯上相鄰的元素的物理位置 不一定 相鄰。7. 【①】在單鏈表中，除了首元結點外，任一結點的存儲位置由 其直接前驅結點的鏈域的值 指示。8． 在n個結點的單鏈表中要刪除已知結點*p，需找到它的前驅結點的地址，其時間復雜度為O（n）。二、判斷正誤（在正確的說法后面打勾，反之打叉）（每小題1分，共10分）（ ）1. 鏈表的每個結點中都恰好包含一個指針。 答：錯誤。鏈表中的結點可含多個指針域，分別存放多個指針。例如，雙向鏈表中的結點可以含有兩個指針域，分別存放指向其直接前趨和直接后繼結點的指針。（ ）2. 鏈表的物理存儲結構具有同鏈表一樣的順序。錯，鏈表的存儲結構特點是無序，而鏈表的示意圖有序。（ ）3. 鏈表的刪除算法很簡單，因為當刪除鏈中某個結點后，計算機會自動地將后續的各個單元向前移動。錯，鏈表的結點不會移動，只是指針內容改變。（ ）4. 線性表的每個結點只能是一個簡單類型，而鏈表的每個結點可以是一個復雜類型。錯，混淆了邏輯結構與物理結構，鏈表也是線性表！且即使是順序表，也能存放記錄型數據。（ ）5. 順序表結構適宜于進行順序存取，而鏈表適宜于進行隨機存取。 錯，正好說反了。順序表才適合隨機存取，鏈表恰恰適于“順藤摸瓜”（ ）6. 順序存儲方式的優點是存儲密度大，且插入、刪除運算效率高。錯，前一半正確，但后一半說法錯誤，那是鏈式存儲的優點。順序存儲方式插入、刪除運算效率較低，在表長為n的順序表中，插入和刪除一個數據元素，平均需移動表長一半個數的數據元素。（ ）7. 線性表在物理存儲空間中也一定是連續的。錯，線性表有兩種存儲方式，順序存儲和鏈式存儲。后者不要求連續存放。（ ）8. 線性表在順序存儲時，邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰。錯誤。線性表有兩種存儲方式，在順序存儲時，邏輯上相鄰的元素在存儲的物理位置次序上也相鄰。（ ）9. 順序存儲方式只能用于存儲線性結構。錯誤。順序存儲方式不僅能用于存儲線性結構，還可以用來存放非線性結構，例如完全二叉樹是屬于非線性結構，但其最佳存儲方式是順序存儲方式。（后一節介紹）（ ）10. 線性表的邏輯順序與存儲順序總是一致的。錯，理由同7。鏈式存儲就無需一致。三、單項選擇題（每小題1分，共10分）（ C ）1．數據在計算機存儲器內表示時，物理地址與邏輯地址相同并且是連續的，稱之為：（A）存儲結構 （B）邏輯結構 （C）順序存儲結構 （D）鏈式存儲結構（ B ），每個元素的長度為2，則第5個元素的地址是