數(shù)據(jù)結(jié)構(gòu)試卷及答案1

算法分析的目的是(C)。找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中輸入和輸出的關(guān)系C.分析算法的效率以求改進D.分析算法的易懂性和文檔性(B)是具有相同特性數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。數(shù)據(jù)符號B.數(shù)據(jù)對象C.數(shù)據(jù)D.數(shù)據(jù)結(jié)構(gòu)用鏈表表示線性表的優(yōu)點是(C)。A.便于隨機存取B.花費的存儲空間比順序表少C.便于插入與刪除D.數(shù)據(jù)元素的物理順序與邏輯順序相同輸入序列為(A,B,C,D)不可能的輸出有(D)。A.(A,B,C,D)B.(D,C,B,A)C.(A,C,D,B)D.(C,A,B,D)在數(shù)組表示的循環(huán)隊列中，front、rear分別為隊列的頭'尾指針，maxSize為數(shù)組的最大長度，隊滿的條件是(B)。A.front=maxSizeB.(rear+1)%maxSize=frontC.rear=maxSizeC.rear=maxSizeD.rear=front設(shè)有串t='Iamagoodstudent'，那么Substr(t,6,6)=(D)。A.studentB.agoodsC.goodD.agood設(shè)有一個對稱矩陣A，采用壓縮存儲方式，以行序為主序存儲all為第一個元素，其存儲地址為1,每個元素占一個地址空間，則a85地址為(B)。D.40已知廣義表LS=(A,(B,C,D),E)運用head和tail函數(shù)，取出LS中原子b的運算(C)。A.Gethead(Gethead(LS))B.Gettail(Gethead(LS))C.Gethead(Gethead(Gettail(LS)))D.Gethead(Gettail(LS))若已知一棵二叉樹先序序列為ABCDEFG，中序序列為CBDAEGF，則其后序序列為(A)。A.CDBGFEAB.CDBFGEAC.CDBAGFED.BCDAGFE下列存儲形式中，(C)不是樹的存儲形式。A.雙親表示法B.左子女右兄弟表示法D.順序表示法C.廣義表表示法對待排序的元素序列進行劃分，將其分為左、右兩個子序列，再對兩個子序列施加同樣的排序操作，直到子序列為空或只剩一個元素為止。這樣的排序方法是(C)。D.順序表示法A.直接選擇排序B.直接插入排序C.快速排序D.起泡排序采用折半查找方法進行查找，數(shù)據(jù)文件應(yīng)為(A)，且限于()。A.有序表順序存儲結(jié)構(gòu)B.有序表鏈式存儲結(jié)構(gòu)C.隨機表順序存儲結(jié)構(gòu)D.隨機表鏈式存儲結(jié)構(gòu)就平均查找速度而言，下列幾種查找速度從慢至快的關(guān)系是(B)A.順序折半哈希分塊B.順序分塊折半哈希C.分塊折半哈希順序D.順序哈希分塊折半執(zhí)行下面程序段時，執(zhí)行S語句的次數(shù)為(D)for(intI=1;I<=n;I++)for(intj=1；j<=I；j++)S;A.n2B.n2/2C.n(n+1)D.n(n+1)/2串是一種特殊的線性表，其特殊性體現(xiàn)在(B)A.可以順序存儲B.數(shù)據(jù)元素是一個字符C.可以鏈接存儲D.數(shù)據(jù)元素可以是多個字符樹的基本遍歷策略分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。結(jié)論(A)是正確的。樹的先根遍歷序列與其對應(yīng)的二叉樹的先序遍歷序列相同樹的后根遍歷序列與其對應(yīng)的二叉樹的先序遍歷序列相同樹的先根遍歷序列與其對應(yīng)的二叉樹的中序遍歷序列相同以上都不對由五個分別帶權(quán)值為9,2,3,5,14的葉子結(jié)點構(gòu)成的一棵哈夫曼樹，該樹的帶權(quán)路徑長度為(C)。A.60B.66C.67D.50一棵二叉樹有67個結(jié)點，這些結(jié)點的度要么是0,要么是2。這棵二叉樹中度為2的結(jié)點有(A)個A.33B.34C.32D.30有一個有序表為｛1,3,9,12,32,41,45,62,75,77,82,95,100｝，當(dāng)二分查找值82為的結(jié)點時，(C)次比較后查找成功。A.1B.2C.4D.8若有文件的關(guān)鍵字序列為：[265][301][751][129][937][863][742][694][076][438],以下為二路歸并排序過程。第二趟為：（D）[265301][129751][863937][694742][076438][076129265301438694742751863937][129265301694742751863937][076438][129265301751][694742863937][076438]二、填空題（本大題共6小題，每空2分，共12分；答案填在下表內(nèi)）1算法是指令的有限序列，其中每一條指令表示一個或多個操作，此外，一個算法還具有五個重要特性，它們分別是—有窮性—、一確定性__、___可行性_____、有零或多個輸入和有一或多個輸出。2算法優(yōu)劣的五個標(biāo)準是正確性、可使用性、—可讀性___、健壯性、__效率一。3有”個球隊參加的足球聯(lián)賽按主客場制進行比賽，共需進行n（n-1）場比賽。4設(shè)有串t='Iamastudent'，s='good'，那么Concat（t,s）='Iamastudentgood'，Substr（t,8,7）='student'。5在解決計算機主機與打印機之間速度不匹配時通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機從該緩沖區(qū)中取出數(shù)據(jù)打印。該緩沖區(qū)應(yīng)該是一個一隊列一—結(jié)構(gòu)，其主要特點是—先進先出。6廣義表（（a）,a）的表頭是（a）___，表尾是O。三、判斷題（對的打“””，錯的打“X”。每小題1分，共10分;答案填在下表內(nèi)）1數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。（"）2三個結(jié)點的二叉樹和三個結(jié)點的樹一樣，都具有三種不同的形態(tài)。（X）3中序序列和后序序列相同的二叉樹為：空樹和缺右子樹的單支樹。（"）4對于兩棵具有相同關(guān)鍵字集合而形狀不同的二叉排序樹，中序遍歷后得到的關(guān)鍵字排列順序相同。（"）5序列｛30，40，50，15，25，35，38，10｝是堆。（X）6對于無向圖的生成樹，從同一頂點出發(fā)所得的生成樹相同。（X）7若設(shè)哈希表長m=14,哈希函數(shù)H（key）=key%11,表中已有4個結(jié)點。addr（15）=4addr（38）=5addr（61）=6addr（84）=7其余地址為空，如用二次探測再散列處理沖突，關(guān)鍵字為49的結(jié)點的地址是9。（"）8一個深度為k的，具有最少結(jié)點數(shù)的完全二叉樹按層次，（同層次從左向右）用自然數(shù)依此對結(jié)點編號則，則編號最小的葉子的序號是2心+1；編號是i的結(jié)點所在的層次號是「logi|+1。（「logi|表示向上取整」（根所在的層次號規(guī)定為1層）。（"）29在一棵7階B樹中，一個結(jié)點中最多有6棵子樹，最少有3棵子樹。（X）10算法可以沒有輸入，但是必須有輸出。（"）四'畫出樹的孩子兄弟表示法示意的樹或森林。（4分）五、要求題（本大題共2小題，共12分）設(shè)關(guān)鍵字的輸入序列為｛4，5，7，2，1，3，6｝1.（8分）從空樹開始構(gòu)造平衡二叉樹，畫出每加入一個新結(jié)點時二叉樹的形態(tài)，若發(fā)生不平衡，指明需做的平衡旋轉(zhuǎn)類型及平衡旋轉(zhuǎn)的結(jié)果。（4分）上面的數(shù)據(jù)作為待排序的數(shù)據(jù)，寫出用快速排序進行一趟劃分后的數(shù)據(jù)序列六、按要求做題（本大題共2小題，共12分）1畫出無向圖G的鄰接表存儲結(jié)構(gòu)，根據(jù)鄰接表存儲結(jié)構(gòu)寫出深度優(yōu)先和廣度優(yōu)先遍歷序列。（7分）2用prim算法求下圖的最小生成樹，寫出最小生成樹的生成過程。（5分）七、算法分析設(shè)計題(本大題共5小題，共30分)寫出程序段的功能,并給出一個測試用例(一個輸入數(shù)據(jù)和一個輸出結(jié)果)(5分)。voidconversion(){Stacks;intn;SElemTypee;initstack(s);printf("Pleaseinputnumber:");scanf("％d”，&n);while(n){push(s,n%8);n=n/8;}while(!stackempty(s)){pop(s,e);printf("％d”,e);}}下面是一個使用棧stack實現(xiàn)對二叉樹進行非遞歸先根遍歷的函數(shù)，請在標(biāo)號處填寫合適的語句。(每空1分，共5分)程序:Voidpreorder(bitree*T){bitree*stack[m];inttop;if(T!=NULL){top=1;stack[top]=(1);while((2)){p=stack[top];top--;printf("％d”,p->data);if(p->rchild!=NULL){(3);stack[top]=p->rchild;}if((4)){top++;(5);}}}⑴⑵⑶⑷⑸請在標(biāo)號處填寫合適的語句。完成下列程序。(每空1分，共5分)intBinary_Search(S_TBLtbl，KEYkx){/*在表tbl中查找關(guān)鍵碼為kx的數(shù)據(jù)元素，若找到返回該元素在表中的位置，否則，返回0*/intmid，flag=0；low=1；high=length；while(⑴&!flag){/*非空，進行比較測試*/TOC\o"1-5"\h\zmid=⑵；if(kx<[mid].key)⑶；elseif(kx>[mid].key)⑷；else{flag=⑸；break；}}returnflag;}⑴⑵⑶⑷⑸下面是一個采用直接選擇排序方法進行升序排序的函數(shù)，請在標(biāo)號處填寫合適的語句。(每空1分，共5分)程序：Voidseletesort(intA[n],intn){inti,j,t,minval,minidx;for(i=1;i<=n-1;i++){minval=A[i+1];(1)for(j=i+2;j<=n;j++)if((2)){(3);minidx=j;}if(⑷){t=A[i+1];(5)A[minidx]=t;}}}⑴⑵⑶⑷⑸5試寫出求有向無環(huán)圖的關(guān)鍵路徑算法的設(shè)計思路(10分)四'畫出樹的孩子兄弟表示法示意的樹或森林。(4分)

五、要求題（本大題共2小題，共12分）一趟劃分后的數(shù)據(jù)序列3124756六、按要求做題（12分）1DFS遍歷序列v1v2v4v8v5v3v6v7(或12485367)BFS遍歷序列v1v2v3v4v5v6v7v8(或12345678)鄰接點的順序可以不同，可以有不同的深度優(yōu)先和廣度優(yōu)先遍歷序列。（5分，如有錯誤酌情扣分。）

七、算法設(shè)計題(30分)將十進制轉(zhuǎn)化成八進制數(shù)(5分)測試用例：輸入10輸出122(5分，每空1分)(1)Ttop>0top++p->lchild!=NULLstack[top]=p->lchild3(5分，每空1分)low<=high(low+high)/2high=mid-1⑷low=mid+1(5)1(5分，每空1分)minidx=i+1minval>A[j]minval=A[j]⑷i!=j(5)A[i+1]=A[minidx]5(10分，不同答案，酌情得分)輸入頂點和弧信息，建立其鄰接表計算每個頂點的入度對其進行拓撲排序排序過程中求頂點的Ve[i]將得到的拓撲序列進棧按逆拓撲序列求頂點的Vl[i]計算每條弧的e[i]和l[i],找出e[i]=l[i]的關(guān)鍵活動第2學(xué)期數(shù)據(jù)結(jié)構(gòu)試卷A選擇題(本大題共15小題，每題2分，共30分；答案填在下表內(nèi))從一個長度為100的順序表中刪除第30個元素時需向前移動(A)個元素A、70B、71C、69D、30在一個具有N個單元的順序表中，假定以地址低端(即下標(biāo)為1的單元)作為底，以top作為頂指針,則當(dāng)做進棧處理時top變化為—D___。A、top不變B、top=0C、top=top-1D、top=top+1從一個具有n個結(jié)點的單鏈表中查找其值等于x結(jié)點時，在查找成功情況下，則平均比較__B__個結(jié)點。A、nB、n/2C、(n-1)/2D、(n+1)/2在一個單鏈表中，若要刪除p指針?biāo)附Y(jié)點的后繼結(jié)點,則執(zhí)行(B)A、p->next;p->next=p->next->next;B、p->next=p->next->next;C、p=p->next;D、p=p->next->>next;在一個鏈隊列中，假定front和rear分別為隊首和隊后指針,則進行插入S結(jié)點的操作時應(yīng)執(zhí)行__C_。A、front->next=s；front=s；B、s->next=rear;rear=s；C、rear->next=s;rear=s；D、s->next=front;front=s；在一棵度為3的樹中度為3的結(jié)點數(shù)為3個，度為2的結(jié)點數(shù)為1個，度為1的結(jié)點數(shù)為1個，那么度為0的結(jié)點數(shù)為__C__個A、6B、7C、8D、9假定一棵二叉樹的結(jié)點數(shù)為33個，則它的最小高度為_C_,最大高度為___A、4,33B、5,33C、6,33D、6,32在一棵完全二叉樹中，若編號為i的結(jié)點有右孩子，則該結(jié)點的右孩子編號為__B_。A、2iB、2i+1C、2i-1D、i/2在一個有向圖中，所有頂點的入度之和等于所有弧數(shù)和__A_倍。A、1B、2C、3D、4對于一個具有N個頂點的圖，若用鄰接矩陣表示，則該矩陣的大小為__D_。A、NB、(N-1)2C、(N+1)2D、N2已知一個圖如圖所示，在該圖的最小生成樹中各邊上數(shù)值之和為__B.

A、21B、26C、28D、33A、21B、26C、28D、33TOC\o"1-5"\h\zA、v1v4v6v2v5v3B、v1v2v3v4v5v6C、v1v4v2v3v6v5D、v1v2v4v6v3v5二維數(shù)組M的元素是4個字符（每個字符占一個存儲單元）組成的串，行下標(biāo)i的范圍從0到4,列下標(biāo)j的范圍從0到5，M按行存儲時元素M[2][4]的起始地址與M按列存儲時元素（D）的起始地址相同。A、m[2][4]B、M[4][2]C、M[3][1]D、M[3][1]具有6個結(jié)點的無向圖至少應(yīng)有（A）條邊才能保證是連通圖。5B、6C、7D、8TOC\o"1-5"\h\z采用鄰接表存儲的圖的深度優(yōu)先遍歷類似于二叉樹的（A）。A先序遍歷B中序遍歷C.后序遍歷D.按層遍歷數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)元素之間抽象化的相互關(guān)系和這種關(guān)系在計算機中的存儲結(jié)構(gòu)表示，根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，通常有下列四類基本結(jié)構(gòu)：集合、線性結(jié)構(gòu)、（1）和（2）。評價算法的標(biāo)準很多，通常是以執(zhí)行算法所需要的（3）和所占用的（4）來判別一個算法的優(yōu)劣。線性表的順序存儲結(jié)構(gòu)特點是表中邏輯關(guān)系相鄰的元素在機器內(nèi)的（5）也是相鄰的?？崭翊拈L度為串中所包含（6）字符的個數(shù)，空串的長度為（7）加上表示指向前驅(qū)和（8）的線索的二叉數(shù)稱為線索二叉樹。三、判斷題（對的打“””，錯的打“X”。每小題1分，共10分）（錯）1.線性表的唯一存儲形式是鏈表。（對）2.已知指針P指向鍵表L中的某結(jié)點，執(zhí)行語句P=P-〉next不會刪除該鏈表中的結(jié)點。（對）3.在鏈隊列中，即使不設(shè)置尾指針也能進行入隊操作。（錯）4.如果一個串中的所有字符均在另一串中出現(xiàn)，則說前者是后者的子串。（錯）5.設(shè)與一棵樹T所對應(yīng)的二叉樹為BT，則與T中的葉子結(jié)點所對應(yīng)的BT中的結(jié)點也一定是葉子結(jié)點。（對）6.快速排序是不穩(wěn)定排序。（錯）7.任一AOE網(wǎng)中至少有一條關(guān)鍵路徑，且是從源點到匯點的路徑中最短的一條。（錯）8.若圖G的最小生成樹不唯一，則G的邊數(shù)一定多于n-1,并且權(quán)值最小的邊有多條（其中n為G的頂點數(shù)）。（錯）9.給出不同的輸入序列建造二叉排序樹，一定得到不同的二叉排序樹。（錯）10.基數(shù)排序是多關(guān)鍵字排序。從最低位關(guān)鍵字起進行排序。四、應(yīng)用題。（共44分）畫出該圖的鄰接矩陣和鄰接表。根據(jù)鄰接表從A開始求DFS和BFS序列。（12分）假設(shè)用于通信的電子由字符集｛a,b,c,d,e,f,g,h｝中的字母構(gòu)成，這8個字母在電文中出現(xiàn)的概率分別為｛，，，，，，，｝畫出哈夫曼樹，并為這8個字母設(shè)計哈夫曼編碼。（8分）已知序列｛70,73,69,23,93，18,11,68｝請給出直接插入排序作升序排序每一趟的結(jié)果和快速排序作升序排序時一趟的結(jié)果。（10分）設(shè)有一組關(guān)鍵字關(guān)鍵碼集為｛47,7,29,11,16,92,22,8,3｝,哈希表表長為11,Hash（key）=keymod11,用線性探測法處理沖突，構(gòu)造哈希表，并求它成功查找的ASL。（8分）二叉樹的先序遍歷序列為ABCDEFGHI,中序遍歷序列為BCAEDGHFI,畫出這棵二叉樹