http://www.oocities.org/SiliconValley/Peaks/8778/TAU_advprog.html

Examination Question Examples

(The correct answers are bolded.)

Question 1

What will be printed by this function (the function is written in pseudocode):
void f()
{
	static int nums = { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
	STACK s;
	int i, n;

	for( i = 0; i < 10; i ++)
		push( &s, nums[i]);
	n = 25;
	for( i = 0; i < 5; i ++)
		n += pop( &s);
	for( i = 0; i < 5; i ++)
		n -= pop( &s);
	printf( "%d\n", n);
}
Answers:
  1. -25
  2. 0
  3. 75
  4. 25

Question 2

Suppose you have to write a database of cars with search by car registration number (7 decimal digits, which are placed in the front and back of each car). The search must be performed as fast as possible. Which data structure is the best choice for this?

Answers:
  1. binary tree
  2. "trie" tree
  3. linked list
  4. array

Question 3

A graph is represented by the following adjacency matrix: 
0 1 0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 1 0 0 0 1 1 0 0
0 0 1 0 0 1 0 0 1 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0
The graph is:

Answers:
  1. directed cycled
  2. undirected cycled
  3. directed acycled
  4. undirected acycled

Question 4

You have 2 non-ordered linked lists with the same length N and unique elements (i.e. some element may be represented in 1 list only once, but different lists may contain the same element). You can not change the lists (e.g. to sort them) or copy the lists (they may be too long). Suppose you have to write a function to calculate number of elements contained in both these 2 lists. What will be the running time of such a function?

Answers:
  1. O(N)
  2. O(NlogN)
  3. O(N2)
  4. O(N3)

Question 5

Using which data structure can we implement a stack data model?

Answers:
  1. array of some structures
  2. linked list of some structures
  3. some special data structure
  4. any of the above

Question 6

Suppose you have a database of people physical data (height, weight, etc.). You want to create a new algorithm to find a person with maximal weight. Which approach may be useful?

Answers:
  1. "divide and conquer" algorithm approach
  2. "greedy" algorithm approach
  3. any of them
  4. none of them

Question 7

You have a recursive function: 
void f1( T* x)
{
	if( x == NULL) return;
	f1( x->next);
	f2( x->v);
}
What is the iterative equivalent of this function?

Answers: 
  1. void f1( T* first)
{
	T* n;
	for( n = first; n != NULL; n = n->next)
		f2( n->v);
}

  2. void f1( T* last)
{
	T* n;
	for( n = last; n != NULL; n = n->prev)
		f2( n->v);
}
  3. both of these functions
  4. none of these functions

Question 8

There is a data model called "deque" ("double ended queue") - it supports both stack-like and queue-like capabilities. Suppose you need implement such a "deque" data model for unknown amount of integer numbers with the following set of operations: What data structure is the best choice for this task?

Answers:
  1. array
  2. linked list
  3. double linked list
  4. binary tree

Question 9

What does this function do? 
T* func( T* d, float v)
{
	if( d == NULL)
	{
		d = (T*)malloc( sizeof( T));
		d->val = v;
		d->lowers = NULL;
		d->uppers = NULL;
	}
	else if( v <= d->val)
		d->lowers = func( d->lowers, v);
	else
		d->uppers = func( d->uppers, v);
	return( d);


}
Answers:
  1. insertion to a linked list
  2. insertion to a double linked list
  3. insertion to a binary tree
  4. sort of double linked list

Question 10

Suppose you are writing a program for electrical communications of a house. You have a graph where: You have to minimize the total amount (length) of electrical wires in the whole house. What is the algorithm needed for this task?

Answers:
  1. reachability test
  2. shortest paths find
  3. clique find
  4. minimal spanning tree find