CS210 - Quiz 1 Master Question Bank

Q1

For which of the following operations is the Doubly Linked List more efficient than a Singly Linked List?

1 pt

A Inserting a node in the middle of the list B Removing the last node C Inserting at the beginning D Removing the first node

Q2

Which operation is not possible in a singly linked list?

1 pt

A Inserting at the beginning B Removing the last node C Traversing in reverse order D Searching for a specific value

Q3

In a doubly linked list, how many next and prev pointers are null?

1 pt

A None B One next and one prev C Two next pointers D One prev pointer

Q4

Which of the following operations in a singly linked list is the fastest?

1 pt

A Searching for a value B Inserting at the end C Printing everything in the list D Removing the first element

Q5

If an unknown list is given to you, how do you know that it is a circular list?

1 pt

A It has a Head, and Head.prev is null B It has a Tail, and Tail.next is null C Head.prev is the same as Tail.next D It has no next or prev with null values

Q6

We remove a node from the middle of a doubly linked list (using pointers Before and After). Which is the correct code?

1 pt

A Before.next = After; After.prev = Before; B Before.next = After.prev; After.prev = Before.next; C Before.next = After.next; After.prev = Before.prev; D None of the above

Q7

Which of the following would insert a node N at the head of a doubly linked list?

1 pt

A N.next = Head; Head.next = N; Head = N; B Head = N; Head.next = N.next; N.next = Head; C N.next = Head.next; Head.prev = N; Head = N; D N.next = Head; Head.prev = N; Head = N;

Q8

A singly linked list has 6 nodes. Which of the following correctly removes the last node?

1 pt

A

Node itr = Head;
                        while(itr.next!=null) itr = itr.next;
                        itr.next = null;

B

Node itr = Head;
                        while(itr.next.next!=null) itr = itr.next;
                        itr.next = null;

C

Node itr = Tail; itr.next = null;

D

Node itr = Tail; itr.prev = null;

Q9

I want to store names of 10 random students inserted in ascending alphabetical order. Which list gives the fastest insertion response?

1 pt

A Circular List B Single List C An array D Double List

Q10

Which of the following uses the least amount of memory?

1 pt

A Circular List B Singly Linked List C Singly Linked List that also has a Tail D Double Linked List

Q11

What will be the result of deleting the tail node in a circular singly linked list?

1 pt

A The tail pointer becomes NULL B The list becomes a singly linked list C The tail pointer moves to the second last node D The next pointer of the head is modified

Q12

What is the correct way to insert a node at the end of a doubly linked list?

1 pt

A Modify the next pointer of the last node and prev pointer of the new node and adjust the trailer properly B Modify only the next pointer of the last node C Modify only the prev pointer of the last node D Modify the head and tail pointers

Q13

What will be the output of the following code for a DLL containing: 1 → 3 → 5 → 7 → 9?

1 pt

Node* temp = trailer.getPrev();
                while (temp != NULL) {
                System.out.println(temp.getElement());
                temp = temp.getPrev();
                }

A 1 3 5 7 9 B 9 7 5 3 1 C 1 3 5 7 D 7 5 3 1

Q14

What will be the output of the following code for a DLL containing: 1 → 3 → 5 → 7 → 9?

1 pt

E temp = header.getElement();

A 1 B 0 C Null D There is a run time error

Q15

Given a circular linked list with tail pointing to node 1 (order: 1→3→5→7→9→back). After C.rotate(); C.rotate();, the tail will point to which value?

1 pt

A 1 B 3 C 5 D 7

Q16

In the implementation of a circular linked list discussed in class, how can you tell if you've completed traversing a full cycle?

1 pt

A The next pointer of the node is NULL B You encounter the head node again C You encounter the last node D None of the above

Q17

In a singly linked list that contains a single node:

1 pt

A The head and tail will point to the same node B The next of the head will point to the tail C The tail will be null D The next of the head will point to the node itself

Q18

Deleting a node in the middle of a doubly linked list requires…

1 pt

A Shifting all the proceeding nodes backward B No iteration or shifting is required C Finding the middle index and deleting the node at that index D Iterating until reaching the middle position and updating the pointers

Q19

List the main attributes of a node in a doubly linked list.

1 pt

Q20

Write an algorithm search(x) to search a singly linked list for the first occurrence of value x and return its (abstract) position number. The first element has position 1, second has position 2, etc. If the element does not exist return -1.

2 pts

Q21

Sketch (draw) the work needed to swap 2 nodes in a doubly linked list, then write the algorithm swap(DLL, p1, p2). Include predecessor and successor pointers.

2 pts

Drawing required on paper - describe your algorithm and key pointer assignments below.

Q22

Sketch how to create a linked list from an array A = [a, b, c, d]. List the steps involved.

2 pts

Drawing required on paper - describe your steps below.

Q23

Assume you have a doubly-linked list (DLL) with an odd number of elements. Write a method that returns a pointer to the middle node. Note: you cannot use the size() method and you cannot count the number of nodes in the list.

3 pts

Q24

Quiz 1 Summer

Sketch (draw) how to remove the 3rd node from a doubly linked list L. Your answer should include drawings and explanations.

2 pts

Drawing required on paper - describe your approach below.

Q25

Quiz 1 Summer

Assume you have a single-linked list A where all nodes contain positive and negative values. Write a method that returns the number of nodes with negative values.

3 pts

Q26

Show how to add a node in a singly linked list at position x. Your answer should include a drawing and explanation (coding is not required).

2 pts

Drawing required on paper - explain the key steps below.

Q27

Assume you have a doubly linked list of Integers. Write a method that returns the average of those elements.

3 pts

Q28

Write an implementation for the method sumEven(int[] myArray) - which finds the summation of the even numbers in an array.

Example: array A = <10, 3, 7, 6, 10, 53>, then sumEven(A) shall return: 26

1 pt

Q29

Suppose a Singly Linked List is implemented with only head and size variables (no tail). Write an implementation for insertLast(E e) - which inserts the new element at the end of the list. Handle all special cases. This method is inside the SLL class.

2 pts

Q30

Write an implementation for the method findKthFromEnd(int k) - which finds the kth node from the end of a doubly linked list. Handle all special cases. This method is inside the DLL class.

2 pts