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

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

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

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