For a B-tree of height h and degree t, the total CPU time used to insert a node is (A) O(h log t) (B) O(t log h) (C) O(t2h) (D) O(th)

For a B-tree of height h and degree t, the total CPU time used to insert a node is (A) O(h log t) (B) O(t log h) (C) O(t2h) (D) O(th)
by

1 Answer

Answer :

(D) O(th)
by

Related questions

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

For any B-tree of minimum degree t ≥2, every node other than the root must have atleast ............... keys and every node can have at most .............. keys. (A) t-1, 2t+1 (B) t+1, 2t+1 (C) t-1, 2t-1 (D) t+1, 2t-1

Description : For any B-tree of minimum degree t ≥2, every node other than the root must have atleast ............... keys and every node can have at most .............. keys. (A) t-1, 2t+1 (B) t+1, 2t+1 (C) t-1, 2t-1 (D) t+1, 2t-1

Last Answer : (C) t-1, 2t-1 

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

The solution of recurrence relation, T(n) = 2T(floor (√n)) + logn is (A) O(n log log logn) (B) O(n log logn) (C) O(log logn) (D) O(logn log logn)

Description : The solution of recurrence relation, T(n) = 2T(floor (√n)) + logn is (A) O(n log log logn) (B) O(n log logn) (C) O(log logn) (D) O(logn log logn)

Last Answer : (D) O(logn log logn)

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) 

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) 

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

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) 

If h* represents an estimate of the cost of getting from the current node N to the goal node and h represents actual cost of getting from current node to the goal node, then A* algorithm gives an optimal solution if (A) h* us equal to h (B) h* overestimates h (C) h* underestimates h (D) none of these

Description : If h* represents an estimate of the cost of getting from the current node N to the goal node and h represents actual cost of getting from current node to the goal node, then A* algorithm gives an optimal solution ... h* us equal to h (B) h* overestimates h (C) h* underestimates h (D) none of these

Last Answer : (C) h* underestimates h

Consider f(N) = g(N) + h(N) Where function g is a measure of the cost of getting from the start node to the current node N and h is an estimate of additional cost of getting from the current node N to the goal node. Then f(N) = h(N) is used in which one of the following algorithms ? (A) A* algorithm (B) AO* algorithm (C) Greedy best first search algorithm (D) Iterative A* algorithm

Description : Consider f(N) = g(N) + h(N) Where function g is a measure of the cost of getting from the start node to the current node N and h is an estimate of additional cost of getting from the current ... ? (A) A* algorithm (B) AO* algorithm (C) Greedy best first search algorithm (D) Iterative A* algorithm

Last Answer : (C) Greedy best first search algorithm

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

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. 

Big - O estimate for f(x) = (x + 1) log(x2 + 1) + 3x2 is given as (A) O(xlogx) (B) O(x2) (C) O(x3) (D) O(x2logx)

Description : Big - O estimate for f(x) = (x + 1) log(x2 + 1) + 3x2 is given as (A) O(xlogx) (B) O(x2) (C) O(x3) (D) O(x2logx)

Last Answer : (B) O(x2)

………………. 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

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

What is the name of the network topology in which there are bi-directional links between each possible node? A) Ring B) Star C) Tree D) Mesh

Description : What is the name of the network topology in which there are bi-directional links between each possible node? A) Ring B) Star C) Tree D) Mesh

Last Answer : D) Mesh

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

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

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 virtual address generated by a CPU is 32 bits. The Translation Lookaside Buffer (TLB) can hold total 64 page table entries and a 4-way set associative (i.e. with 4- cache lines in the set). The page size is 4 KB. The minimum size of TLB tag is (A) 12 bits (B) 15 bits (C) 16 bits (D) 20 bits

Description : The virtual address generated by a CPU is 32 bits. The Translation Lookaside Buffer (TLB) can hold total 64 page table entries and a 4-way set associative (i.e. with 4- cache lines in the set). The page size is 4 KB. The minimum size of TLB tag is (A) 12 bits (B) 15 bits (C) 16 bits (D) 20 bits

Last Answer : (C) 16 bits Explanation: VirtualAddress = 32 bits PageSize = 4KB = 12 bits therefore : VPNTag = 20 bits, OffsetTag = 12 bits TLBEntryLength = VPNTag = 20 bits TotalTLBEntries = 64, 4-way implies ... therefore : TLBIndex = 4 bits TLBTag = TLBEntryLength - TLBIndex = 20 - 4 = 16 bits

The height of h(A) of a fuzzy set A is defined as h(A) = sup A(x) xϵA Then the fuzzy set A is called normal when (A) h(A) = 0 (B) h(A) < 0 (C) h(A) = 1 (D) h(A) < 1

