BASIC CONCEPTS

TRUE/FALSE


1. AN INSTANCE IS A PROBLEM WITH VALUES ASSIGNED TO PARAMETERS.
   ANSWER TO QUESTION 1
   
   
2. THE "PRE-CONDITION" IS A CONDITION THAT MUST BE TESTED BEFORE EACH ITERATION OF THE LOOP.
   ANSWER TO QUESTION 2
   
   
3. BOTH STACK AND QUEUE REMOVE AN ELEMENT FROM TOP (FIRST) POSITION.
   ANSWER TO QUESTION 3
   
   
4. REHASHING IS A COLLISION RESOLUTION MECHANISM USING THE SEPARATE CHAINING APPROACH.
   ANSWER TO QUESTION 4
   
   
5. A DOUBLY-LINKED LIST USES TWO REFERENCES: FIRST AND LAST, TO POINT TO THE FIRST AND LAST ELEMENT IN THE LIST.
   ANSWER TO QUESTION 5
   
   

1. All the three basic sorting algorithms (bubble sort, insertion sort, and selection sort) run in the order of ___ time.
   1. 0(1)
   2. 0(N)
   3. 0(N, logN)
   4. 0(N²)
      
      ANSWER TO QUESTION 1

2. Which of the folloing sorting methods require the most memory space?
   1. bubble sort
   2. shell sort
   3. quick sort
   4. merge sort
      
      ANSWER TO QUESTION 2

3. Which of the folloing sorting methods require the most efficient time?
   1. shell sort
   2. quick sort
   3. insertion sort
   4. bubble sort
      
      ANSWER TO QUESTION 3

4. The purpose of using a balanced tree is to
   1. reduce the number of nodes
   2. improve the search efficiency
   3. reduce the insertion and deletion time
   4. cut down the memory space for nodes
      
      ANSWER TO QUESTION 4

5. Which of the following tree(s) is(are) commonly used for external data that are stored in a file to provide fast search, insertion, and deletion time?
   1. RedBlack Tree (RB Tree)
   2. 2-3-4 Tree
   3. B-Tree
   4. All of the above
      
      ANSWER TO QUESTION 5

6. Which of the following is part of red-black rules that ensure the balance of a RB tree?
   1. If a node is black, its children must be red.
   2. The roof must always be red.
   3. Every path from the root to a leaf,or to a null child, must contain the same number of black nodes.
   4. The parent and child nodes must have a different color.
      
      ANSWER TO QUESTION 6

7. In a 2-3-4 tree, each node can contain ___ keys.
   1. 0,1,2 or 3
   2. 1,2,3, or 4
   3. 2,3, or 4
   4. 1,2, or 3
      
      ANSWER TO QUESTION 7

8. A full binary tree with height K contains how many nodes?
   1. 2^K
   2. 2^K-1
   3. 2^K+1-1
   4. 2^K-1-1
      
      ANSWER TO QUESTION 8

9. If a fully connected graph contains N vertices, then it should have ___ edges.
   1. N
   2. N-1
   3. N*N/2
   4. N*(N-1)/2
      
      ANSWER TO QUESTION 9

10. A topologic sorting can be carried out only on a ___, ___ graph.
    1. undirected, cyclic
    2. undirected, acyclic
    3. directed, cyclic
    4. directed, acyclic
       
       ANSWER TO QUESTION 10

11. The depth-first search uses a ___ to remember where it should go when it reaches a dead end.
    1. stack
    2. queue
    3. priority queue
    4. linked list
       
       ANSWER TO QUESTION 11

12. Which of the following features in ADT provides data security?
    1. abstraction
    2. encapsulation
    3. separation of data from code
    4. none of the above
       
       ANSWER TO QUESTION 12

13. An ADT specification must specify the following two kinds of information.
    1. instance and operation
    2. data type and data content
    3. problem and algorithm
    4. time and space
       
       ANSWER TO QUESTION 13

14. In the set of (key, value) pairs for a hash table, which component(s) must be unique?
    1. key
    2. value
    3. both key and value
    4. neither key nor value
       
       ANSWER TO QUESTION 14

15. A minimum spanning tree for a weighted graph best represents
    1. the minimum number of edges necessary to connect all the vertices in the graph.
    2. the shortest (or cheapest) distance from one vertex to another.
    3. the smallest set of edges that have value smaller than a given minimum weight.
    4. none of the above
       
       ANSWER TO QUESTION 15