國家開放大學(xué)2021至2022年（202101-202207）《1252數(shù)據(jù)結(jié)構(gòu)（本）》期末考試真題及答案完整版（共4套）

試卷代號：1252國家開放大學(xué)2020年秋季學(xué)期期末統(tǒng)一考試

數(shù)據(jù)結(jié)構(gòu)（本）試題2021年1月一、單項選擇題（把合適的選項編號填寫在括號內(nèi)。每小題3分，共45分）在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（）oB.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)D.B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)D.線性結(jié)構(gòu)和非線性結(jié)構(gòu)C.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)）。下面程序段的時間復(fù)雜度是（for（i=l;i<=n；i++））。for（j=l；j<=n；j++）（c[i][j]=0；for（k=l；k<=n；k++）c[i][i]=c[i][j]+a[i][k]*b[k][i]：A.0（1） B.0（log2n）C.O（n） D.0（n3）在一個單鏈表中p指向結(jié)點a,q指向結(jié)點a的直接后繼結(jié)點b,要刪除結(jié)點b,可執(zhí)行（）oA.p->next=q->next B.p=q->nextC.p->next=q D.p->next=q設(shè)有一個長度為n的順序表，要在第i個元素之前（也就是插入元素作為新表的第i個元素），插入一個元素，則移動元素個數(shù)為（）。A.n-i B.n-i-1C.n-i+1 D.i一個隊列的人隊序列是1,2,3,4。則隊列的輸出序列是（）oA.4,3,2,1 B.1,2,3,4C.1,4, 3,2 D.3,2.4,1在一個棧頂指針為top的鏈棧中，將一個p指針?biāo)傅慕Y(jié)點人棧，應(yīng)執(zhí)行（）otop->next=pp->next=top->next;top->next=pp->next=top；top二pp->next=top->next,top=top->next判斷一個循環(huán)隊列Q(最多元素為m)為滿的條件是(Q->front==Q->rearQ->front!=Q->rearQ->front—(Q->rear+l)%mQ->front!=(Q->rear+l)%m求q在p中首次岀現(xiàn)的位置的算法稱為（設(shè)有兩個串p和q,其中q是p求q在p中首次岀現(xiàn)的位置的算法稱為（B.連接D.求串長B.連接D.求串長C.模式匹配一個非空廣義表的表頭()oA.不可能是原子 B.只能是子表C.只能是原子 D.可以是子表或原子樹中的結(jié)點數(shù)等于所有結(jié)點的度數(shù)加（）。TOC\o"1-5"\h\zA.1 B.0C.2 D.-1在一棵二叉樹上，第5層的結(jié)點數(shù)最多為（）。A.8 R.15C.16 D.32在一個圖G中，所有頂點的度數(shù)之和等于所有邊數(shù)之和的（）倍。A.1/2 B.1C.2 D.4對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則所有頂點鄰接表中的結(jié)點總數(shù)為（）oA.n B.eC.2n D.2e有一個長度為12的有序表，按折半査找對該表進(jìn)行査找，在等概率情況下査找成功的平均比較次數(shù)為（）。A.37/12 B.39/12C.41/12 D.35/12從未排序序列中依次取出元素與己經(jīng)排好序的序列中的元素作比較。將其放人已排序序列的正確的位置上，此方法稱為（）oA.插入排序 B.交換排序C.選擇排序 D.歸并排序二、判斷題（根據(jù)敘述正確與否在奠后面的括號內(nèi)打?qū)μ枴盎虼虿嫣枴癤”。每小題2分，共30分）數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶根據(jù)應(yīng)用需要建立的。（）數(shù)據(jù)結(jié)構(gòu)中，元素之間存在多對多的關(guān)系稱為圖狀結(jié)構(gòu)。（）設(shè)有一個單向鏈表，結(jié)點的指針域為next,頭指針為head,p指向尾結(jié)點，為了使該單向鏈表改為単向循環(huán)鏈表，可用語句p->next=heado（）設(shè)有一個單向循環(huán)鏈表，結(jié)點的指針域為next,頭指針為head,指針p指向表中某結(jié)點，若邏輯表達(dá)式p->next=二head;的結(jié)果為真，貝ijp所指結(jié)點為尾結(jié)點。（）棧和隊列都是特殊的線性表，但它們對存取位置的限制不同。（）棧是限定在表的兩端進(jìn)行插入和刪除操作的線性表，又稱為先進(jìn)先岀表。（）遞歸定義的數(shù)據(jù)結(jié)構(gòu)通常用遞歸算法來實現(xiàn)對它的操作。（）-個空格的串的長度是0。（）

