Q1 ANSWER 4 OUT OF 5
Q1a) Define the data
structures.
Q1b) Name three major data
structures and an application for each of the three data structures.
Q1c) Give one example of
static and one example of dynamic data structures.
Q1d) What is recursion and
why is it important? Give an example.
Q1e) What would be the order
of notation for: Bubble sort, quicksort, linear search, binarysearch, and
hashing?
Q1) Write a simple hash
function for the social security number: int hashfun(int ssn)
Q2) Sort the following data
slot[]={8,3,1,5,7,10,4}
Q2a) According to a bubble
sort, show the steps and movement of data.
Q2b) According to the straight selection, show
the steps and movement of data.
Q2c) Indicate one advantage
of bubble sort and one advantage of selection sort that is taken into
consideration in EXSEL sort.
Q2b) Write the function for
either the bubble sort or the straight selection using the following variables.
int tbl[10], i, j, mloc.
Function swap already exists and you don't have to write it.
Q3a) Apply the linear search
with the following data tbl[]={8,3,1,5,7,10,4}, looking for number 7. Show the
steps and the process.
Q3b) Apply the binary search with the
following data tbl[]={1,3,5,7,8,10,12,13}, looking for number 7. Show the steps
and the process.
Q3c) Write a linear search
function using using int linearsearch(int tbl[], int n, int searchkey)
Q3d) Write a recursive binary
search using int binsearch(int tbl[],low,high,searchkey)
Q4a) Build a stack program
with a menu using only the following variables: X, option, mystack[50], and
mytop. Write the main program. The
menu's options are as follows:
1 to push
2 to pop
3 to check if stack is empty
3 to check if stack is full
Q4b) Write the push(int
mystack[],int &mytop, int x) function.
Q4c) Write the the function
int pop(int mystack[], int &mytop).
Q4d) Write the function bool
empty(int mytop)
Q4e) Write the function bool
full(int mytop)
Q5a) Build a queue program
with a menu using only the following variables x, option,myqueue[100],rear and
front
1 to enqueue
2 to dequeue
3 to check if
queue is empty
3 to check if queue is full
Q5b) Write the function
enqueue(int myqueue[],int &rear,int x)
Q5c) Write the function
int dequeue(int myqueue[],int front)
Q5d) Write the function bool
empty(int counter)
Q5e) Write the function bool
full(int counter).
Q6a) Convert the following
infix notation to postfix notation: 9 - 3 *
2
Q6b) Evaluate the
following 9 3
2 * - , by using a stack.
Q6c) Write a function to
evaluate postfix: int evaluate(char
postfix[]).
string postfix contains the
postfix expression. Assume the following function are already existed:
push,pop,empty, isfull, isoperator, operand()
and eval()
Q7) You are to simulate an
Airport with two queues; assume all the following functions and variables
exist: rand, departure queue, arrival queue, dequeue, enqueue, isempty, and
isfull.
DATA
STRUCTURE SOLUTION TEST1 (SAMPLE1)
1a) Define the data
structures: simply it’s a way to organize data.
They are ways in which data is arranged or organized in your computer’s
memory (or stored on a disk). They
contain algorithms, which are procedures a program uses to manipulate the data
in these structures.
1b) Name 3 major data structures and an
application of each:
-
STACK –Provides
last in first out access. examples –
calculator, stack of plates in a cafeteria.
-
QUEUE - provides first in first out access. examples – line of people in a bank, the
lineup of jobs waiting to print in a printer spool, planes arriving and
departing from an airport runway.
-
HASH – a fast
search program of a known element.
examples – a Jersey number on a player, a SSN. Hashing goes right to the location of the
element without having to scan the entire array.
1c) Static - array
- contains memory already known and size iiis determined when the program is
compiled.
Dynamic - Linked list - size is
determined when the program is actually running - uses memory during execution
time.
1d) Recursion - is
when a function calls itself. It is
important in designing certain algorithms.
It’s short and can make some problem solving simpler than doing it
iteratively (looping). Example: the most
common example is Factorial Numbers or power() calculations:
double power ( double x, int n)
{
if (n==0) return 1.0; //any number
x to the 0 power = 1
else return power (x, n-1) * x;}
1e) Order of
notation for the following:
bubblesort (exchange sort) = O(N2)
quicksort (exchange sort) = O(N2)
linear search = O(N)
binary Search =
O(logN)
hash search = O(1) order of one - fastest
Order of preference from
fastest -> slowest:
O(1)
- O(logN) - O(N) - O(N2)
1f) Write a simple
hash function for hashfun(int ssn)
int hashfun (int ssn){
int ssn;
return ssn %10000; }
This
doesn’t allow for collision, but it’s a simple hash function using module to
make the number smaller.
2)
Sort the
following: slot[] = {8,3,1,5,7,10,4}
a)
bubblesort
8 3 1 5 7 10 4
3 8 1 5 7 10 4
3 1 8 5 7 10 4
3 1 5 8 7 10 4
3 1 5 7 8 10 4
3 1 5 7 8 10 4
3 1 5 7 8 4 10
1 3 5 7 8 4 10
1 3 5 7 4 8 10
1 3 5 4 7 8 10
1 3 4 5 7 8 10
1 3 4 5 7 8 10
b)
Selection sort:
8 3 1 5 7 10 4
1 3 8 5 7 10 4
1 3 8 5 7 10 4
1 3 4 5 7 10 8
1 3 4 5 7 10 8
1 3 4 5 7 10 8
1 3 4 5 7 8 10
c)
Advantage of
bubble sort and selection sort in relation to EXSEL sort:
advantage
of bubble sort - if there is no swap in one pass, the data is sorted.
advantage
of selection sort - can place the smallest numbers no matter where they are in
the beginning of the data (SEE chap11).
d)
function for
bubblesort using tbl[10],i,j,mloc
void
bubblesort (int tbl[], int mloc)
{
int mloc=10, i, scan, pass;
for (pass=1; pass<mloc; pass++){
for (scan = 0;
scan<mloc-pass; scan++){
if(tbl[scan]>tbl[scan+1]){
swap (tbl, scan, scan+1);}
}//end
for scan loop
}//end for pass loop
}//end bubblesort function
3a) Apply linear search to
the following looking for 7:
tbl[]={8,3,1,5,7,10,4}
-
what are you
looking for = 7 (n)
-
cin>>n enters
n
-
loop & access
-
compare
-
succeed
-
loop around
-
failure
-
end return;
worst
case and average case O(N).
COMPLETE
PROGRAM AS FOLLOWS:
#include<iostream.h>
linearsearch(int tbl[ ],int searchkey)
{
for(int n=0;
n<14;n++)
if
(searchkey==tbl[n])
return
n;
return -1;
}//end
linearsearch
main()
{
int tbl[]={8,3,1,5,7,10,4};
int searchkey,chosen;
cout<<"Enter the number you
want to search for: ";
cin>>searchkey;
chosen=linearsearch(tbl,searchkey);
if (chosen== -1){
cout
<<"That number you entered " << searchkey << "
" << "is not found. \n";
cout <<
"Please try again." << endl;
}
else
cout<<"The number
you entered " << searchkey << " " <<"was
found." <<endl;
return 0;
}//end
main
3c) linearsearch(int tbl[], int n, int searchkey)
for (n=0; n<14; n++)
if (searchkey == tbl[n])
return n;
else return -1; }
3b) binary search using
tbl[]={1,3,5,7,8,10,12,13}
-
data should be
sorted or sorted to an array
-
look for item in
the middle of the list
-
keep dividing the
list in half until there are no more elements to find
-
either the
element is found - return n;
-
or not found - return -1;
3d) - binary search function:
int binsearch (int tbl[], int low, int high, int
searchkey)
{
int mid;
if (low > high)
{
return -1;
}//end 1st if
mid = (low + high)/2;
if (searchkey == tbl[mid])
{
return mid;
}//end 2nd if
else if ( searchkey < tbl[mid])
{
binsearch (tbl, low, mid-1, searchkey);
}//end else if
else
{
binsearch (tbl, mid+1, high, searchkey);
}
//end else
}//end binsearch function
4a) #include <iostream.h>
void
push (int mystack[], int &mytop, int x)
{ mystack[mytop] = x;
mytop++;
}
int
pop (int mystack[], int &mytop)
{ mytop--;
return mystack[mytop];
}
bool
isfull ( int mytop, const int MAXSIZE )
{ if (mytop == MAXSIZE) return true;
else return false;
}
bool
isempty (int mytop)
{
if (mytop == 0) return true;
else return false;
}
void
main()
{ const int MAXSIZE = 5;
int mystack[MAXSIZE];
int mytop;
int x;
mytop = 0;
char option;
do{ cout
<< "This is a stack program.\n";
cout <<"Please choose
from one of the following options:\n";
cout <<
"1=PUSH\n2=POP\n3=ISFULL\n4=ISEMPTY\n";
cout << "Please enter
your option: ";
cin >> option;
switch (option)
{
case '1':
cout << "Enter a
number to be pushed: ";
cin >> x ;
push (mystack, mytop, x);
break;
case '2':
cout << "Enter number
to be popped: \n"<< pop( mystack,
mytop);
cout<<endl;
break;
case '3':
if(isfull(mytop,
MAXSIZE)==1) cout << "Stack
is full."<< endl;
else cout<< "Stack is
not full."<< endl;
break;
case '4':
if (isempty(mytop)==1) //return true for empty
cout <<
"Stack is empty. Go away!" << endl;
else
cout
<<"Stack isn't empty yet." << endl;
break;
case 'q':
cout
<<"Thank you for playing, menu game is now over. BYE!\n";
cout<< endl;
break;
default:
cout <<"\nInvalid
option entered."
<<"\nYour
options are from 1 - 4 only."
<<"\nPlease
enter correct opitions." << endl;
}//end switch
}// end do
while (option != 'q' || option != 'Q');
}//end main
4b) void push (int mystack[],
int &mytop, int x)
{mystack[mytop] = x;
mytop++;}//end push function
4c) int pop (int mystack[],
int &mytop)
{ mytop --;
return
mystack[mytop];}//end pop function
4d) bool empty(int mytop)
{
if (mytop = = 0) return true;
else return false;}//end empty function
4e) bool full(int mytop, const int MAXSIZE)
{
if (mytop = = MAXSIZE) return true;
else return false;}//end full function
5a) //An example of a Queue
Program
#include <iostream.h>
void enqueue (int myqueue[],
int &rear, int x)
{
myqueue[rear] = x;
rear++;
}//1
int dequeue (int myqueue[],
int &front)
{
front--;
return myqueue[front];
}//2
int isempty (int counter)
{
if (counter==0) return 1;
else return 0;
}//3
int isfull ( int counter, int
MAXSIZE)
{
if (counter == MAXSIZE) return 1;
else return 0;
}//4
void main()
{
const int MAXSIZE = 5;
int myqueue[MAXSIZE];
int rear, front, counter;
int x;
rear = 0;
char option;
do{
cout << "This is a QUEUE
program.\n";
cout <<"Please choose from one of
the following options:\n";
cout <<
"1=Enqueue\n2=Dequeue\n3=Empty\n4=Full\n";
cout << "Please enter your option:
";
cin >> option;
switch (option)
{
case '1':
cout << "Enter a number
Enqueue: ";
cin >> x ;
enqueue(myqueue,
rear, x);
break;
case '2':
cout << "Enter number
to be first: \n"<< dequeue( myqueue,
front);
cout<< endl;
break;
case '3':
if (isempty(counter)==1) //return true for empty
cout
<< "Queue is empty." << endl;
else
cout
<<"Queue has more room." << endl;
break;
case '4':
if (isfull(counter, MAXSIZE)==1)
cout <<
"Queue is full."<< endl;
else
cout<<
"Queue is not full."<< endl;
break;
case 'q':
cout <<"Thank you for
playing, menu game is now over. BYE!\n";
cout<< endl;
break;
default:
cout <<"\nInvalid
option entered."
<<"\nYour
options are from 1 - 4 only."
<<"\nPlease
enter correct options." << endl;
}//end switch
}// end do
while ((option != 'q') || (option != 'Q'));
cout <<"Please choose from one of the
following options:\n";
cout <<
"1=Enqueue\n2=dequeue\n3=ISEMPTY\n4=ISFULL (enter q or Q to quit)\n";
cin >> option;
}//end main
/*
This is a QUEUE program.
Please choose from one of the
following options:
1=Enqueue
2=Dequeue
3=Empty
4=Full
Please enter your option: 3
Queue has more room.
This is a QUEUE program.
Please choose from one of the
following options:
1=Enqueue
2=Dequeue
3=Empty
4=Full
Please enter your
option: */
5b) int enqueue (int myqeue[], int &rear, int
x)
{ myqueue[rear] =
x;
rear ++;}
5c)int dequeue (int myqueue[], int &front)
{
front -- ;
return
myqueue[front] ; }
5d) bool empty (int counter) {
if (counter = =0) return true;
else return false; }
5e) bool full (int counter, int MAXSIZE) {
if (counter = = MAXSIZE) return true;
else return false; }
