The runtime for traversing all the nodes of a binary search tree with n nodes and printing them in an order is (A) O(lg n) (B) O(n lg n) (C) O(n) (D) O(n2 )

The runtime for traversing all the nodes of a binary search tree with n nodes and printing them in an order is (A) O(lg n) (B) O(n lg n) (C) O(n) (D) O(n2 ) 

by

1 Answer

Answer :

(C) O(n) 
by

Related questions

Suppose that we have numbers between 1 and 1000 in a binary search tree and want to search for the number 364. Which of the following sequences could not be the sequence of nodes examined? (A) 925, 221, 912, 245, 899, 259, 363, 364 (B) 3, 400, 388, 220, 267, 383, 382, 279, 364 (C) 926, 203, 912, 241, 913, 246, 364 (D) 3, 253, 402, 399, 331, 345, 398, 364

Description : Suppose that we have numbers between 1 and 1000 in a binary search tree and want to search for the number 364. Which of the following sequences could not be the sequence of nodes examined? (A) 925, 221, 912, 245, 899, ... 926, 203, 912, 241, 913, 246, 364 (D) 3, 253, 402, 399, 331, 345, 398, 364 

Last Answer : (C) 926, 203, 912, 241, 913, 246, 364

The traveling salesman problem involves n cities with paths connecting the cities. The time taken for traversing through all the cities, without knowing in advance the length of a minimum tour, is ___________ a) O(n) b) O(n2) c) O(n!) d) O(n/2)

Description : The traveling salesman problem involves n cities with paths connecting the cities. The time taken for traversing through all the cities, without knowing in advance the length of a minimum tour, is ___________ a) O(n) b) O(n2) c) O(n!) d) O(n/2)

Last Answer : c) O(n!)

A full binary tree with n leaves contains (A) n nodes (B) log2 n nodes (C) 2n –1 nodes (D) 2n nodes

Description : A full binary tree with n leaves contains (A) n nodes (B) log2 n nodes (C) 2n –1 nodes (D) 2n nodes

Last Answer : (C) 2n –1 nodes 

Suppose you are given a binary tree with n nodes, such that each node has exactly either zero or two children. The maximum height of the tree will be (A) n/2 - 1 (B) n/2 + 1 (C) (n-1)/2 (D) (n+1)/2

Description : Suppose you are given a binary tree with n nodes, such that each node has exactly either zero or two children. The maximum height of the tree will be (A) n/2 - 1 (B) n/2 + 1 (C) (n-1)/2 (D) (n+1)/2

Last Answer : (C) (n-1)/2

Which of the following algorithms sort n integers, having the range 0 to (n2 -1), in ascending order in O(n) time ? (A) Selection sort (B) Bubble sort (C) Radix sort (D) Insertion sort

Description : Which of the following algorithms sort n integers, having the range 0 to (n2 -1), in ascending order in O(n) time ? (A) Selection sort (B) Bubble sort (C) Radix sort (D) Insertion sort

Last Answer : (C) Radix sort

Red-black trees are one of many Search tree schemes that are "balanced” in order to guarantee that basic dynamic-set operations take ............. time in the worst case. (1) O(1) (2) O(log n) (3) O(n) (4) O(n log n)

Description : Red-black trees are one of many Search tree schemes that are "balanced” in order to guarantee that basic dynamic-set operations take ............. time in the worst case. (1) O(1) (2) O(log n) (3) O(n) (4) O(n log n)

Last Answer : (2) O(log n) 

Consider the following statements: (a) Depth - first search is used to traverse a rooted tree. (b) Pre - order, Post-order and Inorder are used to list the vertices of an ordered rooted tree. (c) Huffman's algorithm is used to find an optimal binary tree with given weights. (d) Topological sorting provides a labelling such that the parents have larger labels than their children. Which of the above statements are true ? (A) (a) and (b) (B) (c) and (d) (C) (a) , (b) and (c) (D) (a), (b) , (c) and (d)

