全國2009年1月自考數(shù)據(jù)結構導論考試試題,答案,筆記.doc

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