Algorithm Solved MCQs- Part 2

A binary tree with 27 nodes has _______ null branches. 54 27 26 None of the above       _____________________________________________________________________________________

The complexity of multiplying two matrices of order m*n and n*p is mnp mnq mpq npq       _____________________________________________________________________________________

A graph is planar if and only if it does not contain sub graphs homeomorphic   to K5 and K3,3 it does not contain sub graphs isomorphic   to K5 or K3,3 it does not contain sub graphs isomorphic   to K5 and K3,3 it does not contain sub graphs homeomorphic   to K5 or  K3,3       _____________________________________________________________________________________

One can convert a binary tree into its mirror image by traversing it in  Inorder Preorder Postorder Any order       _____________________________________________________________________________________

Time complexities of three algorithms are given. Which should execute the slowest for large values of N? ( 1 2 ) O N O(N) O(log N) None of these       _____________________________________________________________________________________

Which of the following sorting procedure is the slowest?  Quick sort Heap sort Shell sort Bubble sort       _____________________________________________________________________________________

The space factor when determining the efficiency of algorithm is measured by  Counting the maximum memory needed by the algorithm Counting the minimum memory needed by the algorithm Counting the average memory needed by the algorithm Counting the maximum disk space needed by the algorithm       _____________________________________________________________________________________

A hash function f defined as f(key) = key mod 7, with linear probing used to resolve collisions. Insert the keys 37, 38, 72, 48, 98 and 11 into the table indexed from 0 to 6. What will be the location of 11 ? 3 4 5 6       _____________________________________________________________________________________

In ______, the difference between the height of the left sub tree and height of the right tree, for each node, is almost one  Binary search tree AVL tree Complete tree Threaded binary tree       _____________________________________________________________________________________

A BST is traversed in the following order recursively: Right, root, left.The output sequence will be in  Ascending order Descending order Bitomic sequence No specific order       _____________________________________________________________________________________

A sorting technique which uses the binary tree concept such that label of any node is larger than all the labels in the subtrees, is called  Selection sort Insertion sort Heap sort Quick sort       _____________________________________________________________________________________

In order to get the information stored in a Binary Search Tree in the descending order, one should traverse it in which of the following order?  Left, root, right Root, left, right Right, root, left Right, left, root       _____________________________________________________________________________________

If x is a string then xR denotes the reversal of x. If x and y are strings, then (xy)R = xyR yxR yRx yRxR       _____________________________________________________________________________________

When representing any algebraic expression E which uses only binary operations in a 2-tree,  The variable in E will appear as external nodes and operations in internal nodes The operations in E will appear as external nodes and variables in internal nodes The variables and operations in E will appear only in internal nodes the variables and operations in E will appear only in external nodes       _____________________________________________________________________________________

A sort which uses binary tree concept such that any number is larger than all the numbers in the subtree below it,is called  Selection sort Insertion sort Heap sort Quick sort       _____________________________________________________________________________________

Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of n nodes? O(1) O(log n) O(n) O(n log n)       _____________________________________________________________________________________

In a Heap tree  Values in a node is greater than every value in left sub tree and smaller than right sub tree Values in a node is greater than every value in children of it Both of above conditions applies None of above conditions applies       _____________________________________________________________________________________

In worst case Quick Sort has order O (n log n) O (n2/2) O (log n) O (n2/4)       _____________________________________________________________________________________

Which of the following algorithms solves the all pair shortest path problem?  Dijkstra algorithm Floyd algorithm Prim algorithm Warshall algorithm       _____________________________________________________________________________________

Tree Is a bipartite graph With n node contains n-1 edges Is a connected graph All of these       _____________________________________________________________________________________

A graph in which all nodes are of equal degrees is known as Complete graph Regular graph Non regular graph Multi graph       _____________________________________________________________________________________

What is the postfix form of the following prefix *+ab–cd ab+cd–* abc+*– ab+*cd– ab+*cd–       _____________________________________________________________________________________

Which of the following sorting method is stable? Straight insertion sort Binary insertion sort Shell sort Heap sort       _____________________________________________________________________________________

FIRST(1st) TRUE statement in following is  Linear linked list are more space efficient(i.e. require less memory) for storing a list of 1000 names than having a plain flat array Linear linked lists are less time efficient(i.e. require more time) for maintaining (i.e updating) a growing list of over 1000 names (sorted in alphabetic order) than having a plain flat array Array are more versatile(i.e dynamically reconstructable) than linked lists A data structure with two links offers more geometrical configuration than data structure with one link       _____________________________________________________________________________________

