Singly Linked List

Multiple Choice

1. Suppose cursor points to a node in a linked list. What statement changes cursor so that it points to the next node?
1. cursor++;
2. cursor = link( );
3. cursor += link( );
4. cursor = cursor->link( );

Ans. : d, this statement will change the current position of the cursor.

2. Suppose cursor points to a node in a linked list. What Boolean expression will be true when cursor points to the tail node of the list?
1. (cursor == NULL)
2. (cursor->link( ) == NULL)
3. (cursor->data( ) == NULL)
4. (cursor->data( ) == 0.0)
5.  None of the above.

Ans. : b, On the last node, the last node’s link will be pointing toward NULL, so cursor->link() = > Last_node->link

3. Suppose that p is a pointer variable that contains the NULL pointer. What happens if your program tries to read or write *p?
1. A syntax error always occurs at compilation time.
2. A run-time error always occurs when *p is evaluated.
3. A run-time error always occurs when the program finishes.
4. The results are unpredictable.

Ans. : b, when p is evaluated, a runtime error occurs.

4. Suppose that f is a function with a prototype like this:

  void f(________ head_ptr);

       // Precondition: head_ptr is a head pointer for a linked list.

    // Postcondition: The function f has done some computation with

    // the linked list, but the list itself is unchanged.

What is the best data type for head_ptr in this function?

1. node
2. const node
3. node*
4. const node*

Ans. : c, since the linked list is not changing, it does not matters if we accept the node ptr as a formal argument

5. Suppose that f is a function with a prototype like this:

     void f(________ head_ptr);

    // Precondition: head_ptr is a head pointer for a linked list.

    // Postcondition: The function f has done some manipulation of

    // the linked list, and the list might now have a new head node.

What is the best data type for head_ptr in this function?

1.  node
2.  node&
3.  node*
4.  node*&

Ans. : d, since the linked list might change, we have to accept it’s address rather than the node pointer as such.

6. What is the expression for generating a pseudorandom number in the range 1...N?
1.  rand() % N;
2.  rand() / N;
3.  rand() % (N + 1);
4.  rand() / (N + 1);
5.  (rand() % N) + 1;

Ans. :  e, it will work out as that always.

7. Which expression computes a pseudorandom integer between -10 and 10 using rand() from stdlib.h?
1.  (rand( ) % 20) - 10
2.  (rand( ) % 21) - 10
3.  (rand( ) % 22) - 10
4.  (rand( ) % 20) - 11
5.  (rand( ) % 21) - 11

Ans. : a, b, Both give numbers between -10 and 10.

8. What kind of list is best to answer questions such as "What is the item at position n?"
1. Lists implemented with an array.
2. Doubly-linked lists.
3. Singly-linked lists.
4. Doubly-linked or singly-linked lists are equally best

Ans. : a, the list implemented using an array, because array only gives instant access.

9.    Linear order linked list is provided through _________

1. variables
2. arrays
3. Pointer
4. strings

Ans)C

10.    In a Single Link List_________ node contains no links.

1. First
2. Last
3. last but one
4. middle

Ans)B

11.    A linked list is which type of data structure.

1. Linear
2. Non Linear
3. Hierarchical
4. None

Ans)A

12.    In Single Linked List a node contain minimum how many fields(assuming one for data).

1. 2
2. 3
3. 1
4. None

Ans)A

13.    Implementation of priority queue
1) Tree
2) Linked list
3) Doubly linked list

1. 1 and 2
2. 2 and 3
3. 1 and 3
4. All

Ans)B

14.     Null pointer is used to tell
1) End of the linked list
2) Empty pointer field of a structure
3) The linked list is empty

1. 1
2. 2 and 3
3. 1 and 3
4. All

Ans)A

15.    Single link list performs which of the following methods
1) Insertion
2) Modification
3) Searching

1. 1 and 2
2. 2 and 3
3. 1 and 3
4. All

Ans)D

16.    The list with no node is called as
1) Empty list
2) Null list
3) Zero list

1. 1 and 2
2. 2 and 3
3. 1 and 3
4. All

Ans)A

17.   An application that make use of Multilinked Structures Is_________?

1. Sparse matrix
2. Linked list
3. Tree
4. Stack

Ans)A

18.   Given a arbitrary pointer to an element in a singly linked list, the time complexity for its deletion ___________.

1. O(n/2)
2. O(n*n)
3. O(n)
4. O(n*n/2)

Ans)C

19.   In C language to implement the heterogeneous linked list__________ pointer is used.

1. Void
2. Null
3. Int
4. Structure

Ans)A

20.   Searching a linked list requires linked list be created

1. In sorted order only
2. In any order
3. Without under flow condition
4. None

Ans)B

21.   In linked list the logical order of elements –

1. Is same as their physical arrangement
2. Is not necessarily equivalent  to their physical arrangement
3. Is determined by their logical arrangement
4. None

