Skip to ContentGo to accessibility page
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
Order a print copy
Citation/Attribution
Reuse and redistribution of this content in digital or print format:
  • 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 prior written permission.
  • This book uses the Creative Commons Attribution-NonCommercial-ShareAlike License, which means that you can reuse and modify the material only for noncommercial purposes, must attribute OpenStax, and must distribute any derivative works under the same license.
  • Any commercial printing of this textbook, including using a local or custom printer, must be approved by OpenStax, and proper citation provided.
  • OpenStax-copyrighted images, activities, assessments, and similar components of this book are subject to the same licensing – CC-BY-NC-SA. They can be used for noncommercial purposes with attribution. Commercial use requires permission.
  • Permission requests: Anyone who intends to incorporate this content (including text, images, and other components) into large language models, use it in AI offerings, use it commercially (including in print), and/or has questions about another use case is welcome to complete our reuse request form.
Attribution information
  • If you are redistributing all or part of this book in a noncommercial 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 noncommercial digital format, then for every page that includes OpenStax content, you must license the derivative work under the same CC-BY-NC-SA license as the original, and 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

The information below includes the information needed to generate citations in most major styles (APA, MLA, etc.); you must reformat and organize the information as needed to fit the requirements of the style. Use the information below to generate a citation. We recommend using a citation tool such as this one.

© Apr 23, 2026 OpenStax. Textbook content produced by OpenStax is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike License. The OpenStax name, OpenStax logo, OpenStax book covers, OpenStax CNX name, and OpenStax CNX logo, and Rice University name, and Rice University logo trademarks, or wordmarks are not subject to the Creative Commons license and may not be reproduced without the prior and express written consent of Rice University.