Write a procedure that copies a linked list pointed to by List1 to another pointed to by List2 such that the nodes in the copied list are in the reverse order to those in the original list. You may assume that an object stack exists with the following methods: push(x) , a procedure, and the functions pop, full , and empty . The nodes of the list are defined by:
type pointer = ^node; node = record info : integer; next : pointer end;
(b)What is the time analysis for this process?
FUNCTION Height(T : pointer) :integer; {pre: A tree exists and T originally points to the root. post: the function returns the height of the tree. FUNCTION Max(A, B:integer):integer; begin if A > B then Max:= A else Max:= B end (* Max *); begin (* Height *) if T = NIL then Height:= -1 else Height:= 1 + Max(Height(T^.Left), Height(T^.Right)) end (* Height *); procedure correct(T : pointer); {pre: a binary tree with a node definition that includes a balance field. post: the balance field for each node is assigned. begin if T <> nil then begin correct(T^.left); T^.balance := height(T^.left) - height(T^.right); correct(T^.right) end end;(b)What is the time analysis for this algorithm for a BST formed from a list of sorted numbers. (c) Rewrite function height as a procedure called set\_balance so that it does not use procedure Correct and sets the balance field in O(n). Use the following heading: procedure set_balance(T : pointer; var height : integer);
tree = ^ node_rec node_rec = record node_number : integer; left, right : tree end;(a)Write a recursive procedure to insert the node numbers in the node_number field using: procedure insert(T : tree; n : integer);
(b)The compression code ( Huffman code ) associated with, for instance, node number 9 is 001 as shown in the diagram. This code in reverse order (100) can be obtained by continuously mod ing and div ing the node number by two, storing the result of the mod in a variable called digit , until the value of node number becomes 1. Write a procedure that takes the node number from the node_number field and using the above mentioned algorithm, displays the compression code for each leaf. Use the following heading, and the object stack refered to in problem 1. procedure code(T : tree);
const capacity = 10; type range = 0..capacity; hash_rec = record key : integer; deposit : real; branch : integer; link : -1..capacity end {hash_rec ; array_type = array[range] of hash_rec;Fill in the following table for the keys: 1643, 1183, 1241, 1792, 1647, 1123, 677. The slot numbers should go from 0 to 9.
slot key Link __________________________________ __________________________________ __________________________________ __________________________________ __________________________________ __________________________________ __________________________________ __________________________________ __________________________________ __________________________________ __________________________________