Friday, October 21, 2005

Linked List

TWO MARK QUESTIONS...

1) What is a linear linked list?
If each item of a list itself has the pointer to the next item, which gives an explicit ordering of elements is known as linear linked list. Each item contain the information field which contain the actual information and the next address field which is used to access the next item.

2) What is empty list or Null list?
The list having no items is called empty list or null list. The external pointer to empty list is null pointer. The empty list is initialized as list=null

3) Write the procedure for inserting an element in the list.
p=getnode( );
info(p)=x;
next(p)=list;
list=p;

4) Write the procedure for deleting an element from the list.
p=list;
list=next(p);
x=info(p);
freenode(p);

5) What are the disadvantages of representing a stack or queue by linked list?
A node in linked list occupies more storage than corresponding element as it needs an explicit pointer for next item.
Additional time is spent in managing the available list. When an node is deleted, modifications are needed to either the previous or next node or both.

6) What are the advantages of using a linked list rather than array?
While inserting or deleting element from the middle of an array, all the elements should be moved to avoid the empty locations. But, linked list does not need to move all elements, but only the node pointers of two nodes will have to be modified.

7) What is a header node?
The extra node kept in front of the list is called header node. It does not represent any item in the list. It could have the global information about the list.

8) What are the limitations of array implementation of linked list?
The number of nodes needed for execution of a program can not be predicted when the program is written.
The nodes declared at beginning should remain allocated to that program till the execution is complete.

9) What is a circular linked list?
Circular linked list is the list in which the end node of the list point to the header node.

10) What is dangling pointer?
If the link pointing the node is freed by free(pointer), the node will not be used further. But, it contain some illegal information. The value of p is a valid address and the pointer that points to it can be given a *P. This P is called dangling pointer.


OTHER QUESTIONS…
1) Write a program to implement stack using linked list. (16)
2) Write a program to implement queue using linked list (16)
3) Write the procedure to delete all occurrences of number 4 from the linked list.(8)
4) Write the procedure to insert an element in the ordered list. (4)
5) Explain the list implementation of priority queue. (6)
6) Explain about header nodes, and what are the uses of it? (6)
7) Explain how linked list could be represented in an array (10)
8) Write about how the dynamic allocation and freeing of nodes takes place with example. (8)
9) How will you implement a linked list with dynamic memory allocation? (16)
10) Compare the dynamic and array implementation of lists. (6)



WORKS FOR YOU…
1) Explain with necessary diagrams to represent how nodes could be added and deleted in a linked list, in the front, last and middle. (16)
2) Unordered lists are best suited for priority queue implementation. Is this statement true or false? State reasons for your answer. (6)
3) What is the average number of nodes accessed in searching for a particular element in an unordered list? In an ordered list? In an unordered array? In an ordered array?

Thursday, October 06, 2005

Queue

Two mark Questions:

1) Define Queue.
A queue is an ordered collection of items from which items may be inserted at one end called rear end and into which items may be deleted at the other end called the front end.
2) Why queue is called FIFO list?
In a queue, the first element inserted at rear end will be the first element to be deleted at front end. So, queue is called First-in First-out list.

3) What are the difference between Stack and Queue?
Stack: The basic operations like Push and Pop can be done at only one end called top of stack.
Queue: The insertion can be done at rear end and deletion at front end.
Stack: The last element inserted will be the first to be deleted. Hence stack is LIFO list.
Queue: The First element inserted will be the first to be deleted. Hence, Queue is FIFO list.

4) What are the basic operations that could be performed on a Queue?
i) Insertion – insert(q,x) inserts x at the rear end.
ii) Removal – x=remove(q) remove the element in front end.
iii) Empty(q) – Checks whether queue has any elements or not.

5) What are the limitations of linear queue? How they can be rectified?
When an element is removed from linear queue, the location remains unused. Even if the queue is empty, new elements cannot be inserted. To avoid this, consider queue as a circle, having the first element immediately following the last element.

6) Define Priority Queue.
Priority queue is a data structure in which the intrinsic ordering of the elements determine the results of the basic operations like insertion and removal.

7) What are the two types of priority queues? Briefly explain.
Two types of priority queues are,
i) Ascending priority queue – In this queue, the items can be inserted arbitrarily and only the smallest item will be removed.
ii) Descending priority queue- This allows insertion of items arbitrarily, and only the maximum element from queue will be removed first.
8) What is the difference between queue and priority queue?
In queue the elements can be inserted only at rear end and can be removed only at front end. But in priority queue, elements can be arbitrarily inserted. But the complete queue is searched for removal of high priority element.

9) What are the limitations in priority queue? How it could be rectified?
Deletion of elements make a location empty. The search of items include the empty spaces too. This takes more time. To avoid this, use an empty indicator or shift elements forward when each element is deleted. We can also maintain priority queue as an array of ordered elements, to avoid risk in searching.

