福師?數據結構概論?在線作業一答案試卷總分：100測試時間：--一、單項選擇題〔共25道試題，共50分。〕1.最大容量為n的循環隊列，隊尾指針是rear，隊頭是front，那么隊空的條件是〔〕A.(rear+1)MODn=frontB.rear=frontC.rear+1=frontD.(rear-l)MODn=front總分值：2分2.由3個結點可以構造出多少種不同的有向樹？〔〕A.2B.3C.4D.5總分值：2分3.棧和隊都是〔〕A.順序存儲的B.線性結構C.鏈式存儲的D.非線性結構總分值：2分4.下面表達正確的選項是〔〕A.算法的執行效率與數據的存儲結構無關B.算法的空間復雜度是指算法程序中指令(或語句)的條數C.算法的有窮性是指算法必須能在執行有限個步驟之后終止D.以上三種描述都不對總分值：2分5.對關鍵碼序列28，16，32，12，60，2，5，72快速排序，從小到大一次劃分結果為〔〕。A.(2,5,12,16)26(60,32,72)B.(5,16,2,12)28(60,32,72)C.(2,16,12,5)28(60,32,72)D.(5,16,2,12)28(32,60,72)總分值：2分6.設計一個判別表達式中左，右括號是否配對出現的算法，采用〔〕數據結構最正確。A.線性表的順序存儲結構B.隊列C.線性表的鏈式存儲結構D.棧總分值：2分7.假設串S=’software’,其子串的數目是〔〕。A.8B.37C.36D.9總分值：2分8.假設用冒泡排序方法對序列{10,14,26,29,41,52}從大到小排序，需進行〔〕次比擬。A.3B.10C.15D.25總分值：2分9.假設要求盡可能快地對序列進行穩定的排序，那么應選〔〕A.快速排序B.歸并排序C.冒泡排序D.堆總分值：2分10.如果要求一個線性表既能較快的查找，又能適應動態變化的要求，那么可采用()查找法。A.分快查找B.順序查找C.折半查找D.基于屬性總分值：2分11.廣義表運算式Tail(((a,b),(c,d)))的操作結果是〔〕A.(c,d)B.c,dC.((c,d))D.d總分值：2分12.在下面的排序方法中，輔助空間為O〔n〕的是〔〕A.希爾排序B.堆排序C.選擇排序D.歸并排序總分值：2分13.以下數據結構中〔〕是非線性數據結構A.樹B.字符串C.隊D.棧總分值：2分14.假設長度為n的線性表采用順序存儲結構，在其第i個位置插入一個新元素的算法的時間復雜度〔〕(1<=i<=n+1)。A.O(0)B.O(1)C.O(n)D.O(n2)總分值：2分15.設樹T的度為4，其中度為1，2，3和4的結點個數分別為4，2，1，1那么T中的葉子數為〔〕A.5B.6C.7D.8總分值：2分16.散列函數有一個共同的性質，即函數值應當以()取其值域的每個值。A.最大概率B.最小概率C.平均概率D.同等概率總分值：2分17.在下面的排序方法中，輔助空間為O〔n〕的是()A.希爾排序B.堆排序C.選擇排序D.歸并排序總分值：2分18.設森林F對應的二叉樹為B，它有m個結點，B的根為p,p的右子樹結點個數為n,森林F中第一棵樹的結點個數是〔〕A.m-nB.m-n-1C.n+1D.條件缺乏，無法確定總分值：2分19.求解最短路徑的Floyd算法的時間復雜度為()。A.O〔n〕B.O〔n+c〕C.O〔n*n〕D.O〔n*n*n〕總分值：2分20.以下排序算法中，占用輔助空間最多的是：()A.歸并排序B.快速排序C.希爾排序D.堆排序總分值：2分21.假設二叉樹采用二叉鏈表存儲結構，要交換其所有分支結點左、右子樹的位置，利用〔〕遍歷方法最適宜。A.前序B.中序C.后序D.按層次總分值：2分22.輸入序列為ABC，可以變為CBA時，經過的棧操作為〔〕A.push,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop總分值：2分23.設無向圖的頂點個數為n，那么該圖最多有〔〕條邊。A.n-1B.n(n-1)/2C.n(n+1)/2D.0總分值：2分24.要連通具有n個頂點的有向圖，至少需要〔〕條邊。A.n-lB.nC.n+lD.2n總分值：2分25.具有12個關鍵字的有序表，折半查找的平均查找長度〔〕A.3.1B.4C.2.5D.5總分值：2分二、判斷題〔共20道試題，共40分。〕1.二叉樹是度為2的有序樹〔〕A.錯誤B.正確總分值：2分2.集合與線性表的區別在于是否按關鍵字排序。A.錯誤B.正確總分值：2分3.隊列邏輯上是一個下端和上端既能增加又能減少的線性表〔〕。A.錯誤B.正確總分值：2分4.順序存儲方式只能用于存儲線性結構。A.錯誤B.正確總分值：2分5.采用二叉鏈表作存儲結構，樹的前序遍歷和其相應的二叉樹的前序遍歷的結果是一樣的A.錯誤B.正確總分值：2分6.二叉樹的遍歷結果不是唯一的〔〕A.錯誤B.正確總分值：2分7.線性表采用鏈表存儲時，結點和結點內部的存儲空間可以是不連續的〔〕A.錯誤B.正確總分值：2分8.隊列邏輯上是一個下端和上端既能增加又能減少的線性表。A.錯誤B.正確總分值：2分9.線性表采用鏈表存儲時，結點和結點內部的存儲空間可以是不連續的。A.錯誤B.正確總分值：2分10.任一查找樹(二叉分類樹)的平均查找時間都小于用順序查找法查找同樣結點的線性表的平均查找時間〔〕A.錯誤B.正確總分值：2分11.排序的穩定性是指排序算法中的比擬次數保持不變，且算法能夠終止A.錯誤B.正確總分值：2分12.對任何數據結構鏈式存儲結構一定優于順序存儲結構〔〕。A.錯誤B.正確總分值：2分13.用一維數組存儲二叉樹時，總是以前序遍歷順序存儲結點。A.錯誤B.正確總分值：2分14.順序查找法適用于存儲結構為順序或鏈接存儲的線性表〔〕A.錯誤B.正確總分值：2分15.當待排序的元素很大時，為了交換元素的位置，移動元素要占用較多的時間，這是影響時間復雜度的主要因素A.錯誤B.正確總分值：2分16.在執行某個排序算法過程中，出現了排序碼朝著最終排序序列位置相反方向移動，那么該算法是不穩定的。A.錯誤B.正確總分值：2分17.廣義表中的元素或者是一個不可分割的原子，或者是一個非空的廣義表。A.錯誤B.正確總分值：2分18.二叉樹以后序遍歷序列與前序遍歷序列反映的同樣的信息(他們反映的信息不獨立〕〔〕A.錯誤B.正確總分值：2分19.對一棵二叉樹進行層次遍歷時，應借助于一個棧A.錯誤B.正確總分值：2分20.當待排序記錄已經從小到大排序或者已經從大到小排序時，快速排序的執行時間最省。A.錯誤B.正確總分值：2分三、多項選擇題〔共5道試題，共10分。〕1.有關二叉樹以下說法不正確的選項是〔〕A.二叉樹的度為2B.一棵二叉樹的度可以小于2C.二叉樹中至少有一個結點的度為2D.二叉樹中任何一個結點的度都為2總分值：2分2.下面關于求關鍵路徑的說法正確的選項是〔〕。A.求關鍵路徑是以拓撲排序為根底的B.．一個事件的最早開始時間同以該事件為尾的弧的活動最早開始時間相同C.一個事件的最遲開始時間為以該事件為尾的弧的活動最遲開始時間與該活動的持續時間的差D.關鍵活動一定位于關鍵路徑上總分值：2分3.下面關于二分查找的表達不正確的選項是〔〕A.表必須有序，表可以順序方式存儲，也可以鏈表方式存儲B.表必須有序，而且只能從小到大排列C.表必須有序且表中數據必須是整型，實型或字符型D.表必須有序