Description : The height of h(A) of a fuzzy set A is defined as h(A) = sup A(x)  xϵA Then the fuzzy set A is called normal when (A) h(A) = 0 (B) h(A) < 0 (C) h(A) = 1 (D) h(A) < 1

Last Answer : (C) h(A) = 1 

Suppose list Example is [‘h’,’e’,’l’,’l’,’o’], what is len(list Example)? a) 5 b) 4 c) None d) Error

Description : Suppose list Example is [‘h’,’e’,’l’,’l’,’o’], what is len(list Example)? a) 5 b) 4 c) None d) Error

Last Answer : a) 5

What is the output when we execute list(“hello”)? a) [‘h’, ‘e’, ‘l’, ‘l’, ‘o’]. b) [‘hello’]. c) [‘llo’]. d) [‘olleh’].

Description : What is the output when we execute list(“hello”)? a) [‘h’, ‘e’, ‘l’, ‘l’, ‘o’]. b) [‘hello’]. c) [‘llo’]. d) [‘olleh’].

Last Answer : a) [‘h’, ‘e’, ‘l’, ‘l’, ‘o’].

What is the output when following code is executed ? >>> str1 = 'hello' >>> str2 = ',' >>> str3 = 'world' >>> str1[-1:] a) olleh b) hello c) h d) o

Description : What is the output when following code is executed ? >>> str1 = 'hello' >>> str2 = ',' >>> str3 = 'world' >>> str1[-1:] a) olleh b) hello c) h d) o

Last Answer : b) hello

Which of the syntax is correct for insert statement? i) insert into <table_name> values <list of values> ii) insert into <table_name> (column list) values <list of values> A) i-only B) ii-only C) Both of them D) None of them

Description : Which of the syntax is correct for insert statement? i) insert into values ii) insert into (column list) values A) i-only B) ii-only C) Both of them D) None of them

Last Answer : C) Both of them

To insert 5 to the third position in list1, we use which command ? a) list1.insert(3, 5) b) list1.insert(2, 5) c) list1.add(3, 5) d) list1.append(3, 5)

Description : To insert 5 to the third position in list1, we use which command ? a) list1.insert(3, 5) b) list1.insert(2, 5) c) list1.add(3, 5) d) list1.append(3, 5)

Last Answer : a) list1.insert(3, 5)

A scheduling Algorithm assigns priority proportional to the waiting time of a process. Every process starts with priority zero (lowest priority). The scheduler re-evaluates the process priority for every 'T' time units and decides next process to be scheduled. If the process have no I/O operations and all arrive at time zero, then the scheduler implements .............. criteria. (A) Priority scheduling (B) Round Robin Scheduling (C) Shortest Job First (D) FCFS

Description : A scheduling Algorithm assigns priority proportional to the waiting time of a process. Every process starts with priority zero (lowest priority). The scheduler re-evaluates the process priority for every 'T' time ... (A) Priority scheduling (B) Round Robin Scheduling (C) Shortest Job First (D) FCFS

Last Answer : (B) Round Robin Scheduling

After striking the floor, a rubber ball rebounds (7/8)th of height from which it has fallen. Find the total distance that it travels before coming to rest, if it is gently dropped from a height of 420 meters. a) 2940 b) 6300 c) 1080 d) 3360

Description : After striking the floor, a rubber ball rebounds (7/8)th of height from which it has fallen. Find the total distance that it travels before coming to rest, if it is gently dropped from a height of 420 meters. a) 2940 b) 6300 c) 1080 d) 3360

Last Answer : b) 6300

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

Which of the following statement is true? i) Using singly linked lists and circular list, it is not possible to traverse the list backwards. ii) To find the predecessor, it is required to traverse the list from the first node in case of singly linked list. A) i-only B) ii-only C) Both i and ii D) None of both

Description : Which of the following statement is true? i) Using singly linked lists and circular list, it is not possible to traverse the list backwards. ii) To find the predecessor, it is required to traverse the list from the first ... linked list. A) i-only B) ii-only C) Both i and ii D) None of both

Last Answer : C) Both i and ii

Any node is the path from the root to the node is called A) Successor node B) Ancestor node C) Internal node D) None of the above

Description : Any node is the path from the root to the node is called A) Successor node B) Ancestor node C) Internal node D) None of the above

Last Answer : B) Ancestor node

Which is the main function of transport layer? A) Node to node delivery B) End to end delivery C) Synchronization d) Updating and maintaining routing tables

Description : Which is the main function of transport layer? A) Node to node delivery B) End to end delivery C) Synchronization d) Updating and maintaining routing tables

Last Answer : B) End to end delivery

