數(shù)據(jù)結(jié)構(gòu)題集答案

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)題集答案數(shù)據(jù)結(jié)構(gòu)題集

第一章緒論

一、單項(xiàng)選擇題

1.在數(shù)據(jù)結(jié)構(gòu)中，從規(guī)律上可以把數(shù)據(jù)結(jié)構(gòu)分成。A.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C.線性結(jié)構(gòu)和非線性結(jié)構(gòu)D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)2.數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示是指。A.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)B.數(shù)據(jù)結(jié)構(gòu)

C.數(shù)據(jù)結(jié)構(gòu)的規(guī)律結(jié)構(gòu)D.數(shù)據(jù)元素之間的關(guān)系3.是數(shù)據(jù)的最小單位，是數(shù)據(jù)的基本單位。A.數(shù)據(jù)項(xiàng)B.數(shù)據(jù)元素C.信息項(xiàng)D.表元素

4.計(jì)算機(jī)所處理數(shù)據(jù)一般具有某種內(nèi)在聯(lián)系，這是指。

A.數(shù)據(jù)與數(shù)據(jù)之間存在某種關(guān)系B.數(shù)據(jù)元素與數(shù)據(jù)元素之間存在某種關(guān)系C.元素內(nèi)部存在某種結(jié)構(gòu)D.數(shù)據(jù)項(xiàng)與數(shù)據(jù)項(xiàng)之間存在某種關(guān)系5.算法分析的目的是。

A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究輸入和輸出的關(guān)系C.分析算法的效率以求改進(jìn)D.分析算法的易懂性

6.在存儲(chǔ)數(shù)據(jù)時(shí)，不僅要考慮存儲(chǔ)各數(shù)據(jù)元素的值，而且還要存儲(chǔ)。A.數(shù)據(jù)處理的方法B.數(shù)據(jù)元素的類型C.數(shù)據(jù)元素之間的關(guān)系D.數(shù)據(jù)的存儲(chǔ)方法7.算法分析的主要任務(wù)是分析。A.算法是否具有較好的可讀性

B.算法中是否存儲(chǔ)語(yǔ)法錯(cuò)誤和規(guī)律錯(cuò)誤C.算法的功能是否符合設(shè)計(jì)要求

D.算法的執(zhí)行時(shí)間與問(wèn)題規(guī)模之間的關(guān)系。8.數(shù)據(jù)的運(yùn)算。

A.效率與采用何種存儲(chǔ)結(jié)構(gòu)有關(guān)B.是根據(jù)存儲(chǔ)結(jié)構(gòu)來(lái)定義的

C.有算術(shù)運(yùn)算和關(guān)系運(yùn)算兩大類D.必需用程序設(shè)計(jì)語(yǔ)言來(lái)描述

9.算法的計(jì)算量的大小稱為算法的。

A.效率B.時(shí)間繁雜度C.現(xiàn)實(shí)性D.難度10.連續(xù)存儲(chǔ)分派時(shí)，存儲(chǔ)單元的地址。A.一定連續(xù)B.一定不連續(xù)

C.不一定連續(xù)D.部分連續(xù)，部分不連續(xù)二、判斷題

1.數(shù)據(jù)元素是數(shù)據(jù)結(jié)構(gòu)的最小單位。

2.數(shù)據(jù)的規(guī)律結(jié)構(gòu)說(shuō)明數(shù)據(jù)元素之間的順序關(guān)系，它依靠于計(jì)算機(jī)的存儲(chǔ)結(jié)構(gòu)。3.數(shù)據(jù)的規(guī)律結(jié)構(gòu)指數(shù)據(jù)元素的各數(shù)據(jù)項(xiàng)之間的規(guī)律關(guān)系。4.算法的優(yōu)劣與算法的描述語(yǔ)言無(wú)關(guān)，但與使用的計(jì)算機(jī)有關(guān)。5.數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與具體實(shí)現(xiàn)有關(guān)。

三、填空題

1.數(shù)據(jù)的規(guī)律結(jié)構(gòu)指數(shù)據(jù)元素之間的規(guī)律關(guān)系。2.一個(gè)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示稱為存儲(chǔ)結(jié)構(gòu)。

