山東管理學(xué)院成人高考本科學(xué)歷數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題及參考答案

數(shù)據(jù)結(jié)構(gòu)1．算法分析的目的是(C)。A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中輸入和輸出的關(guān)系C.分析算法的效率以求改進D.分析算法的易懂性和文檔性2．（B）是具有相同特性數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。A.數(shù)據(jù)符號B.數(shù)據(jù)對象C.數(shù)據(jù)D.數(shù)據(jù)結(jié)構(gòu)3．用鏈表表示線性表的優(yōu)點是(C)。A.便于隨機存取B.花費的存儲空間比順序表少C.便于插入與刪除D.數(shù)據(jù)元素的物理順序與邏輯順序相同4．輸入序列為（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)5．在數(shù)組表示的循環(huán)隊列中，front、rear分別為隊列的頭、尾指針，maxSize為數(shù)組的最大長度，隊滿的條件是(B)。A.front=maxSizeB.(rear+1)%maxSize=frontC.rear=maxSizeD.rear=front6．設(shè)有串t='Iamagoodstudent'，那么Substr(t,6,6)=（D）。A.studentB.agoodsC.goodD.agood7．設(shè)有一個對稱矩陣A，采用壓縮存儲方式，以行序為主序存儲a11為第一個元素，其存儲地址為1，每個元素占一個地址空間，則a85地址為（B）。A.23B.33C.18D.408．已知廣義表 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))9．若已知一棵二叉樹先序序列為ABCDEFG，中序序列為CBDAEGF，則其后序序列為(A)。A.CDBGFEAB.CDBFGEAC.CDBAGFED.BCDAGFE10．下列存儲形式中，(C)不是樹的存儲形式。A.雙親表示法B.左子女右兄弟表示法C.廣義表表示法D.順序表示法11．對待排序的元素序列進行劃分，將其分為左、右兩個子序列，再對兩個子序列施加同樣的排序操作，直到子序列為空或只剩一個元素為止。這樣的排序方法是(C)。A.直接選擇排序B.直接插入排序C.快速排序D.起泡排序12．采用折半查找方法進行查找，數(shù)據(jù)文件應(yīng)為（），且限于（）。AA.有序表順序存儲結(jié)構(gòu)B.有序表鏈式存儲結(jié)構(gòu)C.隨機表順序存儲結(jié)構(gòu)D.隨機表鏈式存儲結(jié)構(gòu)13．就平均查找速度而言，下列幾種查找速度從慢至快的關(guān)系是（B）A.順序折半哈希分塊B.順序分塊折半哈希C.分塊折半哈希順序D.順序哈希分塊折半14．執(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)/215．串是一種特殊的線性表，其特殊性體現(xiàn)在（B）A.可以順序存儲B.數(shù)據(jù)元素是一個字符C.可以鏈接存儲D.數(shù)據(jù)元素可以是多個字符16．樹的基本遍歷策略分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。結(jié)論()是正確的。AA.樹的先根遍歷序列與其對應(yīng)的二叉樹的先序遍歷序列相同B.樹的后根遍歷序列與其對應(yīng)的二叉樹的先序遍歷序列相同C.樹的先根遍歷序列與其對應(yīng)的二叉樹的中序遍歷序列相同D.以上都不對17．由五個分別帶權(quán)值為9，2，3，5，14的葉子結(jié)點構(gòu)成的一棵哈夫曼樹，該樹的帶權(quán)路徑長度為(C)。A.60B.66C.67D.5018．一棵二叉樹有67個結(jié)點，這些結(jié)點的度要么是0，要么是2。這棵二叉樹中度為2的結(jié)點有(A)個A.33B.34C.32D.3019．有一個有序表為{1,3,9,12,32,41,45,62,75,77,82,95,100},當(dāng)二分查找值82為的結(jié)點時，（C）次比較后查找成功。A.1B.2C.4D.820．若有文件的關(guān)鍵字序列為：[265][301][751][129][937][863][742][694][076][438]，以下為二路歸并排序過程。第二趟為:DA.[265301][129751][863937][694742][076438]B.[076129265301438694742751863937]C.[129265301694742751863937][076438]D.[129265301751][694742863937][076438]二、填空題（本大題共6小題，每空2分，共12分；答案填在下表內(nèi)） 1 算法是指令的有限序列，其中每一條指令表示一個或多個操作，此外，一個算法還具有五個重要特性，它們分別是_______、______、________、有零或多個輸入和有一或多個輸出。 2 算法優(yōu)劣的五個標準是正確性、可使用性、______、______、_____。 3 有n個球隊參加的足球聯(lián)賽按主客場制進行比賽，共需進行_________場比賽。4 設(shè)有串t='Iamastudent'，s='good'，那么Concat(t,s)='Iamastudentgood'，Substr(t,8,7)=__________。 5 在解決計算機主機與打印機之間速度不匹配時通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機從該緩沖區(qū)中取出數(shù)據(jù)打印。該緩沖區(qū)應(yīng)該是一個_________結(jié)構(gòu)，其主要特點是__________。 6 廣義表((a),a)的表頭是_______，表尾是_______。 三、判斷題（對的打“√”，錯的打“×”。每小題1分，共10分;答案填在下表內(nèi)）1數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。對2三個結(jié)點的二叉樹和三個結(jié)點的樹一樣，都具有三種不同的形態(tài)。錯3中序序列和后序序列相同的二叉樹為：空樹和缺右子樹的單支樹。對4對于兩棵具有相同關(guān)鍵字集合而形狀不同的二叉排序樹，中序遍歷后得到的關(guān)鍵字排列順序相同。對5序列{30，40，50，15，25，35，38，10}是堆。錯6對于無向圖的生成樹，從同一頂點出發(fā)所得的生成樹相同。錯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é)點編號則，則編號最小的葉子的序號是2k-2+1；編號是i的結(jié)點所在的層次號是「log2i|+1。（「log2i|表示向上取整」（根所在的層次號規(guī)定為1層）。對9在一棵7階B樹中，一個結(jié)點中最多有6棵子樹，最少有3棵子樹。錯10算法可以沒有輸入，但是必須有輸出。對11．不論是入隊列操作還是入棧操作，在順序存儲結(jié)構(gòu)上都需要考慮“溢出”情況。（對)12．當(dāng)向二叉排序樹中插入一個結(jié)點，則該結(jié)點一定成為葉子結(jié)點。（對)13．設(shè)某堆中有n個結(jié)點，則在該堆中插入一個新結(jié)點的時間復(fù)雜度為0(log2n)。(對)14．完全二叉樹中的葉子結(jié)點只可能在最后兩層中出現(xiàn)。（對)15．哈夫曼樹中沒有度數(shù)為1的結(jié)點。(對)16．對連通圖進行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點。（對)17．先序遍歷一棵二叉排序樹得到的結(jié)點序列不一定是有序的序列。（對)18．由樹轉(zhuǎn)化成二叉樹，該二叉樹的右子樹不一定為空。（錯)19．線性表中的所有元素都有一個前驅(qū)元素和后繼元素。（錯)20.帶權(quán)無向圖的最小生成樹是唯一的。(錯)四、畫出樹的孩子兄弟表示法示意的樹或森林。（4分）A∧B∧∧CD∧H∧∧F∧EG∧∧I∧A∧B∧∧CD∧H∧∧F∧EG∧∧I∧五、要求題（本大題共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分）V1V2V3V4V5V6V7V8V1V2V3V4V5V6V7V82用prim算法求下圖的最小生成樹，寫出最小生成樹的生成過程。（5分）V7V4V3V5V5V7V1V3V7V2V4V5V645425265506030705040V1V250V6V2V6V1V3V4V7V4V3V5V5V7V1V3V7V2V4V5V645425265506030705040V1V250V6V2V6V1V3V4七、算法分析設(shè)計題（本大題共5小題，共30分）1．寫出程序段的功能,并給出一個測試用例（一個輸入數(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);}}2.下面是一個使用棧stack實現(xiàn)對二叉樹進行非遞歸先根遍歷的函數(shù),請在標號處填寫合適的語句。(每空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);}

}}}⑴⑵⑶⑷⑸3.請在標號處填寫合適的語句。完成下列程序。(每空1分，共5分)intBinary_Search(S_TBLtbl，KEYkx){ intmid，flag=0；low=1；high=length；while(⑴&!flag){/*非空，進行比較測試*/mid=⑵；if(kx<tbl.elem[mid].key) ⑶；else if(kx>tbl.elem[mid].key)⑷；else{flag=⑸；break；}}returnflag;}⑴⑵⑶⑷⑸4.下面是一個采用直接選擇排序方法進行升序排序的函數(shù)，請在標號處填寫合適的語句。(每空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((4)){t=A[i+1];(5)A[minidx]=t;}

}}⑴⑵⑶⑷⑸5試寫出求有向無環(huán)圖的關(guān)鍵路徑算法的設(shè)計思路（10分）數(shù)據(jù)結(jié)構(gòu)答案選擇題（本大題共20小題，每題1分，共20分；答案填在下表內(nèi)）12345678910CB:C:D:B:D:B:C:A:C11121314151617181920:CA:B:D:B:A:C:ACD二、填空題（本大題共5小題，每空1分，共12分；答案填在下表內(nèi)） 1 有窮性確定性可行性 2 可讀性健壯性效率 3 n(n-1) 4 'student' 5 隊列先進先出 6 (a)(a) 三、判斷題（對的打“√”，錯的打“×”。每小題1分，共10分）1）true;2）flase;3）true;4）true;5）flase;6）flase;7）true;8）true;9）flase;10）true四、畫出樹的孩子兄弟表示法示意的樹或森林。（4分）AABCDEFGHI其他形式的樹形結(jié)構(gòu)酌情給分。五、要求題（本大題共2小題，共12分）454574574572142571256143324517324517632461752.一趟劃分后的數(shù)據(jù)序列312475