=========================preview======================
(COMP2012)[2011](s)final~=9eu_^_33792.pdf
Back to COMP2012 Login to download
======================================================
THE HONG KONGUNIVERSITY OF SCIENCE & TECHNOLOGY
Department of Computer Science & Engineering
COMP 152: Object-Oriented Programming and Data Structures
Spring 2011
Final Examination
Instructor: Albert Chung (L1) / Long Quan (L2) / Gary Chan (L3)
Date: Tuesday, 24 May 2011
Time: 4:30pm C 7:30pm
Venue: G017 / LG1031 / LG1
. This is a closed-book examination. However, you are allowed to bring with you ONE piece of A4-sized paper with notes written or typed on both sides for use in the exami-nation.

. Your answers will be graded according to correctness, precision, clarity and efficiency.

. During the examination, you should put aside your calculators, mobile phones, PDAs and all other electronic devices. In particular, all mobile phones should be turned off completely.

. This booklet has 24 single-sided pages. Please check that all pages are properly printed before you start working.

. You may use the reverse side of the pages for your rough work or continuation of work.






Student name: __________________________ English name (if any):______________________
Student ID: ________________ Email:______________________ Lecture & lab:____________
I have not violated the Academic Honor Code in this examination (your signature): ___________________
Question
Your score
Maximum score
Question
Your score
Maximum score

1

15
4

25

2

17
5

20

3

23




Total




100




1. Insertion Sort with Recursion (15 points)
Insertion sort can be implemented with recursion stated as follows. In order to sort the array with n elements A[0..n-1], we first (recursively) sort A[0..n-2] (in increasing order) and then insert A[n-1] into the sorted array A[0..n-2].
Write a recursive function ISRecur(int A[], int n) that implements the recursive insertion sort as stated above. The argument A[] is the array to be sorted and n is the number of elements to be sorted.
For example, given data[]={5,3,1,4,7}, we can sort it by calling ISRecur (data,5)to yield the result data[]={1,3,4,5,7}.





2. Validity Checking for n-Queen Problem Using STL vector(17 points)
In chess, a queen can attack horizontally, vertically, or diagonally. The n-queen problem is to determine the positions of n queens on an nn chessboard so that no any two queens can attack each other; in other words, any two queens must never share the same row, column and diagonal. The column and row are indexed from 0 to n-1. The solution of n-queen problem may not be unique. The following figures show two valid solutions and an invalid one for 5-queen problem.



Q1


Q1





Q1


Q2


Q2








Q2










Q3




Q3






Q3