Heap sort algorithm is the same as which of the following algorithms, except for the fact that is uses the heap data structure

Consider the graph G given below:



Th graph G is

Which of the following is in correct LEXICOGRAPHIC order when using ASCII code?

The number of times the statement "x=x+1" is executed in the following program fragment using Theta notation in terms of n is

j=n;

while(j>=1)

{

for(i=1; i<=j; ++i)

x=x+1;

j=j/2;

}

A list of integers is almost sorted with only the largest number being out of place. if this information is not known to the algorithm, then which of the following algorithms sort the list the fastest?

The Depth First and Breadth First traversal Algorithms visit the nodes in exactly the same order in which of the following type of graphs:

The postfix expression ABC+*DE*/is equivalent to which of the following prefix expression?

Algorithm for finding strongly connected components in linear time makes use of

What is the value of the C language expression --n*n + 1*n++ + 1?

Which of the following results in the maximum value if their declarations are

int x=5, y=4;

double z=10.0;

char c=’a’;

(Assume the ASCII value of ‘a’ is 97)

Consider the following function:

double power(double base, unsigned int exponent)

{

if (exponent == 0)

return 1.0;

else if (even (exponent))

return power(base*base, exponent/2);

else

return power(base*base, exponent/2)*base;

}

How many multiplications are executed as a result of the call power(5.0, 12)? (Do not include divisions in this total)

Consider the following program segment:

x=b; k=n; z=1;

while(k!=0)

{

If (odd(k))

z=z*x;

x=x*x;

k=k/2;

}

When the loop terminates. Which of the following must be true?

Consider the following code:

#include

main()

