Difference between revisions of "2022 Paper 1 Revision Quiz"

From TRCCompSci - AQA Computer Science
Jump to: navigation, search
(→‎Abstract Data Types & Dynamic vs Static)
 
(62 intermediate revisions by the same user not shown)
Line 96: Line 96:
 
What will be the final value returned for the call Fact(5):
 
What will be the final value returned for the call Fact(5):
 
{ 120 }
 
{ 120 }
 +
</quiz>
 +
 +
=Arrays=
 +
<quiz display=simple>
 +
 +
{When considering arrays, which of the following are correct
 +
|type="[]"}
 +
+You must declare a size when creating the array
 +
||Correct
 +
-You don't need to specify a size when creating an array
 +
||Incorrect
 +
+The memory for the entire structure is allocated when it is created
 +
||Correct
 +
-Only the initial memory is allocated when creating, the rest is allocated when we add items
 +
||Incorrect
 +
 +
{When using arrays the square brackets [] :
 +
|type="()"}
 +
-Are used to access the whole array
 +
||Incorrect
 +
-Contain the data value to look up in the array
 +
||Incorrect
 +
+Are used to access a specific element in the array
 +
||Correct
 +
-Contain the data value store in the array
 +
||Incorrect
 +
 +
{An array can be of any data type or class.
 +
|type="()"}
 +
+True
 +
||Correct
 +
-False
 +
||Incorrect
 +
 +
{A 2D array can still only be of one data type or class.
 +
|type="()"}
 +
+True
 +
||Correct
 +
-False
 +
||Incorrect
 +
 +
{An Array is a:
 +
|type="()"}
 +
-Abstract Data Structure
 +
||Incorrect
 +
-Dynamic Data Structure
 +
||Incorrect
 +
+Static Data Structure
 +
||Correct
 +
-Strong Data Structure
 +
||Incorrect
 +
</quiz>
 +
 +
=Abstract Data Types & Dynamic vs Static=
 +
<quiz display=simple>
 +
 +
{A Abstract Data type is:
 +
|type="[]"}
 +
-Defined by how it is implemented
 +
||Incorrect
 +
+Not defined by how it is implemented
 +
||Correct
 +
+Can be implemented in many ways
 +
||Correct
 +
-Can only be implement in one way
 +
||Incorrect
 +
 +
{When considering dynamic structures, which of the following are correct
 +
|type="[]"}
 +
-You must declare a size when creating the structure
 +
||incorrect
 +
-You don't need to specify a size when creating the structure
 +
||Correct
 +
-The memory for the entire structure is allocated when it is created
 +
||Incorrect
 +
+Only the initial memory is allocated when creating, the rest is allocated when we add items
 +
||Correct
 +
 +
{The benefits of static structures are:
 +
|type="[]"}
 +
-Makes the most efficient use of memory because it only allocates what is needed
 +
||Incorrect
 +
+Memory allocation is fixed so adding and removing data items should be straight forward
 +
||Correct
 +
+The size of the structure is known so you don't need to calculate the size of the structure
 +
||Correct
 +
-Are very flexible and items can be added and removed without worrying about where they are in the structure
 +
||Incorrect
 +
 +
{The drawbacks of a static structure are:
 +
|type="()"}
 +
-It is possible for the structure to overflow or underflow
 +
||Incorrect
 +
+Can be very inefficient with memory because memory is allocated whether it is needed or not
 +
||Correct
 +
-The memory allocated will be fragmented so will take longer to read
 +
||Incorrect
 +
- You might need to code basic function to get the size or number of items stored
 +
||Incorrect
 +
 +
{The benefits of dynamic structures are:
 +
|type="[]"}
 +
+Makes the most efficient use of memory because it only allocates what is needed
 +
||Correct
 +
-Memory allocation is fixed so adding and removing data items should be straight forward
 +
||Incorrect
 +
-The size of the structure is known so you don't need to calculate the size of the structure
 +
||Incorrect
 +
+Are very flexible and items can be added and removed without worrying about where they are in the structure
 +
||Correct
 +
 +
{The drawbacks of a dynamic structure are:
 +
|type="[]"}
 +
