Assignment Data Structure Using C Language

Part A

Q.1

Define algorithm. Explain the space and time complexity of the algorithm with an example.

Q.2

a) What is linked list? Write a ‘C' function to delete every alternate node starting with first node (i.e. first, third, fifth and so on) in a singly linked list.

b) Define hash functions. Explain the Division method, Mid square method and Folding method of hash functions.

Q.3

a) Write a note on priority queue by giving suitable example.

b) Write a C function to evaluate a postfix expression using stack.

Case Study

Q.1

Bubble sort is a simple sorting algorithm. It works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort.

a) Consider the following values sorted in an array. Sort it in ascending order using Bubble sort technique showing all the iterations:

15, 43, 5, 18, 27, 3, 10

b) Also write a C function to sort one dimensional integer array in ascending order using Bubble Sort technique.

Part B

Question 1: A linear collection of data elements where the linear node is given by means of pointer is called:

A) linked list
B) node list
C) primitive list
D) none of these

Question 2: "p" is a pointer to the structure. A member "mem" of that structure is referenced by

A) *p.mem
B) (*p).mem
C) *(p.mem)
D) none of these

Question 3: Which of the following cannot be performed recursively?

A) binary Search
B) quick sort
C) depth First Search
D) none of the above

Question 4: Which of the following data structure may give overflow error, even though the current number of elements in it is less than its size?

A) stack
B) circular queue
C) simple queue
D) none of the above

Question 5: An adjacency matrix representation of a graph cannot contain information of

A) nodes
B) edges
C) direction of edges
D) parallel edges

Question 6 : Which of the following is a hash function?

A) floding
B) quadratic probing
C) chaining
D) open addressing

Question 7: Number of all possible binary trees with 4 nodes is

A) 14
B) 34
C) 24
D) none of the above

Question 8 :"n" elements of the queue are to be reversed using another queue. The number of "ADD" and "REMOVE" required to do so is

A) 2*n
B) 4*n
C) n
D) the task can not be accomplished

Question 9 : If the in-order pre-order traversal of a binary tree are D,B,F,E,G,H,A,C and A,B,D,E,F,G,H,C respectively then

A) D,F,G,A,B,C,H,E
B) F,H,D,G,E,B,C,A
C) D,F,H,G,E,B,C,A
D) C,G,H,F,E,D,B,A

Question 10 : A stack cannot be used to

A) evaluate an arithmetic expression in postfix form
B) implement recursion
C) convert infix form to postfix from of an expression
D) allocate resources by operating system

Question 11: In linked list, there are no NULL links in

A) Singly linked list
B) Linear doubly linked list
C) Circular linked list
D) None of the above

Question 12: The nth element from the top of the stack S is accessible as

A) S[TOP - n]
B) S[TOP + n]
C) S[TOP - n - 1]
D) None of the above

Question 12: If "ABC", "XXX" and "PQR" are elements of a lexically ordered binary tree then the node which will be traversed first in Preorder is

A) ABC
B) XXX
C) PQR
D) Unpredictable

Question 13: A balanced binary tree is a binary tree in which the heights of the two subtrees of every node never differ by more than

A) 2
B) 1
C) 0
D) None of the above

Question 14: The result of evaluating prefix expression * / b + - d a c d where a = 3, b = 6, c = 1 and d = 5 is

A) 8
B) 5
C) 10
D) None of the above

Question 15: In the array representation of binary tree, the right child of root will be at location of

A) 3
B) 2
C) 5
D) None of the above

Question 16: The total number of comparison in bubble sort is

A) O (n2)
B) O (2n)
C) O (nlogn)
D) None of the above

Question 17: Assume that variable x resides at memory location 100, y at 200 and ip at 1000.

int x=1; y=2; int *ip;
ip=&x
y=*ip

What will be the value of y after execution of above code?

A) 1
B) 2
C) 100
D) 1000

Question 18: Which of the following keyword is used to jump out of a loop without waiting to get back to the conditional test?

A) break
B) continue
C) while
D) exit

Question 19: Pick up the odd one out from the following.

A) a=a+1;
B) a+=1;
C) a++;
D) a=+1;

