# Selftest Answers

1) Yes

2) a) a[ ] = [1,2,3,4,5,9]

b) Heapsort

3)

4)

<SOLUTION1>: | -x |

<SOLUTION2>: | digits[x%10] |

<SOLUTION3>: | x/10 |

5)

< SOLUTION1>: | "" |

< SOLUTION2>: | if (x<0) { sign = "-0"; x = -x;} |

< SOLUTION3>: | x != 0 |

< SOLUTION4>: | result = digits[x%10] + result; x = x / 10; |

6) A binary tree with n leaves has at least n-1 inner nodes. The number of inner nodes is minimal if n=2^{ k} and if the tree is balanced.

7) The bit vector representation takes 1.000.000-1 bits stating for each number between 1 and 1.000.000-1 whether this number is a prime number or not. This requires (1.000.0000-1) / (8 * 1024) 122 KB of memory.

8)

9) Using stacks involves the danger that some requests will never be served. The reason is that new requests are stored at the top of the stack and thus served before the earlier requests which reside further down in the stack.

In queues (FIFO data structures), however, requests are served in the order in which they have entered the system. Thus all requests only spend a finite waiting time in the system.

10) Integer, long, short, cardinal, float, double, boolean, character, ...

Record, tuple, array, struct, union, vector

11) -32768 .. 32767.

12)

C, C++, Java | Pascal |

i = 0; while (i < N) { p(i); i++;} | i := 1; WHILE i <= N DO BEGIN p(i); i = succ(i) END |

13) While-loop: The condition for leaving the loop is tested before an iteration step is executed. Do-while-loop: The condition for leaving the loop is tested after an iteration step is executed.

14) (dangling else problem)

| -2 | 0 | 2 |

| undefined | -1 | 3 |

15) Memory addresses.

16)

T_{Mess}: 1000 bits : 10^{6} bits/s = 1ms

T_{Total}: (1000 : 10^{6}) + (100 : 10^{6}) + 2 Â· (10km : 2Â·10^{2} km/ms) = 1ms + 0.1ms + 0.1ms = 1.2ms

Efficiency: T_{ Mess } : T_{ Total} = 1ms : 1.2ms 0.83

17)a)

b) P_{C} = (1-10^{-3})^{12}

18) A bandlimited continuous-time signal, having no frequency components above fb Hertz, is completely specified by samples that are taken at a uniform rate greater than 2fb Hertz. The frequency 2fb is known as the Nyquist rate. The reconstruction of the continuous-time signal from the discrete-time samples can be achieved by lowpass filtering with cutoff frequency fb.

19) 0.11

20) 3.25

21) g=ae+bf; h=ce+df

22)