Chapter 03- LINKED LIST

 3.1Introduction

1. How many cases are there, which are used to compare various data
structure's execution time in a relative manner?

A. 2
B. 3
C. 4
D. 5
Ans : B. 3

2. Which case of data structure operation takes maximum time?

A. Worst Case
B. Average Case
C. Best Case
D. None of the above

Ans : A. Worst Case

3. In Average case, if operation takes Æ’(n) time in execution, then

m operations will take?

A. Æ’(n)
B. f(m)
C. mf(n)
D. nf(m)

Ans : C. mf(n)

4. __________ is a single elementary unit of information representing

an attribute of an entity.

A. Entity Set
B. Record
C. File
D. Field

Ans : D.Field

5. What is true about Interface in data structure?

A. Each data structure has an interface.
B. Interface represents the set of operations that a data structure
supports.
C. An interface only provides the list of supported operations, type
of parameters they can accept and return type of these operations.
D. All of the above

Ans : D.All of the above

6. Which of the following is not a Characteristics of a Data

Structure?

A. Completeness
B. Correctness
C. Time Complexity
D. Space Complexity

Ans : A. Completeness

7. Which characteristics shows that running time or the execution

time of operations of data structure must be as small as possible?

A. Completeness
B. Correctness
C. Time Complexity
D. Space Complexity

Ans : C.Time Complexity

8. Data items that cannot be divided are called as?

A. Group Items
B. Attribute and Entity
C. Elementary Items
D. File items

Ans : C. Elementary Items

9. Which of the following analysis known as theoretical analysis of

an algorithm?

A. A Posterior Analysis
B. A Priori Analysis
C. A Feasibility Analysis
D. A Independent Analysis

Ans : B. A Priori Analysis

10. Which of the following analysis known as empirical analysis of an

algorithm?

A. A Posterior Analysis
B. A Priori Analysis
C. A Feasibility Analysis
D. A Independent Analysis

Ans : A. A Posterior Analysis

 3.2 Dynamic Emplimentation

Q.1. How do you calculate the pointer difference in a memory efficient
double linked list?

1 head xor tail

2 pointer to previous node xor pointer to next node
3 pointer to previous node €“ pointer to next node
4 pointer to next node €“ pointer to previous node

Answer:- (2)pointer to previous node xor pointer to next node

Q.2. What is a memory efficient double linked list?

Each node has only one pointer to traverse the list back and forth

The list has breakpoints for faster traversal

An auxiliary singly linked list acts as a helper list to traverse

through the doubly linked list

A doubly linked list that uses bitwise AND operator for storing
addresses

Answer C An auxiliary singly linked list acts as a helper list to

traverse through the doubly linked list

3) LLINK is the pointer pointing to the ...

A. successor node
B. predecessor node
C. head node
D. last node
Answer B. predecessor node

4) A ...... indicates the end of the list.

A. Guard
B. Sentinel
C. End pointer
D. Last pointer
Answer B. Sentinel

5) A ........ is a linear list in which insertions and deletions are

made to from either end of the structure.
A. circular queue
B. random of queue
C. priority
D. dequeue
Answer D. dequeue

6) Indexing the........ element in the list is not possible in linked

lists.
A. middle
B. first
C. last
D. anywhere in between
Answer A. middle

7) A linear list in which the pointer points only to the successive

node is......
A. singly linked list
B. circular linked list
C. doubly linked list
D. none of the above.
Answer A. singly linked list

8) .......... may take place only when there is some minimum amount
(or) no space left in free storage
list.
A. Memory management
B. Garbage collection
C. Recycle bin
D. Memory management
Answer B. Garbage collection

9) A linear list in which the last node points to the first node is
........
A. singly linked list
B. circular linked list
C. doubly linked list
D. none of the above
Answer B. circular linked list

10) A doubly linked list has .......... pointers with each node.
A. 0
B. 1
C. 2
D. 3
Answer C. 2

11) Header linked lists are frequently used for maintaining........ in

memory.
A. Polynomials
B. Binomal
C. Trinomial
D. Quadratic equation
Answer A. Polynomials

