Data Structures Test - 1 - PDF Flipbook
Data Structures Test - 1
283 Views
34 Downloads
PDF 4,259,822 Bytes
GATE
CSE
Data
Structures
Test-01Solutions
DATA STRUCTURES
1. Which of the following is useful in implementing quick sort?
a) Stack
b) List
c) Set
d) Queue
Answer: (a)
2. Consider the program below in a hypothetical programming
language which allows global variables and choice of static or
dynamic scoping int i;
Scoping int i;
Program main ()
{
i = 10;
call f ()
}
Procedure f ()
{
int i=20;
call g ()
}
Procedure g ()
{
Print i;
}
1
short x[5];
union {
float y;
long z;
} u;
}t;
Let x be the value printed under static scoping and y be the value
printed under dynamic scoping then x and y are
a) x = 10, y = 20
b) x = 20, y = 10
c) x = 20, y = 20
d) x = 10, y = 10
Answer: (a)
Solution:
In static scoping, the scope of an identifier is determined by its
location in the code, and since that does not change, the scope
doesn’t either.
In dynamic scoping the scoping id determined by the sequence
of calls that has held to the use of an identified and since that
can be different each time that use is reached, is dynamic.
So, here, under static scoping:
x = 20(global i)
Under dynamic scoping:
y = 20(according to the sequence of calls, i.e. 20).
2
3. Assume that the objects of the type short, float and long occupy
2 bytes, 4 bytes and 8 bytes, respectively. The memory
requirement for variable t, ignoring alignment consideration, is
a) 22 bytes
b) 14 bytes
c) 18 bytes
d) 10 bytes
Answer: (c)
Solution:
Here structure creates the minimum of array and union, but
union only creates the minimum for only 'long z’ which is max.
So total minimum required = 18.
4. What will be output of the following program? Assume that you
are running this program in little-endian processor.
#include
int main()
{
short a = 320;
char *ptr;
ptr = (char *)&a;
printf("%d",*ptr);
return 0;
}
a) 1
b) 320
3
c) 64
d) Compilation error
Answer: (c)
Solution:
Since little-endian processor is used so least significant byte is
stored at smallest address. 1302000
Storage of 320 in bits forms;
Char*ptr = (char*) &a;
Now ‘a’ is type casted into character type from short, so now
*ptr points to only single byte, print (ptr) will print 64.
5. if the post fix form of a string is ABC + ‒ D * the actual string
is:
a) (A ‒ (B + c)) * D
b) ((A ‒ B) + C) * D
c) ((A + B) ‒ C) * D
d) (A + (B ‒ C) *D)
Answer: (a)
Solution:
Given postfix is ABC + ‒D* and postfix of given options;
(A ‒ (B + C) * D + ABC + ‒ D*
((A ‒ B) + C) * D = AB ‒ C + D*
((A ‒ B) ‒ C)*D = AB + C ‒ D*
(A + (B ‒ C)* D + ABC ‒ D* +
4
6. What is the output of this C code?
#include
void main()
{
int k = 5;
int *p = &k;
int **m = &p;
printf("%d %d %d", k,*p,**m);
}
a) 5 5 5
b) 5 5 junk
c) 5 junk junk
d) compile time error
Answer: (a)
Solution:
So, K = 5, *p = *(100) = 5
**m = **(200) = *(100) = 5
5, 5, 5 will be printed.
7. Consider the Graph shown below:
This graph is a_____
5
a) complete Graph
b) bioapatite Graph
c) Hamiltonian Graph
d) All of the above
Answer: (c)
Solution:
Number of vertices (n) =6
Number of vertices (e) =13
(a) False, since complete contain e = ( −1)
2
But in given graph e = 6×5 = 15 ≠13
2
(c) True, a humiliation path is a path in an undirected or
directed graph that visited each vertex exactly once. A
Hamiltonian path that is cycle
(b) False, since bipartite graph cannot have odd length cycle,
but given graph contains odd length cycle.
8. _____is used in game trees to reduce the number of branches of
the search tree to be traversed without affecting the solution.
a) Best first search
b) Goal stack planning
c) Alpha-beta pruning procedure
d) Min-max search
6
Answer: (c)
Solution:
Alpha-beta pruning is a search algorithm that seeks to decrease
the number of node that are evaluated by minimax algorithm in
its search tree. It is an adversarial search algorithm used
commonly for machine playing of two-player games. Avoiding
search a part of a tree is called pruning is an example of alpha-
beta pruning.
9. ln f unction point analysis, the number of complexity adjustment
factors is
a) 10
b) 12
c) 14
d) 20
Answer: (c)
Solution:
The unadjusted function point count is multiplied by the second
adjustment factor called the value adjustment factor. This factor
terminal and operational characteristics and is calculated by
answering 14 questions.
The value adjustment factor (VAF) is basses on 14 general
functionally of the application being counted.
10. Recursive procedure are implemented by
a) queue
b) stack
7
c) linked list
d) string
Answer: (b)
11. Consider a single linked list where F and L are pointers to the
first and last elements respectively of the linked list. The time
for performing which of the given operations depends on the
length of the linked list?
a) Delete the first element of the list
b) Interchange the first two elements of the list
c) Delete the last element of the list
d) Add an element at the end of the list
Answer: (c)
Solution:
To delete the last element of the list we need to get the address
of the node just before the last node, because we after deleting
last element we cannot point to new last element since direction.
3 we can go only in one So, we have to do linear search on the
linked list to get the second last element then delete last element
and make second last node (of initial linked list) as last node and
so, it depends on length of linked list.
8
12. What is the time complexity of linear search algorithm over an
array of n elements?
a) O(log2n)
b) O(n)
c) O(n log2n)
d) O(n2)
Answer: (b)
13. A Network Schema
a) restricts to one to many relationship
b) permits many to many relationship
c) stores Data in a Database
d) stores Data in a Relation
Answer: (b)
Solution:
Network model permits the modeling of many to many
relationships in data. A set consisis of an owner record type, a
set name, and number a member record type.
Networkdata structure looks like a tree structure, except that a
department nodecalled a child node may have morethan one
parent or owner node. So, one or more nodes may have multi-
parents. Therefore a network model allows a more natural
modeling of relationship between entities. There is no superior
or subordinate relationship in network model as exists in
hierachical models.
9
14. To declare the version of XML, the correct syntax is
a) < ?xml version = '1.0'/>
b) < *xml version = '1.0'/>
c) < ?xml version = "1.0"/>
d) < xml version = '1.0'/>
Answer: (c)
Solution:
< ? xml version = "1.0"/>
This syntax is used to declare the version of xml.
15. A linear list of elements in which deletion can be done from
one end (front) and insertion can take place only at the other end
(rear) is called
a) queue
b) stack
c) tree
d) Deque
Answer: (a)
16. Which of the following statements concerning Object-Oriented
databases is FALSE?
a) Objects in an object-oriented database contain not only data
but also methods for processing the data
b) Object-oriented databases store computational instructions in
the same place as the data
c) Object-oriented databases are more adept at handling
structured (analytical) data than relational databases.
10
d) Object-oriented databases store more types of data than
relational databases and access that data faster.
Answer: (c)
Solution:
Object oriented database are more adept at handling relational
database than unstructured data.
17. trace the error:
void main ()
{
int*b, &a;
*b = 20
Printf (“%d, %d”, a, *b)
}
a) No error
b) Logical error
c) Syntax error
d) semantic error
Answer: (c)
Solution:
There is syntax error ‘a’ declared as reference but not initialized.
18. Match the following with respect to C++ data
Types:
List: 1 List: 2
A. User defined type 1. Qualifier
B. Built in type 2. Union
11
C. Derived type 3. Void
D. Long double 4. Pointer
Codes:
AB CD
a) 2 3 4 1
b) 3 1 4 2
c) 4 1 2 3
d) 3 4 1 2
Answer: (a)
Solution:
Union is a user defined data structure
C++ data Types
Derived Built-in User-define
data types data data types
types
Array int Structure
Function char Union
Pointer float Class
Reference double Enumeraors
void
19. Which of the following regular expression identities are true?
a) (r + s)* = r*s*
b) (r + s)* = r* + s*
c) (r + s) *= (r*s*) *
12
d) r*s* = r* + s*
Answer: (c)
Solution:
Correct regular expression:
(r + s)* = (r* s*)*
20. The merging two sorted lists of sizes m and n into a sorted list
of size (m + n), required comparisons of 1
a) O(m)
b) O(n)
c) O(m + n)
d) O (log m + log n)
Answer: (c)
21. The_____transfers the executable image of a C++ program
from hard disk to main memory. 2f2
a) Compiler
b) Linker
c) Debugger
d) Loader
Answer: (d)
Solution:
Loader is a program that loads machine codes of a program into
the system memory. A loader is the part of operating system that
responsible for loading programs. A linker is a program that
takes one or more object files generated by a combines them in a
single executable file, library file, or another object file.
13
Debugging checks detects and corrects errors or bugs to allow
proper program operation according to set specifications.
22. The postured traversal of a binary tree is DEBFCA. Find out the
Pre order traversal.
a) ABFCDE
b) ADBFEC
c) ABDECF
d) None of these
Answer: (c)
Solution:
By post order traversal, we cannot draw unique binary tree even
with pre order and post order cannot define unique binary tree.
Given question badly asked.
Howe ever, if we guess, the post order of binary tree:
This has: Poster order: D E B F C A--- pre order: A B D E C F
23. Consider the following pseudo- code
while (m < n)
if (x > y) and (a < b) then
a=a+1
y=y‒1
end if
m = m +1
14
end while
What is cyclamate complexity of the above pseudo -code?
a) 2
b) 3
c) 4
d) 5
Answer: (c)
Solution:
Cyclamate complexity of program = predicate statement + 1
= 3 + 1= 4
24. Member of a class specified as ____are accessible only to
method of the class.2f1
a) private
b) public
c) protected
d) derive
Answer: (a)
Solution:
Public is type or method that can be accessed by any other code
in the same assembly or another assembly that references it.
Private is type or member can only be accessed by code in the
class or struct.
Protected is type or member that can be accessed by code in the
same class or structure, or in a derived class.
15
25. Number of edges in a regular graph of degree d and n vertices
is
a) maximum of n, d
b) n + d
c) nd
d) nd/2
Answer: (d)
26. The following postfix expression is evaluated using a stack
823^/23* + 51‒ the top two elements of the stack after first*is
evaluated
a) 6, 1
b) 5, 7
c) 3, 2
d) 1,5
Answer: (a)
Solution:
Given expression is: 823↑/23*+51*-
Top two elements of the stack after * is evaluated:
16
27. Consider the following two functions,
f(n) = n3, if 0 ≤ n< 10,000
= n2, otherwise
g(n) = n, if 0 ≤ n < 100
= n2 + 5n, otherwise
Which of the following are true?
a) f(n) is O(n3)
b) g(n) is O(ns)
c) O(f(n)) is same as 0 (g(n))
d) g(n) is O(n2)
Answer: (c)
28. An Assertion is a predicate expressing a condition we wish
database to always satisfy. The correct syntax for Assertion is:
a) CREATE ASSERTION 'ASSERTION Name' CHECK
'Predicate'
b) CREATE ASSERTION 'ASSERTION Name'
c) CREATE ASSERTION CHECK predicate
d) SELECT ASSERTION
Answer: (a)
Solution:
An asserting in SQL takes from syntax create assertion
check < predicate >
17
29. Match the following with respect to l/O classes in object-
oriented programming:
List-I
i. f open ()
ii. f close ()
iii. f eno ()
iv. f eof ()
List-II
1. returns end of file
2. return for any problem report
3. returns 0
4. returns a file pointer
Codes:
ABCD
a) 4 1 2 3
b) 3 1 4 2
c) 2 3 4 1
d) 4 3 1 2
Answer: (a)
Solution:
F open (): if the file is successfully opened the function returns a
pointer to a FILE object that can be used to identify the stream
on feature operations otherwise a null pointed is returned.
F close (): if the stream is successfully closed, zero value is
return on failure, EOF is returned.
18
F error (): A non-zero value is returned in the case that the error
indicator associated with the stream is set, otherwise, zero is
returned.
F eof (): A non –zero value is returned in the case that the end of
file indicator associated with the stream is set otherwise, zero is
returned.
30. The average number of comparison performed by the merge
sort algorithm, in merging two sorted lists of length two is
a) 8/3
b) 8/5
c) 11/7
d) 11/6
Answer: (a)
19
Data Loading...