（2023年12月6日）
一、單項選擇題（每小題2分）
1．針對線性表，在儲存後如果最常用的操作是取第i個結點及其前驅，則採用（ ）儲存方式最節省時間。
a．單鏈表 b．順序表 c．單迴圈鍊錶 d．雙鏈表
2．鍊錶所具備的特點是（ ）。
a．可以隨機訪問任一結點
b．占用連續的儲存空間
c．可以通過下標對鍊錶進行直接訪問
d．插入刪除元素的操作不需要移動元素結點
3．資料結構中，與所使用的計算機無關的是資料的（ ）結構。
a．物理 b．儲存 c．邏輯 d．邏輯與物理
4．線性結構中資料元素的位置之間存在（ ）的關係。
a．一對多b．一對一
c．多對多d．每乙個元素都有乙個直接前驅和乙個直接後繼
5．以下特徵中，（ ）不是演算法的特性。
a．有窮性 b．確定性 c．有0個或多個輸出 d．可行性
6．演算法的時間複雜度與（ ）有關。
a．所使用的計算機 b．與計算機的作業系統
c．與資料結構d．與演算法本身
7．設有乙個長度為n的順序表，要在第i個元素之前（也就是插入元素作為新錶的第i個元素），則移動元素個數為（ ）。
a．n-i+1 b．n-i c．n-i-1d．i
8．在乙個單鏈表中，p、q分別指向表中兩個相鄰的結點，且q所指結點是p所指結點的直接後繼，現要刪除q所指結點，可用的語句是（ ）。
a．p=q->next b．p->next=q c．p->next=qnext d．q->next=null
9．棧的插入刪除操作在（ ）進行。
a．棧底 b．棧頂 c．任意位置 d．指定位置
10．在乙個鏈隊中，假設f和r分別為隊頭和隊尾指標，則刪除乙個結點的運算為（ ）。
a．r=f->next; b．r=r->next; c．f=r->next; d．f=f->next;
11．以下說法正確的是（ ）。
a．棧的特點是先進先出，佇列的特點是先進後出 b．棧和佇列的特點都是先進後出
c．棧的特點是先進後出，佇列的特點是先進先出 d．棧和佇列的特點都是先進先出
12．元素3，6，9按順序依次進棧，則該棧的不可能輸出序列是（ ）（進棧出棧可以交替進行）。
a．9，3，6b．9，6，3
c．6，3，9d．3，9，6
13．元素2，4，6，8按順序依次進棧，則該棧的不可能輸出序列是（ ）（進棧出棧可以交替進行）。
a．8，6，4，2b．2，4，6，8
c．4，2，8，6d．8，6，2，4
14．設有乙個10階的對稱矩陣a，採用壓縮儲存的方式，將其下三角部分以行序為主儲存到一維陣列b中（陣列下標從1開始），則矩陣中元素a8,5在一維陣列b中的下標是（ ）。
a．33b．32c．85d．41
15．設有乙個15階的對稱矩陣a，採用壓縮儲存的方式，將其下三角部分以行序為主序儲存到一維陣列b中（陣列下標從1開始），則矩陣中元素a7,6在一維陣列b中的下標是（ ）。
a．42b．13c．27d．32
16．在c語言中，順序儲存長度為3的字串，需要占用（ ）個位元組。
a．3 b．4c．6d．12
17．串函式strcmp（「d」，「d」）的值為（ ）。
a．0b．1c．-1d．3
18．一棵有n個結點採用鏈式儲存的二叉樹中，共有（ ）個指標域為空。
a．n+1b．nc．n-1d．n-2
19．在一棵二叉樹中，若編號為i的結點存在右孩子，則右孩子的順序編號為（ ）。
a．2ib．2i-1c．2i+2d．2i+1
20．設一棵哈夫曼樹共有n個葉結點，則該樹有（ ）個非葉結點。
a．n-1b．nc．n+1d．2n
21．設一棵有n個結點採用鏈式儲存的二叉樹，則該樹共有（ ）個指標域為空。
a．2nb．n+1 c．2n+1d．2n+2
22．在乙個無向圖中，所有頂點的度數之和等於邊數的（ ）倍。
a．3b．2.5c．1.5d．2
23．已知如圖1所示的乙個圖，若從頂點a出發，按廣度優先搜尋法進行遍歷，則可能得到的一種頂點序列為（ ）。
a．abcedfb．aebcfd c．abcefd d．acfdeb
圖124．已知如圖1所示的乙個圖，若從頂點v1出發，按廣度優先進行遍歷，則可能得到的一種頂點序列為（ ）。
a．v1v2v3v6v7v4v5v8 b．v1v2v3v4v5v8v6v7
c．v1v2v3v4v5v6v7v8 d．v1v2v3v4v8v5v6v7
圖125．在有序表中，用折半查詢值86時，經（ ）次比較後查詢成功。
a．3 b．4 c．6d．8
26．在有序表中，用折半查詢法查詢值80時，經（ ）次比較後查詢成功。
a．2b．3 c．4 d．5
27．有乙個長度為10的有序表，按折半查詢對該錶進行查詢，在等概率情況下查詢成功的平均比較次數為（ ）。
a．31/10 b．29/10c．26/10 d．29/9
28．排序演算法中，從未排序序列中依次取出元素與已排序序列（初始為空）中的元素進行比較（要求比較次數盡量少），然後將其放入已排序序列的正確位置的方法是（ ）。
a．冒泡b．直接插入 c．選擇排序 d．折半插入
29．一組記錄的關鍵字序列為（37，70，47，29，31，85），利用快速排序，以第乙個關鍵字為分割元素，經過一次劃分後結果為（ ）。
a．29，31，37，47，70，85 b．31，29，37，47，70，85
c．31，29，37，70，47，85 d．31，29，37，85，47，70
30．排序方法中，從尚未排序序列中挑選元素，並將其依次放入已排序序列（初始為空）的一端的方法，稱為（ ）排序。
a．歸併 b．插入 c．選擇 d．快速
二、填空題（每小題2分）
1．把資料儲存到計算機中,並具體體現資料之間的稱為物理（儲存）結構。
2．結構中的資料元素存在多對多的關係稱為結構。
3．結構中的資料元素存在一對一的關係稱為________結構。
4．要求在n個資料元素中找其中值最大的元素，設基本操作為元素間的比較。則比較的次數和演算法的時間複雜度分別為________和 o(n)。
5．在雙向鍊錶中，每個結點有兩個指標域，乙個指向結點的直接後繼，另乙個指向
6．設有乙個頭指標為head的單向迴圈鍊錶，p指向鍊錶中的結點，若p->next則p所指結點為尾結點。
7．設有乙個頭指標為head的單向鍊錶，p指向表中某乙個結點，且有p->next= =null,通過操作________，就可使該單向鍊錶構造成單向迴圈鍊錶。
8．向乙個棧頂指標為h的鏈棧中插入乙個s所指結點時，可執行和h=s;。
9．從乙個棧頂指標為h的鏈棧中刪除乙個結點時，用x儲存被刪結點的值，可執行
和h=h->next;。(結點的指標域為next)
10．在乙個鏈隊中，設f和r分別為隊頭和隊尾指標，則插入s所指結點的操作為________和r=s; (結點的指標域為next)
11．兩個串相等的充分必要條件是
12．設有n階對稱矩陣a，用陣列s進行壓縮儲存，當i13．對二叉樹的遍歷可分為和層次四種不同的遍歷次序。
資料結構 本 期末綜合練習
2012年6月 期末綜合練習一 一 單項選擇題 1 深度為5的完全二叉樹共有20個結點，則第5層上有 個結點 根所在結點為第一層 a 3b 8c 5d 6 2 同一種邏輯結構 a 只能有唯一的儲存結構 b 可以有不同的儲存結構 c 只能表示某一種資料元素之間的關係 d 以上三種說法均不正確 3 已知...
資料結構 本 期末綜合練習
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.資料結構 指的是資料之間的相互關係，即資料的組織形式。一般包括三個方面的內容 資料的邏輯結構 儲存結構和資料...