Q Explain queue with the help of an example. What are the types of operations that can be performed on a queue? How can you represent a queue in the form of a linked list?
---------------------------
Ans
A queue is a list of elements in which items are inserted at one end of the queue and deleted from the other end of the queue. You can think of a queue as an open ended pipe, with elements being pushed from one end and coming out of another. The end at which elements are inserted is called the rear, and the end from which the elements are deleted is called the front. A queue is also called a First-In-First-Out (FIFO) list because the first element to be inserted in the queue is the first one to be deleted. The queue data structure is similar to the queues in real life.
The following two types of operations can be performed on queues:
•Insert: It refers to the addition of an item in the queue. Items are always inserted at the rear end of the queue.
•Delete: It refers to the deletion of an item from a queue. Items are always deleted from the front of the queue. When an item is deleted, the next item in the sequence becomes the front end of the queue.
class Node
{
public int data; public Node next;
}
class LinkedQueue
{
Node FRONT, REAR;
public LinkedQueue()
{
FRONT = null;
REAR = null;
}
public void insert (int element)
{
}
public void remove()
{
}
public void display()
{
}
}
===========================================
Q Peter has been assigned a task to develop a code to implement a delete operation on a binary search tree. However, before doing so, he first needs to write a code to locate the position of the node to be deleted and its parent. To do so, he has written the following algorithm:
1. Make a variable/pointer currentNode point to the root node.
2. Make a variable/pointer parent point to root.
3. Repeat the steps, a, b, and c until currentNode becomes NULL or the value of the
node to be searched becomes greater than currentNode:
a. Make parent point to currentNode.
b. If the value to be deleted is greater than that of currentNode:
i. Make currentNode point to its left child.
c. If the value to be deleted is less than that of currentNode:
i. Make currentNode point to its right child.
However, the preceding algorithm does not give the desired output. Write the correct algorithm.
-------------------
Ans
1. Make a variable/pointer currentNode point to the root node.
2. Make a variable/pointer parent point to NULL.
3. Repeat the steps, a, b, and c until currentNode becomes NULL or the value of the
node to be searched becomes equal to that of currentNode:
a. Make parent point to currentNode.
b. If the value to be deleted is less than that of currentNode:
i. Make currentNode point to its left child.
c. If the value to be deleted is greater than that of currentNode:
i. Make currentNode point to its right child.
===============================
Q.How can you represent a stack by using a linked list?
Ans...
Code in C#
class Node {
public int info;
public Node next;
public Node(int i, Node n)
{
info = i;
next = n;
}}
After representing a node of a stack, you need to declare a class to implement operations on a stack. In this class, you also need to declare a variable/pointer to hold the address of the topmost element in the stack and initialize this variable/pointer to contain the value, NULL.
class Stack
{
Node top;
public Stack()
{
top = null;
}
bool empty()
{ // Statements }
public void push(int element)
{ // Statements }
public void pop()
{ // Statements }}
After declaring the class to implement the operations on the stack, you need to implement the PUSH and POP operations.
==============================================================
Q. Define the following terms:
a. Edge
b. Depth of a tree
c. Leaf node
d. Degree of a node
e. Children of a node
Ans..
Edge: A link from a parent to a child node is known as an edge.
b. Depth of a tree: The maximum number of levels in a tree is called the depth of
a tree.
c. Leaf node: A node with no children is called a leaf node.
d. Degree of a node: The number of sub trees of a node is called the degree of a
node.
e. Children of a node: The roots of the sub trees of a node are called the children of
the node.
=========================================================================
Q. Explain stack with the help of an example. What are the characteristics of a stack? Briefly explain the operations that can be performed on a stack?
Ans.
A stack is a collection of data items that can be accessed at only one end, which is called top. This means that the items are inserted and deleted at the top. The last item that is inserted in a stack is the first one to be deleted. Therefore, a stack is called a Last-In-First-Out (LIFO) data structure.
A stack is like an empty box containing books, which is just wide enough to hold the books in one pile. The books can be placed, as well as removed, only from the top of the box. The book most recently put in the box is the first one to be taken out. The book at the bottom is the first one to be put inside the box and the last one to be taken out.
The characteristics of stacks are:
1. Data can only be inserted on the top of the stack.
2. Data can only be deleted from the top of the stack.
3. Data cannot be deleted from the middle of the stack. All the items from the top
first need to be removed.
The following two basic operations can be performed on a stack:
1. PUSH
2. POP
When you insert an item into a stack, you say that you have pushed the item into the stack. When you delete an item from a stack, you say that you have popped the item from the stack.
==========================================================================
Q. John has been assigned a task to develop a code to implement preorder traversal of a binary tree. He has developed the code according to the following algorithm:
preorder (root)
1. If (root = NULL):
a. Exit.
2. preorder (left child of root).
3. Visit (root).
4. preorder (right child of root).
Analyze the algorithm and check if the same will execute as expected. Suggest changes, if required. Also, write the algorithm for postorder traversal of a binary tree.
==
Ans.
The given algorithm is incorrect. The algorithm for preorder traversal of tree is:
preorder (root)
1. If (root = NULL):
a. Exit.
2. Visit (root).
3. preorder (left child of root).
4. preorder (right child of root).
The algorithm for postorder traversal of a tree is:
postorder (root)
1. If (root = NULL):
a. Exit.
2. postorder (left child of root).
3. postorder (right child of root).
4. Visit (root).
===========================================================================
Q. Explain stack with the help of an example. What are the characteristics of a stack? Briefly explain the operations that can be performed on a stack?
==
Ans.
A stack is a collection of data items that can be accessed at only one end, which is called top. This means that the items are inserted and deleted at the top. The last item that is inserted in a stack is the first one to be deleted. Therefore, a stack is called a Last-In-First-Out (LIFO) data structure.
A stack is like an empty box containing books, which is just wide enough to hold the books in one pile. The books can be placed, as well as removed, only from the top of the box. The book most recently put in the box is the first one to be taken out. The book at the bottom is the first one to be put inside the box and the last one to be taken out.
The characteristics of stacks are:
1. Data can only be inserted on the top of the stack.
2. Data can only be deleted from the top of the stack.
3. Data cannot be deleted from the middle of the stack. All the items from the top
first need to be removed.
The following two basic operations can be performed on a stack:
1. PUSH
2. POP
When you insert an item into a stack, you say that you have pushed the item into the stack. When you delete an item from a stack, you say that you have popped the item from the stack.
==================================================================
Q. Explain briefly how can you represent a binary tree?
==
Ans..
To represent a binary tree, you need to declare two classes:
•A class to represent a node of the tree: This class represents the structure of each node in a binary tree. A node in a binary tree consists of the following parts:
?Information: It refers to the information held by each node in a binary tree.
?Left child: It holds the reference of the left child of the node.
?Right child: It holds the reference of the right child of the node.
•A Class to represent the binary tree: This class implements various operations on a binary tree, such as insert, delete, and traverse. The class also provides the declaration of the variable/pointer root, which contains the address of the root node of the tree.
==============================================================================
