CC4 Midterms Flashcards
(112 cards)
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
2
Q
o Example: A recipe that tells you exactly how to bake a cake, one step at a time.
A
Algorithm
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
4
Q
o Example: Integers (e.g., 1, 2, 3) are data types that represent whole numbers.
A
Data Types
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
6
Q
o Example: Arrays, Linked Lists, Stacks, and Queues.
A
Data Structure
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)
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)
9
Q
- : Data is arranged in a linear sequence (e.g., Arrays, Lists).
A
Linear Data Structure
10
Q
- : Elements are arranged in a hierarchy or graph, such as Trees and Graphs.
A
Non-Linear Data Structure
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
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.
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
14
Q
o Example: If an algorithm needs to store additional arrays or temporary variables, its space complexity increases.
A
Space Complexity
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
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.
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
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.
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.
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.
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
22
Q
- Example: A 2D array can be visualized as a table with rows and columns (e.g., a chessboard layout).
A
Multidimensional Arrays
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
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.
25
**size of an array**
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
26
**Array Bounds**
4. - 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).
27
**Deleting Items from Arrays**
5. -: When an element is removed from an array, the elements that follow are usually shifted to fill the gap, maintaining the sequence of elements.
28
6. - 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.
**Two-Dimensional Arrays**
29
**Traversing Arrays**
7. - 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.
30
**Inserting in Arrays**
8. - 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.
31
**2D Array Storage Efficiency**
9. - 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.
32
**Efficiency of Insertion/Deletion in Arrays**
10. - 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.
33
**Manipulating Linked Lists**
11. - 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.
34
**Arrays and Nodes**
12. - 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.
35
**Data Storage in Lists**
13. - 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.
36
**Node Structure in Linked Lists**
14. - 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.
37
**Memory Management in Linked Lists**
15. - 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.
38
**Node Placement in Memory**
16. - 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.
39
**Pointers in Linked Lists**
17. - 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.
40
**Traversing Linked Lists**
18. - 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.
41
**Sorting in Linked Lists**
19. - 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.
42
**Efficiency of Insertion at the End**
20. - 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.
43
21. **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?
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.
44
22. **Traversal Speed**
Describe the performance characteristics of traversing through all elements in a linked list. Is it considered fast or slow, and why?
**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.
45
23. **Direct Access of Elements** Can elements in a linked list be accessed directly? What does direct access mean in terms of linked lists?
**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
24. **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?
**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
25. **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?
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
– concealing details from outside world
**Data Encapsulation (Info Hiding)**
49
– separation of data specification and its implementation
**Data abstraction**
50
– collection of objects,
**Data type**
51
– stores and organizes data in a computer
**Data structure**
52
– description of data structure + association operation
**ADTs**
53
**DATA STRUCTURE OPERATION**
* Traversing – accessing each record once
* Searching – finding the location of a value
* Inserting – adding new records
* Deleting – removing a record
54
- accessing each record once
**traversing**
55
- finding the location of a value
**searching**
56
- adding new records
**inserting**
57
- removing a record
**deleting**
58
- elements form a sequence
- Eg. Array, stack, queue, linked list
**Linear Data Structure**
59
- data w/ hierarchical relationships between elements
- Eg. Tree, graphs
**Non-linear data structure**
60
arrange datas in ascending/descending order
**sorting**
61
- reduce size
**compression**
62
- designed for digital signal processing
**fast fourier transforms**
63
- used for encryption of data
**encoding**
64
- identifies geometric shapes
**geometric**
65
- compares image and shapes
**pattern matching**
66
- identifies different programming constructs
**parsing**
67
**CLASSIFICATION**
* iterative
* divide and conquer
* greedy
* back tracking
68
- certain steps are repeated in loops until the goal is achieved (sorting an array)
**iterative**
69
- 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
**divide-and-conquer**
70
- an immediately available best solution at each step is chosen; used for scheduling and graph theory
**greedy**
71
- 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)
**back tracking**
72
quick insertion, very fast access if index is known
slow search, slow deletion, fixed size
**Array**
73
Quicker search than unsorted array
Slow insertion and deletion, Fixed size
**Ordered array**
74
Provides last-in first-out access
Slow access to other items
**Stack**
75
Provides first-in first-out access
Slow access to other items
**Queue**
76
Quick insertion and quick deletion
Slow search
**Linked list**
77
Quick search, insertion and deletion if tree remains balance
Deletion algorithm is complex
**Binary trees**
78
Very fast access if key known, Fast insertion
Slow deletion, access slow if key not known, inefficient memory usage
**Hash table**
79
Fast insertion, deletion. Access to largest item
Slow access to other items
**Heap**
80
Models real world situation
Some algorithms are slow and access
**Graph**
81
– 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)
**Array**
82
- range of values
**index set**
83
- arrangement of data elements
**storage structure**
84
- address of the first element
**base address**
85
- counts the no. of nodes
**ListLength()**
86
– scanning the list of size n
**Time Complexity [O(n)]**
87
– creating temp. variable
**Space Complexity [O(1)]**
88
**OUTPUT TRACING**
head = Data1 -> Data2 -> Data 3
Set current = head
WHILE current is not NULL
Display current.data + " -> "
current = current.next
END WHILE
Data1 -> Data2 -> Data3 -> NULL
89
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
newNode -> Data1 -> Data2 -> Data3 -> NULL
90
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
Data1 -> Data2 -> NewData -> Data3 -> NULL
91
Set head = Data1 -> Data2 -> Data3
// check if the first node is not empty
IF head is not NULL
head = head.next
END IF
Data2 -> Data3 -> NULL
92
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
**
Data1 -> Data3
**DELITING THE MIDDLE NODE**
93
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
newNode <-> 15 <-. 7 <-> 40
**INSERTING BEFORE THE HEAD DLL**
94
// 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
15 <-> 7 <-> 40 <-> newNode
**INSERTING AFTER THE TAIL DLL**
95
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
**INSERTING IN BETWEEN DLL**
96
temp = head
head = head.right
IF head != NULL
head.left = NULL
END IF
**DELETING THE FIRST NODE DLL**
97
temp = head
WHILE temp != NULL
temp = temp.right
END WHILE
temp.left.right = NULL
dispose temp
**DELETING THE LAST NODE DLL**
98
temp.left.right = temp.right
IF temp.right != NULL
temp.right.left = temp.left
END IF
Dispose temp
**DELETING AN INTERMEDIATE NODE DLL**
99
. 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
**INSERTING NODE AT THE END CLL**
100
. 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
**INSERTING NODE AT THE FRONT CLL**
101
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
**DELETING THE LAST NODE CLL**
102
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
**DELETING THE FIRST NODE CLL**
103
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
3
104
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
34
105
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
[1, 2, 3, 4, 5]
106
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
[20,30,40,50,10]
107
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
true
108
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
5 -> 10 -> 15 -> 20 -> NULL
109
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 <-> C <-> NULL
110
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
10 -> 20 -> 30 -> 40 -> 10
111
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
John -> Bob -> NULL
112
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 -> B -> D -> A (circular)
