PART 1
SORTING ARRAYS
Using a program of your choice, Develop a program that asks the user to enter a capital for a
Zambian Province. Upon receiving the user input, the program reports whether the user input is
correct. For this application, the 10 Provinces and their capital cities are stored in a two-
dimensional array in order by Province name. Display the current contents of the array then use a
bubble sort to sort the content by capital. Next, prompt the user to enter answers for all the
province capitals and then display the total correct count. The user's answer is not case-sensitive.
import java.util.Scanner;
public class Test {
/** Main method */
public static void main(String[] args) {
// Create a Scanner
Scanner input = new Scanner(System.in);
// Store 10 provinces and their capitals in a two-dimensional array
String[][] provincesAndCapitals = getData();
int count = 0; // Correct answer
// Repeatedly prompt the user to enter the capital of a province
for (int i = 0; i < provincesAndCapitals.length; i++) {
System.out.print("What is the capital of "
+ provincesAndCapitals[i][0] + "? ");
String capital = input.nextLine();
if (isEqual(provincesAndCapitals[i][1], capital)) {
System.out.println("Your answer is correct");
count++;
else {
System.out.println("The correct answer should be " +
provincesAndCapitals[i][1]);
// Display the total correct count
System.out.println("\nThe correct count is " + count);
/** isEqual returns true if a is equal to c */
public static boolean isEqual(String c, String a) {
if (c.length() != a.length())
return false;
for (int i = 0; i < c.length(); i++) {
if (c.charAt(i) != a.charAt(i))
return false;
return true;
/** getData initializes the array with the 10 provinces and their capitals */
public static String[][] getData() {
String[][] d = {
{"Lusaka", "Lusaka"},
{"Southern", "Livingstone"},
{"Western", "Mongu"},
{"North Western", "Solwezi"},
{"Eastern", "Chipata"},
{"Luapula", "Mansa"},
{"Northern", "Kasama"},
{"Muchinga", "Mpika"},
{"Copperbelt", "Ndola"},
{"Central", "Kabwe"}},
return d;
}
Part 2
(i) Discuss the concepts of Tree Traversing and give examples.
Tree Traversing is a type of graph traversal in the data structure that refers to the process of
visiting, verifying, and updating each node in a tree data structure just once. The order in which
to examine the nodes of the tree is used to classify these traversals.
There are three types of binary tree traversals.
1. In - Order Traversal
2. Pre - Order Traversal
3. Post - Order Traversal
JAVA TRAINING: https://www.javatpoint.com/
(II) Discuss the different practical application of stacks
A Stack is a linear data structure that holds a linear, ordered sequence of elements. It is an
abstract data type.
A Stack can be a fixed specific size, or it can be dynamic, i.e., the Stack size can be changed
dynamically. It can be represented by means of Pointer, Array, Structure, and Linked List.
Application of the Stack
1. A Stack can be used for evaluating expressions consisting of operands and operators.
2. Stacks can be used for Backtracking, i.e., to check parenthesis matching in an expression.
3. Stacks can also be used to convert one form of expression to another form.
4. Stacks can be used for systematic Memory Management.
STACKS AND APPLICATIONS:
https://byjus.com/gate/stack-and-its-applications/#:~:text=and%20Linked%20List.-,Application
%20of%20the%20Stack,used%20for%20systematic%20Memory%20Management.
(ii) Differentiate the different data structures one from the other specifically in the way
data is inserted and deleted. Use relevant properties for each data structure to
differentiate.
A Data structure is a storage that is used to store and organize data. It is a way of arranging data
on a computer so that it can be accessed and updated efficiently
Types of Data Structures
Data structures are divided into two categories:
Linear data structure
Non-linear data structure
PROGRAMIZ : https://www.programiz.com/dsa/data-structure-types
Difference between Linear and Non-linear Data Structures:
Linear Data Structure Non-linear Data Structure
In a linear data structure, data elements
1 are arranged in a linear order where each In a non-linear data structure, data elements
. and every element is attached to its are attached in hierarchically manner.
previous and next adjacent.
2 In linear data structure, single level is Whereas in non-linear data structure,
. involved. multiple levels are involved.
3 Its implementation is easy in comparison While its implementation is complex in
. to non-linear data structure. comparison to linear data structure.
While in non-linear data structure, data
4 In linear data structure, data elements
elements can’t be traversed in a single run
. can be traversed in a single run only.
only.
While in a non-linear data structure,
5 In a linear data structure, memory is not
memory is utilized in an efficient way.
. utilized in an efficient way.
6 Its examples are: array, stack, queue,
While its examples are :trees and graphs.
. linked list, etc.
Applications of linear data structures are Applications of non-linear data structures
7
mainly in application software are in Artificial Intelligence and image
.
development. processing.
Linear Data Structure Non-linear Data Structure
Non-linear data structures are useful for
8 Linear data structures are useful for representing complex relationships and data
. simple data storage and manipulation. hierarchies, such as in social networks, file
systems, or computer networks.
GEEKS PROGRAMMING : https://www.geeksforgeeks.org/difference-between-linear-and-
non-linear-data-structures/
#include <iostream>
#include <queue>
using namespace std;
// Node structure
struct Node {
int data;
Node* left;
Node* right;
Node(int val) {
data = val;
left = NULL;
right = NULL;
};
// Function to traverse binary tree using post-order traversal
void postorderTraversal(Node* node) {
if (node == NULL)
return;
postorderTraversal(node->left);
postorderTraversal(node->right);
cout << node->data << " ";
// Function to add a node to the binary tree
Node* insertNode(Node* node, int val) {
if (node == NULL)
return new Node(val);
if (val < node->data)
node->left = insertNode(node->left, val);
else if (val > node->data)
node->right = insertNode(node->right, val);
return node;
// Function to delete a node from the binary tree
Node* deleteNode(Node* node, int val) {
if (node == NULL)
return node;
if (val < node->data)
node->left = deleteNode(node->left, val);
else if (val > node->data)
node->right = deleteNode(node->right, val);
else {
if (node->left == NULL) {
Node* temp = node->right;
free(node);
return temp;
else if (node->right == NULL) {
Node* temp = node->left;
free(node);
return temp;
Node* temp = node->right;
while (temp->left != NULL)
temp = temp->left;
node->data = temp->data;
node->right = deleteNode(node->right, temp->data);
return node;
}
int main() {
Node* root = new Node(50);
insertNode(root, 30);
insertNode(root, 20);
insertNode(root, 40);
insertNode(root, 70);
insertNode(root, 60);
insertNode(root, 80);
cout << "Binary Tree Traversal (Post-Order): ";
postorderTraversal(root);
cout << endl;
deleteNode(root, 20);
cout << "Binary Tree Traversal (Post-Order) after deleting 20: ";
postorderTraversal(root);
cout << endl;
return 0;
}
Reference
JAVA TRAINING: https://www.javatpoint.com/
STACKS AND APPLICATIONS:
https://byjus.com/gate/stack-and-its-applications/#:~:text=and%20Linked%20List.-,Application
%20of%20the%20Stack,used%20for%20systematic%20Memory%20Management.
PROGRAMIZ : https://www.programiz.com/dsa/data-structure-types
GEEKS PROGRAMMING : https://www.geeksforgeeks.org/difference-between-linear-and-
non-linear-data-structures/
