WGU C949- Data Structures and Algorithms I, C949 Questions with 100% correct answers (scored 99.9%)

Which statement describes a queue data structure?

It is a sequence of elements in which insertions can take place only at the back end and deletions can take place only at the front end.

What are the official indexes for the list list01 given this declaration? int[ ] list01 = {0, 2, 4, 6, 8, 10};

0, 1, 2, 3, 4, 5

Which abstract data type (ADT) has elements of the same type so that the elements can be retrieved based on the index or position?

List

Which category of data does ("FB", 75.00, 75.03, 74.90) represent in the pseudocode?

import datetime

def middle(stock, date):

symbol, current, high, low = stock

return (((high + low) / 2), date)

mid_value, date = middle(("FB", 75.00, 75.03, 74.90),

datetime.date(2014, 10, 31))

Tuple

Which data type does the mystery function return?

return_type mystery (int R)

{

int NumUnits = R;return NumUnits * 3.14;

}

Double

Which value is appropriate for the variable middle given the pseudocode?

function mystery()

{

string last;

string first;

char middle;

int phone;

float rate;

}

'D'

What is the most efficient data type to use for this data set of a fixed size in Java?

a = [0, 0, 1, 4, 7, 16, 31, 64, 127]

Array

What is true about garbage collection?

It reclaims memory from data structures implemented using linked allocations.

What is true about a data structure implemented using linked allocation?

Storage is allocated using pointers to new locations as needed.

What are the array elements corresponding to the mid-values in the first and second iterations of a binary search in an array arr = {45, 77, 89, 90, 94, 99, 100} and key = 100?

90 and 99

What is the effect on the object Computing regarding garbage collection?

Computing obj = new Computing(); obj = null;

It is automatically available for garbage collection.

What are the mid-values in the first and second levels of recursion in this binary search?

int arr = {46, 76, 89, 90, 94, 99, 100} and key = 99

90 and 99

Which data set is represented using the dictionary data type?

A set of students and their test scores

What is a characteristic of keys in an associative dictionary data type?

They are unique and immutable.

Which method can be used to take a value out of a dictionary?

D1[key].remove(value)

Given this data dictionary in Python:

dict = {'white':0x0000, 'black':0x1111}

Which command/function generates the output ['white','black']?

dict.keys()

Items were added sequentially in this stack starting with 'ham':

'sausage'

'toast'

'eggs'

'ham'

What is the correct order of contents after the push operation is performed with the value 'bacon'?

'bacon'

'sausage'

'toast'

'eggs'

'ham'

Items were added sequentially in this stack starting with "dog":

"bird"

"rabbit"

"cat"

"dog"

What is the return value of the pop operation?

"bird"

Which sequence of letters represents preorder traversal of the nodes of this tree?

A

/ \

B C

/ \

/ \

D E

\ / \

F G H

/

I

A B C D F E G I H

An array soc of size 1009 is used where the index is an integer in [0,1008] and the hash-function key%1009.

Where will the data associated with the key given by the last 4 social security digits '2023' be stored?

In soc[5]

A stack s, a queue q, and a max value priority queue p each have a single 3 in them. Next s.push(4), q.push(4), and p.push(4) are executed.

What is the triple (s.pop(), q.pop(), p.pop())?

(4,3,4)

This stack reads left to right with the top to the right:

'green'

'yellow'

'blue'

'red'

What could be the stack after a push operation?