+It is possible for the structure to overflow or underflow
 +
||Correct
 +
-Can be very inefficient with memory because memory is allocated whether it is needed or not
 +
||Incorrect
 +
+The memory allocated will be fragmented so will take longer to read
 +
||Correct
 +
+ You might need to code basic function to get the size or number of items stored
 +
||Correct
 +
 +
</quiz>
 +
 +
=Queues=
 +
<quiz display=simple>
 +
{A queue is ?
 +
|type="()"}
 +
- Last In First Out .
 +
||Incorrect
 +
+ First in First Out.
 +
||Correct
 +
 +
{Complete the following;
 +
|type="{}"}
 +
A new item must be added to the { back|rear|tail } of the queue.
 +
You must remove the item at the { front|head } of the queue.
 +
 +
{In a Linear queue, the front of the queue will move further back as items are taken from the front of the queue.
 +
|type="()"}
 +
+True
 +
||Correct
 +
-False
 +
||Incorrect
 +
 +
{In a Linear queue, when an item is removed from the front of the queue the remaining items are moved forward.
 +
|type="()"}
 +
-True
 +
||Incorrect
 +
+False
 +
||Correct
 +
 +
{A circular queue works by using pointers. The front pointer will point to:
 +
|type="()"}
 +
-The back of the queue
 +
||Incorrect
 +
-The location for the next item onto the queue
 +
||Incorrect
 +
+The first item in the queue
 +
||Correct
 +
-The second item in the queue
 +
||Incorrect
 +
 +
{A circular queue works by using pointers. The rear pointer will point to:
 +
|type="()"}
 +
+The back of the queue
 +
||Correct
 +
-The location for the next item onto the queue
 +
||Incorrect
 +
-The first item in the queue
 +
||Incorrect
 +
-The second item in the queue
 +
||Incorrect
 +
 +
{To make a circular queue you must reset either pointer back to 1 when:
 +
|type="()"}
 +
-Number of Items = Max Queue Size
 +
||Incorrect
 +
-Number of Items = 0
 +
||Incorrect
 +
+When the Pointer Value = Max Queue Size
 +
||Correct
 +
 +
{in a circular queue you must test for empty by:
 +
|type="()"}
 +
-Number of Items = Max Queue Size
 +
||Incorrect
 +
+Number of Items = 0
 +
||Correct
 +
-When the Pointer Value = Max Queue Size
 +
||Incorrect
 +
 +
{in a circular queue you must test for full by:
 +
|type="()"}
 +
+Number of Items = Max Queue Size
 +
||Correct
 +
-Number of Items = 0
 +
||Incorrect
 +
-When the Pointer Value = Max Queue Size
 +
||Incorrect
 +
 +
</quiz>
 +
 +
=Stacks=
 +
<quiz display=simple>
 +
{A stack is ?
 +
|type="()"}
 +
+ Last In First Out .
 +
||Correct
 +
- First in First Out.
 +
||Incorrect
 +
 +
{The stack pointer will point to?
 +
|type="()"}
 +
- The location to store the next item
 +
||Incorrect
 +
+ Top of the stack.
 +
||Correct
 +
- Bottom of the stack.
 +
||Incorrect
 +
 +
{To add an item to the stack you?
 +
|type="()"}
 +
- Pop.
 +
||Incorrect
 +
+ Push.
 +
||Correct
 +
- Peek.
 +
||Incorrect
 +
 +
{To remove an item from the stack you?
 +
|type="()"}
 +
+ Pop.
 +
||Correct
 +
- Push.
 +
||Incorrect
 +
- Peek.
 +
||Incorrect
 +
 +
{To look at the top of the stack without removing it you?
 +
|type="()"}
 +
- Pop.
 +
||Incorrect
 +
- Push.
 +
||Incorrect
 +
+ Peek.
 +
||Correct
 +
</quiz>
 +
 +
=Graphs=
 +
<quiz display=simple>
 +
 +
{Look at this graph:
 +
 +
[[File:Graph-4.jpg|300px]]
 +
 +
select the appropriate options below:
 +
|type="[]"}
 +
- The degree of vertex A is 3
 +
||Incorrect
 +