12) The pointer that points to the first node in the list is........
A. FIRST
B. AVAIL
C. TOP
D. REAR

 3.3 Types of Linked list

(1)........ is not the operation that can be performed on queue.

[A] Traversal

[B] Retrieval

[C] Deletion

[D] Insertion

Answer: [A] Traversal

(2) A linear list in which the last node points to the first node is
........

[A] singly linked list

[B] doubly linked list

[C] circular linked list

[D] none of the above

Answer: [C] circular linked list

(3) A linear list in which the pointer points only to the successive
node is......

[A] singly linked list

[B] circular linked list

[C] doubly linked list

[D] none of the above

Answer: [A] singly linked list

(4) A ...... indicates the end of the list.

[A] Guard

[B] Sentinel

[C] End pointer

[D] Last pointer

Answer: [B] Sentinel

(5) LLINK is the pointer pointing to the ......

[A] head node

[B] last node

[C] successor node

[D] predecessor node

Answer: [D] predecessor node

(6) Indexing the........ element in the list is not possible in linked

lists.

[A] first

[B] middle

[C] last

[D] All of the above

Answer: [B] middle

(7) A doubly linked list has .......... pointers with each node.

[A] 0
[B] 1

[C] 2

[D] 3

Answer: [C] 2

(8) A linear list in which each node has point to the predecessor and
successors nodes is called ........

[A] singly linked list

[B] linear linked list

[C] doubly linked list

[D] None of the above

Answer: [C] doubly linked list

(9) RLINK is the pointer pointing to the......

[A] last node

[B] head node

[C] successor node

[D] predecessor node

Answer: [C] successor node

(10)In a linked list, insertion can be done as.........

[A] beginning

[B] middle

[C] end

[D] all of the above

Answer:
Q.11. What would be the asymptotic time complexity to add a node at
the end of singly linked list, if the pointer is initially pointing to
the head of the list?

1. O(1)

2. O(n)

3. θ(n)

4. θ(1)

Answer:- (3)

 3.4 Operations on linked list

Q.1.What is the worst case run-time complexity of binary search

algorithm?

Ο(n2)

Ο(nlog n)

Ο(n3)

Ο(n)

Answer:- (4)

Q.2. If there's no base criteria in a recursive program, the program

will

not be executed.

execute until all conditions match.

execute infinitely.

obtain progressive approach.

Answer:- (3)

Q.3. The depth of complete binary tree is given by

Dn = n log2n
Dn = n log2n +1

Dn = log2n

Dn = log2n + 1

Answer:- (4)

Q.4. The postfix form of the expression (A+ B)*(C*D- E)*F / G is?