對稀疏矩陣進(jìn)行壓縮存儲，矩陣中每個非零元素對應(yīng)的三元組包括該元素的行號、列號和元素值三項信息。（）深度為k的完全二叉樹至少有個結(jié)點。（）完全二叉樹中沒有度為1的結(jié)點。（）圖的生成樹是惟一的。（）對連通圖進(jìn)行深度優(yōu)先遍歷可以訪問到該圖屮的所有頂點。（）在順序查找、折半查找、哈希表查找3種方法中，平均查找長度與結(jié)點個數(shù)n無關(guān)的査找方法是折半査找。（）n個元素進(jìn)行冒泡法排序，通常需要進(jìn)行n-1趟冒泡。（）三、綜合應(yīng)用及程序設(shè)計題（每小題5分，共25分）在下面空格處填寫一條語句，以使下面的鏈?zhǔn)疥犃腥吭爻鲫牭乃惴ㄍ暾?。intwrite（LinkQueue*q）（QueueNode*p；*隊空*隊空*/{printf（“隊空！無元素可取”）；exit（0）；}while（q->fronr->next!=NULL）/*岀隊*/（p=q->front-〉next；q->front->next=p->next/*岀隊*//*釋放己出隊結(jié)點/*釋放己出隊結(jié)點x//*隊空時，頭尾指針指向頭結(jié)點*/IB.q=q->nextD.p=p->nextB.q=q->nextD.p=p->nextC.q->rear=q->front以下程序是先序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分(樹結(jié)構(gòu)中左、右指針域分別為left和right,數(shù)據(jù)域data為字符型，BT指向根結(jié)點)。voidPreorder(structBTreeNode*BT)(if(BT!=NULL){ ;Preorder(BT->left)；Preorder(BT->right):))A.printf("％c",BT->left) B.printf("％c”.BT->right)Cprintf("％c",BT->data) D.printf("％d",BT->data)

一組記錄的關(guān)鍵字序列為（6,9,7,4,5,8）,利用堆排序（堆頂元素是最小元素）的方法建立初始堆是如下哪個圖？（）B.28,30,36,46,69,74D.B.28,30,36,46,69,74D.30,28.36,46,69,74經(jīng)過兩趟冒泡的結(jié)果序列為(A.36,28,30,46,69,74C,38,36,30,46,69,7435.設(shè)數(shù)據(jù)序列為：｛53,30,36,46,28,20,69,74D.28,36,30,46,69,7437,12,45,24,96)（1）將此序列用快速排序的方法，以第一個記錄為基準(zhǔn)得到的一趟劃分的結(jié)果為（）。（本小題3分）A.30,28.46,36,69,74C.28,30,46,36,69,74(2)用冒泡法對上述序列排序,)o(本小題2分)（1）從空二叉樹開始逐個插入該數(shù)據(jù)序列來形成二叉排序樹，若希望高度最小,應(yīng)該選擇的序列是（）o（本小題3分）A.45,24,53,12,37,96,30 B.37,24,12,30,53,40,9612,24,30,37.45,53,96 D.30,24,12,37,45,96,53（2）用鏈接地址法將該數(shù)據(jù)序列構(gòu)造哈希表，哈希函數(shù)為H（key）=keymod13,則散列地址為1的鏈中有（）個記錄。（本小題2分）A.0 B.1C.2 D.3

