Student Exam Questions


Objective:

The objective is to give students the opportunity to design part of their final exam. In doing so, exam questions submitted by students will be made public. Students will be allowed to study from these knowing that a subset will appear on the final exam.

Rules:

  1. All students are required to submit 1 question prior to 12:00 (noon) July 3rd.
  2. If an insufficient pool of questions is not compiled (30 questions minimum) then the instructor has the right to revoke this offer.
  3. Questions submitted by students can compose up to 66% of the marks on the exam, provided a sufficient pool of questions exist.
  4. Questions must be based on material covered in Cosc 2p03, from the first lecture to material up to and including Test 2.
  5. Questions must be robust, questions which are not robust in content may be rejected by the instructor. This ensures that academic quality is maintained.
  6. Questions accepted, will be posted below, along with the students name who submitted the question.
  7. Accepted questions will be posted in a timely fashion by the instructor.
  8. Individual who's question has been rejected will be notified via email. Individuals will then need to resubmit.
  9. The instructor has the right to augment questions to more accurately represent the intent.
  10. The instructor has the right to change the data used by the question on the exam script. E.g. if the question says use data x, then the instructor can say use data y instead.
  11. The instructor has the right to add questions to cover topics not covered by students. This ensures that topics such as complexity get their fair shake on the exam. You can't avoid a topic, because you don't like it.
  12. Duplicate questions will be rejected. First come first serve.

Suggestions:

  1. Consider looking at old tests and exams.
  2. Consider questions from the text book(s).
  3. Programming questions are difficult to compose, and mark. If the question deals with programming, ensure that the code required is relatively short, and that the solution set is relatively few.  In short, do not ask a questions in which there could be many unique solutions.
  4. Question can make use of multiple topics.
  5. There is nothing wrong with thinking type questions.
  6. A 5 mark question should take 5 to 10 minutes to complete.
  7. A 10 mark question can take anywhere from 10 to 20 minutes to complete.
  8. No question should take more then 20 minutes to complete.

Submission Guidelines.

  1. You can submit your question via email to bockusd@sandcastle.cosc.brocku.ca.
  2. Subject should be 2p03 Exam Question
  3. If the question can be described as text then a plain text email will do.
  4. If the question requires a graphic or you just prefer to use a word processor then please submit it as a word document.
  5. The email message should contain your proper name and student number.

Questions:
Rany Audeh
 The Question covers Complexity and Recursion ( 5 Marks ):
a.(2 Marks) Express the complexity of the following code using Big-O notation. Explain how you reached your answer.
 
for ( i = 1 ; i <=  n ;i ++ ){
   if ( a[i] > 0 ){
      for ( j = 0 ; j< n ; j= j+2)
         c[i] = c[i] / b[i] ;
    }
    else
     c[i] = b[i] ;
 }
 
b.(3 Marks) Express the complexity of the following code using Big-O notation. Explain how you reached your answer. What is the value returned if n = 8 initially?
 
 private int method1(int n){
     if ( n = = 1 ) return 1;
     else return method1(n/2) +n ;
  }/method1    

Dmytro Bernevek
 a) Using the following data crate an AVL tree
[24, 32, 29, 10, 26, 9, 47, 51]

b) Delete node '47' from the tree and then delete node '26' from the tree.
Redraw the tree after every deleton. Do not forget about AVL property after
each deletion.
Janine Imada
 part (a) (5 marks)
 
Convert this CBT into a min heap: [2 5 7 4 9 3 6 8 2].  Redraw the tree after each swap.
 
part (b) (3 marks)
 
Explain, in general terms, how heapsort is applied to a min heap.  Be sure to include a diagram of the array in your answer.
John Athanassiades
 (6 Marks) Given the following input data: [S Y T W A B] create a BST. As the tree is built, you are required to thread the tree so that a S.O.T. can be performed (Recall the 2 Rules from our lecture notes when doing this). In the space below, redraw the tree after EACH insertion showing the state of the threads.
Steven Barkovic
 Using the following data, 10 6 11 25 23 20 2 9 7 27 1, construct a BST. 
Delete the following nodes from the tree 1 9 25.  Redraw the tree after each
deletion.  Determine the average path length before each node is deleted and
after each node is deleted.
Willie Reynolds
 Question covers contiguous storage and binary trees:
 
1 mark - definition - What is contiguous storage??
 
1 mark - Show student a tree and get them to represent it as contiguous storage. 
                ie. Show them Example tree in Dave's notes and must represent this as
                        contiguous storage.
 
Given [ a,b,g,c,f,h,i,d,e]:
 
1 mark:  Calculate the parent of i.
 
1 mark:  Calculate the left child of b.
 
1 mark:  Calculate the right child of g.
Mwinchande Othman Chande
 1) a) Given the following numbers create a BST
      8,5,15,2,7,11,17,1,6,13.  (2 Marks)

   b) write out the order in which the nodes visited for postorder,
      inorder, preorder traversal for the BST you created.
      (3 Marks)

   c) Draw and label a diagram of the contiguous memory representation of
      the tree in part a. (2 Marks)

   d) Show the predecessor and successor threads if the tree in part a was
      to be threaded for a preorder and inorder traversal. (3 Marks)
Keita Muto
 Given algorithms f and g where: f(p) = 10p^2 + 45p - 20 and g(p) = 35p +

40, where p is the problem size:

1) At what problem size p is algorithm f and g computationally equivalent?


2) If p was 20, which algorithm should be used? Explain why?
Geordie Harris
 Given the DAG  complete the following:

Give the output when you apply a Top Sort to the graph.

Do the same using a stack for output.
Justin Kalicharan
 Given the CBT [r, t, w, p, v, s, z, b]

create a max heap based on the lexicographic properties of the data. Show all steps as a separate tree.
Joel Glanfield
 When considering traversing a tree, we have 3 options: S.O.T., Post-
Order, and Pre-Ordered traversals.
1) If we wanted to thread a tree after it has been built, which type of
traversal would we need to use if we wanted left and right threads?
2) Which type of traversal would not allow a tree to be completely threaded
and why?
Mike Sawyer
 Define a min-heap and a max-heap?

and

Build a heap from this list of numbers(2,4,5,3,6,8,7,9,10), give the
final tree representation and give the final array representation of
this heap.
Darryl Gough
 In point form, discuss the advantages and disadvantages of the following
terms or concepts as they pertain to computer data structures.

Recursion    vs.    Iteration
BST        vs.    Sorted Array
Node Deletion from BST    vs.    Soft (lazy) Deletion from a BST
Robert Blacklock
 Given 'head' pointing to a linked list contarining an integer value 'count'
and a node pointer 'next'. Write a method, which uses link inversion to
print out in reverse order.