作者主页:知孤云出岫
下列哪种数据结构适合实现递归算法?
在单链表中删除节点时,需要修改几个指针?
对于一个长度为n的数组,使用二分查找法查找某一元素的时间复杂度是:
下列哪种排序算法是稳定的?
下列哪种树的结构特性使其查找效率最高?
假设一个栈的入栈序列是1, 2, 3,那么以下哪一个可能是它的出栈序列?
对于n个节点的完全二叉树,其高度为:
红黑树是一种特殊的二叉搜索树,下列关于红黑树的说法错误的是:
在邻接矩阵表示的图中,若要判断两个顶点是否相邻,时间复杂度是:
在哈希表中,解决冲突的一种常用方法是:
请简述栈和队列的主要区别,并举例说明它们各自的应用场景。
解释什么是二叉搜索树,并说明如何在二叉搜索树中进行插入和删除操作。
什么是动态规划?请结合一个具体的例子解释其基本思想。
请简述广度优先搜索(BFS)和深度优先搜索(DFS)的基本思想,并比较它们的适用场景。
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, x: int) -> None:
self.stack.append(x)
if not self.min_stack or x <= self.min_stack[-1]:
self.min_stack.append(x)
def pop(self) -> None:
if self.stack:
if self.stack[-1] == self.min_stack[-1]:
self.min_stack.pop()
self.stack.pop()
def top(self) -> int:
return self.stack[-1] if self.stack else None
def getMin(self) -> int:
return self.min_stack[-1] if self.min_stack else None
def lengthOfLongestSubstring(s: str) -> int:
char_set = set()
l = 0
res = 0
for r in range(len(s)):
while s[r] in char_set:
char_set.remove(s[l])
l += 1
char_set.add(s[r])
res = max(res, r - l + 1)
return res
class ListNode:
def __init__(a,x):
self.val = x
self.next = None
def hasCycle(head: ListNode) -> bool:
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def treeToDoublyList(root: TreeNode) -> 'Node':
if not root:
return None
def convert(node):
nonlocal last, first
if node:
convert(node.left)
if last:
last.right, node.left = node, last
else:
first = node
last = node
convert(node.right)
first, last = None, None
convert(root)
last.right, first.left = first, last
return first
好的,以下是整合后的数据结构试卷的答案:
下列哪种数据结构适合实现递归算法?
在单链表中删除节点时,需要修改几个指针?
对于一个长度为n的数组,使用二分查找法查找某一元素的时间复杂度是:
下列哪种排序算法是稳定的?
下列哪种树的结构特性使其查找效率最高?
假设一个栈的入栈序列是1, 2, 3,那么以下哪一个可能是它的出栈序列?
对于n个节点的完全二叉树,其高度为:
红黑树是一种特殊的二叉搜索树,下列关于红黑树的说法错误的是:
在邻接矩阵表示的图中,若要判断两个顶点是否相邻,时间复杂度是:
在哈希表中,解决冲突的一种常用方法是:
请简述栈和队列的主要区别,并举例说明它们各自的应用场景。
答:
解释什么是二叉搜索树,并说明如何在二叉搜索树中进行插入和删除操作。
答:
什么是动态规划?请结合一个具体的例子解释其基本思想。
答:
F(n) = F(n-1) + F(n-2)
请简述广度优先搜索(BFS)和深度优先搜索(DFS)的基本思想,并比较它们的适用场景。
答:
给定一个无序数组,请设计一个算法使其变为有序数组。要求时间复杂度尽可能低,并分析你的算法。
答:
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)
请设计一个数据结构,实现以下功能:插入、删除、获取随机元素,且所有操作的平均时间复杂度为 O(1)。
答:
import random
class RandomizedSet:
def __init__(self):
self.dict = {}
self.list = []
def insert(self, val: int) -> bool:
if val in self.dict:
return False
self.dict[val] = len(self.list)
self.list.append(val)
return True
def remove(self, val: int) -> bool:
if val not in self.dict:
return False
last_element = self.list[-1]
idx = self.dict[val]
self.list[idx] = last_element
self.dict[last_element] = idx
self.list.pop()
del self.dict[val]
return True
def getRandom(self) -> int:
return random.choice(self.list)
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, x: int) -> None:
self.stack.append(x)
if not self.min_stack or x <= self.min_stack[-1]:
self.min_stack.append(x)
def pop(self) -> None:
if self.stack:
if self.stack[-1] == self.min_stack[-1]:
self.min_stack.pop()
self.stack.pop()
def top(self) -> int:
return self.stack[-1] if self.stack else None
def getMin(self) -> int:
return self.min_stack[-1] if self.min_stack else None
def lengthOfLongestSubstring(s: str) -> int:
char_set = set()
l = 0
res = 0
for r in range(len(s)):
while s[r] in char_set:
char_set.remove(s[l])
l += 1
char_set.add(s[r])
res = max(res, r - l + 1)
return res
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def hasCycle(head: ListNode) -> bool:
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def treeToDoublyList(root: TreeNode) -> 'Node':
if not root:
return None
def convert(node):
nonlocal last, first
if node:
convert(node.left)
if last:
last.right, node.left = node, last
else:
first = node
last = node
convert(node.right)
first, last = None, None
convert(root)
last.right, first.left = first, last
return first