AB+ CD*E €“ FG /**

AB + CD* E €“ F **G /

AB + CD* E €“ *F *G /

AB + CDE * €“ * F *G /

Answer:- (3)

Q.5. Which data structure is needed to convert infix notation to

postfix notation?

Branch

Tree

Queue

Stack

Answer:- (4)

Q.6. One can convert a binary tree to its mirror image by traversing
it in

Inorder

Preorder

Postorder

None of the above

Answer:- (3)

Q.7. For an undirected graph with n vertices and e edges, the sum of
degree of each vertex is equal to

2n
2e

(e2+1)/2

(2n-1)/2

Answer:- (2)

Q.8. A data structure in which elements can be inserted or deleted

at/from both the ends but not in the middle is?

Queue

Circular queue

Dequeue

Priority queue

Answer:- (3)

Q.9. What would be the asymptotic time complexity to add a node at

the end of singly linked list, if the pointer is initially pointing to
the head of the list?

O(1)

O(n)

θ(n)

θ(1)

Answer:- (3)

Q.10. Consider the following definition in c programming language

struct node
{
int data;
struct node * next;
}
typedef struct node NODE;
NODE *ptr;

Which of the following c code is used to create new node?

ptr = (NODE*)malloc(sizeof(NODE));

ptr = (NODE*)malloc(NODE);

ptr = (NODE*)malloc(sizeof(NODE*));
ptr = (NODE)malloc(sizeof(NODE));

Answer:- (1)

Q.11. Which of the following points is/are not true about Linked List
data structure when it is compared with array?

Arrays have better cache locality that can make them better in terms
of performance

It is easy to insert and delete elements in Linked List

Random access is not allowed in a typical implementation of Linked

Lists

Access of elements in linked list takes less time than compared to

arrays

Answer:- (4)

Q.12. You are given pointers to first and last nodes of a singly
linked list, which of the following operations are dependent on the
length of the linked list?

Delete the first element

Insert a new element as a first element

Delete the last element of the list

Add a new element at the end of the list

Answer:- (3)

Q.13. What is a memory efficient double linked list?

Each node has only one pointer to traverse the list back and forth

The list has breakpoints for faster traversal

An auxiliary singly linked list acts as a helper list to traverse

through the doubly linked list

A doubly linked list that uses bitwise AND operator for storing
addresses

Answer:- (1)

Q.14. How do you calculate the pointer difference in a memory

efficient double linked list?
head xor tail

pointer to previous node xor pointer to next node

pointer to previous node €“ pointer to next node

pointer to next node €“ pointer to previous node

Answer:- (2)

Q.15. Which of the following application makes use of a circular

linked list?

Undo operation in a text editor

Recursive function calls

Allocating CPU to resources

Implement Hash Tables

Answer:- (3)

Q.16. Array implementation of Stack is not dynamic, which of the

following statements supports this argument?

space allocation for array is fixed and cannot be changed during run-
time

user unable to give the input for stack operations

a runtime exception halts execution

improper program compilation

Answer:- (1)

Q.17. Which of the following data structures can be used for

parentheses matching?

n-ary tree

queue

priority queue

stack

Answer:- (4)

Q.18. What is the time complexity of enqueue operation?

O(logn)

O(nlogn)

O(n)

O(1)

Answer:- (4)

Q.19. In case of insertion into a linked queue, a node borrowed from

the __________ list is inserted in the queue.

AVAIL

FRONT

REAR

NULL

Answer:- (1)

Q.20. Which of the following is true about linked list implementation

of queue?

In push operation, if new nodes are inserted at the beginning of

linked list, then in pop operation, nodes must be removed from end

In push operation, if new nodes are inserted at the beginning, then in

pop operation, nodes must be removed from the beginning

In push operation, if new nodes are inserted at the end, then in pop
operation, nodes must be removed from end

In push operation, if new nodes are inserted at the end, then in pop
operation, nodes must be removed from beginning.

Answer:- (1)

Q.21.The concatenation of two list can performed in O

(1) time. Which of the following variation of linked list can be used?
a.Singly linked list
b.Doubly linked list
c.Circular doubly linked list
d.Array implementation of listAnswer:Circular doubly linked list

21) To insert a new node in linked list free node will be available in
........
A. Available list
B. Avail list
C. Free node list
D. Memory space list

22) If the availability list is null, then the condition is said to be

.........
A. nil block
B. availability list underflow
C. availability list overflow
D. memory loss

Q 23 - Which of the below mentioned sorting algorithms are not

stable?

A - Selection Sort
B - Bubble Sort
C - Merge Sort
D - Insertion Sort

Q 24 - A queue data-structure can be used for ˆ’

A - expression parsing
B - recursion
C - resource allocation
D - all of the above

Q 25 - The following sorting algorithms maintain two sub-lists, one

sorted and one to be sorted ˆ’

A - Selection Sort
B - Insertion Sort
C - Merge Sort
D - both A &am; B

Q 26 - Which of the following searching techniques do not require the

data to be in sorted form

A - Binary Search
B - Interpolation Search
C - Linear Search
D - All of the above

Q 27 - Apriory algorithm analysis does not include ˆ’

A - Time Complexity
B - Space Complexity
C - Program Complexity
D - None of the above!

Q 28 - Which of the below mentioned sorting algorithms are not stable?

A - Selection Sort
B - Bubble Sort
C - Merge Sort
D- Insertion Sort

16. €¦ €¦ €¦ €¦ €¦ €¦. is not an operation performed on linear list

a) Insertion b) Deletion c) Retrieval d) Traversal
A) only a,b and c
B) only a and b
C) All of the above
D) None of the above

17) Very slow way of sorting is..........

A. Insertion sort
B. Heap sort
C. Bubble sort
D. Quick sort

 3.5 Applications of linked list

Question: 1
A data structure in which linear sequence is maintained by pointers is
known as
(A) Array
(B) Stack
(C) Linked list
(D) Pointer-based data structure
Ans: C
Linked list
Question: 2
Which of the following data structure works on the principle of First
Come First Serve?
(A) Priority queue
(B) Heap
(C) Stack
(D) Queue
Ans: D
Queue
Question: 3
A ____ is a linear collection of self-referential structures, called
nodes, connected by pointer links.
(A) Queue
(B) Linked list
(C) Tree
(D) Stack
Ans: B
Linked list
Question: 4
A queue where all elements have equal priority is a
(A) ILFO data structure
(B) LILO data structure
(C) FIFO data structure
(D) LIFO data structure
Ans: C
FIFO data structure
Question: 5
A file that is only read by a program is known as ____
(A) Input file
(B) Temporary file
(C) Work file
(D) Input/output file
Ans: A
Input file
Question: 6
Which of the following sorting algorithm is the slowest?
(A) Bubble sort
(B) Heap sort
(C) Shell sort
(D) Quick sort
Ans: A
Bubble sort
Question: 7
Which of the following data structure can be used to represent many-
to-many relation?
(A) B-tree
(B) Binary tree
(C) Graph
(D) All of above
Ans: C
Graph
Question: 8
Which of the following statement is not true about linked lists?
(A) Element in a linked list, if it is sorted, can be quickly searched
by applying binary search technique
(B) Elements are not necessarily stored in contiguous locations
(C) Insertions and deletions can be performed efficiently as compared
to arrays
(D) Linked list is a dynamic structure
Ans: A
Element in a linked list, if it is sorted, can be quickly searched by
applying binary search technique
Question: 9
Which of the following is not a linear data structure?
(A) Stack
(B) Queue
(C) Linked list
(D) Binary tree
Ans: D
Binary tree
Question: 10
Which of the following data structure permits insertion and deletion
operations only on one end of the structure?
(A) Linked list
(B) Array
(C) Stack
(D) Queue
Ans: C
Stack

 3.6 Generalization of linked list

1. Which of the following is not a disadvantage to the usage of array?

a) Fixed size
b) There are chances of wastage of memory space if elements inserted
in an array are lesser than the allocated size
c) Insertion based on position
d) Accessing elements at specified positions

Answer d) Accessing elements at specified positions

2. What is the time complexity of inserting at the end in dynamic

arrays?
a) O(1)
b) O(n)
c) O(logn)
d) Either O(1) or O(n)

Answer: d) Either O(1) or O(n)

3. What is the time complexity to count the number of elements in the

linked list?
a) O(1)
b) O(n)
c) O(logn)
d) O(n2)

Answer: b O(n)

4. Which of the following performs deletion of the last element in the

list? Given below is the Node class.

class Node { protected Node next; protected Object ele;

Node(Object e,Node n) { ele = e; next = n;
} public void setNext(Node n) { next = n; }
public void setEle(Object e) { ele = e; }
public Node getNext() { return next; }
public Object getEle() { return ele; } } class
SLL { Node head; int size; SLL() { size = 0;
} }

a)public Node removeLast() { if(size == 0) null; Node cur;

 Node temp; cur = head; while(cur.getNext() != null)
{ temp = cur; cur = cur.getNext(); }
temp.setNext(null); size--; return cur; }

b)public void removeLast() { if(size == 0) return null; Node

cur; Node temp; cur = head; while(cur != null) {
temp = cur; cur = cur.getNext(); }
temp.setNext(null); return cur; }

c)public void removeLast() { if(size == 0) return null; Node

cur; Node temp; cur = head; while(cur != null) {
cur = cur.getNext(); temp = cur; }
temp.setNext(null); return cur; }

d)public void removeLast() { if(size == 0) return null;

Node cur; Node temp; cur = head; while(cur.getNext()
!= null) { cur = cur.getNext(); temp = cur; }
temp.setNext(null); return cur; }

Answer: a)public Node removeLast() { if(size == 0) null; Node

cur; Node temp; cur = head; while(cur.getNext() != null)
{ temp = cur; cur = cur.getNext(); }
temp.setNext(null); size--; return cur; }
5. What is the functionality of the following code?

public void function(Node node) { if(size == 0) head =

node; else { Node temp,cur; for(cur = head; (temp
= cur.getNext())!=null; cur = temp); cur.setNext(node); }
size++; }

a) Inserting a node at the beginning of the list

b) Deleting a node at the beginning of the list
c) Inserting a node at the end of the list
d) Deleting a node at the end of the list

Answer: c) Inserting a node at the end of the list

6. What is the space complexity for deleting a linked list?

a) O(1)
b) O(n)
c) Either O(1) or O(n)
d) O(logn)
Answer: a) O(1)

Explanation: You need a temp variable to keep track of current node,

hence the space complexity is O(1).

7. How would you delete a node in the singly linked list? The position
to be deleted is given.
a)
public void delete(int pos) { if(pos < 0) pos = 0; if(pos >
size) pos = size; if( size == 0) return; if(pos == 0)
head = head.getNext(); else { Node temp = head;
for(int i=1; i<pos; i++) { temp = temp.getNext(); }
temp.setNext(temp.getNext().getNext()); } size--; }

b)
public void delete(int pos) { if(pos < 0) pos = 0; if(pos >
size) pos = size; if( size == 0) return; if(pos == 0)
head = head.getNext(); else { Node temp = head;
for(int i=1; i<pos; i++) { temp = temp.getNext(); }
temp.setNext(temp.getNext()); } size--; }

c)
public void delete(int pos) { if(pos < 0) pos = 0; if(pos > size)
pos = size; if( size == 0) return; if(pos == 0) head
= head.getNext(); else { Node temp = head; for(int i=1;
i<pos; i++) { temp = temp.getNext().getNext(); }
temp.setNext(temp.getNext().getNext()); } size--; }

d)public void delete(int pos) { if(pos < 0) pos = 0; if(pos > size)
pos = size; if( size == 0) return; if(pos == 0) head =
head.getNext(); else { Node temp = head; for(int i=0; i<pos;
i++) { temp = temp.getNext(); }
temp.setNext(temp.getNext().getNext()); } size--; }

Answer: a)
public void delete(int pos) { if(pos < 0) pos = 0; if(pos >
size) pos = size; if( size == 0) return; if(pos == 0)
head = head.getNext(); else { Node temp = head;
for(int i=1; i<pos; i++) { temp = temp.getNext(); }
temp.setNext(temp.getNext().getNext()); } size--; }

8. Which of these is not an application of linked list?

a) To implement file systems
b) For separate chaining in hash-tables
c) To implement non-binary trees
d) Random Access of elements

Answer: d) Random Access of elements

9. Which of the following piece of code has the functionality of

counting the number of elements in the list?
a)public int length(Node head) { int size = 0; Node cur = head;
while(cur!=null) { size++; cur = cur.getNext();
} return size; }

b)public int length(Node head) { int size = 0; Node cur = head;

while(cur!=null) { cur = cur.getNext(); size++;
} return size; }
c)public int length(Node head) { int size = 0; Node cur = head;
while(cur!=null) { size++; cur = cur.getNext();
} }

d)public int length(Node head) { int size = 0; Node cur = head;

while(cur!=null) { size++; cur =
cur.getNext().getNext(); } return size; }

Answer: a)public int length(Node head) { int size = 0; Node cur =

head; while(cur!=null) { size++; cur = cur.getNext();
} return size; }

10. How do you insert an element at the beginning of the list?

a)public void insertBegin(Node node) { node.setNext(head); head

= node; size++; }

b)public void insertBegin(Node node) { head = node;

node.setNext(head); size++; }

c)public void insertBegin(Node node) { Node temp = head.getNext()

node.setNext(temp); head = node; size++; }

d)public void insertBegin(Node node) { Node temp = head.getNext()

node.setNext(temp); node = head; size++; }

Answer: a)public void insertBegin(Node node) { node.setNext(head);

head = node; size++; }

11. What is the functionality of the following piece of code?

public int function(int data) { Node temp = head; int var = 0;

while(temp != null) { if(temp.getData() == data)
{ return var; } var = var+1;
temp = temp.getNext(); } return Integer.MIN_VALUE; }

a) Find and delete a given element in the list

b) Find and return the given element in the list
c) Find and return the position of the given element in the list
d) Find and insert a new element in the list

Answer: c) Find and return the position of the given element in the
list

12. The following C function takes a singly linked list as input

argument. It modifies the list by moving the last element to the front
of the list and returns the modified list. Some part of the code left
blank.
typedef struct node
{
int value;
struct node* next;
}Node;
Node* move_to_front(Node* head)
{
Node* p, *q;
if((head==NULL) || (head->next==NULL))
return head;
q=NULL;
p=head;
while(p->next != NULL)
{
q=p;
p=p->next;
}
return head;
}

Choose the correct alternative to replace the blank line

a) q=NULL; p->next=head; head =p ;

b) q->next=NULL; head =p; p->next = head;
c) head=p; p->next=q; q->next=NULL;
d) q->next=NULL; p->next=head; head=p;
/

13. The following C Function takes a singly- linked list of integers

as a parameter and rearranges
the elements of the lists. The function is called with the list
containing the integers 1,2,3,4,5,6,7 in the given order. What will be
the contents of the list after the function completes execution?

struct node{
int value;
struct node* next;
};
void rearrange (struct node* list)
{
struct node *p,q;
int temp;
if (! List || ! list->next) return;
p->list; q=list->next;
while(q)
{
temp=p->value; p->value=q->value;
q->value=temp;p=q->next;
q=p?p->next:0;
}
}
a) 1, 2, 3, 4, 5, 6, 7
b) 2, 1, 4, 3, 6, 5, 7
c) 1, 3, 2, 5, 4, 7, 6
d) 2, 3, 4, 5, 6, 7, 1

ANSWER: b) 2, 1, 4, 3, 6, 5, 7

14. consider the function f defined here:

struct item
{
int data;
struct item * next;
};
int f (struct item *p)
{
return((p==NULL) ||((p->next==NULL)||(p->data<=p->next->data) && (p-
>next)));
}

For a given linked list p, the function f returns 1 if and only if

a) the list is empty or has exactly one element

b) the element in the list are sorted in non-decreasing order of data
value
c) the element in the list are sorted in non-increasing order of data
value
d) not all element in the list have the same data value

ANSWER: b) the element in the list are sorted in non-decreasing order

of data value

15. Which of the following performs deletion of the last element in

the list? Given below is the Node class.

class Node { protected Node next; protected Object ele;

Node(Object e,Node n)
{ ele = e; next = n; } public void
setNext(Node n) { next = n;
} public void setEle(Object e) { ele = e; }
public Node getNext() { return next; }
public Object getEle() { return ele; } } class
SLL { Node head; int size; SLL() { size = 0;
} }

a)public Node removeLast() { if(size == 0) return null; Node

cur; Node temp; cur = head; while(cur.getNext() != null)
{ temp = cur; cur = cur.getNext(); }
 temp.setNext(null); size--; return cur; }

b)public void removeLast() { if(size == 0) return null; Node

cur; Node temp; cur = head; while(cur != null) {
temp = cur; cur = cur.getNext(); }
temp.setNext(null); return cur; }

c)public void removeLast() { if(size == 0) return null; Node

cur; Node temp; cur = head; while(cur != null) {
cur = cur.getNext(); temp = cur; }
temp.setNext(null); return cur; }

d)public void removeLast() { if(size == 0) return null;

Node cur; Node temp; cur = head; while(cur.getNext()
!= null) { cur = cur.getNext(); temp = cur; }
temp.setNext(null); return cur;

Answer a)public Node removeLast() { if(size == 0) return null;

Node cur; Node temp; cur = head; while(cur.getNext()
!= null) { temp = cur; cur = cur.getNext(); }
temp.setNext(null); size--; return cur; }