1、 數據結構與算法復習題一、 寫出以下各詞語對應的中文（英） sequential storge structure 順序存儲結構 Abstract Data Type (ADT) 抽象數據類型 二叉排序樹 Binary sort tree queue 隊列 storge structure 存儲結構 time complexity 時間復雜度 線性表 Linear List 二叉樹 Binary Tree Depth_First Search 深度優先搜索 singly linked lists 單鏈表 二、 單項選擇題 1、數據結構是一門研究非數值計算的程序設計問題中數據元素的 、數據信息在

2、計算機中的存儲結構以及一組相關的運算等的課程。 A: 操作對象: 計算方法: 邏輯結構: 數據映象 2、某線性表最常用的運算是插入和刪除,插入運算是指在表尾插入一個新元素,刪除運算是指刪除表頭第一個元素,那么采用 存儲方式最節省運算時間.。A: 僅有頭指針的單向循環鏈表B: 僅有尾指針的單向循環鏈表C: 單向鏈表D:雙向鏈表3、一個棧的入棧序列是a，b，c，d，e，則棧的不可能的輸出序列是_。 A: abcde B: decba C: edcba D: dceab 4、將一個遞歸算法改為對應的非遞歸算法時，通常需要使用_。 A: 棧 B: 隊列 C: 循環隊列 D: 優先隊列 5、關于空串，下

3、列說法中正確的有_。A: 空串就是空格串 B: 空串的長度可能不為零C: 空串是零個字符的串 D: 空串的長度就是其包含的空格個數6、二維數組A中，每個元素的長度為3個字節，行下標i從0到7，列下標j從0到9，從首地址SA開始連續存放在存儲器內，該數組按行存放時，數組元素A74的起始地址為 。A: SA+141 B: SA+144 C: SA+222 D: SA+2257、某二叉樹的前序和后序序列正好相反，則該二叉樹一定是 的二叉樹。A: 空或只有一個結點 B: 高度等于其結點數 C: 任一結點無左孩子 D: 任一結點無右孩子8、下述棵二叉樹中，是完全二叉樹的是： 。: : : :9、深度為5

4、的二叉樹至多有_個結點。A: 16 B: 32 C: 31 D: 1010、在一個無向圖中，所有頂點的度數之和等于所有邊數的 倍。A: 1/2 B: 1 C: 2 D: 4 11、采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為_.。A: (n+1)/2 B: n/2 C: (n-1)/2 D: n 12、對線性表進行折半搜索時，要求線性表必須_。 A: 以數組方式存儲且結點按關鍵碼有序排列 B: 以數組方式存儲 C: 以鏈接方式存儲且結點按關鍵碼有序排列 D: 以鏈接方式存儲13、下述幾種排序方法中，要求內存量最大的是_。A: 插入排序 B: 選擇排序 C: 快速排序 D:

5、歸并排序14、采用二分查找方法查找長度為n的線性表時，每個元素的平均查找長度為_。A: O（n2） B: O(nlog2n) C: O(n) D: O(log2n)15、在一個單鏈表中，若刪除p所指結點的后續結點，則執行_。A: p=p-next;p-next=p-next-next; B: p-next=p-next-next; C: p-next=p-next; D: p=p-next-next16、非線性結構中，每個結點_。A:無直接前趨 B:只有一個直接前驅和后繼C:只有一個直接前趨和個數不受限制的直接后繼D:有個數不受限制的直接前趨和后繼17、設稀疏矩陣按列優先順序存儲于三元組表，則

6、結點(3，2，-5)是三元組表中的第_項。A:2 B:3 C:4 D:118、對于任何一棵二叉樹T，如果其終端結點數為n0，度為2的結點數為n2，則_。A:n0=n2+1 B:n2=n0+1 C:n0=2n2+1 D:n2=2n0+119、下面程序段的時間復雜度是_。s=0；for(i=0；in；i+) for(j=0；jn；j+) s+=Bij；sum=s；A:O(1) B:O(n) C:(n2) D:O(n3)20、以下闡述不正確的是_。 A: 計算機內的數值運算依靠方程式，而非數值運算（如表、樹等）則要依靠數據結構 B：數據結構是研究非數值計算的程序設計問題中計算機的操作對象以及它們之間