Description : Consider the following statements: (a) Depth - first search is used to traverse a rooted tree. (b) Pre - order, Post-order and Inorder are used to list the vertices of an ordered rooted tree. (c) Huffman's algorithm is used to find an optimal ... (d) (C) (a) , (b) and (c) (D) (a), (b) , (c) and (d)

Last Answer : (D) (a), (b) , (c) and (d)

The asymptotic upper bound solution of the recurrence relation given by T(n)= 2T(n/2)+n/log n is: (1) O(n2) (2) O(n log n) (3) O(n log log n) (4) O(log log n)

Description : The asymptotic upper bound solution of the recurrence relation given by T(n)= 2T(n/2)+n/log n is: (1) O(n2) (2) O(n log n) (3) O(n log log n) (4) O(log log n)

Last Answer : (3) O(n log log n) 

State True or False. i) Binary search is used for searching in a sorted array. ii) The time complexity of binary search is O(logn). A) True, False B) False, True C) False, False D) True, True

Description : State True or False. i) Binary search is used for searching in a sorted array. ii) The time complexity of binary search is O(logn). A) True, False B) False, True C) False, False D) True, True

Last Answer : D) True, True

Any decision tree that sorts n elements has height .............. (1) Ω(log n) (2) Ω(n) (3) Ω(n log n) (4) Ω(n2)

Description : Any decision tree that sorts n elements has height .............. (1) Ω(log n) (2) Ω(n) (3) Ω(n log n) (4) Ω(n2)

Last Answer : (3) Ω(n log n) 

The number of different binary trees with 6 nodes is ............. (A) 6 (B) 42 (C) 132 (D) 256

Description : The number of different binary trees with 6 nodes is ............. (A) 6 (B) 42 (C) 132 (D) 256

Last Answer : (C) 132

In ……………, search start at the beginning of the list and check every element in the list. A) Linear search B) Binary search C) Hash Search D) Binary Tree search

Description : In ……………, search start at the beginning of the list and check every element in the list. A) Linear search B) Binary search C) Hash Search D) Binary Tree search

Last Answer : A) Linear search

A binary search tree whose left subtree and right subtree differ in hight by at most 1 unit is called A) AVL tree B) Red-black tree C) Lemma tree D) None of the above

Description : A binary search tree whose left subtree and right subtree differ in hight by at most 1 unit is called A) AVL tree B) Red-black tree C) Lemma tree D) None of the above

Last Answer : A) AVL tree

Consider the following binary search tree: Image If we remove the root node, which of the node from the left subtree will be the new root? (A) 11 (B) 12 (C) 13 (D) 16

Description : Consider the following binary search tree: If we remove the root node, which of the node from the left subtree will be the new root? (A) 11 (B) 12 (C) 13 (D) 16

Last Answer : (D) 16

Which of the following statements is false? (A) Optimal binary search tree construction can be performed efficiently using dynamic programming. (B) Breadth-first search cannot be used to find connected components of a graph. (C) Given the prefix and postfix walks of a binary tree, the tree cannot be reconstructed uniquely. (D) Depth-first-search can be used to find the components of a graph. (1) A (2) B (3) C (4) D

Description : Which of the following statements is false? (A) Optimal binary search tree construction can be performed efficiently using dynamic programming. (B) Breadth-first search cannot be used to find connected components of a graph. (C) ... used to find the components of a graph. (1) A (2) B (3) C (4) D 

Last Answer : Answer: 2

When an array is passed as a parameter to a function which of the following statements is correct? (A) The function can change values in the original array. (B) The function cannot change values in the original array. (C) Results in compilation error. (D) Results in runtime error.

Description : When an array is passed as a parameter to a function which of the following statements is correct? (A) The function can change values in the original array. (B) The function cannot change values in the original array. (C) Results in compilation error. (D) Results in runtime error.

Last Answer : (A) The function can change values in the original array.

