how does the process look likePage | 1 CSE 100 Final Exam Spring 2019 Total points: 130 out of...

Question

how does the process look likePage | 1  CSE 100 Final Exam  Spring 2019 Total points: 130 out of 135.5 (i.e. 5.5 extra credit points)  This exam is closed book, closed notes. By signing your name below, you are asserting that all work on this exam is yours alone, and that you will not  provide any information to anyone else taking the exam.  In addition, you are agreeing that you will not discuss  any part of this exam with anyone who is not currently taking the exam in this room at any point.  This includes  posting any information about this exam on Piazza or any other social media.  Discussing any aspect of this exam  with anyone outside of this room constitutes a violation of the academic integrity agreement for CSE 100. Signature: ______________________________________________ Name (please print clearly):________________________________________ PID:___________________________________________ Your assigned seat: _______________________________________ Your section (8am or 9:20am): _________________________ DO NOT OPEN THIS EXAM UNTIL YOU ARE INSTRUCTED TO DO SO. Page | 2  Problem 1 (9 pts): C++ coding. Suppose we have a C++ Node class as the follows. The data of this node is a  vector pointer.   a) (6 pts). Given the following constructor, please complete the destructor for this class so valgrind will output no  leaks are possible.   b) (3 pts). If a main function is written as the follows and we assume that the destructor is written correctly, does the code  have a memory leak? Just answer yes or no. You don’t have to justify your answer.                                                                                     Your answer: ________________________________ Problem 2 (15 pts) RB-Tree. Insert the following data into an RB tree (in the exact same order as given from left to  right) and answer the questions below. When describing a node, make sure you state its color as well as its value (such as  (10, red)). You have to use the approach we discussed in class to perform the insertions. You should draw your tree on  the scratch paper. There is no partial credit.   Insert data: 10, 20, 30, 15, 12, 14, 13  a) (2 pts). What is the root of the RB tree: ______________________ b) (4 pts). What are the two children of the root? left child: _______________, right child: _______________  c) (4 pts). List all the leaves of the tree (nodes whose children are only   black nils)? ______________________________  ______________________________________ d) (2 pts). What is the color of 14? __________________________ e) (3 pts). If we insert 16 into the existing tree, draw the resulted   tree in the space to the right. Use double border to indicate   red nodes, and single border for black nodes. #include   using namespace std;  class Node{    vector* data;    Node* left;    Node* right;    Node* parent; public:    Node(int size);    ~Node();  }; Node::Node(int size){    data = new vector();    for (int i = 0; i push_back(new int);    }    left = nullptr;    right = nullptr;    parent = nullptr;  }  Node::~Node(){//complete this destructor } int main(int argc, char** argv){    Node n(10);    Node* ptr = new Node(5);  }  Answer for 2. part e) Page | 3  Problem 3 (11 pts) Priority Queue. We are trying to model airplanes at an airport and each airplane is modeled by its  arrival time and departure time.   class Airplane{  public:          int arr;          int depart;          Airplane(int arrival, int departure);          bool operator, AirplanePtrCmp> pq;   //Insert data into the priority queue. It is omitted here.   //Complete this part of the code to go through the priority queue and print out (arrival,  departure) time for all airplanes in the pq. } Page | 4  Problem 4 (7 pts) KD trees. Build a KD tree with the following data. When you build the tree, pick the first level as the y  level and it alternates afterwards.   a). Build the tree with the following data and then answer the following questions (16, 7), (14, 6), (13, 1), (17, 5), (11, 2), (12, 4), (15, 3) i). What is the root of the tree? ______________________________________ ii). List all the nodes at the x level: _____________________________________ iii). How many leave nodes are there? _____________________________ b). If we search for node (12, 8) using the KD tree from a), list all the nodes that will be traversed in the order  that they are traversed. ________________________________________________________________________    Problem 5 (11 pts): Multi-way trie and TST. Build the required trie for each sub-problem using the words given. The  words are given in the insertion order from left to right. Use a bold or double border to indicate the end of word node.  Your trie will be graded on the correct location of a word so there is no partial credit. Be careful.  a) (5 pts). Build a MWT with the following words: 123, 11, 32, 22. 321. You should assume that there are only 3  unique symbols: 1, 2, and 3. b) (6 pts). Build a TST to store the following words: applet, apple, app, apps, rich, rig, rock Page | 5  Problem 6 (6 pts): BFS and DFS.  Given the following graph in the adjacency matrix form, answer the following questions about BFS and DFS (in the form  that we discussed in class). We assume that when there are multiple nodes to explore, BFS and DFS will equeue or push  the vertex with smaller index onto the queue or stack, respectively. BFS and DFS will only explore nodes that have not  been explored before. DFS will push all the un-explored children of the newly popped node, as discussed in class.  0 1 0 1 0  1 0 1 0 1  0 1 0 1 1  1 0 1 0 1  0 1 1 1 0 a) (2 pts). Run the BFS algorithm that we discussed in class starting from vertex 0. List the enqueue order (start from V0).  ___________________________.   b) (4 pts). Run the DFS algorithm starting from vertex 3. Note that V3 is the first node to be pushed.  List the nodes in the order that they got pushed on the stack: _____________________________________  List the nodes in the order that they got popped from the stack: ________________________________  Problem 7 (13 pts): Huffman Encoding  The distribution of 5 symbols are the following: A – 0.2, B – 0.2, C – 0.2, D – 0.2, E – 0.2.   a) (9 pts). We will first build the Huffman tree. When two nodes are merged together, the new node will assume the  symbol of the right child. The first node dequeued is the right child, and the second node dequeued is the left child. When  two nodes have the same frequency, the smaller the symbol is in ASCII, the higher the priority the node has. When we try  to determine the encoding for each symbol, the left child edge is 0 and the right child edge is 1. When you describe a  node, list both its symbol and frequency (e.g. (A, 0.2)). Answer the following questions about the tree you built.   i) (1 pt). What is the symbol for the root: _________________  ii) (2 pts). Which leaves are the lowest level (not all leaves, just the leaves furthest away from the root):_____________  ________________________________________________  iii) (1 pt). What is the parent of (E, 0.2): ____________________________  vi) (3 pts). What is the encoding for symbol C: __________, Symbol A: ____________, symbol D: ________________  v) (2 pts). What is average bit length of this encoding (you can leave your answer as expressions):  _________________________________  b) (2 pts). What is the optimal average

Page | 1 CSE 100 Final Exam Spring 2019 Total points: 130 out of XXXXXXXXXXi.e. 5.5 extra credit points) This exam is closed book, closed notes. By signing your name below, you are asserting that all...

Get Answer To This Question

Related Questions & Answers

Submit New Assignment