developed segment of a mock exam paper | My Assignment Tutor

PAST EXAM PAPERCOMPUTER SCIENCE DEPARTMENTThis is a past exam paper or a specially developed segment of a mockexam paper which aims to prepare the students for the real exam. Itshould be noted that: the real exam may have a different structure; the real exam may have a different distribution of marks anddifferent number of choices/options; the real exam will definitely have different questions; the unit lecturer who sets the real exam may be different from thelecturer who set the current paper the content of the unit may vary from the content of the unit whichwas taught when the current paper was developed.We would advise the students to read the past exam carefully and tryto answer the questions, even try to simulate conditions of a realexam setting. We would also strongly suggest to the students to seetheir lecturer if they have any questions or need further clarifications.We wish you success with your examination!!1 (Question Continues)TURN OVERTHE UNIVERSITY OF SHEFFIELDCITY LIBERAL STUDIESBSc (HONS) IN COMPUTER SCIENCE MOCK EXAMLEVEL 2 FINAL EXAMINATIONDuration: 2 Hours CSD2210 – DATA STRUCTURES AND ALGORITHMSAnswer THREE (3) questions only, BOTH questions from Part A and ONE (1)question from Part B. All questions are of equal value.AN APPENDIX IS PROVIDED AT THE END OF THE EXAM PAPERPART A1. a) Describe procedural abstraction. What are the benefits from it? Thoroughlyexplain an example (using pseudo-code) in order to justify your answer.[35%]b) State five aspects of programming that modularity has a favorable impact on.[10%]c) You have been asked to construct a recursive solution to a specific problem.What are the four issues that you must take into consideration whenconstructing the recursive solution?[10%]d) Consider the following recursive method foo:int foo ( int x ) {if ( x < 2 )return 1;else if ( x == 2 )return 2;elsereturn (foo(x-2) + foo(x-1) );}Fill in the values for the following calls to the above method. foo(0)foo(1)foo(2)foo(3)foo(4)foo(5)foo(6) [15%]e) Implement in Java or in detailed pseudocode an additional public methodreverse for the Queue ADT which reverses the order of the elements in aqueue.Hint: You may assume the existence of any ADT seen in the appendix.[30%]TURN OVER2 (Question Continues)TURN OVER2. a) Consider the interfaces of the ADTs provided in the appendix. Assume that wehave instantiated ls, st, and qu as dynamic implementations of the linked list,stack and queue ADTs respectively, and all of them are initially empty. Drawthe contents of the linked list ls, the stack st and the queue qu after theexecution of each line of the following code segment. Make sure you indicatethe head and the tail for the list, the top of the stack and the front and back ofthe queue. If ls, st, and/or qu remain unchanged at a specific step, then donot redraw it.1 ls.insert(14)2 ls.append(10);3 st.push( 13 );4 ls.add(2,35);5 qu.enqueue( 7 );6 st.push( ls.get(2) );7 qu.enqueue( 21 );8 qu.enqueue( st.pop() );9 System.out.println(ls.showFront());10 st.push( st.peek() );11 st.push( qu.dequeue() );[30%]b) Consider the following binary search tree.(i) Show the post-order traversal of the tree[10%](ii) Show the pre-order traversal of the tree[10%](iii) Draw the structure of the tree after the deletion of the node with value 44.[5%]c) Draw the binary search tree that is formed when inserting the values 15, 27,51, 35, 31, 47, 36, 28, 50, 62 in the given order. Consider that the binarysearch tree is initially empty.[10%]444339 697337211758623 (Question Continues)TURN OVERd) Consider the following array of integers. Array indices are shown below thenumbers. 81492733463957537983889691 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13]If we used sequential search, how many comparisons are required in order todetermine if the value 85 is stored in the array? How many comparisons wouldbe required in order to find the value 85 if we used binary search?[10%]e) One of your fellow classmates has decided to implement a priority queue ADTusing a binary search tree as the underlying data structure. Do you believe thatit is an efficient approach? Thoroughly justify your answer and explain theperformance of insertion and deletion operations.[25%]PART B3. a) State the most appropriate abstract data type that can be used for the problemslisted below. Your answer must be one the following ADTs: linked list,ordered linked list, circular linked list, stack, queue, tree, binary tree, binarysearch tree.1. A program for a dictionary. The program reads a word from the user, and outputsthe meaning of that word. The program also allows the user to add his owndefinitions at runtime. At any moment, the user can ask the program to add aword; he enters the word, and the definition, and it becomes part of thedictionary. We would also like to give the user the option to show all the wordsthat start with a certain prefix. For example, the user can enter “cat,” and theprogram shows him all the words that start in the letters “cat.”2. A print spooler (program that accepts print jobs from a network interface andsends them to a printer).3. Hierarchical structure of the departments of a corporation4. A certain part of a card game in which a discard pile is maintained. On any turn, aplayer may discard a single card from his hand to the top of this pile or he mayretrieve the top card from this discard pile.5. A token that constantly passes around a ring topology network.[20%]b) The lecturer of the data structures module has assigned a teamwork practical inwhich you have to create a Java program that manages a monthly to-do list.Each of these to-do items contains a description, a category and if it has beencompleted or not; it does not include a priority, a deadline, or a specificday/time that a specific to-do item is to be take place. The operations to beperformed are insertion of a new to-do item, deletion of a to-do item when it is4 (Question Continues)TURN OVERcompleted, modification of one or more attributes of a to-do item and retrievalof one to-do item, all items or based on the category.One of the members of your team, John Mourmouris, has proposed the use ofan array-based linked list as the underlying data structure, because as he said“we can have very fast access to any item in the list”. Do you agree withJohn’s solution approach and/or his supporting argument? Thoroughly justifyyour answer by explaining possible problems that this solution creates.[25%]c) Provide one example for each one of the following rates of growth with regardto computational complexity.ƒ O(1)ƒ O(n)ƒ O(n2)Your examples can be any method of any ADT that appears in the appendix(static or dynamic implementation), or an algorithm for sorting or searching.Note that you are not required to write any code. Make sure your thoroughlyexplain the environment and any circumstances that your examples require.[30%]d) Suppose that you read a binary string—that is, a string of 0s and 1s—onecharacter at a time. Describe how you could use a stack, but no arithmetic, todetermine whether the number of 0s is equal to the number of 1s. When thesecounts are not equal, state how you could tell which character (0 or 1) occursmost frequently and by how much its count exceeds the other’s.[25%]4. a) (i) Describe what an abstract data type (ADT) is. What is the differencebetween an abstract data type and a data structure? What are the issueswhen creating an ADT and what are the concerns when creating a datastructure?[15%](ii) In a linked-list implementation of a queue what are the abstract data typeand data structures involved?[5%]b) The lecturer of the data structures module has asked you to extend thereference-based, single linked list ADT by implementing a methodmoveToEnd(). This method should move the first item of the linked list to theend of the list by manipulating the ListNodes. One of your fellow classmates5 (Question Continues)TURN OVERhas posted the implementation shown below in the forum of the module’s website.public void moveToEnd() {ListNode firstNode = head;head = head.getNext();tail.setNext(firstNode);tail = firstNode;}Thoroughly discuss the solution provided by your classmate. Do you agreethat this solution successfully moves the first item at the end? Does thesolution create other problem(s)? If yes, what modification(s) need to be madein order to correct the problem(s)?Note: Draw an example linked list in order to explain your answer.[25%]c) Consider the following array of integers. 12193326293522 Trace all the steps that are needed in order to sort the array from lowest tohighest using the insertion sort algorithm. For each step indicate thenumber of comparisons and the number of swaps.[25%]d) The following method foo_bar can be added to the reference-based, singlelinked list ADT. The method assumes that there exist at least two nodes in thelinked list.1 public void foo_bar() {2 ListNode node1 = head;3 tail = head;4 ListNode node2 = node1.getNext();5 node1.setNext(null);67 while (node2 != null) {8 ListNode node3 = node2.getNext();9 node2.setNext(node1);10 node1 = node2;11 node2 = node3;12 }13 head = node1;14 }Consider the following single linked list with nodes A, F, R and M.Memory Addr: 100 Memory Addr: 210 Memory Addr: 140 Memory Addr: 120 A F R M HEAD TAIL6 (Question Continues)TURN OVER(i) Draw the above linked list after the execution of lines 1 through 5 of themethod foo_bar. Make sure that you indicate all the references that areincluded in these five lines.[10%](ii) What is the functionality of the method?[10%](iii) Draw the linked list after the execution of the above foo_bar. Make surethat your drawing includes the memory addresses.[10%]END OF QUESTION PAPER 7public interface Queue{// Determines whether a queue is empty.public boolean isEmpty();// Determines whether a queue is full.public boolean isFull();// Adds an item at the back of a queue.public void enqueue(Object newItem) throws QueueException;// Retrieves and removes the front of a queue.public Object dequeue() throws QueueException;// Removes all items of a queue.public void dequeueAll();// Retrieves the item at the front of a queue.public Object peek() throws QueueException;}INTERFACE FOR THE QUEUE ADT (Question Continues)TURN OVER public interface Stack{// Determines whether the stack is empty.public boolean isEmpty();// Determines whether the stack is full.public boolean isFull();// Removes all the items from the stack.public void popAll();// Adds an item to the top of a stack.public void push(Object newItem) throws StackException;// Removes the top of a stack.public Object pop() throws StackException;// Retrieves the top of a stack.public Object peek() throws StackException;}INTERFACE FOR THE STACK ADT public interface LinkedList{// Determines if the list is emptypublic boolean isEmpty();// Determines the size of the listpublic int size();// Retrieves the element from position indexpublic Object get(int index)throws ListIndexOutOfBoundsException;// Deletes all elements from the listpublic void removeAll();// Adds newDataItem at the beginning of the listpublic void insert(Object newDataItem);// Adds newDataItem at the position index of the listpublic void add(int index, Object newDataItem)throws ListIndexOutOfBoundsException,ListException; ***// Adds newDataItem at the end of the listpublic void append(Object newDataItem);// Returns the front element from the listpublic Object showFront();// Returns the last element from the listpublic Object showLast();// Removes the element at position index from the listpublic void remove(int index)throws ListIndexOutOfBoundsException;// Determines if newDataItem exists in the listpublic boolean exists(Object newDataItem);// Removes & retrieves the front element of the listpublic Object removeFront() throws ListException;// Removes and retrieves the last element of the listpublic Object removeLast() throws ListException;}INTERFACE FOR THE LINKED LIST ADT public class ListNode{public ListNode() {next = null;}public ListNode(Object newItem) {item = newItem;next = null;}public ListNode(Object newItem, ListNode nextNode){item = newItem;next = nextNode;}public void setItem(Object newItem) {item = newItem;}public Object getItem() {return item;}public void setNext(ListNode nextNode) {next = nextNode;}public ListNode getNext() {return next;}}IMPLEMENTATION OF THE LISTNODE CLASS public interface BST{// Determines if the BST is emptypublic boolean isEmpty();// Deletes all nodes of the BSTpublic void clear();// Inserts a new node in the BSTpublic void insert(Object item);// Prints the nodes of the BST in-orderpublic void inOrderTraversal();// Prints the nodes of the BST pre-orderpublic void preOrderTraversal();// Prints the nodes of the BST post-orderpublic void postOrderTraversal();// Deletes a node from the BST if it existspublic void delete( Object item )throws TreeException;// Returns the number of nodes in the BSTpublic int sizeOf();}INTERFACE FOR THE BINARY SEARCH TREE ADT APPENDIX***Note: The first element in a linkedlist is inserted in position 1.


Leave a Reply

Your email address will not be published.