數(shù)據(jù)結(jié)構(gòu)試題及答案

1、數(shù)據(jù)結(jié)構(gòu)試題及參考答案時(shí)間:2014-03-1大學(xué)計(jì)算機(jī)專(zhuān)業(yè)數(shù)據(jù)結(jié)構(gòu)期末試題及參考答案一、單項(xiàng)選擇題(每小題1分，共12分)1下面算法的時(shí)間復(fù)雜度為()在一個(gè)長(zhǎng)度為的順序表中順序查找一個(gè)值為的元素.在等概率的情況下，搜索成功時(shí)間元素的平均比較次數(shù)為帶頭結(jié)點(diǎn)的單鏈表為空的判定條件是4已知是一個(gè)不帶表頭的單鏈表的表頭指針，在表首插入結(jié)點(diǎn)的操作是設(shè)循環(huán)隊(duì)列的結(jié)構(gòu)是若有一個(gè)類(lèi)型的隊(duì)列.試問(wèn)判斷隊(duì)列滿的條件應(yīng)為6設(shè)有一個(gè)廣義表（，），9,，運(yùn)算TOC o 1-5 h z的執(zhí)行結(jié)果為AxB（，ab）C（，x（a，b）Dy7在一棵完全二叉樹(shù)中，著編號(hào)為的結(jié)點(diǎn)存在左子女，則左子女結(jié)點(diǎn)的編號(hào)為（）假定樹(shù)根結(jié)點(diǎn)的

2、編號(hào)為0。8對(duì)長(zhǎng)度為10的順序表進(jìn)行搜索，若搜索前面5個(gè)元素的概率相同，均為18，搜索后面5個(gè)元素的概串相同，均為340，則搜索任一元素的平均搜索長(zhǎng)度為（）C389D194.向一棵樹(shù)插入元素時(shí)，可能引起對(duì)最小不平衡于樹(shù)的左單或右單旋轉(zhuǎn)的調(diào)整詞程，此時(shí)需要修改相關(guān)（個(gè)）指針域的值0對(duì)于有向圖，其鄰接矩陣表示比鄰接表表示更易于.求一個(gè)頂點(diǎn)的入度.求一個(gè)頂點(diǎn)的出邊鄰接點(diǎn).進(jìn)行圖的深度優(yōu)先遍歷.進(jìn)行圖的廣度優(yōu)先遍歷1設(shè)有向固有個(gè)頂點(diǎn)和，條邊，采用鄰接表作為其存儲(chǔ)表示，在進(jìn)行拓?fù)渑判驎r(shí)，總的計(jì)算時(shí)間為().A.O(nlog2e)B.O(n+e)C.O(ne)D.O(n2)2在階樹(shù)申報(bào)結(jié)點(diǎn)所包含的關(guān)鍵碼個(gè)

3、數(shù)最少為試題答案及評(píng)分標(biāo)準(zhǔn)一、單項(xiàng)選擇題每(小題1分，共12分，填空題.在橫線處填寫(xiě)合適內(nèi)容每空1分，共16分)屬.性與服務(wù)相同的對(duì)象構(gòu)成類(lèi)，類(lèi)中的每個(gè)對(duì)象稱(chēng)為該類(lèi)的2在類(lèi)的繼承結(jié)構(gòu)中，位于上層的類(lèi)叫做，_其_下_層_的類(lèi)則叫做類(lèi)3若設(shè)串=documentHashdocO，則詼字符串的長(zhǎng)度為4線性表的鏈接存儲(chǔ)只能通過(guò)順_序訪_問(wèn)_。5設(shè)鏈棧中結(jié)點(diǎn)的結(jié)構(gòu)為datan,棧頂指針為to,則向該鏈棧插入一個(gè)新結(jié)點(diǎn)時(shí)，應(yīng)依次執(zhí)行和操_作_。_6廣義表的深度定義為廣義表中括號(hào)被嵌套的_7在一棵高度為h的完全二叉樹(shù)中，最少含有個(gè)結(jié)點(diǎn)。假定樹(shù)根結(jié)點(diǎn)的高度為0。8從有序表（1，220，30，4，356，78，9

