• Wrong document? Swap it for free
  • Written by students who passed
  • Immediately available after payment
  • Read online or as PDF
Sell
Where do you study
Your language
Document preview thumbnail
Preview 4 out of 302 pages
Exam (elaborations)

Cs8391-Data Structures Question Bank

Document preview thumbnail
Preview 4 out of 302 pages

PART-A 1.Define data structure. The data structure can be defined as the collection of elements and all the possible operations which are required for those set of elements. Formally data structure can be defined as a data structure is a set of domains D, a set of domains F and a set of axioms A. this triple (D,F,A) denotes the data structure d. 2. What do you mean by non-linear data structure? Give example. The non-linear data structure is the kind of data structure in which the data may be arranged in hierarchical fashion. For example- Trees and graphs. 3. What do you linear data structure? Give example. The linear data structure is the kind of data structure in which the data is linearly arranged. For example- stacks, queues, linked list. 4. What is abstract data type? What are all not concerned in an ADT?(NOV/DEC 2019) The abstract data type is a triple of D i.e. set of axioms, F-set of functions and A-Axioms in which only what is to be done is mentioned but how is to be done is not mentioned. Thus ADT is not concerned with implementation details. 5. What is a linked list?(NOV/DEC 2019) A linked list is a set of nodes where each node has two fields ‘data’ and ‘link’. The data field is used to store actual piece of information and link field is used to store address of next node. 6. Define doubly linked list. Doubly linked list is a kind of linked list in which each node has two link fields. One link field stores the address of previous node and the other link field stores the address of the next node. 7. State the advantages of circular lists over doubly linked list. In circular list the next pointer of last node points to head node, whereas in doubly linked list each node has two pointers: one previous pointer and another is next pointer. The main advantage of circular list over doubly linked list is that with the help of single pointer field we can access head node quickly. Hence some amount of memory get saved because in circular list only one pointer is reserved. 8. What are the advantages of doubly linked list over singly linked list? The doubly linked list has two pointer fields. One field is previous link field and another is next link field. Because of these two pointer fields we can access any node efficiently whereas in singly linked list only one pointer field is there which stores forward pointer. 9. What is the circular linked list?(NOV/DEC 2018) The circular linked list is a kind of linked list in which the last node is connected to the first node or head node of the linked list. This node is useful for getting the starting address of the linked list. 10. What is the advantage of an ADT?(NOV/DEC 2018) Change: the implementation of the ADT can be changed without making changes in the client program that uses the ADT. Understandability: ADT specifies what is to be done and does not specify the implementation details. Hence code becomes easy to understand due to ADT. Reusability: the ADT can be reused by some program in future. PART-B 1. Explain the insertion operation in linked list. How nodes are inserted after a specified node.(NOV/DEC 2019) 2. Write an algorithm to perform add, delete and display operation using LIST ADT? (NOV/DEC 2018) 3. Discuss deletion operation in circular linked lists.(NOV/DEC 2018) 4. Discuss the insertion operation for a doubly linked list. 5. How to perform deletion operation using linked list? 6. How polynomial expression can be represented using linked list for addition? (NOV/DEC 2018,NOV/DEC 2019) 7. Discuss the deletion operation for doubly linked list. UNIT II PART-A 1. Define Stack A Stack is an ordered list in which all insertions (Push operation) and deletion (Pop operation) are made at one end, called the top. The topmost element is pointed by top. The top is initialized to -1 when the stack is created that is when the stack is empty. In a stack S = (a1,an), a1 is the bottom most element and element a is on top of element ai-1. Stack is also referred as Last In First Out (LIFO) list. 2. What are the various Operations performed on the Stack? The various operations that are performed on the stack are CREATE(S) – Creates S as an empty stack. PUSH(S,X) – Adds the element X to the top of the stack. POP(S) – Deletes the top most elements from the stack. TOP(S) – returns the value of top element from the stack. ISEMTPTY(S) – returns true if Stack is empty else false. ISFULL(S) - returns true if Stack is full else false. 3.What are the postfix and prefix forms of the expression? A+B*(C-D)/(P-R) Postfix form: ABCD-*PR-/+ Prefix form: +A/*B-CD-PR 4.Explain the usage of stack in recursive algorithm implementation? In recursive algorithms, stack data structures is used to store the return address when a recursive call is encountered and also to store the values of all the parameters essential to the current state of the function. 5.Define Queue. A Queue is an ordered list in which all insertions take place at one end called the rear, while all deletions take place at the other end called the front. Rear is initialized to -1 and front is initialized to 0. Queue is also referred as First In First Out (FIFO) list. 6.What are the various operations performed on the Queue? The various operations performed on the queue are CREATE(Q) – Creates Q as an empty Queue. Enqueue(Q,X) – Adds the element X to the Queue. Dequeue(Q) – Deletes a element from the Queue. ISEMTPTY(Q) – returns true if Queue is empty else false. ISFULL(Q) - returns true if Queue is full else false.

Content preview

CS8391-DATA STRUCTURES QUESTION BANK

UNIT I
PART-A
1. Define data structure.

The data structure can be defined as the collection of elements and all the possible
operations which are required for those set of elements. Formally data structure can be defined as
a data structure is a set of domains D, a set of domains F and a set of axioms A. this triple
(D,F,A) denotes the data structure d.

2. What do you mean by non-linear data structure? Give example.

The non-linear data structure is the kind of data structure in which the data may be
arranged in hierarchical fashion. For example- Trees and graphs.

3. What do you linear data structure? Give example.

The linear data structure is the kind of data structure in which the data is linearly
arranged. For example- stacks, queues, linked list.

4. What is abstract data type? What are all not concerned in an ADT?(NOV/DEC 2019)

The abstract data type is a triple of D i.e. set of axioms, F-set of functions and A-Axioms
in which only what is to be done is mentioned but how is to be done is not mentioned. Thus ADT
is not concerned with implementation details.
5. What is a linked list?(NOV/DEC 2019)

A linked list is a set of nodes where each node has two fields ‘data’ and ‘link’. The data
field is used to store actual piece of information and link field is used to store address of next
node.


6. Define doubly linked list.

Doubly linked list is a kind of linked list in which each node has two link fields. One link
field stores the address of previous node and the other link field stores the address of the next
node.

7. State the advantages of circular lists over doubly linked list.

In circular list the next pointer of last node points to head node, whereas in doubly linked
list each node has two pointers: one previous pointer and another is next pointer. The main
advantage of circular list over doubly linked list is that with the help of single pointer field we
can access head node quickly. Hence some amount of memory get saved because in circular list

,only one pointer is reserved.

8. What are the advantages of doubly linked list over singly linked list?

The doubly linked list has two pointer fields. One field is previous link field and another
is next link field. Because of these two pointer fields we can access any node efficiently whereas
in singly linked list only one pointer field is there which stores forward pointer.


9. What is the circular linked list?(NOV/DEC 2018)

The circular linked list is a kind of linked list in which the last node is connected to
the first node or head node of the linked list.

This node is useful for getting the starting address of the linked list.

10. What is the advantage of an ADT?(NOV/DEC 2018)

➢ Change: the implementation of the ADT can be changed without making changes in
the client program that uses the ADT.
➢ Understandability: ADT specifies what is to be done and does not specify the
implementation details. Hence code becomes easy to understand due to ADT.
➢ Reusability: the ADT can be reused by some program in future.

PART-B
1. Explain the insertion operation in linked list. How nodes are inserted after a specified
node.(NOV/DEC 2019)

2. Write an algorithm to perform add, delete and display operation using LIST ADT?

(NOV/DEC 2018)

3. Discuss deletion operation in circular linked lists.(NOV/DEC 2018)

4. Discuss the insertion operation for a doubly linked list.

5. How to perform deletion operation using linked list?

6. How polynomial expression can be represented using linked list for addition? (NOV/DEC
2018,NOV/DEC 2019)

7. Discuss the deletion operation for doubly linked list.

, UNIT II

PART-A

1. Define Stack
A Stack is an ordered list in which all insertions (Push operation) and deletion (Pop
operation) are made at one end, called the top. The topmost element is pointed by top. The top is
initialized to -1 when the stack is created that is when the stack is empty. In a stack S = (a1,an),
a1 is the bottom most element and element a is on top of element ai-1. Stack is also referred as
Last In First Out (LIFO) list.

2. What are the various Operations performed on the Stack?
The various operations that are performed on the stack are

CREATE(S) – Creates S as an empty stack.

PUSH(S,X) – Adds the element X to the top of the stack.
POP(S) – Deletes the top most elements from the stack.
TOP(S) – returns the value of top element from the stack.
ISEMTPTY(S) – returns true if Stack is empty else false.
ISFULL(S) - returns true if Stack is full else false.
3. What are the postfix and prefix forms of the expression?

A+B*(C-D)/(P-R)

Postfix form: ABCD-*PR-/+
Prefix form: +A/*B-CD-PR
4. Explain the usage of stack in recursive algorithm implementation?
In recursive algorithms, stack data structures is used to store the return address when a
recursive call is encountered and also to store the values of all the parameters essential to the
current state of the function.

5. Define Queue.

A Queue is an ordered list in which all insertions take place at one end called the rear, while
all deletions take place at the other end called the front. Rear is initialized to -1 and front is
initialized to 0. Queue is also referred as First In First Out (FIFO) list.

6. What are the various operations performed on the Queue?

The various operations performed on the queue are
CREATE(Q) – Creates Q as an empty Queue.
Enqueue(Q,X) – Adds the element X to the Queue.
Dequeue(Q) – Deletes a element from the Queue.
ISEMTPTY(Q) – returns true if Queue is empty else false.
ISFULL(Q) - returns true if Queue is full else false.

, 7. How do you test for an empty Queue?
The condition for testing an empty queue is rear=front-1. In linked list implementation of
queue the condition for an empty queue is the header node link field is NULL.


8.Define Dequeue.(NOV/DEC 2019)
Dequeue stands for Double ended queue. It is a linear list in which insertions and
deletion are made from either end of the queue structure.


9.Define Circular Queue.
Another representation of a queue, which prevents an excessive use of memory by
arranging elements/ nodes Q1,Q2,…Qn in a circular fashion. That is, it is the queue, which wraps
around upon reaching the end of the queue

10.List any four applications of stack.(NOV/DEC 2018,NOV/DEC 2019)
 Parsing context free languages
 Evaluating arithmetic expressions
 Function call
 Traversing trees and graph
 Tower of Hanoi

PART-B

1. Write an algorithm for Push and Pop operations on Stack using Linked list.(NOV/DEC
2019)
2. Explain the array implementation of stack ADT in detail?
3. Explain in detail about circular queue.
4. Write the algorithm for converting infix expression to postfix (polish)
expression?(NOV/DEC 2019)
5. Explain in detail about priority queue ADT in detail?
6. What is Queue? Explain its operation and implement it using array.(NOV/DEC 2019)
7. Explain linked list implementation of queue ADT in detail?

Document information

Uploaded on
January 17, 2025
Number of pages
302
Written in
2024/2025
Type
Exam (elaborations)
Contains
Questions & answers
$8.99

Wrong document? Swap it for free Within 14 days of purchase and before downloading, you can choose a different document. You can simply spend the amount again.
Written by students who passed
Immediately available after payment
Read online or as PDF

Seller avatar
Reputation scores are based on the amount of documents a seller has sold for a fee and the reviews they have received for those documents. There are three levels: Bronze, Silver and Gold. The better the reputation, the more your can rely on the quality of the sellers work.
NurseBernie
4.7
(217)
Sold
798
Followers
115
Items
1763
Last sold
5 days ago



Why students choose Stuvia

Created by fellow students, verified by reviews

Quality you can trust: written by students who passed their tests and reviewed by others who've used these notes.

Didn't get what you expected? Choose another document

No worries! You can instantly pick a different document that better fits what you're looking for.

Pay as you like, start learning right away

No subscription, no commitments. Pay the way you're used to via credit card and download your PDF document instantly.

Student with book image

“Bought, downloaded, and aced it. It really can be that simple.”

Alisha Student

Working on your references?

Create accurate citations in APA, MLA and Harvard with our free citation generator.

Working on your references?

Frequently asked questions