Category: Data Structure Objective Questions

Data Structures & Algorithms Multiple Choice Questions on “Self Balancing Binary Search Tree”.

1. Which of the following is not the self balancing binary search tree?
a) AVL Tree
b) 2-3-4 Tree
c) Red – Black Tree
d) Splay Tree

Answer: b
Clarification: 2-3-4 Tree is balanced search trees. But it is not a binary tree. So, it is not a self balancing binary tree. AVL tree, Red-Black Tree and Splay tree are self balancing binary search tree.

2. The binary tree sort implemented using a self – balancing binary search tree takes ______ time is worst case.
a) O(n log n)
b) O(n)
c) O(n²)
d) O(log n)

Answer: a
Clarification: The worst case running time of the binary tree sort is O(n²). But, the worst case running time can be improved to the O(n log n) using a self – balancing binary search tree.

3. An AVL tree is a self – balancing binary search tree, in which the heights of the two child sub trees of any node differ by _________
a) At least one
b) At most one
c) Two
d) At most two

Answer: b
Clarification: In an AVL tree, the difference between heights of the two child sub trees of any node is at most one. If the height differs by more than one, AVL tree performs rotations to balance the tree.

4. Associative arrays can be implemented using __________
a) B-tree
b) A doubly linked list
c) A single linked list
d) A self balancing binary search tree

Answer: d
Clarification: Associative arrays can be implemented using a self balancing binary search tree as the worst-case time performance of self – balancing binary search trees is O(log n).

5. Self – balancing binary search trees have a much better average-case time complexity than hash tables.
a) True
b) False

Answer: b
Clarification: For lookup, insertion and deletion hash table take O(1) time in average-case while self – balancing binary search trees takes O(log n). Therefore, hash tables perform better in average-case.

6. Which of the following is a self – balancing binary search tree?
a) 2-3 tree
b) Threaded binary tree
c) AA tree
d) Treap

Answer: c
Clarification: An AA tree, which is a variation of red-black tree, is a self – balancing binary search tree. 2-3 is B-tree of order 3 and Treat is a randomized binary search tree. A threaded binary tree is not a balanced tree.

7. A self – balancing binary search tree can be used to implement ________
a) Priority queue
b) Hash table
c) Heap sort
d) Priority queue and Heap sort

Answer: a
Clarification: Self-balancing binary search trees can be used to construct and maintain ordered lists, to achieve the optimal worst case performance. So, self – balancing binary search tree can be used to implement a priority queue, which is ordered list.

8. In which of the following self – balancing binary search tree the recently accessed element can be accessed quickly?
a) AVL tree
b) AA tree
c) Splay tree
d) Red – Black tree

Answer: c
Clarification: In a Splay tree, the recently accessed element can be accessed quickly. In Splay tree, the frequently accessed nodes are moved towards the root so they are quick to access again.

9. The minimum height of self balancing binary search tree with n nodes is _____
a) log₂(n)
b) n
c) 2n + 1
d) 2n – 1

Answer: a
Clarification: Self – balancing binary trees adjust the height by performing transformations on the tree at key insertion times, in order to keep the height proportional to log₂(n).

10. Binary tree sort implemented using a self balancing binary search tree takes O(n log n) time in the worst case but still it is slower than merge sort.
a) True
b) False

Answer: a
Clarification: The worst case performance of binary tree sort is O(n log n) when it is implemented using a self balancing binary search tree. Self balancing binary search trees perform transformations to balance the tree, which caused balancing overhead. Due to this overhead, binary tree sort is slower than merger sort.

Data Structures & Algorithms Multiple Choice Questions on “Ternary Tree – 1”.

1. How many child nodes does each node of Ternary Tree contain?
a) 4
b) 6
c) 5
d) 3

Answer: d
Clarification: Each node of Ternary tree contains at most 3 nodes. So Ternary tree can have 1, 2 or 3 child nodes but not more than that.

2. Which of the following is the name of the node having child nodes?
a) Brother
b) Sister
c) Mother
d) Parent

Answer: d
Clarification: Parent node is the node having child nodes and child nodes may contain references to their parents. Parent node is a node connected by a directed edge to its child.

3. What is the depth of the root node of the ternary tree?
a) 2
b) 1
c) 0
d) 3

Answer: c
Clarification: Depth is defined as the length of the path from root to the node. So the depth of root node in ternary tree is 0.

4. What is the Height of the root node of ternary tree?
a) 1
b) 2
c) 3
d) 0

Answer: d
Clarification: Height of ternary tree is defined as the length of path from root to deepest node in tree. Therefore, height off root node in ternary tree is 0.

Data Structures & Algorithms Multiple Choice Questions on “Hash Tree”.

1. Hash tree is generalization of ______
a) Heap
b) Hash list
c) BST
d) B – tree

Answer: b
Clarification: Hash list is the list of hashes of the blocks in a set file. Hash tree is a generalization of the hash list in which leaves are labeled with the hash of a data block and every non-leaf node is hash of the labels of its children.

2. Hash tree is used in effective data verification in distributed systems.
a) True
b) False

