CSD201 (Cóc Ghẻ)

Nguồn: https://quizlet.com/vn/392905846/csd201-coc-ghe-flash-cards/mpor

B

1. Process of inserting an element in stack is called \____________
a) Create
b) Push
c) Evaluation
d) Pop

D

2. Process of removing an element from stack is called \__________
a) Create
b) Push
c) Evaluation
d) Pod

A

3. In a stack, if a user tries to remove an element from empty stack it is called \_________
a) Underflow
b) Empty collection
c) Overflow
d) Garbage Collection

A

4. Pushing an element into stack already having five elements and stack size of 5 , then stack becomes
a) Overflow
b) Crash
c) Underflow
d) User flow

D

5. Entries in a stack are "ordered". What is the meaning of this statement?
a) A collection of stacks is sortable
b) Stack entries may be compared with the '

D

6. Which of the following applications may use a stack?
a) A parentheses balancing program
b) Tracking of local variables at run time
c) Compiler Syntax Analyzer
d) All of the mentioned

C

C7. Consider the usual algorithm for determining whether a sequence of parentheses is balanced.
The maximum number of parentheses that appear on the stack AT ANY ONE TIME when the algorithm analyzes: (()(())(())) are:
a) 1
b) 2
c) 3
d) 4 or more

B

8. Consider the usual algorithm for determining whether a sequence of parentheses is balanced.
Suppose that you run the algorithm on a sequence that contains 2 left parentheses and 3 right parentheses (in some order).
The maximum number of parentheses that appear on the stack AT ANY ONE TIME during the computation?
a) 1
b) 2
c) 3
d) 4 or more

D

9. What is the value of the postfix expression 6 3 2 4 + - *:
a) Something between -5 and -15
b) Something between 5 and -5
c) Something between 5 and 15
d) Something between 15 and 100

D

10. Here is an infix expression: 4 + 3*(6*3-12). Suppose that we are using the usual stack algorithm to convert the expression from infix to postfix notation.
The maximum number of symbols that will appear on the stack AT ONE TIME during the conversion of this expression?
a) 1
b) 2
c) 3
d) 4

A

2. The data structure required to check whether an expression contains balanced parenthesis is?
a) Stack
b) Queue
c) Array
d) Tree

B

3. What data structure would you mostly likely see in a non recursive implementation of a recursive algorithm?
a) Linked List
b) Stack
c) Queue
d) Tree

D

4. The process of accessing data stored in a serial access memory is similar to manipulating data on a \________
a) Heap
b) Binary Tree
c) Array
d) Stack

D

6. Which data structure is needed to convert infix notation to postfix notation?
a) Branch
b) Tree
c) Queue
d) Stack

A

What is the result of the following operation
Top (Push (S, X))
a) X
b) Null
c) S
d) None of the mentioned

B

10. Which data structure is used for implementing recursion?
a) Queue
b) Stack
c) Array
d) List

C

4. Which of the following statement(s) about stack data structure is/are NOT correct?
a) Linked List are used for implementing Stacks
b) Top of the Stack always contain the new node
c) Stack is the FIFO data structure
d) Null link is present in the last node at the bottom of the stack

D

6. Which of the following is not an inherent application of stack?
a) Reversing a string
b) Evaluation of postfix expression
c) Implementation of recursion
d) Job scheduling

C

7. The type of expression in which operator succeeds its operands is?
a) Infix Expression
b) Prefix Expression
c) Postfix Expression
d) None of the mentioned

B

9. If the elements "A", "B", "C" and "D" are placed in a stack and are deleted one at a time, what is the order of removal?
a) ABCD
b) DCBA
c) DCAB
d) ABDC

A

1. A linear list of elements in which deletion can be done from one end (front) and insertion can take place only at the other end (rear) is known as a ?
a) Queue
b) Stack
c) Tree
d) Linked list

C

2. The data structure required for Breadth First Traversal on a graph is?
a) Stack
b) Array
c) Queue
d) Tree

A

3. A queue is a ?
a) FIFO (First In First Out) list
b) LIFO (Last In First Out) list
c) Ordered array
d) Linear tree

B

4. In Breadth First Search of Graph, which of the following data structure is used?
a) Stack
b) Queue
c) Linked list
d) None of the mentioned

A

5. If the elements "A", "B", "C" and "D" are placed in a queue and are deleted one at a time, in what order will they be removed?
a) ABCD
b) DCBA
c) DCAB
d) ABDC