試卷代號：1252國家開放大學(xué)2021年春季學(xué)期期末統(tǒng)一考試數(shù)據(jù)結(jié)構(gòu)（本）試題2021年7月一、單項選擇題（把合適的選項編號填寫在括號內(nèi)。每小題3分，共45分）下面程序段的時間復(fù)雜度是（ ）ofor（i=l;i<=n;i++）for（j=l;j<=n;j++）{c[i][j]=0;for（k=l;k<=n;k++）c[i][j]=c[i][j]+a[i][k]*b[k][j];}O⑴ B.O（log2n）C.O（n） D.O（n3）數(shù)據(jù)的存儲結(jié)構(gòu)包括數(shù)據(jù)元素的表示和（）。數(shù)據(jù)處理的方法 B.相關(guān)算法C.數(shù)據(jù)元素的類型 D.數(shù)據(jù)元素間的關(guān)系的表示在一個單鏈表中p所指結(jié)點之后插入一個s所指的結(jié)點時，可執(zhí)行（）。p->next=s;s->next=p->nextp->next=s~>nextp=s->nexts->next=p->next;p->next=s在一個單鏈表中，p、q分別指向表中兩個相鄰的結(jié)點，且q所指結(jié)點是p所指結(jié)點的直接后繼，現(xiàn)要刪除q所指結(jié)點，可用語句（）oA.p=q->next B.p->next=qC.p->next=q->next D.q->next=NULL若讓元素1,2,3依次進(jìn)棧，則出棧順序不可能為（）。B.2,1,3D.B.2,1,3D.1,3,2C.3,1,2

