工程圖學總復習題

1、數(shù)據(jù)結(jié)構和算法的基本概念數(shù)據(jù)結(jié)構和算法的基本概念一判斷題（下列各題，正確的請在前面的括號內(nèi)打一判斷題（下列各題，正確的請在前面的括號內(nèi)打√；錯誤的打；錯誤的打╳）（√）（1）數(shù)據(jù)的邏輯結(jié)構與數(shù)據(jù)元素本身的內(nèi)容和形式無關。（√）（2）一個數(shù)據(jù)結(jié)構是由一個邏輯結(jié)構和這個邏輯結(jié)構上的一個基本運算集構成的整體。（ㄨ）（3）數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（ㄨ）（4）數(shù)據(jù)的邏輯結(jié)構和數(shù)據(jù)的存儲結(jié)構是相同的。（ㄨ）（5）程序和算法原則上沒有區(qū)別，所以在討

2、論數(shù)據(jù)結(jié)構時可以通用。（√）（6）從邏輯關系上講，數(shù)據(jù)結(jié)構主要分為線性結(jié)構和非線性結(jié)構兩類。（√）（7）數(shù)據(jù)的存儲結(jié)構是數(shù)據(jù)的邏輯結(jié)構的存儲映像。（√）（8）數(shù)據(jù)的物理結(jié)構是指數(shù)據(jù)在計算機內(nèi)實際的存儲形式。（ㄨ）（9）數(shù)據(jù)的邏輯結(jié)構是依賴于計算機的。（√）（10）算法是對解題方法和步驟的描述。三選擇題三選擇題（1）數(shù)據(jù)結(jié)構通常是研究數(shù)據(jù)的（A）及它們之間的相互聯(lián)系。A.存儲結(jié)構和邏輯結(jié)構B.存儲和抽象C.聯(lián)系和抽象D.聯(lián)系與邏輯（2）在

3、邏輯上可以把數(shù)據(jù)結(jié)構分成：（C）。A.動態(tài)結(jié)構和靜態(tài)結(jié)構B.緊湊結(jié)構和非緊湊結(jié)構C.線性結(jié)構和非線性結(jié)構D.內(nèi)部結(jié)構和外部結(jié)構（3）數(shù)據(jù)在計算機存儲器內(nèi)表示時，物理地址和邏輯地址相同并且是連續(xù)的，稱之為（C）。A.存儲結(jié)構B.邏輯結(jié)構C.順序存儲結(jié)構D.鏈式存儲結(jié)構（4）非線性結(jié)構中的每個結(jié)點（D）。無直接前趨結(jié)點無直接后繼結(jié)點只有一個直接前趨結(jié)點和一個直接后繼結(jié)點可能有多個直接前趨結(jié)點和多個直接后繼結(jié)點（5）鏈式存儲的存儲結(jié)構所占存儲

4、空間（A）。A分兩部分，一部分存放結(jié)點的值，另一部分存放表示結(jié)點間關系的指針B只有一部分，存放結(jié)點的值C只有一部分，存儲表示結(jié)點間關系的指針D分兩部分，一部分存放結(jié)點的值，另一部分存放結(jié)點所占單元素（6）算法的計算量大小稱為算法的（C）。A.現(xiàn)實性B.難度C.時間復雜性D.效率（7）數(shù)據(jù)的基本單位是（B）。A.數(shù)據(jù)結(jié)構B.數(shù)據(jù)元素C.數(shù)據(jù)項D.文件（8）每個結(jié)點只含有一個數(shù)據(jù)元素，所有存儲結(jié)點相繼存放在一個連續(xù)的存儲區(qū)里，這種存儲結(jié)構稱

5、為（A）結(jié)構。A.順序存儲B.鏈式存儲C.索引存儲D.散列存儲（9）每一個存儲結(jié)點不僅含有一個數(shù)據(jù)元素，還包含一組指針，該存儲方式是（B）（）（6）順序表的每個結(jié)點只能是一個簡單類型，而鏈表的每個結(jié)點可以是一個復雜類型。（√）（7）線性表鏈式存儲的特點是可以用一組任意的存儲單元存儲表中的數(shù)據(jù)元素。（√）（8）線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。（）（9）順序表結(jié)構適宜于進行順序存取，而鏈表適宜于進行隨機存取。（ㄨ）（10）插

6、入和刪除操作是數(shù)據(jù)結(jié)構中最基本的兩種操作，所以這兩種操作在數(shù)組中也經(jīng)常使用。二填空題二填空題順序表中邏輯上相鄰的元素在物理位置上必須相連。線性表中結(jié)點的集合是有限的，結(jié)點間的關系是一對一關系。順序表相對于鏈表的優(yōu)點是：節(jié)省存儲和隨機存取。鏈表相對于順序表的優(yōu)點是：插入、刪除方便。（5）采用順序存儲結(jié)構的線性表叫順序表。（6）順序表中訪問任意一個結(jié)點的時間復雜度均為O(1)。（7）鏈表相對于順序表的優(yōu)點是插入、刪除方便；缺點是存儲密度小。

7、（8）在雙鏈表中要刪除已知結(jié)點P，其時間復雜度為O(1)。（9）在單鏈表中要在已知結(jié)點P之前插入一個新結(jié)點，需找到P的直接前趨結(jié)點的地址，其查找的時間復雜度為O(n)。單鏈表中需知道頭指針才能遍歷整個鏈表。性表中第一個結(jié)點沒有直接前趨，稱為開始結(jié)點。在一個長度為n的順序表中刪除第i個元素，要移動ni個元素。在一個長度為n的順序表中，如果要在第i個元素前插入一個元素，要后移ni1個元素。在無頭結(jié)點的單鏈表中，第一個結(jié)點的地址存放在頭指針中

8、，而其它結(jié)點的存儲地址存放在前趨結(jié)點的指針域中。當線性表的元素總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快速度存取線性表中的元素時，應采用順序存儲結(jié)構。在線性表的鏈式存儲中，元素之間的邏輯關系是通過指針決定的。在雙向鏈表中，每個結(jié)點都有兩個指針域，它們一個指向其前趨結(jié)點，另一個指向其后繼結(jié)點。對一個需要經(jīng)常進行插入和刪除操作的線性表，采用鏈式存儲結(jié)構為宜。雙鏈表中，設p是指向其中待刪除的結(jié)點，則需要執(zhí)行的操作為：pprinext