Ans)B

22. According to Storage strategies Linked list is a

1. Nonlinear
2. Linear
3. Sequential
4. dynamic

Ans : a

23.   Implementation of a list in a dynamic fashion is

1. To call upon the system to allocate and free storage may not be time consuming
2. A set of nodes not reserved in advance for use
3. The address computation  is complex
4. None

Ans)B

24.    If you are using  C language  to implement a heterogeneous  linked list, the pointer type u will prefer is ________

1. int*
2. Null
3. void*
4. float*

Ans)C

25. Which of the following statement is true

a.       The next address field of the node can be empty

b.      A list can exist with no nodes

c.       In a singly linked list the starting address of the list is stored in the address field of the last node

d.    All of the above

Ans : b, A list with no nodes is called empty list or null list

26. Type of storage is used to represent Lists

1. Random
2. Sequential
3. Dynamic
4. Logical

Ans : c , page 187 tenenbaum

     27.  The node in a singly linked list can be deleted,

a. Without traversing the list

b.By traversing the list from the head

c. By traversing the list from the tail

d.                                                                              All of the above

Ans: b

28.     Which of the following operations is not efficiently supported

             by a singly-linked list? 

a.       accessing the element in the current position

b.      insertion after the current position

c.       insertion before the current position

d.      moving to the position immediately following the current position

    Ans : c

29.What is an ordered list

a.          where the address is ordered

b.          where the smaller items precede the larger ones

c.          both a and b

d.         none

          Ans : b

30.According to Access strategies Linked list is a

a.       Nonlinear

b.      Linear

c.       Sequential

d.      dynamic

Ans : b

31.How many nodes are accessed, on the average, in inserting a new element into an ordered list with n nodes

a.(n+1)/2

b.n/2

c.1/(n+1)

d.None

         Ans : b, page 200 of  Tenenbaum 2^nd edition

32.A priority Queue implemented as an ordered linked list requires examining an

    average of approximately _______ nodes for insertion

a. (n+1)/2

b.1/(n+1)

c.n/2

d.one

      Ans :  c, page 200 of  Tenenbaum 2^nd edition

33.A priority Queue implemented as an ordered linked list requires examining an

    average of approximately _______ nodes for deletion

a. (n+1)/2

b.1/(n+1)

c.n/2

d.one

      Ans :  d, page 200 of  Tenenbaum 2^nd edition

34.The advantage of lists over an array for implementing a priority queue is

a.Extra space should be left empty in the end to achieve this

b.Lists will take less time compared to arrays

c.No shifting of elements or gaps are necessary in a list

d.Lists don’t have direct access

         Ans : c, page 200 of  Tenenbaum 2^nd edition

35. An item can be inserted into  ______,without moving any other items

a. List

b. an array if extra space is left empty

c. both a and b

d. none

        Ans : b, page 200 of  Tenenbaum 2^nd edition

36. An extra node at the front of the list, which doesnot represent an item in the list is

Called

a. header node

b. List node

c. List header

d. Both a and c

        Ans : d, page 200 of  Tenenbaum 2^nd edition

     37) A __________is a self-referential data type because it contains a pointer or link to another data of the same type.  

1. Stack
2. Linked list
3. Queue
4. Priority queue

         Ans) B

       Exp)   A Linked list is a self-referential data type because it contains a pointer or link to another data of the same type.

For more refer to http://en.wikipedia.org/wiki/Linked_list

38) Linked lists, at any point in the list in constant time, does  not allow __________.

1. Random access.
2. Insertion
3. Deletion
4. Insertion at end

Ans)A

Exp) Linked lists permit insertion and removal of nodes at any point in the list in constant time, but do not allow random access.For more refer to http://en.wikipedia.org/wiki/Linked_list

39) __________ permits insertion and removal of nodes at any point in the list in constant time, but do not allow random access

1. Stack
2. Linked list
3. Queue
4. Priority queue

Ans)B

Exp) Linked lists permit insertion and removal of nodes at any point in the list in constant time, but do not allow random access.For more refer to http://en.wikipedia.org/wiki/Linked_list

 40) To traverse a___________, you begin at any node and follow the list in either            direction until you return to the original node. 

1. Doubly linked list
2. Two way linked list
3. Circular linked list
4. Singly linked list

Ans) C

You begin at any node and follow the list in either direction until you return to the original node, to traverse a circular linked list. Doubly linked lists and two way linked lists are the same. For more refer to http://en.wikipedia.org/wiki/Linked_list

41) The pointer, in case of a circular linked list, pointing to the whole list is usually called the___________.

1. Double pointer
2. List pointer
3. Circular pointer
4. End pointer

Ans )D

The pointer, in case of a circular linked list, pointing to the whole list is usually called the end pointer. For more refer to http://en.wikipedia.org/wiki/Linked_list