Answer: a
Clarification: Hash trees are used in distributed systems for efficient data verification. Hash tree used hashes instead of the full files, hence they are efficient. Because Hashes are ways of encoding files that are much smaller than the actual file itself.

3. Which of the following is a widely used form of the hash tree?
a) B+ – tree
b) T tree
c) Tiger tree hash
d) Htree

Answer: c
Clarification: The general form the hash tree which is used widely is the Tiger tree hash. It uses a binary hash tree, usually has a data block size of 1024 bytes and uses the Tiger hash.

4. Which of the following is true for a Hash tree?
a) Hashing is used for sequential access
b) Indexing is used for direct access
c) Hash tree allows only sequential access
d) Hashing is used for direct access

Answer: d
Clarification: Hash tree allows direct as well as sequential access of the records. Hashing is used for direct access and indexing is generally used for the sequential access.

5. Hash tree is also known as _____
a) Merkle tree
b) T -tree
c) Hash table
d) B^x-tree

Answer: a
Clarification: Hash tree is generally known as Merkle tree after Ralph Merkle who patented it in 1979. Typically Merkle trees have a branching factor of 2, meaning that each node has up to 2 children.

6. What will be the height of the hash tree with branching factor 2 and with 8 records?
a) 3
b) 5
c) 4
d) 6

7. Where is the hash tree used?
a) in digital currency
b) in sorting of large data
c) for indexing in databases
d) in encryption of data

Answer: a
Clarification: Using Hash tree the data verification, data synchronisation and the consistency verification can be done efficiently. So, the hash tree are digital currencies to organise the transactions.

8. What is the worst case time complexity of the insertion in the hash tree?
a) O(log_k(n))
b) O(n²)
c) O(nlog_k(n))
d) O(kn)

Answer: a
Clarification: To insert a record in the hash tree the key is compressed and hashed to get the slot for the entry. So, a hash tree with branching factor k takes O(log_k(n)) for insertion in worst case.

9. Sequential access in a Hash tree is faster than in B-trees.
a) True
b) False

Answer: a
Clarification: The sequential access in the hash tree is more efficient and faster than in B-tree. Because while constructing the hash tree in the expansions and contractions of the file is an estimated.

10. Hash tree is used in data synchronisation. In the worst case the data synchronisation takes ______ time.
a) O(logn)
b) O(n²)
c) O(nlogn)
d) O(n)

Answer: d
Clarification: In average scenarios, the synchronisation takes O(logn) because it is based on the traversal and searching. The worst case occurs when there are no nodes in common, so the synchronisation takes O(n) time.

/* Link list node */
struct node
{
    int data;
    struct node* next;
};
 
/* head_ref is a double pointer which points to head (or start) pointer 
  of linked list */
static void reverse(struct node** head_ref)
{
    struct node* prev   = NULL;
    struct node* current = *head_ref;
    struct node* next;
    while (current != NULL)
    {
        next  = current->next;  
        current->next = prev;   
        prev = current;
        current = next;
    }
    /*ADD A STATEMENT HERE*/
}

1->2->3->4->5->6
void fun(struct node* start)
{
    if(start == NULL)
    return;
    printf("%d  ", start->data); 
    if(start->next != NULL )
    fun(start->next->next);
    printf("%d  ", start->data);
}

typedef struct node 
{
    int value;
    struct node *next;
}Node;
 
Node *move_to_front(Node *head) 
{
    Node *p, *q;
    if ((head == NULL: || (head->next == NULL)) 
    return head;
    q = NULL; p = head;
    while (p-> next !=NULL) 
    {
        q = p;
        p = p->next;
    }
   _______________________________
  return head;
}

struct node 
{
    int value;
    struct node *next;
};
void rearrange(struct node *list)
{
    struct node *p, * q;
    int temp;
    if ((!list) || !list->next) 
      return;
    p = list;
    q = list->next;
    while(q) 
    {
         temp = p->value;
         p->value = q->value;
         q->value = temp;
         p = q->next;
         q = p?p->next:0;
    }
}

    struct node *temp  = X->next;
    X->data  = temp->data;
    X->next  = temp->next;
    free(temp);

7. You are given pointers to first and last nodes of a singly linked list, which of the following operations are dependent on the length of the linked list?
a) Delete the first element
b) Insert a new element as a first element
c) Delete the last element of the list
d) Add a new element at the end of the list
Answer: c
Clarification: Deletion of the first element of the list is done in O (1) time by deleting memory and changing the first pointer.
Insertion of an element as a first element can be done in O (1) time. We will create a node that holds data and points to the head of the given linked list. The head pointer was changed to a newly created node.
Deletion of the last element requires a pointer to the previous node of last, which can only be obtained by traversing the list. This requires the length of the linked list.
Adding a new element at the end of the list can be done in O (1) by changing the pointer of the last node to the newly created node and last is changed to a newly created node.

8. In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is?
a) log2 n
b) ⁿ⁄₂
c) log2 n – 1
d) n
Answer: d
Clarification: The worst-case happens if the required element is at last or the element is absent in the list. For this, we need to compare every element in the linked list. If n elements are there, n comparisons will happen in the worst case.

TData Structure for Experienced people,