清華大學(xué)數(shù)據(jù)結(jié)構(gòu)試題及答案

清華大學(xué)數(shù)據(jù)結(jié)構(gòu)試題及答案3年。3.假設(shè)樹的廣義表表示為A(C,D(E,F,G),H(I,J)),樹中包含的節(jié)點(diǎn)數(shù)為 ，樹的深度為 ，樹的度數(shù)為 度4.4。后綴公式923+-102/-的值為 對應(yīng)于中綴公式(3+4X)-2Y/3的后綴公式是5。5。 如果二叉樹存儲在鏈表中，除了數(shù)據(jù)字段外，每個(gè)節(jié)點(diǎn)還有兩個(gè)指向左子節(jié)點(diǎn)和右子節(jié)點(diǎn)的指針在這種存儲結(jié)構(gòu)中，由n個(gè)節(jié)點(diǎn)組成的二叉樹總共有 個(gè)指針字段，其中 個(gè)指針字段存儲地址， 個(gè)指針為空指針6。 對于有向圖和有n個(gè)頂點(diǎn)和e條邊的無向圖，在其對應(yīng)的鄰接表中，分別有 個(gè)和 個(gè)邊節(jié)點(diǎn)7。AOV網(wǎng)絡(luò)是一種 圖8。 在有n個(gè)頂點(diǎn)的無向完全圖中，有 條邊，而在有n個(gè)頂點(diǎn)的有向完全圖中，有 條邊9。 假設(shè)一個(gè)線性表是(12，23，74，55，63，40)，如果根據(jù)鍵％4條件進(jìn)行劃分，具有相同余數(shù)的元素變成6。7.8.9.子表。然后，獲得的四個(gè)子表分別是 10。10.如果根節(jié)點(diǎn)在將元素插入到B_tree的過程中最終被拆分，則新樹的高度為11.11。在堆排序過程中，篩選任何一個(gè)分支節(jié)點(diǎn)的時(shí)間復(fù)雜度為__ ，整個(gè)堆排序過程中的時(shí)間復(fù)雜度為 12。12.在快速排序、堆排序和合并排序中， 排序是穩(wěn)定的三、三、操作題（每題6分，共24分）1.1。一個(gè)線性表被鏈接并存儲在下面的數(shù)組A中，其中頭中的指針為［0］。接下來，試著寫出線性表格A01234567數(shù)據(jù)下一步6055077829003444013圖10側(cè)2。2.請畫出圖10的鄰接矩陣和鄰接表3.3。已知圖的頂點(diǎn)集V和邊集E為V={1,2,3,4,5,6,7}；E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}；用Kruskar算法得到最小生成樹，試寫4。4在最小生成樹中按順序排列。將數(shù)據(jù)4、2、5、8、3添加到小根堆后，繪制堆變化。4,4，閱讀算法(每題7分，共14分)1.1。linklistmynote(linklistl){//l是沒有頭節(jié)點(diǎn)的單個(gè)鏈表的頭指針if(lbc(Bt->right);countleftBST->rightvi,VI,寫算法(8點(diǎn))intcountx(lnode*HL,elemtypex){inti=0；節(jié)點(diǎn)*p=h1；〃我正在計(jì)數(shù)器的同時(shí)(p！=NULL){如果(P->數(shù)據(jù)==x)I+；p=p->下一個(gè)；}〃同時(shí)，退出循環(huán)時(shí)I中的值是返回I的x節(jié)點(diǎn)數(shù)；}//CounX1,1,單題(每題2分，共8分)1。當(dāng)在長度為n的序列線性表中順序搜索具有值x的元素時(shí)，搜索成功時(shí)的平均搜索長度(即x和個(gè)元素之間的平均比較時(shí)間，假設(shè)搜索每個(gè)元素的概率相等)為()anbn/2c(n+1)/2d(n-1)/22。在單個(gè)鏈表中，如果由q指示的節(jié)點(diǎn)是由p指示的節(jié)點(diǎn)的前體節(jié)點(diǎn)，如果由s指示的節(jié)點(diǎn)被插入在4和p之間，則執(zhí)行()安s—鏈接二p—鏈接；p—link=s；bp—鏈接二s；s—link=q；cp—link=s—link；s—link=p；dq—link=s；s—link=p；3、3、堆棧插入和刪除操作在()A堆棧頂部b堆棧底部c任意位置d指定位置4和4,并從權(quán)重值分別為11、8、6、2和5的葉節(jié)點(diǎn)生成霍夫曼樹。其加權(quán)路徑長度為()9a24b71c48d532，2，填空題(每空1分，共32分)1，1，數(shù)據(jù)的邏輯結(jié)構(gòu)分為四種類型: 、 、— 和 。2.2.抽象數(shù)據(jù)類型由 和___ 組成3。一個(gè)線性表被鏈接并存儲在下面的數(shù)組A中，標(biāo)題中的指針是一個(gè)［o］。接下來，線性表是a012345678data605642387425next43762014。在表頭帶附加節(jié)點(diǎn)的單鏈表和表頭帶HL指針的循環(huán)單鏈表中，判斷鏈表為空的條件分別為為 和 的條件5。如果一個(gè)循環(huán)隊(duì)列存儲在一個(gè)有n個(gè)元素的一維數(shù)組中，它的頭指針總是指向head元素的 ，并且循環(huán)隊(duì)列的最大長度是 6。當(dāng)堆棧采用順序存儲結(jié)構(gòu)時(shí)，堆棧頂部元素的值可以用-；當(dāng)堆棧采用鏈接存儲的結(jié)構(gòu)時(shí)，堆棧頂部元素的值可以用 表示7,高度為5的二叉樹包含至少 個(gè)節(jié)點(diǎn)，最多― 個(gè)節(jié)點(diǎn);高度為5的理想平衡樹至少包含 個(gè)節(jié)點(diǎn)，最多包含 個(gè)節(jié)點(diǎn)。8。在圖的鄰接表中，每個(gè)節(jié)點(diǎn)被稱為 ，它通常包含三個(gè)域:一個(gè)是 ；2是 ；第三個(gè)是 9，9。在索引文件的索引表中，每個(gè)索引項(xiàng)包含與記錄 ___和 相對應(yīng)的兩項(xiàng)數(shù)據(jù)10.10.假設(shè)樹的廣義表表示為A(B(C,D(E,F,G),H(I,J)),樹中包含的節(jié)點(diǎn)的數(shù)量為 ，樹的深度為 ，樹的度數(shù)為 ，節(jié)點(diǎn)H的父節(jié)點(diǎn)為 ，子節(jié)點(diǎn)為 11，11。在堆排序過程中，篩選任何一個(gè)分支節(jié)點(diǎn)的時(shí)間復(fù)雜度為_ ，整個(gè)堆排序過程的時(shí)間復(fù)雜度為 12，12。在將元素插入到順序?yàn)镸的B_樹的過程中，在每個(gè)節(jié)點(diǎn)中插入一個(gè)索引項(xiàng)(葉節(jié)點(diǎn)中的索引項(xiàng)是關(guān)鍵字和空指針)后，如果該節(jié)點(diǎn)的索引項(xiàng)等于 ，則必須將其分為 個(gè)節(jié)點(diǎn)。3，3,操作問題(每項(xiàng)6分，共24分)1，1，已知一組記錄的排序代碼為(46，79，56，38，40，80，95,24)，并寫出快速排序的每個(gè)除法結(jié)果2,2,一個(gè)線性表是b=(12,23,45,57,20,03,78,31,15,36),哈希表是［0..12］，哈希列函數(shù)為H(鍵)=鍵％13，沖突通過線性探索解決。請繪制哈希表，并計(jì)算在同等概率條件下搜索成功的平均搜索長度。3,3。眾所周知，二叉樹的前序遍歷的結(jié)果序列是ABECKFGHIJ,前序遍歷的結(jié)果是EBCDAFHIGJo試圖寫入二叉樹的后順序遍歷的結(jié)果。4,4。圖的頂點(diǎn)集V的每個(gè)邊集G如下:V={0，1，2,3,4,5,6,7,8,9}；e={(0，1)，(0，4),(1,2),(1,7),(2,8),(3,4),(3,8),(5,6)，(5,8)，(5,9),(6,7)，(7,8)，(8,9)}當(dāng)由鄰接矩陣和鄰接表表示時(shí)，由深度優(yōu)先搜索遍歷獲得的頂點(diǎn)序列和由寬度優(yōu)先搜索遍歷從頂點(diǎn)V0獲得的頂點(diǎn)序列被分別寫入假設(shè)每個(gè)頂點(diǎn)鄰接表中的節(jié)點(diǎn)按頂點(diǎn)數(shù)的降序鏈接深度優(yōu)先序列寬度優(yōu)先序列鄰接矩陣表示鄰接表表示四、四、閱讀算法，回答問題(每項(xiàng)8分，共16分)1,假設(shè)從鍵盤輸入一批整數(shù)，順序是：786345309134-1,請寫出輸出結(jié)果include#includeconsstintstackmassize=30；typedefint元素類型；結(jié)構(gòu)堆棧｛元素類型堆棧［堆棧大小］;inttop｝；包括”stack.h“Vbidmain()stacka；1,單題(每題2分，共20分)1。1.算法的評估不包括以下(b)а。 b.并行性c.正確性d.時(shí)空復(fù)雜性2.2。在帶頭節(jié)點(diǎn)的單鏈表HL中，要將指針p指向的節(jié)點(diǎn)插入頭節(jié)點(diǎn)，執(zhí)行()A.p-＞下一個(gè)=h1-＞下一個(gè)；HL-＞下一個(gè)=p；百寶箱-＞下一個(gè)=HLHL=p；°Cp-＞下一個(gè)=HLp=h1；高度=p；p-＞下一個(gè)=h1；3。3.對于線性表，下列哪種情況應(yīng)該用鏈表來表示？()A。通常需要隨機(jī)訪問元素B。通常需要插入和刪除元素C。表中的元素需要占用連續(xù)的存儲空間D。表中元素的數(shù)量保持不變4.4。堆棧的輸入序列是1.23。則(c)a.231b.321c.312d.1235.5AOV網(wǎng)不能是堆棧的輸出序列，按以下順序?yàn)閍()A.有向圖b。無向圖c。無向無環(huán)圖d。有向無環(huán)圖6。б. 開放尋址方法處理哈希表沖突時(shí)的平均查找長度()A.處理沖突的低于鏈接方法b.處理沖突的高于鏈接方法c.與處理沖突的鏈接方法相同d.高于二進(jìn)制搜索7.7。如果需要形式參數(shù)來直接訪問實(shí)參數(shù)，形式參數(shù)變量應(yīng)該被描述為()參數(shù)A.值b.函數(shù)c.指針d.引用8。8.在稀疏矩陣的帶行指針向量的鏈表存儲中，每個(gè)鏈表中的節(jié)點(diǎn)都有相同的()A.行號b、列號c、元素值d、非零元素?cái)?shù)9。9.快速排序最糟糕的時(shí)間復(fù)雜度是()a.o(log2n)b.o(nlog2n)c.0(n)d.0(N2)10.10。當(dāng)從二進(jìn)制搜索樹中搜索元素時(shí)，其時(shí)間復(fù)雜度大約為()A.操作題(每題6分，共24分)1.1。數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)及其相 當(dāng)節(jié)點(diǎn)之間存在m至Un(m:n)的連接時(shí)，該結(jié)構(gòu)被稱為 2.2。 隊(duì)列的插入在隊(duì)列的末尾，刪除在隊(duì)列的開頭。3.3。 當(dāng)按順序存儲數(shù)組長度為N的堆棧時(shí)，假設(shè)top==N用于指示堆棧為空，則指示堆棧已滿的條件為__\top==0__(僅當(dāng)超過時(shí)才為滿) 4.4.對于長度為n的單鏈存儲的線性表，將元素插入報(bào)頭的時(shí)間復(fù)雜度為 ，而插入元素的時(shí)間復(fù)雜度為5。表末的元素是 5。 假設(shè)w是二維數(shù)組，每個(gè)數(shù)據(jù)元素占用4個(gè)字節(jié)，行下標(biāo)I從0到7,列下標(biāo)j從0到3,那么二維數(shù)組w的數(shù)據(jù)元素總共占用 __個(gè)字節(jié)W中第6行和第4列的元素總共占用 個(gè)字節(jié)如果二維數(shù)組W是按行順序存儲的，并且它的起始地址是100，那么二維數(shù)組元素W[6，3]的起始地址是 6。 廣義表a=(a，(a，b)，((a，b，c))，那么它的深度是 __，它的長度是 7。二叉樹是指度數(shù)為2的 樹對于有n個(gè)節(jié)點(diǎn)的二叉樹，所有節(jié)點(diǎn)的度數(shù)之和 8。當(dāng)以中間順序遍歷二進(jìn)制搜索樹時(shí)，獲得的節(jié)點(diǎn)序列是 在遍歷由算術(shù)表達(dá)式組成的二進(jìn)制語法樹之后，獲得的節(jié)點(diǎn)序列是 6年7月8日9年9月。當(dāng)一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹存儲在一個(gè)二進(jìn)制鏈表中時(shí)，指針的總數(shù)為 ，其中 用于指向子級，而 指針是空閑的10。10.如果一個(gè)完整的二叉樹從0開始編號，并根據(jù)這個(gè)編號順序存儲在一維數(shù)組A中，即編號為0的節(jié)點(diǎn)存儲在［0中］以此類推，［元素的左子兀素是 ，右子元素是 ，父元素是_11。11.在線性表的散列存儲中，有兩種常用的方法來處理沖突，即 和12。12.當(dāng)需要排序的記錄數(shù)量較大，排序代碼隨機(jī)，不要求穩(wěn)定性時(shí)，宜采用 排序。當(dāng)要排序的記錄數(shù)量很大，存儲空間允許并且排序要求穩(wěn)定時(shí)，使用 排序是合適的3、3、操作題（每題6分，共24分）1分。1.知道a6嗎？稀疏矩陣如下，？0？0？？0？？0？5？？？000000000000700000001?0??0???2?0??0???10嘗試：⑴⑴寫它的三元組線性表；(2)(2)給出了三元線性表的順序存儲表示2.2。 有一系列輸入數(shù)據(jù)｛46,25,78,62,12,80｝。通過逐個(gè)輸入數(shù)據(jù)，嘗試從空樹中繪制一個(gè)的二進(jìn)制搜索樹。3.3。 如果圖6中所示的有向圖與鄰接表一起存儲，并且每個(gè)頂點(diǎn)鄰接表中的邊緣節(jié)點(diǎn)根據(jù)端點(diǎn)順序從小到大鏈接，則嘗試寫：(1)深度優(yōu)先生成樹，通過從頂點(diǎn)①進(jìn)行深度優(yōu)先搜索獲得；(2)從頂點(diǎn)(2)開始通過廣度優(yōu)先搜索得到的廣度優(yōu)先生成樹；4.4.已知圖的頂點(diǎn)集V和邊集E分別為V=｛1,2,3,4,5,6,7｝。E=｛，，，，，，，｝；如果存儲在鄰接表中，并且每個(gè)頂點(diǎn)鄰接表中的邊節(jié)點(diǎn)根據(jù)端點(diǎn)的序號從小到大鏈接，則使用主教材中介紹的拓?fù)渑判蛩惴ㄟM(jìn)行排序，并嘗試得到的拓?fù)渑判蛐蛄?。圖64,4,閱讀算法(每題7分，共14分)1.1.int素?cái)?shù)(intn)(intI=1；intx=(int)sqrt(n)；，而(+ix)返回1；否則返回0；}(1)表示算法的功能；(2)該算法的時(shí)間復(fù)雜度是多少？2.2.寫下以下算法的功能:voidaj(adjlistgl，inti，intn)(queueq；初始隊(duì)列(Q)；(［棧頂)棧頂=棧頂-1；否則返回(0)；返回(1)；2.2。 設(shè)計(jì)一種算法，在鏈?zhǔn)酱鎯Y(jié)構(gòu)上建立二叉樹typedefchar數(shù)據(jù)類型；typedef結(jié)構(gòu)節(jié)點(diǎn){datatypedata結(jié)構(gòu)節(jié)點(diǎn)*lchild，*rchild}bitreevoidcreatebitree(bitree*scanf(\if(ch==‘#‘){返回；0}Bt=(bitree*)malloc(sizeof(bitree))；bt->數(shù)據(jù)=chcreatebitree(Bt->lchild)；createbitree(Bt->archild)；3.3。 設(shè)計(jì)一個(gè)算法來判斷二叉樹是否是二叉排序樹intminnum=-32768，flag=1；typedef結(jié)構(gòu)節(jié)點(diǎn){int鍵；結(jié)構(gòu)節(jié)點(diǎn)*lchild，*rchild}bitreevoidinorder(bitree*Bt)(if(Bt!=0)(inorder(Bt->Ichild)；if(minnum>bt->key)標(biāo)志=0；minnum=Bt->key；排序(Bt->rchild)；}}數(shù)據(jù)結(jié)構(gòu)試卷(2)1,選擇題(24分)1。以下關(guān)于線性表的陳述是錯(cuò)誤的()(A)線性表使用順序存儲，必須占用連續(xù)存儲空間(b)線性表使用鏈?zhǔn)酱鎯Γ恍枰加眠B續(xù)存儲空間(c)線性表使用鏈?zhǔn)酱鎯?，便于插入和刪除操作(d)線性表使用順序存儲，便于插入和刪除操作。假設(shè)哈夫曼樹中的葉節(jié)點(diǎn)總數(shù)為M，如果使用二進(jìn)制鏈表作為存儲結(jié)構(gòu)，哈夫曼樹中有()個(gè)空指針字段(a)2m-1(b)2m(c)2m+1(d)4m3。 假設(shè)順序循環(huán)隊(duì)列q[0:m-1]的頭指針和尾指針分別是f和r，頭指針f總是指向團(tuán)隊(duì)頭元素的前一個(gè)位置，尾指針r總是指向團(tuán)隊(duì)尾元素的當(dāng)前位置，那么循環(huán)隊(duì)列中的元素?cái)?shù)量是()(a)r-f(b)f-r(c)(r-f+m)%m(d)(f-r+m)%m4。 假設(shè)二叉樹的中序遍歷序列是ABCD，其前序遍歷序列是CABD，那么遍歷二叉樹得到的序列是()(a)badc(b)bcda(c)cdab(d)cbda5。如果在完全無向圖中有n個(gè)頂點(diǎn)，那么在完全無向圖中有()條邊(a)N2(d)N2-16。如果二叉樹中有2000個(gè)節(jié)點(diǎn)，二叉樹的最小高度是()(a)9(b)10(c)11(d)127。 如果有向圖中有n個(gè)頂點(diǎn)，那么在對應(yīng)于有向圖的鄰接表中有()個(gè)頭節(jié)點(diǎn)(a)n-1(b)n(c)n+1(d)2n-18。 設(shè)置一組初始記錄鍵序列(5,2,6,3,8)，并使用第一個(gè)記錄鍵5作為執(zhí)行快速序列的基礎(chǔ)。結(jié)果是()(a)2，3，5，8，6(b)3，2，5，8，6(c)3，2，5，6，8(d)2，3，6，5，8填寫問題(24分)1.1。為了有效地應(yīng)用HASH搜索技術(shù)，必須解決的兩個(gè)問題是 和2。 2.以下程序段的功能實(shí)現(xiàn)了數(shù)據(jù)X堆棧，要求在下劃線處填寫正確的語句typedef結(jié)構(gòu){國際標(biāo)準(zhǔn)［100］；inttop}sqstack。voidpush(sqstackelse{ ； -_；}}3。 3.通過以中間順序遍歷二進(jìn)制排序樹獲得的序列是 _(有序或無序的)4.4.快速排序的最差時(shí)間復(fù)雜度是 ，平均時(shí)間復(fù)雜度是 5.5。如果二叉樹中0度的節(jié)點(diǎn)數(shù)為N0，1度的節(jié)點(diǎn)數(shù)為N1，則二叉樹中2度的節(jié)點(diǎn)數(shù)為 ；如果采用二進(jìn)制鏈表作為二叉樹的存儲結(jié)構(gòu)，則二叉樹總共有 個(gè)空指針字段6.6.如果無向圖的頂點(diǎn)數(shù)和邊數(shù)分別為n和e，并且所有頂點(diǎn)的度數(shù)之和為d，則e= 7.7。如果一組初始記錄密鑰序列是(55,63,44,38,75,80,31,56),那么通過篩選方法建立的初始堆是vl??3？？2？？4v2？？1？？3v3？？1？？4？？28.8.讓無向圖G的鄰接表是v4？？1？？3、從頂點(diǎn)V1開始的深度優(yōu)先遍歷序列是 ；廣度優(yōu)先遍歷順序是 3、申請問題(36分)1.1。如果一組初始記錄關(guān)鍵字序列是(45,80,48,40,22,78),則分別給出第四簡單選擇排序和第四直接插入排序的結(jié)果2.2。將指針變量P設(shè)置為指向雙鏈表中的節(jié)點(diǎn)A,將指針變量Q設(shè)置為指向插入的節(jié)點(diǎn)B,需要給出節(jié)點(diǎn)A后插入節(jié)點(diǎn)B的操作順序(將雙鏈表中節(jié)點(diǎn)的兩個(gè)指針字段分別設(shè)置為鏈接和rlink)3.3。 將記錄關(guān)鍵字的有序序列設(shè)置為(13,18,24,35,47,50,62,83,90)。搜索方法使用二進(jìn)制搜索，要求在搜索關(guān)鍵字62時(shí)計(jì)算比較時(shí)間，并在搜索成功時(shí)計(jì)算平均搜索長度4.4。 將樹T中的邊集設(shè)置為｛(A，b),(A,c),(A,d),(b,e),(c,f),(c,G)｝。需要用子兄弟表示(二進(jìn)制鏈表)來表示樹的存儲結(jié)構(gòu)，并將樹轉(zhuǎn)換成相應(yīng)的二叉樹5.5。有一個(gè)無向圖G(如右圖所示)，它需要組邊，通過prim算法構(gòu)造最小生成樹來遍歷。6.6。有一組初始記錄關(guān)鍵字（45，80，48，40，22，78），需要構(gòu)造一個(gè)二進(jìn)制排序樹，給出了構(gòu)造過程4。算法設(shè)計(jì)問題（16分）1.1。 有一組初始記錄密鑰序列（K1，K2，...，Kn）。需要設(shè)計(jì)一種算法，能夠在時(shí)間復(fù)雜度為0（n）的范圍內(nèi)將線性表分成兩部分，其中左半部分的每個(gè)鍵小于Ki，右半部分的每個(gè)鍵大于或等于Ki2.2。 有兩