資料結構隨堂測驗

假設在鏈結串列(linked list)類別中有兩指標 first及last，分别指向串列的第一及最後一個元素，試問欲找出串列中最後一個元素所需時間複雜度?

• O(n)

• θ(n)

• θ(n/2)

• O(1)

鏈結串列(Linked List)資料結構在哪一項操作上的效率不如陣列資料結構？

• 在現有資料中間插入一筆資料

• 從現有資料中刪除一筆資料

• 隨機讀取任一元素的資料

• 以上處理效率皆不如陣列

有關以陣列(Array)及鏈結串列(Linked List)方式實作佇列(Queue)之敘述，何者不正確？

• Array 方式在處理上，受宣告時 Array 大小之限制

• Array 方式在儲存相同元素時所用之空間較大

• Linked List 方式，其佇列(Queue)之大小較不受限制

• Linked List 方式需要用到指標方法

關於鏈結串列(Linked List)之敘述，下列何者錯誤？

• 任何型態的鏈結串列，串列中的元素只能記錄下一筆資料的位址，不可記錄前一筆資料的位址

• 鏈結串列中的前後資料存放在記憶體中，可能是不相鄰而散亂在各處

• 記錄相同數量的資料，使用鏈結串列會比使用陣列(Array)需要更多的記憶體空間

• 若將鏈結串列中的最後一個元素指向第一個元素，就可成一個環狀串列，並可用來表示有循環性的資料

有關陣列(Array)與鏈結串列(Linked List)兩者之間的比較，下列何者正確？

• Linked List 的優點是可以直接存取任何一個成員，所以存取速度快。

• Array 可以用來模擬 Linked List，而 Linked List 也可以用來模擬 Array

• 使用 Linked List 的好處是：只要先宣告指標變數即可，要使用空間時再向系統要求所需的空間，所以不會浪費。

• Array 的優點做 Insert、Delete 時不需要搬移大量的成員。

在鏈結串列(Linked List)的資料結構中，假設 head 是指向一個串列的頭的指標，next是用來指向下一個串列元件的指標。現在有一個新增的元件為 p，要加到此串列的最前頭，則下列何者為正確的步驟？

• p→next = head；

  head = p；

• head = p；

  p→next = head→next；

• head→next = p；

• p→next = head→next；

  head = p；

如圖所示，若要將新節點 R 插入到節點 P 與節點 Q 之間，下列敘述何者應優先執行？

• R = Q

• R→link = P→link

• R = P

• P→link = R

如圖所示，若要將節點 Q 刪除，下列敘述何者應優先執行？

• P = Q→link

• P→link = Q

• free(Q)

• P→link = Q→link