Q1. What is the time complexity improvement of skip lists from linked lists in insertion and deletion?.
A. O(n) to O(logn) where n is number of elements.
B. O(n) to O(1) where n is number of elements.
C. no change.
D. O(n) to O(n2) where n is number of elements.
Answer= O(n) to O(logn) where n is number of elements
Q2. To which datastructure are skip lists similar to in terms of time complexities in worst and best cases?.
A. balanced binary search trees.
B. binary search trees.
C. binary trees.
D. linked lists.
Answer= balanced binary search trees
Q3. The nodes in a skip list may have many forward references. their number is determined.
A. probabilistically.
B. randomly.
C. sequentially.
D. orthogonally.
Answer= probabilistically
Q4. Are the below statements true about skiplists? In a sorted set of elements skip lists can implement the below operations i.given a element find closest element to the given value in the sorted set in O(logn) ii.find the number of elements in the set whose values fall a given range in O(logn).
A. TRUE.
B. FALSE.
C. Nothing can be said.
D. None of the mentioned.
Answer= TRUE
Q5. How to maintain multi-level skip list properties when insertions and deletions are done?.
A. design each level of a multi-level skip list with varied probabilities.
B. that cannot be maintained.
C. rebalancing of lists.
D. reconstruction.
Answer= design each level of a multi-level skip list with varied probabilities
Q6. Is a skip list like balanced tree?.
A. TRUE.
B. FALSE.
C. Nothing can be said.
D. None of the mentioned.
Answer= TRUE
Q7. What is indexed skip list?.
A. it stores width of link in place of element.
B. it stores index values.
C. array based linked list.
D. indexed tree.
Answer= it stores width of link in place of element
Q8. The self organizing list improves the efficiency of _______.
A. binary search.
B. jump search.
C. sublist search.
D. linear search.
Answer= linear search
Q9. Which of the following is true about the Move-To-Front Method for rearranging nodes?.
A. node with highest access count is moved to head of the list.
B. requires extra storage.
C. may over-reward infrequently accessed nodes.
D. requires a counter for each node.
Answer= may over-reward infrequently accessed nodes
Q10. What technique is used in Transpose method?.
A. searched node is swapped with its predecessor.
B. node with highest access count is moved to head of the list.
C. searched node is swapped with the head of list.
D. searched nodes are rearranged based on their proximity to the head node.
Answer= searched node is swapped with its predecessor
Q11. The worst case running time of a linear search on the self organizing list is ____.
A. O(1).
B. O(logn).
C. O(n).
D. O(n2).
Answer= O(n)
Q12. Which of the following data structure is preferred to have lesser search time when the list size is small?.
A. search tree.
B. sorted list.
C. self organizing list.
D. linked list.
Answer= self organizing list
Q13. In _____________ method, whenever a node is accessed, it might move to the head of the list if its number of accesses becomes greater than the records preceding it..
A. least recently used.
B. count.
C. traspose.
D. exchange.
Answer= count
Q14. Symbol tables during compilation of program is efficiently implemented using __________.
A. a singly linked list.
B. a doubly linked list.
C. a self organizing list.
D. an array.
Answer= a self organizing list
Q15. Which of the following method performs poorly when elements are accessed in sequential order?.
A. count method.
B. move to front method.
C. transpose meth.
D. ordering method.
Answer= move to front method
Q16. The self organizing list improves _____.
A. average access time.
B. insertion.
C. deletion.
D. binary search.
Answer= average access time
Q17. Which of the following is not the rearranging method used to implement self-organizing lists?.
A. count method.
B. move to front method.
C. ordering method.
D. least frequently used.
Answer= least frequently used
Q18. What is xor linked list ?.
A. uses of bitwise XOR operation to decrease storage requirements for doubly linked lists.
B. uses of bitwise XOR operation to decrease storage requirements for linked lists.
C. uses of bitwise operations to decrease storage requirements for doubly linked lists.
D. just another form of linked list.
Answer= uses of bitwise XOR operation to decrease storage requirements for doubly linked lists
Q19. What does a xor linked list have ?.
A. every node stores the XOR of addresses of previous and next nodes.
B. actuall memory address of next node.
C. every node stores the XOR of addresses of previous and next two nodes.
D. every node stores xor 0 and the current node address.
Answer= every node stores the XOR of addresses of previous and next nodes
Q20. What does first and last nodes of a xor linked lists contain ? (let address of first and last be A and B).
A. NULL xor A and B xor NULL.
B. NULL and NULL.
C. A and B.
D. NULL xor A and B.
Answer= NULL xor A and B xor NULL
Q21. Disadvantages of xor lists.
A. Almost of debugging tools cannot follow the XOR chain, making debugging difficult.
B. You need to remember the address of the previously accessed node in order to calculate the next node's address.
C. In some contexts XOR of pointers is not defined.
D. All of the mentioned.
Answer= All of the mentioned
Q22. Free lists are used in.
A. static memory allocation.
B. dynamic memory allocation.
C. contagious allocations.
D. are used for speeding up linked list operations.
Answer= dynamic memory allocation
Q23. What are implicit and explicit implementations of freelists?.
A. garbage collection and new or malloc operators respectively.
B. new or malloc and garbage collection respectively.
C. implicit implementation is not favored.
D. explicit implementation is not favored.
Answer= garbage collection and new or malloc operators respectively
Q24. What datastructures can be used in implementing a free list?.
A. only linked list.
B. linked list or sort trees.
C. arrays.
D. trees.
Answer= linked list or sort trees
Q25. What are different ways of implementing free lists and which is simple among them?.
A. best fit, first fit, worst fit, simple-first fit.
B. best fit, first fit, worst fit, simple-best fit.
C. best fit, first fit, worst fit, simple-worst fit.
D. best fit simple-best fit.
Answer= best fit, first fit, worst fit, simple-first fit
Q26. What is buddy memory management of free lists ?.
A. modified version of first fit.
B. buddy allocation keeps several†‬free lists,†‬each one holds blocks which are of one particular size.
C. modified version of best fit.
D. a tree representation of free lists.
Answer= buddy allocation keeps several†‬free lists,†‬each one holds blocks which are of one particular size
Q27. How does implicit free lists(garbage collection) works in adding memory to free list ?.
A. whichever comes last will be added to free list.
B. whichever comes first will be added to free list.
C. certain blocks cannot be used if there are no pointers to them and hence they can be freed.
D. makes a probabilistic guess.
Answer= certain blocks cannot be used if there are no pointers to them and hence they can be freed
Q28. What are the disadvantages in implementing buddy system algorithm for free lists ?.
A. internal fragmentation.
B. it takes so much space.
C. we no more have the hole lists in order of memory address, so it is difficult to detect if 2 holes remain adjacent in memory and shall be merged into one hole.
D. both a and c are correct.
Answer= both a and c are correct
Q29. How are free blocks linked together mostly and in what addressing order?.
A. circular linked list and increasing addressing order.
B. linked list and decreasing addressing order.
C. linked list and in no addressing order.
D. none of the mentioned.
Answer= circular linked list and increasing addressing order
Q30. Accessing free list very frequently for wide range of addresses can lead to.
A. paging.
B. segmentation fault.
C. memory errors.
D. cache problems.
Answer= paging
Q31. Binary trees can have how many children?.
A. 2.
B. any number of children.
C. 0 or 1 or 2.
D. 0 or 1.
Answer= 0 or 1 or 2
Q32. Disadvantage of using array representation for binary trees is?.
A. difficulty in knowing children nodes of a node.
B. difficult in finding the parent of a node.
C. have to know the maximum number of nodes possible before creation of trees.
D. difficult to implement.
Answer= have to know the maximum number of nodes possible before creation of trees
Q33. What must be the ideal size of array if the height of tree is 'l'?.
A. 2l-1.
B. l-1.
C. l.
D. 2l.
Answer= 2l-1