algorithm代做、Python，c/c++，Java编程语言调试、data代写

日期：2020-05-15 11:08

Question 1 (20 points):

a. Given the following (unbalanced) binary search tree:

We are executing the following two operations on the tree above (not one after

the other):

• Inserting 10

• Deleting 13

For each one of these operations, apply the algorithm described in class, and

draw the resulting tree.

b. Let T be a binary search tree. If we traverse T in post-order, we get the

following sequence:

Postorder(T): 3, 5, 4, 6, 2, 9, 8, 11, 10, 7, 1

Draw T.

Question 2 (25 points):

Consider the following definition of a mono-data subtree:

Let T be a binary tree containing integers as data in its nodes, and let T’ be a

subtree of T. We say that T’ is a mono-data subtree, if all the nodes of T’ have the

same data.

For example, in the following tree, the subtree that is circled in red is a mono-data

subtree, as all its nodes have the same data (the common data is 4).

Note: Each leaf is a mono-data subtree (these are the smallest mono-data

subtrees possible).

In this question, we will implement the following function:

def count_mono_data_subtrees(bin_tree)

The function is given bin_tree, a non-empty LinkedBinaryTree object, it will

return the number of mono-data subtrees in bin_tree.

For example, if called with the tree above, it should return 6, as these are the six monodata

subtrees:

Complete the implementation (given in the next page) for the function

count_mono_data_subtrees.

In the implementation you should define a nested recursive helper function:

def count_mono_data_subtrees_helper(root)

This function is given root, a reference to a LinkedBinaryTree.Node, that

indicates the root of the subtree that this function operates on.

4

def count_mono_data_subtrees(bin_tree):

def count_mono_data_subtrees_helper(root):

…

…

…

____________ = count_mono_data_subtrees_helper(bin_tree.root)

return _________

Implementation requirements:

1. Your implementation has to run in linear time. That is, if there are n nodes in

the tree, your function should run in θ(n) worst-case.

2. Your implementation for the helper function must be recursive.

3. You are not allowed to:

o Define any other helper function.

o Add parameters to the function’s header lines.

o Set default values to any parameter.

o Use global variables.

Hint:

To meet the runtime requirement, you may want count_mono_data_subtrees_helper

to return more than one value (multiple values could be collected as a tuple).

5

Question 3 (25 points):

We say that a sequence of numbers is a palindrome if it is read the same

backward or forward.

For example, the sequence: 6, 15, 6, 3, 47, 3, 6, 15, 6 is a palindrome.

Implement the following function:

def construct_a_longest_palindrome(numbers_bank)

When given numbers_bank, a non-empty list of integers, it will create and return

a list containing a longest possible palindrome made only with numbers from

numbers_bank.

Notes:

1. The longest palindrome might NOT contain all of the numbers in the

sequence.

2. If no multi-number palindromes can be constructed, the function may return

just one number (as a single number, alone, is a palindrome).

3. If there is more than one possible longest palindrome, your function can

return any one of them.

For example, if numbers_bank=[3, 47, 6, 6, 5, 6, 15, 3, 22, 1, 6, 15],

Then the call construct_a_longest_palindrome(numbers_bank) could return:

[6, 15, 6, 3, 47, 3, 6, 15, 6] (Which is a palindrome of length 9, and

there is no palindrome made only with numbers from numbers_bank that is

longer than 9).

Implementation requirements:

1. You may use one ArrayQueue, one ArrayStack, and one ChaniningHashTableMap.

2. Your function has to run in expected (average) linear time. That is, if numbers_bank

is a list with n numbers, your function should run in &(') average case.

3. Besides the queue, stack, hash table, and the list that is created and returned, you may

use only constant additional space. That is, besides the queue, stack, hash table, and

the returned list, you may use variables to store an integer, a double, etc. However, you

may not use an additional data structure (such as another list, stack, queue, etc.) to

store non-constant number of elements.

6

Question 4 (30 points):

Recall the Minimum-Priority-Queue ADT we introduced in class. A minimum priority queue

is a collection of (priority, value) items, that come out in an increasing order of priorities.

A Minimum-Priority-Queue supports the following operations:

• p = PriorityQueue(): Creates an empty priority queue.

• len(p): Returns the number of items in p.

• p.is_empty(): Returns True if p is empty, or False otherwise.

• p.insert(pri, val): Inserts an item with priority pri and value val to p.

• p.min(): Returns the Item (pri, val) with the lowest priority in p,

or raises an Exception, if p is empty.

• p.delete_min() : Removes and returns the Item (pri, val) with the

lowest priority in p, or raises an Exception, if p is empty.

Complete the definition below of the LinkedMinHeap class, implementing the MinimumPriority-Queue

ADT. In this implementation, you should represent the heap using node

objects and references to form a tree structure (a “linked representation” of the tree). That is,

you should construct Node objects with references to their "children" and “parent”.

Note: In class (when we implemented the ArrayMinHeap class) we represented the heap

using an “array representation” of the tree.

class LinkedMinHeap:

class Node:

def __init__(self, item):

self.item = item

self.parent = None

self.left = None

self.right = None

class Item:

def __init__(self, priority, value=None):

self.priority = priority

self.value = value

def __lt__(self, other):

return self.priority < other.priority

def __init__(self):

self.root = None

self.size = 0

def __len__(self):

…

def is_empty(self):

…

def min(self):

…

def insert(self, priority, value=None):

…

def delete_min(self):

…

7

Notes:

1. In the LinkedMinHeap class that you would need to complete (given in the

previous page), we already implemented two nested classes:

• Node – should be used for each node object of the linked binary tree.

• Item – should be used to store the (priority, value) item of the Priority Queue.

2. We also implemented the __init__ method of the LinkedMinHeap class.

Each LinkedMinHeap object would maintain two data members:

• self.root – A reference to the heap’s root node. Initially set to None

(indicating an empty tree)

• self.size – Indicating the number of nodes in the heap. Initially set to 0.

Implementation requirements:

1. You are not allowed to add data members to the LinkedMinHeap object.

That is, you can’t edit the __init__ method, that initializes root and size as the

only data member.

2. Runtime requirements:

• Each one of the insert and delete_min operations should run in θ(log (n))

worst case (where n is the number of elements in the priority queue).

• Each one of the len, is_empty, and min operations should run in θ(1) worst case.

3. You may define additional helper methods.

Hint: You might want to re-watch the beginning of the last lecture (1134 – 5/6 lecture).

We had a short discussion about one of the challenges in representing the heap using the

linked representation of the tree, and we described a way to overcome this challenge.