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

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

}}⑴⑵⑶⑷⑸5試寫出求有向無環(huán)圖的關(guān)鍵路徑算法的設(shè)計(jì)思路（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 隊(duì)列先進(jìn)先出 6 (a)(a) 三、判斷題（對(duì)的打“√”，錯(cuò)的打“×”。每小題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