# DAT 305 Week 1 Apply — Wk 1 Quiz https://uopcourse.com/category/dat-305/

**DAT/305**

Data Structures for Problem Solving

**The Latest Version A+ Study Guide**

**************************************************

**DAT 305 Entire Course Link**

**https://uopcourse.com/category/dat-305/**

# DAT 305 Week 1 Apply — Course Pre-Assessment Quiz

# Order the following algorithms in the ascending order of their best-case complexity:

# • Bubble sort

# • Selection sort

# • Quick sort

# • Merge sort

# a. Bubble sort < Quick sort == Merge sort < Selection sort

# b. Selection sort < Quick sort < Merge sort < Bubble sort

# c. Selection sort < Bubble sort < Merge sort < Quick sort

# d. Quick sort < Bubble sort == Merge sort < Selection sort

# Which of the following statements is true for a bubble sort structure?

# a. There are three for loops, all of them separate.

# b. There is a single for loop.

# c. There are two for loops, one nested in the other.

# d. There is a while loop.

# What is the result of the following expression in postfix notation?

# 40 10 / 4 * 20 +

# a. 10

# b. 6

# c. 90

# d. 36

# What will be the output of the following program?

# a. null

# null

# b. value1

# value2

# c. A Runtime Exception will be thrown.

# d. value2

# value2

# What will be the output of the following program?

# a. value1

# b. A NullPointer Exception will be thrown.

# c. value1

# value2

# d. value1

# null

# For the given class, which of the following would be the best hashCode function implementation?

# How many elements can be stored in a binary search tree of depth = 9?

# a. 512

# b. 9

# c. 1023

# d. 256

# Consider the following string: ALAMAKOTA, and pattern to be matched: AKO. By how many positions will the first shift be performed, using the bad character rule?

# a. 2

# b. 1

# c. 3

# d. 4

# What is a graph in which every pair of distinct vertices are connected by a unique edge called?

# a. A cycle graph

# b. A simple graph

# c. A directed cycle graph

# d. A complete graph

# Order the following algorithms by their complexity (ascending):

# 1. Dijkstra’s algorithm

# 2. Warshall’s algorithm

# 3. Bellman-Ford algorithm

# 4. Prim’s algorithm

# a. 2 > 1 > 3 > 4

# b. 2 == 3 > 1 > 4

# c. 4 > 1 > 3 > 2

# d. 2 > 3 > 1 > 4

# The given definition describes which of the following terms?

# A graph without self-loop and parallel edges in it.

# a. A simple graph

# b. A weighted graph

# c. A directed graph

# d. An undirected graph

# Where is the following data entity used?

# a. Graph

# b. Linked list

# c. Double linked list

# d. Binary search tree

# Which data structure has a O(1) constant time operation?

# a. Stack

# b. Binary search tree

# c. Priority queue

# d. Array

# Identify the algorithm used in the following code. What is its Big-O?

# a. Quick sort, O(n log n)

# b. Merge sort, O(n log n)

# c. Bubble sort, O(n²)

# d. Insertion sort, O(n²)

# Which algorithm is used to solve the halting problem?

# a. None

# b. Prim’s algorithm

# c. Dijkstra’s algorithm

# d. Ford-Fulkerson algorithm

# What is the worst-case and best-case Big-O for a P-complete problem?

# a. O(n²) and O(n)

# b. O(k^n) and O(n!)

# c. O(n!) and O(1)

# d. O(n^n) and O(n!)

# Convert the following postfix expression to infix.

# abc++

# a. (a + b + c)

# b. a + b + c

# c. (a + (b + c))

# d. (a + b) + c

# Which of the following shows the merge sort algorithm sorting the array [41 29 7]?

# a. [41 29 7] -> [41 29][7] -> [41][29][7] -> [7 29 41]

# b. [41 29 7] -> [41 29][7] -> [29 41 7] -> [7 41 29] -> [7 29 41]

# c. [41 29 7] -> [29 41 7] -> [7 29 41]

# d. [41 29 7] -> [41 29][7] -> [41][29][7] -> [7 29][41] -> [7 29 41]

# The following algorithm takes an input array and the output array has duplicate elements removed. What is the Big-O of this algorithm?

# a. O(n log n)

# b. O(n)

# c. O(n!)

# d. O(n²)

# Which of the following is an important operation to maintain the property of O(log n) search for a binary search tree?

# a. Rehash the elements into the BST

# b. Delete duplicate elements in the BST

# c. Sort the elements in the BST

# d. Rebalance the BST after an insert

