GC UniversityLahore
Time Allowed: 10Minutes MCQ
Part Set “X” Max. Marks: 10
Q#1: Answer MCQ questions by FILLING THE
CIRCLE.
1.
Brute Force Sorting techniques require comparison of
each element with each other element, and therefore run in _____________ time?
A
|
Linear
|
¡
|
B
|
Fixed
|
¡
|
C
|
N
|
¡
|
D
|
N2
|
¡
|
2.
Brute-force Sorting algorithm’s Average case time is
____________ ?
A
|
N
|
¡
|
B
|
N/2
|
¡
|
C
|
Constant
|
¡
|
D
|
Quadratic.
|
¡
|
3.
Only
method to dynamically increase/decrease capacity of __________ data structure
is to dynamically delete and then allocate ccording to new size.
A
|
Singly Linked list
|
¡
|
B
|
Circular Linked list
|
¡
|
C
|
Array
|
¡
|
D
|
All of
above
|
¡
|
4.
Operators stack used in expression
evaluator maintains __________ priorityof operators from top to bottom.
A
|
FIFO
|
¡
|
B
|
LIFO
|
¡
|
C
|
Descending
|
¡
|
D
|
Ascending
|
¡
|
5.
The _______________has the advantage
that compaction is not required.
A
|
Circular buffer
|
¡
|
B
|
Circular Linked list
|
¡
|
C
|
Only A is correct.
|
¡
|
D
|
Both A and B are correct.
|
¡
|
6.
General
order of operations when inserting a new node in any dynamic data structure is
to adjust the pointers of_______________?
A
|
New node,
then adjacent nodes, then globals.
|
¡
|
B
|
Globals, then new node, then
adjacent.
|
¡
|
C
|
Adjacent nodes, then globals, then
new node.
|
¡
|
D
|
New node, then globals, then
adjacent.
|
¡
|
7.
Following is the correct PRE-FIX form of A+B*C/D?
A
|
+A*B/CD
|
¡
|
B
|
ABCD/*+
|
¡
|
C
|
A+*B/CD.
|
¡
|
D
|
None of
above.
|
¡
|
8.
Priority Queue is
different from simple queue as it requires _________________.
A
|
Compaction
|
¡
|
B
|
In-order deletion
|
¡
|
C
|
In Order
insertion.
|
¡
|
D
|
Deletion from both ends.
|
¡
|
9.
A[i -1 ] = i* A[i]
is the typical technique to find ___________ of polynomial?
A
|
Root
|
¡
|
B
|
Antiderivative
|
¡
|
C
|
Derivative
|
¡
|
D
|
One of above (actual statement was
None of above)
|
¡
|
10.
Divide & Conquer Algorithms have
the advantage that Time Cost is reduced to _____________________.
A
|
Log(N)
|
¡
|
B
|
Quadratic.
|
¡
|
C
|
Linear
|
¡
|
D
|
N2.
|
¡
|
Roll No:-BSCS-2016Name:______________Section:_____
Q1
|
Q2
|
Q3
|
Q4
|
Total
|
GC University Lahore
Time Allowed: 1 Hour 5 Minutes Subjective Part
Max. Marks: 10
All necessary boundary checks and special cases must be applied.
Note:
Following solution is not complete. DIY means Do it yourself. Boundary checks
and special cases are applied in some answers.
Q#2: a) Number x is to be inserted
into a linear doubly linked list in order. Write pseudocode.
Node * t=new node(x);
If(!first){first=last=t; return;}//empty case
If(first-> data > =x){//new node to be
inserted even before first.
t-> next=first;
first->prev= t;
first =t;
}
If(last->data<x){insert at last; }//DIY
Node * t1=first;
While(t1 ->next->data<x || t1->next!=NULL){t1=t1->next;}//search
for node’s position or last, then insert after t1
//step-1 set new node’s pointers
t->prev=t1;
t->next=t1->next;
step-2: set adjacent nodes pointers
t1->next->prev=t;
t1->next=t;
//step-3 set global pointers. Not needed
because node is inserted in between first and last
b) Write pseudocode to store Antiderivative of
Polynomial Array A into array B. Consider contant of integration is zero.
B[0]=0;//coefficient of constant term. i.e
constant of integration
For(inti=1;i<N; i++){
B[i]= A[i-1]/i; i-1th power is now ith power
but divided by i power.
}
c)Write pseudocode to find an element x and
delete its previous node in singly linked list.
Bool findAndDeletePrev(int x){
If(first->data= =x )return false;//there is
no node previous to first
If((first->next->data= =x) {//data
matches next to first, therefore delete first
Node * t=first;
First=first->next;
Delete t;
}
Node * t=first;
While(t->next->next->data!=x||
t->next->next!=NULL)t=t->next;//scan for next to next node matching data;
If(t==NULL) return false;//element not found
If(t==last)// assign last pointer to second
last, then delete last. DIY.
}
Q3: a) Write pseudocode to search &remove
a value x from a sortedlinearsingly linked list.
If(!first) return false;//empty list
If(first->data> x|| last->data<x)
{// x does not lie in range of sorted list.
Return false;
}
If(first->data==key){//first node to be
deleted. DIY
}
Node * t=first;
While(t->next->data<=x|| t->next!=NULL){//find
node whose next matches
T=t->next;
}
If(t->next-data==x)//above loop broken before
required node
{
//delete t-> next. DIY
}
Q.3: b) What is problem with following code
for insertion into a circular queue. Give reasons and write correct version.
bool insert(int x){
If (head = = tail) {//circular queue is full
Return
False;
}
else{
If(tail= = MAX)compact(
);
A[tail + +] = x;
Return True;
}
}
1. CQueueis full only when head
= = tail+1, (not when head = = tail)
2. Tail = = MAX does not apply
to circular queue and compaction is not required.
3. if(tail = = MAX) tail = 0;
thenA[tail]= x; Tail + +;
c) Write pseudocdeto implementinsertlast( int x) for a circular
double linked list.
Node * t=new node(x);
If(!first)[first=t;first->prev=first->next=t;
return;} insert to empty
If(first->next==first){t->prev=t->next=first;first->next=first->prev=t;
return;}
t->next=first;
t->prev=first->prev;
first->prev=t; return;
Q. 3 d)Convert the following expression into
Postfix form using stack technique. Then evaluate the answer using stack. Show
dry run steps, especially stack states.
Conversion Steps
Infix=1+9/3^2^1 *4 – 7^2/7*7*7/7
Postfix=1932^1^/*4*+72^7/7*77/*-
+
|
^
|
^
|
/
|
|||
/
|
/
|
*
|
*
|
||
+
|
+
|
+
|
-
|
-
|
Evaluation Steps
1932^1^/*4*+72^7/7*77/*-
^
|
=
|
^
|
=
|
||
2
|
2
|
1
|
1
|
||
3
|
3
|
9
|
9
|
9
|
9
|
9
|
9
|
9
|
9
|
9
|
9
|
1
|
1
|
1
|
1
|
1
|
1
|
Q. 4: a) Write typical pseudocode to insert a
number x into a dynamic array, with the feature that array grows double when
space utilization is greater than 70%.
If(SIZE > = MAX * 0.7)//if utilization is
around 70%
{
Int * t= new int(MAX);// allocate a new array
For(int I = 0 ;I < SIZE ; i++ ) t[i] =
A[i]; copy elements
Delete A;
A=new int(MAX * 2);//delete and re-allocate
double size
For(int I = 0 ; I < SIZE; i++) A[i] = t[i];//copy
back
}
A[SIZE++]=x; //insert-last, if no other method
is specified
b) Write pseudocode to search and modify an
element x in a sorted array, such that its new value becomes x1 and it travels
to its new position in-order.
Int index = search(A, 0,N,x)//can use binary
search to find position of x
If(index= = -1) return false; //element not
found, search returs -1
int index2 = search(A,0,N,x1);//find its new
position.
If(index2>index){//element has to be
shifted righttside
For(inti=index2;i<=index ;i--)A[i-1]=A[i];//copy
each element to its left side
Else{//element is to be
shifted leftside
For(inti=index;i<=index2;i++)A[i-1]=A[i];
}
A[index2]=x2;
//make necessary corrections. Above code is
just a concept
Following
is recursive definition of a
mathematical formula. Write the recursive function. Apply proof of correctness
to check if algorithm is correct or not.
Is it divide &conqer or not?
Is it branch recursion?
x1= x
xN = { x * (x(N-1)/2)2
for N odd
= { (xN/2)2 for N even
IntrecPow(float x, int N)
{
If(N==1)return x;//base case
If(N%2){//odd-case
N=N-1;
Float y= recPow(x,N/2);
Return x*y*y;
}
Else{//even-case
Float y= recPow(x,N/2);
Return y*y;
}
}
This is Divide & Conquer. This is branch
recursion, but only one branch executes in each call.
Proof of correctness:
Base case: xN for N=1 is x1
= x itself. hencebasecase proved
Recursive call:
Even case:algebraically xAB = (xA )B
so xN = (xN /2)2because N/2 * 2= N
(xN /2)2= (xN /2) * (xN /2)by
square rule. So even case is proved.
Odd case: N is decremented to smaller even number. Then
recursive call is generated for even case N – 1.
Then x is multiplied with result. As xN = x
* xN-1 . henceproved.
d) Fill the following table, assign precedence
numbers to all operators and also mention associativity is right-to- left ot
left-to-right.
Operator
|
Precedence
|
Associativity
|
=
|
0
|
Left-right
|
-
(subtract)
|
4
|
Left-right
|
*
|
3
|
Left-right
|
^
|
1
|
Right-left
|
/
|
2
|
Left-right
|
+
|
4
|
Left-right
|
![Twitter](http://1.bp.blogspot.com/-d2tUG2sawAY/US6pfGQ46uI/AAAAAAAAASc/HFH5V6hiVEQ/s000/twitter.png" border=0" border=0 "Twitter")
![Google Plus](http://3.bp.blogspot.com/-PSJegvpbxNY/US6pgxjuQfI/AAAAAAAAASw/0awv_oNumUs/s000/gplus.png" border=0" border=0 "Google Plus")
0 comments:
Post a Comment