數(shù)據(jù)結(jié)構(gòu)與算法復習題.doc

數(shù)據(jù)結(jié)構(gòu)與算法復習題一、 寫出以下各詞語對應(yīng)的中文（英） sequential storge structure 順序存儲結(jié)構(gòu) Abstract Data Type (ADT) 抽象數(shù)據(jù)類型 二叉排序樹 Binary sort tree queue 隊列 storge structure 存儲結(jié)構(gòu) time complexity 時間復雜度 線性表 Linear List 二叉樹 Binary Tree Depth_First Search 深度優(yōu)先搜索 singly linked lists 單鏈表 二、 單項選擇題 1、數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中數(shù)據(jù)元素的 、數(shù)據(jù)信息在計算機中的存儲結(jié)構(gòu)以及一組相關(guān)的運算等的課程。 A: 操作對象: 計算方法: 邏輯結(jié)構(gòu): 數(shù)據(jù)映象 2、某線性表最常用的運算是插入和刪除,插入運算是指在表尾插入一個新元素,刪除運算是指刪除表頭第一個元素,那么采用 存儲方式最節(jié)省運算時間.。A: 僅有頭指針的單向循環(huán)鏈表B: 僅有尾指針的單向循環(huán)鏈表C: 單向鏈表D:雙向鏈表3、一個棧的入棧序列是a，b，c，d，e，則棧的不可能的輸出序列是_。 A: abcde B: decba C: edcba D: dceab 4、將一個遞歸算法改為對應(yīng)的非遞歸算法時，通常需要使用_。 A: 棧 B: 隊列 C: 循環(huán)隊列 D: 優(yōu)先隊列 5、關(guān)于空串，下列說法中正確的有_。A: 空串就是空格串 B: 空串的長度可能不為零C: 空串是零個字符的串 D: 空串的長度就是其包含的空格個數(shù)6、二維數(shù)組A中，每個元素的長度為3個字節(jié)，行下標i從0到7，列下標j從0到9，從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按行存放時，數(shù)組元素A74的起始地址為 。A: SA+141 B: SA+144 C: SA+222 D: SA+2257、某二叉樹的前序和后序序列正好相反，則該二叉樹一定是 的二叉樹。A: 空或只有一個結(jié)點 B: 高度等于其結(jié)點數(shù) C: 任一結(jié)點無左孩子 D: 任一結(jié)點無右孩子8、下述棵二叉樹中，是完全二叉樹的是： 。: : : :9、深度為5的二叉樹至多有_個結(jié)點。A: 16 B: 32 C: 31 D: 1010、在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的 倍。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: 以數(shù)組方式存儲且結(jié)點按關(guān)鍵碼有序排列 B: 以數(shù)組方式存儲 C: 以鏈接方式存儲且結(jié)點按關(guān)鍵碼有序排列 D: 以鏈接方式存儲13、下述幾種排序方法中，要求內(nèi)存量最大的是_。A: 插入排序 B: 選擇排序 C: 快速排序 D: 歸并排序14、采用二分查找方法查找長度為n的線性表時，每個元素的平均查找長度為_。A: O（n2） B: O(nlog2n) C: O(n) D: O(log2n)15、在一個單鏈表中，若刪除p所指結(jié)點的后續(xù)結(jié)點，則執(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)中，每個結(jié)點_。A:無直接前趨 B:只有一個直接前驅(qū)和后繼C:只有一個直接前趨和個數(shù)不受限制的直接后繼D:有個數(shù)不受限制的直接前趨和后繼17、設(shè)稀疏矩陣按列優(yōu)先順序存儲于三元組表，則結(jié)點(3，2，-5)是三元組表中的第_項。A:2 B:3 C:4 D:118、對于任何一棵二叉樹T，如果其終端結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為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: 計算機內(nèi)的數(shù)值運算依靠方程式，而非數(shù)值運算（如表、樹等）則要依靠數(shù)據(jù)結(jié)構(gòu) B：數(shù)據(jù)結(jié)構(gòu)是研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及它們之間的關(guān)系和操作等的學科 C: 數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的物理結(jié)構(gòu)有時可以不加區(qū)分 D：同樣的數(shù)據(jù)對象，用不同的數(shù)據(jù)結(jié)構(gòu)來表示，運算效率可能有明顯的差異 21、計算機算法指的是，它必須具備輸入、輸出和_。 A: 計算方法 B: 排序方法 C: 解決問題的有限運算步驟 D: 程序設(shè)計方法22、數(shù)組與一般線性表的區(qū)別主要在_。A: 存儲方面 B: 元素類型一致C: 邏輯結(jié)構(gòu)方面 D: 不能進行插入、刪除運算23、在解決計算機主機與打印機之間速度不匹配問題時通常設(shè)置一個打印緩沖區(qū)，該緩沖區(qū)應(yīng)該是一個_結(jié)構(gòu)。 A: 棧 B: 隊列 C: 數(shù)組 D: 樹24、在所有排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是_。A: 希爾排序 B: 起泡排序 C: 插入排序 D: 選擇排序25、二叉排序樹中，鍵值最小的結(jié)點_。A: 左指針一定為空 B: 右指針一定為空C: 左、右指針均為空 D: 左、右指針均不為空三、 在一個C語言程序中，有結(jié)構(gòu)類型STUDENT的定義和結(jié)構(gòu)數(shù)組allstudents的聲明如下：struct STUDENT char name10; int number;STUDENT allstudents1050; allstudents是一個二維數(shù)組，它的每個元素都是包含name和number的結(jié)構(gòu)類型。已知在C語言中，二維數(shù)組使用以行序為主序的存儲結(jié)構(gòu)，char類型占用1字節(jié)，int類型占用4字節(jié)。假定allstudents在內(nèi)存中的起始存儲位置是2000，請寫出計算allstudentsij的存儲位置的算式，并計算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)的概率分別為27，43，19，3，12，要求：1、 構(gòu)造一棵Huffman樹（左結(jié)點的權(quán)不大于右結(jié)點的權(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)造最小生成樹過程中順序選出的各條邊 ，并畫出最小生成樹 。始頂點號終頂點號權(quán)值 答:始頂點號終頂點號權(quán)值0313545223151432、圖G(V，E)，其中V=1,2,3,4,5,6，,，請畫出圖G，并寫出其鄰接矩陣和鄰接表表示。答：圖G如下所示，圖G的鄰接矩陣和鄰接表表示分別如圖(b)和(c)所示。對于這類問題，只要掌握了圖的概念和存儲結(jié)構(gòu)就可以做出正確的答案。通常情況下對圖的頂點排列順序和各頂點的鄰接點排列順序并沒有特定要求，因此，在寫出鄰接矩陣和鄰接表表示時，只要按照某種排列順序畫出相應(yīng)的結(jié)構(gòu)圖就可以了。但應(yīng)該注意的是，對于鄰接矩陣表示，如果頂點結(jié)點的順序不同，那么鄰接矩陣就不相同；對于鄰接表表示，如果頂點結(jié)點的順序或者鄰接點的順序不同，那么鄰接表就不相同。0 1 1 1 0 00 0 0 0 1 00 1 0 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ù)二叉樹的已知遍歷，恢復該二叉樹并進行其他遍歷操作 已知一棵二叉樹的先序遍歷為：acbrsedfmlk，中序遍歷為：rbsceafdlkm ，試畫出該二叉樹 ，并寫出它的后序遍歷 。答:(1) 畫出該二叉樹:(2)后序遍歷:rsbecfklmda八、 構(gòu)造哈希表并求其成功查找時的ASL 設(shè)有一組關(guān)鍵字（19，01，23，14，55，20，84，27，68，11，10，77），采用哈希函數(shù)：H（key）= key % 13，若用開放定址法的線性探測法解決沖突，試在013的哈希地址空間中對該關(guān)鍵字序列構(gòu)造哈希表并求其成功查找時的ASL。1、填寫對應(yīng)的哈希表 哈希地址012345678910111213關(guān)鍵字 比較次數(shù) 2、求其成功查找時的ASL 答：依題意，m=13，線性探測法的下一個地址計算公式為：di = H（key）di+1 = （di+1）% m ；i=1，2，1、哈希表如下：（3分）哈希地址012345678910111213關(guān)鍵字11455276819208423111077比較次數(shù)1214311311322、共有12個關(guān)鍵字，等概率查找，則成功查找時（2分）ASL=（1+2+1+4+3+1+1+3+1+1+3+2）/12=23/121.9九、建立二叉排序樹并作插入和刪除操作 已知一組關(guān)鍵字為28,9,32,40,34,22,25,33,7,15,要求：1、建立一棵二叉排序樹 2、畫出插入結(jié)點20后的二叉排序樹 3、畫出再刪除結(jié)點32后的二叉排序樹 答： 建二叉排序樹 插入結(jié)點20后的二叉排序樹 或 刪除結(jié)點32后的二叉排序樹十、排序算法操作 1、用希爾排序法，對8個數(shù)值（4，19，28，29，11，21，74，87）進行排序，增量序列為: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、用快速排序法，對8個數(shù)值（46，6，98，19，32，40，60，40）進行排序，并輸出前2趟的結(jié)果。 答：第1趟排序結(jié)果： 40，6，40，19，32，46，60，98第2趟排序結(jié)果： 32，6，40，19，40，46，60，983、用冒泡排序法，對 10個數(shù)值（46,74,53,14,26,38,86,65, 27,34）進行排序，并輸出前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)為二叉鏈表，結(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; Inorder(T- rchild); 對于上圖所示的二叉樹：（1）畫出執(zhí)行上述算法后所建立的結(jié)構(gòu) （2）說明該算法的功能 答：（1）執(zhí)行上述算法后建立的結(jié)構(gòu)為如下所示的鏈表 （2）該算法的功能是用中序遍歷遞歸算法對二叉樹進行遍歷，將二叉樹中葉結(jié)點數(shù)據(jù)域的值作為單鏈表結(jié)點的值，并用頭插法建立一個以Leafhead為頭指針的逆序單鏈表（即按二叉樹中葉結(jié)點數(shù)據(jù)從右至左鏈接成一個鏈表。2、下列算法以二叉鏈表為存儲結(jié)構(gòu)，交換二叉樹各結(jié)點的左右子樹。請在有橫線的地方填寫合適的內(nèi)容。 typedef char DataType;typedef struct node DataType data; struct node *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é)點的單鏈表，結(jié)果返回單鏈表的頭指針 typedef char DataType; typedef struct node DataType data; struct node *next; ListNode; typedef ListNo