1252數(shù)據(jù)結構（本）-國家開放大學2022年1月（2021秋）期末考試真題-開放本科

1、 試卷代號：1252國家開放大學2021年秋季學期期末統(tǒng)一考試數(shù)據(jù)結構（本） 試題2022年1月一、單項選擇題（把合適的選項編號填寫在括號內。每小題3分，共45分）1.下列說法中，不正確的是( )。A.數(shù)據(jù)元素是數(shù)據(jù)的基本單位B.數(shù)據(jù)項是數(shù)據(jù)中不可分割的最小可標識單位C.數(shù)據(jù)可有若干個數(shù)據(jù)元素構成D.數(shù)據(jù)項可由若干個數(shù)據(jù)元素構成2.每個存儲結點不僅含有一個數(shù)據(jù)元素，還包含一組指針，該存儲方式是( )存儲方式。A.順序B.鏈接C.索引D.散列3.在一個單鏈表中p指向結點a，q指向結點a的直接后繼結點b，要刪除結點b，可執(zhí)行( )。A.p-next=q-nextB.p=q-nextC.p-next

2、=qD.p-next=q4.在一個單鏈表中p所指結點之后插入一個s所指的結點時，可執(zhí)行( )。A.p-next=s;s-next=p-nextB.p-next=s-nextC.p=s-nextD.s-next=p-next,p-next=s5.向順序棧中壓入新元素時，應當( )。A.先移動棧頂指針，再存入元素B.先存入元素，再移動棧頂指針C.先后次序無關緊要D.同時進行6.一般情況下，將遞歸算法轉換成等價的非遞歸算法應該設置( )。A.棧B.隊列C.堆?；蜿犃蠨.數(shù)組7.判斷一個循環(huán)隊列Q(最多元素為m)為滿的條件是( )。A.Q-front=Q-rearB.Q-front!=Q-rearC.

3、Q-front=(Q-rear+l)%mD.Q-front!=(Q-rear+l)%m8.空串與空格串( )。A.相同B.不相同C.可能相同D.無法確定9.廣義表(f，h，(a，b，d，c)，d，e，(i，j)，k)的長度是( )。A.6B.10C.8D.410.二叉樹第k層上最多有( )個結點。A.2kB.2k-lC.2k-lD.2k-l11.樹中的結點數(shù)等于所有結點的度數(shù)加( )。A.1B.OC.2D.-112.對于具有n個頂點的圖，若采用鄰接矩陣表示，則該矩陣的大小為( )。A.nB.n2C.n-lD.(n-l)213.對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則所有頂點鄰

4、接表中的結點總數(shù)為( )。A.nB.eC.2nD.2e14.采用折半查找方法查找長度為n的線性表時，其算法的時間復雜度為( )。A.O(n2)B.O(nlog2n)C.O(n)D.0(1og2n)15.從未排序序列中依次取出元素與已經排好序的序列中的元素作比較。將其放人已排序序列的正確的位置上，此方法稱為( )。A.插入排序B.交換排序C.選擇排序D.歸并排序二、判斷題（根據(jù)敘述正確與否在其后面的括號內打對號“”或打叉號“”。每小題2分，共30分）16.數(shù)據(jù)元素可以有一個或多個數(shù)據(jù)項組成。( )17.數(shù)據(jù)結構中，元素之間存在多對多的關系稱為圖狀結構。( )18.設有一個單向鏈表，結點的指針域為

5、next，頭指針為head，p指向尾結點，為了使該單向鏈表改為單向循環(huán)鏈表，可用語句p-next=head。( )19.設有一個單向循環(huán)鏈表，結點的指針域為next，頭指針為head，指針p指向表中某結點，若邏輯表達式p-next=head;的結果為真，則p所指結點為尾結點。( )20.循環(huán)隊列隊頭指針在隊尾指針前一個位置，隊列是“滿”狀態(tài)。( )21.棧是限定在表的兩端進行插入和刪除操作的線性表，又稱為先進先出表。( )22.向一個棧頂指針為h的鏈棧(結點的指針域為next)中插入一個s所指結點時，先執(zhí)行s-next=h，再執(zhí)行h=s操作。( )23.串的兩種最基本的存儲方式是順序和鏈接。(

6、 )24.對稀疏矩陣進行壓縮存儲，矩陣中每個非零元素對應的三元組包括該元素的行號、列號和元素值三項信息。( )25.深度為k的完全二叉樹至少有2k-l個結點。( )26.如果結點A有3個兄弟，而且B是A的雙親，則B的度是4。( )27.用鄰接矩陣存儲圖的時候，占用空間大小不但與圖的結點個數(shù)有關還與圖的邊數(shù)有關。( )28.對連通圖進行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點。( )29.二叉排序樹在呈單支二叉樹時，查找效率最低。( )30.冒泡排序是一種比較簡單的插入排序方法。( )三、綜合應用及程序設計題（每小題5分，共25分）31.設有一個頭指針為head的不帶頭結點單向鏈表中(結點類型為N

7、ODE)，p為指向鏈表中某個結點的指針。以下程序段為插入一個指針為s的結點，使它成為p結點的直接驅，請選擇其中空格的選項。NODE*q；q=head；while(q-next!=p) ；s-next=p；(3分)A.p=p-nextB.q=q-nextC.s=s-nextD.head=head-next(2分)A.p-next=qB.p-next=sC.q-next=sD.q-next=p32.以下為求二叉樹深度的算法，完成程序中空格部分。intBTreeDepth(BTreeNode*BT)if (BT=NULL)return O；else(int dep1=BTreeDepth(BT-le

8、ft)；*計算左子樹的深度*Int dep2=BTreeDepth(BT-right)；*計算右子樹的深度*if( )return depl+l；elsereturn dep2+!；A.depldep2B.deplleft=NULLD.BT-right=NULL33.設有數(shù)據(jù)集合：50，39，17，83，91，14，65)(1)依次取集合中各數(shù)據(jù)構造一棵二叉排序樹是下圖中的( )。（3分）(2)二叉排序樹的( )遍歷是有序序列。（2分）A.先序B.中序C.后序D.按層34.已知某帶權圖的鄰接矩陣如下所示： 0 6 1 6 0 5 1 5 0 5356455364 0 20 626 0從頂點1出發(fā)的廣度優(yōu)先搜索序列為( )。A.1,2,3,4,5,6B.1,4,3,2,6,5C.1,3,2,4,6,5D.1,2,4,3,5,635.以下函數(shù)在a0到an-l中，用折半查找算法查找關鍵字等于k的記錄，查找成功返回該記錄的下標，失敗時返回-l，完成程序中的空格選項。typedef structint key;NODE；Int Binary_Search(NODE a,int n,int k)int low,mid,hig