The delete() method in a Linked List deletes the entire list. For the following questions, state any assumptions you make about the design Write the delete function for a singly linked Write the delete function for a circly linked

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Assume a 64 bit machine with 4 byte int, 1 byte char, and 8 byte doubles for all questions.

1. [8 points] The delete() method in a Linked List deletes the entire list. For the following questions, state any assumptions you make about the design 
2. Write the delete function for a singly linked
3. Write the delete function for a circly linked
4. [8 pts] Using geometric expansion by a factor of 2, write a function that takes a pointer to an integer array, allocates more space, then returns the pointer to the reallocated You cannot make any assumptions about the array parameter (empty, full, etc) and you cannot use realloc (you may use any other library functions).
5. [2 pts] Briefly explain why you have to return a pointer to the reallocated
6. [6 pts] Write a C function that takes only a Binary Search Tree as a parameter and returns an array containing the data in the tree sorted in descending You may need to use a secondary recursive function to accomplish this.
7. [6 pts] Draw the array representation after each sift-down operation in the heapify algorithm for a max-heap with a starting array of the following values: [1, 2, 4, 6, 7, 9, 10, 18, 100]
8. [9 pts] Given a hash table with m=11 entries and the following hash function h1: h1(key) = key mod m

Insert the keys {22, 1, 13, 11, 24, 33, 18, 42, 31} in the given order (from left to right) to the hash table by drawing each of the following collision resolution methods:

1. [3 pts] Chaining
2. [3 pts] Linear Open Addressing
3. [3 pts] Rehashing
   1. Draw the new array only once after

6. [6 pts] True or False:
   1. Dynamic Arrays (Vectors) are faster and more efficient than standard arrays . Explain why this is or is not true 
   2. Function pointers must be dereferenced before you can call Explain why this is or is not true with an example.
   3. Binary Search Trees can be a return type of a function Explain why this is or is not true with an example.
   4. [3 pts] Arrays can be a return type of a function Explain why this is or is not true with an example.

 

7. [10 pts] Given the solution for the Two Iterator Cycle Detection algorithm, write a function that takes a pointer to a Linked list as a parameter, and uses the two iterator solution to determine if there is a cycle. Your function should return a pointer to the node at the beginning of the

 

8. [8 points] The insert() function of a Linked List traditionally appends the item to the For the following questions, state any assumptions you make about the design of the list.

 

1. [4 pts] Write the insert function for a singly linked
2. [4 pts] Write the insert function for a doubly linked

 

10. [5 points] Write a C function that takes a Doubly linked list as a You must use a secondary data structure to make a deep copy of the list in reverse order of the original list and return a pointer to the new reversed list.
11. [10 points] Draw the tree representation after max-heapifying the following array with values in the following Circle your final result. We will only grade the circled answer.:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100]

11. [5 points] What would happen if you repeatedly removed the priority value from the heap in the previous question and inserted it into a standard binary search tree?

Draw a representation of the Binary Search Tree after inserting all values

For the below pseudo code, abstract out any external functions needed. For example, printNode(node) to print a node’s value.

 

12a) (3 pts) Write pseudocode for a single recursive function that takes a BST root node as a parameter and performs a deep copy of a Binary Search Tree, returning a pointer to the copy BST:

12b) (3 pts) Write pseudocode for a single recursive function that takes a BST root node as a parameter and deletes all nodes in a Binary Search tree:

12c) (3 pts) Write pseudocode for a single recursive function that takes a BST root node as a parameter and performs a sorted print in a Binary Search tree:

 

13. (5 pts) Draw a binary search tree with the values inserted in the following order: 11, 72, 5, 20, 12, 7, 2, 1, 8, 100

 

1. How many leaves does the tree have?
2. What is the root?
3. What is the tree’s max height?

 

14. (5 pts) How would the previous Binary Tree appear in memory as an array?

 

1. Show the steps involved when you min-heapify the array
2. Show the steps involved (both array and logical tree) when you remove the priority value

15. [6 points] If p is a pointer to a structure, write some C code which uses all the following code snippets:

“++p->i”, “p++->i”, “*p->i”, “*p->i++”, “(*p->i)++”, and “*p++->i”.

Describe the action of each code snippet as a comment.

 

16. [7 points] What is the value of i after executing each of the following:

 

1. i = sizeof(char);
2. i = sizeof(int);
3. int a; i = sizeof a;
4. char b[5]; i = sizeof(b);
5. char *c=b; i = sizeof(c);
6. struct {int d;char e;} s; i = sizeof s;
7. void f(int j[5]) { i = sizeof j;}

 

17. [5 points] Use structs to define a data structure suitable for representing a binary tree of Be sure to include the methods (function pointers) required for all operations (not just public).

 

18. [7 points] Write a function, mirror, which takes a Binary search tree as a parameter and returns a reversed version of the binary search tree, with larger values on the left and smaller values on the right (you may use an auxiliary function).

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of