2023學(xué)年第一學(xué)期數(shù)據(jù)結(jié)構(gòu)試題(A卷)

22023~2023學(xué)年第一學(xué)期數(shù)據(jù)構(gòu)造期末考試試題考試時(shí)間 100分鐘 考試方式 閉卷筆試一、單項(xiàng)選擇題：〔每題2分，共40分〕在每題給出的四個(gè)選項(xiàng)中，請(qǐng)選出一項(xiàng)最符合題目要求的。從規(guī)律上可以把數(shù)據(jù)構(gòu)造分為〔 〕兩大類。動(dòng)態(tài)構(gòu)造、靜態(tài)構(gòu)造 B.挨次構(gòu)造、鏈?zhǔn)綐?gòu)造C.線性構(gòu)造、非線性構(gòu)造 D.根本構(gòu)造、構(gòu)造構(gòu)造以下術(shù)語中〔 〕與數(shù)據(jù)的存儲(chǔ)構(gòu)造無關(guān)。棧 B.哈希表 C.線索樹 D.雙向鏈表下面的程序段的時(shí)間簡(jiǎn)單度為〔 。for〔i=1；i<=n；i++〕for〔j=1；j<=n；j++〕x=x+1；A.O(log2n) B.O(2n) C.O(n) D.O(n2)假設(shè)長(zhǎng)度為n的線性表承受挨次存儲(chǔ)構(gòu)造在其第i(1<=i<=n+1)個(gè)位置插入一個(gè)元素的算法的時(shí)間簡(jiǎn)單度為〔 〕。A.O(0) B.O(1) C.O(n) D.O(n2)為解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題，通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)輯構(gòu)造應(yīng)當(dāng)是〔〕。A.棧B.隊(duì)列C.樹D.圖假設(shè)元素a，b，c，d，e，f依次進(jìn)棧，允許進(jìn)棧、退棧操作交替進(jìn)展。但不允許連續(xù)三次進(jìn)展退棧工作，則不行能得到的出棧序列是〔 〕。dcebfa B.cbdaef C.bcaefd D.afedcb假設(shè)對(duì)n階對(duì)稱矩陣A以行序?yàn)橹餍蚍绞綄⑵湎氯切蔚脑舶ㄖ鲗?duì)角線上全部元素〕依次存放于一維數(shù)組B[1..(n(n+1))/2]中，則在B中確定A矩陣中的元素aij〔i<j〕的位置k的關(guān)系為( )。A.i*(i-1)/2+j B.j*(j-1)/2+I C.i*(i+1)/2+j D.j*(j+1)/2+i在一棵度為4的樹T中假設(shè)有20個(gè)度為4的結(jié)點(diǎn)，10個(gè)度為3的結(jié)點(diǎn)，1個(gè)度為2的結(jié)點(diǎn)，10個(gè)度為1的結(jié)點(diǎn)，則數(shù)T的葉節(jié)點(diǎn)個(gè)數(shù)是〔 。A.41 B.82 C.113 D.122給定二叉樹以下圖所示設(shè)N代表二叉樹的根，L代表根結(jié)點(diǎn)的左子樹，R代表根結(jié)點(diǎn)的右子樹。假設(shè)遍歷后的結(jié)點(diǎn)序列為〔3，1，7，5，6，2，4〕，則其遍歷方式是〔 〕。11234567A.LRN B.NRL C.RLN D.RNL將森林轉(zhuǎn)換為對(duì)應(yīng)的二叉樹假設(shè)在二叉樹中結(jié)點(diǎn)u是結(jié)點(diǎn)v的父結(jié)點(diǎn)的父結(jié)點(diǎn)則在原來的森林中，u和v可能具有的關(guān)系是〔 〕。I.父子關(guān)系 Ⅱ.兄弟關(guān)系 Ⅲ.u的父結(jié)點(diǎn)與v的父結(jié)點(diǎn)是兄弟關(guān)系A(chǔ).只有Ⅱ B.I和Ⅱ C.I和Ⅲ D.I、Ⅱ和Ⅲ以下編碼中〔 〕不是前綴碼。A.〔00，01，10，11〕 B.〔0，10，110，111〕C.〔0，1，00，11〕 D.〔1，01，000，001〕在以下圖所示的平衡二叉樹中插入關(guān)鍵字48后得到一棵平衡二叉樹，在平衡二叉樹中，關(guān)鍵字37所在結(jié)點(diǎn)的左、右子結(jié)點(diǎn)保存的關(guān)鍵字分別是〔 。242413533790A.13，48 B.24，48 C.24，53 D.24，90假設(shè)無向圖G=(V.E)中含7個(gè)頂點(diǎn)，則保證圖G在任何狀況下都是連通的，則需要的邊數(shù)最少是〔 。A.6 B.15 C.16 D.2114G=(VE)V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>}，圖G的拓?fù)湫蛄惺恰?。A.V1,V3,V4,V6,V2,V5,V7 B.V1,V3,V2,V6,V4,V5,V7C.V1,V3,V4,V5,V2,V6,V7 D.V1,V2,V5,V3,V4,V6,V715.關(guān)鍵字序列351376，9102，用折半查找法查找66與6，要將給定值與關(guān)鍵字比較的次數(shù)分別為〔 。A.6，7 B.2，3C.2，4D.3，4以下表達(dá)中，不符合m階B樹定義要求的是〔 〕。根結(jié)點(diǎn)最多有m棵子樹 B.全部葉結(jié)點(diǎn)都在同一層上C.各結(jié)點(diǎn)內(nèi)關(guān)鍵字均升序或降序排列 D.葉結(jié)點(diǎn)之間通過指針鏈接對(duì)一組數(shù)據(jù)〔2，12，16，88，5，10〕進(jìn)展排序，假設(shè)前三趟排序結(jié)果如下：〔，1，1，，1，8〕則承受的排序方法可能是〔。起泡排序B.希爾排序C.歸并排序D.基數(shù)排序以下關(guān)鍵字序列中〔 〕是堆。A.〔75,65,30,15,25,45,20,10〕 B.〔75,65,45,10,30,25,20,15〕C.〔75,45,65,10,25,30,20,15〕 D.〔75,45,65,30,15,25,20,10〕19.對(duì)關(guān)鍵字序列〔05，46，13，55，94，17，42〕進(jìn)展基數(shù)排序，一趟排序后的結(jié)果是〔。A.〔05，46，13，55，94，17，42〕 B.〔05，13，17，42，46，55，94〕C.〔42，13，94，05，55，46，17〕 D.〔05，13，46，55，17，42，94〕以下排序方法中〔 〕是穩(wěn)定的排序方法。A.折半插入排序 B.直接選擇排序 C.希爾排序 D.快速排序1~3題各10分，4、5題各15分，共60分。1.99請(qǐng)?jiān)趫D中標(biāo)出各結(jié)點(diǎn)的值。2．設(shè)無向圖G=〔V，E〕，其中V={1，2，3，4，5}，E={〔1，2，4〕，〔2，5，5〕，〔1，3，2〕，〔2，4，4〕，〔3，4，1〕，〔4，5，3〕，〔1，5，8〕}，每條邊由一個(gè)三元組G中從頂點(diǎn)1到其余各點(diǎn)的了短路徑的求解過程。要求列出最短路徑上的頂點(diǎn)，并計(jì)算路徑長(zhǎng)度。0～9，哈希函數(shù)為：H〔Key〕＝KeyMOD7，用線性探測(cè)法再散列法處理沖突，依據(jù)關(guān)鍵字序列〔16，8，15，32，24，30〕哈希造表，試答復(fù)以下問題：畫出哈希表的示意圖；假設(shè)查找關(guān)鍵字24，需要依次與哪些關(guān)鍵字進(jìn)展比較？假定每個(gè)關(guān)鍵字的查找概率相等，求查找成功時(shí)的平均查找長(zhǎng)度。地址下標(biāo)地址下標(biāo)關(guān)鍵字0123456789兩個(gè)升序序列長(zhǎng)度分別為mnab素歸并成一個(gè)非遞減的序列并存放到數(shù)組c描述算法的根本設(shè)計(jì)思想；描述算法的具體實(shí)現(xiàn)步驟；依據(jù)設(shè)計(jì)思想和實(shí)現(xiàn)步驟，承受程序設(shè)計(jì)語言描述算法〔使用C或C++或JAVA語言實(shí)現(xiàn)〕，關(guān)鍵之處請(qǐng)給出簡(jiǎn)要注釋。用一個(gè)帶有表頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列結(jié)點(diǎn)構(gòu)造為 假設(shè)該循環(huán)鏈表只設(shè)一個(gè)尾指針rear指向隊(duì)尾元素結(jié)點(diǎn)〔留意不設(shè)頭指針列和出隊(duì)列算法。要求：描述算法的根本設(shè)計(jì)思想；描述算法的具體實(shí)現(xiàn)步驟；依據(jù)設(shè)計(jì)思想和實(shí)現(xiàn)步驟，承受程序設(shè)計(jì)語言描述算法〔使用C或C++或JAVA語言實(shí)現(xiàn)〕，關(guān)鍵之處請(qǐng)給出簡(jiǎn)要注釋。2023~2023學(xué)年第一學(xué)期數(shù)據(jù)構(gòu)造期末考試參考答案一、單項(xiàng)選擇題：〔240〕1.C2．A3.D4.C5.B6.D7.B8.B9.D10.B11.C12.C13.A14.A15.B16.D17.A18.D19.C 20.A1~3題各10分，4、5題各15分，共60分。1.55194627382．假設(shè)頂點(diǎn)數(shù)組為{V1，V2，V3，V4，V5}，則鄰接矩陣為：∞4 2 ∞84 ∞∞452 ∞∞1∞∞4 1 ∞38 5 ∞3∞V1頂點(diǎn)V1i=1∞i=2∞i=3∞i=4∞i=5∞無V24{V1，V2}4{V1，V2}4{V1，V2}V32{V1，V3}V4∞3{V1，V3，V4}V58{V1，V5}8{V1，V5}6{V1，V3，V4，V5}6{V1，V3，V4，V5}VjV3V4V2V5SS{V1，V3}{V1，V3，V4}{V1，V2，V3，V4}{V1，V2，V3，V4，V5}V1為起點(diǎn)到頂點(diǎn)V24，路徑為{V1，V2}；V1為起點(diǎn)到頂點(diǎn)V32，路徑為{V1，V3}；V1為起點(diǎn)到頂點(diǎn)V43，路徑為{V1，V3，V4}；V1為起點(diǎn)到頂點(diǎn)V56，路徑為{V1，V3，V4，V5}?！?〕哈希表的示意圖:地址下標(biāo)0123456789關(guān)鍵字81615322430〔2〕24，15,32,243〔3〕查找成功時(shí)的平均查找長(zhǎng)度：ASL=〔1+1+3+1+3+5〕/6=7/3。〔1〕算法的根本設(shè)計(jì)思想：順次比較a，b兩個(gè)數(shù)組的元素，將較小的一個(gè)存放到c數(shù)組中去，并取下一個(gè)元素；當(dāng)一個(gè)數(shù)組搜尋到終點(diǎn)的時(shí)候，將另一個(gè)數(shù)組的剩余元素依次存放到c算法的具體實(shí)現(xiàn)步驟：i，j分別表示a，b0；用kc0。①當(dāng)i<mj<na[ib[jc1，c1，重復(fù)①；②當(dāng)i<m時(shí)，將ac③當(dāng)j<n時(shí)，將bc算法的CvoidMerge(inta[],intb[],intc[],intm,intn)//{inti,j,k；for(i=0,j=0,k=0；i<m&&j<n；++k)//a，b{if(a[i]<b[j])c[k]=a[i++]；//a[ic[k]中，取aelsec[k]=b[j++]； //b[j]存放到c[k]中，取b}while〔i<m)c[k++]=a[i++]； //當(dāng)b中沒有元素時(shí)while〔j<n〕c[k++]=b[j++]； //當(dāng)a中沒有元素時(shí)}〔1〕算法的根本設(shè)計(jì)思想：改寫尾指針。出隊(duì)列，推斷隊(duì)列是否為空，假設(shè)不為空，則刪除循環(huán)鏈表中第一個(gè)數(shù)據(jù)元素，假設(shè)原隊(duì)列只有一個(gè)元素，刪除后要改寫尾指針。算法的具體實(shí)現(xiàn)步驟：數(shù)據(jù)構(gòu)造為單鏈表，一個(gè)數(shù)據(jù)域data，一個(gè)指針域link。初始化：生成一個(gè)結(jié)點(diǎn)rear，假設(shè)安排成功，rear入隊(duì)列：給元素x安排結(jié)點(diǎn)空間s，假設(shè)安排成功，s數(shù)據(jù)域賦值為x，s指向頭結(jié)點(diǎn)，ss出隊(duì)列：推斷隊(duì)列是否為空；假設(shè)不為空，h指向鏈表的頭結(jié)點(diǎn)，刪除hhh。算法的C#defineOK1#defineERROR0typedefintStatus；typedefstrucNode{intdata；strucNode*link；}QNode,*QLink；StatusInitQueue(QLink&rear)//函數(shù)首部，初始化成功返回OK，否則返回ERROR{rear=〔QLink〕malloc〔sizeof〔QNode〕；//安排頭結(jié)點(diǎn)空間if〔rea〕retur〔ERRO； //動(dòng)態(tài)存儲(chǔ)安排失敗，返回rear->link=rear； //循環(huán)鏈表retur〔O；}StatusEnQueue(QLink&rear,intx)//OKERROR{QLinks；s=〔QLink〕malloc〔sizeof〔QNode〕； //給xif〔sretur〔ERRO； //動(dòng)態(tài)存儲(chǔ)安排失敗，返回ERRORs->data=x； //結(jié)點(diǎn)的數(shù)據(jù)域?yàn)閤s->link=rear->link； //結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)rear->link=s； //將結(jié)點(diǎn)連到鏈表尾部rear=s； //sretu