一、填空題
1. **性表的單鏈表儲存結構中，每個結點包含兩個域，乙個叫
域，另乙個叫域 。
2. 向棧中壓入元素的操作是
1. 設字串s1="abcdefg",s2="pqrst"，則運算s=concat (sub(s1,2,len(s2)),sub(s1,len(s2),2))後的串值為
3. 對於乙個長度為n的順序儲存的線性表，在表頭插入元素的時間複雜度為在表尾插入元素的時間複雜度為
4. 深度為k的完全二叉樹至少有個結點，至多有個結點。
5. 在乙個稀疏矩陣中，每個非零元素所對應的三元組包括該元素的三項。
6. 佇列的插入操作在進行，棧的刪除操作進行。
7. 棧的特點是佇列的特點是
8. 資料的儲存結構被分為順序結構和四種。
9. 如果結點a有3個兄弟，而且b是a的雙親，則b的度是
10. n個頂點的連通圖至少有條邊。
11. 折半查詢的儲存結構僅限於
12. 將f=1+1/2+1/3+……+1/n轉化成遞迴函式，其遞迴出口是遞迴體是
13. 在一棵二叉樹，第4層上的結點數最多為個。
14. 採用順序查詢方法查詢長度為n的線性表時，每個元素的平均查詢長度為
二、單選題（把答案填在下表）
1. 在乙個長度為n的順序儲存的線性表中，在第i個元素（1≤i≤n+1）的位置插入乙個新元素時，需要從後向前依次後移個元素。
a、n-i b、n-i+1 c、n-i-1 d、i
2. 將上三角矩陣a[n*n]壓縮儲存於一維陣列b[1]到b[n*(n-1)/2]中，則a[i,j](i<=j)儲存在中。
a、b[i+j] b、b[(i-1)*n+j] c、b[i*n+j-1] d、沒有儲存
3. 對乙個具有t個非零元素的m*n大小的稀疏矩陣採用順序儲存，求其轉置矩陣的普通轉置演算法的時間複雜度為 。
a、o(m) b、o(n) c、o(n+t) d、o(n*t)
4. 若讓元素1,2,3依次進棧，則出棧次序不可能出現第種情況。
a、3，2，1 b、2，1，3 c、3，1，2 d、1，3，2
5. 設高度為h的二叉樹上只有度為0和2的結點，則此類二叉樹中所包含的結點數至少為 。
a、2hb、2h-1 c、2h+1d、h+1
6. 假定乙個順序佇列的隊首和隊尾指標分別為f和r，則判斷隊空的條件為 。
a、f+1==r b、r+1==f c、f==0 d、f==r
7. 對乙個滿二叉樹，m個樹葉，n個結點，深度為h，則有 。
a、n=h+mb、h+m=2n
c、m=h-1d、n=2h-1
8. 採用鄰接表儲存的圖的深度優先遍歷演算法類似於二叉樹的 。
a、先序遍歷b、中序遍歷
c、後序遍歷d、按層遍歷
9. 在所有排序方法中，關鍵字比較的次數與記錄的初始排列次序無關的是 。
a、希爾排序b、氣泡排序
c、插入排序d、選擇排序
10. 具有6個頂點的無向圖至少應有條邊才能確保是乙個連通圖。
a、5b、6c、7d、8
11. n個節點的完全二叉樹，編號為i的節點是葉子結點的條件是 。
a、ind、2*i>n
12. 向乙個有127個元素的順序表中插入乙個新元素並保持原來順序不變，平均要移動個元素。
a、64b、63.5c、63d、7
13. 在乙個單鏈表hl中，若要在指標q所指結點的後面插入乙個由指標p所指向的結點，則執行 。
a、q->next=p->next; p->next=q;
b、p->next=q->next; q=p;
c、q->next=p->next; p->next=q;;
d、p->next=q->next; q->nxet=p;
三、簡答題
1、已知稀疏矩陣如下圖所示，要求畫出其轉置矩陣的三元順序表。
2、已知字元：c1，c2，c3，c4，c5，c6的權分別為：17，5，16，4，8，11，請構造相應的赫夫曼樹(畫出必要過程)，並給出相應字元的赫夫曼編碼。
3、已知序列，請給出採用氣泡排序法對該序列作公升序排序時的每一趟的結果。
4、給定帶權無向圖g1如下所示，要求：畫出其鄰接矩陣的儲存結構，並按普里姆演算法構造其最小生成樹，要畫出構造過程。
四、演算法設計題
2、已知無序的順序表（qlist[n]）， 建立一相應帶頭結點的有序單鏈
表（head）。鍊錶結點資料型別:linklist
例如：由變為
資料結構練習題
習題3 棧和佇列 一 基本內容 棧和佇列的結構特點 在兩種儲存結構上如何實現棧和佇列的基本操作以及棧和佇列在程式設計中的應用。二 學習要點 1.掌握棧和佇列的特點。2 熟練掌握棧型別的兩種實現方法，即兩種儲存結構表示時的基本操作實現演算法，特別應注意棧滿和棧空的條件以及它們的描述方法。3 熟練掌握迴...
資料結構練習題
習題5 陣列和廣義表 一 基本內容 陣列定義及表示方式 特殊矩陣和稀疏矩陣的壓縮儲存方法及運算的實現 廣義表的邏輯結構和儲存結構。二 學習要點 1.了解陣列的兩種儲存表示方法，並掌握陣列在以行為主的儲存結構中的位址計算方法。2 掌握對特殊矩陣進行壓縮儲存時的下標變換公式。3 了解稀疏矩陣的兩種壓縮儲...
資料結構練習題
a.n b.n 1 2 c.n 1 9 對於乙個具有n個頂點和e條邊的無向圖，若採用鄰接表表示，則表頭向量的大小為 所有鄰接表中的接點總數是 b.n 1 c.n 1 d.n e a.e 2 b.e d.n e 10 已知乙個圖如圖7.1所示，若從頂點a出發按深度搜尋法進行遍歷，則可能得到的一種頂點序...