CSE334_Practice Set2

The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19. Which one of the following is the postorder traversal of the tree?

• 20, 19, 18, 16, 15, 12, 11, 10

• 19, 16, 18, 20, 11, 12, 10, 15

• 11, 12, 10, 16, 19, 18, 20, 15

• 10, 11, 12, 15, 16, 18, 19, 20

What is the worst-case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order?

• Θ(n^2)

• Θ(1)

• Θ(n)

• Θ(n log n)

What is the worst-case time complexity of inserting n^2 elements into an AVL tree with n elements initially?

• Θ(n^2 log n)

• Θ(n^2)

• Θ(n^4)

• Θ(n^3)

Consider the following C program. What is the output of this program? #include struct Ournode{ char x,y,z; }; int main(){ struct Ournode p = {'1', '0', 'a'+2}; struct Ournode *q = &p; printf ("%c, %c", *((char*)q+1), *((char*)q+2)); return 0; }

• 0, c

• 0, a+2

• '0', 'a+2'

• '0', 'c'

Consider the following C Program void f(int, short); void main() { int i = 100; short s = 12; short *p = &s; ___________ ; // call to f() } Which one of the following expressions, when placed in the blank above, will NOT result in a type-checking error?

• f(i, *p)

• i = f(i,s)

• f(s, *s)

• f(i, *s)

A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT (n refers to the number of items in the queue)?

• The worst-case time complexity for both operations will be Ω(n)

• Worst case time complexity for both operations will be Ω(log n)

• At most one operation can be performed on O(1) time but the worst-case time for the other operation will be Ω(n)

• Both operations can be performed in O(1) time

The result evaluating the postfix expression 10 5 + 60 6/ * 8 – is

• 284

• 71

• 213

• 142

Let A be a square matrix of size n x n. Consider the following program. What is the expected output? C = 100 for i = 1 to n do for j = 1 to n do { Temp = A[i][j] + C A[i][j] = A[j][i] A[j][i] = Temp - C } for i = 1 to n do for j = 1 to n do Output(A[i][j]);

• The matrix A itself

• Adding 100 to upper diagonal elements and subtracting 100 from diagonal elements of A

• Transpose of the matrix A

• None of the above

Consider the following program in C language: #include main() { int i; int *pi = &i; scanf("%d", pi); printf("%d ", i+5); } Which one of the following statements is TRUE?

• Compilation fails

• Execution results in a run-time error

• On execution, the value printed is 5 more than the address of variable i

• On execution, the value printed is 5 more than the integer value entered

A program P reads 500 integers in the range [0, 100] representing the cores of 500 students. It then prints the frequency of each score above 50. What would be the best way for P to store the frequencies?

• An array of 50 numbers

• An array of 100 numbers

• A dynamically allocated array of 550 numbers

• An array of 500 numbers