全國2014年4月02142數(shù)據(jù)結(jié)構(gòu)導(dǎo)論自考試題

絕密★考試結(jié)束前

20144月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題課程代碼：02142請考生按規(guī)定用筆將所有試題的答案涂、寫在答題紙上。選擇題部分注意事項：筆填寫在答題紙規(guī)定的位置上。每小題選出答案后，用2B橡皮擦干凈后，再選涂其他答案標(biāo)號。不能答在試題卷上。一、單項選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個備選項中只有一個是符合題目要求的，請將其選出并將“答題紙”的相應(yīng)代碼涂黑。錯涂、多涂或未涂均無分。下列幾種算法時間復(fù)雜度中，最小的是A.O(logn)2C.O(n2)

B.O(n)D.O(1)數(shù)據(jù)的存儲方式中除了順序存儲方式和鏈?zhǔn)酱鎯Ψ绞街?，還有C.線性存儲方式和索引存儲方式

線性存儲方式和散列存儲方式D.表長為n的順序表中做刪除運算的平均時間復(fù)雜度為A.O(1)C.O(n)

B.O(logn)2D.O(n2)查找值為x的平均時間復(fù)雜度為A.O(1)C.O(n)

B.O(logn)2D.O(n2)元素的進(jìn)棧次序為A，B，C，D，E，出棧的第一個元素為E，則第四個出棧的元素為A.D B.CC.B D.A帶頭結(jié)點的鏈隊列中，隊列頭和隊列尾指針分別為frontrear，則判斷隊列空的條件為A.front==rearC.rear!==NULL5的二叉樹，結(jié)點個數(shù)最多為A.31個C.63個

B.front!=NULLD.front==NULLB.32個D.64個如果結(jié)點A2個兄弟結(jié)點，結(jié)點B為A的雙親，則B的度為A.1C.4

B.3D.59.將題9圖所示的一棵樹轉(zhuǎn)換為二叉樹，結(jié)點C是A.A的左孩子B.A的右孩子C.B的右孩子D.E的右孩子10.n為圖的頂點個數(shù)，e為圖中弧的數(shù)目，則圖的拓?fù)渑判蛩惴ǖ臅r間復(fù)雜度為A.O(n)C.O(n-e)A.對角矩陣C.上三角矩陣

B.O(e)D.O(n+e)B.稀疏矩陣D.對稱矩陣101個元素的順序表中查找值為x的元素結(jié)點時，平均比較元素的次數(shù)為A.50C.100

B.51D.101構(gòu)造散列函數(shù)的方法很多，常用的構(gòu)造方法有A.B.線性探測法、二次探測法、除留余數(shù)法C.線性探測法、除留余數(shù)法、鏈地址法D.線性探測法、二次探測法、鏈地址法就平均時間性能而言，快速排序方法最佳，其時間復(fù)雜度為A.O(n)C.O(n2)A.直接插入排序C.堆排序

B.O(nlogn)2D.O(1ogn)2B.冒泡排序D.歸并排序非選擇題部分注意事項：用黑色字跡的簽字筆或鋼筆將答案寫在答題紙上，不能答在試題卷上。二、填空題(本大題共13小題，每小題2分，共26分)數(shù)據(jù)的基本單位。雙向循環(huán)鏈表中，在p所指結(jié)點的后面插入一個新結(jié)需要修改四個指針，分別t->prior=；t->next=p->nex； ；p->next=。在帶有頭結(jié)點的循環(huán)鏈表中，尾指針為rear，判斷指針P所指結(jié)點為首結(jié)點的條件是 。若線性表中最常用的操作是求表長和讀表元素，則順序表和鏈表這兩種存儲方式中，節(jié)省時間的。不含任何數(shù)據(jù)元素的棧稱。稀疏矩陣一般采用的壓縮存儲方法。22.100個結(jié)點的二叉樹采用二叉鏈表存儲時用來指向左右孩子結(jié)點的指針域 個。23.已知完全二叉樹的第5層有5個結(jié)點，則整個完全二叉樹個結(jié)點。24.n個頂點的有向圖G用鄰接矩陣A[1..n，1..n]存儲，其第i列的所有元素之和等于頂點V的 。i具有10個頂點的有向完全圖的弧數(shù)為 ?！艾F(xiàn)象，通常采用

解決沖突。在長度為n的帶有崗哨的順序表中進(jìn)行順序查找，查找不成功時，與關(guān)鍵字的比較次為 。歸并排序算法的時間復(fù)雜度。三、應(yīng)用題(本大題共5小題，每小題6分，共30分)稀疏矩陣A29圖所示，寫出該稀疏矩陣A的三元組表示法。設(shè)二叉樹的中序遍歷序列為BDCEAFHG，后序遍歷序列為樹。31圖所示無向圖的鄰接矩陣，并寫出每個頂點的度。題31圖013，散列函數(shù)H(k)=kmod11，(mod)，待散列序列為理沖突的過程。33.將一組鍵值(80，50，65，13，86，35，96，57，39，79，59，15)應(yīng)用二路歸并排序算法從小到大排序，試寫出各趟的結(jié)果。四、算法設(shè)計題(本大題共2小題，每小題7分，共14分)設(shè)單鏈表及鏈棧S的結(jié)構(gòu)定義如下：typedefstructnode{DataTypestruct｝linkstack；編寫一個算法voidReverseList(1inkstackS將帶頭結(jié)點單鏈表head中序號(a，a，a1 2 3a，a，a)，逆置后變?yōu)?a