A B C D       _____________________________________________________________________________________

A B C D       _____________________________________________________________________________________

The complexity of searching an element from a set of n elements using Binary search algorithm is O(n) O(log n) O(n2) O(n log n)       _____________________________________________________________________________________

Assuming P ? NP, which of the following is TRUE? NP-complete = NP NP-completenP=theta NP-hard = NP P = NP-complete       _____________________________________________________________________________________

Using the standard algorithm ,what is the time required to determine that a number n is prime? Constant time Quadratic time Logarithmic time Linear time       _____________________________________________________________________________________

The data structure required for breadth first traversal on a graph is Queue Stack Array Tree       _____________________________________________________________________________________

A binary tree can easily be converted into q 2-tree  by replacing each empty sub tree by a new internal node by inserting an internal nodes for non-empty node by inserting an external nodes for non-empty node by replacing each empty sub tree by a new external node       _____________________________________________________________________________________

The number of vertices of odd degree in a graph is  Always zero Either even or odd Always odd Always even       _____________________________________________________________________________________

The minimum number of multiplications and additions required to evaluate the polynomial P = 4x3+3x2-15x+45 is 6 & 3 4 & 2 3 & 3 8 & 3       _____________________________________________________________________________________

Number of ordered trees with 3 nodes A,B,C is 16 12 13 14       _____________________________________________________________________________________

A program that checks spelling works in the following way. A hash table has been defined in which each entry is a Boolean variable initialized to false. A hash function has been applied to each word in the dictionary, and the appropriate entry in the hash table has been set to true. To check the spelling in a document, the hash function is applied to every word in the document, and the appropriate entry in the table is examined. Which of the following is (are) correct? I. true means the word was int the dictionary. II. false means the word was not in the dictionary. III. Hash table size should increase with document size. I only II only I and II only II and III only       _____________________________________________________________________________________

Id one uses straight two way merge sort algorithm to sort the following elements in ascending order 20,47,15,8,9,4,40,30,12,17 then order of these elements after the second pass of the algorithm is 8,9,15,20,47,4,12,17,30,40 8,15,20,47,4,9,30,40,12,17 15,20,47,4,8,9,12,30,40,17 4,8,9,15,20,47,12,17,30,40       _____________________________________________________________________________________

The upper bound of computing time of m coloring decision problem is O(nm) O(nm) O(nmn) O(nmmn)       _____________________________________________________________________________________

Leaves of which of the following trees are at the same level ? Binary tree B-tree AVL-tree Expression tree       _____________________________________________________________________________________

Quick sort is also known as Merge sort Heap sort Bubble sort None of these       _____________________________________________________________________________________

If every node u in G is adjacent to every other node v in G, A graph is said to be  Isolated Complete Finite Strongly Connected       _____________________________________________________________________________________

The pre order and post order traversal of a Binary Tree generates the same output. The tree can have maximum Three nodes Two nodes One node Any number of nodes       _____________________________________________________________________________________

A B C D       _____________________________________________________________________________________

Which of the following statements are TRUE? (1) The problem of determining whether there exists a cycle in an undirected graph is in P. (2) The problem of determining whether there exists a cycle in an undirected graph is in NP. (3) If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A. 1,2 and 3 1 and 2 only 2 and 3 only 1 and 3 only       _____________________________________________________________________________________

A simple graph in which there exists an edge between every pair of vertices is called Complete graph Euler graph Planar graph Regular graph       _____________________________________________________________________________________

Two isomorphic graphs must have Equal number of vertices Same number of edges Same number of vertices All of the above       _____________________________________________________________________________________

The Worst case occur in linear search algorithm when  Item is somewhere in the middle of the array Item is not in the array at all Item is the last element in the array Item is the last element in the array or is not there at all       _____________________________________________________________________________________

The most common hash functions use the__________to compute hash address.  Division method Union method Subtraction method None of the above       _____________________________________________________________________________________

If h is any hashing function and is used to hash n keys in to a table of size m, where n<=m, the expected number of collisions involving a particular key x is less than 1 less than n less than m less than n/2       _____________________________________________________________________________________

If each node in a tree has value greater than every value in its left subtree and has value less than every in the its right subtree ,the tree is called Complete tree Full binary tree Binary search tree Threaded tree       _____________________________________________________________________________________

Every cut set of a connected euler graph No such characterization Atleast three edges An even number of edges An odd number of edges