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

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

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

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

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