西南交大數(shù)據(jù)結構主觀題作業(yè)

1、114弘成無錫數(shù)字化學習中心弘成無錫數(shù)字化學習中心批次批次層次：專升本層次：專升本專業(yè)：計算機科學與技術專業(yè)：計算機科學與技術姓名：劉鵬亮姓名：劉鵬亮學號：學號：15940673314參考答案：雙向34.在鏈表中，可以用表尾指針代替表頭指針。參考答案：雙向35.根據(jù)n個數(shù)據(jù)元素建立對應的順序表和單鏈表存儲結構，其算法的時間復雜度最好的情況是，最壞的情況是。參考答案：O(n)，O(n2)36.求線性表的順序存儲和鏈式存儲的長度的算法時間復

2、雜度分別是和。參考答案：O(1)O(n)37.在一個帶頭結點的單鏈表中，在表頭插入或刪除與在其他位置插入或刪除，其操作過程是否相同？。參考答案：相同38.在一個不帶頭結點的單鏈表中，在表頭插入或刪除與在其他位置插入或刪除，其操作過程是否相同？。參考答案：不相同39.闡述順序表和鏈表存儲方式的特點。參考答案：順序表存儲方式為數(shù)據(jù)分配連續(xù)的存儲單元，數(shù)據(jù)元素按邏輯順序依次存儲到相應存儲單元中，使得邏輯相鄰的數(shù)據(jù)元素物理也相鄰，因此可以實現(xiàn)隨

3、即訪問線性表的數(shù)據(jù)元素，即數(shù)據(jù)訪問的時間復雜度為O(1)。鏈表存儲方式分配的存儲單元可以不連續(xù)，通過每個結點的指針域來表示數(shù)據(jù)元素之間的邏輯關系，只能順序訪問線性表中的數(shù)據(jù)元素。40.若頻繁地對一個線性表進行插入和刪除操作，則該線性表宜采用何種存儲結構，為什么？參考答案：若頻繁地對一個線性表進行插入和刪除操作，則該線性表宜采用鏈式存儲結構。因此鏈式存儲結構在插入和刪除數(shù)據(jù)元素時不需要移動數(shù)據(jù)元素，只需要修改結點的指針域就可以改變數(shù)據(jù)元素

4、之間的邏輯關系。41.在單鏈表、雙向循環(huán)鏈表和單循環(huán)鏈表中，若僅知道指針p指向某結點，不知道頭指針，能否將結點p從相應的鏈表中刪除？若可以，時間復雜度各為多少。參考答案：要實現(xiàn)刪除p結點的操作，必須找到其前驅結點，修改其指針域的值使其指向p的后繼結點，以實現(xiàn)刪除結點p。單鏈表不行，因此不知道頭指針就無法找到結點p的前驅結點。雙向循環(huán)鏈表和單循環(huán)鏈表可以可以實現(xiàn)刪除p結點。單循環(huán)鏈表刪除p結點的時間復雜度為O(n)，雙循環(huán)鏈表刪除P結點的