1、吉大18春學期數據結構在線作業一-0005試卷總分:100 得分:100一、單選題 (共 10 道試題,共 40 分)在單鏈表中，刪除p所指結點的直接后繼的操作是( )p-next=p-next-next;p=p-next;p-next=p-next-next;p-next=p-next;p=p-next-next;答案:A2.單鏈表中，增加頭結點的目的是為了( )。方便運算的實現用于標識單鏈表使單鏈表中至少有一個結點用于標識起始結點的位置答案:A3.任何一顆二叉樹的葉結點在其先根、中根、后跟遍歷序列中的相對位置( )?？隙òl生變化有時發生變化肯定不發生變化無法確定答案:C4.在圖的鄰接表存儲

2、結構上執行深度優先搜索遍歷類似于二叉樹上的( )。先根遍歷中根遍歷后根遍歷按層次遍歷答案:A5.非空的循環單鏈表head的尾結點(由指針p所指)滿足( )。p-next=NULLp=NULLp-next=headp=head答案:C6.在具有n個單元的循環隊列中，隊滿共有_個元素。nn-1n+1n+2答案:B7.深度為6的二叉樹最多有( )個結點。64633231答案:B8.帶頭結點的單鏈表head為空的判斷條件是()。head=NULLhead-next=NULLhead-next=headhead!=NULL答案:B9.含n個頂點的連通圖中的任意一條簡單路徑，其長度不可能超過( )。1n/

3、2n-1n答案:C10.在 一個單鏈表中，已知q所指結點是p所指結點的直接前趨，若在p,q之間插入s結點，這執行（ ）操作。s-next=p-next;p-next=sq-next=s;s-next=pp-next=s-next;s-next=p;p-next=s;s-next=q;答案:B二、多選題 (共 5 道試題,共 20 分)11.圖的存儲結構有（）鄰接矩陣鄰接表數組表示法十字鏈表答案:ABCD12.二叉樹的遍歷方式有（）先根遍歷中根遍歷后根遍歷深度遍歷答案:ABC13.遞歸過程中要保存的信息包括（ ）返回地址本次調用中與形參結合的實參值本次遞歸調用中的局部變量值執行結果答案:ABC1

4、4.屬于插入排序的排序方法有（）直接插入排序對半插入排序漸減增量排序冒泡排序答案:ABC15.一個好的算法應具備以下性質（ ）正確性可讀性穩健性有窮性答案:ABCD三、判斷題 (共 10 道試題,共 40 分)16.設有兩個串p和q，求q在p中首次出現的位置的運算稱作模式匹配答案:正確17.快速排序的速度在所有排序方法中為最快，而且所需附加空間也最少答案:錯誤18.不是所有的AOV網都有一個拓樸序列答案:正確19.對于前序遍歷和中序遍歷結果相同的二叉樹為所有結點只有右孩子的二叉樹答案:正確20.算法和程序沒有區別，所以在數據結構中二者是通用的。( )答案:錯誤21.判斷一個表達式中左右括號是否匹配，采用棧實現較為方便答案:正確22.鄰接多重表示法對于有向圖和無向圖的存儲都適用答案:正確23.從未排序的序列中依次取出一個元素與已排序序列中的元素進行比較，然后將其放在已排序序列的合適位置上，該排序方法稱為插入排序答案:正確24.在最好和最壞情況下的時間復雜度均為O(