Top List List

The Data Structure of avail list is

This set of Data Structure Multiple Choice Questions & Answers [MCQs] focuses on Singly 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
View Answer

Answer: d
Explanation: Array elements can be accessed in two steps. First, multiply the size of the data type with the specified position, second, add this value to the base address. Both of these operations can be done in constant time, hence accessing elements at a given index/position is faster.

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]
View Answer

Answer: d
Explanation: Depending on whether the array is full or not, the complexity in dynamic array varies. If you try to insert into an array that is not full, then the element is simply stored at the end, this takes O[1] time. If you try to insert into an array which is full, first you will have to allocate an array with double the size of the current array and then copy all the elements into it and finally insert the new element, this takes O[n] time.

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]
View Answer

Answer: b
Explanation: To count the number of elements, you have to traverse through the entire list, hence complexity is O[n].

Note: Join free Sanfoundry classes at Telegram or Youtube

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; } }

Take Data Structure I Practice Tests - Chapterwise!
Start the Test Now: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

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; }

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; }

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; }

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; }

View Answer

Answer: a
Explanation: Since you have to traverse to the end of the list and delete the last node, you need two reference pointers. cur to traverse all the way and find the last node, and temp is a trailing pointer to cur. Once you reach the end of the list, setNext of temp to null, cur is not being pointed to by any node, and hence it is available for garbage collection.

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
View Answer

Answer: c
Explanation: The for loop traverses through the list and then inserts a new node as cur.setNext[node];

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]
View Answer

Answer: a
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 size] pos = size; if[ size == 0] return; if[pos == 0] head = head.getNext[]; else { Node temp = head; for[int i=1; i

Bài Viết Liên Quan

Toplist mới

Bài mới nhất

Chủ Đề