計概16-02佇列－公職試題

【選擇題】

【A】01.當鍵盤資料輸入時，系統正處於忙碌的狀態下，應採取下列那一種機制來達到鍵盤輸入緩衝(buffer)？ (A)先進先出的佇列緩衝 (B)後進先出的堆疊緩衝 (C)具可搶奪式的資料緩衝 (D)隨機選擇的雜湊緩衝。[109身心五等]

佇列是先進先出的有序串列，工作按先後順序來處理，如鍵盤輸入資料、印表機印表。

 

【D】02.一個空的佇列(queue)依序執行以下的動作後：enqueue(K), enqueue(M), enqueue(J), dequeue(), enqueue(N), dequeue(), enqueue(U)，則佇列中第一個元素為何？ (A)U (B)K (C)M (D)J。[109身心四等]

佇列：先進先出，由尾端加入資料，由頭端取出資料。

enqueue(K) → K

enqueue(M) → M K

enqueue(J) → J M K

dequeue() → J M

enqueue(N) → N J M

dequeue() → N J

enqueue(U) → U N J

 

【B】03.若以鏈結串列(Linked list)實作佇列(Queue)資料結構，則要在那裡插入一個新元素？ (A)在鏈結串列的開頭 (B)在鏈結串列的末尾 (C)在鏈結串列的中心位置 (D)依元素的值決定在鏈結串列的位置。[110地方四等電子]

佇列：先進先出(FIFO, First In First Out)由尾端加入資料，由頭端取出資料。

 

【C】04.計算機網路中的延遲效應，影響網路效能甚劇烈。有一串流媒體到達佇列的速率為V(packets/s)，連結的傳輸速率為R(bits/s)，每一封包含有L(bits)，試問該串流媒體的流量強度LV/R較合理的值為何？ (A)LV/R>2 (B)LV/R=1 (C)LV/R<1 (D)1<LV/R<2。[110國安五等]

LV/R不能大於1。若LV/R大於1，則位元到達佇列的平均速率超過從該佇列傳輸出去的速率，佇列的增加將趨於無界，並且排隊時延將趨向無窮大。

 

【B】05.作業系統的工作項目之一是對程序(process)使用I/O裝置做排程(scheduling)，藉由下列那一種資料結構的幫助，作業系統可讓等待時間越久的程序越先使用I/O裝置？ (A)I/O堆疊(stack) (B)I/O佇列(queue) (C)I/O雜湊表(hash table) (D)I/O二元樹(binary tree)。[111地方四等電子]

(B)I/O佇列：具有FIFO(First In First Out，先進先出)的性質。

 

【C】06.某一空佇列(queue)接收以下命令(虛擬碼)：insert 9, 1, 6, 4, 5，remove 3個，insert 6, 1, 5, 3之後，佇列由頭(head)往尾巴(tail)數的第2筆資料為何？ (A)1 (B)4 (C)5 (D)3。[111身心五等]

insert 9, 1, 6, 4, 5 → 9, 1, 6, 4, 5

remove 3個 → 4, 5

insert 6, 1, 5, 3 → 4, 5, 6, 1, 5, 3

 

【C】07.若佇列(Queue)的內容組態是：a、b、c、d(a在前端、d在尾端)。依序對佇列做插入(Enqueue)、取出(Dequeue)：Dequeue=>Dequeue=>Enqueue(e)=>Enqueue(f)。則佇列的最後組態為何？ (A)a、b、e、f(a在前端、f在尾端) (B)f、e、c、d(f在前端、d在尾端) (C)c、d、e、f(c在前端、f在尾端) (D)e、f、c、d(e在前端、d在尾端)。[112身心五等]

佇列取出a、b後，剩c(在前端)、d，插入e、f，最後組態為c、d、e、f

 

【A】08.佇列所使用的儲存策略(strategy)為何？ (A)先進先出(FIFO) (B)先進後出(FILO) (C)後進先出(LIFO) (D)只進不出(JINO)。[112身心五等]

佇列是先進先出的有序串列，工作按先後順序來處理。

 

【D】09.圖示用先廣後深搜尋法(Breadth-First Search)搜尋，當走訪優先權相同時，數字大的先走，走訪結果何者正確？ (A)12483657 (B)13786524 (C)12345678 (D)13276548。[112鐵路員級]