|
CS210 - Algorithms and Data Structures I Department of Computer Science National University of Ireland, Maynooth |
|
|
CS210 - Algorithms and Data Structures I Department of Computer Science National University of Ireland, Maynooth |
T Naughton, NUIM
Back to CS210 home
Laboratory Exam 1
The following questions are representative of the questions that will appear on the exam. Pseudocode with comments is sufficient for full marks.
Section I: Iteration and arrays.
Problems [A] [B] [C] [D] [E] [F] [G] [H]
If you need to create a new array you could use
int tempA[] = new int[5]; // new array of length 5
for example.
Section II: Stacks and queues.
Problems [P] [Q] [R] [S] [T] [U] [V] [W] [X] [Y] [Z]
For these problems, assume that the code is already written for a stack object (that holds integers) called s. Assume also that it includes the functionality for the well known stack operations clear(), push(int e), pop(), and isEmpty() (you may assume that the stack can never be overfilled). Use syntax as follows: push a onto the stack with "s.push(a)", clear the stack with "s.clear()", etc. Here is an example program.
Example A Write a function that takes an int stack and two integers as arguments and pushes both integers onto the stack.
void example(MyStack s, int a, int b) {
/* This function pushes both a and b (in that
** order) onto s.
*/
s.push(a);
s.push(b);
}
The same assumptions will hold where a queue is called for. Assume the queue operations clear(), enqueue(int e), dequeue(), and isEmpty() are supported.
In solving Section II problems your data structures are restricted to counter variables, stacks, and queues. You may not declare arrays to hold the elements of stacks/queues. You could use
int counter; // used to count from 1 to n
int temp; // a single variable to tempoarily store an element
MyStack tempS = new MyStack(); // new empty stack, no fixed size
MyQueue tempQ = new MyQueue(); // new empty queue, no fixed size
for example.
Problem A Write a function that takes an array of ints and returns the smallest value found in the list. If the list is empty, then return -1. Your function should have the following format.
int example(int list[]) {
/* This function returns the smallest int found in list[].
** If the list has no elements, return -1.
*/
// Your code here
}
Problem B Write a function that takes an array of ints and returns the largest value found in the list. If the list is empty, then return -1. Your function should have the following format.
int example(int list[]) {
/* This function returns the largest int found in list[].
** If the list has no elements, return -1.
*/
// Your code here
}
Problem C Write a function that takes an array of ints and returns the index of the largest value found in the list. If two or more indexes have this property, return the largest index. If the list is empty, return -1. Your function should have the following format. [Java solution]
int example(int list[]) {
/* This function returns the index of the largest int in list.
** If there are multiple occurances of this int we return the
** highest index. If the list has no elements, return -1.
*/
// Your code here
}
Problem D Write a function that takes an array of ints and returns the index of the largest value found in the list. If two or more indexes have this property, return the smallest index. If the list is empty, return -1. Your function should have the following format. [Java solution]
int example(int list[]) {
/* This function returns the index of the largest int in list.
** If there are multiple occurances of this int we return the
** lowest index. If the list has no elements, return -1.
*/
// Your code here
}
Problem E Write a function that takes an array of ints and prints out the indexes of the first two duplicate integer values found in the list. If no duplicates are found then print an appropriate message. Your function should have the following format. [Java solution]
void example(int list[]) {
/* This function prints out the indexes of the first two duplicates
** found in list. The user is notified if no duplicates are found.
*/
// Your code here
}
Problem F Write a function that takes an integer array as an argument and returns true if the array is a palindrome, and false if it is not. (A palindrome reads the same backwards as it does forwards -- {1,2,2,1} and {21,2,21} are palindromes, {1,1,2,1} is not.) If the array is empty, return true. Your function should have the following format.
boolean example(int list[]) {
/* This function returns true if list[] is empty or
** is a palindrome, else returns false.
*/
// Your code here
}
Problem G Write a function that takes an integer array list[] as an argument and returns a newly created array that only contains the odd valued integers from list[]. If there are no odd integers in list[] return an array of length zero. Your function should have the following format. [Java solution]
int [] example(int list[]) {
/* This function returns a newly created array containing
** the odd integers from list[]. If there are no integers
** in list[] return an array of length 0.
*/
// Your code here
}
Problem H Write a function that takes an integer array list[] and a positive integer n as arguments and returns a newly created array that only contains the last n integers of list[]. If there are no integers in list return an array of length zero. Your function should not change list[] and should have the following format. [Java solution]
int [] example(int list[], int n) {
/* This function returns a newly created array containing
** the last n integers from list[]. If there are no integers
** in list[] return an array of length 0.
*/
// Your code here
}
Problem P Write a function that takes an int stack and an int queue as arguments and prints out the contents of the queue in reverse. [Java solution]
void example(MyStack s, MyQueue q) {
/* This function uses stack s to print queue q in reverse.
*/
// Your code here
}
Problem Q Write a function that takes an int stack and an int queue q as arguments and returns a queue containing the elements of q in reverse order. [Java solution]
MyQueue example(MyStack s, MyQueue q) {
/* This function uses s to return a queue
** containing the elements of q in reverse.
*/
// Your code here
}
Problem R Write a function that takes an int stack s and an integer n as arguments, and prints out the first n elements that had originally been pushed onto the stack. Assume that s contains more than n elements. When your function has finished the stack should be empty and only the last n elements to be popped off the stack should be on the screen. [Java solution]
void example(MyStack s, int n) {
/* This function prints the first n elements pushed onto s.
** On exit, s will be empty.
*/
// Your code here
}
Problem S Write a function that takes an int queue q as an argument, and returns the queue with the order of its elements reversed.
MyQueue example(MyQueue q) {
/* This function reverses a queue.
*/
// Your code here
}
Problem T Write a function that takes a char queue q of characters as an argument, and returns true if the queue contains matching brackets, otherwise false. Each brackets will be either '(', ')', '[', or ']'. The queue will contain other symbols besides brackets. Non-bracket symbols are to be ignored by the function. [Java solution]
boolean example(MyQueue q) {
/* This function checks if the queue contains matching
** brackets. Possible brackets are '(', ')', '[', ']'.
** Ignore all other symbols.
*/
// Your code here
}
Problem U Write a function that takes an int queue q and an integer n as arguments, and prints out the first n elements that had been originally entered into the queue. Assume that q contains more than n elements.
void example(MyQueue q, int n) {
/* This function prints the first n elements in queue q.
*/
// Your code here
}
Problem V Write a function that takes an int queue q and an integer n as arguments, and prints out the last n elements of the queue. Assume that q contains more than n elements. [Java solution]
void example(MyQueue q, int n) {
/* This function prints the last n elements in queue q.
*/
// Your code here
}
Problem W Write a function that takes an int queue q and an integer n as arguments, and returns a new queue containing the first n elements of q in a reverse order to the order that they had appeared in q. For example if q contains {3, 6, 9, 5, 7} and n is 3, return a queue with {9, 6, 3}. If q contains less than n elements, return a queue with all elements reversed.
MyQueue example(MyQueue q, int n) {
/* This function returns in reverse the first n elements of q.
*/
// Your code here
}
Problem X Write a function that takes an int queue q and an integer n as arguments, and returns a new queue containing the last n elements of q in the same relative order as they they had appeared in q. For example if q contains {3, 6, 9, 5, 7} and n is 3, return a queue with {9, 5, 7}. If q contains less than n elements, return a queue with the elements unchanged. [Java solution]
MyQueue example(MyQueue q, int n) {
/* This function returns (in order) the last n elements of q.
*/
// Your code here
}
Problem Y Write a function that takes an int queue q as an argument, and returns a queue containing (in reverse) every third element of q starting with the last element. For example, if q contains {a, b, c, d, e} then a queue containing {e, b} should be returned. [Java solution]
MyQueue example(MyQueue q) {
/* This function returns a queue containing the reverse of
** every third element of q.
*/
// Your code here
}
Problem Z Write a function that takes a char queue q as an argument, where the queue contains a selection of alphabet symbols {a, .., z} and some `+' symbols. The function should print to the screen the two characters that precede (come before) every occurance of `+' in the queue. For example, if q contains {a, b, c, +, e, e, e, +, f, g, +, p} then "cbeegf" should be printed to the screen. Assume that at least 2 alphabet symbols precede each `+' symbol.
void example(MyQueue q) {
/* This function prints out the two symbols preceding each '+'.
*/
// Your code here
}