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

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