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

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

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

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

5、歸并排序14、采用二分查找方法查找長度為n的線性表時(shí)，每個(gè)元素的平均查找長度為_。A: O（n2） B: O(nlog2n) C: O(n) D: O(log2n)15、在一個(gè)單鏈表中，若刪除p所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行_。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、非線性結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)_。A:無直接前趨 B:只有一個(gè)直接前驅(qū)和后繼C:只有一個(gè)直接前趨和個(gè)數(shù)不受限制的直接后繼D:有個(gè)數(shù)不受限制的直接前趨和后繼17、設(shè)稀疏矩陣按列優(yōu)先順序存儲于三元組表，則

6、結(jié)點(diǎn)(3，2，-5)是三元組表中的第_項(xiàng)。A:2 B:3 C:4 D:118、對于任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則_。A:n0=n2+1 B:n2=n0+1 C:n0=2n2+1 D:n2=2n0+119、下面程序段的時(shí)間復(fù)雜度是_。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: 計(jì)算機(jī)內(nèi)的數(shù)值運(yùn)算依靠方程式，而非數(shù)值運(yùn)算（如表、樹等）則要依靠數(shù)據(jù)結(jié)構(gòu) B：數(shù)據(jù)結(jié)構(gòu)是研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對象以及它們之間

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

8、序無關(guān)的是_。A: 希爾排序 B: 起泡排序 C: 插入排序 D: 選擇排序25、二叉排序樹中，鍵值最小的結(jié)點(diǎn)_。A: 左指針一定為空 B: 右指針一定為空C: 左、右指針均為空 D: 左、右指針均不為空三、 在一個(gè)C語言程序中，有結(jié)構(gòu)類型STUDENT的定義和結(jié)構(gòu)數(shù)組allstudents的聲明如下：struct STUDENT char name10; int number;STUDENT allstudents1050; allstudents是一個(gè)二維數(shù)組，它的每個(gè)元素都是包含name和number的結(jié)構(gòu)類型。已知在C語言中，二維數(shù)組使用以行序?yàn)橹餍虻拇鎯Y(jié)構(gòu)，char類型占用1字節(jié)，

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

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

11、1432、圖G(V，E)，其中V=1,2,3,4,5,6，,，請畫出圖G，并寫出其鄰接矩陣和鄰接表表示。答：圖G如下所示，圖G的鄰接矩陣和鄰接表表示分別如圖(b)和(c)所示。對于這類問題，只要掌握了圖的概念和存儲結(jié)構(gòu)就可以做出正確的答案。通常情況下對圖的頂點(diǎn)排列順序和各頂點(diǎn)的鄰接點(diǎn)排列順序并沒有特定要求，因此，在寫出鄰接矩陣和鄰接表表示時(shí)，只要按照某種排列順序畫出相應(yīng)的結(jié)構(gòu)圖就可以了。但應(yīng)該注意的是，對于鄰接矩陣表示，如果頂點(diǎn)結(jié)點(diǎn)的順序不同，那么鄰接矩陣就不相同；對于鄰接表表示，如果頂點(diǎn)結(jié)點(diǎn)的順序或者鄰接點(diǎn)的順序不同，那么鄰接表就不相同。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)圖 圖及其存儲結(jié)構(gòu)1(a)34256(c)126453223545666七、根據(jù)二叉樹的已知遍歷，恢復(fù)該二叉樹并進(jìn)行其他遍歷操作 已知一棵二叉樹的先序遍歷為：acbrsedfmlk，中序遍歷為：rbsceafdlkm ，試畫出該二叉樹 ，并寫出它的后序遍歷 。答:(1) 畫出該二叉樹:(2)后序遍歷:rsbecfklmda八、 構(gòu)造哈希表并求其成功查找時(shí)的ASL 設(shè)有一組關(guān)鍵字（19，01，23，14，55，20，84，27，68，11，10，77），采用哈希函數(shù)：H（key）= key % 13，若用開放定址

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

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

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

16、，結(jié)合下圖閱讀下列算法。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）畫出執(zhí)行上述算法后所建立的結(jié)構(gòu) （2）說明該算法的功能 答：（1）執(zhí)行上述算法后建立的結(jié)構(gòu)為如下所示的鏈表 （2）該算法的功能是用中序遍歷遞歸算法對二叉樹進(jìn)行遍歷，將二叉樹中葉結(jié)點(diǎn)數(shù)據(jù)域的值作為單鏈表結(jié)點(diǎn)的值，并用頭插法建立一個(gè)以Leafhead為頭指針的逆序單鏈表（即按二叉樹中葉結(jié)點(diǎn)數(shù)據(jù)從右至左鏈接成一個(gè)鏈表。2、下列算法以二叉鏈表為存儲結(jié)構(gòu)，交換二叉樹各結(jié)點(diǎn)的左右子樹。請?jiān)谟袡M線的地方填寫合適的內(nèi)容。 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、寫一算法用頭插法建立無頭結(jié)點(diǎn)的單鏈表，結(jié)果返回單鏈表的頭指針 typedef char DataType; typedef struct node DataType data; struct node *next; ListNode; typedef Li