Basic CS-Data Structures (3i Infotech Papers): Sample Questions 1 - 3 of 52

Examrace Placement Series prepares you for the toughest placement exams to top companies.

Question number: 1

» Basic CS » Data Structures

Essay Question▾

Describe in Detail

What is a hash table? When would you can use one?

Explanation

Understanding of Hash table

Understanding of Hash Table

Understanding of Hash table

  • Value is stored in a data structure called hash table.

  • Uses a hash function to compute an index into an array which element will search.

Image of the hash table

Image of the Hash Table

Image of the hash table

  • Also used with key/value pairs to store and retrieve value using key.

  • Hash table access of data becomes very fast if we know the index of the desired data.

  • The average time required to search for an element in a hash table is O (1).

  • Basic operation of hash table:
    • Search: search an element in a hash table.

    • Insert: insert an element in a hash table.

    • Delete: Delete an element from a hash table.

Question number: 2

» Basic CS » Data Structures

Short Answer Question▾

Write in Short

If a binary tree has 20 nodes then it has how many null branches?

Explanation

  • A binary tree with 20 nodes has 21 many null branches.

  • Consider, a tree with 5 nodes (n = 5)

  • No. of null pointer = 2n- (n-1) =n + 1

  • When, n = 20

  • Then n + 1= 20 + 1=21

Question number: 3

» Basic CS » Data Structures

Essay Question▾

Describe in Detail

There are 8,15,13,14 nodes in 4 different trees. Which of them could form a full binary tree?

Explanation

  • There are 8,15,13,14 nodes in 4 different trees- of these tree with 15 nodes could be a full binary tree.

  • There are 2n-1 nodes in a full binary tree.

Method of elimination:

  • Full binary trees contain odd number of nodes- 8 and 14 nodes cannot be full binary trees.

  • 13 nodes can form a complete binary tree but not a full binary tree.

  • So, 15 nodes is a correct answer.

Bellow given full binary tree and complete binary tree:

Full binary tree and complete binary tree

Full Binary Tree and Complete Binary Tree

Full binary tree and complete binary tree

  • A complete Binary Tree has all levels completely filled except possibly the last level and the last level has all keys towards as much to the left as possible.

  • All full binary trees are complete binary trees, but all complete binary trees are not full binary trees.