DAT 305 Week 1 Apply — Course Pre-Assessment 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.