年國(guó)家開(kāi)放大學(xué)電大數(shù)據(jù)結(jié)構(gòu)期末綜合考題及答案

年國(guó)家開(kāi)放大學(xué)電大數(shù)據(jù)結(jié)構(gòu)期末綜合考題及答案一、單項(xiàng)選擇題1.數(shù)據(jù)的物理結(jié)構(gòu)(D)。A.與數(shù)據(jù)的邏輯結(jié)構(gòu)無(wú)關(guān)B.僅僅包括數(shù)據(jù)元素的表示C.只包括數(shù)據(jù)元素間關(guān)系的D.包括數(shù)據(jù)元素的表示和關(guān)系的表示2.數(shù)據(jù)元素是數(shù)據(jù)A.只能有一個(gè)數(shù)據(jù)項(xiàng)組成B.至少有二個(gè)數(shù)據(jù)項(xiàng)組成C.可以是一個(gè)數(shù)據(jù)項(xiàng)也可以由若干個(gè)數(shù)據(jù)項(xiàng)組成D.至少有一個(gè)數(shù)據(jù)項(xiàng)為指針類型3.從nA.基本操作是數(shù)據(jù)元素間的交換B.算法的時(shí)間復(fù)雜度是O(n2)C.算法的時(shí)間復(fù)雜度是D.需要進(jìn)行(n+1)次數(shù)據(jù)元素間的比較4.線性表的順序結(jié)oA.邏輯上相鄰的元素在物理位置上不一定相鄰B.數(shù)據(jù)元素是不能隨機(jī)訪問(wèn)的C.邏輯上相鄰的元素在物理位置上也相鄰D.進(jìn)行數(shù)據(jù)元素的插入、刪除效率較高5.以下表中可以隨機(jī)A.單向鏈表B.雙向鏈表D.順序表6.帶頭結(jié)點(diǎn)的單向鏈表為空的判斷條件是(B)(設(shè)頭指針為head)。D.n-i8.線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在(A)的關(guān)A.x=top-data;top=toD.top-next=top;x=top-data;10.設(shè)順序存儲(chǔ)的線性表長(zhǎng)度為n,要?jiǎng)h除第i個(gè)元素，按課本的算法，當(dāng)i=(C)時(shí)，D.411.以下說(shuō)法正確的是(CC.棧的刪除和插入操作都只能在棧頂進(jìn)行B.棧的特點(diǎn)是D.隊(duì)列的刪除和插入操作都只能在隊(duì)頭進(jìn)行12以下說(shuō)法在隊(duì)頭進(jìn)行13.串函數(shù)StrCmp(“abA”,”aba”的值為(D)。C.“abAaba”D.dcba15.設(shè)有一個(gè)12階的對(duì)稱矩陣A,采用壓縮存儲(chǔ)A的第一個(gè)元素為a1,1,數(shù)組b的下標(biāo)從1開(kāi)始),則矩陣A中第4行的元素在數(shù)組b中的下標(biāo)i一定有(A)。D.m/217.設(shè)有一個(gè)帶頭結(jié)點(diǎn)的鏈隊(duì)列，隊(duì)列中每個(gè)結(jié)點(diǎn)鏈隊(duì)列的頭指針和尾指針，要執(zhí)行出隊(duì)操作，用x保存出隊(duì)元A.連通圖G一定存在生成樹(shù)B.連通圖G的生成樹(shù)中一定包含G的所有頂點(diǎn)C.連通圖G的生成樹(shù)中不一定包含G的所有邊D.連通圖G的生成樹(shù)可以是不連通的19.散列查找的原A.在待查記錄的關(guān)鍵字值與該記錄的存儲(chǔ)位置之間建立確定的對(duì)應(yīng)關(guān)系B.按待查記錄的關(guān)鍵字有序的順序方C.按關(guān)鍵字值的比較進(jìn)行查找D.基于二分查找的方法20.空串的長(zhǎng)度為(A)。D.321.排序過(guò)程中，每一趟從無(wú)序子表中將一個(gè)待排序的記錄按其關(guān)鍵字的大小放置到已經(jīng)排好序的子序列的適當(dāng)位置，直到全部排好序?yàn)橹?，該排序算法是D)。A.選擇排序B.快速排序C.冒泡排序D.直接插入排序22.采用順序查找法對(duì)長(zhǎng)度為n的線性表進(jìn)行查找(不采用表尾設(shè)監(jiān)視哨的方法),最壞的情況下要進(jìn)行(B)次元素間D.n/223.設(shè)有一個(gè)10階的對(duì)稱矩陣A,采用壓縮存儲(chǔ)A的第一個(gè)元素為a1,1,數(shù)組b的下標(biāo)從1開(kāi)始),則矩陣元素a5,3對(duì)應(yīng)一維數(shù)組b的數(shù)組元素是(C)。D.b24.如圖1若從頂點(diǎn)a出發(fā)按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的頂點(diǎn)序列為(D)。A.acebdfghB.aebcghdfC.aedfbcghD.abecdfgh圖125.已知如圖2所示的一個(gè)圖，若從頂點(diǎn)a出發(fā)，按A.abecdf圖226.一棵哈夫曼樹(shù)總共有23個(gè)結(jié)點(diǎn)，該樹(shù)共有(D)個(gè)葉結(jié)點(diǎn)(終端結(jié)點(diǎn))。2.通?？梢园涯吵鞘兄懈鞴徽军c(diǎn)間的線路圖抽象成_圖狀 3.設(shè)有一個(gè)單向鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext,頭指針為用語(yǔ)句_p-next=head_。4.設(shè)有一個(gè)單向循環(huán)鏈表，頭指針為head,鏈表中結(jié)點(diǎn)的指針域?yàn)閚ext,p指向尾結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，若要?jiǎng)h除尾結(jié)點(diǎn)，得到一個(gè)新的單向循環(huán)鏈表，可執(zhí)行操作_p-next=head。5.循環(huán)隊(duì)列的隊(duì)頭指針為f,隊(duì)尾指針為r,當(dāng)r=f_時(shí)表明隊(duì)列已空。6.在一個(gè)鏈隊(duì)中，f和r分別為隊(duì)頭和隊(duì)尾指針，隊(duì)結(jié)點(diǎn)的指針域?yàn)閚ext,則插入一個(gè)s所指結(jié)點(diǎn)的操作為_(kāi)r-next=s_;r=s;7.設(shè)有一個(gè)鏈棧，棧頂指針為hs,現(xiàn)有一個(gè)s所指向的結(jié)點(diǎn)要入棧，則可執(zhí)行操作_s-next=hs;和hs=s;8.循環(huán)隊(duì)列的隊(duì)頭指針為f,隊(duì)尾指針為r,當(dāng) r==f時(shí)表明隊(duì)列為空。9.在一個(gè)鏈隊(duì)中，f和r分別為隊(duì)頭和隊(duì)尾指針，隊(duì)結(jié)點(diǎn)的指針域?yàn)閚ext,則插入一個(gè)s所指結(jié)點(diǎn)的操作為r-next=s;11.串的兩種最基本的存儲(chǔ)方式分別是_順序存儲(chǔ)和鏈12.一棵二叉樹(shù)沒(méi)有單分支結(jié)點(diǎn)，有6個(gè)葉結(jié)點(diǎn)，則該樹(shù)13.一棵二叉樹(shù)中順序編號(hào)為i的結(jié)點(diǎn)，若它存在左、右孩子，則左、右孩子編號(hào)分別為_(kāi)2i 14.按照二叉樹(shù)的遞歸定義，對(duì)二叉樹(shù)遍歷的常用算法有-15.兩個(gè)串相等的充分必要條件是--串長(zhǎng)度相等且對(duì)應(yīng)位置16.把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中，并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為物理存儲(chǔ)結(jié)構(gòu)。17.一棵二叉樹(shù)葉結(jié)點(diǎn)(終端結(jié)點(diǎn))數(shù)為5,單分支結(jié)點(diǎn)數(shù)為2,該樹(shù)共有_11_個(gè)結(jié)點(diǎn)。18.如圖3所示的二叉樹(shù)，其后序遍歷序列為19.根據(jù)搜索方法的不同，圖的遍歷有_深度優(yōu)先搜索遍歷20.二叉樹(shù)為二叉排序的充分必要條件是其任一結(jié)點(diǎn)的值均21.一個(gè)有序表{3,4,10,14,34,43,46,64,75,78,90,96,130}用折半查找法查找值為90的結(jié)點(diǎn)，經(jīng)4次比較后4(1)設(shè)有查找表{5,14,2,6,18,7,4,1依次取表中數(shù)據(jù)，構(gòu)造一棵二叉排序樹(shù).(2)說(shuō)明如何通過(guò)序列的二叉排序樹(shù)得到相中序遍歷5.(1)利用篩選過(guò)程把序列{42,82,67,102,16,32,57,52}建成堆(小根堆),畫(huà)出相應(yīng)的完全二叉樹(shù)(不(2)寫(xiě)出對(duì)上述堆對(duì)應(yīng)的完全二叉樹(shù)進(jìn)行中序遍歷得到的序列四、程序填空題1.以下函數(shù)在a到a[n-1]中，用折半查找算法查找關(guān)鍵字等于k的記錄，查找成功返回該記錄的下失敗時(shí)返回-1,完成程序中的空格typedefkey;....}NODE;intBinary_Search(NODEa[],intn,intk) 」2x是要進(jìn)棧的結(jié)點(diǎn)的數(shù)據(jù) ; }3x為voidInQueue(ElemTy ; ; 三、綜合應(yīng)用題(每小題010分，共030分)4282675257321610216423252576初始樹(shù)堆1.(1)low=high(2)mid(3)a[2.(1)low=high(2)mid(3)a[mid].keyk;(4)high=mi3.(1)sizeof(structnode)(2)p-next=top(3)top=p4.(1)malloc(sizeof(structnode))(2)rear-next=p(3)p期末綜合練習(xí)二二一、單項(xiàng)選擇題1.(CD.數(shù)據(jù)項(xiàng)2.同一種邏輯結(jié)構(gòu)(A.只能有唯一的存儲(chǔ)結(jié)構(gòu)B.可以有不同的存儲(chǔ)結(jié)構(gòu)C.只能表示某一種數(shù)據(jù)元素之間的關(guān)系D.以上三種說(shuō)法均不正確3.設(shè)鏈表中的結(jié)點(diǎn)是NODE類型的結(jié)構(gòu)體變量，且有NODE*p;為了申請(qǐng)一個(gè)新結(jié)點(diǎn)，并由p指向該結(jié)點(diǎn)，可用以下語(yǔ)句(Ap=(Bp=(*NODE)malloc(sizeof(NODE));C.p=(NODE)malloc(sizeof(p));D.p=(NODE*4.鏈表所具備的特點(diǎn)是(A.可以隨機(jī)訪問(wèn)任一結(jié)點(diǎn)B.占用連續(xù)的存儲(chǔ)空間C.插入刪除元D.可以通過(guò)下標(biāo)對(duì)鏈表進(jìn)行直接訪問(wèn)5.設(shè)順序存儲(chǔ)的線性長(zhǎng)度為n,要在第i個(gè)元素之前插入一個(gè)新元素，按課本的算點(diǎn)，可用的語(yǔ)句是(m,則m一定不可能是(A.x=top-data;top=toD.top=top-next;x=data;19.以下說(shuō)法正確的是(A.連通圖G的生成樹(shù)中可以包含回路B.連通圖G的生成樹(shù)可以是不連通的C.連通圖G的生成樹(shù)一定是唯一的D.連通圖G的生成樹(shù)一定是連通而不包含回路的20.在一個(gè)的運(yùn)算為(n-1趟冒泡，在第j趟冒泡中共要進(jìn)行()次元素間的比較。D.n-j-122.一個(gè)棧的進(jìn)棧序列是a,b,c,d不可能輸出序列是()(進(jìn)棧出棧可以交替進(jìn)行)。24.有一個(gè)長(zhǎng)度為10的有序表，按折半查找對(duì)該表進(jìn)行查D.31/1025.如圖1若從頂點(diǎn)a出發(fā)按深度優(yōu)先搜索法進(jìn)A.aebcfdB.abedcfC.acebdfD.acfbdeD.4129.數(shù)據(jù)的()結(jié)構(gòu)與所使用的計(jì)算機(jī)無(wú)關(guān)。A.邏輯B.物理D.邏輯與存儲(chǔ)30.在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的(二、填空題1.通常可以把一本含有不同章節(jié)的書(shū)的目錄結(jié) 3.要在一個(gè)單向鏈表中p所指向的結(jié)點(diǎn)之后插入一個(gè)s這樣做正確嗎?若正確則回答正確，若不正確則說(shuō)明應(yīng)如何(1)以2,3,4,7,8,9作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹(shù)(要求每個(gè)結(jié)點(diǎn)的左子樹(shù)根結(jié)點(diǎn)的權(quán)小于等于右子樹(shù)根結(jié)點(diǎn)的權(quán)),給出相應(yīng)權(quán)重值葉結(jié)點(diǎn)的哈夫曼編碼。(2)一棵哈夫曼樹(shù)有n個(gè)葉結(jié)點(diǎn)，它一共有述理由?3.(1)畫(huà)出對(duì)長(zhǎng)度為10的有序表進(jìn)行折半查找的判定樹(shù)(以序號(hào)1,2,……10表示樹(shù)結(jié)點(diǎn))(2)對(duì)上述序列進(jìn)行折半查找，求等概率條件下，成功查4.一組記錄的關(guān)鍵字序列為(46,79,56,38,40,84)(1)利用快速排序的方法，給出以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果(給出逐次交換元素的過(guò)程，要求以升序排列)(2)對(duì)上述序列用堆排序的方法建立大根堆，要求以二叉5.(1)利用篩選法，把序列{37,77,62,97,11,27,52,,畫(huà)出相應(yīng)的完全二叉樹(shù)(2)寫(xiě)出對(duì)上述堆所對(duì)應(yīng)的二叉樹(shù)進(jìn)行前序遍歷得到的序列6.設(shè)查找表為(50,60,75,85,96,98,105,110,120,130)(1)說(shuō)出進(jìn)行折半查找成功查找到元素120需要進(jìn)行多少次元素間的比較?(2)為了折半查找元素95,經(jīng)過(guò)多少次元素間的比較才能確定不能查到?(3)畫(huà)出對(duì)上述有序表進(jìn)行折半NODEtemp;{; ;}2以下是用尾插法建立帶頭結(jié)點(diǎn)且有n個(gè)結(jié)點(diǎn)的單向鏈表的程序，結(jié)點(diǎn)中的數(shù)據(jù)域從前向后依次為1,2,3......,n完成程序NODE*create(n){NODE*head,*p,*q;p=(NODE*)malloc(sizeof(NODE));hea;pnext=NULL;/*建立頭結(jié)點(diǎn)pnext=NULL;2:11103:111141107:008:019:1046,79,56,38,40,8440,79,56,38,40,856,38,79,8440,38,56,38,7952849631071235679384084)個(gè)字節(jié)。數(shù)之和為(4.串函數(shù)StrCat(a,b)的功能是進(jìn)行串(D.連接5.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù))結(jié)構(gòu)。C.邏輯與物理)個(gè)指針域?yàn)榭铡.n-27.鏈表所具備的特點(diǎn)是(D.可以通過(guò)下標(biāo)對(duì)鏈表進(jìn)行直接訪問(wèn)8.設(shè)一棵哈夫曼樹(shù)共有n個(gè)非葉結(jié)點(diǎn)，則該樹(shù)有()個(gè)葉結(jié)點(diǎn)。D.2n9.線性表只要以(A.鏈接D.二叉樹(shù)10.從一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)D.top=top-next;x=data;11.散列查找的原理是(定的對(duì)應(yīng)關(guān)系B.按待查記錄的關(guān)鍵字有序的順序方式存儲(chǔ)C.按關(guān)鍵字值的比較進(jìn)行查找D.基于二分查找的方法12.一棵完全二叉樹(shù)共有5層，且第5層上有六個(gè)結(jié)點(diǎn)，該樹(shù)共有()個(gè)結(jié)點(diǎn)。B40,38,46,56,79,84C.40,38,46,84,56,79D.38,40,46,56,79,8429.隊(duì)列的插入操作在()進(jìn)行。C.隊(duì)頭或隊(duì)尾D.在任意指定位置題二、填空題(每小題2分，共24分)1.一棵二叉樹(shù)沒(méi)有單分支結(jié)點(diǎn)，有6個(gè)葉結(jié)點(diǎn)，則該樹(shù)總2.在二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，通常每個(gè)結(jié)點(diǎn)中設(shè)置三個(gè)、右指針。3.設(shè)一棵完全二叉樹(shù)，其最高層上最右邊的葉結(jié)點(diǎn)的編號(hào)為奇數(shù)，該葉節(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為10,該完全二叉樹(shù)一共4.一棵二叉樹(shù)中順序編號(hào)為i的結(jié)點(diǎn)，若它存在左、右孩__5.按照二叉樹(shù)的遞歸定義，對(duì)二叉樹(shù)遍歷的常用算法有6.串的兩種最基本的存儲(chǔ)方式是 o7.數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)多的關(guān)系稱為結(jié)數(shù)都為2,則該樹(shù)共有個(gè)葉結(jié)點(diǎn)。10.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，其相應(yīng)的鏈?zhǔn)酱鎯?chǔ)13.如圖4所示的二叉樹(shù)，其后序遍歷序列為14.n個(gè)元素進(jìn)行冒泡法排序，通常需要進(jìn)行趟冒15o_17.圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。18,根據(jù)搜索方法的不同，圖的遍歷有 19.對(duì)記錄序列排序是指按記錄的某個(gè)關(guān)鍵字排序，記錄序20.按某關(guān)鍵字對(duì)記錄序列排序，若關(guān)鍵字三、綜合題1.(1)利用篩選過(guò)程把序列{42,82,67,102,16,32,57,52}建成堆(小根堆),畫(huà)出該堆(不要求中間過(guò)程)。(2)寫(xiě)出對(duì)上述堆對(duì)應(yīng)的完全二叉樹(shù)進(jìn)行中序遍歷得到的2.設(shè)查找表為(16,15,20,53,64,7),(1),寫(xiě)出每一趟的排序過(guò)程，通常對(duì)n個(gè)元素進(jìn)行冒泡排序要進(jìn)行多少趟冒泡?第j趟要進(jìn)行多少次元素間的比較?(1)設(shè)有查找表{5,14,2,6,18,7,4,1依對(duì)取表中數(shù)據(jù)，構(gòu)造(2)說(shuō)明如何由序列的二叉排序樹(shù)得到相應(yīng)序列的排序結(jié)4.(1)設(shè)有一個(gè)整數(shù)序列{50,38,16,82,110,13,64},(2)利用上述二叉排序樹(shù)，為了查找110,經(jīng)多少次元素間的比較能成功查到，為了查找15,經(jīng)多少次元素間的比較可5.(1)對(duì)給定權(quán)值2,1,3,3,4,5,構(gòu)造哈夫曼樹(shù)。(2)同樣用上述權(quán)值構(gòu)造另一棵哈夫曼樹(shù)，使兩棵哈夫曼四、程序填空題1.以下函數(shù)為鏈隊(duì)列的入隊(duì)操作，x為要 ; ; ;2.設(shè)線性表為(6,10,16,4),以下程序用說(shuō)明結(jié)構(gòu)變量的方法建立單向鏈表，并輸出鏈表中各結(jié)點(diǎn)中的數(shù)據(jù)。#defineNULL0{NODEa,b,c,d,*head,*p;a./*以上結(jié)束建表過(guò)程*/p=head;/*p為工作指針，準(zhǔn)備輸出3.以下函數(shù)在head為頭指針的具有頭結(jié)點(diǎn)的單向鏈表中*next;};typedefNODEintj; 4.以下程序是后序遍歷二叉樹(shù)的遞歸算法的程序，完成程期末綜合練習(xí)三答案一、單項(xiàng)選擇題1.C二、填空題1.112.值域左指針3.214.2i和2i+15.先序；中序；后序6.順序存儲(chǔ)9.物理(存儲(chǔ))18.深度優(yōu)先搜索遍歷廣度優(yōu)先搜索遍歷19.主關(guān)鍵字20.相等三、綜合應(yīng)用題1.(1)2.(1)原序列16777777圖4(3平均查找長(zhǎng)度=(1*1+2*2+3*3)/6=14/6圖6(2中序遍歷中序2,3,4,5,6,7,14,16,1850388213110641671520641653(2)三次；四次1.(1)malloc(sizeof(structnode))(2)p18(1)amp;a(2)dnext=NULL(3)p-data(4)p=p-3.(1)ji-1p4.(1)Postorder(BT-left)(2)Postorder(BT-right)