# DonHe NYU CS-UY 1134 Midterm Exam

AI悦创原创大约 12 分钟...约 3600 字

code1
class ArrayStack:
def __init__(self):
"""initializes an empty ArrayStack object. A stack object has:
data -- an ArrayList, storing the elements currently in the stack in the
stack in the order they entered the stack"""
def __len__(self):
"""returns the number of elements stored in the stack"""
def is_empty(self):
"""returns True if and only if the stack is empty"""
def push(self, elem):
"""inserts elem to the stack"""
def pop(self):
"""removes and returns the item that entered the stack last
(out of all the items currently in the stack),
or raises an Exception, if the stack is empty"""

def top(self):
"""returns (without removing) the item that entered the stack
last (out of all the items currently in the stack),
or raises an Exception, if the stack is empty"""


## # Question 1

Consider the following definition of the left circular-shift operation: lf seq is the sequence $$ , the left circular-shift of seq is $$ ,that is the sequence we get when moving the first entry to the last position, while shifting all other entries to the previous position. For example, the left circular-shift of: $<2, 4, 6, 8, 10>$, is: $<4, 6, 8, 10, 2>$.

def left_circular_shift(self)


When called, the method should apply a left circular-shift operation in place. That is, it should mutate the calling object, so that after the execution, it would contain the resulted sequence.

For example, if lnk_lst is [2<—>4<—>6<—>8<—>10],

After calling lnk_lst. left_circular_shift(),

lnk_lst should be: [4<—>6<—>8<—>10<—>2]

Implementation requirements:

1. Your implementation must run in worst-case CONSTANT time.

2. In this implementation, you are not allowed to use the delete_node, delete_first, delete_last add_after, add_before, add_first and/or the add_last methods of the DoublyLinkedList class.

You are expected to change the values of prev and/or next attributes for some node(s) to reflect the left circular-shift operation.

def left_circular_shift(self):
if (len(self) <= 1):
return
else:


## # Solution 1

Code1
class DoublyLinkedList:
class Node:
def __init__(self, data=None, next=None, prev=None):
"""初始化一个新的节点。
data: 节点存储的数据。
next: 指向下一个节点的引用。
prev: 指向前一个节点的引用。"""
self.data = data
self.next = next
self.prev = prev

def disconnect(self):
"""断开节点的连接，清除数据和指针。"""
self.data = None
self.next = None
self.prev = None

def __init__(self):
"""初始化一个空的双向链表。
包含两个哨兵节点：头节点和尾节点，以及一个元素计数器 n。"""
self.trailer = self.Node()  # 哨兵尾节点
self.n = 0  # 元素计数

def __len__(self):
"""返回链表中元素的数量。"""
return self.n

def is_empty(self):
"""判断链表是否为空。"""
return self.n == 0

"""在两个给定节点之间添加一个新节点。
data: 要添加的数据。
predecessor: 新节点的前一个节点。
successor: 新节点的后一个节点。
返回新添加的节点。"""
new_node = self.Node(data, successor, predecessor)
predecessor.next = new_node
successor.prev = new_node
self.n += 1
return new_node

"""在链表的开始处添加一个新元素。
data: 要添加的数据。
返回新添加的节点。"""

"""在链表的末尾处添加一个新元素。
data: 要添加的数据。
返回新添加的节点。"""

def delete_node(self, node):
"""从链表中删除一个节点。
node: 要删除的节点。
返回被删除节点的数据。"""
predecessor = node.prev
successor = node.next
predecessor.next = successor
successor.prev = predecessor
self.n -= 1
data = node.data
node.disconnect()
return data

def __iter__(self):
"""提供链表的迭代器，允许遍历链表中的元素。"""
while current != self.trailer:
yield current.data
current = current.next

def __repr__(self):
"""返回链表的字符串表示，展示其中的数据值。"""
data = [str(node.data) for node in self]
return "<-->".join(data)

def left_circular_shift(self):
"""执行一个左循环移位操作。
将第一个元素移动到链表的末尾。"""
if self.n <= 1:
return

last_node = self.trailer.prev  # 找到最后一个元素节点

# 重新连接节点以完成左循环移位

first_node.next = self.trailer
first_node.prev = last_node
last_node.next = first_node
self.trailer.prev = first_node