................. maintains the list of free disk blocks in the Unix file system. (A) I-node (B) Boot block (C) Super block (D) File allocation table

Description : ................. maintains the list of free disk blocks in the Unix file system. (A) I-node (B) Boot block (C) Super block (D) File allocation table

Last Answer : (C) Super block 

Which of the following statements are true with reference to the way of describing XML data ? (a) XML uses DTD to describe the data (b) XML uses XSL to describe the data (c) XML uses a description node to describe the data Codes : (A) (a) only (B) (b) only (C) (a) and (b) (D) (a) and (c)

Description : Which of the following statements are true with reference to the way of describing XML data ? (a) XML uses DTD to describe the data (b) XML uses XSL to describe the data (c) XML uses a description node to describe the data Codes : (A) (a) only (B) (b) only (C) (a) and (b) (D) (a) and (c)

Last Answer : Answer: D

Which of the following information about the UNIX file system is not correct? (A) Super block contains the number of i-nodes, the number of disk blocks, and the start of the list of free disk blocks. (B) An i-node contains accounting information as well as enough information to locate all the disk blocks that holds the file’s data. (C) Each i-node is 256-bytes long. (D) All the files and directories are stored in data blocks.

Description : Which of the following information about the UNIX file system is not correct? (A) Super block contains the number of i-nodes, the number of disk blocks, and the start of the list of free disk blocks. (B ... Each i-node is 256-bytes long. (D) All the files and directories are stored in data blocks. 

Last Answer : (C) Each i-node is 256-bytes long.

A node X on a 10 Mbps network is regulated by a token bucket. The token bucket is filled at a rate of 2 Mbps. Token bucket is initially filled with 16 megabits. The maximum duration taken by X to transmit at full rate of 10 Mbps is ............ secs. (1) 1 (2) 2 (3) 3 (4) 4

Description : A node X on a 10 Mbps network is regulated by a token bucket. The token bucket is filled at a rate of 2 Mbps. Token bucket is initially filled with 16 megabits. The maximum duration taken by X to transmit at full rate of 10 Mbps is ............ secs. (1) 1 (2) 2 (3) 3 (4) 4

Last Answer : (2) 2 

If a, b, c be the p^th, q^th, r^th terms of a GP, then the value of (q – r) log a + (r – p) -Maths 9th

Description : If a, b, c be the p^th, q^th, r^th terms of a GP, then the value of (q – r) log a + (r – p) -Maths 9th

Last Answer : (a) 0Let h be the first term and k be the common ratio of a GP, then a = hkp - 1, b = hkq - 1, c = hkr - 1∴ (q - r) log a + (r - p) log b + (p - q) log c = log [hkp -1]q - r + log [hkq -1]r - p + log[hkr -1]p - ... r + r - p + p - q) (kp - 1)q - r (kq -1)r - p (kr -1)p - q = log(ho ko) = log 1 = 0.

Consider a uniprocessor system where new processes arrive at an average of five processes per minute and each process needs an average of 6 seconds of service time. What will be the CPU utilization ? (A) 80 % (B) 50 % (C) 60 % (D) 30 %

Description : Consider a uniprocessor system where new processes arrive at an average of five processes per minute and each process needs an average of 6 seconds of service time. What will be the CPU utilization ? (A) 80 % (B) 50 % (C) 60 % (D) 30 %

Last Answer : (B) 50 %

Assume that a program will experience 200 failures in infinite time. It has now experienced 100 failures. The initial failure intensity was 20 failures/CPU hr. Then the current failure intensity will be (A) 5 failures/CPU hr (B) 10 failures/CPU hr. (C) 20 failures/CPU hr. (D) 40 failures/CPU hr.

Description : Assume that a program will experience 200 failures in infinite time. It has now experienced 100 failures. The initial failure intensity was 20 failures/CPU hr. Then the current failure intensity will be (A) 5 failures/CPU hr (B) 10 failures/CPU hr. (C) 20 failures/CPU hr. (D) 40 failures/CPU hr.

Last Answer : (B) 10 failures/CPU hr.

A CPU handles interrupt by executing interrupt service subroutine................. (A) by checking interrupt register after execution of each instruction (B) by checking interrupt register at the end of the fetch cycle (C) whenever an interrupt is registered (D) by checking interrupt register at regular time interval

Description : A CPU handles interrupt by executing interrupt service subroutine................. (A) by checking interrupt register after execution of each instruction (B) by checking interrupt register ... cycle (C) whenever an interrupt is registered (D) by checking interrupt register at regular time interval

Last Answer : (A) by checking interrupt register after execution of each instruction

