數(shù)據(jù)結(jié)構(gòu)習(xí)題集1

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

《數(shù)據(jù)結(jié)構(gòu)》練習(xí)冊(cè)

陜西理工學(xué)院計(jì)算機(jī)系數(shù)據(jù)結(jié)構(gòu)精品課建設(shè)小組編

計(jì)算機(jī)科學(xué)與技術(shù)系

前言

《數(shù)據(jù)結(jié)構(gòu)》練習(xí)冊(cè)依照《數(shù)據(jù)結(jié)構(gòu)》課程的教學(xué)大綱編著，分為九章，主要題型包括：選擇題、判斷題、填空題和程序題，每章都從基礎(chǔ)出發(fā)，有少部分難度較大題型。編寫的目的是為了給學(xué)生提供一個(gè)練習(xí)和提高的平臺(tái)?？勺鳛槲倚Ｓ?jì)算機(jī)科學(xué)與技術(shù)、信息系統(tǒng)與信息管理與網(wǎng)絡(luò)工程本科專業(yè)學(xué)生的輔助教材使用。由于編寫時(shí)間較倉(cāng)促，有錯(cuò)誤在所難免，敬請(qǐng)教師和學(xué)生提出寶貴看法。

計(jì)算機(jī)科學(xué)與技術(shù)系《數(shù)據(jù)結(jié)構(gòu)》課程組

2023年8月

第一章緒論

一、選擇題

1.組成數(shù)據(jù)的基本單位是（）A．?dāng)?shù)據(jù)項(xiàng)B．?dāng)?shù)據(jù)類型C．?dāng)?shù)據(jù)元素D．?dāng)?shù)據(jù)變量2.數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的（）以及它們之間的相互關(guān)系。A．理想結(jié)構(gòu)，物理結(jié)構(gòu)B．理想結(jié)構(gòu)，抽象結(jié)構(gòu)C．物理結(jié)構(gòu)，規(guī)律結(jié)構(gòu)D．抽象結(jié)構(gòu)，規(guī)律結(jié)構(gòu)3.在數(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)

4.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的（①）以及它們之間的（②）和運(yùn)算等的學(xué)科。

①A．?dāng)?shù)據(jù)元素B．計(jì)算方法C．規(guī)律存儲(chǔ)D．?dāng)?shù)據(jù)映像②A．結(jié)構(gòu)B．關(guān)系C．運(yùn)算D．算法5.算法分析的兩個(gè)主要方面是（）。A．?dāng)?shù)據(jù)繁雜性和程序繁雜性B．正確性和簡(jiǎn)明性C．可讀性和簡(jiǎn)明性D．空間繁雜性和時(shí)間繁雜性6.算法分析的目的是（）。A．找出數(shù)據(jù)結(jié)構(gòu)的合理性B．研究算法中的輸入和輸出的關(guān)系C．分析算法的效率以求改進(jìn)D．分析算法的易懂性和文檔性7.計(jì)算機(jī)算法指的是（①）,它必需具備輸入、輸出和（②）等5個(gè)特性。①A．計(jì)算方法B．排序方法C．解決問(wèn)題的有限運(yùn)算序列D．調(diào)度方法②A．可執(zhí)行性，可移植性和可擴(kuò)展性B．可行性，確定性和有窮性C．確定性、有窮性和穩(wěn)定性D．易讀性、穩(wěn)定性和安全性二、判斷題

1.數(shù)據(jù)的機(jī)內(nèi)表示稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。（）2.算法就是程序。（）

3.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（）

4.算法的五個(gè)特性為：有窮性、輸入、輸出、完成性和確定性。（）5.算法的時(shí)間繁雜度取決于問(wèn)題的規(guī)模和待處理數(shù)據(jù)的初態(tài)。（）三、填空題

1.數(shù)據(jù)規(guī)律結(jié)構(gòu)包括________、________、________和________四種類型,其中樹(shù)形結(jié)構(gòu)和圖形結(jié)構(gòu)合稱為_(kāi)_______。

2.在線性結(jié)構(gòu)中,第一個(gè)結(jié)點(diǎn)________前驅(qū)結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有________個(gè)前驅(qū)結(jié)點(diǎn)；最終一個(gè)結(jié)點(diǎn)________后續(xù)結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有________個(gè)后續(xù)結(jié)點(diǎn)。

3.在樹(shù)形結(jié)構(gòu)中,樹(shù)根結(jié)點(diǎn)沒(méi)有________結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有________個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒(méi)有________結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)可以________。

4.在圖形結(jié)構(gòu)中,每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以________。

5.線性結(jié)構(gòu)中元素之間存在________關(guān)系,樹(shù)形結(jié)構(gòu)中元素之間存在________關(guān)系,圖形結(jié)構(gòu)中元素之間存在________關(guān)系。

6.算法的五個(gè)重要特性是________、________、________、________、________。7.數(shù)據(jù)結(jié)構(gòu)的三要素是指________、________和________。

8.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)相比較,主要優(yōu)點(diǎn)是________________________________。

1

9.設(shè)有一批數(shù)據(jù)元素,為了最快的存儲(chǔ)某元素,數(shù)據(jù)結(jié)構(gòu)宜用________結(jié)構(gòu),為了便利插入一個(gè)元素,數(shù)據(jù)結(jié)構(gòu)宜用________結(jié)構(gòu)。

四、算法分析題

