a) 排序是按照元素的值或某個域的值排列元素，使之成為有序表
b) 線性表的排序不改變表中元素及其各個域的值
c) 插入排序演算法的時間複雜度的數量級是o(n2)
d) 對線性表排序不改變元素的儲存順序
8． 對單鏈表表示法，以下說法錯誤的是〖 d 〗。
a) 資料域用於儲存線性表的乙個資料元素
b) 指標域用於存放乙個指向本結點所含資料元素的直接後繼所在的節點的指標
c) 所有資料通過指標的鏈結而組織成單鏈表
d) null稱為空指標，他不指向任何節點只起標誌作用
9． 以下有關雙鏈表的敘述中，說法錯誤的是〖 b 〗。
a) 從表中任一結點出發都能通過前後移動操作掃瞄整個鍊錶
b) 只有從頭結點開始才能掃瞄鍊錶中全部結點
c) 雙鏈表的特點是查詢結點的前趨和後繼都很容易
d) 某一結點的儲存位置同時存放在其前趨結點的後繼指標域中，及後繼結點的前趨指標域中
10．在有關稀疏矩陣的儲存結構的敘述中，以下錯誤的是〖 c 〗。
a) 稀疏矩陣的順序儲存是對其相應的三元組線性表進行順序儲存
b) 稀疏矩陣的鏈結儲存是對其相應的三元組線性表進行鏈結儲存
c) 稀疏矩陣的儲存是對其非零元素構成的線形表進行順序儲存
d) 稀疏矩陣的十字鏈結儲存是對其相應的三元組線性表進行十字鏈結儲存
11．對於棧的入棧和出棧操作，假定同一輸入序列中不含相同的元素，以下敘述中正確的是〖 a 〗。
a) 不同的入棧和出棧組合，將得到不同的輸出序列
b) 輸出序列的排列順序可以是輸入序列中元素的全排列
c) 輸出序列的排列順序只能是與輸入序列完全相反的
d) 輸出序列的排列順序只能是與輸入序列完全相同的
12．已知一算術表示式的中綴形式為a+b*c-d/e，字尾形式為a b c * + d e / -，其字首形式為
a) – a + b * c / d eb) – a + b * c d / e
c) - + * a b c / d ed) - + a * b c / d e
13．乙個輸入序列abcd經過乙個棧到達輸出序列，則下面錯誤的輸出序列的是〖 c 〗。
a) bcad b) cbda c) dabc d) acbd
14．已知佇列q的輸入序列為0,1,2,3,4,5,6，執行插入和刪除元素的順序是：qinsert(q,0)，qinsert(q,1)，qinsert(q,2)，qdelete(q)，qinsert(q,4)，qdelete(q)，qinsert(q,5)，qdelete(q)，qinsert(q,6)，此時隊頭和隊尾指標分別指向〖 d 〗。
a) 3，4 b) 4，5 c) 3，6 d) 2，6
15．在一棵具有n個結點的完全二叉樹中，樹枝結點的最大編號為〖 c 〗。
a) (n+1)/2 b) (n-1)/2 c) [n/2」 d] n/2
16．在一棵哈夫曼樹中，帶權葉子結點的權值分別為4,8,6,7,4，其中離根結點最近的結點的權值是〖 a 〗。
a) 8b) 7 c) 6 d) 5
17．在一棵具有n個結點的二叉樹第i層上，最多具有〖 b 〗。
a) 2 i個結點 b) 2 i-1個結點 c) 2 i-1個結點 d. 2 n個結點
18．某二叉樹的前序序列和後序序列正好相反，則該二叉樹一定是〖 a 〗。
a) 空或只有乙個結點的二叉樹
b) 任意結點無左子樹的二叉樹
c) 高度等於其結點數的二叉樹
d) 任意結點無右子樹的二叉樹
19．對給出的一組關鍵字。若按關鍵字非遞減排序，第一趟排序結果為，則採用的排序演算法是〖 d 〗。
a) 快速排序 b) 二路歸併排序 c) 簡單選擇排序 d) 希爾排序
20．一組記錄的關鍵字為，利用快速排序法並以第乙個記錄為基準得到的第一趟劃分結果是〖 c 〗。
a) 40，42，45，55，80，85b) 42，40，45，80，55，85
c) 42，40，45，55，80，85d) 42，40，45，85，55，80
二．填空題
1．在關係r=中，其中除葉結點外，每乙個結點都有後繼結點。
2．資料的儲存結構，即資料在計算機中的儲存方式通常有：順序索引、雜湊等多種形式。
3． 求單鏈表長度的時間複雜性的數量級為
4． **性表的順序儲存中，元素之間的邏輯關係是通過決定的。
5． 順序儲存結構屬於鏈式結構屬於動態結構。
6． 在乙個廣義表中，其資料元素有和子表之分。
7． 用迴圈鍊錶表示的佇列長度為n，則入隊的時間複雜度是
8． 向棧中插入乙個元素時，首先應判斷棧是否
9． 中綴表示式轉換成字尾表示式的規則是：把每個運算子都移到它的兩個的後面，並刪除所有括號。
10．一棵有n個結點的滿二叉樹有個度為1的結點。
11．某二叉樹的後序遍歷的結點順序是c,d,b,g,f,e,a，則該二叉樹的根結點是
12．一棵二叉樹的深度等於左子樹和右子樹中的加1。
13．一棵具有n個結點的二叉樹，若有m個葉子結點，則該二叉樹上度為1的結點有個。
14．對於一棵完全二叉樹，設乙個結點的編號為i，若它的左孩子結點存在，則其結點的編號為
15．具有n個結點的完全二叉樹若按層次從上到下、從左到右對其編號（根結點為1），則編號最小的葉子結點序號是
16．哈夫曼樹的帶權路徑長度的樹，通常權值較大的結點離根最近。
17．乙個無序序列可以通過構造一棵樹而變成乙個有序序列，構造樹的過程就是對無序序列進行排序的過程。
18．在一棵有n個結點的非平衡二叉樹中進行查詢，平均時間複雜度的上限（即最壞情況平均時間複雜度）為
19．在二叉排序樹插入新結點時，不必移動其它結點，僅需使樹葉結點的指標由指向新結點即可。
20．二分查詢的儲存結構僅限於的順序儲存結構。
三． 名詞解釋題
1． 資料元素
2． 表頭結點
3． 中綴表示式
4． 二叉樹的線索化
5． 連通圖
四． 簡答題
1． 用文字給出遍歷乙個單鏈表的演算法描述。
2． 簡述佇列的結構及操作。
3． 畫出乙個具有16個結點的完全二叉樹
4． 已知乙個字尾算術表示式為： 25 x a a b + * b寫出對應的中綴表示式。
5． 索引查詢是**性表的索引儲存結構的基礎上進行的，請說明索引儲存的基本思想。
五． 完成填空題
1. 索引項的型別定義：
struct indexitem
;順序儲存的索引表的型別定義：
typedef indexitem indexlist[ilmsize];
陣列的型別定義：
typedef elemtype manlist[maxsize];
分塊查詢的演算法如下：
int block(manlist a, indexlist b, int m, keytype k)
2． 雜湊表的型別定義如下：
typedef elemtype hashlist1[hashmaxsize];
採用開放定址法，向雜湊表插入乙個元素的演算法如下：
int insert( hashlist1 ht, int m, elemtype item)
item;
}3． 求解迷宮演算法的程式如下：
#include<>
const m=6,n=8;
int maze[m+2][n+2];
int mark[m+2][n+2];
int move[4][2]=,,,};
資料結構 試題
西南科技大學網路教育學院重修補考試題單 課程名稱 資料結構專業班級命題教師 孫敏 學生姓名學號成績 考試時間月日第1頁共4 頁 一.填空題 每空2分,共20分 1.資料元素是 的基本單位 2.資料結構被形式的定義為 d,s 其中d是 的有限集合,s是d上 的有限集合 3.計算機演算法指的是 它的五個...
資料結構部分試題
1 資料的邏輯結構包括四種型別。2 在棧中，訪問資料遵循的原則是 3 二分查詢法，表中元素必須按存放 4 雜湊表一般按儲存方式構造的儲存結構 5 圖有和三種結構 6 評價演算法優劣的主要標準是和 7 在佇列結構中，允許插入的一端成為允許刪除的一端稱為8 順序表相對於鍊錶的優點有和 9 解決佇列假溢位...
資料結構基礎試題
資料結構試卷 a卷 考試時間 分鐘閉卷 班級學號姓名成績 一 單項選擇 每空2分，共30分 1.資料結構是一門研究非數值計算的程式設計問題中,資料元素的 資料資訊在計算機中的 以及一組相關的運算等的課程。a 操作物件 計算方法 邏輯結構 資料映象 a 儲存結構 關係運算演算法 2.線性表的邏輯順序與...