Two marks Questions with Answers

Two Marks Questions with Answers

Q.1 Explain the term data structure.

Ans. : 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 functions F and a set of axioms A. This triple (D, F, A) denotes the data structure d.

Q.2 What do you mean by non linear data structure? Give examples.

Ans. : 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.

Q.3 What do you mean by linear data structure? Give example.

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

Q.4 Enlist the various operations that can be performed on data structure.

Ans. : Various operations that can be performed on the data structure are -

1. Create

2. Insertion of element

3. Deletion of element

4. Searching for the desired element

5. Sorting the elements in the data structure

6. Reversing the list of elements.

Q.5 What is abstract data type? What are all not concerned in an ADT ?

Ans; 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.

Q.6 List out the areas in which data structures are applied extensively.

Ans. Following are the areas in which the data structures are applied extensively.

1. Operating system - The data structures like priority queues are used for scheduling the jobs in the operating system.

2. Compiler design - The tree data structure is used in parsing the source program. Stack data structure is used in handling the recursive calls.

3. Database management system - The file data structure is used in database management systems. Sorting and searching techniques can be applied on these data in the file.

4. Numerical analysis package - The array is used to perform the numerical analysis on the given set of data.

5. Graphics -The array and linked list are useful in graphics applications.

6. Artificial intelligence -The graph and trees are used for the applications like building expression trees, game playing.

7. Networking - The graph is used for finding the shortest path length between any two computers that are connected in a LAN.

8. Simulation - The queue is used for simulation and modeling.

Q.7 What is a linked list ?

Ans. : 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.make sure

Q.8 What are the pitfalls encountered in singly linked list ?

Ans. : Following are the pitfalls encountered in singly linked list :

1. The singly linked list has only forward pointer and no backward link is provided. Hence the traversing of the list is possible only in one direction. Backward traversing is not possible.

2. Insertion and deletion operations are less efficient because for inserting the element at desired position the list needs to be traversed. Similarly, traversing of the list is required for locating the element which needs to be deleted.

Q.9 Define doubly linked list.

Ans; 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 next node.

Using doubly linked list traversing the linked list in forward and backward direction becomes efficient.

Q.10 Write down the steps to modify a node in linked lists.

Ans. :

1. Enter the position of the node which is to be modified.

2. Enter the new value for the node to be modified.

3. Search the corresponding node in the linked list.

4. Replace the original value of that node by a new value.

5. Display the message as "The node is modified".

Q.11 Differentiate between arrays and lists.

Ans; In arrays any element can be accessed randomly with the help of index of array, whereas in lists any element can be accessed by sequential access only.

Insertions and deletions of data is difficult in arrays on the other hand insertion and deletion of data is easy in lists.

Q.12 State the properties of LIST abstract data type with suitable example.

Ans. : Various properties of LIST abstract data type are -

1. It is linear data structure in which the elements are arranged adjacent to each other.

2. It allows to store single variable polynomial.

3. If the LIST is implemented using dynamic memory then it is called linked list. Example of LIST are - Stacks, Queues, Linked List.

Q.13 State the advantages of circular lists over doubly linked list.

Ans. : 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 field is reserved.

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

Ans. : 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, which makes accessing of any node difficult one.

Q.15 Why is linked list used for polynomial arithmetic ?

Ans. : Following are the reasons for which linked list is used for polynomial arithmetic -

i) We can have separate coefficient and exponent fields for representing each term of polynomial. Hence there is no limit for exponent. We can have any number as an exponent.

ii) The arithmetic operation on any polynomial of arbitrary length is possible using linked list.

Q.16 What is the advantage of linked list over arrays ?

Ans. : The linked list makes use of the dynamic memory allocation. Hence the user can allocate or de allocate the memory as per his requirements. On the other hand, the array makes use of the static memory location. Hence there are chances of wastage of the memory or shortage of memory for allocation.

Q.17  What is circular linked list ?

Ans. 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.

Refer section 1.8.

Q.18 What is the basic purpose of header of the linked list?

The header node is the very first node of the linked list. Sometimes a dummy value such as -999 is stored in the data field of header node. Refer Fig. 1.13.1.

This node is useful for getting the starting address of the linked list. As there is only a forward link present in the linked list, for accessing the entire linked list it is necessary to obtain the starting address of the linked list.

Q.19 What is advantage of an ADT ?

Ans. : The advantages of ADT are -

1. Change: The implementation of the ADT can be changed without making changes in the client program that uses the ADT.

2. Understandability: ADT specifies what is to be done and does not specify the implementation details. Hence code becomes easy to understand due to ADT.

3. Reusability: The ADT can be reused by some program in future.

4. Flexibility: Different implementations are possible for the same ADT.

Q.20 Should arrays of linked lists be used for the following type of applications. Justify your answer.

a) Many search operations in sorted list.

 b) Many search operations in unsorted list.

Ans. : a) If the list is sorted then using linked list the desired element can be searched, simply by moving forward using 'next' pointer.

b) If a list is not sorted then using arrays the desired element can be searched. The arrays facilitates the access to random element.

Q.21 What are abstract data type ?

OR     Define ADT

Ans. : Refer Q.5.

Q.22 What is static linked list ? State any two applications of it.

Ans. : The linked list structure which can be represented using arrays is called static linked list.

1. It is easy to implement, hence for creation of small databases, it is useful.

2. The searching of any record is efficient, hence the applications in which the record need to be searched quickly, the static linked lists are used.

Q.23 Write syntax of calloc() and relloc() and mention its applications in the linked list.

Ans. : calloc() is for allocating the required amount of memory. The syntax is void *calloc(size_t nitems, size_t size)

This function returns the pointer to the allocated memory. The calloc function is just similar to malloc but it initializes the allocated memory to zero and malloc does not.

The realloc() function modifies allocated memory size by malloc() and calloc() functions to new size. The syntax is

void *realloc (void *ptr, size_t size)

If insufficient memory exists then to expand the memory block, realloc() is used..

Q.24 State the advantage of ADT.

Ans. : Abstract Data Type (ADT) specifies only what kind of operations are to be done on data structure. It does not specify how to do those operations.

• Thus implementation details can be hidden from end user, and only important properties are represented to the user.

• ADT represents only abstract view hence it is easy for the user to understand data structure in simplistic manner.

Q.25 What are the disadvantages of linked list over arrays.

Ans. :

1) In linked list, we can access elements in sequence. So it is very difficult and time consuming to access element randomly.

2) Some amount of memory gets wasted in storing the next node's address in each nodes.