國家開放大學(xué)本科末考試數(shù)據(jù)結(jié)構(gòu)歷年試題與參考答案18Q

國家開放大學(xué)(中央廣播電視大學(xué))2018年秋季學(xué)期“開放本科”期末考試數(shù)據(jù)結(jié)構(gòu)(本)試題2019年1月一、單項(xiàng)選擇題(每小題3分，共30分)1.如下圖所示，若從頂點(diǎn)a出發(fā)，按圖的廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為()。A.acebdfC.aecbdfB.aecbfdD.acefdb參考答案：aecbdf2.結(jié)構(gòu)中的元素之間存在一對多的關(guān)系是()。A.集合B.線性結(jié)構(gòu)C.樹形結(jié)構(gòu)D.圖狀結(jié)構(gòu)參考答案：樹形結(jié)構(gòu)3.設(shè)有一個(gè)長度為18的順序表，要在第4個(gè)元素之前插入1個(gè)元素(也就是插入元素作為新表的第4個(gè)元素)，則移動(dòng)元素個(gè)數(shù)為()。A.15C.5B.16D.4參考答案：154.一個(gè)不帶頭結(jié)點(diǎn)的單循環(huán)鏈表，尾指針為rear，在鏈表中插人一個(gè)s所指向的新結(jié)點(diǎn)，并作為新的尾結(jié)點(diǎn)，可執(zhí)行()。A.rear一>next=s；s一>next=rear一>next；rear=s；B.rear一>next=s一>next；rear=s；C.s一>next=rear一>next；rear一>next=s一>next；rear=s；D.s一>next=rear一>next；rear一>next=s；rear=s；參考答案：s一>next=rear一>next；rear一>next=s；rear=s；5.元素a，b，c，d按順序依次進(jìn)棧，則該棧的不可能輸出序列是()(進(jìn)棧出?？梢越惶孢M(jìn)行).A.c，b，a，dC.a，c，b，dB.d，c，b，aD.d，c，a，b參考答案：d，c，a，b6.在一個(gè)棧頂指針為top的鏈棧中進(jìn)行出棧操作，用變量x保存棧頂元素的值，則執(zhí)行()。A.x=top->data；top=top->next；C.top=top一>next；x=top一>data；B.x=top->data；D.top=top->next；x=data；參考答案：x=top->data；top=top->next；7.設(shè)有一個(gè)18階的對稱矩陣A，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中(數(shù)組下標(biāo)從1開始)，則矩陣中a10.8元素對應(yīng)于數(shù)組中第()號元素。(矩陣中的第1個(gè)元素是a1.1)A.51C.52B.53D.54參考答案：538.一棵采用鏈?zhǔn)酱鎯?chǔ)的二叉樹中，共有n個(gè)指針域被有效使用(即指針域?yàn)榉强?。該二叉樹有()個(gè)指針域?yàn)榭?。A.n+1C.n--1B.nD.n+2參考答案：n+29.在一棵二叉樹中，若編號為9的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號為()。A.18C.15B.16D.19參考答案：1910.設(shè)一棵哈夫曼樹共有15個(gè)非葉結(jié)點(diǎn)，則該樹總共有()個(gè)結(jié)點(diǎn)。A.29C.31B.27D.28參考答案：31二、填空題(每小題2分，共24分)11.在n個(gè)整數(shù)中求最大數(shù)的算法中，其基本操作是_____________.參考答案：元素間的比較12.設(shè)有一個(gè)長度為20的順序表，要?jiǎng)h除第5個(gè)元素，則最少要移動(dòng)元素的個(gè)數(shù)為_____________.參考答案：1513.在雙向鏈表中，要?jiǎng)h除p所指的結(jié)點(diǎn)，其中所用的一條語句(p->prior)->next=p->next；的功能是：使P所指結(jié)點(diǎn)的直接前驅(qū)的右指針指向_____________.參考答案：P所指結(jié)點(diǎn)的直接后繼14.設(shè)有一個(gè)頭指針為head的單向鏈表，p指向鏈表中的某結(jié)點(diǎn)，若要使該鏈表成為單向循環(huán)鏈表，可用語句while(p->next!=NULL)_____________.和p一>next=head；。參考答案：p=p->next15.在一個(gè)鏈隊(duì)中，設(shè)front和rear分別為隊(duì)頭和隊(duì)尾指針，則s所指結(jié)點(diǎn)(數(shù)據(jù)域已賦值)的人隊(duì)操作為s一>next=NULL；_____________rear=s；。參考答案：rear->next=s；16.字符串a(chǎn)l=“heijing”，a2=“hef”，a3=“heifang”，a4=“hefi”中最小的是_______.參考答案：a217.棧的特點(diǎn)之一是：元素進(jìn)、出棧的次序是：后進(jìn)_____________.參考答案：先出18.在對10個(gè)記錄的序列(14，30，10，7，22，13，66，85，47，58)進(jìn)行直接插人排序時(shí)，當(dāng)把第6個(gè)記錄13插人到有序表時(shí)，為尋找插人位置，元素間需比較_____________次。(由小到大排列)參考答案：419.18個(gè)元素進(jìn)行冒泡法排序，通常需要進(jìn)行17趟冒泡，其中第10趟冒泡共需要進(jìn)行_____________次元素間的比較。參考答案：820.一棵有15個(gè)結(jié)點(diǎn)的哈夫曼樹，采用鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)，該樹結(jié)構(gòu)中有____________個(gè)葉結(jié)點(diǎn)。參考答案：821.廣義表的(b，(a，b)，d，(c，((e，f)，j)))深度是_____________.參考答案：422.序列4，2，7，9，5，3，8，6采用歸并排序算法(升序)，經(jīng)一趟歸并后，序列的結(jié)果為_____________.參考答案：2，4，7，9，3，5，6，8三、綜合題(每小題6分，共30分)23.(1)已知某二叉樹的后序遍歷序列是febch，給出該二叉樹的根結(jié)點(diǎn)?又該二叉樹的中序遍歷序列是fbehc，分別給出該二叉樹的左、右子樹的結(jié)點(diǎn)?(2)畫出上述二叉樹?若上述二叉樹的各個(gè)結(jié)點(diǎn)的字符分別代表不同的整數(shù)(其中沒有相等的)，并恰好使該樹成為一棵二叉排序樹，試給出h、b、c、f、e的大小關(guān)系。

