資料結構的觀念問題

1.In a (randomized) skip list with n entries the expected space complexity is O(n^2)

2.An edge in a graph is a self loop if it has the same end vertices.

3.A list-based queue takes O(n) time for dequeue() and enqueue() when the first element of the queue is implemented as the tail of the singly linked list.

4.A list-based stack takes O(n) time for push(k) and pop() when the top of the stack is implemented as the tail of the singly linked list.

5.A “static” variable in Java is declared as a variable that is associated with an individual instance (object) of the class.

6.A graph consists of a set of vertices and a set of edges; both can be used to store elements.

想請教這五題是非題,因為我沒有答案,但自己觀念好像都不是很正確

故想請教各位高手

我是寫X O X X O O

第一題因為我沒學過,我看到有O(n)和O(n log n)的說法,想請教一下

第二題的self loop是不是就是指cycle呢?

第三、四題我不太懂 "implemented as the tail of the singly linked list."這邊的意思,請問這段話是什麼意思?

第五題我不太確定

第六題意思應該是 G = (V,E) 有一組頂點集合和邊集合,前面敘述應該是對的,但後面都可以用來存值的意思是??

不好意思 麻煩了,謝謝

3 個解答

評分
  • sponge
    Lv 6
    5 年前
    最佳解答

    1. X

    根據參考資料,它的空間複雜度也不會到 O(n^2)

    O(n) 是「平均」狀況,也就是考慮各種隨機出來的儲存結果

    因為 skip list 為機率式結構,所以每次建立的 list 皆不同

    但將所有可能狀況取平均即 O(n)

    這些狀況中最差者稱為 worst case, 需要空間 O(n log n)

    2. O

    self loop 是 cycle 的一個特例

    cycle 兩端點一樣但中間可經過某些點

    self loop 中間不經任何點,是長度 1 的 cycle

    3. X

    您有問題那句話意指 queue 的第一個元素落在 singly linked list 的尾部

    enqueue 將資料由 queue 後面推入,即從 list 的 head 加入

    dequeue 將資料由 queue 前面彈出,即從 list 的 tail 去除

    singly linked 特性為存取 head 只需 O(1), 存取 tail 需 O(n) 時間

    4. O

    此題 stack top 落在 list 的 tail, push 和 pop 都存取 stack top

    因此這種做法二者都要時間 O(n)

    5. X

    題意為,static 變數指的是那些與物件實例有關的變數

    static 變數應該只與類別有關,所有該類別的物件共用相同的參考

    簡言之 static 變數只佔有一個固定位置讓大家存取

    而非 member 是每個物件將自己的成員放在屬於自己的空間

    6. X

    圖內的邊代表的是「點與點間的關係」

    element 資料存在圖上的每個點中

    所以邊上存放的應為 attribute 比如 cost, 而非 element

    希望如上解釋對您有幫助!

  • 5 年前

    社會人士 自己從頭開始自己學 原本不是相關科系

  • 5 年前

    問同學比較快

    去吧

還有問題?馬上發問,尋求解答。