表達(dá)式a*（b+c）-d的后綴表達(dá)式是（ ）oA.abcd*+- B.abc+*d~C.abc*++d- D.-+*abcd)o判斷順序棧s滿（元素個數(shù)最多n個）的條件是（)oR.s->tnp!=OD.s->top!=n-lA.s->t.op==0R.s->tnp!=OD.s->top!=n-ls~>top==n~l8.串的長度是指(A.串中所含不同字母的個數(shù)A.串中所含不同字母的個數(shù)C.串中所含不同字符的個數(shù)串中所含字符的個數(shù)D.串中所含非空格字符的個數(shù)廣義表的(a,(d,a,b),h,(e,((i,j),k)))深度是(TOC\o"1-5"\h\zA.6 B.10C.8 D.4在一棵二叉樹中，若編號為8的結(jié)點存在右孩子，則右孩子的順序編號為（）。A.18 B.16C,15 D.17在一棵二叉樹上，第5層的結(jié)點數(shù)最多為（B.15B.15D.3216-個具有n個頂點的無向完全圖包含（）條邊。A.n（n-l） B.n（n+l）C.n（n-l）/2 D.n（n+l）/213.對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則所有頂點鄰接表中的結(jié)點總數(shù)為（）oB.eD.2eB.eD.2eC.2n對于一個線性表，若要求既能進(jìn)行較快地插入和刪除，又要求存儲結(jié)構(gòu)能夠反映數(shù)據(jù)元素之間的邏輯關(guān)系，則應(yīng)該（）。A.以順序存儲方式A.以順序存儲方式以鏈接存儲方式C.以索引存儲方式C.以索引存儲方式以散列存儲方式從未排序序列中挑選元素，并將其放人已排序序列的一端，此方法稱為()。A.插入排序 B.交換排序C.選擇排序 D.歸并排序二、 判斷題(根據(jù)敘述正確與否在其后面的括號內(nèi)打?qū)μ柣虼虿嫣枴癤”。每小題2分，共30分)TOC\o"1-5"\h\z數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。 (通?？梢园岩槐竞胁煌鹿?jié)的書的目錄結(jié)構(gòu)抽象成線性結(jié)構(gòu)。(要在一個單向鏈表中刪除p所指向的結(jié)點，已知q指向P所指結(jié)點的直接前驅(qū)結(jié)點，若鏈表中結(jié)點的指針域為next,則可執(zhí)行q->next=p->nexto (要在一個帶頭結(jié)點的單向循環(huán)鏈表中刪除頭結(jié)點，得到一個新的不帶頭結(jié)卒的單向循環(huán)鏈表，若結(jié)點的指針域為next,頭指針為head,尾指針為p,則可執(zhí)行head=head->next;p->next=head;o (若讓元素1,2,3依次進(jìn)棧，則出棧次序1,3,2是不可能出現(xiàn)的情況。(遞歸定義的數(shù)據(jù)結(jié)構(gòu)通常用遞歸算法來實現(xiàn)對它的操作。 (隊列的特性是先進(jìn)后岀。 (用字符數(shù)組存儲長度為n的字符串，數(shù)組長度至少為n+1。 (-個廣義表的表頭總是一個廣義表。 (若樹的度為2時，該樹為二叉樹。 (深度為5的二叉樹最多有31個結(jié)點。 (存儲圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點個數(shù)有關(guān)，而且與圖的邊數(shù)也有關(guān)。 (圖的深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列不是惟一的。 (理想情況下，哈希表查找等概率查找成功的時間復(fù)雜度是0(1)。(n個元素進(jìn)行冒泡法排序，通常第j趟冒泡要進(jìn)行n-j次元素間的比較。(三、 綜合應(yīng)用及程序設(shè)計題(每小題5分，共25分)設(shè)線性表以不帶頭結(jié)點的單向鏈表存儲，鏈表頭指針為head。以下程序的功能是輸出鏈表中各結(jié)點中的數(shù)據(jù)域data,完成程序中空格部分。ndefineNULL0Voidmain(){NODE*head,*p;p二head;/*p為工作指針*/do(printf("%d\n",p->data); )while( @ );

①（3分）B.p=head~>nextD.head=head->nextB.p!二B.p=head~>nextD.head=head->nextB.p!二NULLD.p==headC.p=p->next②(2分)A.p=NULLC.p!=head寫出下列程序執(zhí)行后的結(jié)果SeqQueueQ;InitQueue(Q);inta[4]={5,8,12,15);for(inti—0;i<4;i++)InQueue(Q,a[i]);InQueue(Q,OutQueuc(Q》；InQueue(Q,30);InQueue(Q,OutQueue(Q)+10);while(IQueueEmpty(QjprintfOutQueue(Q》;執(zhí)行后的輸出結(jié)果為:oA.58121530 B.121553018D.121551830C.812153018D.12155183033.設(shè)查找表為:序號12345678序列412181937556577（1）畫岀對上述查找表進(jìn)行折半查找所對應(yīng)的判定樹是（）。（3分））次比較。）次比較。（2分）（2）用折半查找在該查找表成功查找到元素55需要經(jīng)過（A.1A.1試卷代號：試卷代號：1252⑵⑵B.或1（本小題2分）C.3D.434.順序查找算法如下，完成程序中空格部分。Intsearch(NODEa[],intn,intk)/*在a[0],a[l]...a[n-1]中查找關(guān)鍵字等于k的記錄，査找成功返回記錄的下標(biāo)，失敗時返回T*/（inti=0;while（i<n&&a[i].key!=k） ①if（ ② ）returni;elsereturn-1,}（2分）A.k++;C.n++;（3分）A.a[i].key==nC.a[n],key=kB.i++;D.a++:B.a[i].key==kD.a[n].key==i35.設(shè)數(shù)據(jù)序列為:{53,30,37,12,45,24,96）從空二叉樹開始逐個插入該數(shù)據(jù)序列來形成二叉排序樹，若希望高度最小，應(yīng)該選擇的序列是()。(3分)A.45,24,53,12,37,96,30 B.37,24,12,30,53,45,96C.12,24,30,37,45,53,96 D.30,24,12,37,45,96,53用鏈接地址法將該數(shù)據(jù)序列構(gòu)造哈希表，哈希函數(shù)為H(key)=keymodl3.則散列地址為1的鏈中有(A.0C.2)個記錄。(2分)B.1D.3國家開放大學(xué)2020年秋季學(xué)期期末統(tǒng)一考試數(shù)據(jù)結(jié)構(gòu)（本）口試題答案及評分標(biāo)準(zhǔn)（供參考）2021年1月一、單項選擇題（每小題3分，共45分）1.D2.D3.A4.C5.B6.C7.C8.C9.D10.A11.C12.C13.D14.A15.A二、判斷題（每小題2分，共30分）16.<17.<18.419.寸20.V21.x22.y/23.x24.V25.x26.x27.x28.q29.x30.a/三、綜合應(yīng)用及程序設(shè)計題（每小題5分，共25分）C.或q->rear=q->frontC.或printf（"％c”,BT->data）C.（1）D.或30,28,36,46,69,74（本小題3分）（2）A.或36,28,30,46,69,74（本小題2分）（1）B或37,24,30,53,45,96（本小題3分）試卷代號：1252國家開放大學(xué)2021年春季學(xué)期期末統(tǒng)一考試數(shù)據(jù)結(jié)構(gòu)（本）試題答案及評分標(biāo)準(zhǔn)（供參考）2021年7月一、單項選擇題（毎小題3分，共45分）1.D2.D3.D4.C5.C6.B7.C8.B9.D10.D11.C12.C13.D14.B15.C二、判斷題（毎小題2分，共30分）16J17.x18.419J20.x21.?22.x23.424.x25.x26.V27.x28J29.V30.寸三■綜合應(yīng)用及程序設(shè)計題（毎小題5分，共25分）①C.或p=p->next（3分）②B.或p!=NULL（2分）B.或121553018（1）D.⑵B.或2①B.或i++;（2分）②B.或a[i].key==k（3分）⑴B.或37,24,12,30,53,45,96（3分）（2）B.或1（2分）試卷代號：試卷代號：1252試卷代號：試卷代號：1252國家開放大學(xué)2021年秋季學(xué)期期末統(tǒng)一考試

數(shù)據(jù)結(jié)構(gòu)（本）試題2022年1月一、單項選擇題（把合適的選項編號填寫在括號內(nèi)。每小題3分，共45分）下列說法中，不正確的是（ ）。數(shù)據(jù)元素是數(shù)據(jù)的基本單位數(shù)據(jù)項是數(shù)據(jù)中不可分割的最小可標(biāo)識單位數(shù)據(jù)可有若干個數(shù)據(jù)元素構(gòu)成數(shù)據(jù)項可由若干個數(shù)據(jù)元素構(gòu)成'每個存儲結(jié)點不僅含有一個數(shù)據(jù)元素，還包含一組指針，該存儲方式是（ ）存儲方式。A.順序 B.鏈接C.索引 D.散列在一個單鏈表中p指向結(jié)點a,q指向結(jié)點a的直接后繼結(jié)點b,要刪除結(jié)點b,可執(zhí)行（）oA.p->next=q->next B.p=q->nextC.p->next=q D.p->next=q在一個單鏈表中p所指結(jié)點之后插入一個s所指的結(jié)點時，可執(zhí)行（p->next=s;s->next=p->nextp->next=s->nextp=s~>nexts->next=p->next,p->next=s向順序棧中壓入新元素時，應(yīng)當(dāng)（A.先移動棧頂指針，再存入元素C.先后次序無關(guān)緊要)<.）。B.先存入元素，再移動棧頂指針D,同時進(jìn)行—般情況下，將遞歸算法轉(zhuǎn)換成等價的非遞歸算法應(yīng)該設(shè)置（A.棧 B.隊列C,堆棧或隊列 D,數(shù)組判斷一個循環(huán)隊列Q（最多元素為m）為滿的條件是（ ）。Q->front==Q->rearQ->front!=Q->rearQ->front==（Q->rear+l）%mQ->front!=（Q->rear+l）%m空串與空格串（ ）oA.相同C.可能相同廣義表（f,h,（a,b,d,c）,dA.6C.8二叉樹第k層上最多有（ ）個結(jié)點。A.2kC.2k-l樹中的結(jié)點數(shù)等于所有結(jié)點的度數(shù)加（e.((i,B.不相同D,無法確定j）,k））的長度是（B.10D.4)oB.2k-'D.2k-l)oTOC\o"1-5"\h\z1 B.OC.2 D.-1對于具有n個頂點的圖，若采用鄰接矩陣表示，則該矩陣的大小為（ ）。n B.n2C.n~l D.（n~l）2對于一個具有n個頂點和。條邊的無向圖，若采用鄰接表表示，則所有頂點鄰接表中的結(jié)點總數(shù)為（ ）。n B.eC.2n D.2e釆用折半査找方法査找長度為n的線性表時，其算法的時間復(fù)雜度為（ ）。0（n2） B.0（nlog2n）C.O（n） D.0（log2n）從未排序序列中依次取出元素與己經(jīng)排好序的序列中的元素作比較。將其放人己排序序列的正確的位置上，此方法稱為（ ）。A.插入排序 B.交換排序C.選擇排序 D.歸并排序二、 判斷題（根據(jù)敘述正確與否在其后面的括號內(nèi)打?qū)μ柣虼虿嫣枴癤”。每小題2分,共30分）TOC\o"1-5"\h\z數(shù)據(jù)元素可以有一個或多個數(shù)據(jù)項組成。（ ）數(shù)據(jù)結(jié)構(gòu)中，元素之間存在多對多的關(guān)系稱為圖狀結(jié)構(gòu)。（ ）設(shè)有一個單向鏈表，結(jié)點的指針域為next,頭指針為head,p指向尾結(jié)點，為了使該單向鏈表改為單向循環(huán)鏈表，可用語句p->next=heado（ ）設(shè)有一個單向循環(huán)鏈表，結(jié)點的指針域為nexl,頭指針為head，指針p指向表中某結(jié)點，若邏輯表達(dá)式p->next=head;的結(jié)果為真，則p所指結(jié)點為尾結(jié)點。（ ）循環(huán)隊列隊頭指針在隊尾指針前一個位置，隊列是“滿”狀態(tài)。（ ）棧是限定在表的兩端進(jìn)行插入和刪除操作的線性表，又稱為先進(jìn)先出表。（ ）向一個棧頂指針為h的鏈棧（結(jié)點的指針域為next）中插入一個s所指結(jié)點時，先執(zhí)行s->next=h,再執(zhí)行h=s操作。（ ）串的兩種最基本的存儲方式是順序和鏈接。（ ）對稀疏矩陣進(jìn)行壓縮存儲，矩陣中每個非零元素對應(yīng)的三元組包括該元素的行號、列號和元素值三項信息。（ ）深度為k的完全二叉樹至少有2」1個結(jié)點。（ ）如果結(jié)點A有3個兄弟，而且B是A的雙親，則B的度是4。（ ）用鄰接矩陣存儲圖的時候，占用空間大小不但與圖的結(jié)點個數(shù)有關(guān)還與圖的邊數(shù)有關(guān)。（ ）對連通圖進(jìn)行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點。（ ）-叉排序樹在呈單支二叉樹時，査找效率最低。（ ）冒泡排序是一種比較簡單的插入排序方法。（ ）三、 綜合應(yīng)用及程序設(shè)計題（每小題5分，共25分）設(shè)有一個頭指針為head的不帶頭結(jié)點單向鏈表中（結(jié)點類型為NODE）,p為指向鏈表中某個結(jié)點的指針。以下程序段為插入一個指針為s的結(jié)點，使它成為p結(jié)點的直接驅(qū),請選擇其中空格的選項。NODE*q；

q=head：while(q->next!=p)①：s->next=p；②；B.Q=q->nextD.head=head-〉nextB.p->next=sB.Q=q->nextD.head=head-〉nextB.p->next=sD.q->next=p完成程序中空格部分。A.D=p->nextC.s=s->next(2分)A.p->next=qC.q->next=s以下為求二叉樹深度的算法,intBTreeDepth(BTreeNode*BT){if(BT==NULL)return0：else{(intdepl=BTreeDepth(BT->left):/*計算左子樹的深度*/Intdep2=BTreeDepth(BT->right):/*計算右子樹的深度*/if( )returndepl+1；elsereturndep2+!；A.depl>dep2 B.depl<dep2C.BT—>left==NULL D.BT->right==NULL設(shè)有數(shù)據(jù)集合：{50,39,17,83,91,14,65)(1)依次取集合中各數(shù)據(jù)構(gòu)造一棵二叉排序樹是下圖中的( )?(3分)）遍歷是有序序列。（2分）（2）二叉排序樹的（A.先序B.中序）遍歷是有序序列。（2分）（2）二叉排序樹的（A.先序B.中序C.后序D.按層已知某帶權(quán)圖的鄰接矩陣如下所示:g84260g84260836806585082150564605838061588從頂點1出發(fā)的廣度優(yōu)先搜索序列為（ ）oA.1,2,3,4,5,6 B.1,4,3,2,6,5C.1,3,2,4,6,5 D.1,2,4,3,5,6以下函數(shù)在a[0]到a[n-l]中，用折半查找算法查找關(guān)鍵字等于k的記錄，查找成功返回該記錄的下標(biāo)，失敗時返回T,完成程序中的空格選項。typedefstruct{intkey; )NODE；IntBinary_Search(NODEa[],intn,intk){intlow,mid,high;low=0;high=n-l;while( Q )(mid=( ② )if(a[mid].key==k)returnmid;elseif(a[mid].key<k)low=mid+l,elsehigh=mid-l,return-1(3分)A.a[mid].key==ka[mid].key<k(3分)A.a[mid].key==ka[mid].key<k(2分)A.(low+high)/2mid-1a[mid].key>kD.low<=highmid+1D.low+high試卷代號：1252國家開放大學(xué)2022試卷代號：12522022年7月一、單項選擇題（把合適的選項編號填寫在括號內(nèi)。每小題3分，共45分）線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形結(jié)構(gòu)都是按數(shù)據(jù)的（ ）來分類的。A.存儲結(jié)構(gòu) B.物理和存儲結(jié)構(gòu)C.物理結(jié)構(gòu) D.邏輯結(jié)構(gòu)在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ ）。A.動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) D.線性結(jié)構(gòu)和非線性結(jié)構(gòu)設(shè)有一個長度為n的順序表，要刪除第i個元素，則需移動元素的個數(shù)為（ ）。A.i B.n-i-1C.n~i D.n~i+l設(shè)有一個長度為10的順序表，要在第3個元素之后插入一個元素，則需移動元素的個數(shù)為（）。TOC\o"1-5"\h\zA.3 B.6C.7 D.8-個隊列的入隊序列是10,20,30,40o則隊列的輸出序列是（ ）＜＞A.40,30,20,10C.10,40,30,20A.40,30,20,10C.10,40,30,20在一棵二叉樹中（其根結(jié)點編號為1）,序編號為（）。A.18C.15隊列的出隊操作在（ ）進(jìn)行。A.隊頭C.任意位置串函數(shù)index（a,b）的功能是進(jìn)行（ ）。A.求子串C.模式匹配一個非空廣義表的表頭元素（ ）＜,A.不可能是原子C.只能是原子鏈表所具備的特點之一是（ ）。A.可以隨機(jī)訪問任一結(jié)點C.插入元素的操作不需要移動元素11.樹中所有結(jié)點數(shù)等于所有結(jié)點的度加（30,20,40,10若編號為8的結(jié)點存在右孩子，則該右孩子的順1617B.隊尾D.指定位置B.串連接D.求串長B.只能是子表D.可以是子表或原子B.需要占用連續(xù)的存儲空間D.刪除元素的操作需要移動元素）。TOC\o"1-5"\h\zA.1 B.02 D.-1在一個無向圖G中，所有邊數(shù)之和等于的所有頂點的度數(shù)之和（ ）倍。A.1/2 B.12 D.4對于一個具有4個頂點和5條邊的無向圖，若釆用鄰接表表示，則所有頂點鄰接表中的

TOC\o"1-5"\h\z結(jié)點總數(shù)為（ ）0A.4 B.5C.8 D.10有一個長度為5的線性表，按順序查找某關(guān)鍵字，在等概率情況下查找成功的平均比較次數(shù)為（ ）。A.2 B.2.5C.3 D.3.5假定一組記錄的排序碼為（46,79,56,38,40,80）,對其進(jìn)行歸并排序的過程中，第二趟歸并后的結(jié)果為（B.46979,38,56,40,80D.B.46979,38,56,40,80D.38,40,46,56,79,80C.38,46,56,79,40,80二、判斷題（根據(jù)敘述正確與否在其后面的括號內(nèi)打?qū)μ枴?或打叉號“X”。每小題2分，共30分）TOC\o"1-5"\h\z數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。（ ）數(shù)據(jù)結(jié)構(gòu)中，元素之間存在一對多的關(guān)系稱為圖狀結(jié)構(gòu)。（ ）設(shè)有一個單向鏈表，結(jié)點的指針域為next,頭指針為head,p指向尾結(jié)點，為了使該單向鏈表改為單向循環(huán)鏈表，可用語句p->next=heado（ ）線性表用關(guān)鍵字的順序方式存儲，可以用二分法査找。（ ）往棧中插入元素的操作方式是：先寫入元素，后移動棧頂指針。（ ）棧是限定在表的一端進(jìn)行插入和刪除操作的線性表，又稱為先進(jìn)后出表。（ ）遞歸定義的數(shù)據(jù)結(jié)構(gòu)通常用遞歸算法來實現(xiàn)對它的操作。（ ）串是一種特殊的線性表，其特殊性表現(xiàn)在組成串的數(shù)據(jù)元素都是字符。（ ）對稀疏矩陣進(jìn)行壓縮存儲，矩陣中每個非零元素對應(yīng)的三元組包括該元素的行號、列號和元素值三項信息。（ ）二叉樹只能釆用二叉鏈表來存儲。（ ）完全二叉樹中沒有度為1的結(jié)點。（ ）圖的生成樹是惟一的。（ ）對連通圖進(jìn)行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點。（ ）在有序順序存儲的線性表中查找一個元素，用折半査找速度一定比順序查找快。（對n個元素進(jìn)行冒泡法排序，最多需要進(jìn)行n-］趟冒泡。（ ）三、綜合應(yīng)用及程序設(shè)計題（每小題5分，共25分）在下面空格處填寫一條語句，以使下面的鏈?zhǔn)疥犃腥吭爻鲫牭乃惴ㄍ暾ntwrite（LinkQueue*q）{QueueNode*p；/*隊空/*隊空*/（printf（“隊空!無元素可取”）；exit（0）；/*出隊*//*釋放已出隊結(jié)點*/while(q->front->next!=NULL){p=q->front~>next；q->front->next=p->next;printf("%4d",p/*出隊*//*釋放已出隊結(jié)點*//*隊空時，頭尾指針指向頭結(jié)點*/程序中空格部分的選項為:B.q=q->next;D.p=p->next;A.q->front=q->rearB.q=q->next;D.p=p->next;C.q->rear=q->front;以下程序是先序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分(樹結(jié)構(gòu)中左、右指針域分別為left和right,數(shù)據(jù)域data為字符型，BT指向根結(jié)點)。VoidPreorder(structBTreeNode*BT)(if(BT!=NULL)( :Preorder(BT->left)；Preorder(BT->right):)}A.printf("％c”,BT->left) B.printf("％c”,BT->right)C.printf(c”,BT->data) D.printf("％d,BT->data)330-組記錄的關(guān)鍵字序列為(6,9,7,4,5,8