Consider three CPU intensive processes P1, P2, P3 which require 20, 10 and 30 units of time, arrive at times 1, 3 and 7 respectively. Suppose operating system is implementing Shortest Remaining Time first (preemptive scheduling) algorithm, then .............. context switches are required (suppose context switch at the beginning of Ready queue and at the end of Ready queue are not counted). (A) 3 (B) 2 (C) 4 (D) 5

Description : Consider three CPU intensive processes P1, P2, P3 which require 20, 10 and 30 units of time, arrive at times 1, 3 and 7 respectively. Suppose operating system is implementing Shortest Remaining Time first (preemptive scheduling) ... end of Ready queue are not counted). (A) 3 (B) 2 (C) 4 (D) 5

Last Answer : (A) 3

The Servlet Response interface enables a servlet to formulate a response for a client using the method ............... (A) void log(Exception e, String s) (B) void destroy() (C) int getServerPort() (D) void setContextType(String Type)

Description : The Servlet Response interface enables a servlet to formulate a response for a client using the method ............... (A) void log(Exception e, String s) (B) void destroy() (C) int getServerPort() (D) void setContextType(String Type)

Last Answer : (D) void setContextType(String Type)

A certain tree has two vertices of degree 4, one vertex of degree 3 and one vertex of degree 2. If the other vertices have degree 1, how many vertices are there in the graph? (A) 5 (B) n – 3 (C) 20 (D) 11

Description : A certain tree has two vertices of degree 4, one vertex of degree 3 and one vertex of degree 2. If the other vertices have degree 1, how many vertices are there in the graph? (A) 5 (B) n – 3 (C) 20 (D) 11

Last Answer : (D) 11

A thread is usually defined as a light weight process because an Operating System (OS) maintains smaller data structure for a thread than for a process. In relation to this, which of the following statement is correct? (A) OS maintains only scheduling and accounting information for each thread. (B) OS maintains only CPU registers for each thread. (C) OS does not maintain a separate stack for each thread. (D) OS does not maintain virtual memory state for each thread.

Description : A thread is usually defined as a light weight process because an Operating System (OS) maintains smaller data structure for a thread than for a process. In relation to this, which of the following ... separate stack for each thread. (D) OS does not maintain virtual memory state for each thread.

Last Answer : (B) OS maintains only CPU registers for each thread.

Consider the following justifications for commonly using the two-level CPU scheduling : I. It is used when memory is too small to hold all the ready processes. II. Because its performance is same as that of the FIFO. III. Because it facilitates putting some set of processes into memory and a choice is made from that. IV. Because it does not allow to adjust the set of in-core processes. Which of the following is true ? (A) I, III and IV (B) I and II (C) III and IV (D) I and III

Description : Consider the following justifications for commonly using the two-level CPU scheduling : I. It is used when memory is too small to hold all the ready processes. II. Because its performance is same as that of the FIFO. III. Because it ... ? (A) I, III and IV (B) I and II (C) III and IV (D) I and III

Last Answer : (D) I and III

A DMA controller transfers 32-bit words to memory using cycle Stealing. The words are assembled from a device that transmits characters at a rate of 4800 characters per second. The CPU is fetching and executing instructions at an average rate of one million instructions per second. By how much will the CPU be slowed down because of the DMA transfer? (A) 0.06% (B) 0.12% (C) 1.2% (D) 2.5%

Description : A DMA controller transfers 32-bit words to memory using cycle Stealing. The words are assembled from a device that transmits characters at a rate of 4800 characters per second. The CPU is fetching and executing instructions at an average ... of the DMA transfer? (A) 0.06% (B) 0.12% (C) 1.2% (D) 2.5%

Last Answer : Answer: B

A virtual memory has a page size of 1K words. There are eight pages and four blocks. The associative memory page table contains the following entries: Image Which of the following list of virtual addresses (in decimal) will not cause any page fault if referenced by the CPU? (A) 1024, 3072, 4096, 6144 (B) 1234, 4012, 5000, 6200 (C) 1020, 3012, 6120, 8100 (D) 2021, 4050, 5112, 7100

Description : A virtual memory has a page size of 1K words. There are eight pages and four blocks. The associative memory page table contains the following entries:  Which of the following list of virtual addresses (in ... 1234, 4012, 5000, 6200 (C) 1020, 3012, 6120, 8100 (D) 2021, 4050, 5112, 7100

Last Answer : Answer: C Explanation: The pages which are not in main memory are: 1020 will not cause page fault (1024-2047) 3012 will not cause page fault (3072-4095) 6120 will not cause page fault (4096-5119) 8100 will not cause page fault (6144-7167)

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 )

Description : 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 ) 

Last Answer : (C) O(n)