CS2201 Data Structures – Unit 1 and Unit 2 Important 2 and 16 Marks with Answers

Anna University

Department of Computer Science Engineering

Third Semester

CS2201 Data Structures

(Regulation 2008)

Unit - I LINEAR STRUCTURES

PART - A

1. Write down the definition of data structures?

A data structure is a mathematical or logical way of organizing data in the memory that consider not only the items stored but also the relationship to each other and also it is characterized by accessing functions.

 

2. List down any four applications of data structures?

Ø Compiler design

Ø Operating System

Ø Database Management system

Ø Network analysis

 

3. What is meant by an abstract data type(ADT)?

An ADT is a set of operation. A useful tool for specifying the logical properties of a datatype is the abstract data type. ADT refers to the basic mathematical concept that defines the datatype. Eg. Objects such as list, set and graph along their operations can be viewed as ADT's

 

4. What are the operations of ADT?

Union, Intersection, size, complement and find are the various operations of ADT.

 

5. What is meant by list ADT?

List ADT is a sequential storage structure. General list of the form a1, a2, a3.…., an and the size of the list is 'n'. Any element in the list at the position I is defined to be ai, ai+1 the successor of ai and ai-1 is the predecessor of ai.

 

6.What are the various operations done under list ADT?

Ø Print list

Ø Insert

Ø Make empty

Ø Remove

Ø Next

Ø Previous

Ø Find kth

 

7. What is single linked list?

It is a linear data structure which consists a pointer field that points to the address of its next node (successor) and the data item.

 

8. Define double linked list?

It is linear data structure which consists of two links or pointer fields

Ø Next pointer points to the address of the next(successor) node.

Ø Previous pointer points to the address of the previous(predecessor) node.

 

9. What is meant by dummy header?

It is ahead node in the linked list before the actual data nodes.

Header of the linked list is the first element in the list and it stores the number of elements in the list. It points to the first data element of the list.

 

10. Difference between Arrays and Linked List?

Arrays

Linked List

Size of any array is fixed

Size of list is variable

It is necessary to specify the number of

elements during declaration

It is not necessary to specify the

number of elements during declaration

Insertion and deletions are difficult and

costly

Insertions and deletions are done in

less time

It occupies less memory than a linked

list

It occupies more memory

Coding is easy

Careful coding is needed to avoid

memory errors.

 

11. List three examples that uses linked list?

Ø Polynomial ADT

Ø Radix sort

Ø Multi lists

 

12. What are the advantages in the array implementation of list?

a) Print list operation can be carried out at the linear time

b) Find Kth operation takes a constant time

 

13. What is a Stack?

A Stack is an ordered collection of items into which new items may be inserted and from

which items may be deleted at one end, called the top of the stack. The other name of stack is Last-in -First-out list.

 

14. What are the two operations of Stack?

Ø PUSH

Ø POP

 

15. What is a Queue?

A Queue is an ordered collection of items from which items may be deleted at one end called the front of the queue and into which tems may be inserted at the other end called rear of the queue.Queue is called as First –in-First-Out (FIFO).

 

16. Mention applications of stack?

Ø Evaluation of arithmetic expressions

Ø Balancing the symbols

Ø Function calls

Ø Tower of Hanoi

Ø Reversing a string

Ø 8-Queen’s Problem

 

17. Define Infix, prefix and postfix notations?

Ø Infix operators are placed in between the operands

Ø Prefix operators are placed before the operands

Ø Postfix Operators are placed after the operands.

 

18. Mention applications of queue.

Ø Batch processing in an operating system.

Ø To implement priority queue.

Ø Simulation

Ø Mathematics user queuing theory.

Ø Computer networks where the server takes the jobs of the client as per the queue strategy.

 

19. Define Priority Queue.

Priority queue is a queue in which inserting an item or removing an item can be performed from any position based on some priority.

 

20. Convert the expression ((A + B) * C – (D – E) ^ (F + G)) to equivalent Postfix notations.

Postfix Notation: AB + C * DE - - FG + ^

 

21. Write the structure implementation file for singly linked list.

struct Node

{

ElementType Element;

struct Node *Next;

};

 

22. Write the structure implementation file for doubly linked list.

struct Node

{

ElementType Element;

struct Node *FLINK;

struct Node *BLINK;

};

 

23. Write a routine to return a position of an element.

Position Find(int X, List L)

{

Position P;

P=LàNext;

while(P!=NULL && PàElement!=X)

P=PàNext;

Return P;

}

 

24. Mention DLL advantages and disadvantages.

Advantage:

Ø Deletion operation is easier.

Ø Finding the predecessor and successor of a node is easier.

Disadvantage:

Ø More memory space is required since it has two pointers.

 

25. What are the ways a stack can be implemented?

Stack can be implemented two ways, they are

Ø Array implementation

Ø Linked list implementation

 

26. What are the three ways to represent arithmetic expression?

  1. Infix Notation
  2. Prefix Notation
  3. Postfix Notation

 

27. What is meant by Dequeue? Why it is used?

Dequeue is the Double Ended Queue. Which is used to insert and delete operations are performed at the both the ends.

 

28. Write the procedure to insert and delete an element in a queue.

To insert an element X onto the queue Q, the rear pointer is incremented by 1 and then set Queue[Rear] = X.

To delete an element from the queue Q, the Queue[Front] is returned and the Front pointer is incremented by 1

 

29. What is the principle of Radix sort?

Radix sort – sorts on the least significant digits first. On the first pass entire numbers sort on the least significant digit and combines in an array. Then on the second pass, the entire numbers are sorted again on the second least-significant digits and combine in a array and so on.

 

30. How do you push and pop elements in a linked stack?