C

6. A data structure in which elements can be inserted or deleted at/from both the ends but not in the middle is?
a) Queue
b) Circular queue
c) Dequeue
d) Priority queue

A

7. A normal queue, if implemented using an array of size MAX_SIZE, gets full when
a) Rear \= MAX_SIZE - 1
b) Front \= (rear + 1)mod MAX_SIZE
c) Front \= rear + 1
d) Rear \= front

C

8. Queues serve major role in
a) Simulation of recursion
b) Simulation of arbitrary linked list
c) Simulation of limited resource allocation
d) All of the mentioned

B

9. Which of the following is not the type of queue?
a) Ordinary queue
b) Single ended queue
c) Circular queue
d) Priority queue

A

1. A linear collection of data elements where the linear node is given by means of pointer is called?
a) Linked list
b) Node list
c) Primitive list
d) None of the mentioned

B

2. Consider an implementation of unsorted singly linked list. Suppose it has its representation with a head pointer only.
Given the representation, which of the following operation can be implemented in O(1) time?
i) Insertion at the front of the linked list
ii) Insertion at the end of the linked list
iii) Deletion of the front node of the linked list
iv) Deletion of the last node of the linked list
a) I and II
b) I and III
c) I, II and III
d) I, II and IV

C

3. In linked list each node contain minimum of two fields. One field is data field to store the data second field is?
a) Pointer to character
b) Pointer to integer
c) Pointer to node
d) Node

C

4. What would be the asymptotic time complexity to add a node at the end of singly linked list, if the pointer is initially pointing to the head of the list?
a) O(1)
b) O(n)
c) θ(n)
d) θ(1)

B

5. What would be the asymptotic time complexity to add an element in the linked list?
a) O(1)
b) O(n)
c) O(n2)
d) None of the mentioned

B

6. What would be the asymptotic time complexity to find an element in the linked list?
a) O(1)
b) O(n)
c) O(n2)
d) None of the mentioned

A

7. What would be the asymptotic time complexity to insert an element at the second position in the linked list?
a) O(1)
b) O(n)
c) O(n2)
d) None of the mentioned

C

8. The concatenation of two list can performed in O(1) time. Which of the following variation of linked list can be used?
a) Singly linked list
b) Doubly linked list
c) Circular doubly linked list
d) Array implementation of list

D

1. What kind of linked list is best to answer question like "What is the item at position n?"
a) Singly linked list
b) Doubly linked list
c) Circular linked list
d) Array implementation of linked list

D

2. Linked lists are not suitable to for the implementation of?
a) Insertion sort
b) Radix sort
c) Polynomial manipulation
d) Binary search

A

3. Linked list is considered as an example of \___________ type of memory allocation.
a) Dynamic
b) Static
c) Compile time
d) None of the mentioned

B

4. In Linked List implementation, a node carries information regarding
a) Data
b) Link
c) Data and Link
d) None of the mentioned

C

5. Linked list data structure offers considerable saving in
a) Computational Time
b) Space Utilization
c) Space Utilization and Computational Time
d) None of the mentioned

D

6. Which of the following points is/are true about Linked List data structure when it is compared with array
a) Arrays have better cache locality that can make them better in terms of performance
b) It is easy to insert and delete elements in Linked List
c) Random access is not allowed in a typical implementation of Linked Lists
d) All of the mentioned

D

8. Which of the following sorting algorithms can be used to sort a random linked list with minimum time complexity?
a) Insertion Sort
b) Quick Sort
c) Heap Sort
d) Merge Sort

D

5. In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is
a) log 2 n
b) n⁄2
c) log 2 n - 1
d) n

A

6. Given pointer to a node X in a singly linked list. Only one pointer is given, pointer to head node is not given, can we delete the node X from given linked list?
a) Possible if X is not last node
b) Possible if size of linked list is even
c) Possible if size of linked list is odd
d) Possible if X is not first node

C

7. You are given pointers to first and last nodes of a singly linked list, which of the following operations are dependent on the length of the linked list?
a) Delete the first element
b) Insert a new element as a first element
c) Delete the last element of the list
d) Add a new element at the end of the list

D

8. In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is
a) log2 n
b) n⁄2
c) log2 n - 1
d) n

D

1. Which of the following is not a disadvantage to the usage of array?
a) Fixed size
b) You know the size of the array prior to allocation
c) Insertion based on position
d) Accessing elements at specified positions

