全國(guó)2009年1月自考數(shù)據(jù)結(jié)構(gòu)導(dǎo)論考試試題,答案,筆記.doc

全國(guó)2009年1月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題課程代碼：02142一、單項(xiàng)選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫(xiě)在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無(wú)分。1.數(shù)據(jù)的不可分割的最小標(biāo)識(shí)單位是（ A ）A.數(shù)據(jù)項(xiàng) B.數(shù)據(jù)記錄C.數(shù)據(jù)元素(數(shù)據(jù)和運(yùn)算基本單位)D.數(shù)據(jù)變量2. for（i=0；im；i+）for（j=0；jt；j+）cij=0；for（i=0；im；i+）for（j=0；jt；j+）for（k=0；knext=pnextnext（下一個(gè)，下一個(gè)原則）B.p=pnextC.p=pnextnextD.pnext=pHsSHs5.向一個(gè)棧頂指針為hs的鏈棧中插入一個(gè)*s結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行的操作為（ B ）A.hsnext=s；B.snext=hs；hs=s；（下一個(gè)，賦值原則）C.snext=hsnext；hsnext=s；D.snext=hs；hs=hsnext；6.設(shè)循環(huán)隊(duì)列的元素存放在一維數(shù)組Q030中，隊(duì)列非空時(shí)，front指示隊(duì)頭元素的前一個(gè)位置，rear指示隊(duì)尾元素。如果隊(duì)列中元素的個(gè)數(shù)為11，front的值為25，則rear應(yīng)指向的元素是（ A ）A.Q4B.Q5C.Q14D.Q15 30-25-1=47.定義二維數(shù)組A18，010，起始地址為L(zhǎng)OC，每個(gè)元素占2L個(gè)存儲(chǔ)單元，在以行序?yàn)橹餍虻拇鎯?chǔ)方式下，某數(shù)據(jù)元素的地址為L(zhǎng)OC+50L，則在以列序?yàn)橹餍虻拇鎯?chǔ)方式下，該元素的存儲(chǔ)地址為（ D ）具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)1. 有n-1個(gè)孩子2. 有n+1空指域NULL3. 有2n個(gè)指針域A.LOC+28LB.LOC+36LC.LOC+50LD.LOC+52L8.具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，擁有指向孩子結(jié)點(diǎn)的分支數(shù)目是（ A ）A.n-1B.nC.n+1（指針域?yàn)镹ULL）D.2n（指針域）9.對(duì)一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)按層序編號(hào)，則編號(hào)為49的結(jié)點(diǎn)，它的左孩子的編號(hào)為（ B ）1. 若，m*2n,則無(wú)左孩子2. 若，m*2+1n,則無(wú)右孩子。若有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)；1. 已知編號(hào)m2. 其左孩子為m*23. 其右孩子為m*2+1A.99B.98（49*2）C.97D.5010.有m個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)，其結(jié)點(diǎn)總數(shù)是（ A ）A.2m-1B.2mC.2m+1D.2（m+1）11.有n個(gè)結(jié)點(diǎn)的無(wú)向圖的邊數(shù)最多為（ B ）A.n+1B.C.n（n+1）D.2n（n+1） 注：有向圖為：n*（n1）0 1 2 1 0 32 3 012.設(shè)圖的鄰接矩陣為，則該圖為（ A ）A.有向圖（雜亂矩陣）B.無(wú)向圖（為對(duì)稱(chēng)矩陣）如：C.強(qiáng)連通圖D.完全圖13.二分查找算法的時(shí)間復(fù)雜度是（ D ）A.O（n2）（冒泡排序（平均復(fù)雜時(shí)間程度） B.O（nlog2n） （快速排序）C.O（n）（冒泡排序（最好情況下時(shí)間復(fù)雜程度）D.O（log2n）14.已知8個(gè)元素（34，76，45，18，26，54，92，65），按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹(shù)，則該樹(shù)的深度為（ B ）A.4B.5 注：1.二次排序樹(shù)的規(guī)則：C.6D.7 左小又大，連續(xù)一致原則 規(guī)律：1. 左面的總小于右面的2. 差值最小原則 1 2 3 4 515.采用排序算法對(duì)n個(gè)元素進(jìn)行排序，其排序趟數(shù)肯定為n-1趟的排序方法是（ C ）A.插入和快速B.冒泡和快速C.選擇和插入D.選擇和冒泡二、填空題（本大題共13小題，每小題2分，共26分）請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無(wú)分。16.在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有順序存儲(chǔ)方式、鏈?zhǔn)酱鎯?chǔ)方式、_索引存儲(chǔ)方式 _和散列存儲(chǔ)方式等四種。17. 作為一個(gè)算法輸入的數(shù)據(jù)所含數(shù)據(jù)元素的數(shù)目，或與此數(shù)目有關(guān)的其他參數(shù)，稱(chēng)為 _算法輸入的規(guī)?；騿?wèn)題的規(guī)模_。18.在雙鏈表中，存儲(chǔ)一個(gè)結(jié)點(diǎn)有三個(gè)域，一個(gè)是數(shù)據(jù)域，另兩個(gè)是指針域，分別指向 _直接前趨_和 _直接后繼_。19.在有n個(gè)元素的鏈隊(duì)列中，入隊(duì)和出隊(duì)操作的時(shí)間復(fù)雜度分別為_(kāi)O（1）_和_O（n）_。20.在棧結(jié)構(gòu)中，允許插入的一端稱(chēng)為 _棧頂_；在隊(duì)列結(jié)構(gòu)中，允許插入的一端稱(chēng)為 _隊(duì)尾_。21.在循環(huán)隊(duì)列中，存儲(chǔ)空間為0n-1。設(shè)隊(duì)頭指針front指向隊(duì)頭元素前一個(gè)空閑元素，隊(duì)尾指針指向隊(duì)尾元素，那么其隊(duì)空標(biāo)志為rear=front，隊(duì)滿標(biāo)志為 _（rear+1）%maxsize=front_。22.深度為k的二叉樹(shù)至多有 _2k -1 _個(gè)結(jié)點(diǎn)，最少有 _2k-1_個(gè)結(jié)點(diǎn)。23.設(shè)有一稠密圖G，則G采用 _鄰接矩陣_存儲(chǔ)結(jié)構(gòu)較省空間。設(shè)有一稀疏圖G，則G采用 _鄰接表_存儲(chǔ)結(jié)構(gòu)較省空間。24.在一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x的結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較_（n+1）/2_個(gè)元素結(jié)點(diǎn)。25.假定對(duì)線性表R059進(jìn)行分塊檢索，共分為10塊，每塊長(zhǎng)度等于6。若檢索索引表和塊均用順序檢索的方法，則檢索每一個(gè)元素的平均檢索長(zhǎng) 度為_(kāi)9_。分塊查找的平均查找長(zhǎng)度為：ASLbs=1/2*(s/n+s)+1 ,其中，S表示為元素個(gè)總數(shù)。n，表示為每個(gè)塊中的元素。 1/2(60/6+6)+1=926.文件在外存儲(chǔ)器上的組織結(jié)構(gòu)主要有三種：順序文件、散列文件和索引文件，其中 _順序_特別適應(yīng)磁帶存儲(chǔ)器，也適應(yīng)磁盤(pán)存儲(chǔ)器。27.在插入排序、冒泡排序、快速排序、歸并排序等排序算法中，占用輔助空間最多的是 _歸并排序_。28.冒泡排序最好的時(shí)間復(fù)雜度為 _O（n）_，平均時(shí)間復(fù)雜度為 _O（n2）_，是一種穩(wěn)定的排序算法。注：1.快速排序是不穩(wěn)定的，時(shí)間復(fù)雜度為：O（nlog2n）但在最壞情況下，近似于O（n2） 2.二分法的時(shí)間復(fù)雜程度為：O（log2n）三、應(yīng)用題（本大題共5小題，每小題6分，共30分）1. 解題過(guò)程：前：A B C D E F G 中：C B D A E G F 前：B C D 前：E F G 中：C B D 中：E G FC D 前：F G 中：G F29.已知一棵二叉樹(shù)的前序序列是ABCDEFG，中序序列是CBDAEGF。請(qǐng)構(gòu)造出該二叉樹(shù)，并給出該二叉樹(shù)的后序序列。答： 后序遍歷為：C D B G F E A解題說(shuō)明：1. 前序遍歷的第一個(gè)為“root”2. 后續(xù)遍歷的最后一個(gè)為“root”3. 中序遍歷為控制左右孩子的分界點(diǎn)。4. 總體思路：先找root，然后到對(duì)應(yīng)的中續(xù)遍歷或后續(xù)遍歷中找到該元素，對(duì)應(yīng)著該元素的左邊的所有元素到前序或者后續(xù)里找到對(duì)應(yīng)元素，再確定root，依次類(lèi)推即可。5. 前序：中左右 中續(xù)：左中右 后續(xù) ：左右中30.將題30圖所示的由三棵樹(shù)組成的森林轉(zhuǎn)化為一棵二叉樹(shù)。解題思路：1. 除保留第一個(gè)兄弟結(jié)點(diǎn)外，其它連接父節(jié)點(diǎn)的兄弟結(jié)點(diǎn)全部斷開(kāi)，變?yōu)槠湫值芙Y(jié)點(diǎn)的右孩子。（如紅箭頭所示）2. 為垂直線的順時(shí)針旋轉(zhuǎn)45度（不旋轉(zhuǎn)就擠到一起啦。）（如黃箭頭所示）3. 割裂后的結(jié)點(diǎn)，左孩子是誰(shuí)的，還是誰(shuí)的，不改變。（如綠箭頭）題30圖解： “”代表結(jié)束符號(hào)31.已知某圖的鄰接表存儲(chǔ)結(jié)構(gòu)如題31圖所示：注：解題思路：1.深度優(yōu)先搜索法是按照每一選定的頂點(diǎn)出發(fā)，走“一路到底原則”（但不能走相同路徑），但走完后包括所有節(jié)點(diǎn)。（選擇路徑不同，其最后結(jié)果不一樣，答案不唯一。）2.廣度優(yōu)先搜索法是指的從某點(diǎn)出發(fā)能夠輻射到的最大范圍選的點(diǎn)。題31圖（1） 畫(huà)出該圖。 （2）根據(jù)該鄰接表從頂點(diǎn)A出發(fā)，分別寫(xiě)出按深度優(yōu)先搜索法和廣度優(yōu)先搜索法進(jìn)行遍歷的結(jié)點(diǎn)序列。答：根據(jù)該鄰接表從頂點(diǎn)出發(fā)1.深度優(yōu)先搜索法為：A-B-C-F-G-H-E-D 2.廣度優(yōu)先搜索法為: A-B-D-C-E-F-H-G32.假定采用H（k）=k mod 7計(jì)算散列地址，引用線性探測(cè)的開(kāi)放定址法解決沖突，試在06的散列地址空間中，對(duì)關(guān)鍵字序列（38，25，74，63，52，48）構(gòu)造散列表，并求出等概率情況下查找成功的平均查找長(zhǎng)度。答：由題意可知關(guān)鍵字構(gòu)成的散列表如下圖。 下標(biāo) 0 1 2 3 4 5 6634838257452 探查次數(shù) 1 3 1 1 2 4等概況下的查找成功的平均查找長(zhǎng)度為：（1+3+1+1+2+4）/7=1.711. 題中給出多少長(zhǎng)度范圍，就有多少個(gè)空間。（注意，一般是從0開(kāi)始，所以有N+1個(gè)空格）2. 按照關(guān)鍵字順序依次進(jìn)行余數(shù)運(yùn)算。（題目已給出公式），按照余數(shù)放在對(duì)應(yīng)下表內(nèi)，若沖突，往后放。3. 注意，最后的次數(shù)算的是每一個(gè)格都要計(jì)算到的。33.用快速排序法對(duì)數(shù)據(jù)序列（49，38，65，97，16，53，134，27，39）進(jìn)行排序，寫(xiě)出其第一趟排序的全過(guò)程。答：初始關(guān)鍵字49 38 65 97 16 53 134 27 39 第1趟排序后3938271649 53 134 97 65 第2趟排序后16 38 27 3949 53 134 97 65第3趟排序后16 3827 3949 53 134 97 65第4趟排序后16 27 38 3949 53 134 97 65第5趟排序后16 27 38 39 49 53 134 97 65第6趟排序后16 27 38 39 49 53 65 97 134 第7趟排序后 16 27 38 39 49 53 65 97 134解題經(jīng)驗(yàn)：1. 對(duì)第一個(gè)數(shù)字初始2. 然后將這個(gè)數(shù)字與中間的數(shù)字進(jìn)行比較，若大于這個(gè)數(shù)字，那么這個(gè)數(shù)字往前推一個(gè)，若小于這個(gè)數(shù)字，那么這個(gè)數(shù)字往后退一個(gè)。3. 然后以關(guān)鍵字為分界點(diǎn)，1.若分界點(diǎn)左的數(shù)小于分界點(diǎn)，分界點(diǎn)右的數(shù)大于分界點(diǎn)，那么這個(gè)數(shù)字不動(dòng)。2.第三找出分界點(diǎn)左面大于分界點(diǎn)的數(shù)，按照從后往前的順序?qū)憽Ｔ僬页龇纸琰c(diǎn)右面的大于分界點(diǎn)的數(shù)，也是倒著寫(xiě)。4. 最后，分別對(duì)分好的塊前后比較，前大于后，調(diào)換，小于不動(dòng)，依次類(lèi)推。先左后右原則。四、算法設(shè)計(jì)題（本大題共2小題，每小題7分，共14分）34.完善下列折半插入排序算法。Void binasort（struct node rMAXSIZE，int n）for（i=2；i=n；i+）r0=ri；low=1；high=i-1；while（low=high）mid=（1）_(low+high)/2_；if（r0.key=low；j- -）（4）rhigh=_Aj+1=Aj_；rlow=r0 ；35.下列算法的功能是求出指定結(jié)點(diǎn)在給定的二叉排序樹(shù)中所在的層次。請(qǐng)完善該算法。Void