2023年6月
期末綜合練習一
一、單項選擇題
1．深度為5的完全二叉樹共有20個結點，則第5層上有（ ）個結點(根所在結點為第一層)。
a．3b．8c．5d．6
2．同一種邏輯結構（ ）。
a．只能有唯一的儲存結構
b．可以有不同的儲存結構
c．只能表示某一種資料元素之間的關係
d．以上三種說法均不正確
3．已知乙個圖的邊數為m，則該圖的所有頂點的度數之和為（ ）。
a．2m b．mc．2m+1 d．m/2
4．鍊錶所具備的特點是（ ）。
a．可以隨機訪問任一結點
b．占用連續的儲存空間
c．插入刪除元素的操作不需要移動元素結點
d．可以通過下標對鍊錶進行直接訪問
5．資料結構中，與所使用的計算機無關的是資料的（ ）結構。
a．物理 b．儲存 c．邏輯與物理 d．邏輯
6．資料的物理結構（ ）。
a．與資料的邏輯結構無關b．僅僅包括資料元素的表示
c．只包括資料元素間關係的表示 d．包括資料元素的表示和關係的表示
7．鍊錶所具備的特點是（ ）。
a．可以隨機訪問任一結點b．占用連續的儲存空間
c．插入刪除不需要移動元素結點 d．可以通過下標對鍊錶進行直接訪問
8．線性結構中資料元素的位置之間存在（ ）的關係。
a．一對一b．一對多
c．多對多d．每乙個元素都有乙個直接前驅和乙個直接後繼
9．線性表只要以（ ）方式儲存就能進行折半查詢。
a．鏈結 b．順序c．關鍵字有序的順序 d．二叉樹
10．以下表中可以隨機訪問的是（ ）。
a．單向鍊錶b．雙向鍊錶
c．單向迴圈鍊錶d．順序表
11．雜湊查詢的原理是（ ）。
a．在待查記錄的關鍵字值與該記錄的儲存位置之間建立確定的對應關係
b．按待查記錄的關鍵字有序的順序方式儲存
c．按關鍵字值的比較進行查詢
d．基於二分查詢的方法
12．演算法的時間複雜度與（ ）有關。
a．所使用的計算機 b．與計算機的作業系統
c．與演算法本身d．與資料結構
13．對n個元素進行氣泡排序若某趟冒泡中只進行了（ ）次元素間的交換，則表明序列已經排好序。
a．1b．2c．0d．n-1
14．設有乙個長度為n的順序表，要刪除第i個元素需移動元素的個數為（ ）。
a．n-i+1 b．n-i c．n-i-1 d．i
15．排序過程中，每一趟從無序子表中將乙個待排序的記錄按其關鍵字的大小放置到已經排好序的子串行的適當位置，直到全部排好序為止，該排序演算法是( )。
a．直接插入排序b．快速排序
c．氣泡排序d．選擇排序
16．在乙個單鏈表中，p、q分別指向表中兩個相鄰的結點，且q所指結點是p所指結點的直接後繼，現要刪除q所指結點，可用的語句是（ ）。
a．p=q->next b．p->next=q c．p->next=qnext d．q->next=null
17．在對一組元素（64，48，106，33，25，82，70，55，93）進行直接插入排序時，當進行到要把第7個元素70插入到已經排好序的子表時，為找到插入位置，需進行（ ）次元素間的比較（指由小到大排序）。
a．6b．2c．3d．4
18．從乙個棧頂指標為top的鏈棧中刪除乙個結點時，用變數x儲存被刪結點的值，則執行（ ）。
a．x=top->data; top=top->next; b．x=top->data;
c．top=top->next; x=top->data; d．top=top->next; x=data;
19．採用順序查詢法對長度為n的線性表進行查詢（不採用表尾設監視哨的方法），最壞的情況下要進行（ ）次元素間的比較。
a．n+2 b．nc．n-1d．n/2
20．在乙個鏈隊中，假設f和r分別為隊頭和隊尾指標，則刪除乙個結點的運算為（ ）。
a．r=f->next; b．r=r->next; c．f=f->next; d．f=r->next;
21．如圖1，若從頂點a出發按廣度優先搜尋法進行遍歷，則可能得到的頂點序列為（ ）。
a．acebdgf
b．abecdgf
c．acfedgb
d．abecfdg
圖122．乙個棧的進棧序列是a，b，c，d，e，則棧的不可能輸出序列是（ ）（進棧出棧可以交替進行）。
a．dceab b．edcba c．decba d．abcde
23．元素2，4，6，8按順序依次進棧，則該棧的不可能輸出序列是（ ）（進棧出棧可以交替進行）。
a．8，6，4，2b．2，4，6，8
c．4，2，8，6d．8，6，2，4
24．有乙個長度為10的有序表，按折半查詢對該錶進行查詢，在等概率情況下查詢成功的平均比較次數為（ ）。
a．26/10 b．29/10 c．29/9 d．31/10
25．排序方法中，從未排序序列中挑選元素，並將其依次放入已排序序列（初始為空）的一端的方法，稱為（ ）排序。
a．歸併 b．插入 c．選擇 d．快速
26．排序演算法中，從未排序序列中依次取出元素與已排序序列（初始為空）中的元素進行比較（要求比較次數盡量少），然後將其放入已排序序列的正確位置的方法是（ ）。
a．冒泡 b．直接插入 c．折半插入 d．選擇排序
27．一棵哈夫曼樹總共有23個結點，該樹共有（ ）個葉結點（終端結點）
a．10b．13c．11d．12
28．設有乙個10階的對稱矩陣a，採用壓縮儲存的方式，將其下三角部分以行序為主儲存到一維陣列b中（陣列下標從1開始），則矩陣中元素a8,5在一維陣列b中的下標是（ ）。
a．33b．32c．85d．41
29．佇列的插入操作在（ ）進行。
a．隊頭 b．隊尾 c．隊頭或隊尾d．在任意指定位置
30．在乙個無向圖中，所有頂點的度數之和等於邊數的（ ）倍。
a．3b．2.5c．1.5d．2
二、填空題
1．一棵二叉樹沒有單分支結點，有6個葉結點，則該樹總共有________個結點。
2．棧和佇列的操作特點分別是和
3．設一棵完全二叉樹，其最高層上最右邊的葉結點的編號為奇數，該葉節點的雙親結點的編號為10，該完全二叉樹一共有________個結點。
4．結構中的資料元素存在多對多的關係稱為結構。
5．按照二叉樹的遞迴定義，對二叉樹遍歷的常用演算法有三種。
6．根據資料元素間關係的不同特性，通常可分為集合、線性四類基本結構。
7．資料結構中的資料元素存在一對多的關係稱為________結構。
8．要求在n個資料元素中找其中值最大的元素，設基本操作為元素間的比較。則比較的次數和演算法的時間複雜度分別為________和
9．把資料儲存到計算機中,並具體體現資料之間的邏輯結構稱為________結構。
10．在乙個單向鍊錶中p所指結點之後插入乙個s所指向的結點時，應執行和p->next=s;的操作。
11．結構中的資料元素存在一對一的關係稱為________結構。
12．在二叉樹的鏈式儲存結構中，通常每個結點中設定三個域，它們是值域 、
13．如圖2所示的二叉樹，其後序遍歷序列為
圖214．一棵二叉樹中順序編號為i的結點，若它存在左、右孩子，則左、右孩子編號分別為
15．n個元素進行冒泡法排序，通常需要進行________趟冒泡。
16．向乙個棧頂指標為h的鏈棧中插入乙個s所指結點時，可執行s->next=h;和________。
資料結構 本 期末綜合練習
2008年12月6日 一 單項選擇題 每小題2分 1 針對線性表，在儲存後如果最常用的操作是取第i個結點及其前驅，則採用 儲存方式最節省時間。a 單鏈表 b 順序表 c 單迴圈鍊錶 d 雙鏈表 2 鍊錶所具備的特點是 a 可以隨機訪問任一結點 b 占用連續的儲存空間 c 可以通過下標對鍊錶進行直接訪...
資料結構 本 期末綜合練習
2015年11月 綜合練習一 一 單項選擇題 1.對稀疏矩陣進行壓縮儲存,可採用三元組表，乙個10 行8列的稀疏矩陣a共有73 個零元素，其相應的三元組表共有 c 個元素。a 8b 80 c 7d 10 2.對稀疏矩陣進行壓縮儲存,可採用三元組表，乙個10 行8列的稀疏矩陣a，其相應的 三元組表共有...
資料結構練習
華東理工大學網路學院 資料結構 ch1緒論和ch2線性表 班級學號姓名成績 一 名詞解釋 每小題2分，共10分 1.資料結構 2.線性結構 3.儲存結構 4.邏輯結構 5.非線性結構 答 1.資料結構 指的是資料之間的相互關係，即資料的組織形式。一般包括三個方面的內容 資料的邏輯結構 儲存結構和資料...