Other questions:
1) Define queue and explain the basic operations in Queue with algorithm(8)
2) Write a C program to create queue and to implement its basic operations using array(16)
3) Explain about priority queue (8)

Works for you….
1) Write a C program to implement the basic operations on Circular queue.
2) Define Deque. Write the algorithm for input restricted deque and output restricted deque.

Saturday, October 01, 2005

Stack

Two mark Questions...

1. Define stack.
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 stack.

2. What is top of stack?
The end of stack, at which the items are added or deleted is called top of stack.

3. Why stack is called LIFO list?
The last element inserted into the stack is the first element to be deleted.For this reason, stack is called Last-In First-Out list.

4.What are the operations that can be performed on a stack?
i) Push- Adding an item to a stack. Push(S,i) adds an item i to the top of stack.
ii) Pop - Removes an item from stack. i=Pop(S) returns the top element to i.

5. What is empty stack?
The stack which contains no items in it is called Empty stack.

6. What causes underflow of stack? How it could be avoided?
If an illegal attempt is made to pop or access an item from empty stack, it causes stack underflow.
To avoid underflow, before any pop(S) or stacktop(S), check whether empty(S) is true or false.

7. What is nesting depth and parenthesis counts in an expression?
Nesting depth is the number of scope that have been opened, but not yet closed at that point.
Parenthesis count is the number of left parenthesis minus number of right parenthesis encountered at a particular point when the expression is scanned from left end.

8. What are the two conditions for admissible pattern of expression?
i. The Parenthesis count at the end of the expression is 0.
ii. The parenthesis count at each point in the expression is nonnegative

9. How an expression is validated if the delimiters are different?
The delimiters in an expression can be (,), [,] and {,}. But the scope ender must be same as scope opener. The number of scopes and type of scopes should be kept on account
Push scope opener to stack. When scope ender is encountered, check if the opener is matching. Otherwise, expression is invalid. At the end of expression, stack must be empty. Otherwise, expression is invalid

10. What are the limitations in the stack, When array used as home of stack?
The Array is finite collection of elements and in stack the number of elements is unlimited. As the stack dynamically changes the attempt to insert more elements than the array size cause overflow

11. Define Modularization?
Modularization is the concept of isolating the complex implementation into set of independent and easily identifiable units, to make the program easily understandable and modifiable.

12. What are the error conditions that could occur in stack implementation? How could they be rectified?
i) Overflow
ii) Underflow
To avoid overflow, the stack should be checked whether it is full or not before every push operation.
To avoid underflow, the stack should be checked for emptiness before every pop operation.

13. What is overflow in stack?
When array is used as home of stack, and when the stack contains as many elements as array, and as attempt is to push another element on stack, it cause overflow.

14. Why infix expression should be converted to Prefix / Postfix?
In Infix, operator precedence can be set only after scanning the expression for several times. But, conversion of Infix to Postfix or Prefix with use of stack, help to set precedence based on order of arrangement in a single scanning

15. Convert ((A+B) * C – (D – E)) $ (F + G) To Postfix and Prefix notation.
Prefix : $ - * + ABC – DE + FG.
Postfix : AB + C * DE -- FG + $


Other Questions:

1. Write the algorithm to check the validity of expression. (6)
2. Write the ADT For Stack (6)
3. Write a Program to implement the stack operations like push, pop and peep using arrays (16)
4. Convert 4$2*3-3+8/4/(1+1) to postfix using stack (10)
5. Write the algorithm to evaluate postfix expression (8)
6. Evaluate the following postfix expression using stack 653*+1-93/+
7. Write a program in C, to evaluate postfix expression (16)
8. Write the algorithm to convert Infix expression to postfix (8)
9. Write C program to convert Infix to Postfix (16)


Works For You........

1. Stack is static object. Is this statement true or False ? Comment the reason for your answer.

2. Write Parenthesis count at each point of the following expressions and check whether it is valid or not?
i) A+ ((( B-C) * (D-E) + F) / G)
ii) (a-b (C+D)) * (a - b)
iii) A- (B-C)(C-D) (D+(E*F)

3. Show contents of stack, at each point of the expression
i) (A+B})
ii) (A+B) -{C+D}-[F+G]
iii) {[A+B]}-[(C+D)]
iv) ((H) * {([J+K])})
v) ((( A ))))

4. Convert the following Infix expression to Postfix and Prefix
i) A+B* C+D/E + F/G
ii) ((X+Y) * (W+Z)) / (A*B) + (C/D)
iii) A+B+C+D+E

5. Evaluate the following Postfix expressions
i) AB + C - BA+ C$-
ii) ABC+* CBA-+*

(Assume A=1, B=2, C=3)