University of Mumbai 2009 M.C.A Data Structures - Question Paper
MCA Data Structures
V\Cr SEK -TT
Con. 2266Os.
DoJrW STfuc-hj rCL$,
(HEViSED COURSE) (3 Hours)
Cioocj
[Totai Marks ; 1UG
- Note: Question 1 is compulsory
Answer any 4 from the remaining 6 questions
All questions carry equal marks
Q1 a) Write short notes on
i) Big-O Notation
ii) Circular Linked Lists '
(10)
iii) Depth-First Traversal and Breadth-First Traversal in graphs
b) Given the set of symbols and corresponding frequency table as below, explain the steps to find the Huffman Code
I
H
G
10
F
1
C
4
D
6
Symbol
Frequency
(10)
Q2 a) Using midsquare hashing method store the keys given below in .an array of size 1000 .
224562, 137466, 214562.140T45, 214576. 162145, 144467, 199645, 234534 Because of the key length square only the first three digits of the key.
Use pseudorandom number generator for rehashing is collisions occur (Take a = 3 and c = -1 as factors)
(10)
(10)
b) Define and explain the stack data structure with a suitable example. Give algorithms for Push, Pop, StackFull and Stack Empty functions.
(10)
b) For a singly linked list, write algorithms to
i) Count the number of nodes in the list.
ii) Append two lists together
Define sn AVI Tree. Write an algorithm to Rotate AVL Tree Left and illustrate with the help of an exarr.pSe
i) Write an algorithm for sorting elements using Shell Sort.
ii) , An array contains the elements .
81,94,11,96,12,35.17,95,28,58,41,75.15
Show the contents of the array as it goes through Shell Sort {Consider
increment factors 5, 3 and 1)
A binary tree has 10 nodes. The inorder and preorder traversal are shown below. Inorder Traversal: A B C E D F J G I H .
Preorder Traversal: JCBADEFIGH
Show a step-wise reconstruction of the binary tree along with its postorder traversal'
Write the algorithm to
i) Delete an element in a doubly linked iist
ii) Interchange the nth and mth element of a doubly linked list
What is queue? Explain the working of a circular queue and give algorithms for inserting an element and deleting an element from the circular queue.
|
i) Give Ojikstra's algorithm to determine the shortest path in a graph ii) Determine the minimum spanning tree of the following graph using |
 |