42) In a ______________, each node has one link, similarly to an ordinary singly-linked list, except that the next link of the last node points back to the first node.

1. Doubly linked list
2. Singly-circularly-linked list
3. Doubly circular linked list
4. Two way linked list

Ans) B

Each node has one link, similarly to an ordinary singly-linked list, except that the next link of the last node points back to the first node, in a singly circularly linked list. For more refer to http://en.wikipedia.org/wiki/Linked_list

43) In a______________, each node has two links, similarly to doubly-linked list, except that previous link of the first node points to the last node and the next link of the last node points to the first node.

1. Doubly-circularly-linked list
2. Doubly linked list
3. Singly-circularly-linked list
4. Two way linked list

Ans)  A

Each node has two links, similarly to doubly-linked list, except that previous link of the first node points to the last node and the next link of the last node points to the first node

in a doubly-circularly-linked list. For more refer to http://en.wikipedia.org/wiki/Linked_list

44) In a __________, insertions and removals can be done at any point with access to any nearby node.

1. Doubly-circularly-linked list
2. Doubly linked list
3. Singly-circularly-linked list
4. Two way linked list

Ans) B

For more refer to http://en.wikipedia.org/wiki/Linked_list

45) _______________are most useful for describing naturally circular structures, and have the advantage of regular structure and being able to traverse the list starting at any point.

1. Doubly linked list
2. Two way linked list
3. Singly linked list
4. Circular linked list

Ans) D

46)Which of the following operations is not efficiently supported by a singly-linked list?

a. Accessing the element in the current position

b. Insertion after the current position

c. Insertion before the current position

d. Moving to the position immediately following the current position

e. All of the above are efficiently supported

Ans.: c, To insert before the current position another pointer has to be made to point to the position before the current position.

47) The header node of a linked list

(a) Simplifies deletion

(b) Simplifies insertion

(c) Points to null

(d) Both (a), (b)

Ans) D

48) If a header node is used, which of the following indicates a list L with one item?

(a) L.Header.Next = null

(b) L.Header.Next /= null

(c) L.Header.Next /= null and then L.Header.Next.Next /= null

(d) L.Header.Next /= null and then L.Header.Next.Next = null

(e) None of the above

Ans)D

49) Insertion of a node into a doubly linked list requires how many changes to various Next and Prev pointers?

(a) No changes

(b) 1 Next, 1 Prev

(c) 2 Next, 2 Prev

(d) 3 Next, 3 Prev

(e) None of the above

Ans)C

50)What operation is supported in constant time by the doubly linked list, but not by the singly linked list?

(a) Advance

(b) Move back

(c) First

(d) Retrieve

(e) All of the above are always constant time

Ans)B, Doubly linked list has two pointers pointing to forward and backward Simultaneously

51) Consider the following statements.

(i) A linked list consists of a series of structures, which are necessarily adjacent in memory.

(ii) In a singly linked list, each structure contains an element and a reference to a record containing its successor.

(iii) In an array-based list, even if the array is dynamically allocated, an estimate of the maximum size of the list is required.

(iv) In an array based list, inserting at position 0 requires first pushing the entire array down one spot to make room.

(v) In an array-based list, deleting elements from the middle can be performed without shifting the remaining elements.

Which of the above statements is/are valid for a list?

1. (ii) & (iv) only
2. (ii), (iii) & (iv) only
3. (iii), (iv) & (v) only
4. (ii) & (iv) only
5. (ii), (iii), (iv) & (v) only

Ans) B

52)Consider the following operations.

(i) Append an element to the end of a list.

(ii) Concatenate two lists.

(iii) Free all the nodes in a list.

(iv)Reverse a list, so that the last element becomes the first and so-on.

(v) Delete the last element from a list.

(vi)Delete the nth element from a list with at least n elements.

(vii) Combine two ordered lists into a single ordered list.

Which of the above are valid operations in singly linked lists?

1. (i), (ii), (iii), (v), (vi) & (vii)
2. (iii), (iv), (v), (vi) & (vii)
3. (i), (ii), (iii), (iv), (vi) & (vii)
4. (i), (ii), (iii), (iv) & (vii)
5. (i), (ii), (iii), (iv), (v), (vi) & (vii)

Ans) E

53) Consider the following algorithm.

(i) An empty node is created.

(ii) The node’s information field is initialized to an integer e1.

(iii) The node is being included at the end of the list, and the next field is set to null.

(iv) The node is now included in the list by making the next field of the last node of the list a reference to the newly created node.

(v) The new node follows all the nodes of the list, but this fact has to be reflected in the value of the tail, which now becomes the reference to the new node.

Which of the following does the above algorithm describe?

1. The process of adding a new node to the last node of the tree
2. The process of adding a new node to any location of the list
3. The process of adding a new node to the end of the list
4. The process of deleting a node from the end of the list
5. The process of deleting a node from the beginning of the list

Ans) C