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).

Related Questions

. The fundamental operations of create, read, update, and delete (CRUD) in either Python or Java

CS 340 Milestone One Guidelines and Rubric  Overview: For this assignment, you will implement the fundamental operations of create, read, update,

. 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

Retail Transaction Programming Project  Project Requirements:  Develop a program to emulate a purchase transaction at a retail store. This

. The following program contains five errors. Identify the errors and fix them

7COM1028   Secure Systems Programming   Referral Coursework: Secure

. Accepts the following from a user: Item Name Item Quantity Item Price Allows the user to create a file to store the sales receipt contents

Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip

. The final project will encompass developing a web service using a software stack and implementing an industry-standard interface. Regardless of whether you choose to pursue application development goals as a pure developer or as a software engineer

CS 340 Final Project Guidelines and Rubric  Overview The final project will encompass developing a web service using a software stack and impleme