Which of the following differentiates between overloaded functions and overridden functions ? (A) Overloading is a dynamic or runtime binding and overridden is a static or compile time binding. (B) Overloading is a static or compile time binding and overriding is dynamic or runtime binding. (C) Redefining a function in a friend class is called overloading, while redefining a function in a derived class is called as overridden function. (D) Redefining a function in a derived class is called function overloading, while redefining a function in a friend class is called function overriding.

Description : Which of the following differentiates between overloaded functions and overridden functions ? (A) Overloading is a dynamic or runtime binding and overridden is a static or compile time binding. ... function overloading, while redefining a function in a friend class is called function overriding.

Last Answer : (B) Overloading is a static or compile time binding and overriding is dynamic or runtime binding.

A software design pattern used to enhance the functionality of an object at runtime is: (1) Adapter (2) Decorator (3) Delegation (4) Proxy

Description : A software design pattern used to enhance the functionality of an object at runtime is: (1) Adapter (2) Decorator (3) Delegation (4) Proxy

Last Answer : Answer: 2

A binary tree T has n leaf nodes. The number of nodes of degree 2 in T is

Description : A binary tree T has n leaf nodes. The number of nodes of degree 2 in T is  A) log2n B) n-1 C) n D) 2n

Last Answer : A binary tree T has n leaf nodes. The number of nodes of degree 2 in T is n-1

State true or false. i) An empty tree is also a binary tree. ii) In strictly binary tree, the outdegree of every node is either o or 2. A) True, False B) False, True C) True, True D) False, False

Description : State true or false. i) An empty tree is also a binary tree. ii) In strictly binary tree, the outdegree of every node is either o or 2. A) True, False B) False, True C) True, True D) False, False

Last Answer : C) True, True

................... comparisons are necessary in the worst case to find both the maximum and minimum of n numbers. (A) 2n-2 (B) n + floor(lg n) - 2 (C) floor(3n/2) - 2 (D) 2 lg n – 2

Description : ................... comparisons are necessary in the worst case to find both the maximum and minimum of n numbers. (A) 2n-2 (B) n + floor(lg n) - 2 (C) floor(3n/2) - 2 (D) 2 lg n – 2

Last Answer : (C) floor(3n/2) - 2

If h is chosen from a universal collection of hash functions and is used to hash n keys into a table of size m, where n ≤ m, the expected number of collisions involving a particular key K is (A) less than 1 (B) less than lg n (C) greater than 1 (D) greater than lg n

Description : If h is chosen from a universal collection of hash functions and is used to hash n keys into a table of size m, where n ≤ m, the expected number of collisions involving a particular key K is (A) less than 1 (B) less than lg n (C) greater than 1 (D) greater than lg n

Last Answer : (A) less than 1

Which of the following is asymptotically smaller? (A) lg(lg*n) (B) lg*(lg n) (C) lg(n!) (D) lg*(n!)

Description : Which of the following is asymptotically smaller? (A) lg(lg*n) (B) lg*(lg n) (C) lg(n!) (D) lg*(n!)

Last Answer : (A) lg(lg*n) 

Consider an implementation of unsorted single linked list. Suppose it has its representation with a head and a tail pointer (i.e. pointers to the first and last nodes of the linked list). Given the representation, which of the following operation cannot be implemented in O(1) time ? (A) Insertion at the front of the linked list. (B) Insertion at the end of the linked list. (C) Deletion of the front node of the linked list. (D) Deletion of the last node of the linked list.

Description : Consider an implementation of unsorted single linked list. Suppose it has its representation with a head and a tail pointer (i.e. pointers to the first and last nodes of the linked list). Given the ... the front node of the linked list. (D) Deletion of the last node of the linked list.

Last Answer : (D) Deletion of the last node of the linked list. 

