Mock 4 – Trees, Heaps & Hashing (Part 3)

Given six weights 4, 15, 25, 5, 8, 16, construct a 2-tree (binary tree). What is the minimum weighted path length?

Consider: A. The number of labelled binary trees possible with n nodes is (2n)!/(n + 1)!. B. The number of binary search trees possible with n nodes is (2n)!/((n + 1)! n!). C. The number of unlabelled binary trees possible with n nodes is C(2n, n)/(n + 1)!. D. The number of simple, undirected, labelled graphs possible with n vertices is 2^(n(n−1)/2).

Match List I with List II

How many different binary trees are possible with ' n ' nodes?

Consider a B-tree of height h and minimum degree t ≥ 2 containing n keys, n ≥ 1. Which is correct?

How many rotations are required during the construction of an AVL tree if the elements 35, 50, 40, 25, 30, 60, 78, 20, 28 are added in this sequence?

A hash function h(key) = key mod 7 with linear probing is used to insert the keys 44, 45, 79, 55, 91, 18, 63 into a table indexed 0 to 6. What will be the location of key 18?

A complete -ary tree is a tree in which each n I node has children or no children. Let be the L number of internal nodes and be the number n L = 41 of leaves in a complete -ary tree. If , I = 10 n and , What is the value of ?

In a binary max heap containing numbers, the smallest element can be found in ____ time.

In a B-Tree, each node represents a disk block. Suppose one block holds 8192 bytes. Each key uses 32 bytes. In a B-tree of order M there are M - 1 keys. Since each branch is on another disk block, we assume a branch is of 4 bytes. The total memory requirement for a non-leaf node is

Consider a weighted directed graph. The current shortest distance from source S to node x is represented by d[x]. Let d[v]= 29, d[u]= 15, w[u,v]=12. What is the updated value of d[v] based on current information?

Consider double hashing of the form h(k, i) = (h (k) + ih (k)) mod m 1 2 h (k) = k mod m where 1 h (k) = 1 + (k mod n) 2 n = m − 1 m = 701 where and k = 123456 For , what is the difference between first and second probes in terms of slots?

A binary search tree is constructed by inserting the following numbers in order : 60,25,72,15,30,68,101,13,18,47,70,34 The number of nodes in the left subtree is

In a ternary tree, the number of internal nodes of degree 1,2 , and 3 is 4,3 , and 3 respectively. The number of leaf nodes in the ternary tree is

Consider a singly linked list. What is the worst case time complexity of the best-known algorithm to delete the node a, pointer to this node is q, from the list?

Consider the array A=<4, 1, 3, 2, 16, 9, 10, 14, 8, 7>. After building heap from the array A, the depth of the heap and the right child of max-heap are _________ and _________ respectively. (Root is at level 0).

A binary search tree in which every non-leaf node has non-empty left and right subtrees is called a strictly binary tree. Such a tree with 19 leaves :

A 5-ary tree is tree in which every internal node has exactly 5 children. The number of left nodes in such a tree with 8 internal nodes will be :

Consider a hash table of size seven, with starting index zero, and a hash function (7x+3) mod 4. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing ? Here “__” denotes an empty location in the table.