- The degree of vertex D is 1
 +
||Incorrect
 +
+ The degree of vertex B is 3
 +
||Correct
 +
+ The degree of vertex E is 1
 +
||Correct
 +
 +
{Look at this graph:
 +
 +
[[File:Graph-4.jpg|300px]]
 +
 +
select the appropriate options below:
 +
|type="[]"}
 +
- Directed
 +
||Incorrect
 +
+ Undirected
 +
||Correct
 +
- Weighted
 +
||Incorrect
 +
+Unweighted
 +
||Correct
 +
 +
{Look at this graph:
 +
 +
[[File:Graph1.png|300px]]
 +
 +
select the appropriate options below:
 +
|type="[]"}
 +
- Directed
 +
||Incorrect
 +
+ Undirected
 +
||Correct
 +
+ Weighted
 +
||Correct
 +
- Unweighted
 +
||Incorrect
 +
 +
{Look at this graph:
 +
 +
[[File:Graph2.png|300px]]
 +
 +
select the appropriate options below:
 +
|type="[]"}
 +
+ Directed
 +
||Correct
 +
- Undirected
 +
||Incorrect
 +
- Weighted
 +
||Incorrect
 +
+ Unweighted
 +
||Correct
 +
 +
{Look at this graph:
 +
 +
[[File:Graph3.png|300px]]
 +
 +
Complete the adjacency matrix, use Y & N only:
 +
|type="{}"}
 +
<table style="border:1px solid black;">
 +
  <tr>
 +
  <td> </td><td>0</td><td>1</td><td>2</td><td>3</td>
 +
  </tr>
 +
  <tr>
 +
    <td>0</td><td>X</td><td>{ Y }</td><td>{ Y }</td><td>{ Y }</td>
 +
  </tr>
 +
    <tr>
 +
    <td>1</td><td> { Y } </td><td>X</td><td> { Y } </td><td> { N } </td>
 +
  </tr>
 +
    <tr>
 +
    <td>2</td><td>{ Y }</td><td>{ Y }</td><td>X</td><td>{ N }</td>
 +
  </tr>
 +
    <tr>
 +
    <td>3</td><td>{ Y } </td><td> { N } </td><td> { N } </td><td>X</td>
 +
  </tr>
 +
</table>
 +
 +
{Look at this graph:
 +
 +
[[File:Graph2.png|300px]]
 +
 +
Complete the adjacency matrix, use Y & N only:
 +
|type="{}"}
 +
<table style="border:1px solid black;">
 +
  <tr>
 +
  <td> </td><td>A</td><td>B</td><td>C</td><td>D</td>
 +
  </tr>
 +
  <tr>
 +
    <td>A</td><td>X</td><td>{ Y }</td><td>{ N }</td><td>{ Y }</td>
 +
  </tr>
 +
    <tr>
 +
    <td>B</td><td> { N } </td><td>X</td><td> { Y } </td><td> { Y } </td>
 +
  </tr>
 +
    <tr>
 +
    <td>C</td><td>{ N }</td><td>{ N }</td><td>X</td><td>{ N }</td>
 +
  </tr>
 +
    <tr>
 +
    <td>D</td><td>{ N } </td><td> { N } </td><td> { N } </td><td>X</td>
 +
  </tr>
 +
</table>
 +
 +
{Look at this graph:
 +
 +
[[File:Graph3.png|300px]]
 +
 +
Complete the adjacency list (separate with commas & no spaces):
 +
|type="{}"}
 +
<table style="border:1px solid black;">
 +
  <tr>
 +
  <td> </td><td>Connected</td>
 +
  </tr>
 +
  <tr>
 +
    <td>0</td><td>{ 1,2,3 }</td>
 +
  </tr>
 +
    <tr>
 +
    <td>1</td><td> { 0,2|0.2 } </td>
 +
  </tr>
 +
    <tr>
 +
    <td>2</td><td>{ 0,1|0.1 }</td>
 +
  </tr>
 +
    <tr>
 +
    <td>3</td><td>{ <nowiki>0</nowiki> } </td>
 +
  </tr>
 +