D

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)

B

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) None of the mentioned

A

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)

D

8. Which of these is an application of linked lists?
a) To implement file systems
b) For separate chaining in hash-tables
c) To implement non-binary trees
d) All of the mentioned

D

1. Which of the following is false about a doubly linked list?
a) We can navigate in both the directions
b) It requires more space than a singly linked list
c) The insertion and deletion of a node take a bit longer
d) None of the mentioned

A

3. What is a memory efficient double linked list?
a) Each node has only one pointer to traverse the list back and forth
b) The list has breakpoints for faster traversal
c) An auxiliary singly linked list acts as a helper list to traverse through the doubly linked list
d) None of the mentioned

B

5. How do you calculate the pointer difference in a memory efficient double linked list?
a) head xor tail
b) pointer to previous node xor pointer to next node
c) pointer to previous node - pointer to next node
d) pointer to next node - pointer to previous node

C

6. What is the time complexity of inserting a node in a doubly linked list?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(1)

C

1. What differentiates a circular linked list from a normal linked list?
a) You cannot have the 'next' pointer point to null in a circular linked list
b) It is faster to traverse the circular linked list
c) You may or may not have the 'next' pointer point to null in a circular linked list
d) All of the mentioned

A

4. What is the time complexity of searching for an element in a circular linked list?
a) O(n)
b) O(nlogn)
c) O(1)
d) None of the mentioned

C

5. Which of the following application makes use of a circular linked list?
a) Undo operation in a text editor
b) Recursive function calls
c) Allocating CPU to resources
d) All of the mentioned

B

9. Which of the following is false about a circular linked list?
a) Every node has a successor
b) Time complexity of inserting a new node at the head of the list is O(1)
c) Time complexity for deleting the last node is O(n)
d) None of the mentioned

B

10. Consider a small circular linked list. How to detect the presence of cycles in this list effectively?
a) Keep one node as head and traverse another temp node till the end to check if its 'next points to head
b) Have fast and slow pointers with the fast pointer advancing two nodes at a time and slow pointer advancing by one node at a time
c) Cannot determine, you have to pre-define if the list contains cycles
d) None of the mentioned

A

1. Which of the following real world scenarios would you associate with a stack data structure?
a) piling up of chairs one above the other
b) people standing in a line to be serviced at a counter
c) offer services based on the priority of the customer
d) all of the mentioned

C

3. What does 'stack underflow' refer to?
a) accessing item from an undefined stack
b) adding items to a full stack
c) removing items from an empty stack
d) index out of bounds exception

A

5. What is the time complexity of pop() operation when the stack is implemented using an array?
a) O(1)
b) O(n)
c) O(logn)
d) O(nlogn)

B

6. Which of the following array position will be occupied by a new element being pushed for a stack of size N elements(capacity of stack \> N).
a) S[N-1].
b) S[N].
c) S[1].
d) S[0].

C

7. What happens when you pop from an empty stack while implementing using the Stack ADT in Java?
a) Undefined error
b) Compiler displays a warning
c) EmptyStackException is thrown
d) NoStackException is thrown

A

9. 'Array implementation of Stack is not dynamic', which of the following statements supports this argument?
a) space allocation for array is fixed and cannot be changed during run-time
b) user unable to give the input for stack operations
c) a runtime exception halts execution
d) all of the mentioned

A

10. Which of the following array element will return the top-of-the-stack-element for a stack of size N elements(capacity of stack \> N).
a) S[N-1].
b) S[N].
c) S[N-2].
d) S[N+1].

A

1. What is the complexity of searching for a particular element in a Singly Linked List?
a) O(n)
b) O(1)
c) logn
d) nlogn

D

2. Which of the following statements are correct with respect to Singly Linked List(SLL) and Doubly Linked List(DLL)?
a) Complexity of Insertion and Deletion at known position is O(n) in SLL and O(1) in DLL
b) SLL uses lesser memory per node than DLL
c) DLL has more searching power than SLL
d) All of the mentioned

B

6. What does 'stack overflow' refer to?
a) accessing item from an undefined stack
b) adding items to a full stack
c) removing items from an empty stack
d) index out of bounds exception

D

9. Which of the following data structures can be used for parentheses matching?
a) n-ary tree
b) queue
c) priority queue
d) stack

C

10. Minimum number of queues to implement stack is \___________
a) 3
b) 4
c) 1
d) 2

