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

...wd......wd......wd...數(shù)據(jù)構(gòu)造與算法復(fù)習(xí)題寫出以下各詞語對應(yīng)的中文〔英〕sequentialstorgestructure順序存儲構(gòu)造AbstractDataType(ADT)抽象數(shù)據(jù)類型二叉排序樹Binarysorttreequeue隊列storgestructure存儲構(gòu)造timecomplexity時間復(fù)雜度線性表LinearList二叉樹BinaryTreeDepth_FirstSearch深度優(yōu)先搜索singlylinkedlists單鏈表單項選擇題1、數(shù)據(jù)構(gòu)造是一門研究非數(shù)值計算的程序設(shè)計問題中數(shù)據(jù)元素的、數(shù)據(jù)信息在計算機(jī)中的存儲構(gòu)造以及一組相關(guān)的運(yùn)算等的課程。A:操作對象Ｂ:計算方法Ｃ:邏輯構(gòu)造Ｄ:數(shù)據(jù)映象2、某線性表最常用的運(yùn)算是插入和刪除,插入運(yùn)算是指在表尾插入一個新元素,刪除運(yùn)算是指刪除表頭第一個元素,那么采用存儲方式最節(jié)省運(yùn)算時間.。 A:僅有頭指針的單向循環(huán)鏈表B:僅有尾指針的單向循環(huán)鏈表C:單向鏈表D:雙向鏈表3、一個棧的入棧序列是a，b，c，d，e，則棧的不可能的輸出序列是____。A:abcdeB:decbaC:edcbaD:dceab4、將一個遞歸算法改為對應(yīng)的非遞歸算法時，通常需要使用_____。A:棧 B:隊列 C:循環(huán)隊列D:優(yōu)先隊列5、關(guān)于空串，以下說法中正確的有____。A:空串就是空格串B:空串的長度可能不為零C:空串是零個字符的串D:空串的長度就是其包含的空格個數(shù)6、二維數(shù)組A中，每個元素的長度為3個字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址SA開場連續(xù)存放在存儲器內(nèi)，該數(shù)組按行存放時，數(shù)組元素A[7][4]的起始地址為。A:SA+141B:SA+144C:SA+222D:SA+2257、某二叉樹的前序和后序序列正好相反，則該二叉樹一定是的二叉樹。 A:空或只有一個結(jié)點B:高度等于其結(jié)點數(shù) C:任一結(jié)點無左孩子D:任一結(jié)點無右孩子8、下述４棵二叉樹中，是完全二叉樹的是：。Ａ:Ｂ:Ｃ:Ｄ:9、深度為5的二叉樹至多有____個結(jié)點。A:16B:32C:31D:1010、在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的倍。A:1/2B:1C:2D:411、采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為____.。A:(n+1)/2B:n/2C:(n-1)/2D:n12、對線性表進(jìn)展折半搜索時，要求線性表必須______。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、在一個單鏈表中，假設(shè)刪除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、非線性構(gòu)造中，每個結(jié)點______。A:無直接前趨B:只有一個直接前驅(qū)和后繼C:只有一個直接前趨和個數(shù)不受限制的直接后繼D:有個數(shù)不受限制的直接前趨和后繼17、設(shè)稀疏矩陣按列優(yōu)先順序存儲于三元組表，則結(jié)點(3，2，-5)是三元組表中的第__________項。A:2B:3C:4D:118、對于任何一棵二叉樹T，如果其終端結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則______。A:n0=n2+1B:n2=n0+1C:n0=2n2+1D:n2=2n0+119、下面程序段的時間復(fù)雜度是________。s=0；for(i=0；i<n；i++)for(j=0；j<n；j++)s+=B[i][j]；sum=s；A:O(1)B:O(n)C:Ｏ(n2)D:O(n3)20、以下闡述不正確的選項是______。A:計算機(jī)內(nèi)的數(shù)值運(yùn)算依靠方程式，而非數(shù)值運(yùn)算〔如表、樹等〕則要依靠數(shù)據(jù)構(gòu)造B：數(shù)據(jù)構(gòu)造是研究非數(shù)值計算的程序設(shè)計問題中計算機(jī)的操作對象以及它們之間的關(guān)系和操作等的學(xué)科C:數(shù)據(jù)的邏輯構(gòu)造和數(shù)據(jù)的物理構(gòu)造有時可以不加區(qū)分D：同樣的數(shù)據(jù)對象，用不同的數(shù)據(jù)構(gòu)造來表示，運(yùn)算效率可能有明顯的差異21、計算機(jī)算法指的是，它必須具備輸入、輸出和____。A:計算方法B:排序方法C:解決問題的有限運(yùn)算步驟D:程序設(shè)計方法22、數(shù)組與一般線性表的區(qū)別主要在____。A:存儲方面B:元素類型一致C:邏輯構(gòu)造方面D:不能進(jìn)展插入、刪除運(yùn)算

23、在解決計算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題時通常設(shè)置一個打印緩沖區(qū)，

