CC4 Midterms Flashcards

1
Q
  • is a step-by-step unambiguous instruction used to solve a given problem.
    o Example: A recipe that tells you exactly how to bake a cake, one step at a time.
A

Algorithm

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

o Example: A recipe that tells you exactly how to bake a cake, one step at a time.

A

Algorithm

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q
  • In programming, IT defines a set of values and the operations that can be performed on those values. Predefined values include integers, floats, and strings.
    o Example: Integers (e.g., 1, 2, 3) are data types that represent whole numbers.
A

Data Types

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

o Example: Integers (e.g., 1, 2, 3) are data types that represent whole numbers.

A

Data Types

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q
  • is a way to organize and store data in a computer so that it can be accessed and modified efficiently.
    o Example: Arrays, Linked Lists, Stacks, and Queues.
A

Data Structure

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

o Example: Arrays, Linked Lists, Stacks, and Queues.

A

Data Structure

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q
  • Refers to a type of data that is defined by its behavior (operations that can be performed on it), rather than its concrete implementation.
    o Example: A stack can be represented with an array or linked list, but as an ADT, you only care about operations like push, pop, and peek.
A

4. Abstract Data Types (ADT)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

o Example: A stack can be represented with an array or linked list, but as an ADT, you only care about operations like push, pop, and peek.

A

4. Abstract Data Types (ADT)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q
  • : Data is arranged in a linear sequence (e.g., Arrays, Lists).
A

Linear Data Structure

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q
  • : Elements are arranged in a hierarchy or graph, such as Trees and Graphs.
A

Non-Linear Data Structure

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q
  • it measures how the running time of an algorithm grows with the input size. Common cases include:

o Best Case: Minimum time an algorithm takes to complete.
o Worst Case: Maximum time an algorithm takes to complete.
o Average Case: The expected running time across all possible inputs.

A

Time Complexity

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

ENUMERATE THE COMMON CASES IN TIME COMPLEXITY AND DIFFERENTIATE THEM

A

o Best Case: Minimum time an algorithm takes to complete.

o Worst Case: Maximum time an algorithm takes to complete.

o Average Case: The expected running time across all possible inputs.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q
  • refers to the amount of memory an algorithm uses as it runs.

o Example: If an algorithm needs to store additional arrays or temporary variables, its space complexity increases.

A

Space Complexity

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

o Example: If an algorithm needs to store additional arrays or temporary variables, its space complexity increases.

A

Space Complexity

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q
  • are used to describe the performance of algorithms when the input size becomes very large. Common notations include:
    o Big O (O): Describes the worst-case scenario.
    o Omega (Ω): Describes the best-case scenario.
    o Theta (Θ): Describes the average-case scenario.
A

Asymptotic Notation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

ENUMERATE THE COMMON NOTATIONS AND DIFFERENTIATE THEM

A

o Big O (O): Describes the worst-case scenario.
o Omega (Ω): Describes the best-case scenario.
o Theta (Θ): Describes the average-case scenario.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q
  • Data elements that are accessed one after the other in sequence (e.g., accessing elements in an array). However, it’s not always compulsory to store elements sequentially in memory.
A

Sequential Access

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Accessing Elements in an Array

A
  • Each element in an array can be accessed using an index. The index is a numerical value starting at 0 (for most programming languages) that represents the position of an element.
  • Example:In the array arr[5] = [10, 20, 30, 40, 50], arr[2] refers to the third element, which is 30.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

ADVANTAGES OF ARRAYS

A
  • Arrays allow direct access to elements using their index, making retrieval very efficient.
  • Example: Accessing the element at index 4 in an array is instantaneous and does not require searching through the rest of the array.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

DISADVANTAGES OF ARRAYS

A
  • Arrays have a fixed size and require contiguous memory space. Inserting or deleting elements can be slow because it may require shifting elements.
  • Example: If you delete an element at the beginning of the array, all subsequent elements need to be shifted left.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q
  • Arrays can have multiple dimensions, such as 2D or 3D arrays, allowing data to be stored in a matrix or grid form.
  • Example: A 2D array can be visualized as a table with rows and columns (e.g., a chessboard layout).
A

Multidimensional Arrays

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q
  • Example: A 2D array can be visualized as a table with rows and columns (e.g., a chessboard layout).
A

