全國2007年1月高等教育自學考試

數據結構導論試題

課程代碼：02142

一、單項選擇題(本大題共15小題，每小題2分，共30分)

在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內。錯選、多選或未選均無分。

1．關于棧和隊列的說法中正確的是（     ）

A．棧和隊列都是線性結構

B.棧是線性結構，隊列不是線性結構

C.棧不是線性結構，隊列是線性結構

D.棧和隊列都不是線性結構

2．關于存儲相同數據元素的說法中正確的是（     ）

A．順序存儲比鏈式存儲少占空間

B.順序存儲比鏈式存儲多占空間

C.順序存儲和鏈式存儲都要求占用整塊存儲空間

D.鏈式存儲比順序存儲難于擴充空間

3．從邏輯關系來看，數據元素的直接前驅為0個或1個的數據結構只能是（     ）

A．線性結構 B.樹形結構

C.線性結構和樹型結構 D.線性結構和圖狀結構

4．已知一個單鏈表中，指針q指向指針p的前趨結點，若在指針q所指結點和指針p所指結點之間插入指針s所指結點，則需執行（     ）

A．q→next=s；p→next=s； B.q→next=s；s→next=p；

C.q→next=s；q→next=p； D.q→next=s；s→next=q；

5．在長度為n的線性表中刪除一個指針p所指結點的時間復雜度是（     ）

A．O(n) B.O(1)

C.O(log₂n) D.O(n²)

6．設一個棧的輸入序列是a，b，c，d，則所得到的輸出序列（輸入過程中允許出棧）不可能出現的是（     ）

A．a，b，c，d B.a，b，d，c

C.d，c，b，a D.c，d，a，b