We perform a PUSH operation by inserting at the front of the list.

We perform a POP operation by deleting the element at the front of the list.

 

31. Swap two adjacent elements by adjusting only the pointers (and not the data) using: singly linked list.

void swap_with_nest(Posiiton P, before P, List L)

{
Position P, After P;

P=before PàNext;

After P=PàNext;

PàNext=After PàNext;

Before PàNext=After P;

After PàNext=P;

}

PART – B

  1. Explain in detail about the linked list implementation using an example.
  2. What is a DLL? Explain the algorithm in detail for inserting and deleting a node from DLL?
  3. Describe the Cursor-based linked list with its implementation in detail. (OR)

Explain Cursor implementation of linked list operations in detail.

  1. Explain in detail three applications of linked list with suitable example.
  2. Describe circular queue implementation in detail giving all the relevant features.
  3. Explain the process of postfix expression evaluation with an example.
  4. Write a procedure to convert the given infix expression to postfix expression using stack.
  5. Explain in detail any three applications of stack.
  6. Explain how linked list is used for polynomial multiplication.
  7. Write the functions to perform the insert and delete operations on queue.
  8. What is stack ADT? Explain how it can be implemented using arrays.
  9. Write ADT operations for array implementation of polynomial addition.
  10. Write ADT operations for array implementation of a queue.
  11. Write suitable routines to perform insertion and deletion operations in a linked queue.
  12. Explain how the given expression is converted into postfix expression using stack.
    A+((B*D+E/F)^G-H)/C+E*F)-B*E

Unit - II TREE STRUCTURES

PART - A

1. Define tree?

Trees are non-liner data structure, which is used to store data items in a shorted sequence. It represents any hierarchical relationship between any data Item. It is a collection of nodes, which has a distinguish node called the root and zero or more non-empty sub trees T1, T2,….Tk. each of which are connected by a directed edge from the root.

 

2. Define Height of tree?

The height of n is the length of the longest path from root to a leaf. Thus all leaves have height zero. The height of a tree is equal to a height of a root.

 

3. Define Depth of tree?

For any node n, the depth of n is the length of the unique path from the root to node n. Thus for a root the depth is always zero.

 

4. What is the length of the path in a tree?

The length of the path is the number of edges on the path. In a tree there is exactly one path form the root to each node.

 

5. Define sibling?

Nodes with the same parent are called siblings.

 

6. Define binary tree?

A Binary tree is a finite set of data items which is either empty or consists of a single item called root and two disjoin binary trees called left sub tree max degree of any node is two.

 

7. What are the two methods of binary tree implementation?

Two methods to implement a binary tree are,

a. Linear representation.

b. Linked representation

 

8. What are the applications of binary tree?

Binary tree is used in data processing.

a. File index schemes

b. Hierarchical database management system

 

9. List out few of the Application of tree data-structure?

Ø The manipulation of Arithmetic expression

Ø Used for Searching Operation

Ø Used to implement the file system of several popular operating systems

Ø Symbol Table construction

Ø Syntax analysis

 

10. Define expression tree?

Expression tree is also a binary tree in which the leafs terminal nodes or operands and non-terminal intermediate nodes are operators used for traversal.

 

11. Write the procedure to construct the expression trees?

1. Convert the given infix expression into postfix notation

2. Create a stack and read each character of the expression and push into the stack, if operands are encountered.

3. When an operator is encountered pop 2 values from the stack.

 

12. Define tree traversal and mention the type of traversals?

Visiting of each and every node in the tree exactly is called as tree traversal.

Three types of tree traversal

1. Inorder traversal

2. Preoder traversal

3. Postorder traversal.

 

13. Define in -order traversal?

In-order traversal entails the following steps;

a. Traverse the left subtree

b. Visit the root node

c. Traverse the right subtree

 

14. Define threaded binary tree.

A binary tree is threaded by making all right child pointers that would normally be null point to the inorder successor of the node, and all left child pointers that would normally be null point to the inorder predecessor of the node.

 

15. What are the types of threaded binary tree?

Right-in threaded binary tree

Left-in threaded binary tree

Fully-in threaded binary tree

 

16. Define 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.

 

17. List out the steps involved in deleting a node from a binary search tree.

  1. Deleting a node is a leaf node (ie) No children
  2. Deleting a node with one child.
  3. Deleting a node with two Childs.

 

18.Show the result of inserting 3,1,4,6,9,2,5,7 into an initially empty binary search tree.

clip_image001

 

19. Define lazy deletion?

When an element is to be deleted it is left in the tree itself and marked a s being deleted. This is called as lazy deletion and is an efficient procedure if duplicate keys are present in the binary search tree, because the field that keeps count of the frequency of appearance of the element can be decremented of the element can be decremented.

 

20. Define complete binary tree.

If all its levels, possible except the last, have maximum number of nodes and if all the nodes in the last level appear as far left as possible.

PART - B

  1. Explain the tree traversal techniques with an example.
  2. Explain binary search tree in detail.
  3. Construct an expression tree for the expression (a+b*c) + ((d*e+f)*g). Give the outputs when you apply inorder, preorder and postorder traversals.
  4. How to insert an element into a binary search tree and write down the code for the insertion routine with an example.
  5. How to remove an element from binary search tree and its algorithm with example.
  6. Explain the concept of threaded binary tree with example.
  7. What are threaded binary tree? Write an algorithm for inserting a node in a threaded binary tree.
  8. Create a binary search tree for the following numbers start from an empty binary search tree. 45,26,10,60,70,30,40 Delete keys 10,60 and 45 one after the other and show the trees at each stage.
  9. What are the different storage representations for a binary tree? Explain with example.

Labels: ,

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)