Q::21. What item is at the root after the following sequence of insertions into an empty splay tree:
1, 11, 3, 10, 8, 4, 6, 5, 7, 9, 2 ?
(A) 1 (B) 2
(C) 4 (D) 8
Answer: B
Explanation:
A splay tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O(log n) amortized time(amortized analysis is a method for analyzing a given algorithm's time complexity). For many sequences of non-random operations, splay trees perform better than other search trees, even when the specific pattern of the sequence is unknown. The splay tree was invented by Daniel Dominic Sleator and Robert Endre Tarjan in 1985.
All normal operations on a binary search tree are combined with one basic operation, called splaying. Splaying the tree for a certain element rearranges the tree so that the element is placed at the root of the tree. One way to do this is to first perform a standard binary tree search for the element in question, and then use tree rotations in a specific fashion to bring the element to the top. Alternatively, a top-down algorithm can combine the search and the tree reorganization into a single phase.
For more details visit
Q::22. Suppose we are implementing quadratic probing with a Hash function, Hash (y)=X mode 100. If an element with key 4594 is inserted and the first three locations attempted are already occupied, then the next cell that will be tried is:
(A) 2 (B) 3
(C) 9 (D) 97
Answer: B
Explanation:
h(4594) = 94 i.e. our first attempt
94 + 1^2 = 95 second attempt
94 + 2^2 = 98 third attempt
94 + 3^2 = 103 % 100 = 3 i.e. next cell to be tried will be 3.
Q::23. Weighted graph:
(A) Is a bi-directional graph
(B) Is directed graph
(C) Is graph in which number associated with arc
(D) Eliminates table method
Answer: C
Explanation:
A weight is a numerical value, assigned as a label to a vertex or edge of a graph. A weighted graph is a graph whose vertices or edges have been assigned weights; more specifically, a vertex-weighted graph has weights on its vertices and an edge-weighted graph has weights on its edges. The weight of a subgraph is the sum of the weights of the vertices or edges within that subgraph.
Q::24. What operation is supported in constant time by the doubly linked list, but not by the singly linked list?
(A) Advance (B) Backup
(C) First (D) Retrieve
Answer: B
Q::25. How much extra space is used by heap sort?
(A) O(1) (B) O(Log n)
(C) O(n) (D) O(n2)
Answer: A
Explanation:
| A run of the heapsort algorithm sorting an array of randomly permuted values. In the first stage of the algorithm the array elements are reordered to satisfy the heap property. Before the actual sorting takes place, the heap tree structure is shown briefly for illustration. | |
| Class | Sorting algorithm |
|---|---|
| Data structure | Array |
| Worst case performance |  |
| Best case performance |  [1] |
| Average case performance | |
| Worst case space complexity |  auxiliary |
ugc net computer science question papers,ugc net computer science december 2014 question papers,
ugc net computer science june 2014 question papers,
ugc net computer science december 2014 question papers,
ugc net computer science june 2013 question papers,
ugc net computer science december 2013 question papers,
ugc net computer science june 2012 question papers,
ugc net computer science december 2012 question papers,
ugc net computer science june 2011 question papers,
ugc net computer science december 2011 question papers,
ugc net computer science june 2010 question papers,
ugc net computer science december 2010 question papers,
ugc net computer science june 2009 question papers,
ugc net computer science december 2009 question papers,
ugc net computer science june 2008 question papers,
ugc net computer science december 2008 question papers,
december 2004 ugc net computer science paper,ugc net computer science december 2004 solution, cbse net all solved papers, cbse net
No comments:
Post a Comment