gs gs121 Abstract Data Types - Doubly Linked Lists - Quiz No.1
gs gs121 Data Structures and Algorithms Quiz
This quiz belongs to book/course code gs gs121 Data Structures and Algorithms of gs organization. We have 169 quizzes available related to the book/course Data Structures and Algorithms. This quiz has a total of 10 multiple choice questions (MCQs) to prepare and belongs to topic Abstract Data Types. NVAEducation wants its users to help them learn in an easy way. For that purpose, you are free to prepare online MCQs and quizzes.
NVAEducation also facilitates users to contribute in online competitions with other students to make a challenging situation to learn in a creative way. You can create one to one, and group competition on an topic of a book/course code. Also on NVAEducation you can get certifications by passing the online quiz test.
Question 1: Which of the following is false about a doubly linked list?
We can navigate in both the directions
It requires more space than a singly linked list
The insertion and deletion of a node take a bit longer
Implementing a doubly linked list is easier than singly linked list
Question 2: Given the Node class implementation, select one of the following that correctly inserts a node at the tail of the list.
public class Node { protected int data; protected Node prev; protected Node next; public Node(int data) { this.data = data; prev = null; next = null; } public Node(int data, Node prev, Node next) { this.data = data; this.prev = prev; this.next = next; } public int getData() { return data; } public void setData(int data) { this.data = data; } public Node getPrev() { return prev; } public void setPrev(Node prev) { this.prev = prev; } public Node getNext { return next; } public void setNext(Node next) { this.next = next; } } public class DLL { protected Node head; protected Node tail; int length; public DLL() { head = new Node(Integer.MIN_VALUE,null,null); tail = new Node(Integer.MIN_VALUE,null,null); head.setNext(tail); length = 0; } } public void insertRear(int data) { Node node = new Node(data,tail.getPrev(),tail); node.getPrev().setNext(node); tail.setPrev(node); length++; } public void insertRear(int data) { Node node = new Node(data,tail.getPrev(),tail); node.getPrev().getPrev().setNext(node); tail.setPrev(node); length++; } public void insertRear(int data) { Node node = new Node(data,tail.getPrev(),tail); node.getPrev().setNext(tail); tail.setPrev(node); length++; } public void insertRear(int data) { Node node = new Node(data,head,tail); node.getPrev().setNext(node); tail.setPrev(node); length++; }
Question 3: 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
Question 4: Which of the following piece of code removes the node from a given position?
public void remove(int pos) { if(pos<0 || pos>=size) { System.out.println("Invalid position"); return; } else { if(head == null) return; if(pos == 0) { head = head.getNext(); if(head == null) tail = null; } else { Node temp = head; for(int i=1; i<position; i++) temp = temp.getNext(); } temp.getNext().setPrev(temp.getPrev()); temp.getPrev().setNext(temp.getNext()); } size--; } public void remove(int pos) { if(pos<0 || pos>=size) { System.out.println("Invalid position"); return; } else { if(head == null) return; if(pos == 0) { head = head.getNext(); if(head == null) tail = null; } else { Node temp = head; for(int i=1; i<position; i++) temp = temp.getNext(); } temp.getNext().setPrev(temp.getNext()); temp.getPrev().setNext(temp.getPrev()); } size--; } public void remove(int pos) { if(pos<0 || pos>=size) { System.out.println("Invalid position"); return; } else { if(head == null) return; if(pos == 0) { head = head.getNext(); if(head == null) tail = null; } else { Node temp = head; for(int i=1; i<position; i++) temp = temp.getNext().getNext(); } temp.getNext().setPrev(temp.getPrev()); temp.getPrev().setNext(temp.getNext()); } size--; } public void remove(int pos) { if(pos<0 || pos>=size) { System.out.println("Invalid position"); return; } else { if(head == null) return; if(pos == 0) { head = head.getNext(); if(head == null) tail = null; } else { Node temp = head; for(int i=1; i<position; i++) temp = temp.getNext().getNext(); } temp.getNext().setPrev(temp.getNext()); temp.getPrev().setNext(temp.getPrev()); } size--; }
Question 5: 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
Question 6: What is the worst case time complexity of inserting a node in a doubly linked list?
O(nlogn)
O(logn)
O(n)
O(1)
Question 7: How do you insert a node at the beginning of the list?
public class insertFront(int data) { Node node = new Node(data, head, head.getNext()); node.getNext().setPrev(node); head.setNext(node); size++; } public class insertFront(int data) { Node node = new Node(data, head, head); node.getNext().setPrev(node); head.setNext(node); size++; } public class insertFront(int data) { Node node = new Node(data, head, head.getNext()); node.getNext().setPrev(head); head.setNext(node); size++; } public class insertFront(int data) { Node node = new Node(data, head, head.getNext()); node.getNext().setPrev(node); head.setNext(node.getNext()); size++; }
Question 8: Consider the following doubly linked list: head-1-2-3-4-5-tail. What will be the list after performing the given sequence of operations?
Node temp = new Node(6,head,head.getNext()); Node temp1 = new Node(0,tail.getPrev(),tail); head.setNext(temp); temp.getNext().setPrev(temp); tail.setPrev(temp1); temp1.getPrev().setNext(temp1);
head-0-1-2-3-4-5-6-tail
head-1-2-3-4-5-6-tail
head-6-1-2-3-4-5-0-tail
head-0-1-2-3-4-5-tail
Question 9: What is the functionality of the following piece of code?
public int function() { Node temp = tail.getPrev(); tail.setPrev(temp.getPrev()); temp.getPrev().setNext(tail); size--; return temp.getItem(); }
Return the element at the tail of the list but do not remove it
Return the element at the tail of the list and remove it from the list
Return the last but one element from the list but do not remove it
Return the last but one element at the tail of the list and remove it from the list
Question 10: Consider the following doubly linked list: head-1-2-3-4-5-tail. What will be the list after performing the given sequence of operations?
Node temp = new Node(6,head,head.getNext()); head.setNext(temp); temp.getNext().setPrev(temp); Node temp1 = tail.getPrev(); tail.setPrev(temp1.getPrev()); temp1.getPrev().setNext(tail);
head-6-1-2-3-4-5-tail
head-6-1-2-3-4-tail
head-1-2-3-4-5-6-tail
head-1-2-3-4-5-tail
Online Quizzes of gs121 Data Structures and Algorithms
Binary Trees - Binary Search Tree - Quiz No.1
gs gs121
Data Structures and Algorithms Online Quizzes
Binary Trees - Binary Search Tree - Quiz No.2
gs gs121
Data Structures and Algorithms Online Quizzes
Binary Trees - Preorder Traversal - Quiz No.1
gs gs121
Data Structures and Algorithms Online Quizzes
