跳至主要內容

DonHe NYU CS-UY 1134 Midterm Exam

AI悦创原创2023年11月18日大约 12 分钟...约 3600 字

code1

Question 1

Consider the following definition of the left circular-shift operation:
lf seq is the sequence <a1,a2,...an1,an><a_1, a_2,...a_{n-1}, a_n> , the left circular-shift of seq is <a2,a3,,an,a1><a_2, a_3,…,a_n, a_1> ,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><2, 4, 6, 8, 10>, is: <4,6,8,10,2><4, 6, 8, 10, 2>.

Add the following method to the DoublyLinkedList class:

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

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, 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><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 θ(n)\theta(n).

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

    • one ArrayStack object
    • θ(1)\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

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 θ(n)\theta(n) worst-case.
  2. You must give a recursive implementation.
  3. You are not allowed to:
    1. Define a helper function.
    2. Add parameters to the function's header line
    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悦创·编程一对一

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

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

方法一:QQ

方法二:微信:Jiabcdefh

你认为这篇文章怎么样?
  • 0
  • 0
  • 0
  • 0
  • 0
  • 0
评论
  • 按正序
  • 按倒序
  • 按热度
通知
关于编程私教&加密文章