Multidimensional Arrays

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q
    • Arrays are used to store a finite, ordered sequence of elements. This means every element in the array has a specific position or index, which allows for efficient data access based on index numbers.
A

Arrays as Lists

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Relationship Between Values and Indexes

A

While arrays hold elements in an ordered sequence, there may or may not be any inherent relationship between the value of an element and its position in the array. This depends on how the array is being used.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

size of an array

A

Once an array is created, its size is fixed in most programming languages. You cannot increase or decrease the size of the array during the program’s execution unless you’re working with dynamic data structures like lists in some languages

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

Array Bounds

A
    • In an array, the Lower Bound is the smallest index, typically starting at 0, and the Upper Bound is the highest index, which depends on the size of the array (size - 1).
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

Deleting Items from Arrays

A
  1. -: When an element is removed from an array, the elements that follow are usually shifted to fill the gap, maintaining the sequence of elements.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q
    • 2D arrays are arrays of arrays and can store data in a matrix form. They are often used to store and manipulate data like strings, which may require multiple rows and columns.
A

Two-Dimensional Arrays

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

Traversing Arrays

A
    • When you traverse an array, you examine every element. This is usually necessary for operations such as searching or displaying all elements. There are no shortcuts in this process unless some data structures use optimizations like skipping certain elements.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

Inserting in Arrays

A
    • When you insert a new element into an array, the new data is placed in the specified position, potentially shifting other elements to accommodate the insertion. This operation does not replace any existing element unless explicitly stated.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

2D Array Storage Efficiency

A
    • In 2D arrays, every row typically needs to have the same number of elements. If not all rows need the same amount of storage, this can result in wasted memory.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

Efficiency of Insertion/Deletion in Arrays

A
    • Operations like insertion and deletion in arrays may require moving multiple elements, which can be time-consuming, especially with large arrays. This affects their efficiency.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

Manipulating Linked Lists

A
    • Unlike arrays, linked lists do not support direct index-based access. To find or modify an element, you need to traverse the list starting from the head, which involves following the pointers between nodes.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

Arrays and Nodes

A
    • Arrays are collections of elements, whereas linked lists are collections of nodes, where each node contains a data element and a reference (or pointer) to the next node in the sequence.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

Data Storage in Lists

A
    • Linked lists can store simple or complex data types. Each node may hold various types of data, including objects or structures, making them more flexible in terms of data storage.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

Node Structure in Linked Lists

A
    • Each node in a linked list, except the last one, points to the next node. The last node typically contains a null reference or pointer, indicating the end of the list.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

Memory Management in Linked Lists

A
    • Linked lists are dynamic structures and allocate memory from a specific area called the heap. This means the memory for each node is allocated as needed during runtime.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
38
Q

Node Placement in Memory

A
    • Unlike arrays, nodes in a linked list are not necessarily placed in contiguous memory locations. The nodes can be scattered across different memory addresses, with each node storing a reference to the next one.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
Q

Pointers in Linked Lists

A
    • Linked lists are implemented using pointers or references. Each node stores a pointer to the next node in the list, allowing traversal and manipulation of the list structure.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
40
Q

Traversing Linked Lists

A
    • To access or search for data within a linked list, traversal is required. This involves moving from one node to the next by following the pointers.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
41
Q

Sorting in Linked Lists

A
    • When sorting a linked list, comparison of data occurs between nodes. Depending on the sorting method, either the data itself or the node pointers are adjusted to arrange the nodes in order.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
42
Q

Efficiency of Insertion at the End

A
    • Inserting a node at the end of a linked list often involves traversing the entire list to find the last node. This can take time, especially for long lists, unless a tail pointer is maintained.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
43
Q
  1. Node Insertion Time Complexity When a node is inserted at the end of a linked list, how many nodes are examined, and what is the time complexity of this operation?
A

To insert a node at the end of a linked list, you need to traverse the entire list to find the last node. This requires examining n nodes, where n is the number of nodes in the list.

Therefore, the time complexity of inserting a node at the end of a linked list is O(n), or linear time. This means that the time taken for this operation increases linearly with the number of nodes in the list.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
44
Q
  1. Traversal Speed
    Describe the performance characteristics of traversing through all elements in a linked list. Is it considered fast or slow, and why?
A

Linked lists are slower than arrays due to indirect memory access and cache misses. However, they are efficient for insertions and deletions at the beginning or middle.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
45
Q
  1. Direct Access of Elements Can elements in a linked list be accessed directly? What does direct access mean in terms of linked lists?