</table>
 +
 +
{Look at this graph:
 +
 +
[[File:Graph2.png|300px]]
 +
 +
Complete the adjacency list (separate with comma no spaces, use None if nothing is connected):
 +
|type="{}"}
 +
<table style="border:1px solid black;">
 +
  <tr>
 +
  <td> </td><td>Connected</td>
 +
  </tr>
 +
  <tr>
 +
    <td>A</td><td> { B,D }</td>
 +
  </tr>
 +
    <tr>
 +
    <td>B</td><td> { C,D } </td>
 +
  </tr>
 +
    <tr>
 +
    <td>C</td><td>{ None }</td>
 +
  </tr>
 +
    <tr>
 +
    <td>D</td><td>{ None } </td>
 +
  </tr>
 +
</table>
 +
 +
{Complete the following
 +
|type="{}"}
 +
You should use an adjacency list when there are { few } edges.
 +
 +
You should use an adjacency matrix if there are { many } edges.
 +
 +
{Processing adjacency matrix is much simpler because you can have direct access to check if an edge exists
 +
|type="()"}
 +
+True
 +
||Correct
 +
- False
 +
||Incorrect
 +
 +
</quiz>
 +
 +
=Trees=
 +
<quiz display=simple>
 +
{Which of the following must a graph have to also be a tree?
 +
|type="[]"}
 +
-Not Connected
 +
||Incorrect
 +
+ Connected.
 +
||Correct
 +
-  Weighted
 +
||Incorrect
 +
- Unweighted.
 +
||Incorrect
 +
- Directed.
 +
||Incorrect
 +
+ Undirected.
 +
||Incorrect
 +
-With Cycles
 +
||Incorrect
 +
+Without Cycles
 +
||Correct
 +
</quiz>
 +
 +
=Graph Traversal=
 +
<quiz display=simple>
 +
 +
{Depth First Traversal uses a:
 +
|type="()"}
 +
-Queue
 +
||Incorrect
 +
+Stack
 +
||Correct
 +
-List
 +
||Incorrect
 +
-Dictionary
 +
||Incorrect
 +
 +
{Breadth First Traversal uses a:
 +
|type="()"}
 +
+Queue
 +
||Correct
 +
-Stack
 +
||Inorrect
 +
-List
 +
||Incorrect
 +
-Dictionary
 +
||Incorrect
 +
 +
{Complete the following:
 +
|type="{}"}
 +
For Depth First & Breadth First traversals it is important to know when a node has been { discovered }.
 +
When you evaluate a node the { neighbours } of the current node will be add to the Stack or Queue.
 +
It is important to also record when you have { fully|completely } explored the current node.
 +
</quiz>
 +
 +
=Searching Algorithms=
 +
<quiz display=simple>
 +
 +
</quiz>
 +
 +
=Sorting Algorithms=
 +
<quiz display=simple>
 +
{Which sorting algorithm uses 'Divide & Conquer' strategy?
 +
|type="()"}
 +
- Bubble Sort.
 +
||Incorrect
 +
+ Merge Sort.
 +
||Correct
 +
- Neither.
 +
||Incorrect
 +
 +
{Which sorting algorithm will complete a number of passes?
 +
|type="()"}
 +
+ Bubble Sort.
 +
||Correct
 +
- Merge Sort.
 +
||Incorrect
 +
- Neither.
 +
||Incorrect
 +
 +
{Which sorting algorithm will break a list into multiple lists containing a single value?
 +
|type="()"}
 +
- Bubble Sort.
 +
||Incorrect
 +
+ Merge Sort.
 +
||Correct
 +
- Neither.
 +
||Incorrect
 +
 +
{Which sorting algorithm will be recursive?
 +
|type="()"}
 +
- Bubble Sort.
 +
||Incorrect
 +
+ Merge Sort.
 +
||Correct
 +
- Neither.
 +
||Incorrect
 +
 +
{Which sorting algorithm will sort the list with N-1<sup>2</sup> comparisons?
 +
|type="()"}
 +
+ Bubble Sort.
 +
||Correct
 +
- Merge Sort.
 +
||Incorrect
 +
- Neither.
 +
||Incorrect
 +
 +
</quiz>
 +
 +
