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

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

24.設(shè)查找表為(1，2，3，4，5，6，7，8，9，10，11)(1)畫出對上述查找表進行折半查找所對應(yīng)的判定樹(樹中結(jié)點用數(shù)值表示)。(2)說明成功查找到元素5，9各需要經(jīng)過多少次元素間的比較?(3)說明查找不到元素4.2，5.5各需要經(jīng)過多少次元素間的比較?四、程序填空題(每空2分，共16分)25.以下程序是折半插人排序的算法設(shè)待排序的記錄序列存放在a[1]，…a[n]中，以a[0]作為輔助工作單元，以下程序是要把a[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é)點)。voidInorder(structBTreeNode*BT){ aif(BT!=NULL)(1)