A

No, elements in a linked list cannot be accessed directly. Linked lists use sequential access, which means you must start at the beginning and follow pointers to reach a specific element. This is slower than direct access in arrays.

46
Q
  1. The Tail Node What is the significance of the tail node in a linked list? How does the link pointer in the last node behave, and what symbolic value is used to mark the end?
A

The tail node in a linked list is the last node.Its link pointer is null to indicate the end. Having a reference to the tail node improves performance for adding or removing elements at the end. null. This indicates that there are no more nodes following the tail node.

47
Q
  1. Circular LinkedList In a circular linked list, what happens to the pointer in the tail node? Where does it point, and how is this different from a regular linked list?
A

In a circular linked list, the tail node’s pointer points back to the head, forming a loop. This is different from a regular linked list where the tail pointer is null.

48
Q

– concealing details from outside world

A

Data Encapsulation (Info Hiding)

49
Q

– separation of data specification and its implementation

A

Data abstraction

50
Q

– collection of objects,

A

Data type

51
Q

– stores and organizes data in a computer

A

Data structure

52
Q

– description of data structure + association operation

A

ADTs

53
Q

DATA STRUCTURE OPERATION

A
  • Traversing – accessing each record once
  • Searching – finding the location of a value
  • Inserting – adding new records
  • Deleting – removing a record
54
Q
  • accessing each record once
A

traversing

55
Q
  • finding the location of a value
A

searching

56
Q
  • adding new records
A

inserting

57
Q
  • removing a record
A

deleting

58
Q
  • elements form a sequence
  • Eg. Array, stack, queue, linked list
A

Linear Data Structure

59
Q
  • data w/ hierarchical relationships between elements
  • Eg. Tree, graphs
A

Non-linear data structure

60
Q

arrange datas in ascending/descending order

A

sorting

61
Q
  • reduce size
A

compression

62
Q
  • designed for digital signal processing
A

fast fourier transforms

63
Q
  • used for encryption of data
A

encoding

64
Q
  • identifies geometric shapes
A

geometric

65
Q
  • compares image and shapes
A

pattern matching

66
Q
  • identifies different programming constructs
A

parsing

67
Q

CLASSIFICATION

A
  • iterative
  • divide and conquer
  • greedy
  • back tracking
68
Q
  • certain steps are repeated in loops until the goal is achieved (sorting an array)
A

iterative

69
Q
  • a given problem is fragmented into sub-problems which are solved partially; terminated when further sub-division cannot be performed; used for searching and sorting
A

divide-and-conquer

70
Q
  • an immediately available best solution at each step is chosen; used for scheduling and graph theory
A

greedy

71
Q
  • all possible solutions are explored, until the end is reached and then the steps are traced back; useful in graph theory (dept first seasrch, breadth first search; used frequently for traversing trees)
A

back tracking

72
Q

 quick insertion, very fast access if index is known
 slow search, slow deletion, fixed size

A

Array

73
Q

 Quicker search than unsorted array
 Slow insertion and deletion, Fixed size

A

Ordered array

74
Q

 Provides last-in first-out access
 Slow access to other items

A

Stack

75
Q

 Provides first-in first-out access
 Slow access to other items

A

Queue

76
Q

 Quick insertion and quick deletion
 Slow search

A

Linked list

77
Q

 Quick search, insertion and deletion if tree remains balance
 Deletion algorithm is complex

A

Binary trees

78
Q

 Very fast access if key known, Fast insertion
 Slow deletion, access slow if key not known, inefficient memory usage

A

Hash table

79
Q

 Fast insertion, deletion. Access to largest item
 Slow access to other items

A

Heap

80
Q

 Models real world situation
 Some algorithms are slow and access

A

Graph

81
Q

– collection of homogenous, ordered and finit set of elements
 direct access to elements
 have fixed size, more memory, slow deleting and inserting (shifting to the left)

A

Array

82
Q
  • range of values
A

index set

83
Q
  • arrangement of data elements
A

storage structure

84
Q
  • address of the first element
A

base address

85
Q
  • counts the no. of nodes
A

ListLength()

86
Q

– scanning the list of size n

A

Time Complexity [O(n)]

87
Q

– creating temp. variable

A

Space Complexity [O(1)]