=Optimisation Algorithms=
 +
<quiz display=simple>
 +
 +
</quiz>
 +
 +
=Order of Complexity=
 +
<quiz display=simple>
 +
{Complete the following:
 +
|type="{}"}
 +
 +
1) Constant        : { O(1) }
 +
2) { Logarithmic } : O(log N)
 +
3) Linear          : { O(N) }
 +
4) Linearithmic    : { O(N log N)  }
 +
5) { Polynomial  }  : O (N<sup>2</sup>)
 +
6) { Exponential  } : O(k<sup>N</sup>) 
 +
7) Factorial      : { O(N!)  }
 +
 +
{Complete the Order of Complexity for the following examples:
 +
|type="{}"}
 +
 +
1) Finding the first item in a list      : { O(1)|Constant }
 +
2) { Binary Search } : Logarithmic or O(log N)
 +
3) { Linear Search } :  Linear or O(N)
 +
4) Merge Sort        : { Linearithmic|O(N log N) }
 +
5) { Bubble Sort }  : Polynomial or O (N<sup>2</sup>)
 +
6) { Chess Board Problem  } : Exponential or O(k<sup>N</sup>) 
 +
7) { Travelling Salesman Problem }: Factorial or O(N!)
 +
</quiz>
 +
 +
=Halting Problem=
 +
<quiz display=simple>
 +
{Complete the Halting Problem:
 +
|type="{}"}
 +
‘Is it possible to { write|create } a program that can tell given any { program } and its { inputs } and without { executing } the program, whether it will { halt }?’
 
</quiz>
 
</quiz>

Latest revision as of 16:58, 3 June 2022

Recursion

1. In Recursion, the part of the code which runs itself is called?

General Case.
→Correct
Base Case.
→Incorrect
Repeating Case.
→Incorrect
Recursive Case.
→Incorrect

2. In Recursion, the condition which stops the recursive calls is called?

General Case.
→Correct
Base Case.
→Incorrect
Repeating Case.
→Incorrect
Recursive Case.
→Incorrect

3. Look at this sample code: 

1: public int Fact(int num)
2: {
3:   if (num == 0)
4:       return 1;
5:   else
6:       return num * Fact(num-1);
7: }

Which of these lines are the General Case?

3
→Incorrect
4
→Incorrect
5
→Incorrect
6
→Correct

4. Look at this sample code: 

1: public int Fact(int num)
2: {
3:   if (num == 0)
4:       return 1;
5:   else
6:       return num * Fact(num-1);
7: }

Which of these lines are the Base Case?

3
→Almost, this is the condition which causes the base case
4
→Correct
5
→Incorrect
6
→Incorrect

5. Look at this sample code: 

 1: public int Fact(int num)
 2: {
 3:   if (num == 0)
 4:       return 1;
 5:   else
 6:       return num * Fact(num-1);
 7: }

The function Fact is run with the parameter of 5. 

Fact(5);
What is the return value for the First call:
What is the return value for the Second call:
What is the return value for the Third call:
What is the return value for the Fourth call:
What is the return value for the Fifth call:
What is the return value for the Sixth call:
What will be the final value returned for the call Fact(5):

Your score is 0 / 0


Arrays

1. When considering arrays, which of the following are correct

You must declare a size when creating the array
→Correct
You don't need to specify a size when creating an array
→Incorrect
The memory for the entire structure is allocated when it is created
→Correct
Only the initial memory is allocated when creating, the rest is allocated when we add items
→Incorrect

2. When using arrays the square brackets [] :

Are used to access the whole array
→Incorrect
Contain the data value to look up in the array
→Incorrect
Are used to access a specific element in the array
→Correct
Contain the data value store in the array
→Incorrect

3. An array can be of any data type or class.

True
→Correct
False
→Incorrect

4. A 2D array can still only be of one data type or class.

True
→Correct
False
→Incorrect

5. An Array is a:

Abstract Data Structure
→Incorrect
Dynamic Data Structure
→Incorrect
Static Data Structure
→Correct
Strong Data Structure
→Incorrect

Your score is 0 / 0


Abstract Data Types & Dynamic vs Static

1. A Abstract Data type is:

Defined by how it is implemented
→Incorrect
Not defined by how it is implemented
→Correct
Can be implemented in many ways
→Correct
Can only be implement in one way
→Incorrect

2. When considering dynamic structures, which of the following are correct

You must declare a size when creating the structure
→incorrect
You don't need to specify a size when creating the structure
→Correct
The memory for the entire structure is allocated when it is created
→Incorrect
Only the initial memory is allocated when creating, the rest is allocated when we add items
→Correct

3. The benefits of static structures are:

Makes the most efficient use of memory because it only allocates what is needed
→Incorrect
Memory allocation is fixed so adding and removing data items should be straight forward
→Correct
The size of the structure is known so you don't need to calculate the size of the structure
→Correct
Are very flexible and items can be added and removed without worrying about where they are in the structure
→Incorrect

4. The drawbacks of a static structure are:

It is possible for the structure to overflow or underflow
→Incorrect
Can be very inefficient with memory because memory is allocated whether it is needed or not
→Correct
The memory allocated will be fragmented so will take longer to read
→Incorrect
You might need to code basic function to get the size or number of items stored
→Incorrect

5. The benefits of dynamic structures are:

Makes the most efficient use of memory because it only allocates what is needed
→Correct
Memory allocation is fixed so adding and removing data items should be straight forward
→Incorrect
The size of the structure is known so you don't need to calculate the size of the structure
→Incorrect
Are very flexible and items can be added and removed without worrying about where they are in the structure
→Correct

6. The drawbacks of a dynamic structure are:

It is possible for the structure to overflow or underflow
→Correct
Can be very inefficient with memory because memory is allocated whether it is needed or not
→Incorrect
The memory allocated will be fragmented so will take longer to read
→Correct
You might need to code basic function to get the size or number of items stored
→Correct

Your score is 0 / 0


Queues

1. A queue is ?

Last In First Out .
→Incorrect
First in First Out.
→Correct

2. Complete the following;

A new item must be added to the of the queue.
You must remove the item at the of the queue.

3. In a Linear queue, the front of the queue will move further back as items are taken from the front of the queue.

True
→Correct
False
→Incorrect

4. In a Linear queue, when an item is removed from the front of the queue the remaining items are moved forward.

True
→Incorrect
False
→Correct

5. A circular queue works by using pointers. The front pointer will point to:

The back of the queue
→Incorrect
The location for the next item onto the queue
→Incorrect
The first item in the queue
→Correct
The second item in the queue
→Incorrect

6. A circular queue works by using pointers. The rear pointer will point to:

The back of the queue
→Correct
The location for the next item onto the queue
→Incorrect
The first item in the queue
→Incorrect
The second item in the queue
→Incorrect

7. To make a circular queue you must reset either pointer back to 1 when:

Number of Items = Max Queue Size
→Incorrect
Number of Items = 0
→Incorrect
When the Pointer Value = Max Queue Size
→Correct

8. in a circular queue you must test for empty by:

Number of Items = Max Queue Size
→Incorrect
Number of Items = 0
→Correct
When the Pointer Value = Max Queue Size
→Incorrect

9. in a circular queue you must test for full by:

Number of Items = Max Queue Size
→Correct
Number of Items = 0
→Incorrect
When the Pointer Value = Max Queue Size
→Incorrect

Your score is 0 / 0


Stacks

1. A stack is ?

Last In First Out .
→Correct
First in First Out.
→Incorrect

2. The stack pointer will point to?

The location to store the next item
→Incorrect
Top of the stack.
→Correct
Bottom of the stack.
→Incorrect

3. To add an item to the stack you?

Pop.
→Incorrect
Push.
→Correct
Peek.
→Incorrect

4. To remove an item from the stack you?

Pop.
→Correct
Push.
→Incorrect
Peek.
→Incorrect

5. To look at the top of the stack without removing it you?

Pop.
→Incorrect
Push.
→Incorrect
Peek.
→Correct

Your score is 0 / 0


Graphs

1. Look at this graph:

Graph-4.jpg

select the appropriate options below:

The degree of vertex A is 3
→Incorrect
The degree of vertex D is 1
→Incorrect
The degree of vertex B is 3
→Correct
The degree of vertex E is 1
→Correct