Which of the following arguments are not valid? (a) “If Gora gets the job and works hard, then he will be promoted. If Gora gets promotion, then he will be happy. He will not be happy, therefore, either he will not get the job or he will not work hard”. (b) “Either Puneet is not guilty or Pankaj is telling the truth. Pankaj is not telling the truth, therefore, Puneet is not guilty”. (c) If n is a real number such that n>1, then n2>1. Suppose that n2>1, then n>1. Codes: (A) (a) and (c) (B) (b) and (c) (C) (a), (b) and (c) (D) (a) and (b)

Description : Which of the following arguments are not valid? (a) If Gora gets the job and works hard, then he will be promoted. If Gora gets promotion, then he will be happy. He will not be happy, therefore, either he will not get the job or he ... and (c) (B) (b) and (c) (C) (a), (b) and (c) (D) (a) and (b)

Last Answer : Answer: B Explanation: (a) P: Gora gets the job  Q: Gora works hard  R: Gora gets promotion  S: Gora will be happy The argument can bet written as  (P˄Q)→R  R→S  ¬S ... also be written as: ((P˅Q)˄¬P)→Q where P, and Q are propositions expressed in some formal system.

The inorder and preorder Traversal of binary Tree are dbeafcg and abdecfg respectively. The post-order Traversal is ............ (A) dbefacg (B) debfagc (C) dbefcga (D) debfgca

Description : The inorder and preorder Traversal of binary Tree are dbeafcg and abdecfg respectively. The post-order Traversal is ............ (A) dbefacg (B) debfagc (C) dbefcga (D) debfgca

Last Answer : (D) debfgca

Which one of the following is used to compute cyclomatic complexity ? (A) The number of regions – 1 (B) E – N + 1, where E is the number of flow graph edges and N is the number of flow graph nodes. (C) P – 1, where P is the number of predicate nodes in the flow graph G. (D) P + 1, where P is the number of predicate nodes in the flow graph G.

Description : Which one of the following is used to compute cyclomatic complexity ? (A) The number of regions - 1 (B) E - N + 1, where E is the number of flow graph edges and N is the number of flow graph nodes. (C) ... in the flow graph G. (D) P + 1, where P is the number of predicate nodes in the flow graph G.

Last Answer : (D) P + 1, where P is the number of predicate nodes in the flow graph G.

A …………… is an acyclic digraph, which has only one node with indegree 0, and other nodes have indegree 1. A) Directed tree B) Undirected tree C) Dis-joint tree D) Direction oriented tree

Description : A …………… is an acyclic digraph, which has only one node with indegree 0, and other nodes have indegree 1. A) Directed tree B) Undirected tree C) Dis-joint tree D) Direction oriented tree

Last Answer : A) Directed tree

Consider the following game tree in which root is a maximizing node and children are visited left to right. What nodes will be pruned by the alphabeta pruning? (A) I (B) HI (C) CHI (D) GHI

Description : Consider the following game tree in which root is a maximizing node and children are visited left to right. What nodes will be pruned by the alphabeta pruning?  (A) I (B) HI (C) CHI (D) GHI

Last Answer : (B) HI

The number of disk pages access in B-tree search, where h is height, n is the number of keys, and t is the minimum degree, is: (A) θ(logn h*t) (B) θ(logt n*h) (C) θ(logh n) (D) θ(logt n)

Description : The number of disk pages access in B-tree search, where h is height, n is the number of keys, and t is the minimum degree, is: (A) θ(logn h*t) (B) θ(logt n*h) (C) θ(logh n) (D) θ(logt n)

Last Answer : Answer: D

What is the difference between linear and binary search?

Description : What is the difference between linear and binary search?

Last Answer : A: Linear search does not require the array to be sorted, whereas, binary search requires that the array be sorted. Linear search checks for the search item in a linear fashion from the beginning cell till the end, ... tell what is control variable in your loop. So if your loop is for(int i = 1; i

When does Binary search fail?

Description : When does Binary search fail?

Last Answer : A: When the array is not sorted.

In general, the binary search method needs no more than ……………. comparisons. A) [log2n]-1 B) [logn]+1 C) [log2n] D) [log2n]+1

