Data Structures using C++
Data structures using C++
Total : 80 marks Time: 2 hours
Section A
Answer any 6 questions. Each question carries 3 marks.
(Write in not less than a paragraph)
1.
Write any three applications of stack.
- Expression
Evaluation.
- Expression
Conversion. i. Infix to Postfix. ii. Infix to Prefix. iii.
Postfix to Infix. iv. Prefix to Infix.
- Backtracking.
- Memory Management.
2.
Differentiate PUSH and POP.
A push denotes data being
added to it, meaning data is being “pushed” into the stack. On the other hand,
a pop denotes data retrieval, and in particular refers to the
topmost data being accessed
3.
Explain Complete binary tree.
A complete
binary tree is a binary tree in which every level,
except possibly the last, is completely
filled, and all nodes are as far left as possible.
4.
Explain binary search.
Binary search is an efficient algorithm for finding an
item from a sorted list of items. It works by repeatedly dividing in half the
portion of the list that could contain the item, until you've narrowed down the
possible locations to just one.
5.
Define data structures.
Data Structure can be defined as the group of data elements which provides an efficient way of storing and
organising data in the
computer so that it can be used efficiently. Some examples of Data
Structures are arrays, Linked List, Stack, Queue, etc
6.
Differentiate stack and queue.
Stack and Queue both are the non-primitive data
structures. The main differences between stack and queue are that stack uses LIFO (last in first
out) method to access and add data elements whereas Queue uses FIFO (First in first
out) method to access and add data elements.
7.
Explain circular doubly linked list.
Circular doubly
linked list is a more
complexed type of data structure in which a node contain pointers to its
previous node as well as the next node. Circular doubly linked list doesn't contain NULL in any of
the node. ... The first node of the list also contain address of the last node in its previous
pointer.
8.
Define sparse Matrix.
A matrix is a
two-dimensional data object made of m rows and n columns, therefore having
total m x n values. If most of the elements of the matrix have 0
value, then it is called a sparse matrix
9.
Define double ended queue.
Double ended queues, called deques for short, are a
generalized form of the queue.
It is exactly like a queue except
that elements can be added to or removed from the head or the tail.
10. Explain
garbage collection.
garbage collection (GC) is a form of automatic memory
management.
The garbage collector, or just collector, attempts to
reclaim garbage, or memory occupied
by objects that are no
longer in use by the program.
11. Define
binary search tree.
Binary Search
tree can be defined as a class of binary trees, in which the nodes are
arranged in a specific order. This is also called ordered binary tree. In a binary search tree, the value of all
the nodes in the left sub-tree is
less than the value of the root.
12. Define
recursion.
Recursion is
the process of defining something in terms of itself.
(6 x 3 = 18 Marks)
Section B
Answer any 4 questions. Each question carries 8 marks.
(Write in not less than 2 pages)
13. Explain polynomial
representation and its addition.
An essential characteristic of the
polynomial is that each term in the polynomial expression consists of two
parts:
·
one is the coefficient
·
other is the exponent
Example:
·
Algorithm
14. Explain
insertion sort with example.
Insertion
sort is a simple sorting algorithm that works similar to the way you sort playing
cards in your hands. The array is virtually split into a sorted and an unsorted
part. Values from the unsorted part are picked and placed at the correct
position in the sorted part.
Algorithm
To sort an array of size n in ascending
order:
1: Iterate from arr[1] to arr[n] over the
array.
2: Compare the current element (key) to its
predecessor.
3: If the key element is smaller than its
predecessor, compare it to the elements before. Move the greater elements one
position up to make space for the swapped element.
Example:
15. Differentiate
linear and binary search.
·
Linear search is a search that
finds an element in the list by searching the element
sequentially until the element is found in the list. On the other hand, a binary
search is a search that finds the middle element in
the list recursively until the middle element is matched with a searched
element.
·
Algorithm with
example
16. Explain
different types of linked lists.
There are Four
common types of Linked List.
·
Circular doubly list
·
Figures and explanation
17. Explain
PUSH and POP algorithms.
18. Convert the infix expression A+B*C/D
into postfix.
19. Explain postfix evaluation algorithm.
Algorithm
1) Add ) to postfix
expression.
2) Read postfix expression Left to Right until ) encountered
3) If operand is encountered, push it onto Stack
[End If]
4) If operator is encountered, Pop two elements
i) A
-> Top element
ii) B->
Next to Top element
iii) Evaluate B operator A
push B operator A onto Stack
5) Set result
= pop
6) END
20. Explain hashing and
different hashing algorithms.
·
Hashing is an algorithm that calculates a
fixed-size bit string value from a file. A file basically contains blocks of
data. Hashing transforms
this data into a far shorter fixed-length value or key which represents the
original string.
·
Division method, Mid square method, Digit folding method etc
21. Explain different collision resolving methods.
Collision resolution are:
·
Linear probing.
·
Double hashing.
·
Random hashing.
·
Separate chaining.
(4 x 8 = 32 Marks)
Section C
Answer up to 3 questions carrying 15 marks each. However, total marks
for this section should not exceed 30 marks. Marks scored over 30 will be
ignored
22. Explain static and dynamic data structures.
Data structures can be two types :
1. Static Data Structure
2. Dynamic Data Structure
·
I n
Static data structure the size of the structure is fixed. The content of the
data structure can be modified but without changing the memory space allocated
to it.
·
In Dynamic data structure the size of the structure in
not fixed and can be modified during the operations performed on it. Dynamic
data structures are designed to facilitate change of data structures in the run
time.
·
Explanation with example
23. What is binary tree? Explain different traversal
methods of Binary tree with algorithm.
·
24. Explain different types of queue with algorithms.
·
Simple
Queue
A
simple queue is the most basic queue. In this queue, the enqueue operation takes place
at the rear, while the
dequeue operation takes place at the front:
·
Its applications are process scheduling, disk
scheduling, memory management, IO buffer, pipes, call center phone systems, and
interrupt handling.
·
Circular
Queue
A circular queue permits
better memory utilization than a simple queue when the
queue has a fixed size.
In this queue, the last node points to the first node and creates
a circular connection. Thus, it allows us to insert an item at the first node
of the queue when the last node is full and the first node is free.
It’s also called a ring buffer:
·
·
Priority
Queue
·
A priority queue is a
special kind of queue in which each item has a predefined priority of service. In this queue, the enqueue operation takes place at the rear
in the order of arrival of the items, while the dequeue operation takes place
at the front based on the priority of the items.
·
That is to say that an item with a high priority will
be dequeued before an item with a low priority.
·
In the case, when two or
more items have the same priority, then they’ll be dequeued in the order of
their arrival. Hence, it may or may not strictly follow the FIFO rule:
·
·
Double-Ended Queue (Deque)
·
A deque is also a special type of queue. In this
queue, the enqueue and
dequeue operations take place at both front and rear. That
means, we can insert an item at both the ends and can remove an item from both
the ends. Thus, it may or may not adhere to the FIFO order:
·
25. Explain different file organization methods.
·
File organization refers to the way data is
stored in a file. File organization is very important because it determines the
methods of access, efficiency, flexibility and storage devices to use. There
are four methods of organizing files on a storage media. This include:
·
sequential,
·
random,
·
serial and
·
indexed-sequential
·
Sequential file organization
·
Records are stored and accessed in a particular
order sorted using a key field.
Retrieval requires searching sequentially through the entire file
record by record to the end.
Because the record in a file are sorted in a particular order, better
file searching methods like the binary search technique can be used to reduce
the time used for searching a file .
Since the records are sorted, it is possible to know in which half of
the file a particular record being searched is located, Hence this method
repeatedly divides the set of records in the file into two halves and searches
only the half on which the records is found.
For example, of the file has records with key fields 20, 30, 40, 50,
60 and the computer is searching for a record with key field 50, it starts at
40 upwards in its search, ignoring the first half of the set.
Advantages of sequential file organization
The sorting makes it easy to access records.
The binary chop technique can be used to reduce record search time by
as much as half the time taken.
Disadvantages of sequential file organization
The sorting does not remove the need to access other records as the
search looks for particular records.
Sequential records cannot support modern technologies that require
fast access to stored records.
The requirement that all records be of the same size is sometimes
difficult to enforce.
Random or
direct file organization
·
Records are stored randomly but accessed
directly.
·
To access a file stored randomly, a record key is
used to determine where a record is stored on the storage media.
·
Magnetic and optical disks allow data to be
stored and accessed randomly.
Advantages of random file access
Quick retrieval of records.
The records can be of different sizes.
Serial file
organization
Records in a file are stored and accessed one after another.
The records are not stored in any way on the storage medium this type
of organization is mainly used on magnetic tapes.
Advantages of serial file organization
It is simple
It is cheap
Disadvantages of serial file organization
It is cumbersome to access because you have to access all proceeding
records before retrieving the one being searched.
Wastage of space on medium in form of inter-record gap.
It cannot support modern high speed requirements for quick record
access.
Indexed-sequential
file organization method
Almost similar to sequential method only that, an index is used to
enable the computer to locate individual records on the storage media. For
example, on a magnetic drum, records are stored sequential on the tracks.
However, each record is assigned an index that can be used to access it
directly.
(Maximum 30 Marks)
Comments
Post a Comment