要求：所有的題目的解答均寫在答題紙上，需寫清楚題目的序號。每張答題紙都要寫上姓名和學號。
1. 資料結構是指 。
a. 一種資料型別
b. 資料的儲存結構
c. 一組性質相同的資料元素的集合
d. 相互之間存在一種或多種特定關係的資料元素的集合
2. 以下演算法的時間複雜度為 。
void fun(int n)
}a. o(nb. o()
c. o(nlog2nd. o(log2n)
3. 在乙個長度為n的有序順序表中刪除其中第乙個元素值為x的元素時，在查詢元素x時採用二分查詢方法，此時刪除演算法的時間複雜度為 。
a. o(nb. o(nlog2n)
c. o(n2d. o()
4. 若乙個棧採用陣列s[0..n-1]存放其元素，初始時棧頂指標為n，則以下元素x進棧的正確操作是 。
5. 設環形佇列中陣列的下標為0～n-1，其隊頭、隊尾指標分別為front和rear（front指向佇列中隊頭元素的前乙個位置，rear指向隊尾元素的位置），則其元素個數為 。
a. rear-frontb. rear-front-1
c. (rear-front)％n+1d. (rear-front+n)％n
6. 若用乙個大小為6的陣列來實現環形佇列，隊頭指標front指向佇列中隊頭元素的前乙個位置，隊尾指標rear指向隊尾元素的位置。若當前rear和front的值分別為0和3，當從佇列中刪除乙個元素，再加入兩個元素後，rear和front的值分別為 。
a. 1和5b. 2和4
c. 4和2d. 5和1
7. 一棵高度為h（h≥1）的完全二叉樹至少有個結點。
a. 2h-1b. 2h
c. 2h+1d. 2h-1+1
8. 設一棵哈夫曼樹中有999個結點，該哈夫曼樹用於對個字元進行編碼。
a. 999b. 499
c. 500d. 501
9. 乙個含有n個頂點的無向連通圖採用鄰接矩陣儲存，則該矩陣一定是 。
a. 對稱矩陣b. 非對稱矩陣
c. 稀疏矩陣d. 稠密矩陣
10. 設無向連通圖有n個頂點e條邊，若滿足 ，則圖中一定有迴路。
a. e≥nb. ec. e=n-1d. 2e≥n
11. 如果從無向圖的任一頂點出發進行一次廣度優先遍歷即可訪問所有頂點，則該圖一定是 。
a.完全圖b.連通圖
c.有迴路d.一棵樹
12. 設有100個元素的有序表，用折半查詢時，不成功查詢時最大的比較次數是 。
a. 25b. 50
c. 10d. 7
13. 從100個元素確定的順序表中查詢其中某個元素（關鍵字為正整數），如果最多隻進行5次元素之間的比較，則採用的查詢方法只可能是 。
a.折半查詢b.順序查詢
c.雜湊查詢d.二叉排序樹查詢
14. 有乙個含有n（n>1000）個元素資料序列，某人採用了一種排序方法對其按關鍵字遞增排序，該排序方法需要關鍵字比較，其平均時間複雜度接近最好的情況，空間複雜度為o(1)，該排序方法可能是 。
a.快速排序b.堆排序
c.二路歸併排序d.都不適合
15. 對乙個線性序列進行排序，該序列採用單鏈表儲存，最好採用排序方法。
a.直接插入排序b.希爾排序
c.快速排序d.都不適合
1. 如果對含有n（n>1）個元素的線性表的運算只有4種：刪除第乙個元素；刪除最後乙個元素；在第乙個元素前面插入新元素；在最後乙個元素的後面插入新元素，則最好使用以下哪種儲存結構，並簡要說明理由。
（1）只有尾結點指標沒有頭結點指標的迴圈單鏈表
（2）只有尾結點指標沒有頭結點指標的非迴圈雙鏈表
（3）只有頭結點指標沒有尾結點指標的迴圈雙鏈表
（4）既有頭結點指標也有尾結點指標的迴圈單鏈表
2. 對於乙個帶權連通無向圖g，可以採用prim演算法構造出從某個頂點v出發的最小生成樹，問該最小生成樹是否一定包含從頂點v到其他所有頂點的最短路徑。如果回答是，請予以證明；如果回答不是，請給出反例。
3. 有一棵二叉排序樹按先序遍歷得到的序列為：(12,5,2,8,6,10,16,15,18,20)。回答以下問題：
（1）畫出該二叉排序樹。
（2）給出該二叉排序樹的中序遍歷序列。
（3）求在等概率下的查詢成功和不成功情況下的平均查詢長度。
1.（15分）假設二叉樹b採用二叉鏈儲存結構，設計乙個演算法void findparent(btnode *b,elemtype x,btnode *&p)求指定值為x的結點的雙親結點p。提示，根結點的雙親為null，若在二叉樹b中未找到值為x的結點，p亦為null。
2. （10分）假設乙個有向圖g採用鄰接表儲存。設計乙個演算法判斷頂點i和頂點j（i≠j）之間是否相互連通，假設這兩個頂點均存在。
3.（15分）有乙個含有n個整數的無序資料序列，所有的資料元素均不相同，採用整數陣列r[0..n-1]儲存，請完成以下任務：
（1）設計乙個盡可能高效的演算法，輸出該序列中第k（1≤k≤n）小的元素，演算法中給出適當的注釋資訊。 提示：利用快速排序的思路。
（2）分析你所設計的求解演算法的平均時間複雜度，並給出求解過程。
「資料結構」考試試題（a）參***
要求：所有的題目的解答均寫在答題紙上，需寫清楚題目的序號。每張答題紙都要寫上姓名和學號。
4. c 5. d
6. b 7. a 8. c 9. a 10. a
11. b 12. d
1. 答：本題答案為（3），因為實現上述4種運算的時間複雜度均為o(1)。
2. 答：不是。如圖1所示的圖g從頂點0出發的最小生成樹如圖2所示，而從頂點0到頂點的2的最短路徑為02，而不是最小生成樹中的012。
圖1 乙個帶權連通無向圖g 圖2 圖g的一棵最小生成樹
3. 答：（1）先序遍歷得到的序列為：
(12,5,2,8,6,10,16,15,18,20)，中序序列是乙個有序序列，所以為：(2,5,6,8,10,12,15,16,18,20)，由先序序列和中序序列可以構造出對應的二叉樹，如圖3所示。4分
（2）中序遍歷序列為：2,5,6,8,10,12,15,16,18,20。4分
（3）asl成功=(1×1+2×2+4×3+3×4)/10=29/10。1分
asl不成功=(5×3+6×4/11=39/11。1分
圖31.（15分）解：演算法如下：
void findparent(btnode *b,elemtype x,btnode *&p)
}else p=null;
}2. （10分）解：演算法如下：
int visited[maxv];
void dfs(algraph *g,int v深度優先遍歷演算法
}bool dfstr**e(algraph *g,int i,int j)
3.（15分）（1）採用快速排序的演算法如下： （12分）
int quickselect(int r,int s,int t,int k) //在r[s..t]序列中找第k小的元素
{ int i=s,j=t;
int tmp;
if (s { tmp=r[s用區段的第1個記錄作為基準
while (i!=j從區段兩端交替向中間掃瞄,直至i=j為止
while (j>i && r[j]>=tmp)
j從右向左掃瞄,找第1個小於tmp的r[j]
r[i]=r[j將r[j]前移到r[i]的位置
while (ii從左向右掃瞄,找第1個大於tmp的r[i]
資料結構試題,模擬考試題
資料結構試題 單選題在資料結構的討論中把資料結構從邏輯上分為 c a 內部結構與外部結構b 靜態結構與動態結構 c 線性結構與非線性結構d 緊湊結構與非緊湊結構。2 採用線性鍊錶表示乙個向量時，要求占用的儲存空間位址 d a 必須是連續的b 部分位址必須是連續的 c 一定是不連續的d 可連續可不連續...
資料結構導論自考試題
全國2008年10月高等教育自學考試 課程 02142 一 單項選擇題 本大題共15小題，每小題2分，共30分 在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其 填寫在題後的括號內。錯選 多選或未選均無分。1.從邏輯上可以把資料結構分為 a.動態結構 靜態結構 b.順序結構 鏈式結構 c....
全國自考試題資料結構試卷
全國2008年1月高等教育自學考試 資料結構試題 課程 02331 一 單項選擇題 本大題共15小題，每小題2分，共30分 在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其 填寫在題後的括號內。錯選 多選或未選均無分。1.邏輯上通常可以將資料結構分為 a.動態結構和靜態結構 b.順序結構和...