Assignment: Data Structure Using C Language
Q.1
a) Write an algorithm to add and multiply two large integers, which cannot be represented by built-in types.
b) Write a "c" function to find recursively the maximum and minimum element of an array A of size "n" elements. Find also the number of comparisons required for this.
Q.2
a) How do you represent a stack and a queue by using one-dimensional array?
b) Write "c" functions for pushing into or popping from a stack.
c) Write "c" functions for adding an element to a queue and removing an element from a queue.
Q.3
a) Define directed and undirected graphs. Give examples. Show that the sum of degrees of all vertices in an undirected graph is twice the number of edges.
b) Define weighted graph and sub-graph. Give examples.
Q.4
a) Show that a tree with "n" nodes has exactly (n - 1) edges.
b) Prove that a binary tree with "n" internal nodes has (n + 1) external nodes.
c) If "E" and "I" denote the external and internal path lengths of a binary tree having "n" internal nodes then the following identity holds
E = I + 2*n. Prove it.
Q.5
a) Determine with the help of an example whether the initial order of elements is preserved in the case of bubble sort.
b) Write a "c" function to sort a list of integers using insertion sort technique where the list is represented through links using pointers.