3.數(shù)據(jù)的物理結(jié)構(gòu)主要包括順序存儲(chǔ)結(jié)構(gòu)的表示和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的表示。4.數(shù)據(jù)規(guī)律結(jié)構(gòu)包括集合、線性結(jié)構(gòu)、樹(shù)和圖四種，樹(shù)結(jié)構(gòu)和圖結(jié)構(gòu)統(tǒng)稱為非線性結(jié)構(gòu)。

5.順序存儲(chǔ)方法把規(guī)律上規(guī)律上相鄰的元素存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元里；鏈?zhǔn)酱鎯?chǔ)方法中結(jié)點(diǎn)間的規(guī)律關(guān)系是由指針域表示的。6、數(shù)據(jù)結(jié)構(gòu)研究的是規(guī)律結(jié)構(gòu)和物理結(jié)構(gòu)以及它們之間的相互關(guān)系，并對(duì)于這種結(jié)構(gòu)定義相應(yīng)的運(yùn)算，設(shè)計(jì)出相應(yīng)的算法。7.算法的執(zhí)行時(shí)間是問(wèn)題規(guī)模n的函數(shù)。

8.以下是4個(gè)算法所有語(yǔ)句頻度之和的表達(dá)式，其中的繁雜度一致的是A和B。A.TA(n)=2n3+3n2+1000B.TB(n)=n3-n2log2n-1000C.TC(n)=n2log2n+n2D.TD(n)=n2+1000四、解答題

1.簡(jiǎn)述數(shù)據(jù)的規(guī)律結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)的關(guān)系。

答：在數(shù)據(jù)結(jié)構(gòu)中，規(guī)律結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)是密切相關(guān)的，存儲(chǔ)結(jié)構(gòu)不僅將數(shù)據(jù)元素存儲(chǔ)到計(jì)算機(jī)中，而且還要表示各數(shù)據(jù)元素之間的規(guī)律關(guān)系。規(guī)律結(jié)構(gòu)與計(jì)算機(jī)無(wú)關(guān)，存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中的表示。尋常狀況下，一種規(guī)律結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，例如，線性結(jié)構(gòu)可以采取順序存儲(chǔ)結(jié)構(gòu)或鏈?zhǔn)酱娲纸Y(jié)構(gòu)表示。2.數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型有什么區(qū)別？答：數(shù)據(jù)結(jié)構(gòu)是相互間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，一般包括三個(gè)方面的內(nèi)容：數(shù)據(jù)的規(guī)律結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和多數(shù)據(jù)的運(yùn)算。數(shù)據(jù)類型是一個(gè)值得集合和定義在這個(gè)值集上的一組操作的總稱。數(shù)據(jù)結(jié)構(gòu)重點(diǎn)考慮元素之間的關(guān)系，數(shù)據(jù)類型重點(diǎn)考慮數(shù)據(jù)的個(gè)體特征。

3.當(dāng)為解決某一問(wèn)題已經(jīng)選定其數(shù)據(jù)的規(guī)律結(jié)構(gòu)后，選擇數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)時(shí)，應(yīng)從哪些方面考慮？

答：尋常從兩個(gè)方面考慮：第一是算法實(shí)現(xiàn)的存儲(chǔ)空間繁雜度；其次是算法執(zhí)行的時(shí)間繁雜度。若存儲(chǔ)空間難以確定，宜選擇鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，否則選擇順序存儲(chǔ)結(jié)構(gòu)。若插入、刪除操作頻繁，則選鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，否則選擇順序存儲(chǔ)結(jié)構(gòu)。

其次章線性表

一、單項(xiàng)選擇題

1.鏈表不具備的特點(diǎn)是。

A.可隨機(jī)訪問(wèn)任一結(jié)點(diǎn)B.插入刪除不需要移動(dòng)元素C.不必事先估算存儲(chǔ)空間D.所需空間與其長(zhǎng)度成正比2.設(shè)線性表有n個(gè)元素，以下操作中，在順序表上實(shí)現(xiàn)比在鏈表上實(shí)現(xiàn)效率更高。A.輸出第i（1≤i≤n）個(gè)元素的值B.順序輸出這n個(gè)元素

C.交換第1個(gè)與第2個(gè)元素的值