# What is the Big-O of a recursive bubble sort?

# a. O(n³)

# b. O(n log n)

# c. O(n)

# d. O(n²)

# How many times is the swap function called in the insertion sort algorithm?

# a. O(n log n)

# b. O(n!)

# c. O(n)

# d. O(n²)

# What is the data structure used in the following code?

# a. Single-linked list

# b. Double-linked list

# c. Priority queue

# d. Binary search tree

# If the letters ‘A’, ‘B’, ‘C’, and ‘D’ are inserted into a queue, in what order are they removed?

# a. DBCA

# b. ABCD

# c. BACD

# d. DCBA

# For a hash table with five slots, and using chaining to resolve collisions what does the inserted sequence: 35, 2, 18, 6, 3, 10, 8, 5 look like in the hash table for the hash function h(x) = x % 5?

# a. [ (5, 10, 35) , (2,6) , (3,8) , () ]

# b. [ (3), (5,6), (8, 10), (35) ]

# c. [ (35, 10, 5) , (6), (2), (3,8) , () ]

# d. [ (3, 5, 6), (10), (35), () ]

# What is the Big-O for the following function?

# a. O(n)

# b. O(n log n)

# c. O(n³)

# d. O(n²)

# DAT 305 Week 1 Practice — Lab Simulations

Using the MindTap Access link,** complete** the following Lab Activities found in the Practice section of the Wk 1: Algorithms and Complexities folder:

· Lab Activity 1.1: Writing an Algorithm to Convert Numbers from Octal to Decimal MindTap

· Lab Activity 1.2.A: Developing a Timing Table Using the Exponential Algorithm MindTap

· Lab Activity 1.2.B: Converting Expressions to Big O Notations MindTap

· Lab Activity 1.3: Developing a Faster Intersection Algorithm

*Note:* You will receive points for completion and not for performance.

# DAT 305 Week 1 Lab Assessment 1: Algorithms and Complexities

Using the MindTap Access link,** complete** the Wk 1 Lab Assessment 1: Algorithms and Complexities found in the Apply section of the Wk 1: Algorithms and Complexities folder.

*Note: *You have 3 attempts to complete the assessment. A final score will be awarded.

# DAT 305 Week 1 Apply — Wk 1 Quiz

# Out of the following list, which runtime complexity scales the worst?

# a. O(n2)

# b. O(log n)

# c. O(1)

# d. O(n)

# What is the runtime complexity of the following code?

# a. O(n)

# b. O(1)

# c. O(n log n)

# d. O(10n)

# The binary search algorithm has a big O of which of the following?

# a. O(n log n)

# b. O(2n)

# c. O(log n)

# d. O(1)

# If we developed an algorithm that performs 5 + 2 log n + n operations, we can say that the algorithm has a complexity of which of the following?

# a. O(n)

# b. O(5)

# c. O(n2)

# d. O(log n)

# DAT 305 Week 2 Practice — Lab Simulations

Using the MindTap Access link,** complete** the following Lab Activities found in the Practice section of the Wk 2: Sorting Algorithms and Fundamental Data Structures folder:

· Lab Activity 2.1: I Lab Activity 2.4.B: Selection Sort in Java

· Lab Activity 2.2: Understanding the Partitioning Method

· Lab Activity 2.3: Implementing Merge Sort in Java

· Lab Activity 2.4.A: Traversing the Linked List

· Lab Activity 2.4.B: Evaluating the Postfix Expression

# DAT 305 Week 2 Lab Assessment 2: Sorting Algorithms and Fundamental Data Structures

Using the MindTap Access link,** complete** the Wk 2 Lab Assessment 2: Sorting Algorithms and Fundamental Data Structures found in the Apply section of the Wk 2: Sorting Algorithms and Fundamental Data Structures folder.

# DAT 305 Week 2 Apply — Wk 2 Quiz

# Which of the following describes the worst performance of merge sort?

# a. O(n log n)

# b. O(log n)

# c. O(n)

# d. O(n2)

# If after partitioning the pivot always ends up in the middle, which of the following will be the performance of quicksort?

# a. O(n2)

# b. O(log n)

# c. O(n)

# d. O(n log n)

# Which of the following describes the ordering of a stack?

# a. First in first out

# b. Last in last out

# c. Last in first out

# d. First in second out

# Which of the following statements is true for a doubly linked list?

# a. It has at least two pointers in each node

# b. It has a backup of the data

# c. It has twice the number of nodes as a normal linked listed

# d. It stores the elements in a sorted manner

# Which of the following is a formula to search for an item in a linked list?

