Data Structure 6 Flashcards
What is the logical last step in an algorithm that averages the high temperatures for 10 days and displays the average high temperature?
Printing the temperature
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 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
