Register

GATE CSE 2002 | Question: 1.5

• retagged by
14,786 views
25 votes
25 votes

In the worst case, the number of comparisons needed to search a single linked list of length $n$ for a given element is

  1. $\log n$
  2. $\frac{n}{2}$
  3. $\log_2 {n} - 1$
  4. $n$
• retagged by
User Avatar

6 Answers

0 votes
0 votes
In the worst case scenario,either we will find the element in the last node of otherwise we will not find the node after traversal to whole linked list .so to find a node in the worst case we have to traverse all the linked list till the last node ..that's why no. Of comparisons will also be 'n' .and we don't do binary search in Linked list so log n  base 2 can never be the our answer.
User Avatar
Page:
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

20 votes
20 votes
1 answer
1
Kathleen asked Sep 15, 2014
2,556 views
GATE CSE 2002 | Question: 6
Draw all binary trees having exactly three nodes labeled $A, B$ and $C$ on which preorder traversal gives the sequence $C, B, A$.
Draw all binary trees having exactly three nodes labeled $A, B$ and $C$ on which preorder traversal gives the sequence $C, B, A$.
User Avatar
39 votes
39 votes
8 answers
2
Kathleen asked Sep 15, 2014
18,679 views
GATE CSE 2002 | Question: 1.25, ISRO2008-30, ISRO2016-6
The maximum number of edges in a $n$-node undirected graph without self loops is $n^2$ $\frac{n(n-1)}{2}$ $n-1$ $\frac{(n+1)(n)}{2}$
The maximum number of edges in a $n$-node undirected graph without self loops is$n^2$$\frac{n(n-1)}{2}$$n-1$$\frac{(n+1)(n)}{2}$
User Avatar
32 votes
32 votes
5 answers
3
Kathleen asked Sep 15, 2014
13,791 views
GATE CSE 2002 | Question: 1.24
In the absolute addressing mode: the operand is inside the instruction the address of the operand in inside the instruction the register containing the address of the operand is specified inside the instruction the location of the operand is implicit
In the absolute addressing mode:the operand is inside the instructionthe address of the operand in inside the instructionthe register containing the address of the operan...
User Avatar
21 votes
21 votes
1 answer
4
Kathleen asked Sep 15, 2014
8,232 views
GATE CSE 2002 | Question: 1.23
The optimal page replacement algorithm will select the page that Has not been used for the longest time in the past Will not be used for the longest time in the future Has been used least number of times Has been used most number of times
The optimal page replacement algorithm will select the page thatHas not been used for the longest time in the pastWill not be used for the longest time in the futureHas b...
User Avatar
Link Copied!