{

float sum=0.0, j=1.0, i=2.0;

while(i/j > 0.001)

{

j=j+j;

sum=sum+i/j;

printf(“%f \n”, sum);

}

When this code is executed, which of the following integers best approximates the last number that is printed?

Thrashing problem in operating systems can not be solved by

1. Increasing the degree of multiprogramming

2. Increasing the clock speed of the processor

3. Decreasing the degree of multiprogramming

4. Increasing the memory

In operating systems when does multilevel feedback scheduling become FCFS?

Consider a reference sequence r₁,r₂,r₃,....,r_n, with a FIFO page replacement algorithm and that gives K_i

Page faults with i page frames allocated. When the number of page frames is j, then for Kj and Ki which of the following is always TRUE when i

If a system has 1 GB RAM with a page size of 8KB and the operating system occupies 16 MB of RAM, how many page frames does the system have for user processes?

In databases, spurious may occur due to 1. Bad normalization 2. Theta joins 3. Updating tables from joins other than theta joins

In the context of databases, entity integrity constraint states that

Suppose there is an open(external) hash table with four buckets, numbered 0,1,2,3. Suppose integers are hashed into these buckets using hash function h(x)=r mod 4. If the sequence of perfect squares 1,4,9,...i² … is hashed into the table, then as the total number of entries in the table grows, what will happen?

The truth table for (p V q) V (p ⋀ r) is the same as truth table for

The number of distinct regular binary trees that can be constructed with 7 nodes named as a, b, c, d, e, f, g is

The boolean function that is equivalent to the boolean function

(~(~p ⋀ q) ⋀ ~(~p⋀~q)) V (p ⋀ r) is

In octal, the twelve- bit two’s complement of the hexadecimal number 2AF₁₆ is

What is the radix of the numbers if the solutions to the quadratic equation

X² - 10x + 31 = 0 is x=5 and x=8?

A 36-bit floating-point binary number has eight bits plus sign bit for the exponent and 26 bits plus sign bit for mantissa. The mantissa is a normalized fraction. Number in the mantissa and exponent are in signed magnitude representation. The largest and smallest positive quantities that can be represented excluding zero are

Using karnaugh map. Four variable boolean function F(A,B,C,D)=Σ(3,7,11,13,14,15) can be simplified to

Let r=1(1+0)*, s=11*0 and t=1*0 be three regular expressions respectively corresponding to three regular sets R, S and T, then which one of the following is TRUE?

Which of the following is (are) FALSE about Context free Languages?

1. Context free languages are closed under intersection

2. Context free languages are closed under concatenation

3. Context free languages are closed under Kleene’s closure.

Which of the following is (are) undecidable problem(s)?

1. Determination of ambiguity of context free grammar(s)?

2. Given two context free grammars G1 and G2 determining whether they generate exactly the same language.

3. Determining whether the language accepted by a Turing machine is finite or infinite.

Consider the following grammar where λ denote the null string

S→ aSb

S→ bSa

S→ SS

S→ λ

Which of the following best characterizes the language generated by the above grammar?

Consider the following grammar where λ denote the null string

S→ aSb

S→ bSa

S→ SS

S→ λ

Which of the following best characterizes the language generated by the above grammar?

In computer networking, an Internet socket or network socket is an end-point of a bidirectional inter-process communication flow across an Internet Protocol-based computer network. A socket address combines which of the following?

Questions 33-34 are based on the following:

In a Distance Vector (DV) routing algorithm each node x maintains a distance vector Dx where costs paths from node x to any other node y in the network with N nodes are estimated. Each node then updates its DV based on the DV update from its neighbour v as: D_x(y)=min_v{c(x,v)+D_v(y)} for each node y in N

Consider the case when after an update D_x(y) does not change, then it implies that

Questions 33-34 are based on the following:

In a Distance Vector (DV) routing algorithm each node x maintains a distance vector Dx where costs paths from node x to any other node y in the network with N nodes are estimated. Each node then updates its DV based on the DV update from its neighbour v as: D_x(y)=min_v{c(x,v)+D_v(y)} for each node y in N

Consider the case when after an update D_x(y) has changed, then which of the following are correct:
1. The update helps to find a least-cost path from node x to y

2. The update needs to be communicated to x’s neighbours in an asynchronous fashion.

3. There is necessarily a count to infinity problem.

A router software had a bug that set TTL field values to NULL when forwarding IP packets, irrespective of the actual TTL value. How many hops further will these IP packets be forwarded

Consider the queuing delay in a router buffer(preceding an outbound link). Suppose all packets are L bits, the transmission rate is R bps and that N packets arrive the buffer every LN/R seconds. The average queuing delay of a packet is

UDP checksum for two 16 bit numbers: 1110011001100110, 1101010101010101 is

After reading the following passage carefully, answer questions 38-40 on the basis of what is stated or implied in the passage.

There was a table set out under a tree in front of the house, and the March Hare and the hatter were having tea at it: a Dormouse was sitting between them, fast asleep, and the other two were using it as a cushion, resting their elbows on it, and talking over its head. “Very uncomfortable for the Dormouse,”thought Alice; “only as its asleep, I suppose it doesn’t mind.”

The table was a large one, but the three were all crowded together at one corner of it. “No room!” they cried out when they saw Alice coming. “There’s plenty of room! Said Alice indignantly, and she sat down in a large arm-chair at one end of the table.

Who were “the three” sitting at one corner of the table?

According to Alice, which of the following is TRUE?

Which of the following is TRUE from the above passage?

A digital computer has a common bus system for 16 registers of 32 bits each. The bus is constructed with multiplexers.

a. How many selection inputs are there in each multiplexer?

b. What size of multiplexers are needed?

c. How many multiplexers are there in the bus?

The access time of a cache memory is 100ns and that of main memory is 100ns. It is estimated that 80% of the memory requests are for read and the remaining 20% for write. The hit ratio for read accessed only is 0.9. A write-through procedure is used.

a. What is the average access time of the system considering only memory read cycles?

b. What is the average access time of the system considering both the read and write requests?

c. What is the hit ratio talking into consideration the write cycles?

The size of a file is 16MB in a file system that uses 2KB as the block size. How many index blocks are needed to store this file in indexed allocation? Assuming the inode structure, how many levels of indexing is needed? How many disk blocks, other than the inode, need to be read to access the 300th block?

Design Push Down Automaton for the language consisting of all words of the form aⁿb^ma^mbⁿ, where m,n > 0 over the alphabet Σ={a,b}. Also provide a context free grammar that generates this language.

Prove

Write an algorithm to find a maximum cost spanning tree, i.e., the spanning tree with highest possible cost. Suppose the edges are sorted according to non-increasing order of their costs and stored in a list. If there are n nodes in the input graph then will the first n-1 edges of this list will always be part of the maximum spanning tree? Justify your answer.

Consider the following relation STUDY and functional dependencies F1, F2, F3, F4 and F5.

Relation

STUDY [ Stid, Name, birthdate, Coursecode, Title, Credits, Dept, Dname, Location, Semester, marks, grade]

Functional Dependencies:

F1: {Stid} → { Name, Birthdate}

F2: {coursecode} → {Title, Credits, Dept}

F3: {Dept} → {Dname, Location}

F4: {Stid, coursecode} → {Semester, Marks, Grade}

F5: {Marks} → {Grade}

A. Find all candidate keys for relation STUDY

B. What is the highest normal form of relation STUDY?

C. Decompose you make, identify the normal form of the original and the resulting relations? Give brief justification for each normalization step.

In C language, how do you declare and define a two dimensional array D of integers with r rows and c columsdunalically In C language, a two dimensional array M with 4 rows and 6 columns may be declared as a formal parameter to a function as M[][6], but not as M[4][]. Why?

A machine uses a 16-bit two’s complement representation for integers, and little-endian byte-ordering, this means that the least significant byte of an integer is stored at the lower address. Determine what the following program fragment will print:

int x; /* 16 bit signed integer */

char *p=(char *) &x;

x=0x0013;

printf(“x is %d\n”,x);

printf(“%d %d\n”,p[0],p[1]);