Examlet Week 7 (CPSC 221)

Problem 1

Suppose you are given a sorted array of numbers where and you are given a number and asked to find its index in the array (or to output if it isn't in ).

What is a lower bound on the number of comparisons any comparison-based algorithm must make in the worst case to solve this problem? (Select all that apply. Be careful: the choices are not asymptotic unless they are explicitly described with .)

Select all possible options that apply.

Problem 2

Consider the binary tree class described in lecture where we have 1) variable root that is the treeNode pointer representing the root of the binary tree and 2) each treeNode consists of an integer data element, and two treeNode pointers called left and right.

What does fun(root) return?

int fun(treeNode * curr) {
    if (curr != null) {
        ret1 = fun(curr->left);
        ret2 = fun(curr->right);
        return 1 + min(ret1, ret2);
    }
    else return -1;
}

[ ] (a) fun returns the height of the tree.
[x] (b) fun returns the shortest distance from root to an empty subtree.
[ ] (c) fun returns the number of elements in the tree.
[ ] (d) fun returns the sum of all elements in the tree.
[ ] (e) None of the other options is correct.

Problem 3

Fill in the blank with the correct response:

A perfect binary tree with height 9, 512 has leaves.

Problem 4

In this problem we will investigate some properties of a full 8-ary tree. A full 8-ary tree is a rooted tree in which every node has either 0 or 8 children. In a full tree, a non-leaf node is called an internal node.

Suppose you know that a full 8-ary tree has leaves. How many internal nodes does it have?

Now generalize your response to the previous part: suppose you know that a full 8-ary tree has leaves. Give an exact expression for the number of internal nodes:

Hint for above - it may be helpful to compare the number of leaves and total nodes for several of the smallest full trees you can construct in order to identify a simple pattern.

Problem 5

Fill in the blank with the correct response:

A complete binary tree with 190 nodes, has 63 leaves on the deepest level.

Problem 6

Derive the closed form of the following recurrence, and then enter your closed form in the answer box below. You may assume that is a multiple of 2.

General form after rounds of substitution/recursion (where the form after round of substitution/recursion is ):

Closed form:

Problem 7

Consider a sequence of push and pop operations used to push the integers 0 through 9 on a stack. The numbers will be pushed in order, however the pop operations can be interleaved with the push operations, and can occur any time there is at least one item on the stack. When an item is popped, it is printed to the terminal. Which of the following could be a possible output from such a sequence of operations?

[ ] (a) 1,0,3,4,6,9,8,5,7,2
[ ] (b) 3,2,1,0,4,6,5,9,7,8
[ ] (c) 0,7,2,8,4,5,6,1,3,9
[ ] (d) 9,8,6,7,5,4,3,2,1,0
[x] (e) 0,2,1,6,5,4,3,9,8,7

Problem 8

Consider a null-terminated, singly-linked list with only a head pointer, and a partial class definition below:

struct ListNode {
    int data;
    ListNode* next;
};

class LinkedList {
    private:
        ListNode* front;
    public:
        // functions which may be used for this question
        int Length();
        void Clear();
};

In this question, you will complete a function that "splits" a linked list, producing two lists that contain alternating elements from the original list.

Here, the first list will contain the first element of each pair of consecutive elements in its original order, and the second list will contain the second element in each pair of consecutive elements.

Please note the following requirements/characteristics of the Split function:

The Split function is a public member of the LinkedList class. Therefore you may assume that the function is being called from the object (*this) which will be treated as list1 in the diagrams above. You can access its front pointer by using this->front or simply front.
You may assume that the length of this (i.e. list1) is a multiple of 2.
The splitting of the lists must be done by re-assigning each node's next attribute. Do NOT use new or delete in your solution, and do not change the data attribute of any nodes.
The second list is passed by reference to the Split function. You will have access to its front attribute.

Draw pictures to help yourself visualize your pointer movements! Establish loop invariant configurations of local pointers to help with your loop logic. If you are unable to write a general solution, you may earn partial credit for solving the first four test cases (lengths 0, 2, 4, 6). The Length function may be helpful.

If grading results cannot be produced after submission, please try refreshing this page.

void LinkedList::Split(LinkedList& list2) {
    // Handle empty list
    if (front == nullptr) {
        list2.front = nullptr;
        return;
    }

    // Initialize fronts
    list2.front = front->next;

    ListNode* curr1 = front;
    ListNode* curr2 = list2.front;

    // Traverse while pairs exist
    while (curr2 != nullptr && curr2->next != nullptr) {
        curr1->next = curr2->next;   // skip node into list1
        curr1 = curr1->next;

        curr2->next = curr1->next;   // skip node into list2
        curr2 = curr2->next;
    }

    // Terminate list1
    curr1->next = nullptr;
}