# a. O(n)

# b. O(2n)

# c. O(log n)

# d. O(1)

# Which of the following is an advantage of implementing a queue using an array?

# a. It prioritizes the elements in the queue

# b. It does not have to keep a head and a tail pointer

# c. It is more efficient if the exact size of the input is known upfront

# d. It is not restricted by a static size

# DAT 305 Week 3 Practice — Lab Simulations

Using the MindTap Access link,** complete** the following Lab Activities found in the Practice section of the Wk 3: Hash Tables, Binary Search Trees and Algorithm Design Paradigms folder:

· Lab Activity 3.1: Implementing Open Addressing

· Lab Activity 3.2.A: Implementing BFS in Java

· Lab Activity 3.2.B: Retrieving the Successor of an Element When the Tree is Traversed in Inorder

· Lab Activity 4.2: Solving the Maximum Subarray Problem

· Lab Activity 4.3: The Coin Change Problem

# DAT 305 Week 3 Lab Assessment 3: Hash Tables and Binary Search Trees

Using the MindTap Access link,** complete** the following assessments in the Apply section of the Wk 3: Hash Tables, Binary Search Trees and Algorithm Design Paradigms folder:

· Wk 3 Lab Assessment 3: HashTables and Binary Search Trees

· Wk 3 Lab Assessment 4: Algorithm Design Paradigms

**DAT 305 Week 3 Lab Assessment 4 Algorithm Design Paradigms**

Using the MindTap Access link,** complete** the following assessments in the Apply section of the Wk 3: Hash Tables, Binary Search Trees and Algorithm Design Paradigms folder:

· Wk 3 Lab Assessment 3: HashTables and Binary Search Trees

· Wk 3 Lab Assessment 4: Algorithm Design Paradigms

# DAT 305 Week 3 Apply — Wk 3 Quiz

Using the MindTap Access link,** complete** the** **Wk 3 Quiz in the Apply section of the Wk 3: Hash Tables, Binary Search Trees and Algorithm Design Paradigms.

# DAT 305 Week 4 Practice — Lab Simulations

Using the MindTap Access link,** complete** the following Lab Activity found in the Practice section of the Wk 4: String Matching Algorithms folder:

· Lab Activity Lab Activity 5.2:Implementing the Bad Character Rule

# DAT 305 Week 4 Lab Assessment 5: String Matching Algorithms

# Using the MindTap Access link, complete the Module Wk 4 Lab Assessment 5: String Matching Algorithms in the Apply section of the Wk 4: String Matching Algorithms folder.

# DAT 305 Week 4 Apply — Wk 4 Quiz

# If the length of the array P is 4 and the length of the array T is 14, how many shifts of P need to be performed in the string searching algorithm?

# a. 9

# b. 10

# c. 11

# d. 12

# What is the best case for the naive string search algorithm?

# a. The first character of the pattern P isn’t present in text T

# b. All characters in pattern P are different

# c. All characters in text T are different

# d. Pattern P is half the size of text T

# What is the worst case for the naive string search algorithm?

# a. All characters of the pattern P are present in text T

# b. All characters of the pattern P and text T are the same

# c. Pattern P is of size one

# d. Text T is composed of pattern P concatenated N times

# How many borders does the string BABBAB have?

# a. 0

# b. 1

# c. 2

# d. 3

# Using the good suffix rule, if we have pattern P = “BABCABCAB” and we found a mismatch of T[i] with P[6], which index of P should we look into aligning with T[i]?

# a. 0

# b. 1

# c. 3

# d. 5

# Using only the bad character rule, how many shifts are performed when trying to find P = BAB in T = BACBABCAB?

# a. 2

# b. 3

# c. 5

# d. 8

# Which string matching algorithms are better suited (or can be extended to be better suited) to work with a set of patterns (check all that apply)?

# a. Boyer-Moore

# b. Aho-Corasick

# c. Knuth-Morris-Pratt

# d. Rabin-Karp

# Which algorithms (in the implementations described in the course) can achieve a worst–case matching time of O(n) (check all that apply)?

# a. Knuth-Morris-Pratt

# b. Aho-Corasick

# c. Boyer-Moore

# d. Rabin-Karp

# DAT 305 Week 5 Practice — Lab Simulations

Using the MindTap Access link,** complete** the following Lab Activities found in the Practice section of the Wk 5: Graphs, Prime Numbers, and Complexity Classes folder:

· Lab Activity 6.1: Building the Adjacency Matrix Representation of a Weighted Undirected Graph

· Lab Activity 6.2: Using BFS to Find the Shortest Path Out of a Maze