Define a B-Tree. Build a B-Tree of order 3 created by inserting the following data arriving in sequence 77, 12, 48, 69, 33. 89, 97, 91. 37, 45, 83.
i) What is a Heap? Give the algorithm for Reheap Down.
ii) Make a heap out of the following data 23, 7, 92, 6, 12, 14, 40, 44, 20, 21
SEM-Tt~
v-F.x-I-09-D-Scan-5
Con. 2272-09,
: i'Ui
/3 Hours}
23r<* Hctj 2&0<j
BB-9204 [Total Marks : 100
(1) Question No. 1 is compulsory.
N.B.
(2) Attempt any four out of remaining six questions m Assumptions should be made whenever reqmred and should be wjri, seated.
(3)
(4)
(5)
Answers to questions should be grouped and written togeth .
Draw the diagrams whenever required.
For the processes listed below the table, draw Gantt chart and calculate 12 Average waiting time and Average turn around time using .
1- (a)
FCFS (First come first serve)
(i)
(ii)
(iii)
SJF (Shortest job first) in both conditions preemptive and non-prccmpme
(b)
| |||||||||||||||
|
Describe the differences among schedulers. short-term, medium-term and long-term |
Suppose a disk drive has 400 cylinders, numbered 0 to 399. The driver is currently serving a request at cylinder 120 and previous request was at cylinder 140. The queue of pending request in FIFO order is .
12
2. (a)
86 147,312,91,177,48,309,222,175,130
Startin'* from the current head position, what is the total distance m cyl.nders that the'disk aim moves to satisfy all pending request for each of the fol.owing
disk scheduling algorithm ?
Ci'l SSTF (ii) SCAN (iii) C-SCAN What is process ? Explain about five-state Process model in Process
(b)
Management in detail.
10
What is virtual memory ? Explain paging technique in virtual
3. (a)
(b)
On a simple paging system with 224 bytes of physical memory, 256 pages
of loglcal address space and a page size of 2> bytes, how many bits are m
logical address ? .
What is thread ? Explain various kinds of threads in detail.
|
Processes |
Allocation |
Max |
Available | ||||||
|
R1 |
R2 |
R3 |
R1 |
R2 |
R3 |
R1 |
R2 |
R3 | |
|
P0 |
0 |
1 |
0 |
7 |
5 |
3 |
3 |
3 |
2 |
|
PI |
2 |
0 |
0 |
3 |
2 |
2 | |||
|
P2 |
3 |
0 |
2 |
9 |
0 |
2 | |||
|
P3 |
2 |
1 |
1 |
2 |
2 |
2 | |||
|
P4 |
0 |
0 |
2 |
4 |
3 |
3 | |||
Using bankers algorithm answers the following :
(i) What is the context of matrix need ?
(ii) Is the system in safe state ? Give the sequence.
(iii) If a request from process PI arrives for (I, 0, 2) can the request be granted immediately ?
Explain the difference between micro kernel and monolithic kernel architectures. 8 Give examples of both type of operating system.
(b)
5. (a) What is deadlock ? What are the necessary conditions for occurrence of JO deadlock also mention the methods of handling deadlock ?
Explain direct memory access (DMA) in detail with suitable example. 10
(b)
(a)
(b)
Which different types of shells are available in UNIX ? Explain any five 10 salient features of UNIX and also explain the architecture of UNIX.
Discuss different methods of file access and also explain which one is the 10 best access method.
7, Write short notes on any four :
(a) Process Control Block (PCB)
(b) Buffering
(c) Semaphore
(d) Multiprogramming, Multitasking, Multiprocessing
(e) Context Switching'
(f) Monitors.
|
(REVISED COURSE) ws April 09 147 Con. 2276-09. (3 Hours) |
BB-9207 [Total Marks : 100 |
N.B: (1) Question No. 1 is compulsory.
(2) Attempt any four out of remaining six questions.
(3) Assume any necessary data but justify the same.
(4) Figures to the right indicate marks.
(5) Use of calculator is allowed.
1. (a) (i) Consider 4 computer firms A,B,C and D bidding for a contract. A survey of past bidding success of these firms on similar contract gives following probability of winning P(A)=0.35, P(B)=0.15, P(C)=0.3, P(D)=0 2 Before discussion is made to avail a contract the firm B withdraws its bid. Find the new probability of winning.
[5]
(ii) Using usual notation notations, find the harmonic mean of Beta Distribution of first kind.
(b) (i) While calculating coefficient of correlation between two variables x and y from 25 pairs of observation, the following results were obtained. [5]
x2=650, y2=460, x=125, Ey=100, xy=508.
It was discovered later that two data pairs were wrongly typed as (6,14) and (9,6) instead of the correct values (8,12) and (6,8). Obtain the correct value of correlation coefficient.
(ii) Let xi and X2 be two stochastic random variables having variance k and 2 respectively. If variance of Y=3xi-x2 is 25 find k. [5]
2. (a) The joint distribution function (cumulative) of X and Y is given by [10]
FXY(x,y)= 1 -e'x-e"y+e"(x+y) , x>0, y>0 =0, otherwise
(i) Find the marginal density functions of X and Y.
(ii) Find P(X<loY<l) and P(X+Y<1).
(b) (i) The mean of two samples of size 50 and 100 respectively are 54.1 and 50.3 and standard deviation are 8 and 7. Find the mean and standard deviation of the sample obtained by combining the two samples. [5]
(ii) The number of jobs arriving at a computer center between 9am and 10 am is a random variable X with a Poisson distribution with mean 2. The number of jobs arriving between 10 am and 11 am is a random variable Y with Poisson distribution with mean 6. If X and Y are independent, find the probability that more than 5 jobs will arrive between 9 am and 11 am. [5]
3. (a) (i) Of all graduate students in university 70% are women and 30% are men. Suppose that 20% and 25% of the female and male population, respectively, smokes cigarettes. What is the probability that a randomly selected graduate is a woman who smokes? Also find the probability that a randomly selected graduate is a smoker? [5]
(ii) If X and Y are independent R.V.S following N(8,4) and N(12,48) respectively, find the value of X s.t. [5]
P(2X-Y<2X) = P(X+2Y>X)
Where X follow normal distribution with parameters |i and cr2 is given by X-Na2).
b(i) A box of 6 IC chips contains 2 defective. A computer center makes a random purchase of 3 of the IC chips. If X is the number of defective chips purchased by the computer center, find the probability distribution of X. [5]
|
(ii) Calculate the coefficient of variation for the following data: [5] | ||||||||||||||||||||||
|
|
4. (a) (i) The following are the marks obtained by 8 students in two subjects Computer Graphics (CG) and Probability & Statistics (PS). Calculate rank correlation coefficient. | ||||||||||||||||||
|
(ii) The mean weekly sales of soap bars in independent departmental stores was 146.3 bars per store. After an advertising campaign the mean weekly sales in 22 stores for a typical week increased to 153.7 and showed a standard deviation of 17.2. Was the advertising campaign successful? (Given: The value of ta at 5% level of significance for 21 degrees of freedom is 1.72) [5]
(b) (i)-Assuming steady state probability for the (M/M/1): (FCFS/oo/oo) queuing model
when there are n customers in the system as p - J |I-J, obtain the relation
for expected number of customers in the system. Assume that the mean arrival rate (X) and mean service rate(n) are constant. [51
(ii) A person repairing radios finds that the time spent on the radio sets has been exponential distribution with mean 20 minutes. If the radios are repaired in the order in which they come in and their arrival is approximately Poisson with an average rate of 15 for 8-hour day, What is the repairmans expected idle time each day? How many jobs are ahead of the average radio set just brought in? [5]
5 (a) (i) It is believed that the precision of an instrument is no more than 0.16. Write down the null and alternative hypothesis for testing this belief. Carry out the test at 1% level given 11 measurements of the same subject on the instrument: [5]
2.5, 2.3, 2.4, 2.3, 2.5, 2.7, 2.5, 2.6, 2.6, 2.7, 2.5
(Given for 10 degrees of freedom at 1% level of significance, the table value of x is 23.2)
(ii) Show that the variance Beta distribution of first kind is
(m + n) (m + n + 1)
[5] [5]
where m and n are parameters of the distribution.
(b) (i) Calculate the Bowleys coefficient of skewness.
|
x |
10-15 |
15-20 |
20 25 |
25 30 |
SO BS |
35-40 |
40 45 |
45-50 |
|
f |
2 |
5 |
7 |
13 |
21 |
16 |
8 |
3 |
(ii) The amount of bread in 100s of pounds (x) that a certain bakery is able to sell in a day has the following probability distribution.
f(x) =Ax, 0<x<5
= A(10-x), 5<x<10
= 0, otherwise
Find the value of A such that f(x) is a pdf.. What is the probability that number of pounds of bread that will be sold tomorrow is more than 500 pounds [5]
6. (a) (i) The probability of occurrence of an event A is 0.7, the probability of nonoccurrence of B is 0.5 and non occurrence of at least one of A and B is 0.6. Find the probability that at least one of A and B occur. [5]
(ii) Establish the lack of memory property of geometric distribution,
[5]
[5]
[ TURN OVER
[5]
b) (i) Find the value of k so that
f(x)=kx2( 1 -x3), 0<x< 1
= 0 , otherwise
(ii) If X is a discrete random variable with pmf P(X), then prove that E(aX+b)=aE(X)+b and V(X)=a2V(X), where a and b are constants.
|
No of colds experienced in 12 months |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
No of persons |
15 |
46 |
91 |
162 |
110 |
95 |
82 |
26 |
13 |
2 |
(ii) Out of 100 jobs received at a computer center, 50 are of class 1, 30 of class 2, and 20 of class 3. A sample of 30 jobs is taken with replacement. Find the probability that the sample will contain ten jobs of each class. [5]
(b) (i) Consider discrete random variables X and Y with the joint pmf as below.
|
-1 |
0 |
1 | |
|
_2 |
1/16 |
1/16 |
1/16 |
|
-1 |
1/8 |
1/16 |
1/8 |
|
1 |
1/8 |
1/16 |
1/8 |
|
2 |
1/16 |
1/16 |
1/16 |
Are X and Y independent? Are they un-correlated?
(i i) Calculate the modal marks for the following:
|
Marks |
10-30 |
30-50 |
50-70 |
70-90 |
90-110 |
110-130 J |
|
No of students |
4 |
10 |
14 |
I- 12 |
8 |
6 |
|
Attachment: |
| Earning: Approval pending. |
