Skip to ContentGo to accessibility pageKeyboard shortcuts menu
OpenStax Logo
Introduction to Computer Science

Review Questions

Introduction to Computer ScienceReview Questions

Review Questions

1 .
Why did we introduce tree data structures as an alternative to linear data structures?
  1. Some complex data can only be represented with a tree data structure.
  2. Some simple data can only be represented with a tree data structure.
  3. Linear data structures cannot implement sets and maps.
  4. Tree data structures are typically more effective at implementing sets and maps.
2 .
How does the graph abstract data type differ from other abstract data types?
  1. It can model the relationships between elements.
  2. It is more efficient than other abstract data types.
  3. It can solve problems that other abstract data types cannot solve.
  4. It does not specify a particular data structure implementation.
3 .
What abstract data type do binary heaps most commonly implement?
  1. lists
  2. sets
  3. maps
  4. priority queues
4 .
What is one way to describe the relationship between algorithms, problems, and modeling?
  1. Algorithms are the foundation for problem models.
  2. Algorithms solve a model of a problem.
  3. Each algorithm can only be used to solve a single problem.
  4. Each problem can only have a single model.
5 .
At what point do computer scientists apply algorithm design patterns?
  1. when learning canonical algorithms
  2. when modeling a problem
  3. when solving new problems
  4. when analyzing an algorithm
6 .
How does the model of computation relate to the problem model?
  1. The model of computation is synonymous with problem model.
  2. Problem models constrain the model of computation.
  3. The model of computation constrains the problem modeling process.
  4. The model of computation describes a single algorithm for each problem model.
7 .
Why is case analysis important?
  1. Case analysis provides an alternative to asymptotic analysis.
  2. Case analysis focuses on small inputs.
  3. Case analysis simplifies the step-counting by introducing a cost model.
  4. Case analysis considers factors other than the size of the problem.
8 .
What is true about the order of growth of binary search with respect to the size of the sorted list?
  1. In the best case, the order of growth of binary search is constant.
  2. In the best case, the order of growth of binary search is logarithmic.
  3. In the worst case, the order of growth of binary search is constant.
  4. In the worst case, the order of growth of binary search is linear.
9 .
How does time complexity relate to space complexity?
  1. Time complexity measures efficiency according to the size of the problem, while space complexity does not.
  2. Both time and space complexity measure the efficiency of algorithms as they relate to the nature of the problem.
  3. Time complexity focuses on asymptotic analysis while space complexity focuses on experimental analysis.
  4. Both time and space complexity can apply methods from asymptotic analysis and experimental analysis.
10 .
What are the three steps in divide and conquer algorithms?
11 .
Why do many greedy algorithms fail to compute the best solution to a combinatorial problem?
12 .
What are the three steps in reduction algorithms?
13 .
What is quicksort’s algorithm design pattern and algorithmic paradigm?
  1. Quicksort is an application of the binary search tree algorithm design pattern and an example of the divide and conquer algorithmic paradigm.
  2. Quicksort is an application of the binary search tree algorithm design pattern and an example of the brute-force algorithmic paradigm.
  3. Quicksort is an application of the binary search tree algorithm design pattern and an example of the greedy algorithmic paradigm.
  4. Quicksort is an application of the binary search tree algorithm design pattern and an example of the randomized incremental construction algorithmic paradigm.
14 .
What graph problems can breadth-first search solve?
  1. exponential node tree
  2. minimum spanning trees
  3. unweighted shortest paths
  4. weighted shortest paths
15 .
What is a primary drawback of hashing?
  1. There can be collisions as the same element can hash to multiple values.
  2. There can be collisions between multiple elements that hash to the same value.
  3. Hashing is slower than binary search for search problems.
  4. Hashing is faster than binary search for search problems.
16 .
What is the relationship between Turing machines and models of computation?
17 .
What is one of the three key ideas of the Turing machine?
  1. infinite memory by virtualization
  2. a memory bank for storing data
  3. using divide and conquer to always reduce an algorithm to O(n) runtime
  4. using divide and conquer to always reduce an algorithm to O(1) runtime
18 .
What is P versus NP?
  1. P refers to the polynomial time complexity class, whereas NP refers to the nondeterministic polynomial time complexity class.
  2. P refers to any Big O notation past O(N3), whereas NP refers to any Big O notation less than O(N3).
  3. NP is a constant runtime, whereas P is polynomial runtime.
  4. P refers to constant runtime, whereas NP is linear runtime.
PreviousNext
Citation/Attribution

This book may not be used in the training of large language models or otherwise be ingested into large language models or generative AI offerings without OpenStax's permission.

Want to cite, share, or modify this book? This book uses the Creative Commons Attribution License and you must attribute OpenStax.

Attribution information
  • If you are redistributing all or part of this book in a print format, then you must include on every physical page the following attribution:
    Access for free at https://openstax.org/books/introduction-computer-science/pages/1-introduction
  • If you are redistributing all or part of this book in a digital format, then you must include on every digital page view the following attribution:
    Access for free at https://openstax.org/books/introduction-computer-science/pages/1-introduction
Citation information

© Oct 29, 2024 OpenStax. Textbook content produced by OpenStax is licensed under a Creative Commons Attribution License . The OpenStax name, OpenStax logo, OpenStax book covers, OpenStax CNX name, and OpenStax CNX logo are not subject to the Creative Commons license and may not be reproduced without the prior and express written consent of Rice University.