Anna University - Data Structure and Algorithm (DSA) - April / May 2011 - Question Paper Two Marks with Answers

B.Tech. DEGREE EXAMINATION, APRIL/MAY 2011 - Third Semester

Electrical and Electronics Engineering

DATA STRUCTURES AND ALGORITHMS - (Regulation 2008)

Two Marks with Answers

 1.Define Stack. What are the operations performed on a stack?

A stack is a linear data structure which follows Last In First Out (LIFO) principle, in which both insertion and deletion occur at only one end of the list called top.

The fundamental operations on the stack are :-
(j) PUSH - equivalent to insert
(ii) POP - equivalent to delete.

2.Mention the applications of list.

1. Polynomial ADT.
2. Radix sort.
3. Multilist,

3.Define tree. List the tree traversal techniques.

A tree is a collection of nodes. The collection can be empty, otherwise, a tree consists of a distinguished node r, called the root, and zero or more non empty (sub) trees T1, T2 Tk each of whose roots are connected by a directed edge from r.

Traversing means visiting each node only,once. Tree traversal is a method for visiting all the nodes in the tree exactly once.

There are three types of tree traversal techniques, namely:
1. Inorder traversal
2. Preorder traversal
3. Post order traversal.

4. Differentiate a binary tree from a binary search tree.

Binary search tree is a binary tree in which for every node X in the tree, the values of all the keys in its left subtree are smaller than the key value in X, and the values of all the keys in its right subtree are larger than the key value in X.

5. What is meant by binary heaps.

The efficient way of implementing priority queue is binary is Binary heap is merely referred as heaps, Heaps have two properties namely.
* Structure property .
* Heap order property

6. What is linear hashing? Specify its merits and demerits.

In linear hashing f (key) directly refers to value.
Best case time complexity 0(1)
Worst case time complexity 0(n) .

7.What is meant by digraph? Define the terms in-degree and out-degree with respect to a digraph.

A directed graph or digraph is a pair G = (V,E) where V is a set whose elements are called vertices (nodes) and E is a set of ordered pairs of elements of V (edges or directed edges or arcs). For directed edge (v, w) in E, v is its tail and w its head, (v;w) is represented in the diagrams as the arrow, v -> w, (ie)
simply vw.

Indegree of a Node = No.of incoming edges (nodes)
Outdegree of a Node = No. of outgoing edges (nodes)

8. Write the adjacency matrix for the following graph.

9.What is dynamic programming? Give two examples.

Dynamic programming is one of the optimal algorithm technique when comparing to other methods. What is the advantage of this method? From which classification it has been derived?
Examples:

Sorting by distribution counting.

Horspool's algorithm.

10.What is meant by NP-complete problem.

A problem L is NP-complete if & only if L is NP hard & L E NP.