['red','blue','yellow', 'green', 'purple"]

Items were added sequentially onto the stack starting with 'red':

'green'

'yellow'

'blue'

'red'

What is the stack after a pop operation?

'yellow'

'blue'

'red'

Which command helps to speed up comparisons using dictionary keys during a dictionary (d) lookup in this pseudocode clip?

h = hash(key)

for pair in d:

if h == pair[0]:

return pair[1]

hash(object)

What does the method any(b) return in Python if b is a dictionary?

Returns True if any key of the dictionary is true.

Which Java method is used to read bytes from a standard file?

Java.io.FileInputStream

Which command will retrieve an item from the top of the stack?

Pop()

Which command will insert object x at position index in a list?

Add(int index, Object x)

Which command will return true if x is in a list, otherwise return false?

Contains(Object x)

When should a dictionary be used instead of a list?

When the program uses key-value pairs as its data

Which data structure is indexed?

Array

Which data structure may only store homogeneous data elements?

Arrays

Which data structure uses a last in, first out (LIFO) removal of items?

Stack

Given:

heapList = [22, 33, 44, 55, 66]

Which index is the right child of item 22?

44

What is the logical first step in an algorithm that extracts all the positive values from a given list of numbers?

Initialize the result to an empty list

What is displayed when n = 2 in this pseudocode?

for(int i = 2; i <= n; i++){

for(j = 0; j <= n;){

display j;

j = j + n/2; the division is integer division, decimal part neglected

}

}

0, 1, 2

Given a set of numeric data and two declared variables: small and max, what is the logical first step in an algorithm that finds the smallest number?

Checking that the list contains at least one number

What is the output of the pseudocode below if the variables declared in the main program are global?

Main

Declare X as Integer, Y as Integer

Set X = 1

Set Y = 2

Call Sub(X, Y)

Write X

Write Y

End Program

Subprogram Sub(Integer Num1, Integer Num2 as Reference)

Declare X as Integer

Set Num1 = 3

Set Num2 = 4

Set X = 5

Write X

End Subprogram

5

14

How many times in this pseudocode is the function F called?

Main

Declare K as Integer

K = 3

Set Result = F(K)

Write Result

End Program

Function F(N) as Integer

If N == 1 Then

Set F = 1

Else

Set F = N * F(N - 1)

Set N = N - 1

End If

End Function

3

What is displayed in Step 5 if A = 15 and B = 5 in the pseudocode below?

Step 1: Start

Step 2: Read A, B

Step 3: C= A*B

Step 4: D=A/B

Step5: Print C

Step 6: Stop

75

What is displayed in step 3 if midterm = 60 and final = 65 in this pseudocode?

Step 1: Declare midterm, final as integer

Step 2: average = (midterm+final)/2

Step 3: if (average < 50) then Print "Fail" Else Print "Pass"

endif

Pass

How many times will count++ execute when i = 3, in this pseudocode?

int count = 0;

int N = 4;

for (int i = 0; i < N; i++)

for (int j = 0; j < i; j++)

count++;

3

At the end of obj, what is the time complexity of inserting in this pseudocode?

void DynamicArrayAppend(DynamicArray obj, const void input) {

if (obj->logicalSize == obj->capacity - 1) {

obj->capacity *= 2;

obj->internalArray = realloc(obj->internalArray, obj->capacity * obj->itemSize);

}

obj->logicalSize += 1; DynamicArraySet(obj, obj->logicalSize - 1, input);

}

DynamicArray *obj = DynamicArrayCreate(sizeof(int));for (int i = 0; i < n; i++) {

int number = rand() % 10; DynamicArrayAppend(obj, &number);

}

O(1) or O(n)

What is the time complexity of this pseudocode?

double sumCol(double table[][], int numRows, int numCols, int col)

{

double cSum = 0;

for (int row = 0; row < numRows; row++)

{

cSum += table[row][col];

}

return cSum;

}

O(n)

What is the time complexity of the instructions in this pseudocode?

for (i = 0; i < N; i++){

for (j = i+1; j < N; j++) {

... // sequence of statements that do not alter N

}

}

O(N^2)

What is the time complexity of this pseudocode?

Algorithm Algo1(A)

Input: An array A storing n ≥ 1 integers

Output: The sum of the elements in A

s=A[1]

for i=1 to n do

s=s+A[i]

return s

O(n)

What is the time complexity of this pseudocode?

Algorithm Algo3(A, B)

Input: Arrays A and B, each of them storing n≥1 integers

Output: Count array B[i], where B[i] equals the sum of A[1] to A[i], i=1 to n

c=0

for i=1 to n do

for j=1 to n do

s=A[1]

for k=1 to j do

s=s+A[k]

if B[i]=s then

c=c+1

return c

O(n^3)

What is an attribute of a bubble sort algorithm?

Ideal for small number of n

What is a characteristic of quick sort?

Recursively breaks down a problem into two or more subproblems of the same or related type

Which Big-O notation represents the time complexity of a bubble sort?

​​​​​O(n^2)

What is the typical run time for an insertion sort?

O(n^2)

A large set of floating point numbers that are in range from 0.0 to 1.0 and are uniformly distributed across the range need to be sorted.

Which sort procedure is useful when the input is uniformly distributed over the range?

Bucket

How many buckets are needed when sorting 13 numbers that have 15 digits each, using the radix-sort algorithm?

10

Which type of sorting algorithm is demonstrated in this pseudocode?

for i from 0 to N - 1

if a[i] > a[i + 1]

swap( a[i], a[i + 1])

end

Bubble

Which type of sorting algorithm is demonstrated in this pseudocode?

def shortSort(alist):

exchanges = True

passnum = len(alist)-1

while passnum > 0 and exchanges:

exchanges = False

for i in range(passnum):

if alist[i]>alist[i+1]:

exchanges = True

temp = alist[i]

alist[i] = alist[i+1]

alist[i+1] = temp

passnum = passnum-1

Bubble

Which type of sorting algorithm is demonstrated in this code?

int partition( void *a, int low, int high )

{

int left, right;

void *pivot_item;

pivot_item = a[low];

pivot = left = low;

right = high;

while ( left < right ) {

/ Move left while item < pivot /

while( a[left] <= pivot_item ) left++;

/ Move right while item > pivot /

while( a[right] > pivot_item ) right--;

if ( left < right ) SWAP(a,left,right);

}

/ right is final position for the pivot /

a[low] = a[right];

a[right] = pivot_item;

return right;

}

Quick

singly-linked list

a data structure for implementing a list ADT, where each node has data and a pointer to the next node

doubly-linked list

a data structure for implementing a list ADT, where each node has data, a pointer to the next node, and a pointer to the previous node. The list structure typically points to the first node and the last node

hash table

a data structure that stores unordered items by mapping (or hashing) each item to a location in an array (or vector)

all(list)

True if every element in list is True (!= 0), or if the list is empty.

any(list)

True if any element in the list is True.

list nesting

a list inside another list

Ex: my_list = [[5, 13], [50, 75, 100]]

my_list[start:end]

Get a list from start to end (minus 1).

Code:my_list = [5, 10, 20]print(my_list[0:2])

Output: [5, 10]

my_list[start:end:stride]

Get a list of every stride element from start to end (minus 1).

Code: my_list = [5, 10, 20, 40, 80]print(my_list[0:5:3])

Output: [5, 40]

my_list[start:]

Get a list from start to end of the list.

Code: my_list = [5, 10, 20, 40, 80]print(my_list[2:])

Output: [20, 40, 80]

my_list[:end]

Get a list from beginning of list to end (minus 1).

Code: my_list = [5, 10, 20, 40, 80]print(my_list[:4])

Output: [5, 10, 20, 40]

my_list[:]

Get a copy of the list.

dictionary

another type of container object that is different from sequences like strings, tuples, and lists. References to objects as key-value pairs - each key in the dictionary is associated with a value

dict method

a function provided by the dict type that operates on a specific dict object.

List

an ADT for holding ordered data.

Ex: Array, linked list

Bag

an ADT for storing items in which the order does not matter and duplicate items are allowed.

Ex: Array, Linked List

Set

an ADT for a collection of distinct items.

Ex: Binary search tree, hash table

Dictionary (Map)

an ADT that associates (or maps) keys with values.

Ex: Hash table, binary search tree

inserting a new item at the beginning it causes no shift to the data

what is an advantage of a linked list over an array?n

N

In the worst case, inserting a new node into a tree with N nodes requires how many comparisons?

reference count

A _____________is an integer counter that represents how many variables reference an object. When an object's reference count is 0, that object is no longer referenced.

while loop

A ______ executes a block of code as long as the loop's expression is True.

print(user_value*5)

The syntax __________ produces a new string, which repeats the value of user_value 5 times. In this case, the value of user_value may be "-", thus the result of the multiplication is "-----".

range()

generates a sequence of numbers, starting at zero and ending before a value given inside the parentheses. For example, for i in range(3) sets i to 0 during the first iteration of the for loop, i to 1 during the second iteration, and finally i to 2 on the third iteration. The value within the parentheses is not included in the generated sequence.

namespace

A ____________ maps names to objects. The Python interpreter uses namespaces to track all of the objects in a program.

object

In a program, an ______ consists of some internal data items plus operations that can be performed on that data.

list.index(val)

find the index of the first element in list whose value matches val.

list.count(val)

Count the number of occurrences of the value val in list.

name

A ,__________ also called an identifier, is a sequence of letters (a-z, A-Z, _) and digits (0-9), and must start with a letter. Note that "_", called an underscore, is considered to be a letter.

type()

built-in function ___________ prints the type of an object.

Identity:

A unique identifier that describes the object

selection sort

O(n^2) A sort algorithm that repeatedly searches remaining items to find the least one and moves it to its final location.

Remove(list, x)

Removes x Remove(list, 77), list: 99

Search(list, x)

Returns item if found, else returns null Search(list, 99), returns item 99Search(list, 22), returns null

Print(list)

Prints list's items in orderPrint(list) outputs: 99, 77

Sort(list)

Sorts the lists items in ascending orderlist becomes: 77, 99

IsEmpty(list)

Returns true if list has no items

For list 99, 77, IsEmpty(list) returns false

record

data structure that stores subitems, with a name associated with each subitem

array

a data structure that stores an ordered list of items, with each item is directly accessible by a positional index

homogeneous data elements Inserting at the beginning requires making room for the new item. So every current item must be shifted once.

linked list

data structure that stores ordered list of items in nodes, where each node stores data and has a pointer to the next node; can have multiple subitems No shifting of other items is required, which is an advantage of using linked lists.

binary tree

A data structure that consists of nodes, with one root node at the base of the tree, and two nodes (left child and right child) extending from the root, and from each child node

can have no children, single left or right, or both right and left

hash table

data structure that stores unordered items by mapping (or hashing) each item to a location in an array

max-heap

a tree that maintains the simple property that a node's key is greater than or equal to the node's childrens' keys

min-heap

a tree that maintains the simple property that a node's key is less than or equal to the node's childrens' keys

vertice

part of a graph the represents an item in a graph