TUHH: Selftest

TUHH > Studying > Before Studying > Degree Courses > Information and Media Technologies > Admission Requirements > Selftest

Selftest

1) Are you familiar with at least one of the following programming languages:

C
C++
Java
Pascal

2) Consider the array a[ ]=[3,5,9,4,2,1] of n=6 integers

a) What will be the result of the procedure whoknows with respect to a[ ]?

b) What is the well-introduced name for the procedure?

procedure whoknows;

var
la,r : integer;
x : real;

Procedure proc_s;

Label 13;

var
i,j : integer;

     Begin
         i:=la;
         j:=2*i;
         x:=a[i];
         while (j<=r) do
         Begin
             if ((j<=r) and (a[j]<a[j+1])) then
             j=j+1;
             if (x>=a[j]) then
             goto 13;
             a[i]:=a[j];
             i:=j;
             j:=2*i
         End;
     13: a[i]=x
     End;

Begin
     la:=(n Div 2)+1;
     r:=n;
     While (la>1) do
     Begin
         la:=la-1;
         proc_s;
     End;
     While (r>1) do
     Begin
         x:=a[la];
         a[la]:=a[r];
         a[r]:=x;
         r:=r-1;
         proc_s
    End;
End;

3) Write down the disjunctive normal form (DNF) for the Boolean XOR-function. Transform this formula into a conjunctive normal form (KNF) using the distributive laws of a Boolean algebra!

4) Complete the following recursive function definition (in Java). The function toString should return a string with the decimal representation of x. (e.g., toString(-163) = "-0163").

String[ ] digits = {"0","1","2","3","4","5","6","7","8","9" };
static public String toString(int x) {
   if (x == 0) { return "0";}
   else { if (x < 0) {return "-" + toString( <SOLUTION1> ); }
        else {
          String digit = <SOLUTION2>;
          return toString(<SOLUTION3>) + digit;}
   }
}

5) Modify the definition of the function toString such that it uses a loop instead of recursion. The result of the function should remain unchanged.

String[ ] digits = {"0","1","2","3","4","5","6","7","8","9" };
public static String toString(int x){
   String result = < SOLUTION1>;
   String sign = "0";
   < SOLUTION2>
   while (<SOLUTION3>){
   < SOLUTION4>
   }
   return sign + result;
}

6) Let n be the number of leaves in a binary tree T. What is the minimum number of inner nodes in T?

7) How many KB memory does is take to hold a bit vector representation of the set of prime numbers less than 1.000.000?

8) Construct a binary search tree by inserting the sequence of keys in the order H, T, M, D, V, G. The nodes of the search tree are ordered based on alphabetical order.

9) Why does one use queues and not stacks as data structures to collect pending service requests for process scheduling?

10) Name one example for a simple data type and one example for a structured data type.

11) What is the value range of a signed 16-bit integer variable?

12) Restate one of the following for-loops with the help of a while-loop (let N be any integer value).

`C, C++, Java`	`Pascal`
`for` `(i = 0; i < N; i++)` `p(i);`	`FOR` `i := 1 TO N DO` `p(i);`

13) What is the difference between a while-loop and a do-while-loop (Pascal: repeat-until-loop)?

14) Given the following statements, what is the value of "y" if "x" equals to -2, 0, 2?

`C, C++, Java`	`Pascal`
`if` `(x >= 0)` `if` `(x > 0)` `y = x + 1;` `else` `y = x - 1;`	`IF` `(x >= 0) THEN` `IF` `(x > 0) THEN` `y := x + 1` `ELSE` `y := x - 1;`

15) What are the values of pointer variables?

16) Two systems are connected with a bi-directional communication link. One system acts as a sender of information, partitioned into a sequence of messages. The other system receives this message sequence. Messages can get corrupted or lost. To allow the retransmission of corrupted or lost messages, a simple protocol is used. The receiver must acknowledge every message, the sender will retransmit a message if its acknowledgement is not received after a certain amount of time. The sender is only allowed to send a new message, if the previous message has been acknowledged by the receiver. This results in a "stop & wait" protocol, illustrated by the following picture.

Assume that the sender has always something to send and no messages are lost. Each message has a length of 1000 bits, each acknowledgement is 100 bits long. The throughput of the communication link equals 10⁶ bits per second, the distance between sender and receiver is 10km. The speed of the communication link is 2/3 of the speed of light, approximately 2Â·10⁵ km/s. Calculate the efficiency of this "stop & wait" protocol, where efficiency is the time to transfer only the messages in relation to the total time (including the acknowledgements).

17) A message of 12 bits is transmitted via a channel which exhibits a bit error rate of 10^-3.
a) What is the probability of observing 3 bit errors?
b) What is the probability of a correct reception?

18) What is meant by sampling and reconstruction of continuous-time signals ?

19) What is the binary value of the decimal number 0.75 ?

20) What is the decimal value of the binary number 11.01 ?

21) Write down the equations for g and for h in the expression
$\begin{displaymath} \left( \begin{array} {c} a\,\,\,\,\,\,b\\ c\,\,\,\,\,\,d\end... ...) \,=\, \left( \begin{array} {c} g\\ h\end{array}\right)\right)\end{displaymath}$