B

1. Which of the following properties is associated with a queue?
a) First In Last Out
b) First In First Out
c) Last In First Out
d) None of the mentioned

B

2. In a circular queue, how do you increment the rear end of the queue?
a) rear++
b) (rear+1) % CAPACITY
c) (rear % CAPACITY)+1
d) rear-

A

3. What is the term for inserting into a full queue known as?
a) overflow
b) underflow
c) null pointer exception
d) all of the mentioned

D

4. What is the time complexity of enqueue operation?
a) O(logn)
b) O(nlogn)
c) O(n)
d) O(1)

A

6. What is the need for a circular queue?
a) effective usage of memory
b) easier computations
c) all of the mentioned
d) none of the mentioned

A

9. What is the space complexity of a linear queue having n elements?
a) O(n)
b) O(nlogn)
c) O(logn)
d) O(1)

D

1. In linked list implementation of queue, if only front pointer is maintained, which of the following operation take worst case linear time?
a) Insertion
b) Deletion
c) To empty a queue
d) Both Insertion and To empty a queue

C

2. In linked list implementation of a queue, where does a new element be inserted?
a) At the head of link list
b) At the centre position in the link list
c) At the tail of the link list
d) None of the mentioned

B

3. In linked list implementation of a queue, front and rear pointers are tracked. Which of these pointers will change during an insertion into a NONEMPTY queue?
a) Only front pointer
b) Only rear pointer
c) Both front and rear pointer
d) None of the mentioned

C

4. In linked list implementation of a queue, front and rear pointers are tracked. Which of these pointers will change during an insertion into EMPTY queue?
a) Only front pointer
b) Only rear pointer
c) Both front and rear pointer
d) None of the mentioned

A

5. In case of insertion into a linked queue, a node borrowed from the \__________ list is inserted in the queue.
a) AVAIL
b) FRONT
c) REAR
d) None of the mentioned

A

6. In linked list implementation of a queue, from where is the item deleted?
a) At the head of link list
b) At the centre position in the link list
c) At the tail of the link list
d) None of the mentioned

A

7. In linked list implementation of a queue, the important condition for a queue to be empty is?
a) FRONT is null
b) REAR is null
c) LINK is empty
d) None of the mentioned

B

8. The essential condition which is checked before insertion in a linked queue is?
a) Underflow
b) Overflow
c) Front value
d) Rear value

A

9. The essential condition which is checked before deletion in a linked queue is?
a) Underflow
b) Overflow
c) Front value
d) Rear value

A

10. Which of the following is true about linked list implementation of queue?
a) In push operation, if new nodes are inserted at the beginning of linked list, then in pop operation, nodes must be removed from end
b) In push operation, if new nodes are inserted at the beginning, then in pop operation, nodes must be removed from the beginning
c) In push operation, if new nodes are inserted at the end, then in pop operation, nodes must be removed from end
d) None of the mentioned

D

1. With what data structure can a priority queue be implemented?
a) Array
b) List
c) Heap
d) All of the mentioned

C

2. Which of the following is not an application of priority queue?
a) Huffman codes
b) Interrupt handling in operating system
c) Undo operation in text editors
d) Bayesian spam filter

C

4. What is the time complexity to insert a node based on key in a priority queue?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)

C

6. What is not a disadvantage of priority scheduling in operating systems?
a) A low priority process might have to wait indefinitely for the CPU
b) If the system crashes, the low priority systems may be lost permanently
c) Interrupt handling
d) None of the mentioned

D

7. What are the advantages of priority queues?
a) Easy to implement
b) Processes with different priority can be efficiently handled
c) Applications with differing requirements
d) All of the mentioned

C

8. What is the time complexity to insert a node based on position in a priority queue?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)

A

1. What is a dequeue?
a) A queue with insert/delete defined for both front and rear ends of the queue
b) A queue implemented with a doubly linked list
c) A queue implemented with both singly and doubly linked lists
d) None of the mentioned

D

4. What are the applications of dequeue?
a) A-Steal job scheduling algorithm
b) Can be used as both stack and queue
c) To find the maximum of all sub arrays of size k
d) All of the mentioned

C

7. What is the time complexity of deleting from the rear end of the dequeue implemented with a singly linked list?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)

C

1. Binary trees can have how many children?
a) 2
b) any number of children
c) 0 or 1 or 2
d) 0 or 1