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

《數(shù)據(jù)結構》練習冊

陜西理工學院計算機系數(shù)據(jù)結構精品課建設小組編

計算機科學與技術系

前言

《數(shù)據(jù)結構》練習冊依照《數(shù)據(jù)結構》課程的教學大綱編著，分為九章，主要題型包括：選擇題、判斷題、填空題和程序題，每章都從基礎出發(fā)，有少部分難度較大題型。編寫的目的是為了給學生提供一個練習和提高的平臺。可作為我校計算機科學與技術、信息系統(tǒng)與信息管理與網(wǎng)絡工程本科專業(yè)學生的輔助教材使用。由于編寫時間較倉促，有錯誤在所難免，敬請教師和學生提出寶貴看法。

計算機科學與技術系《數(shù)據(jù)結構》課程組

2023年8月

第一章緒論

一、選擇題

1.組成數(shù)據(jù)的基本單位是（）A．數(shù)據(jù)項B．數(shù)據(jù)類型C．數(shù)據(jù)元素D．數(shù)據(jù)變量2.數(shù)據(jù)結構是研究數(shù)據(jù)的（）以及它們之間的相互關系。A．理想結構，物理結構B．理想結構，抽象結構C．物理結構，規(guī)律結構D．抽象結構，規(guī)律結構3.在數(shù)據(jù)結構中，從規(guī)律上可以把數(shù)據(jù)結構分成（）。A．動態(tài)結構和靜態(tài)結構B．緊湊結構和非緊湊結構C．線性結構和非線性結構D．內(nèi)部結構和外部結構

4.數(shù)據(jù)結構是一門研究非數(shù)值計算的程序設計問題中計算機的（①）以及它們之間的（②）和運算等的學科。

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

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

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

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

1.數(shù)據(jù)規(guī)律結構包括________、________、________和________四種類型,其中樹形結構和圖形結構合稱為________。

2.在線性結構中,第一個結點________前驅(qū)結點,其余每個結點有且只有________個前驅(qū)結點；最終一個結點________后續(xù)結點,其余每個結點有且只有________個后續(xù)結點。

3.在樹形結構中,樹根結點沒有________結點,其余每個結點有且只有________個前驅(qū)結點；葉子結點沒有________結點,其余每個結點的后續(xù)結點可以________。

4.在圖形結構中,每個結點的前驅(qū)結點數(shù)和后續(xù)結點數(shù)可以________。

5.線性結構中元素之間存在________關系,樹形結構中元素之間存在________關系,圖形結構中元素之間存在________關系。

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

8.鏈式存儲結構與順序存儲結構相比較,主要優(yōu)點是________________________________。

1

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

四、算法分析題

1.求以下算法段的語句頻度及時間繁雜度for(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.在一個單鏈表中，若刪除p所指結點的后續(xù)結點，則執(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.以下有關線性表的表達中，正確的是（）。A．線性表中的元素之間隔是線性關系B．線性表中至少有一個元素

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

1.線性表的鏈接存儲，表中元素的規(guī)律順序與物理順序一定一致。（）2.假使沒有提供指針類型的語言，就無法構造鏈式結構。（）

3.線性結構的特點是只有一個結點沒有前驅(qū)，只有一個結點沒有后繼，其余的結點只有一個前驅(qū)和后繼。（）

2

4.語句p=p->next完成了指針負值并使p指針得到了p指針所指后繼結點的數(shù)據(jù)域值。（）5.要想刪除p指針的后繼結點，我們應當執(zhí)行q=p->next；p->next=q->next；free(q)。（）三、填空題

1.已知P為單鏈表中的非首尾結點，在P結點后插入S結點的語句為：________。

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

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

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

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

5.已知L是無表頭結點的單鏈表，是從以下提供的答案中選擇適合的語句序列，實現(xiàn)：表尾插入s結點的語句序列是________。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;四、算法設計題

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

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

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

4.某百貨公司倉庫中有一批電視機，按其價格從低到高的次序構成一個循環(huán)鏈表，每個結點有價格、數(shù)量和鏈指針三個域?，F(xiàn)新到m臺價格為h的電視機，試編寫算法修改原鏈表。

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

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

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

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