## # Question 2

Implement the following function:

def remove_all(q, val)


This function is called with:

1. q - an ArrayQueue object containing integers
2. val - an integer

When called, it should remove all occurrences of val from q, so that when the function is done, val would no longer be in q, and all the other numbers will remain there, keeping the relative order they had before the function was called.

For example, if q contains the elements: $<4, 2, 15, 2, 5, 1, 10, -2, 3>$ (4 is first in line, and 3 is last in line), after calling remove_all(q, 2), q should be: $<4, 15, 5, 1, 10, -2, 3>$.

Implementation requirement:

1. Your function should run in linear time. That is, if there are n items in q, calling remove_all(q, val) will run in $\theta(n)$.

2. For the memory: In addition to q (the ArrayQueue that was given as input), your function may use:

• one ArrayStack object
• $\theta(1)$ additional memory.

That is, in addition to q and the ArrayStack, you may not use another data structure (such as a list, another stack, another queue, etc.) to store non-constant number of elements.

3. You should use the interfaces of ArrayStack and of ArrayQueue as a black box. That is, you may not assume anything about their implementation.

def remove_all(q, vat):


## # Solution 2

Code1-参考1
class ArrayStack:
# 假设这是一个栈的实现，具有常规的 push, pop, is_empty 等方法

def remove_all(q, val):
stack = ArrayStack()

# 遍历队列中的所有元素
initial_size = len(q)
for _ in range(initial_size):
elem = q.dequeue()
if elem != val:
stack.push(elem)

# 将栈中的元素重新放入队列，恢复原始顺序
while not stack.is_empty():
q.enqueue(stack.pop())

# 注意：这里假设 ArrayQueue 和 ArrayStack 已经提供了相应的接口，
# 包括 enqueue, dequeue, push, pop, is_empty 等方法。


## # Question3

Give a recursive implementation of the following function:

def has_full_path_of_ones(root)


This function is given root, a reference to a LinkedBinaryTree.Node that is the root of a non-empty binary tree containing only 0s and 1s as data (in each node).

When calling has_path_of_ones(root), it should return True if the tree rooted by root has a path that starts at the root and ends at a leaf, and that the data in all the nodes along it is 1.

For example, if we call the function on the trees below, then, for the tree on the left, the function should return True. However, for the tree on the right, the function should return False.

Implementation requirements:

1. Your function has to run in worst case linear time. That is, if there are n nodes in the tree, your function should run in $\theta(n)$ worst-case.
2. You must give a recursive implementation.
3. You are not allowed to:
1. Define a helper function.
3. Set default values to any parameter.
4. Use global variables.
def has_full_path_of_ones(root):


## # Solution 3

Code1
def has_full_path_of_ones(root):
# 如果节点为空，说明没有找到全为1的路径，返回False
if root is None:
return False
# 如果节点的值不是1，也返回False
if root.data != 1:
return False
# 如果节点没有子节点，且节点的值为1，说明找到一条全为1的路径
if root.left is None and root.right is None:
return True
# 递归检查左子树或右子树中是否有全为1的路径
return has_full_path_of_ones(root.left) or has_full_path_of_ones(root.right)



## # Question 4

A Parity-Queue is an abstract data type that stores a collection of integer numbers. It still provide a FIFO behavior, like a regular queue. But, in addition to allowing to access (read or delete) the number that entered first, it also allows to access (read or delete) the even number that was entered first, and the odd number that was entered first.

A Parity-Queue has the following operations:

AI悦创·编程一对一

AI悦创·推出辅导班啦，包括「Python 语言辅导班、C++ 辅导班、java 辅导班、算法/数据结构辅导班、少儿编程、pygame 游戏开发、Web、Linux」，全部都是一对一教学：一对一辅导 + 一对一答疑 + 布置作业 + 项目实践等。当然，还有线下线上摄影课程、Photoshop、Premiere 一对一教学、QQ、微信在线，随时响应！微信：Jiabcdefh

C++ 信息奥赛题解，长期更新！长期招收一对一中小学信息奥赛集训，莆田、厦门地区有机会线下上门，其他地区线上。微信：Jiabcdefh

• 0
• 0
• 0
• 0
• 0
• 0

• 按正序
• 按倒序
• 按热度