7、的關系和操作等的學科 C: 數據的邏輯結構和數據的物理結構有時可以不加區分 D：同樣的數據對象，用不同的數據結構來表示，運算效率可能有明顯的差異 21、計算機算法指的是，它必須具備輸入、輸出和_。 A: 計算方法 B: 排序方法 C: 解決問題的有限運算步驟 D: 程序設計方法22、數組與一般線性表的區別主要在_。A: 存儲方面 B: 元素類型一致C: 邏輯結構方面 D: 不能進行插入、刪除運算23、在解決計算機主機與打印機之間速度不匹配問題時通常設置一個打印緩沖區，該緩沖區應該是一個_結構。 A: 棧 B: 隊列 C: 數組 D: 樹24、在所有排序方法中，關鍵字比較的次數與記錄的初始排列次

8、序無關的是_。A: 希爾排序 B: 起泡排序 C: 插入排序 D: 選擇排序25、二叉排序樹中，鍵值最小的結點_。A: 左指針一定為空 B: 右指針一定為空C: 左、右指針均為空 D: 左、右指針均不為空三、 在一個C語言程序中，有結構類型STUDENT的定義和結構數組allstudents的聲明如下：struct STUDENT char name10; int number;STUDENT allstudents1050; allstudents是一個二維數組，它的每個元素都是包含name和number的結構類型。已知在C語言中，二維數組使用以行序為主序的存儲結構，char類型占用1字節，

9、int類型占用4字節。假定allstudents在內存中的起始存儲位置是2000，請寫出計算allstudentsij的存儲位置的算式，并計算allstudents53的存儲位置。答: (1) allstudentsij的存儲位置=2000+(i*50+j)*14 (2) allstudents53的存儲位置=2000(5*50+3)*14=5542四、寫出下列程序段的輸出結果（棧的元素類型SelemType為char） 輸出結果是：五、 構造Huffman樹，并求出帶權路徑的長度及給出Huffman編碼假設用于通信的電文由字符集A，B，C，D，E中的字母構成，這些字母在電文中出現的概率分別為

10、27，43，19，3，12，要求：1、 構造一棵Huffman樹（左結點的權不大于右結點的權） 2、 求出帶權路徑的長度（2分）3、 給出Huffman編碼（左分支為0，右分支為1） 答： 1、對應的Huffman樹 2、帶權路徑的長度 （27*2+43*1+19*3+3*4+12*4）=2143、Huffman編碼字符ABCDEHuffman編碼10011111001101六、 圖的應用1、應用Prim（普里姆）算法求解下列連通圖的最小生成樹 要求按如下格式給出在構造最小生成樹過程中順序選出的各條邊 ，并畫出最小生成樹 。始頂點號終頂點號權值 答:始頂點號終頂點號權值031354522315

11、1432、圖G(V，E)，其中V=1,2,3,4,5,6，,，請畫出圖G，并寫出其鄰接矩陣和鄰接表表示。答：圖G如下所示，圖G的鄰接矩陣和鄰接表表示分別如圖(b)和(c)所示。對于這類問題，只要掌握了圖的概念和存儲結構就可以做出正確的答案。通常情況下對圖的頂點排列順序和各頂點的鄰接點排列順序并沒有特定要求，因此，在寫出鄰接矩陣和鄰接表表示時，只要按照某種排列順序畫出相應的結構圖就可以了。但應該注意的是，對于鄰接矩陣表示，如果頂點結點的順序不同，那么鄰接矩陣就不相同；對于鄰接表表示，如果頂點結點的順序或者鄰接點的順序不同，那么鄰接表就不相同。0 1 1 1 0 00 0 0 0 1 00 1 0

12、 0 1 10 0 0 0 0 10 0 0 0 0 10 0 0 0 0 0(b)圖 圖及其存儲結構1(a)34256(c)126453223545666七、根據二叉樹的已知遍歷，恢復該二叉樹并進行其他遍歷操作 已知一棵二叉樹的先序遍歷為：acbrsedfmlk，中序遍歷為：rbsceafdlkm ，試畫出該二叉樹 ，并寫出它的后序遍歷 。答:(1) 畫出該二叉樹:(2)后序遍歷:rsbecfklmda八、 構造哈希表并求其成功查找時的ASL 設有一組關鍵字（19，01，23，14，55，20，84，27，68，11，10，77），采用哈希函數：H（key）= key % 13，若用開放定址