D.輸出與給定值x相等的元素在線性表中的序號(hào)

3.假使最常用的操作是取第i個(gè)結(jié)點(diǎn)及其前驅(qū)，則采用存儲(chǔ)方法最節(jié)省時(shí)間。A.單鏈表B.雙鏈表C.線性鏈表D.順序表4.線性表是具有n個(gè)的有限序列（n≥0）。A.表元素B.字符C.數(shù)據(jù)元素D.數(shù)據(jù)項(xiàng)5.下面關(guān)于線性表的表達(dá)中，錯(cuò)誤的是。

A.線性表采用順序存儲(chǔ)，則必需占用一片連續(xù)的存儲(chǔ)單元B.線性表采用順序存儲(chǔ)，則便于插入和刪除操作

C.線性表采用鏈?zhǔn)酱鎯?chǔ)，則不必占用一片連續(xù)的存儲(chǔ)單元D.線性表采用鏈?zhǔn)酱鎯?chǔ)，則便于插入和刪除操作6.線性表的順序存儲(chǔ)結(jié)構(gòu)是一種。

A.隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)B.順序存取的存儲(chǔ)結(jié)構(gòu)C.索引存取的存儲(chǔ)結(jié)構(gòu)D.Hash存取的存儲(chǔ)結(jié)構(gòu)7.單鏈表中增加一個(gè)頭結(jié)點(diǎn)的目的是為了。

A.使單鏈表至少有一個(gè)結(jié)點(diǎn)B.標(biāo)識(shí)表首結(jié)點(diǎn)的位置C.便利運(yùn)算的實(shí)現(xiàn)D.說(shuō)明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)

8.不帶頭結(jié)點(diǎn)的單鏈表（頭指針為h）為空的條件是。A.h==NULLB.h->next==NULLC.h->next==hD.h!=NULL

9.帶頭結(jié)點(diǎn)的單鏈表（頭指針為h）為空的條件是。A.h==NULLB.h->next==NULLC.h->next==hD.h!=NULL

10.帶頭結(jié)點(diǎn)的循環(huán)雙向鏈表（頭指針為L(zhǎng)）為空的條件是。A.L==NULLB.L->next->prior==NULLC.L->prior==NULLD.L->next==L

11.非空的循環(huán)單鏈表（頭指針為head）的尾結(jié)點(diǎn)（由p指向）滿足。A.p->next==NULLB.p==NULLC.p->next==headD.p==head

12.設(shè)一個(gè)鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，則選用最節(jié)省時(shí)間。A.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表B.單循環(huán)鏈表C.帶尾指針的單循環(huán)鏈表D.單鏈表

13.若某線性表最常用的操作存取任意指定序號(hào)的元素和在表尾進(jìn)行插入和刪除，則選用的存儲(chǔ)方式最節(jié)省時(shí)間。

A.順序表B.雙鏈表C.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D.單循環(huán)鏈表

14.在n個(gè)結(jié)點(diǎn)的線性表的順序?qū)崿F(xiàn)中，算法的時(shí)間繁雜度為O(1)的操作是。A.訪問(wèn)第i個(gè)結(jié)點(diǎn)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)B.在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)C.刪除第i個(gè)結(jié)點(diǎn)D.以上都不對(duì)15.若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間繁雜度為。

A.O(0)B.O(1)C.O(n)D.O(n2)

16.對(duì)于順序存儲(chǔ)的線性表，訪問(wèn)結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間繁雜度為。A.O(n)O(n)B.O(n)O(1)C.O(1)O(n)D.O(1)O(1)

17.線性表以鏈?zhǔn)椒绞酱鎯?chǔ)，訪問(wèn)第i個(gè)結(jié)點(diǎn)的時(shí)間繁雜度為。A.O(i)B.O(1)C.O(n)D.O(i-1)18.循環(huán)鏈表H尾結(jié)點(diǎn)p的特點(diǎn)是。A.p->next==HB.p->next==H->nextC.p==HD.p==H->next二、判斷題

1.取線性表的第i個(gè)元素的時(shí)間同i的大小有關(guān)。

2.線性表中每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼。3.順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。

4.線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)空間可以不連續(xù)。