Question 20: Which of the following is the correct way of declaring an array of integer pointers?

A) int *arr[10];
B) int arr[10];
C) *int arr[10];
D) int *arr;

Question 21: The expression, i=30 * 10+27; evaluates to

A) 327
B) -327
C) 810
D) 0

Question 22: Which of the following is returned by the function ‘strcmp' if the strings that are compared are identical?

A) 0
B) 1
C) 2
D) true

Question 23: The statement that correctly defines a character called letter is

A) letter :=char;
B) char letter;
C) letter : char;
D) character letter

Question 24 :The statement that defines an input file handle called input_file, which is a pointer to type FILE, is:

A) FILE*input_file;
B) type input _file as FILE;
C) input_file FILE;
D) *FILE input_file;

Question 25: Close the file associated with input_file

A) close input_file;
B) fclose(input_files);
C) fcloseall();
D) input_file(fclose);

Question 26: Consider the following code segment

int a[10], *p1, *p2;
p1 = &a[4];
p2 = &a[6[;

Which of the following is incorrect w.r.t pointers?

A) p1 +2
B) p2 - 2
C) p2 - p1
D) p2 +p1

Question 27: The second expression (j - k), in the following expression will be evaluated

(i + 5) || (j - k)

A) if the expression (i + 5) is true.
B) if the expression (i + 5) is false.
C) irrespective of whether (i + 5) is true or false.
D) will not be evaluated in any case.

Question 28: In the for statement : for (exp1; exp2; exp3 ) { ........}

where exp1, exp2 and exp3 are expressions. What is/are optional?

A) None of the expressions are optional.
B) Only exp1 and exp3 are optional.
C) Only exp1 is optional
D) All the expressions are optional

Question 29: Which of the following statement is not true for register variable?

A) Only a few register variables may be defined in a function.
B) It is not possible to take the address of a register variable.
C) A struct variable can be stored in registers.
D) If a register declaration is not honored, the register variables are treated as auto variables.

Question 30 : Which of the following is false for goto statement?

A) Use of the goto statement should generally be avoided.
B) A goto statement transfers the control to a labeled statement.
C) No two statements in a function can have same label.
D) With a goto statement, the control can be transferred to any statement of other program.

Question 31: The output of the following code segment will be

char x = ‘B';
switch ( x ) {
case ‘A' : printf("a");
case ‘B' : printf("b");
case ‘C' : printf("c");
}

A) B
B) b
C) BC
D) bc

Question 32: How many values at the most can be returned to the calling function through a single return statement?

A) 0
B) 1
C) 2
D) any number of values

Question 33: A constant cannot be used except

A) for assigning initial value to a variable.
B) with ++ operator.
C) as a formal argument.
D) on LHS of an assignment operator

Question 34: Which of the following preprocessor directives is used to create marcos

A) #include
B) #ifdef
C) #define
D) #undef

Question 35: Which of the following data type is a structured data type with heterogeneous elements?

A) Array
B) Structure
C) enum
D) Pointer

Question 36: For the program given below what will be the correct output?

int total;
int &sum = total;
total = 100;
printf("sum = %d total = %d\n", sum, total);
A) sum = 100 total = 100
B) sum = 100 total = 0
C) sum = 0 total = 100
D) none of the above

Question 37: A dummy header in the linked list contains

A) first record of actual data
B) last record of actual data
C) pointer to the last record of actual data
D) None of the above

Question 38: Write the output of the following program.

int a[ ]={1, 2, 3}, *p;
p = &a[0]; printf("%d", *(p+3));

A) 3
B) Junk value
C) Runtime error
D) Address of third element

Question 39: If the outdegree of Every node is exactly equal to m or 0 and the numbers of nodes at level k is m k - 1 (consider root at level

1) then tree is called as
i) Full m-ary Tree
ii) Complete m-ary Tree
iii) Positional m-ary Tree.

A) Only i)
B) Only iii)
C) Both i) & ii)
D) Both ii) & iii)

Question 40: Which of the following keyword is used to jump out of a loop without waiting to get back to the conditional test?

A) break
B) continue
C) while
D) exit