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

試卷代號(hào)：1252座位號(hào)□□國家開放大學(xué)2019年秋季學(xué)期期末統(tǒng)一考試數(shù)據(jù)結(jié)構(gòu)（本）試題2020年1月一、單項(xiàng)選擇題(每小題3分，共30分)1．以下說法不正確的是()。A．線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不必占用連續(xù)的存儲(chǔ)空間B．一種邏輯結(jié)構(gòu)只能有唯一的存儲(chǔ)結(jié)構(gòu)C.一種邏輯結(jié)構(gòu)可以有不同的存儲(chǔ)結(jié)構(gòu)D．線性表的順序存儲(chǔ)結(jié)構(gòu)必須占用連續(xù)的存儲(chǔ)空間2．單向鏈表所具備的特點(diǎn)之一是()。A．可以隨機(jī)訪問表中任一結(jié)點(diǎn)B．需要占用連續(xù)的存儲(chǔ)空間C．插入元素和刪除元素的操作不需要移動(dòng)元素D．可以通過指向某元素的指針操作，直接訪問到該結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)3．線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在()的關(guān)系。A．多對(duì)多B．一對(duì)多C．一對(duì)一D．每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼4．在一個(gè)單向鏈表中，p和q分別是指向結(jié)點(diǎn)類型的指針，要?jiǎng)h除p所指結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)，可執(zhí)行()。A.q=p->next;p->next=q->nextB．q=p;p=q->nextC.q-p->next;p->next=qD．q-p；p->next=q5．設(shè)有帶頭結(jié)點(diǎn)的且頭指針為head的非空的單向鏈表，指針p指向其尾結(jié)點(diǎn)，要使該單向鏈表成為不蒂頭結(jié)點(diǎn)的單向循環(huán)鏈表，則可利用下述語句：head=head->next;和()。A．p-headB.p=NULLC.p->next=headnhead=p6．元素20，14·160，180按順序依次進(jìn)棧，則該棧的不可能輸出序列是()。（進(jìn)棧出?？梢越惶孢M(jìn)行）。A.180,160,14,20 B.20,14,160,180C.180,160,20,14 D.14,20,180,1607．設(shè)有一個(gè)15階的對(duì)稱矩陣A(第一個(gè)元素為a1，1)，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣中元素a5，3在一維數(shù)組B中的下標(biāo)是()。A．11 B．13C．14 D．128．設(shè)一棵有n個(gè)葉結(jié)點(diǎn)的二叉樹，度數(shù)為1的結(jié)點(diǎn)有4個(gè)，則該樹共有()個(gè)結(jié)點(diǎn)。A．2n B．2n+3C．2n+2 D．2n+49．設(shè)根結(jié)點(diǎn)所在層為第一層，一棵具有5層的完全二叉樹，最后一層有6個(gè)結(jié)點(diǎn)，則該樹總共有()個(gè)結(jié)點(diǎn)。A．22 B．20C.21 D.1010．已知如圖l所示的一個(gè)圖，若從頂點(diǎn)a出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為()。圖1A．a(chǎn)becdfg B．a(chǎn)cfebdgC．a(chǎn)ebcfdg D．a(chǎn)edfcbg二、填空題（每小題2分，共24分）11．把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中，并具體體現(xiàn)數(shù)據(jù)元素間的邏輯關(guān)系稱為____結(jié)構(gòu)。12．設(shè)有一個(gè)長(zhǎng)度為22的順序表，要?jiǎng)h除第8個(gè)元素需移動(dòng)元素的個(gè)數(shù)為____。13．在一棵二叉樹中，若編號(hào)為i的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號(hào)為____。14．設(shè)一棵哈夫曼樹共有18個(gè)非葉結(jié)點(diǎn)，則該樹總共有____個(gè)結(jié)點(diǎn)。15．棧元素的進(jìn)、出棧次序是：后進(jìn)一。16．在對(duì)10個(gè)記錄的序列(8，36，19，78，4，10，53，45，27，68)進(jìn)行直接插入排序時(shí)，當(dāng)把第6個(gè)記錄10插入到有序表時(shí)，為尋找插入位置，元素間需比較____次。17．n個(gè)元素進(jìn)行冒泡法排序，通常需要進(jìn)行n-l趟冒泡，其中第j趟冒泡共需要進(jìn)行次元素間的比較。18．序列7，1，4，2，5，3，8，6用歸并法排序（升序），經(jīng)一次歸并后的結(jié)果序列是。19．中序遍歷一棵____樹可得到一個(gè)有序序列。20．廣義表(h，(b，a)．f，e，（（i，j)，k））的深度是____。21．____結(jié)構(gòu)中，數(shù)據(jù)元素間存在一對(duì)多的關(guān)系。22．字符串a(chǎn)l="beijing”，a2一“bef”，a3一“beifang”，a4一“befi”最小的是____。三、綜合題（每小題中每問6分，共30分）23．設(shè)查找表為序號(hào)1234567891011序列11162425436171839192123(1)畫出對(duì)上述查找表進(jìn)行折半查找所對(duì)應(yīng)的判定樹（樹中結(jié)點(diǎn)用下標(biāo)表示）。(2)說明不成功查找元素45需要經(jīng)過多少次比較？(3)求在等概率條件下，成功查找的平均比較次數(shù)？24．(1)一組記錄的關(guān)鍵字序列為(37，67,43，25，27，32)，給出利用堆排序（堆頂元素是最小元素）的方法建立的初始堆（要求以完全二叉樹描述）。(2)對(duì)關(guān)鍵字序列(40，73，49，31·33，77)采用快速排序，給出以第一個(gè)關(guān)鍵字為分割元素，經(jīng)過一次劃分后的結(jié)果。四、程序填空題（每空2分，共16分）25.以下函數(shù)在a[0]到a[n-l]中，用折半查找算法查找關(guān)鍵字等于k的記錄，查找成功返回該記錄的下標(biāo)，失敗時(shí)返回-l，完成程序中的空格。typedefstruct{intkey,……｝NODE;intBinary_Search(NODEa[],intn,intk){intlow,mid,high;low=0：(l)while(_low<=high){Mid=(2)if(a[mid].key==k)return(3)elseif(a[mid].key<k)low=mid+l;else(4)｝(5)｝26.以下程序是先序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）。voidPreorder(structBTreeNode*BT){if(BT!=NULL)((l)(2)Preorder(BT->right);)}利用上述程序?qū)ο聢D進(jìn)行遍歷，結(jié)果是(3)；圖2試卷代號(hào)：1252國家開放大學(xué)2020年春季學(xué)期期末統(tǒng)一考試數(shù)據(jù)結(jié)構(gòu)（本）試題2020年7月一.單項(xiàng)選擇題（每小題3分，共30分）1.設(shè)主串為“DBcCDABcdEFdBc”，以下模式串能與主串成功匹配的是（）。 A.dBc B.BCd C.DBC D.Abc2.順序表所具備的特點(diǎn)之一是（）。 A.可以隨機(jī)訪問任一結(jié)點(diǎn) B.不用占用連續(xù)的存儲(chǔ)空間 C.插入刪除操作不需要移動(dòng)元素 D.必須要有頭指針3.在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，p指向一個(gè)已生成的結(jié)點(diǎn)，現(xiàn)要為該結(jié)點(diǎn)的數(shù)據(jù)域賦值e，并使結(jié)點(diǎn)入隊(duì)的運(yùn)算為p->data=e;p->next一NULL;和（）。 A.f->next=p;f=p B.r->next=p;r=p C.p->next=r;r=p D.p->next=f;f=p4.在一個(gè)頭指針為head的帶頭結(jié)點(diǎn)的單向循環(huán)鏈表中，p指向尾結(jié)點(diǎn)，要使該鏈表成為不帶頭結(jié)點(diǎn)的單向鏈表，可執(zhí)行（）。 A.head=head->next;p=NULL B.head—head->next;P->next=head C.head->next=p->next D.head-head->next;p->next=NULL5。元素212，214，216，218按順序依次進(jìn)棧，則該棧的不可能輸出序列是（）（進(jìn)棧出?？梢越惶孢M(jìn)行）。 A.212,214,216,218 B.216,214,212,218 C.214,212,218,216 D.218,216,212,2146.設(shè)有一個(gè)25階的對(duì)稱矩陣A(第一個(gè)元素為ai，，，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中(數(shù)組下標(biāo)從1開始)，則矩陣中元素a4，s在一維數(shù)組B中的下標(biāo)是（）。 A.10 B.9 C.7 D.87.在一棵二叉樹中，編號(hào)為19的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的順序編號(hào)為（）。 A.9 B.8 C.34 D.358.線性表以（）方式存儲(chǔ)，能進(jìn)行折半查找。 A.關(guān)鍵字有序的 B.順序 C.鏈接 D.關(guān)鍵字有序的順序9.如圖1所示的一個(gè)圖，若從頂點(diǎn)a出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（）。 A.abecdfg B.aecbdfg C.aebcfdg D.aedfcbg10.設(shè)一棵哈夫曼樹共有31個(gè)結(jié)點(diǎn)，則該樹共有（）個(gè)非葉子結(jié)點(diǎn)。 A.14 B.15 C.16 D.17二、填空題（每小題2分，共24分）II.____結(jié)構(gòu)中，數(shù)據(jù)元素的位置之間存在多對(duì)多的關(guān)系。12.設(shè)有一個(gè)長(zhǎng)度為20的順序表，要插入一個(gè)元素，并作為第6個(gè)元素，需移動(dòng)元素的個(gè)數(shù)為____。13.數(shù)組a經(jīng)初始化chara[]一“fhglisp”；a[6]中存放的是________。14.序列4，2，15，13，18，16，采用冒泡排序算法，經(jīng)一趟冒泡后，序列的結(jié)果是。15.對(duì)19個(gè)元素的序列用冒泡排法進(jìn)行排序，通常第7趟冒泡中，共需要進(jìn)行次元素間的比較。16.對(duì)一組記錄(41，25，93，20，12，78，46，51，89)進(jìn)行直接插入排序（由小到大排序），當(dāng)把第7個(gè)記錄46插入有序表，為尋找插入位置需比較____次。17.設(shè)有一棵深度為5的完全二叉樹，第5層上有4個(gè)結(jié)點(diǎn)，該樹共有一個(gè)結(jié)點(diǎn)。（根所在結(jié)點(diǎn)為第1層）18.設(shè)有串pl=”DEADFG”，P2=”DEAFDF”，P3=”DEADFAB”P4=”DEAFE”，四個(gè)串中最大的是____。19.一棵有8個(gè)葉結(jié)點(diǎn)的哈夫曼樹，則該樹共有__個(gè)結(jié)點(diǎn)。20.____遍歷二叉排序樹可得到一個(gè)有序序列。21.廣義表(g，(a，b，d，c)，d，e，((i，j)，k》的長(zhǎng)度是____。22.在一個(gè)單向鏈表中，已知q指向p所指結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，現(xiàn)要?jiǎng)h除p所指結(jié)點(diǎn)，則可以用操作q->next=________。三、綜合題（每小題中每問6分，共30分） 23.(1)設(shè)有數(shù)據(jù)集合{50，39，17，83，111，14，65，13，91，102，49}，依次取集合中各數(shù)據(jù)構(gòu)造一棵二叉排序樹。 (2)-組記錄的關(guān)鍵字序列為(6，9，7，4，5，8)，利用堆排序（堆頂元素是最小元素）的方法建立初始堆。（要求用完全二叉樹表示） 24.(1)如下為一個(gè)長(zhǎng)度為10的有序表，給出按折半查找對(duì)該表進(jìn)行查找的判定樹。 (2)按折半查找對(duì)該表進(jìn)行查找，求在等概率情況下查找成功的平均比較次數(shù)。 (3)以1，2，3，6，7，8作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹。序號(hào)12345678910序列28356075798086909599四、程序填空題（每空2分，共16分） 25.設(shè)線性表以不帶頭結(jié)點(diǎn)的單向鏈表存儲(chǔ)，鏈表頭指針為head，以下程序的功能是：(1)輸出鏈表中各結(jié)點(diǎn)中的數(shù)據(jù)域data。(2)把該單向鏈表改為以p作為尾指針的單向循環(huán)鏈表。(鏈表中結(jié)點(diǎn)的指針域?yàn)閚ext，數(shù)據(jù)域?yàn)閐ata)。#defineNULL0voidmain（）{NODE*head，*p；p=head；/*p為工作指針*／do{printf(“%d\n”，(1))；(2)；｝while(p->next!=(（3）);printf(“%d\n”p->data);（（4））｝ 26.以下程序是后序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）。完成程序中空格部分。voidpostorder(structBTreeNode*BT){if((1))｛postorder(BT->left)；(2)(3)｝利用上述程序?qū)ο聢D所示二叉樹遍歷的結(jié)果為(4)試卷代號(hào)：1252國家開放大學(xué)2019年秋季學(xué)期期末統(tǒng)一考試數(shù)據(jù)結(jié)構(gòu)（本）試題答案及評(píng)分標(biāo)準(zhǔn)（供參考）2020年1月一、單項(xiàng)選擇題（每小題3分，共30分）1．B2．C3．C4．A5．C6．C7．B8．B9．C10．D二、填空題（每小題2分，共24分）11．存儲(chǔ)（物理）12.1413.2i+114.3715．先出16.417．n-j18.1,7,2.4,3,5.6,819．二叉排序樹20.321．樹形22．a(chǎn)2三、綜合題（每小題中每問6分，共30分）23．(1)(2)4次(3)平均查找長(zhǎng)度=(1+2*2+3*4+4*4)/11=324.(1)25,27,32,67.37.43(2)33，31,40,49,73,77四、程序填空題（每空2分，共16分）25.(1)high=n-1(2)low+high)/2(3)mid(4)high=mid-1(5)ret