1.Assume alist is a list of the integers {50, 15, 20, 45, 35, 10, 5}. For parts (a) and (b), display the order of elements in alist after calling f();
template < typename T>
void f(list< T> &alist, T item)
{ queue< T> q;
list< T>::iterator iter = alist.begin();
while (iter != alist.end())
if (*iter > item)
{
q.push(*iter);
alist.erase(iter++);
}
else
iter++;
while (!q.empty())
{
alist.push_back(q.front());
q.pop();
}
}
(a)List after calling f(alist, 30).
(b)List after calling f(alist, 12).
2.Assume an array implementation of a queue with a maximum size of 5. Initially, the queue has the characters 'A', 'B', 'C', and 'D'. Draw pictures of the initial array contents and then the contents after each queue operation. Identify the front and rear positions in each picture.
3.Use the following doubly linked list. Give the data value for the node referenced by each pointer value.
Figure: see image.
(a)p->next
(b)q->prev->prev
(c)header->next->next
(d)p->next->prev
(e)q->next->next
4. Trace the function f() and use it to modify elements in a linked list.
template < typename T>
void f(node< T> * & front)
{ node< T> *prev, *curr, *p;
if (front != NULL || front->next != NULL)
{
curr = front->next;
prev = front;
do
{ p = curr->next;
curr->next = prev;
if (p != NULL)
{ prev = curr;
curr = p;
}
}
while (p != NULL);
front->next = NULL;
front = curr;
}
}
Assume a linked list has the following five elements
9 -> 30 -> 17 -> 4 -> 20
front
Give the order of the elements that occur after calling f().
5. (a)What is the runtime efficiency for inserting a node in a singly linked list?
(b)What is the runtime efficiency for deleting a node in a singly linked list?
(c)What is the runtime efficiency for locating the last node in a singly linked list?
6.Assume the declaration
node< char> *p, *q, *r;
After executing the following statements, what is the order of the data values in the resulting list?
p = new node< char> ('A');
q = new node< char>('B');
r = new node< char>('C');
p->next = r;
r->next = q;
7.Which of the following lists represent a possible inorder scan of a binary search tree.
(a) 7 3 8 2 9 4 11
(b) 2 3 4 7 8 9 11
(c) 11 2 9 3 8 4 7
(d) All of the above
8.(a) Display the binary search tree formed by entering the characters in the specified order
P, T, V, Z, S, F, C
(b)Using the tree from (a), give the NLR scan of the nodes.
(c) Using the tree from part (a), give the LNR scan of the nodes.
(d) Using the tree from part (a), give the RNL scan of the nodes.
9.For each of the following, create a binary search tree that contains the characters:
(a)M, T, J, R, G, D
(b)F, W, X, A, B, M, T, R
10.Trace the following tree scan function and describe its action.
template < typename T>
int treeFunc(tnode< T> *t)
{ int n = 0, left, right;
if (t != NULL)
{ if (t->left != NULL)
n++;
if (t->right != NULL)
n++;
left = treeFunc(t->left);
right = treeFunc(t->right);
return n + left + right;
}
else
return 0;
}
(a) identifies the number of leaf nodes in the tree
(b) identifies the number of nodes in the tree
(c) identifies the number of edges in the tree
(d) identifies the depth of the tree.
11. Use the following tree that combines both operators and operands. The tree is called an expression tree. see image.
(a)Give the postorder scan of the tree
(b)Give the inorder scan of the tree
(c)Assuming the values are integers and the operators follow C++ definitions, evaluate the expression:
12.The template class freq has data members value and count where value represents an item and count indicates the frequency of the item in a collection.
Class Declaration
template < typename T>
class freq
{
public:
// constructor
freq(T v, int ct = 1);
// increment the frequency by +1
void increment();
// comparison operators compare value attributes
friend bool operator< (const freq< T>& a, const freq< T>& b);
friend bool operator< = (const freq< T>& a, const freq< T>& b);
// access member functions
T getValue() const;
int getCount() const;
private:
T value;
int count;
};
Parts (a) - (b) explore elements of a program that declares a set of freq objects and uses elements from an array of integers to insert and update the freq objects in the set.
int arr[] = {6, 3, 3, 9, 4, 9, 6, 9, 3};
(a)Declare s to be a set of freq objects whose values are integers.
(i)set< freq, int> s;
(ii)set< freq< int> > s;
(iii)freq< set< int> > s;
(iv)set< freq> s< int>;
(b)Complete the loop that inserts a new freq object in the set for the first occurrence of a value in the array or updates the count of an existing freq object if the array value is a duplicate.
for (int i = 0; i < 9; i++)
if ((sIter = s.find(arr[i])) == s.end())
_________________________ // select the code
(i) s< freq< int> >.insert(arr[i]);
(ii) s.insert(freq(arr[i]));
(iii) s.insert(arr[i]);
(iv) s.insert(freq< int>(arr[i]));
else
_________________________ // select the code
(i) (*sIter).increment();
(ii) *(sIter).increment();
(iii) s.increment(*sIter);
(iv) s.increment(sIter);
13.Let map m store key value pairs where the key component is an integer item and the value component is the frequency of the value in a collection. The integer array arr defines a list of nine elements.
int arr[] = {6, 3, 3, 9, 4, 9, 6, 9, 3};
map< int, int> m;
Complete the loop that scans the elements in the array and adds a new entry in the map for the first occurrence of a value and increments the value component for a duplicate value.
for (int i = 0; i < 9; i++)
_________________________
// select from choices (i) through (iv)
(i) m(arr[i]) = (m(arr[i]) > 1) : m(arr[i])++ ? 1;
This would have been valid if m is accessed using square braces and not parenthesis. So answer is none of the above.
(ii) m[arr[i]] += 1;
(iii) m[arr[i]++];
(iv) None of the above
14.Use the following sequence of integer values.
8, 1, 5, 3, 16, 18, 7, 33, 9, 15, 22, 10
(a)Build the 2 - 3 - 4 tree.
(b)Convert the resulting 2 - 3 - 4 tree to a red-black tree.
15.Use the integer hash function hf(x) = x and table size 11. Using chaining with separate lists, show the location in the hash table for each integer value in the following sequence.
5, 19, 43, 38, 63, 96, 44, 65