2. Look at this graph:

Graph-4.jpg

select the appropriate options below:

Directed
→Incorrect
Undirected
→Correct
Weighted
→Incorrect
Unweighted
→Correct

3. Look at this graph:

Graph1.png

select the appropriate options below:

Directed
→Incorrect
Undirected
→Correct
Weighted
→Correct
Unweighted
→Incorrect

4. Look at this graph:

Graph2.png

select the appropriate options below:

Directed
→Correct
Undirected
→Incorrect
Weighted
→Incorrect
Unweighted
→Correct

5. Look at this graph:

Graph3.png

Complete the adjacency matrix, use Y & N only:

0123
0X
1 X
2X
3 X

6. Look at this graph:

Graph2.png

Complete the adjacency matrix, use Y & N only:

ABCD
AX
B X
CX
D X

7. Look at this graph:

Graph3.png

Complete the adjacency list (separate with commas & no spaces):

Connected
0
1
2
3

8. Look at this graph:

Graph2.png

Complete the adjacency list (separate with comma no spaces, use None if nothing is connected):

Connected
A
B
C
D

9. Complete the following

You should use an adjacency list when there are edges.
You should use an adjacency matrix if there are edges.

10. Processing adjacency matrix is much simpler because you can have direct access to check if an edge exists

True
→Correct
False
→Incorrect

Your score is 0 / 0


Trees

1. Which of the following must a graph have to also be a tree?

Not Connected
→Incorrect
Connected.
→Correct
Weighted
→Incorrect
Unweighted.
→Incorrect
Directed.
→Incorrect
Undirected.
→Incorrect
With Cycles
→Incorrect
Without Cycles
→Correct

Your score is 0 / 0


Graph Traversal

1. Depth First Traversal uses a:

Queue
→Incorrect
Stack
→Correct
List
→Incorrect
Dictionary
→Incorrect

2. Breadth First Traversal uses a:

Queue
→Correct
Stack
→Inorrect
List
→Incorrect
Dictionary
→Incorrect

3. Complete the following:

For Depth First & Breadth First traversals it is important to know when a node has been .
When you evaluate a node the of the current node will be add to the Stack or Queue.
It is important to also record when you have explored the current node.

Your score is 0 / 0


Searching Algorithms

Your score is 0 / 0


Sorting Algorithms

1. Which sorting algorithm uses 'Divide & Conquer' strategy?

Bubble Sort.
→Incorrect
Merge Sort.
→Correct
Neither.
→Incorrect

2. Which sorting algorithm will complete a number of passes?

Bubble Sort.
→Correct
Merge Sort.
→Incorrect
Neither.
→Incorrect

3. Which sorting algorithm will break a list into multiple lists containing a single value?

Bubble Sort.
→Incorrect
Merge Sort.
→Correct
Neither.
→Incorrect

4. Which sorting algorithm will be recursive?

Bubble Sort.
→Incorrect
Merge Sort.
→Correct
Neither.
→Incorrect

5. Which sorting algorithm will sort the list with N-12 comparisons?

Bubble Sort.
→Correct
Merge Sort.
→Incorrect
Neither.
→Incorrect

Your score is 0 / 0


Optimisation Algorithms

Your score is 0 / 0


Order of Complexity

1. Complete the following:

1) Constant  :
2)  : O(log N)
3) Linear  :
4) Linearithmic  :
5)  : O (N2)
6)  : O(kN)
7) Factorial  :

2. Complete the Order of Complexity for the following examples:

1) Finding the first item in a list  :
2)  : Logarithmic or O(log N)
3)  : Linear or O(N)
4) Merge Sort  :
5)  : Polynomial or O (N2)
6)  : Exponential or O(kN)
7) : Factorial or O(N!)

Your score is 0 / 0


Halting Problem

1. Complete the Halting Problem:

‘Is it possible to a program that can tell given any and its and without the program, whether it will ?’

Your score is 0 / 0
Retrieved from ‘http://www.trccompsci.online/mediawiki/index.php?title=2022_Paper_1_Revision_Quiz&oldid=8549’