高考申論題
108年
[資訊處理] 程式語言
第 ⑶ 題
📖 題組：
下列為資料結構 List 的 Java 程式，而 ListTest 為測試類別（class），試回答以下問題：（35 分） class ListNode
{
T data;
ListNode nextNode;
ListNode(T object)
{
this(object, null);
}
ListNode(T object, ListNode node)
{
data = object;
nextNode = node;
}
T getData() { return data; } // 補全程式意涵
ListNode getNext() { return nextNode; } // 補全程式意涵
}
public class List
{
private ListNode firstNode;
private ListNode lastNode;
private String name;
public List()
{
this("list");
}
public List(String listName)
{
name = listName;
firstNode = lastNode = null;
}
public void insertAtFront(T insertItem)
{
if (isEmpty()) firstNode = lastNode = new ListNode(insertItem);
else firstNode = new ListNode(insertItem, firstNode);
}
public void insertAtBack(T insertItem) { /* 略 */ }
public T removeFromFront() throws EmptyListException
{
if (isEmpty()) throw new EmptyListException(name);
T removedItem = firstNode.data;
if (firstNode == lastNode) firstNode = lastNode = null;
else firstNode = firstNode.nextNode;
return removedItem;
}
public T removeFromBack() throws EmptyListException { /* 待撰寫 */ }
public boolean isEmpty() { return firstNode == null; }
public void print()
{
if (isEmpty())
{
System.out.printf("Empty %s%n", name);
return;
}
System.out.printf("The %s is: ", name);
ListNode current = firstNode;
while (current != null)
{
System.out.printf("%s ", current.data);
current = current.nextNode;
}
System.out.println();
}
}
public class EmptyListException extends RuntimeException
{
public EmptyListException() { this("List"); }
public EmptyListException(String name) { super(name + " is empty"); }
}
public class ListTest
{
public static void main(String[] args)
{
List list = new List<>();
try
{
list.insertAtFront(-1);
list.insertAtFront(99);
list.print();
int removedItem = list.removeFromFront();
removedItem = list.removeFromFront();
list.print();
removedItem = list.removeFromFront();
list.print();
}
catch (EmptyListException emptyListException)
{
emptyListException.printStackTrace();
}
}
}
下列為資料結構 List 的 Java 程式，而 ListTest 為測試類別（class），試回答以下問題：（35 分） class ListNode
撰寫 public T removeFromBack() throws EmptyListException。
📝 此題為申論題
思路引導 VIP
- 邊界情況：(A) 串列為空：拋出例外。(B) 只有一個節點：清空
firstNode與lastNode。(C) 多個節點：必須從頭遍歷到「倒數第二個」節點，才能將其nextNode設為null並更新lastNode。 - 單向鏈結限制：因為是單向串列，刪除尾端比刪除前端複雜，時間複雜度為 O(n)。
🤖
AI 詳解
AI 專屬家教
【考點分析】 考察單向鏈結串列（Singly Linked List）刪除尾端節點的邏輯，關鍵在於獲取倒數第二個節點的引用。 【參考解答】
▼ 還有更多解析內容