24.設(shè)查找表為(1，2，3，4，5，6，7，8，9，10，11)(1)畫出對上述查找表進(jìn)行折半查找所對應(yīng)的判定樹(樹中結(jié)點(diǎn)用數(shù)值表示)。(2)說明成功查找到元素5，9各需要經(jīng)過多少次元素間的比較?(3)說明查找不到元素4.2，5.5各需要經(jīng)過多少次元素間的比較?四、程序填空題(每空2分，共16分)25.以下程序是折半插人排序的算法設(shè)待排序的記錄序列存放在a[1]，…a[n]中，以a[0]作為輔助工作單元，以下程序是要把a(bǔ)[i]插人到已經(jīng)有序的序列a[1]，…a[i一1]中。voidbinsort(NODEa[]，intn){ intx，i，j，s，k，m；For(i=2；i<=(1)___________；i++){ a0]=a[i]；x=a[i].key；s=1；j=i-1；while(s<=j){ m=(2)_____________; if(x<a[m].key) (3)__________________; else (4)__________________;}for(k=i一1；k>=j+1；k--) (5)______________=a[k]；a[j+1]==a[0]； }}參考答案：(1)n(2)(s+j)/2；(3)j=m一1；(4)s=m+1；(5)a[k+1]26.以下程序是中序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分(樹結(jié)構(gòu)中，左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn))。voidInorder(structBTreeNode*BT){ aif(BT!=NULL)(1)