数据结构真题

**数据结构真题**

###1. 队列实现#### 题目描述设计一个队列类，支持 enqueue、dequeue 和 isEmpty 操作。队列中的元素类型为整数。

#### 实现代码

class Queue:
 def __init__(self):
 self.items = []

 def enqueue(self, item):
 """向队列尾部添加元素"""
 self.items.append(item)

 def dequeue(self):
 """从队列头部移除元素"""
 if not self.isEmpty():
 return self.items.pop(0)
 else:
 raise IndexError("Queue is empty")

 def isEmpty(self):
 """检查队列是否为空"""
 return len(self.items) ==0# 示例使用q = Queue()
q.enqueue(1)
q.enqueue(2)
print(q.dequeue()) # 输出:1print(q.isEmpty()) # 输出: False

###2. 栈实现#### 题目描述设计一个栈类，支持 push、pop 和 isEmpty 操作。栈中的元素类型为整数。

#### 实现代码

class Stack:
 def __init__(self):
 self.items = []

 def push(self, item):
 """向栈顶部添加元素"""
 self.items.append(item)

 def pop(self):
 """从栈顶部移除元素"""
 if not self.isEmpty():
 return self.items.pop()
 else:
 raise IndexError("Stack is empty")

 def isEmpty(self):
 """检查栈是否为空"""
 return len(self.items) ==0# 示例使用s = Stack()
s.push(1)
s.push(2)
print(s.pop()) # 输出:2print(s.isEmpty()) # 输出: False

###3. 链表实现#### 题目描述设计一个链表类，支持 insert、delete 和 isEmpty 操作。链表中的元素类型为整数。

#### 实现代码

class Node:
 def __init__(self, data=None):
 self.data = data self.next = Noneclass LinkedList:
 def __init__(self):
 self.head = None def insert(self, data):
 """向链表尾部添加元素"""
 if not self.head:
 self.head = Node(data)
 else:
 current = self.head while current.next:
 current = current.next current.next = Node(data)

 def delete(self, data):
 """从链表中移除指定元素"""
 if self.head is None:
 return if self.head.data == data:
 self.head = self.head.next return current = self.head while current.next:
 if current.next.data == data:
 current.next = current.next.next return current = current.next def isEmpty(self):
 """检查链表是否为空"""
 return self.head is None# 示例使用ll = LinkedList()
ll.insert(1)
ll.insert(2)
print(ll.isEmpty()) # 输出: Falsell.delete(1)
print(ll.isEmpty()) # 输出: False

###4. 哈希表实现#### 题目描述设计一个哈希表类，支持 put、get 和 isEmpty 操作。哈希表中的元素类型为整数。

#### 实现代码

class HashTable:
 def __init__(self, size=10):
 self.size = size self.table = [[] for _ in range(size)]

 def put(self, key, value):
 """向哈希表中添加或更新元素"""
 index = hash(key) % self.size for i, (k, v) in enumerate(self.table[index]):
 if k == key:
 self.table[index][i] = (key, value)
 return self.table[index].append((key, value))

 def get(self, key):
 """从哈希表中获取元素"""
 index = hash(key) % self.size for k, v in self.table[index]:
 if k == key:
 return v raise KeyError("Key not found")

 def isEmpty(self):
 """检查哈希表是否为空"""
 return all(not bucket for bucket in self.table)

# 示例使用ht = HashTable()
ht.put(1, "one")
print(ht.get(1)) # 输出: oneprint(ht.isEmpty()) # 输出: False

###5. Trie树实现#### 题目描述设计一个Trie树类，支持 insert、search 和 startsWith 操作。Trie树中的元素类型为整数。

#### 实现代码

class TrieNode:
 def __init__(self):
 self.children = {}
 self.isEndOfWord = Falseclass Trie:
 def __init__(self):
 self.root = TrieNode()

 def insert(self, word):
 """向Trie树中添加元素"""
 node = self.root for char in word:
 if char not in node.children:
 node.children[char] = TrieNode()
 node = node.children[char]
 node.isEndOfWord = True def search(self, word):
 """从Trie树中获取元素"""
 node = self.root for char in word:
 if char not in node.children:
 return False node = node.children[char]
 return node.isEndOfWord def startsWith(self, prefix):
 """检查Trie树是否包含指定前缀"""
 node = self.root for char in prefix:
 if char not in node.children:
 return False node = node.children[char]
 return True# 示例使用trie = Trie()
trie.insert("apple")
print(trie.search("apple")) # 输出: Trueprint(trie.startsWith("app")) # 输出: True

以上是五个数据结构真题的实现代码和示例使用。每个真题都有一个具体的描述和实现代码，包括注释和示例使用。