# Data Structures

Computing

## Quiz 12 :Sorting

Question Type
Proceed as in Problem 15, but for the recursive function level() in Exercise 23.
Free
Essay

Problem Plan:
BST.h
• BST.h file is referred from the book
o Add the function "generateBST()" to BST.h file
• Declare the "num" variable with the value of random with module by 26 as an integer.
• Declare the "item" variable for the upper case letter.
• Form the binary search tree if the given "item" is less than root place it in left side or greater than root means place it in right side of the root.
o Add the function "TreeLevel()" to BST.h file
• Define the function "TreeLevel()" for to check the level of nodes
• Get the Boolean variable for assign the found or not found
• loop until 'fnd' is 'true' and pointer is not null
• If pointer node is "null" assign Boolean variable as "false" that is not found
• If pointer node is greater than 'i' value then increment the left level value
• If pointer node is less than 'i' value then increment the right level value
• Otherwise return 0
Main.cpp:
• Define "main()" function
o Create the object for BST
o Check the BST is empty or not
o Call the "generateBST()" to generate and insert the alphabet randomly
o Print the object
o Get level of the tree element using the function "TreeLevel()"
o Print the level
Program:
/ **********************************************************
* Program to test the function level iteratively *
********************************************************** /
BST.h:
/ / include required header files
#include
#include
#ifndef BINARY_SEARCH_TREE
#define BINARY_SEARCH_TREE
template
/ / declare the class named 'BST'
class BST
{
public:
/ / constructor
/ / refer the functions in the book from the pages
/ / 675, 679, 684, 671, 673
/ / Declaration of generateBST()
void generateBST();
/ / Declare TreeLevel() function
int TreeLevel(const DataType i);
/ / access specifier
private:
/ / declare the class named 'BinNode'
class BinNode
{
/ / access specifier
public:
/ / declaration of the objects
DataType data;
BinNode * left;
BinNode * right;
/ / constructor
BinNode()
: left(0), right(0)
{}
/ / parameterized constructor
BinNode(DataType item)
: data(item), left(0), right(0)
{}
};
/ / declaration of the object
typedef BinNode * BinNodePointer;
/ * refer the below functions search2(), inorderAux(), graphAux() from the book from the pages 686, 672, 674 * /
/ / declare the object for BinNodePointer
BinNodePointer myRoot;
};
template
/ / constructor for the class BST
inline BST ::BST()
: myRoot(0)
{}
template
/ / function definition for 'empty()'
inline bool BST ::empty() const
{
return myRoot == 0;
}
template
/ *
refer the function definition for 'search()' from the book
refer the function 'insert()' from the book of page 679
function definition for the function 'TreeLevelAux()'
Defection of TreeLevelAux() with parameters
* /
template
int BST ::TreeLevel(const DataType i)
{
/ / Declare the variables
bool fnd = false;
int c = 0;
BST ::BinNodePointer p = myRoot;
/ / loop until 'fnd' is true and pointer is not null
while (!fnd p != 0)
{
/ / check 'i' is less than pointer data
if (i p- data)
{
/ / increment count as 1
c++;
/ / move pointer to left
p = p- left;
}
/ / check 'i' is greater than pointer data
else if (i p- data)
{
/ / increment 'count' as 1
c++;
/ / move pointer to right
p = p- right;
}
/ / assign 'fnd' as true
else
fnd = true;
}
/ / if found is true return c
if (fnd)
return c;
/ / otherwise return -1
else
return -1;
}
/ / Definition of generateBST()
template
inline void BST ::generateBST()
{
/ / assign num value as random which modules by 26.
int num = rand() % 26;
/ / assign item values as Upper letter.
char item = static_cast ('A' + num);
BST ::BinNodePointer
/ / assign the locptr value as myroot
locptr = myRoot,
/ / assign parent value as zero.
parent = 0;
/ / set found equal to false.
bool found = false;
/ / check item found and pointer is not null
while (!found locptr != 0)
{
/ / assign parent value as locptr
parent = locptr;
/ / check item is less than data
if (item locptr- data)
/ / then, assign locptr as locptr left value
locptr = locptr- left;
/ / Check item is less than right of node pointer
else if (locptr- data item) / / descend right
/ / move the pointer to right
locptr = locptr- right;
else
/ / item is found
found = true;
}
if (!found)
{
/ / construct node containing item
locptr = new BST ::BinNode(item);
/ / Check empty tree
if (parent == 0)
myRoot = locptr;
/ / Insert item to left of parent
else if (item parent- data)
parent- left = locptr;
/ / Insert item to right of parent
else
parent- right = locptr;
}
else
cout "Item already in the tree\n";
}
/ *
refer the function definition for 'remove()' from the book
refer the function definition for 'inorder()' from the book
refer the function definition for 'graph()' from the book
refer the function definition for 'search()()' from the book
refer the function definition for 'inorderAux()' from the book
refer the function definition for 'graphAux()' from the book * /
#endif
Main.cpp:
/ / Includes required header files
#include
using namespace std;
#include "BST.h"
/ / Definition of main
int main()
{
/ * Create object for BST and check the BST is empty or not * /
BST chBST;
cout "Constructing empty BST\n";
cout "BST " (chBST.empty() ? "is" : "is not") " empty\n";
/ / Insert the element to the BST
cout "\nInsert the element into the BST.";
int num;
/ / Get number of elements count
cout "\n\nEnter how many elements";
cin num;
/ / Generate the random characters
for (int i=0;i
{
chBST.generateBST();
}
cout endl;
char ch;
/ / Display the BST
chBST.graph(cout);
/ / Get any Tree element from the user
cout "Enter any character";
cin ch;
/ / Find the tree level
int a=chBST.TreeLevel(ch);
cout "\n\n\nThe level of tree :" a;
cout "\n\n";
}
Sample Output:
Constructing empty BST
BST is empty
Insert the element into the BST.
Enter how many elements10
Y
U
Q
P
M
H
G
E
A
Enter any characterE
The level of tree :3

Tags
Choose question tag
Write a driver program to test the recursive linearSearch() function from Exercise 8.
Free
Essay

Program plan:
Here in the above, the function "Linear_search" are declaring with the following the arguments:
• Declare the required variables.
• Include "if" statement to check the loc is equal to n, return false.
• Then, "else if" to check "a[loc]" is equal to "x", return
• Then "else" make recursion for the function through itself.
• Define the main program
o Declares the required variables
o Display to get the values
o Get the elements using the loop
o Calling the function
o Display the position of the element
o Return the location
Program:
/ **********************************************************
* Driver Program to test the recursive "linearSearch()" * * function *
********************************************************** /
/ / include the required header files
#include
#include
/ / define the capacity size
#define capacity 20
using namespace std;
/ / include Linear_search function with the argument
int Linear_search(int a[], int x, int n, bool found, int loc)
{
/ / initials the i
int i = n;
/ / assign the item into an array
a[i] = x;
/ / check the loc equal to n
if (loc == n)
return found = false;
/ / else if check the array element equal to x
else if (a[loc] == x)
return found = loc != n + 1;
/ / then
else
/ / performed recursion function
return Linear_search(a, x, n, found, loc=loc+1);
}
/ / define the main program
int main()
{
/ / declares the required variables
int a[capacity], n, x, loc = 0;
bool found = false,flag;
/ / display to get the values
cout "How many elements?";
cin n;
cout "\nEnter elements of the array\n";
/ / get the elements using the loop
for (int i = 0;i
cin a[i];
cout "\nEnter element to search:";
cin x;
/ / calling the function
flag = Linear_search(a, x, n, found, loc);
if (flag == true)
/ / display the position of the element
cout "\nElement is found ";
else
/ / return the location
system("pause");
return 0;
}
Sample Output:
How many elements? 5
Enter elements of the array
3
6
9
5
2
Enter element to search: 9
Element is found.

Tags
Choose question tag
Write a driver program to test the linear search function for move-ahead-one self-organizing array-based lists in Exercise 12.
Free
Essay

Program plan:
• Include "Linear_search" function with the argument
o initials the variable
o Declare an array
o While to check whether condition
o Check "if" loc is equal to searching value
o Set as true
o Increment the loc
o Declare a loop to check the loc.
o Perform an interchanging of the elements.
o Assign the "a[i]" to decreased order
o Assigning the value
o Check "if" is found
o Then, display
o Displaying the moved to the front value.
• Define the main program
o Declares the required variables
o Display to get the values
o Get the elements using the loop
o Calling the function
o Then return zero
Program:
/ **********************************************************
* Driver Program to test the move-ahead-one * * self-organizing ********using array based linearSearch * * function *
********************************************************** /
/ / include the required header files
#include
#include
/ / define the capacity size
#define capacity 20
using namespace std;
/ / include Linear_search function with the argument
int Linear_search(int a[], int x, int n, bool found, int loc)
{
/ / initials the variable
int i , temp;
/ / declare an array
assert(n
loc = 0;
/ / while to check whether condition
while (!found loc
{
/ / check "if" loc is equal to searching value
if (a[loc] == x)
/ / set as true
found = true;
/ / increment the loc
else
loc++;
}
if (!found)
{
/ / declare a loop to check the loc
/ / perform an interchanging of the elements.
for (i = 0; i
temp = a[0];
a[0]=x;
a[i]=temp;
}
/ / if is found
if(found)
/ / then, display
cout "\n Element is found at position " loc;
else
{
/ / Displaying the moved to the front value.
for (i = 0;i loc + 1;i++)
cout a[i];
cout "\n Element is added at the first position";
}
/ / return loc value
return loc;
}
/ / define the main program
int main()
{
/ / declares the required variables
int a[capacity], n, x, loc = 0;
bool found = false;
/ / display to get the values
cout "How many elements?";
cin n;
cout "\n Enter elements of the array\n";
/ / get the elements using the loop
for (int i = 0;i
cin a[i];
cout "\n Enter element to search:";
cin x;
/ / calling the function
Linear_search(a, x, n, found, loc);
cout endl;
/ / pause the screen
system ("pause");
/ / return 0
return 0;
}
Sample Output:
How many elements? 5
Enter elements of the array
6
3
2
1
4
Enter element to search: 8
832146
Element is added at the first position
How many elements? 5
Enter elements of the array
5
3
2
1
6
Enter element to search: 3
Element is found at position 1

Tags
Choose question tag
Write a driver program to test the linearSearch() function for ordered lists in Exercise 7.
Essay
Tags
Choose question tag
Write a driver program to test the linear search function for move-to-the-front self-organizing array-based lists in Exercise 10.
Essay
Tags
Choose question tag
Write a definition for the following function generateBST() for generatinga binary search tree containing uppercase letters inserted in a random order: BST generateBSTO; / *------------------------------------- Generate a BST with uppercase letters 'A'-'Z' inserted in random order.Precondition: None.Postcondition: A BST containing uppercase letters inserted in random order has been generated and returned.--------------------------------------* /
Essay
Tags
Choose question tag
Write a driver program to test the interpolation-search function in Exercise 14.
Essay
Tags
Choose question tag
Repeat Problem 11, but also include interpolation search (see Exercise 14).
Essay
Tags
Choose question tag
Write a driver program to test the linear search function for move-to-the-front self-organizing linked lists in Exercise 11.
Essay
Tags
Choose question tag
Test the function level() in Exercise 22 by using generateBST() of Problem 14 to generate BSTs and then determine the level of 'A', 'B',…, 'Z' in each tree.
Essay
Tags
Choose question tag
Linear search is not practical for large lists because the search time becomes unaccept-ably large. In a dictionary, this problem is alleviated by providing thumb cutouts that allow direct access to the beginnings of sublists, which can then be searched. Imitating this approach, we might break a long list into a number of sublists and construct an index array of these sublists. Write a program to read records from StudentFile (described at the end of Chapter 4) and store them in an array of sublists of names beginning with 'A', 'B', 'C', … The program should then accept a name and retrieve the record for this student.
Essay
Tags
Choose question tag
Test the function inorder() of Exercise 26. Generate binary trees using the function generateBST() in Problem 14, and then traverse them using inorder().
Essay
Tags
Choose question tag
Linear search outperforms binary search for small lists. Write a program to compare the computing times of linear search and binary search.
Essay
Tags
Choose question tag
Test the function levelByLevel() of Exercise 27. Generate binary trees using the function generateBST() in Problem 14, and then traverse them using levelByLevel().
Essay
Tags
Choose question tag
Test the function leaf Count() from Exercise 25. Generate binary trees using the function generateBST() in Problem 14, display them using displayPreOrder() (see Exercise 21), and then count the leaves using leafCount().
Essay
Tags
Choose question tag
Writea driver program to test the linear search function for move-ahead-one self-organizing Jinked lists in Exercise 13.
Essay
Tags
Choose question tag
Write a driver program to test theimproved linearSearch() function in Exercise 6.
Essay
Tags
Choose question tag
Write a driver program to test the function displayPreOrder() in Exercise 21.
Essay