Questions on various Topics of Data Structures(Randomly Mixed) Set 8

Interview questions on binary search, bubble sort, linear search, linked lists, selection sort and trees in data structures. These questions have been arranged in random order. The questions are meant for a fresher preparing for a job interview. Please inform us if you find any mistakes. This is subjective type short answers question and answer set no. 8 in this series.

Last Reviewed and Updated on February 7, 2020
Posted by Parveen(Hoven),
Aptitude Trainer and Software Developer

Interview and Exam Questions and Answers

This set contains a list of commonly asked questions. They are short interview questions aimed at freshers interview, campus placement drives, and also for job interviews. You can use these to have a quick grasp and brush-up of your fundamentals. These questions can be viewed on a mobile phone also because this website is built on responsive web design.

Definitions

How do you define terms:

  1. Siblings/Brothers
  2. Internal node
  3. Level of a node
  4. Depth of a tree

  1. Siblings/Brothers: Children of the same node are called siblings of each other. In the preceding figure:
    1. Nodes 7 and 3 are siblings of each other
    2. Nodes 2 and 6 are siblings of each other
  2. Internal Node: An intermediate node between the root and the leaf nodes is called an internal node. It is also referred to as a non terminal node. In preceding figure, nodes 7,3,6 and 9 are internal nodes
  3. Level of a node: The distance of a node from the root is called the level of a node. The root always lies at level 0. As move down the tree, the level of a node increases in such a way that if a node is at level n, then its children are at level n+1. In preceding figure, level of node 1 is 0, level of nodes 7 and 3 are 1 and so on.
  4. Depth of a tree: The maximum number of levels in a tree is called the depth of a tree. In other words, depth of a tree is one more than maximum level of the tree. The depth of a tree in above figure is 4

Binary searches can be done on an array[Yes/No]?

Yes.

What is the worst case performance of selection sort?

The worst case performance of selection sort is O(n2).

Suppose an array A with elements indexed 1 to n is to be searched for a value x. Write pseudo code that performs a forward search, returning n + 1 if the value is not found.

  1. Set i to 1.
  2. Repeat this loop:
    1. If i > n, then exit the loop.
    2. If A[i] = x, then exit the loop.
    3. Set i to i + 1.
  3. Return i.

Selection sort is suitable for which type of list.

Selection sort is suitable for small list.

Write an algorithm to insert a node between two nodes in the doubly-linked list.

  1. Identify the nodes between which the new node is to be inserted. Mark them as previous and current respectively. To locate previous and current, execute the following steps:
    1. Make current point to the first node.
    2. Make previous point to NULL.
    3. Repeat step d and e until current.info>newnode.info or current=NULL.
    4. Make previous point to current.
    5. Make current point to the next node in sequence.
  2. Allocate memory for the new node.
  3. Assign value to the data field of the new node.
  4. Make the next field of the new node point to current.
  5. Make the prev field of the new node point to previous.
  6. Make the prev field of current point to the new node.
  7. Make the next field of previous point to the new node.

What is the best case efficiency of binary search?

The best case efficiency of binary search is O(1).

What are steps for postorder traversing a binary tree?

The steps for post order traversing a binary tree are as follows:

  1. Traverse the left subtree
  2. Traverse the right subtree
  3. Visit the root

How does the representation of a node in a doubly-linked list differ from that in a singly-linked list?

Unlike singly-linked list, in which each node stores the address of only the next node in the list, each node in a doubly-linked list holds the address of its previous node also.

Which is the fundamental principle of hashing?

The fundamental principle of hashing is to convert a given key value to an offset address to retrieve a record.

My C/C++ Videos on Youtube

Here is the complete playlist for video lectures and tutorials for the absolute beginners. The language has been kept simple so that anybody can easily understand them. I have avoided complex jargon in these videos.