4、，295中棧折半搜索56、78和98元素時(shí)，其搜索長(zhǎng)度分別為、和9n個(gè)n頂點(diǎn)的連通無(wú)向圖中各頂點(diǎn)的度之和最少為_(kāi)o設(shè)圖的頂點(diǎn)數(shù)為n,則求解最短路徑的S算法的時(shí)間復(fù)雜度為11給定一組數(shù)據(jù)對(duì)象的關(guān)鍵碼為4,679,5,638,40,84,則利用堆排序方法建立的初始最大堆的堆首和堆尾的關(guān)鍵碼分別為_(kāi)和12在索引表中，著一個(gè)索引項(xiàng)對(duì)應(yīng)數(shù)據(jù)對(duì)象表中的一個(gè)表項(xiàng)，則稱(chēng)此索引為稠密索引，若對(duì)應(yīng)數(shù)據(jù)對(duì)象表中的若干表項(xiàng)，則稱(chēng)此索引為索_引_計(jì)算機(jī)專(zhuān)業(yè)數(shù)據(jù)結(jié)構(gòu)試題答案及評(píng)分標(biāo)準(zhǔn)二、填空題，在橫線處填寫(xiě)合適內(nèi)容（每空1分，共”分）1實(shí)例2基類(lèi)派生類(lèi)（或子類(lèi)）4鏈接指針5p-Link=top;=p;6重?cái)?shù)。118446

5、12。稀疏三、判斷題，在每小題后面的括號(hào)內(nèi)打?qū)μ?hào)表示正確或打叉號(hào)表示錯(cuò)誤（每小題1分，共12分）TOC o 1-5 h z1算法和程序都應(yīng)具有下面些特征：有輸入，有輸出，確定性，有窮性，有效性。()2用字符數(shù)組存儲(chǔ)長(zhǎng)度為的字符串，數(shù)組長(zhǎng)度至少為n+1()3在用循環(huán)單鏈表表示的鏈?zhǔn)疥?duì)列中，可以不設(shè)隊(duì)頭指針，僅在鏈尾設(shè)置隊(duì)尾指針()4個(gè)廣義表的表尾總是一個(gè)表()5在樹(shù)的存儲(chǔ)中，若使每個(gè)結(jié)點(diǎn)帶有指向雙親結(jié)點(diǎn)的指針將在算法中為尋找雙親結(jié)點(diǎn)帶來(lái)方便()6假定有兩個(gè)用單鏈有序表表示的集合，則這兩個(gè)集合的交運(yùn)算可得到一個(gè)新的集合單鏈表，其長(zhǎng)度小于等于參加運(yùn)算的任意個(gè)集合單鏈表的長(zhǎng)度()7鄰按矩陣適用于稀疏圖

6、(邊數(shù)遠(yuǎn)小于頂點(diǎn)數(shù)的平方)，鄰接表適用于稠密圖(邊數(shù)接近于頂點(diǎn)數(shù)的平方)()8對(duì)一個(gè)無(wú)向連通圖進(jìn)行一次深度優(yōu)先搜索可以追訪圖中的所有頂點(diǎn)()9在任何情況，快速排序需要進(jìn)行關(guān)鍵碼比較的次數(shù)都是0在索引順序結(jié)構(gòu)的搜索中對(duì)索引表既可以采取順序搜索，也可以采用折半搜索()1對(duì)于一棵具有個(gè)結(jié)點(diǎn)。高度為的任何二叉樹(shù)，進(jìn)行任一種次序遍歷的時(shí)間復(fù)雜度均為T(mén)OC o 1-5 h z12圖中各個(gè)頂點(diǎn)的編號(hào)是人為的，不是它本身固有的，因此可以根據(jù)需要進(jìn)行改變()計(jì)算機(jī)專(zhuān)業(yè)數(shù)據(jù)結(jié)構(gòu)試題答案及評(píng)分標(biāo)準(zhǔn)三、判斷題每(空1分，共12分)1錯(cuò)對(duì)23對(duì)4對(duì)5對(duì)對(duì)67錯(cuò)8對(duì)9錯(cuò)10對(duì)1錯(cuò)112對(duì)運(yùn)算題(每小題6分，共30分)1設(shè)

7、有一個(gè)的對(duì)稱(chēng)矩陣A將其上三角部分按行存放在一個(gè)一維數(shù)組中，存放于中，那么存放于中什么位置在中的存放位置：2有7個(gè)帶權(quán)結(jié)點(diǎn)，其權(quán)值分別為3，78，2，6，1中，1，4試以它們?yōu)槿~子結(jié)點(diǎn)生成一棵霍夫曼樹(shù)，求出該樹(shù)的帶權(quán)路徑長(zhǎng)度和高度，假定樹(shù)根的高度為中帶權(quán)路徑長(zhǎng)度：高度：3已知有向圖（）其中，,=，,，,，,，,c請(qǐng)問(wèn)該圖的鄰接表中，每個(gè)頂點(diǎn)單鏈表各有多少邊結(jié)點(diǎn)頂點(diǎn)：abcde邊結(jié)點(diǎn)數(shù)：4E知一個(gè)網(wǎng)絡(luò)的頂點(diǎn)集和邊集分別為：V=，1O，2，3，4，5，6，7；E=，20，1，3，14，24，2，5，36，3，7，4，7，5，7，67，）若存儲(chǔ)它采用鄰接表，并且每個(gè)頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號(hào)