Description : In general, the binary search method needs no more than ……………. comparisons. A) [log2n]-1 B) [logn]+1 C) [log2n] D) [log2n]+1

Last Answer : D) [log2n]+1

Level order Traversal of a rooted Tree can be done by starting from root and performing: (A) Breadth First Search (B) Depth first search (C) Root search (D) Deep search

Description : Level order Traversal of a rooted Tree can be done by starting from root and performing: (A) Breadth First Search (B) Depth first search (C) Root search (D) Deep search

Last Answer : (A) Breadth First Search

The order of a leaf node in a B+ tree is the maximum number of children it can have. Suppose that block size is 1 kilobytes, the child pointer takes 7 bytes long and search field value takes 14 bytes long. The order of the leaf node is ............ (1) 16 (2) 63 (3) 64 (4) 65

Description : The order of a leaf node in a B+ tree is the maximum number of children it can have. Suppose that block size is 1 kilobytes, the child pointer takes 7 bytes long and search field value takes 14 bytes long. The order of the leaf node is ............ (1) 16 (2) 63 (3) 64 (4) 65

Last Answer : Answer: All

The number of distinct binary images which can be generated from a given binary image of right M × N are (A) M + N (B) M × N (C) 2M + N (D) 2MN

Description : The number of distinct binary images which can be generated from a given binary image of right M × N are (A) M + N (B) M × N (C) 2M + N (D) 2MN

Last Answer : (D) 2MN

To eliminate the inaccuracy problem in planning problem or partial order planning problem we can use ___________________ data structure/s. a) Stacks b) Queue c) BST (Binary Search Tree) d) Planning Graphs

Description : To eliminate the inaccuracy problem in planning problem or partial order planning problem we can use ___________________ data structure/s. a) Stacks b) Queue c) BST (Binary Search Tree) d) Planning Graphs

Last Answer : d) Planning Graphs

………………. Is a directed tree in which outdegree of each node is less than or equal to two. A) Unary tree B) Binary tree C) Dinary tree D) Both B and C

Description : ………………. Is a directed tree in which outdegree of each node is less than or equal to two. A) Unary tree B) Binary tree C) Dinary tree D) Both B and C

Last Answer : B) Binary tree

The property of binary tree is A) The first subset is called left subtree B) The second subtree is called right subtree C) The root cannot contain NULL D) The right subtree can be empty

Description : The property of binary tree is A) The first subset is called left subtree B) The second subtree is called right subtree C) The root cannot contain NULL D) The right subtree can be empty

Last Answer : D) The right subtree can be empty

Consider the formula in image processing RD = 1 - (1/CR) Where CR = n1/n2 CR is called as compression ratio n1 and n2 denotes the number of information carrying units in two datasets that represent the same information. In this situation RD is called as relative ................ of the first data set. (A) Data Compression (B) Data Redundancy (C) Data Relation (D) Data Representation

Description : Consider the formula in image processing RD = 1 - (1/CR) Where CR = n1/n2 CR is called as compression ratio n1 and n2 denotes the number of information carrying units in two datasets that represent ... . (A) Data Compression (B) Data Redundancy (C) Data Relation (D) Data Representation

Last Answer : (B) Data Redundancy

Which of the following is used to determine the specificity of requirements ? (A) n1/n2 (B) n2/n1 (C) n1+n2 (D) n1–n2 Where n1 is the number of requirements for which all reviewers have identical interpretations, n2 is number of requirements in a specification.

Description : Which of the following is used to determine the specificity of requirements ? (A) n1/n2 (B) n2/n1 (C) n1+n2 (D) n1–n2 Where n1 is the number of requirements for which all reviewers have identical interpretations, n2 is number of requirements in a specification.

Last Answer : (A) n1/n2 

A heuristic is a way of trying ___________ a) To discover something or an idea embedded in a program b) To search and measure how far a node in a search tree seems to be from a goal c) To compare two nodes in a search tree to see if one is better than another d) All of the mentioned

