×
Log in to StudySoup
Get Full Access to SUNY - CPS 310 - Study Guide
Join StudySoup for FREE
Get Full Access to SUNY - CPS 310 - Study Guide

Already have an account? Login here
×
Reset your password

cps 310

cps 310

Description

School: SUNY College at New Paltz
Department: CPS
Course: Data Structures
Professor: Brian murphy
Term: Summer 2016
Tags:
Cost: 50
Description: CMP 338 TEST Each problem is worth 5 pts
Uploaded: 08/25/2017
2 Pages 241 Views 0 Unlocks
Reviews



5) What is the reason that we used a dummy node at the head and tail of many of our linked list implementations?




Why wouldn’t this happen if you were implementing pop for a Stack?




b) What is the equivalent postfix expression?



CMP 338 TEST Each problem is worth 5 pts. PART I 1) Given: 5 + 3 * ( 6 - 2 / 3 ) + 4 a) Trace the infix evaluation algorithm algorithm. b) What is the equivalent postfix expression? c) Very briefly explain the process you followed in the If you want to learn more check out Explain what a wavelength is.
Don't forget about the age old question of Enumerate the composition of matter.
Don't forget about the age old question of siddhartha study guide
If you want to learn more check out cs10 dartmouth
Don't forget about the age old question of how are organic molecules broken down by catabolic pathways
If you want to learn more check out How does one consider gender roles in developing marketing ads and campaigns?
trace. 2) List and briefly describe the public methods of the Stack ADT. List and briefly describe the public methods of the Queue ADT. 3) Write the code for the dequeue method of a Queue class implemented with an array.  Include any supporting declarations from the Queue class.  After many enqueue, dequeue operations would your queue lose access to the array? How many? Why?  Why wouldn’t this happen if you were implementing pop for a Stack? 4) Explain the circumstances under which a linked list implementation of a stack is superior to an array implementation. Explain the circumstances under which an array implementation of a stack is superior to a linked list implementation. PART II 5) What is the reason that we used a dummy node at the head and tail of many of our linked list implementations? Why didn't we do this for the linked list implementation of the Stack or Queue? 6) Write the two methods push and pop for a linked list implementation of a stack. 7) a)When devising an algorithm for linked lists, why must you be careful about the order in which you change the references?  b)Why doesn't binary search on a Linked List Structure run in O (lg n) time, but instead in O (n) time?  c)What does the code current = current.next; as related to Linked List Structures do?  d) Draw two versions of an empty linked list, one with dummy nodes and one without.  e) How would you determine in code that each of the lists in 7d are empty? 8) Write a method that inserts an int into an ordered list that is implemented as a linked list. PART III 9) Given the following list of values: 47, 83, 56, 30, 12, 67, 35, 25, 80, 61 a) Draw the binary search tree that would evolve by inserting the values into the tree in the order in which they are presented. b) Draw the array representation of this binary search tree. c) In what order would you insert the values so as to get a complete binary search tree? d) In what order would you insert the values so as to get an array implementation of a binary search tree to require the maximum  number of array elements? e) How many array elements would be needed for the array described in part d? 10) Describe what do each of the following int binary search tree methods do: a) public BTN x (int a) {  if ((a > data) && (right != null)) return right.x (a);  if ((a < data) && (left != null)) return left.x (a);  return this; } b) public void y (int a) {  BTN n = x (a);  if (a > n.data) n.right = BTN (a);  if (a < n.data) n.left = BTN (a); } 11) Write an insert method for a binary search tree implemented using linked nodes.  12) a) What advantages do binary search trees have over linked lists and linear arrays for implementation of an   ordered list ADT? In your explanation use worst case time complexities to make your case.PART IV 13) Given the following list of inputs: 47, 83, 56, 30, 12, 67, 35, 25, 80, 61 a) Trace the development of the heap in abstract form that would evolve by inserting the inputs in the order that they are  presented. b) Draw the final version of the array representation of this heap, i.e. you need not show the array develop. c) What property of a heap led to the array being smaller than that of the binary search tree in problem 9b. 14) Write a remove function for a heap class as well as any support functions that are called by your remove function. 15) Given the following list of values: 43, 21, 34, 25, 58, 12, 44 Trace the steps of applying heapsort using both an array and a linked structure representation for the trace. 16) a) What is the worst case time complexity of heapsort, mergesort, and bubblesort? b) Why might you choose to use heapsort over mergesort and why choose mergesort and heapsort over bubble sort? c) When developing the code for heapsort in class, what did we notice towards the end concerning how we could use the array   containing the list that allowed our code to achieve the benefit you just mentioned in problem16b?  d) How do you find the children of a node in the array in terms of the arithmetic involved?  e) How do you find the parent of a node in the array in terms of the arithmetic involved? PART V 17) In the coin flipping game, discussed in class and appearing in your text, a graph was presented to solve   the problem. a) What did each of the vertices represent? b) What did each of the edges represent? c) List three algorithms that could be used to determine whether the game is winnable. Explain how you would apply one of these three algorithms to make this determination. d) In terms of the coin game, what can be determined by applying Dijkstra's algorithm to its graphical representation and how  would you apply the algorithm in order to get the above mentioned desired result? For problems 18-20 refer to the adjacency matrix for a graph shown on the board. 18) Represent the graph as a linked structure and as an edge list. 19) Trace both a breadth first traversal and a depth first traversal starting from v0.   Be sure to indicate which traversal is which. 20) Trace Dijktra's algorithm starting from v0. Explain how you would determine the shortest path from v0 to v5.

Page Expired
5off
It looks like your free minutes have expired! Lucky for you we have all the content you need, just sign up here