经典数据结构面试题及答案.docxVIP

经典数据结构面试题及答案

面试题1：如何反转一个单链表？

题目描述：

编写一个函数来反转一个单链表。你可以假设链表的节点定义如下：

```python

classListNode:

def__init__(self,val=0,next=None):

self.val=val

self.next=next

```

答案：

```python

defreverse_linked_list(head):

prev=None

current=head

whilecurrent:

next_node=current.next

current.next=prev

prev=current

current=next_node

returnprev

测试代码

创建链表12345

head=ListNode(1)

head.next=ListNode(2)

head.next.next=ListNode(3)

head.next.next.next=ListNode(4)

head.next.next.next.next=ListNode(5)

反转链表

new_head=reverse_linked_list(head)

打印反转后的链表

whilenew_head:

print(new_head.val,end=)

new_head=new_head.next

输出:54321

```

面试题2：如何实现一个循环队列？

题目描述：

使用数组实现一个循环队列。循环队列是一种线性数据结构，它使用固定大小的数组，并支持两个主要操作：enqueue（在队列尾部添加一个元素）和dequeue（从队列头部移除一个元素）。

答案：

```python

classCircularQueue:

def__init__(self,k):

self.queue=[None]k

self.head=0

self.tail=0

self.size=k

defenqueue(self,value):

if(self.tail+1)%self.size==self.head:

returnFalse

self.queue[self.tail]=value

self.tail=(self.tail+1)%self.size

returnTrue

defdequeue(self):

ifself.head==self.tail:

returnFalse

value=self.queue[self.head]

self.queue[self.head]=None

self.head=(self.head+1)%self.size

returnvalue

测试代码

cq=CircularQueue(3)

cq.enqueue(1)

cq.enqueue(2)

cq.enqueue(3)

print(cq.dequeue())输出:1

print(cq.dequeue())输出:2

```

面试题3：如何检查二叉树是否是平衡的？

题目描述：

一个二叉树每个节点的左右子树的高度差不超过1，则该树是平衡的。请实现一个函数来检查任何给定的二叉树是否是平衡的。

答案：

```python

classTreeNode:

def__init__(self,val=0,left=None,right=None):

self.val=val

self.left=left

self.right=right

defis_balanced(root):

defcheck_height(node):

ifnotnode:

return0,True

left_height,left_balanced=check_height(node.left)

ri