8、即域的值從小到大的次序鏈接的，則按教材中介紹的進(jìn)行拓?fù)渑判虻乃惴?，?xiě)出得到的拓?fù)湫蛄校ㄌ崾荆合犬?huà)出對(duì)應(yīng)的圖形，然后再運(yùn)算）拓?fù)湫蛄校?已知有一個(gè)數(shù)據(jù)表為3，018，2，015，38，12，44，53，給出進(jìn)行歸并排序的過(guò)程中每一趟排序后的數(shù)據(jù)表的變化試題答案及評(píng)分標(biāo)準(zhǔn)四、運(yùn)算題(每小題6分，共30分)43答案說(shuō)明：根據(jù)題意，矩陣中當(dāng)元素下標(biāo)與滿足W時(shí)，任意元素在一維數(shù)組中的存放位置為2一一*+因此，在數(shù)組中的位置為：(2*1501)*52+8=432帶權(quán)路徑長(zhǎng)度：13，1高度：43評(píng)分標(biāo)準(zhǔn)：每個(gè)數(shù)據(jù)對(duì)給1分，全對(duì)給6分頂點(diǎn)：abcde邊結(jié)點(diǎn)數(shù)：112124評(píng)分標(biāo)準(zhǔn)；若與答案完全相同得6分，若仍

9、為一種拓?fù)湫蛄杏玫?分，其他用酌情處理拓?fù)湫蛄校?，3，6，0，2，5，4，7。分步給分算法分析題每（小題6分，共18分）設(shè)字符串類(lèi)具有下列操作：t計(jì)算字符串的長(zhǎng)度ca；aa提取字符串第個(gè)字符的值若字符串a(chǎn)的值為“ababcabcacbab，a的值為“abcac”，（1給）出下面算法執(zhí)行后返回的結(jié)果，（2給）出下面算法的功能。includeString,hintunknown（String&Tar,S返回結(jié)果：算法功能：2已知二叉樹(shù)中的結(jié)點(diǎn)類(lèi)型定義為:其中為結(jié)點(diǎn)值域，和分別為指向左、右子女結(jié)點(diǎn)的指針域下面函數(shù)的功能是返回二叉樹(shù)中值為的結(jié)點(diǎn)所在的層號(hào)根據(jù)題意按標(biāo)號(hào)把合適的內(nèi)容填寫(xiě)到算法后面相應(yīng)標(biāo)

10、號(hào)的位置.intNodeLevel(BinTreeNode*空樹(shù)的層號(hào)為根結(jié)點(diǎn)的層號(hào)為向子樹(shù)中查找結(jié)點(diǎn)若樹(shù)中不存在結(jié)點(diǎn)則返回假定一個(gè)有向無(wú)權(quán)圖采用鄰接矩陣存儲(chǔ)，請(qǐng)指出下面算法的功能。為圖中的頂點(diǎn)數(shù)為圖中的邊數(shù)算法功能：計(jì)算機(jī)專(zhuān)業(yè)數(shù)據(jù)結(jié)構(gòu)試題答案及評(píng)分標(biāo)準(zhǔn)五、算法分析題(每小題6分，共18分)1.返回結(jié)果，5算法功能：字符串的模式匹配算法(1)returncl+l;NodeLeve，lX()BT-rightc2=0從有向無(wú)權(quán)圖中刪除與頂點(diǎn)相連的所有邊，包括出邊和入邊。算法設(shè)計(jì)題(每小題6分共12分)1請(qǐng)寫(xiě)出在循環(huán)隊(duì)列上進(jìn)行插入操作的算法。要求若插入成功則返目u否則返回s循環(huán)隊(duì)列定義如下：為已定義過(guò)的整型常量，表示隊(duì)列數(shù)組空間長(zhǎng)度指向隊(duì)尾元素后一個(gè)位置，指向隊(duì)頭元索/fr注意：當(dāng)且時(shí)，隊(duì)列空，當(dāng)且=時(shí)，隊(duì)列滿，即隊(duì)列中已有個(gè)元素.oolEnCQueue(