全國2002年10月高等教育自學考試

數據結構導論試題

課程代碼：02142

一、單項選擇題(在下列每小題四個備選答案中選出一個正確答案，并將其字母標號填入題干的括號內。每小題2分，共30分)

1．下列數據組織形式中，（      ）的結點按邏輯關系依次排列形成一個“鎖鏈”。

A.集合         B.樹形結構

C.線性結構        D.圖狀結構

2．數據結構可以形式化地定義為（S，△），其中S指某種邏輯結構，△是指（      ）

A.S上的算法       B.S的存儲結構

C.在S上的一個基本運算集    D.在S上的所有數據元素

3．下列說法正確的是（      ）

A.線性表的邏輯順序與存儲順序總是一致的

B.線性表的鏈式存儲結構中，要求內存中可用的存儲單元可以是連續的，也可以不連續

C.線性表的線性存儲結構優于鏈式存儲結構

D.每種數據結構都具有插入、刪除和查找三種基本運算

4．設非空單鏈表的數據域為data，指針域為next，指針p指向單鏈表中第i個結點，s指向已生成的新結點，現將s結點插入到單鏈表中，使其成為第i個結點，下列算法段能正確完成上述要求的是（      ）

A.s->next=p->next;p->next=s；

B.p->next=s;s->next=p->next；

C.s->next=p->next;p->next=s;交換p->data和s->data；

D.p=s;s->next=p；

5．稀疏矩陣一般采用（      ）方法壓縮存儲。

A.三維數組       B.單鏈表

C.三元組表       D.散列表

6．樹若用雙親鏈表表示，則（      ）

A.可容易地實現求雙親及子孫的運算

B.求雙親及子孫的運算均較困難

C.可容易地實現求雙親運算，但求子孫運算較困難

D.可容易地實現求子孫運算，但求雙親運算較困難

7．將一棵有50個結點的完全二叉樹按層編號，則對編號為25的結點x，該結點（      ）

A.無左、右孩子

B.有左孩子，無右孩子

C.有右孩子，無左孩子

D.有左、右孩子

8．用鄰接表作為有向圖G的存儲結構。設有n個結點、e條弧，則拓撲排序的時間復雜度為（      ）

A.O(n)        B.O(n+e)

C.O(e)        D.O(n*e)

9．如果從無向圖的任一頂點出發進行一次深度優先搜索即可訪問所有頂點，則該圖一定是（      ）

A.完全圖       B.連通圖

C.有回路       D.一棵樹