· Lab Activity 6.3: Improving Floyd-Warshall’s Algorithm to Reconstruct the Shortest Path

# DAT 305 Week 5 Apply — Course Post-Assessment Quiz

# Which of the following statements is true?

# Removing an element from a linked list is faster than adding an element to a linked list.

# Traversing a linked list has the same complexity as removing an element from a list.

# Traversing a linked list has the same complexity as adding an element to a list.

# Removing and adding an element to a linked list has the same complexity as a traversing operation.

# a. 2 and 4

# b. 4

# c. 1

# d. 1 and 3

# What is the maximum number of comparisons that can take place in bubble sort? Assume that there are n elements in the array.

# a. (1/2)n(n-1)

# b. (1/2)(n-1)

# c. (1/4)(n-1)

# d. (1/4)n(n-1)

# What will be the output of the following program?

# a. value1

# value2

# b. A Runtime Exception will be thrown.

# c. null

# null

# d. value2

# value2

# What will be the output of the following program?

# a. null

# null

# b. value1

# value2

# c. A Runtime Exception will be thrown.

# d. value2

# value2

# What will be the output of the following program?

# a. A NullPointer Exception will be thrown.

# b. value1

# value2

# c. value1

# d. value1

# null

# Which of the following is an advantage of chained hash table (external hashing) over the open addressing scheme?

# a. Deletion is easier.

# b. Space utilization is less.

# c. The worst-case complexity of search operations is less.

# d. None of the above.

# The given definition describes which of the following terms?

# Search or exhaustive search, also known as generate and test, is a very general problem-solving technique and algorithmic paradigm that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem’s statement.

# a. Brute-Force

# b. Dynamic programming

# c. Greedy algorithm

# d. Divide and conquer

# Consider the following string: KOTMAALE, and pattern to be matched: AALE. By how many positions will the first shift be performed, using the bad character and good prefix rules?

# a. 2

# b. 4

# c. 1

# d. 3

# What is a graph without self loops and parallel edges called?

# a. A directed cycle graph

# b. A cycle graph

# c. A complete graph

# d. A simple graph

# Which of the following are the worst-case running times of insertion sort, merge sort, and quick sort respectively?

# a. O(nlog(n)), O(nlog(n)), and O(n²)

# b. O(n²), O(n log(n)), and O(n log(n))

# c. O(n²), O(n log n), and O(n²)

# d. O(n²), O(n²), and O(n log(n))

# What is the knapsack value for the given input?

# value = [ 20, 5, 10, 40, 15, 25 ]

# weight = [1, 2, 3, 8, 7, 4 ]

# W = 10

# a. 60

# b. 35

# c. 115

# d. 40

# Which of the following algorithms is a greedy algorithm?

# Merge sort

# Quick sort

# Insertion sort

# Bubble sort

# a. Merge sort and quick sort

# b. Insertion sort and bubble sort

# c. Quick sort and insertion sort

# d. None

# What data structure is a prime number used with?

# a. Hash table

# b. Stack

# c. Array

# d. Queue

# For the starting permutation [3, 57, 64, 54, 1, 35, 98], what are the steps to bubble sort into a sorted arrangement of [1, 3, 35, 54, 57, 64, 98]?

# a. [1, 3, 35, 54, 57, 64, 98] -> [3, 54, 1, 35, 57, 64, 98] -> [3, 57, 64, 54, 1, 35, 98] -> [3, 1, 35, 54, 57, 64, 98] -> [1, 3, 35, 54, 57, 64, 98] -> [3, 57, 54, 1, 35, 64, 98] -> [1, 3, 35, 54, 57, 64, 98]

# b. [3, 1, 35, 54, 57, 64, 98] -> [1, 3, 35, 54, 57, 64, 98] -> [1, 3, 35, 54, 57, 64, 98] -> [3, 57, 64, 54, 1, 35, 98] -> [3, 57, 54, 1, 35, 64, 98] -> [3, 54, 1, 35, 57, 64, 98]

# c. [3, 57, 64, 54, 1, 35, 98] -> [3, 57, 54, 1, 35, 64, 98] -> [3, 54, 1, 35, 57, 64, 98] -> [3, 1, 35, 54, 57, 64, 98] -> [1, 3, 35, 54, 57, 64, 98] -> [1, 3, 35, 54, 57, 64, 98]

# d. [1, 3, 35, 54, 57, 64, 98] -> [3, 57, 64, 54, 1, 35, 98] -> [3, 1, 35, 54, 57, 64, 98] -> [1, 3, 35, 54, 57, 64, 98] -> [3, 57, 54, 1, 35, 64, 98] -> [3, 54, 1, 35, 57, 64, 98]