該緩沖區(qū)應(yīng)該是一個_____構(gòu)造。A:棧B:隊列C:數(shù)組D:樹24、在所有排序方法中，關(guān)鍵字比擬的次數(shù)與記錄的初始排列次序無關(guān)的是____。A:希爾排序B:起泡排序C:插入排序D:選擇排序25、二叉排序樹中，鍵值最小的結(jié)點____。A:左指針一定為空B:右指針一定為空C:左、右指針均為空D:左、右指針均不為空在一個C語言程序中，有構(gòu)造類型STUDENT的定義和構(gòu)造數(shù)組allstudents的聲明如下：structSTUDENT{charname[10];intnumber;}STUDENTallstudents[10][50];allstudents是一個二維數(shù)組，它的每個元素都是包含name和number的構(gòu)造類型。在C語言中，二維數(shù)組使用以行序為主序的存儲構(gòu)造，char類型占用1字節(jié)，int類型占用4字節(jié)。假定allstudents在內(nèi)存中的起始存儲位置是2000，請寫出計算allstudents[i][j]的存儲位置的算式，并計算allstudents[5][3]的存儲位置。答:(1)allstudents[i][j]的存儲位置=2000+(i*50+j)*14(2)allstudents[5][3]的存儲位置=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〕=2142、帶權(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}，Ｅ＝{<1,2>,<1,3>,<1,4>,<2,5>,<3,2>,<3,5>,<3,6>,<4,6>,<5,6>}，請畫出圖G，并寫出其鄰接矩陣和鄰接表表示。答：圖G如下所示，圖G的鄰接矩陣和鄰接表表示分別如圖(b)和(c)所示。對于這類問題，只要掌握了圖的概念和存儲構(gòu)造就可以做出正確的答案。通常情況下．對圖的頂點排列順序和各頂點的鄰接點排列順序并沒有特定要求，因此，在寫出鄰接矩陣和鄰接表表示時，只要按照某種排列順序畫出相應(yīng)的構(gòu)造圖就可以了。但應(yīng)該注意的是，對于鄰接矩陣表示，如果頂點結(jié)點的順序不同，那么鄰接矩陣就不一樣；對于鄰接表表示，如果頂點結(jié)點的順序或者鄰接點的順序不同，那么鄰接表就不一樣。011100011100000010010011000001000001000000(b)圖圖及其存儲構(gòu)造1(a)34256(c)12645322354∧5∧6∧∧6∧6∧七、根據(jù)二叉樹的遍歷，恢復(fù)該二叉樹并進(jìn)展其他遍歷操作一棵二叉樹的先序遍歷為：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，假設(shè)用開放定址法的線性探測法解決沖突，試在0～13的哈希地址空間中對該關(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/12≈1.9九、建設(shè)二叉排序樹并作插入和刪除操作一組關(guān)鍵字為{28,9,32,40,34,22,25,33,7,15},要求：1、建設(shè)一棵二叉排序樹2、畫出插入結(jié)點20后的二叉排序樹3、畫出再刪除結(jié)點32后的二叉排序樹答：建二叉排序樹插入結(jié)點20后的二叉排序樹或刪除結(jié)點32后的二叉排序樹或十、排序算法操作1、用希爾排序法，對8個數(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、用快速排序法，對8個數(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個數(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十一、閱讀理解算法并答復(fù)以下問題和填充1、二叉樹的存儲構(gòu)造為二叉鏈表，結(jié)合以以下圖閱讀以下算法。typedefstructnode{TElemTypedata;structnode*next;}ListNode;typedefListNode*LinkList;LinkListLeafhead=NULL;voidInorder(BTreeT){LinkLists;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í)行上述算法后所建設(shè)的構(gòu)造〔2〕說明該算法的功能答：〔1〕執(zhí)行上述算法后建設(shè)的構(gòu)造為如下所示的鏈表〔2〕該算法的功能是用中序遍歷遞歸算法對二叉樹進(jìn)展遍歷，將二叉樹中葉結(jié)點數(shù)據(jù)域的值作為單鏈表結(jié)點的值，并用頭插法建設(shè)一個以Leafhead為頭指針的逆序單鏈表〔即按二叉樹中葉結(jié)點數(shù)據(jù)從右至左鏈接成一個鏈表。2、以下算法以二叉鏈表為存儲構(gòu)造，交換二叉樹各結(jié)點的左右子樹。請在有橫線的地方填寫適宜的內(nèi)容。typedefcharDataType;typedefstructnode{DataTypedata;structnode*lchild,*rchild;}BinTNode;typedefBinTNode*BinTree;BinTreeswap(BinTreeT){BinTreet,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、以下算法的功能是什么voidabct(SqList&L){for(i=2;i<=L.length;++i)if(LT(L.r[i].key,L.r[i-1].key)){L.r[0]=L.r[i];L.r[i]=L.r[i-1];for(j=i-2;LT(L.r[0].key,L.r[j].key);--j)L.r[j+1]=L.r[j];L.r[j+1]=L.r[0];}}//InsertSort答：直接插入排序十二、算法設(shè)計1.在單鏈表上實現(xiàn)線性表的求表長ListLength(L)運(yùn)算。答：由于在單鏈表中只給出一個頭指針，所以只能用遍歷的方法來數(shù)單鏈表中的結(jié)點個數(shù)了。算法描述如下：intListLength(LinkList*L){//求帶頭結(jié)點的單鏈表的表長intlen=0;ListList*p;p=L;while(p->next!=NULL){p=p->next;len++;}return(len);}2、寫一算法用頭插法建設(shè)無頭結(jié)點的單鏈表，結(jié)果返回單鏈表的頭指針typedefcharDataType;typedefstructnode{DataTypedata;structnode*next;}ListNode;typedefListNode*LinkList;答：3、線性表的元素是無序的，且以帶頭結(jié)點的單鏈表作為存儲構(gòu)造；設(shè)計一個刪除表中所有值小于max但大于min的元素的算法。算法描述如下：delete(LinkList*head,intmax,intmin){}答：delete(LinkList*head,intmax,intmin){LinkList*p,*q;