5.在一個(gè)設(shè)有頭指針和尾指針的單鏈表中，執(zhí)行刪除單鏈表最終一個(gè)結(jié)點(diǎn)的操作與鏈表的長(zhǎng)度無(wú)關(guān)。三、填空題

1.向一個(gè)長(zhǎng)度為n的順序表中的第i個(gè)元素之前插入一個(gè)元素時(shí)，需要向后移動(dòng)n-i+1個(gè)元素。

2.在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素時(shí)，需要向前移動(dòng)n-i個(gè)元素。3.在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是簡(jiǎn)化插入、刪除算法。

4.在單鏈中要?jiǎng)h除某一指定結(jié)點(diǎn)，必需找到該結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)。5.訪問(wèn)單鏈表中的結(jié)點(diǎn)，必需沿著指針域依次進(jìn)行。

6.在雙鏈表中每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向直接前驅(qū)結(jié)點(diǎn)，一個(gè)指向直接后繼結(jié)點(diǎn)。

7.在雙向循環(huán)鏈表中，刪除最終一個(gè)結(jié)點(diǎn)的算法時(shí)間繁雜度為O(1)。8.訪問(wèn)一個(gè)線性表中具有給定值的時(shí)間繁雜度的數(shù)量級(jí)是O(n)。

9.由n個(gè)數(shù)據(jù)元素生成一個(gè)順序表，若每次都調(diào)用插入算法把一個(gè)元素插入到表頭，則整個(gè)算法的時(shí)間繁雜度為O(n)，若每次都調(diào)用插入算法把一個(gè)元素插入到表尾，則整個(gè)算法的時(shí)間繁雜度為O(n2)。

10.在雙向鏈表中，可以用表尾指針代替表頭指針。

11.根據(jù)n個(gè)數(shù)據(jù)元素建立對(duì)應(yīng)的順序表和單鏈表存儲(chǔ)結(jié)構(gòu)，其算法的時(shí)間繁雜度最好的狀況是O(n)，最壞的狀況是O(n2)。

12.求線性表的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的長(zhǎng)度的算法時(shí)間繁雜度分別是O(1)和O(n)。

13.在一個(gè)帶頭結(jié)點(diǎn)的單鏈表中，在表頭插入或刪除與在其他位置插入或刪除，其操作過(guò)程是否一致？一致。

14.在一個(gè)不帶頭結(jié)點(diǎn)的單鏈表中，在表頭插入或刪除與在其他位置插入或刪除，其操作過(guò)程是否一致？不一致。四、簡(jiǎn)答題

1.闡述順序表和鏈表存儲(chǔ)方式的特點(diǎn)。答：順序表存儲(chǔ)方式為數(shù)據(jù)分派連續(xù)的存儲(chǔ)單元，數(shù)據(jù)元素按規(guī)律順序依次存儲(chǔ)到相應(yīng)存儲(chǔ)單元中，使得規(guī)律相鄰的數(shù)據(jù)元素物理也相鄰，因此可以實(shí)現(xiàn)隨機(jī)訪問(wèn)線性表的數(shù)據(jù)元素，即數(shù)據(jù)訪問(wèn)的時(shí)間繁雜度為O(1)。

鏈表存儲(chǔ)方式分派的存儲(chǔ)單元可以不連續(xù)，通過(guò)每個(gè)結(jié)點(diǎn)的指針域來(lái)表示數(shù)據(jù)元素之間的規(guī)律關(guān)系，只能順序訪問(wèn)線性表中的數(shù)據(jù)元素。

2.若頻繁地對(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ù)元素之間的規(guī)律關(guān)系。

3.在單鏈表、雙向循環(huán)鏈表和單循環(huán)鏈表中，若僅知道指針p指向某結(jié)點(diǎn)，不知道頭指針，能否將結(jié)點(diǎn)p從相應(yīng)的鏈表中刪除？若可以，時(shí)間繁雜度各為多少。

答：要實(shí)現(xiàn)刪除p結(jié)點(diǎn)的操作，必需找到其前驅(qū)結(jié)點(diǎn)，修改其指針域的值使其指向p的后繼結(jié)點(diǎn)，以實(shí)現(xiàn)刪除結(jié)點(diǎn)p。單鏈表不行，由于