數據結構復習題及參考答案(已修改)

　

【正文】 《數據結構》復習題及參考答案`0001 01B1 數據結構是一門研究非數值計算的程序設計問題中計算機的 以及它們之間的 和運算等的學科。~0001操作對象 關系`0002 01B1 數據結構被形式地定義為（D, R），其中D是 的有限集合，R是D上的 有限集合。~0002數據元素 關系`0003 01B2 數據結構包括數據的 數據的 和數據的 這三個方面的內容。~0003邏輯結構 存儲結構 運算`0004 01B1數據結構按邏輯結構可分為兩大類，它們分別是 和 。~0004線性結構 非線性結構`0005 01B1 線性結構中元素之間存在 關系，樹形結構中元素之間存在 關系，圖形結構中元素之間存在 關系。~0005 一對一 一對多 多對多`0006 01B1在線性結構中，第一個結點 前驅結點，其余每個結點有且只有 1個前驅結點；最后一個結點 后續結點，其余每個結點有且只有1個后續結點。~0006沒有 沒有`0007 01B2 在樹形結構中，樹根結點沒有 結點，其余每個結點有且只有 個前驅結點；葉子結點沒有 結點，其余每個結點的后續結點數可以 。~0007 前驅 1 后續 任意多個`0008 01B1在圖形結構中，每個結點的前驅結點數和后續結點數可以 。~0008 任意多個`0009 01B2數據的存儲結構可用四種基本的存儲方法表示，它們分別是 。~0009 順序 鏈式 索引 散列`0010 01B2 數據的運算最常用的有5種，它們分別是 。~0010 插入 、 刪除、修改、 查找 、排序`0011 01B2一個算法的效率可分為 效率和 效率。~0011時間 空間 `0012 01C1非線性結構是數據元素之間存在一種：（ ）A、一對多關系 B、多對多關系 C、多對一關系 D、一對一關系~0012B`0013 01C1數據結構中，與所使用的計算機無關的是數據的（ ）結構；A、存儲 B、物理 C、邏輯 D、 物理和存儲~0013C`0014 01C1 算法分析的目的是（ ）A、找出數據結構的合理性 B、 研究算法中的輸入和輸出的關系C、分析算法的效率以求改進 D、 分析算法的易懂性和文檔性~0014C`0015 01C1算法分析的兩個主要方面是（ ）A、空間復雜性和時間復雜性 B、 正確性和簡明性C、可讀性和文檔性 D、 數據復雜性和程序復雜性~0015 A`0016 01C2計算機算法指的是（ ）A、計算方法 B、排序方法 C、 解決問題的有限運算序列 D、 調度方法~0016C`0017 01C2計算機算法必須具備輸入、輸出和（ ）等5個特性。A、可行性、可移植性和可擴充性 B、 可行性、確定性和有窮性C、 確定性、有窮性和穩定性 D、 易讀性、穩定性和安全性~0017 B`0018 01A2數據結構和數據類型兩個概念之間有區別嗎？~0018簡單地說，數據結構定義了一組按某些關系結合在一起的數組元素。數據類型不僅定義了一組帶結構的數據元素，而且還在其上定義了一組操作。`0019 01A1簡述線性結構與非線性結構的不同點。~0019線性結構反映結點間的邏輯關系是一對一的，非線性結構反映結點間的邏輯關系是多對多的。`0020 01A2分析下面各程序段的時間復雜度： for (i=0。 in。 i++)for (j=0。 jm。 j++)A[i][j]=0。~0020O（m*n）`0021 01A2分析下面各程序段的時間復雜度：s=0。 for i=0。 in。 i++)for(j=0。 jn。 j++) s+=B[i][j]。sum=s。~0021 O（n2）`0022 01A2分析下面各程序段的時間復雜度：x=0。for(i=1。 in。 i++) for (j=1。 j=ni。 j++)x++。~0022因為x++共執行了n1+n2+……＋1= n(n1)/2，所以執行時間為O（n2）`0023 01A2分析下面各程序段的時間復雜度：i=1。 while(i=n) i=i*3。~0023O（log3n）`0024 01E2設有數據邏輯結構S=（D,R），試按各小題所給條件畫出這些邏輯結構的圖示，并確定相對于關系R，哪些結點是開始結點，哪些結點是終端結點？ 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)}~0024此圖為圖形結構 d1，d2—無直接前驅，是開始結點 d6,d7—無直接后繼是終端結點 `0025 02B1在順序表中插入或刪除一個元素，需要平均移動 元素，具體移動的元素個數與 有關。~0025表中一半 表長和該元素在表中的位置`0026 03C1判定一個棧ST（最多元素為m0）為空的條件是Ａ、STtop0 Ｂ、STtop=0 Ｃ、STtopm0 Ｄ、STtop=m0~0026 B`0027 02B2 向一個長度為n的向量的第i個元素(1≤i≤n+1)之前插入一個元素時，需向后移動 個元素。~0027ni+1`0028 02B2 向一個長度為n的向量中刪除第i個元素(1≤i≤n)時，需向前移動 個元素。~0028 ni`0029 02B1在順序表中訪問任意一結點的時間復雜度均為 ，因此，順序表也稱為 的數據結構。~0029 O(1) 隨機存取`0030 02B1順序表中邏輯上相鄰的元素的物理位置 相鄰。單鏈表中邏輯上相鄰的元素的物理位置 相鄰。~0030 必定 不一定`0031 02B1在單鏈表中，除了首元結點外，任一結點的存儲位置由 指示。~0031其直接前驅結點的鏈域的值`0032 02B2 在n個結點的單鏈表中要刪除已知結點*p，需找到它的 ，其時間復雜度為 。~0032 前驅結點的地址 O（n）`0033 02D1鏈表的每個結點中都恰好包含一個指針。（ ） ~0033 X`0034 02D1鏈表的物理存儲結構具有同鏈表一樣的順序。（ ）~0034X`0035 02D1鏈表的刪除算法很簡單，因為當刪除鏈中某個結點后，計算機會自動地將后續的各個單元向前移動。（ ）~0035X`0036 02D1線性表的每個結點只能是一個簡單類型，而鏈表的每個結點可以是一個復雜類型。（ ）~0036 X`0037 02D1順序表結構適宜于進行順序存取，而鏈表適宜于進行隨機存取。（ ） ~0037 X`0038 02D1 順序存儲方式的優點是存儲密度大，且插入、刪除運算效率高。（ ）~0038X`0039 02D1線性表在物理存儲空間中也一定是連續的。（ ）~0039 X`0040 02D1線性表在順序存儲時，邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰。（ ）~0040X`0041 02D1順序存儲方式只能用于存儲線性結構。（ ）~0041X`0042 02D1線性表的邏輯順序與存儲順序總是一致的。（ ）~0042 X`0043 02C1數據在計算機存儲器內表示時，物理地址與邏輯地址相同并且是連續的，稱之為（ ）A、存儲結構 B、邏輯結構 C、順序存儲結構 D、鏈式存儲結構~0043C`0044 02C1 一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是（ ）A、110 B、108 C、100 D、120~0044B`0045 02C1在n個結點的順序表中，算法的時間復雜度是O（1）的操作是（ ）A、 訪問第i個結點（1≤i≤n）和求第i個結點的直接前驅（2≤i≤n） B、 在第i個結點后插入一個新結點（1≤i≤n）C、 刪除第i個結點（1≤i≤n）D、 將n個結點從小到大排序~0045A`0046 02C2個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動（ ）個元素A、8 B、 C、63 D、7~0046B`0047 02C2鏈接存儲的存儲結構所占存儲空間（ ）A、 分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針B、 只有一部分，存放結點值C、只有一部分，存儲表示結點間關系的指針D、 分兩部分，一部分存放結點值，另一部分存放結點所占單元數~0047 A`0048 02C1鏈表是一種采用（ ）存儲結構存儲的線性表；A、順序 B、鏈式 C、星式 D、網狀~0048 B`0049 02C1線性表若采用鏈式存儲結構時，要求內存中可用存儲單元的地址（ ）A、必須是連續的 B、部分地址必須是連續的C、一定是不連續的 D、連續或不連續都可以~0049 D`0050 02C1線性表Ｌ在（ ）情況下適用于使用鏈式結構實現。A、需經常修改Ｌ中的結點值 B、需不斷對Ｌ進行刪除插入 C、Ｌ中含有大量的結點 D、Ｌ中結點結構復雜~0050 B`0051 10B1若索引文件采用稠密索引,則每個索引項與主文件中的______記錄相對應,若索引文件采用稀疏索引,則每個索引項與主文件中的_______記錄相對應.~0051 一個 一組(成若干條)`0052 08E2 已知一堆數組A中的數據如下,試寫出在快速排序的過程中每次劃分后數據的排序情況. 1 2 3 4 5 6 7 8 ┌─┬─┬─┬─┬─┬─┬─┬─┐ │45│28│64│53│15│36│74│30│ └─┴─┴─┴─┴─┴─┴─┴─┘ (1) (2) (3)~0052 [ 30 28 36 15 ] 45 [ 53 74 64 ] [ 15 28 ] 30 36 45 53 [ 74 64] 15 28 30 36 45 53 64 74`0053 08C1 下列排序算法中,第一趟排序完畢后,其最大或最小元素不一定在其最終位置上的算法是( ) A、歸并排序 B、直接選擇排序 C、樹形選擇排序 D、冒泡排序~0053A`0054 08C1 直接插入排序的時間復雜度為( ). A、O(n) B、0(log2n) C、0(nlog2n) D、0(n2)~0054 d`0055 10B1 文件的檢索和修改有兩種方式______和______~0055 實時的 批量的`0056 10C2 對順序文件的檢索方法可以是( )A、 順序存取 B、隨機存取 C、按關鍵字存取 D、前三種方法都可以~0056 D`0057 10B1 在查找索引文件時,首先要查找_______ 。然后再查找________~0057 索引表 主文件`0058 08E3 利用堆排序的方法給已知數組A中的數據排序,寫出在構成初始堆和利用堆排序的過程中,每次篩運算后數據的排列情況: 1