13、法的線性探測法解決沖突，試在013的哈希地址空間中對該關鍵字序列構造哈希表并求其成功查找時的ASL。1、填寫對應的哈希表 哈希地址012345678910111213關鍵字 比較次數 2、求其成功查找時的ASL 答：依題意，m=13，線性探測法的下一個地址計算公式為：di = H（key）di+1 = （di+1）% m ；i=1，2，1、哈希表如下：（3分）哈希地址012345678910111213關鍵字11455276819208423111077比較次數1214311311322、共有12個關鍵字，等概率查找，則成功查找時（2分）ASL=（1+2+1+4+3+1+1+3+1+1+3+2

14、）/12=23/121.9九、建立二叉排序樹并作插入和刪除操作 已知一組關鍵字為28,9,32,40,34,22,25,33,7,15,要求：1、建立一棵二叉排序樹 2、畫出插入結點20后的二叉排序樹 3、畫出再刪除結點32后的二叉排序樹 答： 建二叉排序樹 插入結點20后的二叉排序樹 或 刪除結點32后的二叉排序樹十、排序算法操作 1、用希爾排序法，對8個數值（4，19，28，29，11，21，74，87）進行排序，增量序列為:5、3、1，并輸出前2趟的結果。 答：第1趟排序結果： 4，19，28，29，11，21，74，87第2趟排序結果： 4，11，21，29，19，28，74，872、

15、用快速排序法，對8個數值（46，6，98，19，32，40，60，40）進行排序，并輸出前2趟的結果。 答：第1趟排序結果： 40，6，40，19，32，46，60，98第2趟排序結果： 32，6，40，19，40，46，60，983、用冒泡排序法，對 10個數值（46,74,53,14,26,38,86,65, 27,34）進行排序，并輸出前2趟的結果。 答：第1趟排序結果： 46 , 53, 14,26,38,74,65,27,34,86 第2趟排序結果： 46,14 ,26,38, 53,65,27,34,74,86十一、 閱讀理解算法并回答問題和填充 1、已知二叉樹的存儲結構為二叉鏈表

16、，結合下圖閱讀下列算法。typedef struct node TElemType data; struct node *next;ListNode;typedef ListNode *LinkList;LinkList Leafhead=NULL;void Inorder(BTree T) LinkList s; if(T) Inorder(T-lchild); if(!T-lchild) & (!T-rchild) s=(ListNode*)malloc(sizeof(ListNode); s-data=T-data; s-next=Leafheak; Lerfhead=s; Inorde

17、r(T- rchild); 對于上圖所示的二叉樹：（1）畫出執行上述算法后所建立的結構 （2）說明該算法的功能 答：（1）執行上述算法后建立的結構為如下所示的鏈表 （2）該算法的功能是用中序遍歷遞歸算法對二叉樹進行遍歷，將二叉樹中葉結點數據域的值作為單鏈表結點的值，并用頭插法建立一個以Leafhead為頭指針的逆序單鏈表（即按二叉樹中葉結點數據從右至左鏈接成一個鏈表。2、下列算法以二叉鏈表為存儲結構，交換二叉樹各結點的左右子樹。請在有橫線的地方填寫合適的內容。 typedef char DataType;typedef struct node DataType data; struct nod

18、e *lchild, *rchild; BinTNode; typedef BinTNode *BinTree; BinTree swap(BinTree T) BinTree t,t1,t2; if (T=NULL) t=_(1);else t=(BinTree)malloc(sizeof(BinTNode);t-data=_(2); t1=swap(T-lchild); t2=swap(T-rchild); t-lchild=_(3);t-rchild=_(4); return(_(5); 答：(1) NULL ;(2) T-data;(3) t2 ;(4) t1 ;(5) _ t_; 3、下列算法的功能是什么？void abct(SqList &L) for ( i=2; inext!=NULL ) p=p-next;len+; return (len);2、寫一算法用頭插法建立無頭結點的單鏈表，結果返回單鏈表的頭指針 typedef char DataType; typedef struct node DataType data; struct node *next; ListNode; typedef Li