CSD-Full – comprehensive Communication Sciences and Disorders study guide and exam
preparation material
ace - ANS ✔✔(Choose 3 :)
Which of sentences about singly linked list are true:
A. Deleting a node at the beginning of the list takes constant time `O ( 1 )`.
B. Deleting last node of the list always takes `O ( lgn )` time.
C. On the average, delete operation executes O ( n ) steps.
D. Search operation takes O ( n ) time in the best case.
E. There is no immediate access to the predecessor of any node in list.
ac - ANS ✔✔(Choose 2 :)
Select correct statement(s) about Doubly Linked List:
A. Deleting a node at the end of the list takes constant time O( 1 ).
B. Inserting a new node at the end of the list requires O( n ) steps.
C. The node which is deleted from the list will be claimed by the garbage collector.
D. Methods for processing doubly linked list are simpler than those of singly linked list.
b - ANS ✔✔Select incorrect statement about skip list:
A. In a skip list of n nodes, for each k and i such that 1 ≤ k ≤ `|__lgn__|` and 1 ≤ i ≤ `|__n/2^(k-
1)__|` - 1, the node in position `2^(k-1)` • i points to the node in position `2^(k-1)` • (i + 1)
B. The number of reference fields indicates the level of each node, and the number of levels is
maxLevel = `[lgn]`+ 1
,C. All of the others.
D. None of the others.
ce - ANS ✔✔(Choose 2)
Select incorrect statement about skip list:
A. Searching is efficient.
B. Insertion and Deletion are very inefficient.
C. The search time is O (lgn) in the worst case.
D. `maxLevel` of skip list which has 20 elements is 5
E. In 20-element skip list, the node in position 3 points to the node in position 7
cd - ANS ✔✔(Choose 2)
Select correct statement(s):
A. A linked list is a collection of nodes storing data and links to other nodes
B. A linked structure is a data structure composed of nodes, each node holding some
information
and a reference to another node in the list.
C. A singly linked list is a node that has a link only to its successor in this sequence
,D. Inserting a new node at the end of the singly linked list without tail field requires O( n ) steps.
a - ANS ✔✔Linked lists allow easy insertion and deletion of information because such
operations
have a local impact on the list.
A. True
B. False
cd - ANS ✔✔(Choose 2:)
Which of the following operations take O( 1)time:
A. Deleting one any node in linked list
B. Inserting one node to the end of singly linked list without tail.
C. Deleting one node from the begin of doubly linked list
D. Searching one node in singly linked list without tail in the best case.
bd - ANS ✔✔(Choose 2)
Select correct statements about Linked List:
A. The nodes in doubly linked list contain only references to the predecessors.
B. Skip lists was motivated by the need to speed up the searching process.
, C. In the worst case, search time of skip list is O(lgn)
D. The efficiency of search in singly and doubly linked lists can be improved by dynamically
organizing the list in a certain manner using Self-Ogranizing Lists.
ac - ANS ✔✔(Choose 2)
Which of the following statements about the Stack are true
A. Popping operation in the linked list implementation is executed in the constant time O(1)
B. Clear operation in the linked list implementation is executed in the constant time O(1)
C. Popping operation in the array implementation is executed in the constant time O(1)
D. Pushing operation in the linked list implementation is always executed in the constant time
O(1)
bc - ANS ✔✔(Choose 2)
In the circular array version of the Queue class, which operations require O(n) linear time for
their worst-case behavior
A. dequeue()
B. enqueue() when the capacity has been reached
C. clear()
preparation material
ace - ANS ✔✔(Choose 3 :)
Which of sentences about singly linked list are true:
A. Deleting a node at the beginning of the list takes constant time `O ( 1 )`.
B. Deleting last node of the list always takes `O ( lgn )` time.
C. On the average, delete operation executes O ( n ) steps.
D. Search operation takes O ( n ) time in the best case.
E. There is no immediate access to the predecessor of any node in list.
ac - ANS ✔✔(Choose 2 :)
Select correct statement(s) about Doubly Linked List:
A. Deleting a node at the end of the list takes constant time O( 1 ).
B. Inserting a new node at the end of the list requires O( n ) steps.
C. The node which is deleted from the list will be claimed by the garbage collector.
D. Methods for processing doubly linked list are simpler than those of singly linked list.
b - ANS ✔✔Select incorrect statement about skip list:
A. In a skip list of n nodes, for each k and i such that 1 ≤ k ≤ `|__lgn__|` and 1 ≤ i ≤ `|__n/2^(k-
1)__|` - 1, the node in position `2^(k-1)` • i points to the node in position `2^(k-1)` • (i + 1)
B. The number of reference fields indicates the level of each node, and the number of levels is
maxLevel = `[lgn]`+ 1
,C. All of the others.
D. None of the others.
ce - ANS ✔✔(Choose 2)
Select incorrect statement about skip list:
A. Searching is efficient.
B. Insertion and Deletion are very inefficient.
C. The search time is O (lgn) in the worst case.
D. `maxLevel` of skip list which has 20 elements is 5
E. In 20-element skip list, the node in position 3 points to the node in position 7
cd - ANS ✔✔(Choose 2)
Select correct statement(s):
A. A linked list is a collection of nodes storing data and links to other nodes
B. A linked structure is a data structure composed of nodes, each node holding some
information
and a reference to another node in the list.
C. A singly linked list is a node that has a link only to its successor in this sequence
,D. Inserting a new node at the end of the singly linked list without tail field requires O( n ) steps.
a - ANS ✔✔Linked lists allow easy insertion and deletion of information because such
operations
have a local impact on the list.
A. True
B. False
cd - ANS ✔✔(Choose 2:)
Which of the following operations take O( 1)time:
A. Deleting one any node in linked list
B. Inserting one node to the end of singly linked list without tail.
C. Deleting one node from the begin of doubly linked list
D. Searching one node in singly linked list without tail in the best case.
bd - ANS ✔✔(Choose 2)
Select correct statements about Linked List:
A. The nodes in doubly linked list contain only references to the predecessors.
B. Skip lists was motivated by the need to speed up the searching process.
, C. In the worst case, search time of skip list is O(lgn)
D. The efficiency of search in singly and doubly linked lists can be improved by dynamically
organizing the list in a certain manner using Self-Ogranizing Lists.
ac - ANS ✔✔(Choose 2)
Which of the following statements about the Stack are true
A. Popping operation in the linked list implementation is executed in the constant time O(1)
B. Clear operation in the linked list implementation is executed in the constant time O(1)
C. Popping operation in the array implementation is executed in the constant time O(1)
D. Pushing operation in the linked list implementation is always executed in the constant time
O(1)
bc - ANS ✔✔(Choose 2)
In the circular array version of the Queue class, which operations require O(n) linear time for
their worst-case behavior
A. dequeue()
B. enqueue() when the capacity has been reached
C. clear()
