CS 692 Capstone Exam Algorithms Spring 2019: Choose any 2 of the 3 problems.
1) Given a nonempty binary tree, write a function that returns the number of leaves in the tree.
Notes:
The function should have just one argument, a pointer to the root. No global variables may be used.
No additional functions may be defined.
2) Solve the recurrence relation where and
for a nonnegative integer k. Your answer should be a precise function of n in closed form. An asymptotic answer is not acceptable. Justify your solution.
3) Let G be a connected undirected graph with vertices v[0], , v[n-1] and m edges. The edges are stored using the adjacency lists implementation.
a) Write code that prints the vertex numbers in breadth-first search order.
For any local data structure you use (such as stacks, queues, etc.), you may assume that the basic operations already exist (and so you dont need to write the code for pop, enqueue, etc.).
b) State in big-theta terms the runtime of your routine as a function of n and/or m.
c) Suppose the graph had been given as an adjacency matrix. For this implementation, state in big-theta terms the runtime of your routine as a function of n and/or m.
CS 692 Capstone Exam Algorithms Fall 2018: Choose any 2 of the 3 problems.
1) Write a boolean function that is given a binary tree and returns true if and only if the tree has an odd number of nodes. An empty tree is considered to have an even number of nodes.
Notes:
The function should have just one argument, a pointer to the root.
No global variables may be used.
No additional functions may be defined. You may not count the number of nodes.
2) Consider the following insertion sort algorithm.
void insertion_sort(element a[], int n)
// Put a[0]..a[n-1] into ascending order by insertion sort. {
for (int k = 1; k < n; k++) {// At this point, a[0]..a[k-1] are already in order.// Insert a[k] where it belongs among a[0]..a[k].You need to write code for this insertion as the body of the for-k loop.}//endfor k }a) Write the code for the body of the for-k loop to complete the insertion sort routine.b) Count the precise best case and worst case number of element comparisons in your insertion sort routine. Your answers should be functions of n in closed form. Note that closed form means that you must resolve all sigmas and …s. Asymptotic answers (such as ones that use big-oh, big-theta, etc.) are not acceptable.3) For each function with input argument n, determine the asymptotic number of fundamental operations that will be executed. Note that fc and fd are recursive. Choose each answer from among the following. You do not need to explain your choices.(1) (logn) (n) (nlogn) (n2) (n2logn) (n3) (2n) (n!)a)void fa(int n) {for(i = n; i > 0; i = i/2)
Perform 1 fundamental operation;
//endfor i
}
b)
void fb(int n) {
for(i = 1; i <= n; i++) {for(j = 1; j < n; j++)Perform 1 fundamental operation;//endfor jfor(k = 1; k <= i; k++)Perform 1 fundamental operation;//endfor k}//endfor i }c)void fc(int n) {if (n > 1){
fc(n/2);
fc(n/2);
Perform n-1 fundamental operations;
}//endif }
d)
void fd(int n) {
if (n > 1){
fd(n/2);
Perform n-1 fundamental operations;
}//endif
}
CS 6901 Capstone Exam Data Structures and Algorithms Fall 2017 Choose any 2 of the 3 problems.
1) Given a possibly empty binary tree, write a function that returns the number of nodes in the tree that have a right child, but no left child. The prototype for your function is
int RightNoLeft(TreeNode *ptr) .
Global variables may not be used. No additional functions may be defined. Declare all data structures.
2) Given an array of n nonzero real numbers a[0]a[n-1], write a function to partition
the array (not sort) so that all its negative elements come before all its positive elements.
Your algorithm should have O(n) time complexity. The function prototype is
void negpospartition(float a[], int n) .
3) Count the precise number of fundamental/basic operations executed in the following code. Your answer should be a function of n ( n 1 ) in closed form. Note that closed
form means that you must resolve all s and s. An asymptotic answer (such as one that uses big-oh, big-theta, etc.) is not acceptable.
for(int k = 1; k < n; k++) {Perform 1 fundamental/basic operation;for (int j = k; j <= n; j++)Perform 1 fundamental/basic operation;//endfor j}//endfor kCS 6901 Capstone Exam Data Structures and Algorithms Spring 2017 Choose any 2 of the 3 problems.1) Given a possibly empty binary tree containing character data, write a function that returns the number of left children in the tree. The prototype for your function should beint LeftCount(TreeNode *ptr) .Global variables may not be used. Declare all data structures.2) Given a possibly empty singly linked list, write a function that reverses the last 4 nodes of the list (without altering the earlier nodes). If the given list has fewer than 5 nodes, the entire list should be reversed. The prototype for your function should bevoid Reverse4(Nodetype *ptr) .3) Solve the recurrence relation T ( n ) 2 T ( n / 2 ) ( n 1 ) where T (1 ) 0 and n 2 kfor a nonnegative integer k. Your answer should be a precise function of n in closed form. An asymptotic answer is not acceptable. Justify your solution.CS 6901 Capstone Exam Data Structures and Algorithms Winter 2017 Choose any 2 of the 3 problems.1) Given a (possibly empty) binary search tree of integers, write a function that constructs a singly linked list of the trees entries in ascending order. Return a pointer to the first entry in the list.2) Implement a FIFO queue of integers using a circular array a[0] .. a[n-1], where n is a constant.a) Declare the data structure.b) Write a function that is given the circular array queue and an integer x and returns true if and only if x is an entry in the queue.3) For each function with input argument n, determine the asymptotic number of fundamental operations that will be executed. Note that fc is recursive. Choose each answer from among the following. You do not need to explain your choices.(1) (logn) (n) (nlogn) (n2) (n2logn) (n3) (2n) (n!)a)void fa(int n) {for(i = n; i > 0; i = i/2)
Perform 1 fundamental operation;
//endfor i
}
b)
void fb(int n) {
for(i = 1; i <= n; i++) {for(j = 1; j < n; j++)Perform 1 fundamental operation;//endfor jfor(k = 1; k <= i; k++)Perform 1 fundamental operation;//endfor k}//endfor i }c)void fc(int n) {if (n == 1)Perform 1 fundamental operation;else {fc(n-1);Perform 1 fundamental operation;fc(n-1);}//endif } CS 6901 Capstone Exam Data Structures and Algorithms Fall 2016: Choose any 2 of the 3 problems.1) Consider the implementation of a closed hash table a[0]..a[n-1] to store positive integers, using quadratic probing to resolve collisions. A value of 0 indicates that a hash table location is currently unused. The hash function is h ( x ) x % n .Write a function that is given a new entry x to be inserted. The function returns the index of where its placed in the array. Return -1 if no empty slot is found. The average runtime of your routine should be according to the usual hashing standards.3) Solve the recurrence relation T ( n ) 2 T ( n / 2 ) 3 n where T (1 ) 1 and n 2 k for a nonnegative integer k. Your answer should be a precise function of n in closed form. Anasymptotic answer is not acceptable. Justify your solution.CS 6901 Capstone Exam Data Structures Spring 2016: Choose any 2 problems.1. Write a boolean function that is given a binary tree and returns true if and only if the tree has an even number of nodes. An empty tree is considered to have an even number of nodes.Notes: The function should have just one argument, a pointer to the root.No global variables may be used.No additional functions may be defined. You may not count the number of nodes.2. Given the following two sorted arrays of integers: A[0]..A[n-1],B[0]..B[m-1].Write an algorithm that merges the contents of A and B into a new sorted array of integersC[0..n+m-1].Your algorithm must run in O(n+m).3. Let G (V , E , W ) be a connected undirected weighted graph with n | V | vertices and m | E | edges. The edges are stored using the adjacency lists implementation.a) Write a function that constructs a linked list of the edge weights in G in depth-first search order. Return a pointer to the first entry in the list.b) State in big-theta terms the runtime of your routine as a function of n and/or m .c) Suppose the graph had been given as an adjacency matrix. For this implementation, state in big-theta terms the runtime of your routine as a function of n and/or m .2) Write a recursive function that prints out the items of a (possibly empty) singly linked list of integers in reverse order. The function should run in linear time.For example, given the linked list 83 –> 9 > 74 > 122 ,
the output would be 122 74 9 83.
CS 6901 Capstone Exam Data Structures and Algorithms Winter 2016 Choose any 2 of the 3 problems.
1) Consider an application that requires a task to perform the following sequence of operations on a single data structure:
i) find a specific value in the data structure
ii) delete this value from the data structure
iii) insert some other value, at the appropriate place, into the data structure
Consider each of the following data structures as a candidate for the above task, which involves performing all three operations.
For each data structure, state the overall time complexity using big-theta notation in terms of the average case and the worst case as a function of n, where n is the number of elements in the data structure.
Do NOT guess: +2 points for correct answer, -2 points for incorrect answer, 0 points for no answer.
Big-Theta Notation
Average Case
Worst Case
Unsorted Array
Sorted Array
Doubly-Linked List
Binary Search Tree
Hash Table
2) Implement a stack of integers using a linked list. Declare the data structure and give code for the following operations:
a) initialize_to_empty
b) push
c) pop (pop should both return a value and remove it from the stack)
3) Consider a general tree containing character values, where a node can have zero or more children. An efficient data structure, with respect to storage, is for each node to have a child pointer (first_child) and a sibling pointer (next_sibling).
For example, the tree below has a root A which has three children B, C, and D. Essentially, the sibling pointers form a linked list of children of one parent.
If the child pointer is NULL, then the node has no children.
If a sibling pointer is NULL, then this is the last child in the linked list. The root does not have any siblings.
A
BCD
EFG
a). Declare the data structure in the language of your choice. For example, typedef struct tree_node *tree_ptr;
b). Write a recursive function to print out the elements of the tree in a postorder traversal. For example,
void postorder(tree_ptr p) {
}
c). What would be the printout for the tree above?
CS 6901 Capstone Exam Data Structures and Algorithms Fall 2015 Choose any 2 of the 3 problems.
1)
2) Given a (possibly empty) singly linked list of distinct integers, write a function that removes the node containing the integer x. The function returns true if x is found, false otherwise. The prototype is
bool remove_node(nodeptr & *head, int x) .
3) For each function with input argument n, determine the precise number of fundamental operations that will be executed. Your answer should be a function of n in closed form. Note that closed form means that you must resolve all s and s. An asymptotic answer (such as one that uses big-oh, big-theta, etc.) is not acceptable. Assume that n 1 for all parts.
Note that fc is recursive.
a)
void fa(int n) {
for(int i = 0; i <= n; i = i+2)Perform 1 fundamental operation;//endfor i}b)void fb(int n) {for(int k = 2; k <= n; k++)for(int j = 1; j < n; j++)Perform 1 fundamental operation;//endfor j//endfor k}c)void fc(int n) {if (n > 1) {
Perform n-1 fundamental operations;
fc(n-1);
}//endif
}
Write the function int CountInternal(treeNode *p) that counts the number of non-leaf
nodes in the (possibly empty) binary tree with root p. Declare all data structures.
CS 6901 Capstone Exam Data Structures and Algorithms Spring 2015 Choose any 2 of the 3 problems.
1) Write a recursive function CountNodes of a (possibly empty) binary tree, which returns the total number of nodes in the tree. Include the declaration of your data structure.
2) Apply the Heap Sort algorithm to the following list. Draw the array after each step. a[0] .. a[7]: {60, 50, 30, 10, 80, 70, 20, 40}
3) For each function with input argument n, determine the asymptotic number of fundamental operations that will be executed. Note that fd is recursive. Choose each answer from among the following. You do not need to explain your choices.
(1) (logn) (n) (nlogn) (n2) (n2logn) (n3) (2n) (n!)
a)
void fa(int n) {
for(i = 1; i <= n; i = i+2)Perform 1 fundamental operation;//endfor i}b)void fb(int n) {for(i = 1; i <= n; i = 2*i)Perform 1 fundamental operation;//endfor i}c)void fc(int n) {for(i = 1; i < n; i++) {Perform 2 fundamental operations;for(j = i; j <= n; j++)Perform 1 fundamental operation;//endfor jfor (k = 1; k <= n; k++)Perform 1 fundamental operation;//endfor k}//endfor i }d)void fd(int n) {if (n > 1) {
fd(n/2);
fd(n/2);
Perform n fundamental operations;
}//endif
}
CS 6901 Capstone Exam Data Structures and Algorithms Fall 2014 Choose any 2 of the 3 problems.
1) a) Give a precise definition of f O ( g ) (big-oh). b) Use the definition to prove that f O ( n ) , where
n2 n, f ( n ) 5 n 7 ,
4 n ,
n23 n 2 3 a n d n o d d . n 2 3 a n d n e v e n
2) Implement a FIFO queue of integers using a circular array a[0] .. a[n-1], where n is a constant. Declare the data structure and give code for the following operations:
a) initialize_to_empty
b) insert_at_rear
c) remove_from_front
d) is_full (return true if the queue is full; false otherwise)
3) Write the function
int CountKey(treeptr *p, int keyval);
that is given a (possibly empty) binary tree and returns the number of times a particular integer key (keyval) occurs as a leaf node. Declare all data structures.
Reviews
There are no reviews yet.