Description : A heuristic is a way of trying ___________ a) To discover something or an idea embedded in a program b) To search and measure how far a node in a search tree seems to be from a goal c) To compare two nodes in a search tree to see if one is better than another d) All of the mentioned

Last Answer : d) All of the mentioned

A heuristic is a way of trying __________ a) To discover something or an idea embedded in a program b) To search and measure how far a node in a search tree seems to be from a goal c) To compare two nodes in a search tree to see if one is better than the other is d) All of the mentioned

Description : A heuristic is a way of trying __________ a) To discover something or an idea embedded in a program b) To search and measure how far a node in a search tree seems to be from a goal c) To compare two nodes in a search tree to see if one is better than the other is d) All of the mentioned

Last Answer : d) All of the mentioned

A heuristic is a way of trying (A) To discover something or an idea embedded in a program (B) To search and measure how far a node in a search tree seems to be from a goal (C) To compare two nodes in a search tree to see if one is better than the other (D) Only (a), (b) and (c).

Description : A heuristic is a way of trying (A) To discover something or an idea embedded in a program (B) To search and measure how far a node in a search tree seems to be from a goal (C) To compare two nodes in a search tree to see if one is better than the other (D) Only (a), (b) and (c).

Last Answer : (D) Only (a), (b) and (c).

A graph is a collection of nodes, called ………. And line segments called arcs or ……….. that connect pair of nodes. A) vertices, edges B) edges, vertices C) vertices, paths D) graph node, edges

Description : A graph is a collection of nodes, called ………. And line segments called arcs or ……….. that connect pair of nodes. A) vertices, edges B) edges, vertices C) vertices, paths D) graph node, edges

Last Answer : A) vertices, edges

State true of false. i) A node is a parent if it has successor nodes. ii) A node is child node if out degree is one. A) True, True B) True, False C) False, True D) False, False

Description : State true of false. i) A node is a parent if it has successor nodes. ii) A node is child node if out degree is one. A) True, True B) True, False C) False, True D) False, False

Last Answer : B) True, False

State true or false. i) The degree of root node is always zero. ii) Nodes that are not root and not leaf are called as internal nodes. A) True, True B) True, False C) False, True D) False, False

Description : State true or false. i) The degree of root node is always zero. ii) Nodes that are not root and not leaf are called as internal nodes. A) True, True B) True, False C) False, True D) False, False

Last Answer : C) False, True

Given a flow graph with 10 nodes, 13 edges and one connected components, the number of regions and the number of predicate (decision) nodes in the flow graph will be (A) 4, 5 (B) 5, 4 (C) 3, 1 (D) 13, 8

Description : Given a flow graph with 10 nodes, 13 edges and one connected components, the number of regions and the number of predicate (decision) nodes in the flow graph will be (A) 4, 5 (B) 5, 4 (C) 3, 1 (D) 13, 8

Last Answer : (B) 5, 4

In Unix operating system, special files are used to : (A) buffer data received in its input from where a process reads (B) provide a mechanism to map physical device to file names (C) store list of file names plus pointers associated with i-nodes (D) store information entered by a user application program or utility program

Description : In Unix operating system, special files are used to : (A) buffer data received in its input from where a process reads (B) provide a mechanism to map physical device to file names (C ... pointers associated with i-nodes (D) store information entered by a user application program or utility program

Last Answer : (B) provide a mechanism to map physical device to file names 

A unix file system has 1-KB blocks and 4-byte disk addresses. What is the maximum file size if i-nodes contain 10 direct entries and one single, double and triple indirect entry each? (A) 32 GB (B) 64 GB (C) 16 GB (D) 1 GB

Description : A unix file system has 1-KB blocks and 4-byte disk addresses. What is the maximum file size if i-nodes contain 10 direct entries and one single, double and triple indirect entry each? (A) 32 GB (B) 64 GB (C) 16 GB (D) 1 GB

Last Answer : (C) 16 GB