# How is prime factorization a hard problem?

# a. Multiplying prime numbers is difficult

# b. Finding the prime factors multiplied for a number is hard

# c. Prime factorization uses division

# d. Prime factorization is NP-complete

# When do we use an adjacency list?

# a. For a hash table

# b. For a graph that is undirected

# c. When sorting a list

# d. When searching through a list for an element

# Which data structure is used to convert an infix expression to prefix or postfix?

# a. Linked list

# b. Priority queue

# c. Hash table

# d. Stack

# Which algorithm sorts the following list [5 3 9 7] using the steps of: [5 3 9 7] -> [3 5 9 7] -> [3 5 9 7] -> [3 5 7 9] -> [3 5 7 9]?

# a. Bubble sort

# b. Insertion sort

# c. Binary search

# d. Merge sort

# What is the Big-O for an algorithm that takes two arrays of equal size n, and returns true if the arrays are disjoint — no elements in common — by taking an element from the first array and then checking if it is in the second array?

# a. O(n²)

# b. O(2^n)

# c. O(n!)

# d. O(n³)

# For the array [ 99 3 57 93 8 9 7 71 1 ], what is the array arrangement after the first step in the insertion sort?

# a. [ 3 99 57 93 8 9 7 71 1 ]

# b. [ 57 3 99 93 8 9 7 71 1 ]

# c. [ 99 3 57 93 8 9 7 71 1 ]

# d. [ 1 3 57 93 8 9 7 71 99 ]

# What do Prim’s algorithm and Kruskal’s algorithm do after they take a graph?

# a. Remove all cycles or loops from the graph

# b. Find the average weight of the edges

# c. Create a shortest path from the graph

# d. Construct a minimum spanning tree

# What is the worst-case performance of the merge sort algorithm on a sorted list of elements?

# a. O(n)

# b. O(n log n)

# c. O(n²)

# d. O(n³)

# What is the algorithm used in the following code?

# a. Graph

# b. Recursive

# c. Greedy

# d. Dynamic programming

# For the string text “The cat in the hat is fat on the mat now!” and the search pattern “dog” along with a performance operation of O(1), what is the search time using the Boyer-Moore algorithm?

# a. O(45)

# b. O(9)

# c. O(42)

# d. O(126)

# What is represented by O(n) to Ω(n) to Θ(n)?

# a. Measures of linear algorithm performance

# b. Results of computing recurrence relations

# c. Asymptotically tighter bounds on algorithm performance

# d. Different functions for the hash table’s hash function

# DAT 305 Week 5 Apply — Wk 5 Quiz

# Given the previous Java implementation of an adjacency list representation of a directed graph, what is the runtime complexity of computing the out-degree of every vertex?

# a. O(V2)

# b. O(V*E)

# c. O(V + E)

# d. O(V)

# Given the previous Java implementation of an adjacency list representation of a directed graph, what is the runtime complexity of computing the in-degree of every vertex?

# a. O(V2)

# b. O(V*E)

# c. O(V + E)

# d. O(V)

# Given the previous Java implementation of an adjacency matrix representation of a directed graph, what is the runtime complexity of counting the number of edges of the graph?

# a. O(V + E)

# b. O(V2)

# c. O(V)

# d. O(V*E)

# A vertex u of a directed graph can end up in a depth-first tree containing only u, even though u has both outward and inward edges.

# a. True

# b. False

# If vertices u and v are in different trees of the depth-first forest, then u and v must not be connected.

# a. True

# b. False

# A depth-first tree is always different from a breadth-first tree rooted at the same vertex for the same graph G.

# a. True

# b. False

# Using which one of the following data structures can we implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time?

# a. Binary Tree

# b. Queue

# c. Heap

# d. Stack

# Given a directed graph with negative edge weights, Dijkstra’s algorithm is capable of finding the shortest path between two nodes.

# a. True

# b. False

# Which algorithm design paradigm does the Floyd-Warshall algorithm follow?

# a. Divide and conquer

# b. Greedy

# c. Prune and search

# d. Dynamic programming

# DAT 305 Week 5 Lab Assessment 6 Graphs, Prime Numbers, and Complexity Classes

Using the MindTap Access link,** complete** Module Lab Assessment 6: Graphs, Prime Numbers, and Complexity Classes in the Apply** **section of the Wk 5: Graphs, Prime Numbers, and Complexity Classes folder.