1) Define linked list.
Ans:A linked list is a data structure used for storing collections of data.
2) Why constant time for accessing array elements?
Ans:To access an array element, the address of an element is computed as an offset from the base address of the array and one multiplication is needed to compute what is supposed to be added to the base address to get the memory address of the element. First the size of an element of that data type is calculated and then it is multiplied with the index of the element to get the value to be added to the base address.
This process takes one multiplication and one addition. Since these two operations take constant time, we can say the array access can be performed in constant time.
3) Another name for dynamic array
a) array list
b) list
c) linked list
d) none
Ans:a(Array list)
4) How to implement dynamic arrays?
Ans:Initially start with some fixed size array. As soon as that array becomes full, create the new array double the size of the original array. Similarly, reduce the array size to half if the elements in the array are less than half.
5) What are the basic operations on a list?
Ans:
- Traversing the list.
- Inserting an item in the list.
- Deleting an item from the list.
6) Doubly linked list is also called as
a) list
b) two-way linked list
c) skip list
d) none
Ans:b(Two-way linked list)
7) What are the primary disadvantages of doubly linked lists?
Ans:
- Each node requires an extra pointer, requiring more space.
- The insertion or deletion of node takes a bit longer.
8) Which linked lists do not have ends?
a) Single linked lust
b) doubly linked list
c) circular linked list
d) none
Ans:c(circular linked list)
9) List some applications of circular list.
Ans:
- Used in managing the computing resources of a computer.
- Implementing stacks and queues.
10) Define skip lists.
Ans:Skip list is a data structure that can be used as an alternative to balanced binary trees.
11) If the head of a linked list is pointing to kth element , then how will you get the elements before kth element.
Ans:Use memory efficient linked lists or XOR linked lists.
12) If we want to concatenate two linked lists which of the following gives O(1) complexity?
a) Singly linked lists
b) Doubly linked lists
c) Circular doubly linked lists
d) None
Ans: c(Circular Doubly Linked Lists). This is because for singly and doubly linked lists, weneed to traverse the first list till the end and append the second list. But in the case of circular doubly linked lists we don’t have to traverse the lists.
13)Is it possible to get O(1) access time for Linked Lists?
Ans: Yes. Create a linked list and at the same time keep it in a hash table. For n elements we have to keep all the elements in a hash table which gives a preprocessing time of O(n).To read any element we require only constant time O(1) and to read n elements we require n * 1 unit of time = n units. Hence by using amortized analysis we can say that element access can be performed within O(1) time.
14) In a linked list with n nodes, the time taken to insert an element after an element pointed by some pointer is
a) O(1)
b) O(logn)
c) O(n)
d) O(nlogn)
Ans:a(O(1))
15) Which sorting algorithm is easily adaptable to singly linked lists?
Ans: Simple Insertion sort is easily adabtable to singly linked lists. To insert an element, the linked list is traversed until the proper position is found, or until the end of the list is reached. It is inserted into the list by merely adjusting the pointers without shifting any elements, unlike in the array. This reduces the time required for insertion but not the time required for searching for the proper position.
16) Collection of homogenous elements is
a) array
b) lists
c) node
d) none
Ans:a(array)
17) What is fixed size array?
Ans:In fixed size array, the total size of an array is fixed or constant.
18) What is success node?
Ans:The node which comes after the inserting node is called success node.
19) Which of these best describes an array?
a) A data structure that shows a hierarchical behaviour
b) Container of objects of similar types
c) Arrays are immutable once initialised
d) Array is not a data structure
Ans:b
20) What are the disadvantages of arrays?
a) Data structure like queue or stack cannot be implemented
b) There are chances of wastage of memory space if elements inserted in an array are lesser than the allocated size
c) Index value of an array can be negative
d) Elements are sequentially accessed
Ans:b
| 
| 