1.求以下算法段的語(yǔ)句頻度及時(shí)間繁雜度f(wàn)or(i=1;inext=p;p->next=s;B．s->next=p->next;p->next=s;C．s->next=p->next;p=s;D．p->next=s;s->next=p;5.在一個(gè)單鏈表中，若刪除p所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行（）。A．p->next=p->next->next;B．p=p->next;p->next=p->next->next;C．p->next=p->next;D．p=p->next->next;6.以下有關(guān)線性表的表達(dá)中，正確的是（）。A．線性表中的元素之間隔是線性關(guān)系B．線性表中至少有一個(gè)元素

C．線性表中任何一個(gè)元素有且僅有一個(gè)直接前趨D．線性表中任何一個(gè)元素有且僅有一個(gè)直接后繼7.線性表是具有n個(gè)（）的有限序列（n≠0)。A．表元素B．字符C．?dāng)?shù)據(jù)元素D．?dāng)?shù)據(jù)項(xiàng)二、判斷題

1.線性表的鏈接存儲(chǔ)，表中元素的規(guī)律順序與物理順序一定一致。（）2.假使沒(méi)有提供指針類型的語(yǔ)言，就無(wú)法構(gòu)造鏈?zhǔn)浇Y(jié)構(gòu)。（）

3.線性結(jié)構(gòu)的特點(diǎn)是只有一個(gè)結(jié)點(diǎn)沒(méi)有前驅(qū)，只有一個(gè)結(jié)點(diǎn)沒(méi)有后繼，其余的結(jié)點(diǎn)只有一個(gè)前驅(qū)和后繼。（）

2

4.語(yǔ)句p=p->next完成了指針負(fù)值并使p指針得到了p指針?biāo)负罄^結(jié)點(diǎn)的數(shù)據(jù)域值。（）5.要想刪除p指針的后繼結(jié)點(diǎn)，我們應(yīng)當(dāng)執(zhí)行q=p->next；p->next=q->next；free(q)。（）三、填空題

1.已知P為單鏈表中的非首尾結(jié)點(diǎn)，在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語(yǔ)句為：________。

2.順序表中規(guī)律上相鄰的元素物理位置()相鄰，單鏈表中規(guī)律上相鄰的元素物理位置________相鄰。

3.線性表L＝（a1，a2，...，an）采用順序存儲(chǔ)，假定在不同的n＋1個(gè)位置上插入的概率一致，則插入一個(gè)新元素平均需要移動(dòng)的元素個(gè)數(shù)是________。

4.在非空雙向循環(huán)鏈表中，在結(jié)點(diǎn)q的前面插入結(jié)點(diǎn)p的過(guò)程如下：

p->prior=q->prior;q->prior->next=p;p->next=q;________;

5.已知L是無(wú)表頭結(jié)點(diǎn)的單鏈表，是從以下提供的答案中選擇適合的語(yǔ)句序列，實(shí)現(xiàn)：表尾插入s結(jié)點(diǎn)的語(yǔ)句序列是________。A．p->next=s;B．p=L;C．L=s;D．p->next=s->next;E．s->next=p->next;F．s->next=L;G．s->next=null;H．while(p->next!=0)p=p->next;I．while(p->next!=null)p=p->next;四、算法設(shè)計(jì)題

1.試編寫一個(gè)求已知單鏈表的數(shù)據(jù)域的平均值的函數(shù)（數(shù)據(jù)域數(shù)據(jù)類型為整型）。

2.已知帶有頭結(jié)點(diǎn)的循環(huán)鏈表中頭指針為head,試寫出刪除并釋放數(shù)據(jù)域值為x的所有結(jié)點(diǎn)的c函數(shù)。

3.某百貨公司倉(cāng)庫(kù)中有一批電視機(jī)，按其價(jià)格從低到高的次序構(gòu)成一個(gè)循環(huán)鏈表，每個(gè)結(jié)點(diǎn)有價(jià)格、數(shù)量和鏈指針三個(gè)域?，F(xiàn)出庫(kù)（銷售）m臺(tái)價(jià)格為h的電視機(jī)，試編寫算法修改原鏈表。

4.某百貨公司倉(cāng)庫(kù)中有一批電視機(jī)，按其價(jià)格從低到高的次序構(gòu)成一個(gè)循環(huán)鏈表，每個(gè)結(jié)點(diǎn)有價(jià)格、數(shù)量和鏈指針三個(gè)域。現(xiàn)新到m臺(tái)價(jià)格為h的電視機(jī)，試編寫算法修改原鏈表。

5.線性表中的元素值按遞增有序排列，針對(duì)順序表和循環(huán)鏈表兩種不同的存儲(chǔ)方式，分別編寫C函數(shù)刪除線性表中值介于a與b（a≤b）之間的元素。

6.設(shè)A=(a0,a1,a2,...,an-1),B=(b0,b1,b2,...,bm-1)是兩個(gè)給定的線性表,它們的結(jié)點(diǎn)個(gè)數(shù)分別是n和m,且結(jié)點(diǎn)值均是整數(shù)。

若n=m，且ai=bi（0≤iB。試編寫一個(gè)比較A和B的C函數(shù)，該函數(shù)返回-1或0或1，分別表示AB。7.試編寫算法,刪除雙向循環(huán)鏈表中第k個(gè)結(jié)點(diǎn)。

8.線性表由前后兩部分性質(zhì)不同的元素組成(a0,a1,...,an-1,b0,b1,...,bm-1),m和n為兩部分元素的個(gè)數(shù),若線性表分別采用數(shù)組和鏈表兩種方式存儲(chǔ),編寫算法將兩部分元素?fù)Q位成(b0,b1,...,bm-1,a0,a1,...,an-1),分析兩種存儲(chǔ)方式下算法的時(shí)間