88
Q

OUTPUT TRACING
head = Data1 -> Data2 -> Data 3
Set current = head
WHILE current is not NULL
Display current.data + “ -> “
current = current.next
END WHILE

A

Data1 -> Data2 -> Data3 -> NULL

89
Q

Set head = Data1 -> Data2 -> Data3
// create a new node
newNode.data =NewData // this is a value
newNode.next = head
// update the head pointer to point to the next node
head = newNode

A

newNode -> Data1 -> Data2 -> Data3 -> NULL

90
Q

Set head = Data1 -> Data2 -> Data3
// create the new node
newNode.data = NewData
// traverse to the node just before position p (p-1)
Set current = head
i = 1
WHILE I < p-1 AND current is not NULL
current = current.next
i = I + 1
END WHILE
// insert the new node by updating pointers
IF current is not NULL
newNode.next = current.next
current.next = newNode
END IF

A

Data1 -> Data2 -> NewData -> Data3 -> NULL

91
Q

Set head = Data1 -> Data2 -> Data3
// check if the first node is not empty
IF head is not NULL
head = head.next
END IF

A

Data2 -> Data3 -> NULL

92
Q

Set head = Data1 -> Data2 -> Data3
// check if the list is not empty and has more than one node
IF head is not NULL AND head.next is not NULL
Set current = head
Set previous = NULL
// Traverse the list until you find the node to delete
WHILE current is not NULL AND current.value != targetValue
Set previous = current
Set current = current.next END WHILE
// If the node is found IF current is not NULL
// Update the previous node’s next pointer to skip the current node
previous.next = current.next
// Delete the current node (node to be deleted)
delete current
END IF
**

A

Data1 -> Data3

DELITING THE MIDDLE NODE

93
Q

Set head = 15 <-> 7 <-> 40
// create new node
newNode.data = NewData
IF head is NULL
head = newNode
newNode.left = NULL
newNode.right = NULL
ELSE
head.left = newNode
newNode.right = head
newNode.left = NULL
head = newNode
END IF

A

newNode <-> 15 <-. 7 <-> 40

INSERTING BEFORE THE HEAD DLL

94
Q

// Input new node
newNode.data = NewData
Set head = 15 <-> 7 <-> 40
temp = head
// traverse to the last node
WHILE tempT is not NULL
temp = tempt.right
END WHILE
temp.right =newNode
newNode.left = tempt
IF head is NULL
head = newNode
newNode.left = NULL
newNode.right = NULL
ELSE
temp = head
WHILE temp.right is not NULL
temp = temp.right
END WHILE
temp.right = newNOde
newNode.left = temp
newNode.right = NULL
END IF

A

15 <-> 7 <-> 40 <-> newNode

INSERTING AFTER THE TAIL DLL

95
Q

Input newNOde, positionNOde
temp = head
WHILE temp != positionNOde
temp = temp.right
END WHILE
newNOde.right = temp.right
newNOde.left = temp
IF temp.right != NULL
Temp.right.left = newNOde
Temp.right = newNOde

A

INSERTING IN BETWEEN DLL

96
Q

temp = head
head = head.right
IF head != NULL
head.left = NULL
END IF

A

DELETING THE FIRST NODE DLL

97
Q

temp = head
WHILE temp != NULL
temp = temp.right
END WHILE
temp.left.right = NULL
dispose temp

A

DELETING THE LAST NODE DLL

98
Q

temp.left.right = temp.right
IF temp.right != NULL
temp.right.left = temp.left
END IF
Dispose temp

A

DELETING AN INTERMEDIATE NODE DLL

99
Q

. Initialize head to NULL
2. Create a new node (newNode)
3. 3. If the list is empty (head == NULL):
a. Set head = newNode
b. Set newNode.next = head // link to itself since it’s circular
4. Else:
a. Set temp = head
b. Traverse the list until temp.next == head // find the last node
c. Set temp.next = newNode // link last node to new node
d. Set newNode.next = head // link new node to head to complete the circle

A

INSERTING NODE AT THE END CLL

100
Q

. Create a new node (newNode) 2. If the list is empty (head == NULL): a. Set head = newNode b. Set newNode.next = head // new node points to itself 3. Else: a. Set temp = head b. Traverse the list until temp.next == head // Find the tail node c. Set newNode.next = head // New node points to current head d. Set temp.next = newNode // Tail node points to new node e. Set head = newNode // Update head to the new node

