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

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