A

INSERTING NODE AT THE FRONT CLL

101
Q
  1. If the list is empty (head == NULL): a. Print “List is empty” 2. Else if head.next == head: // Only one node in the list a. Set head = NULL // Remove the only node 3. Else: a. Set temp = head b. Traverse the list to find the second-to-last node (temp.next.next == head) c. Set temp.next = head // Second-to-last node points to head
A

DELETING THE LAST NODE CLL

102
Q
  1. If the list is empty (head == NULL): a. Print “List is empty” 2. Else if head.next == head: // Only one node in the list a. Set head = NULL // Remove the only node 3. Else: a. Set temp = head b. Traverse the list to find the tail node (temp.next == head) c. Set temp.next = head.next // Tail node points to the second node d. Set head = head.next // Update head to the second node
A

DELETING THE FIRST NODE CLL

103
Q

declaring numbers = [1, 3, 7, 1, 7, 5, 1, 9]
declaring count = 0
for each number in numbers do
if number == 1 then
count += 1
endif
endfor
print count

A

3

104
Q

declaring numbers = [12, 35, 1, 10, 34, 1]
for k in range(0, numbers.length -1):
if numbers[k] < numbers[k + 1]:
numbers[k], numbers[k + 1] = numbers[k + 1], numbers[k]
second_largest_num = numbers[1]
print second_largest_num

A

34

105
Q

declaring numbers = [1, 2, 2, 3, 4, 4, 5]
initializing num_sole as an array
for each number in numbers do
if number is not on num_sole:
append number to num_sole
print num_sole

A

[1, 2, 3, 4, 5]

106
Q

declaring numbers = [10, 20, 30, 40, 50]
set first = numbers[0]
for j from 0 to length of numbers – 2 do
numbers[j] = numbers[j+1]
endfor
numbers[length of numbers – 1] = first
print numbers

A

[20,30,40,50,10]

107
Q

declaring numbers = [10, 20, 30, 40, 50]
set is_sorted = true
for j from 0 to length of numbers – 2 do
if numbers[j] > numbers[j+1] then
set is_sorted = false
endif
endfor
if is_sorted then
print “true”
else
print “false”
endif

A

true

108
Q

Pseudo Code: Pseudo Code:
Set head = 5 -> 10 -> 15 -> NULL
Create newNode with value 20
Set temp = head
WHILE temp.next is not NULL
Set temp = temp.next
END WHILE
Set temp.next = newNode
Set newNode.next = NULL
Set temp = head
WHILE temp is not NULL
PRINT temp.value
Set temp = temp.next
END WHILE

A

5 -> 10 -> 15 -> 20 -> NULL

109
Q

Set temp = head
WHILE temp.value is not ‘B’
Set temp = temp.next
END WHILE
Set temp.prev.next = temp.next
IF temp.next is not NULL
Set temp.next.prev = temp.prev
END IF
Set temp = head
WHILE temp is not NULL
PRINT temp.value
Set temp = temp.next
END WHILE

A

A <-> C <-> NULL

110
Q

Set head = 10 -> 20 -> 30 -> 10 (circular)
Create newNode with value 40
Set temp = head
WHILE temp.value is not HEAD
Set temp = temp.next
END WHILE
Set newNode.next = temp.next
Set temp.next = newNode
Set temp = head
WHILE temp is not head
PRINT temp.value
Set temp = temp.next

A

10 -> 20 -> 30 -> 40 -> 10

111
Q

Set head = John -> Alice -> Bob -> NULL
Set temp = head
IF head.value is ‘Alice’
Set head = head.next
ELSE
WHILE temp.next.value is not ‘Alice’
Set temp = temp.next
END WHILE
Set temp.next = temp.next.next
END IF
Set temp = head
WHILE temp is not NULL
PRINT temp.value
Set temp = temp.next
END WHILE

A

John -> Bob -> NULL

112
Q

Set head = A -> B -> C -> D -> A (circular)
Set temp = head
IF head.value is ‘C’
Set head = head.next
ELSE
WHILE temp.next.value is not ‘C’
Set temp = temp.next
END WHILE
Set temp.next = temp.next.next
END IF
Set temp = head
DO
PRINT temp.value
Set temp = temp.next
WHILE temp is not head

A

A -> B -> D -> A (circular)