2011级数据结构试卷A及答案 - 副本 (2)

(

密

封

线

内

不

答

题

)

…

…

…

…

…

…

…

…

…

…

…

…

…

…

< br>…

密

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

封

…

…

…

…

< br>…

…

…

…

…

…

…

…

…

…

…

线

…

…

…

…

…

…

…

…

…

…

…

…

…

< br>…

学

院

专

业

座

位

号

诚信应考

,

考试作弊将带来严重后果！

华南理工大学期末考试

《

Data Structure

》试卷

A

注意事项：

1.

考前请将密封线内填写清楚；

2.

所有答案请答在答题纸上；

3

．考试形式：闭卷；

4.

本试卷共十大题，满分

100

分 ，考试时间

120

分钟

。

题

号

一

二

三

四

五

六

七

八

九

十

总分

得

分

评卷人

1. Select the correct choice.

(20 scores, each 2 scores)

(1) Pick the growth rate that corresponds to the most inefficient algorithm as n gets

large: (

C

)

(A) 2n

3

(B) 2n

2

logn

(C) n!

(D) 2

n

(2) An algorithm must be or do all of the following EXCEPT:

(

B

)

(A) Partially correct

(B) Ambiguous

(C) Can stop

(D) Concrete steps

(3) If a data element requires 6 bytes and a pointer requires 2 bytes, then a linked list

representation

will

be

more

space

efficient

than

a

standard

array

representation

when the fraction of non-null elements is less than about: (

B

)

(A) 1/4

(B) 3/4

(C) 4/7

(D) 2/3

(4)

Which statement is not correct among the following four:

(

C

)

(A)

The Quick- sort is an unstable sorting algorithm.

(B)

The

number

of

empty

sub-trees

in

a

non-empty

full

binary

tree

is

one

more

than the number of nodes in the tree.

(C)

The best case for my algorithm is n becoming larger and larger because that is

the most quickly.

(D)

A

cluster

is

the

smallest

unit

of

allocation

for

a

file,

so

all

files

occupy

a

multiple of the cluster size.

(5) Which of the following is a true statement: (

C

)

(A) A general tree can be transferred to a binary tree with the root having both left

child and right child.

(B)

In

a

BST,

the node

can be

enumerated sorted by

a preorder

traversal

to

the

BST.

(C) In a BST, the left child of any node is less than the right child, but in a heap,

the left child of any node could be less than or greater than the right child.

(D) A heap must be full binary tree.

(6) The golden rule of a disk-based program design is to: (

B

)

(A)

Improve

the

basic

I/O

operations.

(B)

Minimize

the

number

of

disk

《

Data Structure

》

A

试卷

第

1

页

共

5

页

_

_

_

_

_

_

_

_

_

_

_

_

_

_

< br>_

_

_

_

_

_

_

姓

名

学

号

accesses.

(C) Eliminate the recursive calls. (D) Reduce main memory use.

(7) Given an array as A[m] [n]. Supposed that

A

[0] [0] is located at 644

(10)

and

A

[2]

[2] is stored at 676

(10)

, and every element occupies one space.

“

(10)

”

means that the

number is presented in decimals. Then the element

A

[1] [1]

(10)

is at position:

(

D

)

(A)

692

(B)

695

(C)

650

(D)

660

(8) If there is 1MB working memory, 4KB blocks, and yield 128 blocks for working

memory. By the multi-way merge in external sorting, the average run size and the

sorted size in one pass of multi-way merge on average are separately (

C

)?

(A)

1MB, 128 MB

(B) 2MB, 512MB

(C)

2MB, 256MB

(D) 1MB, 256MB

(9)

In

the

following

sorting

algorithms,

which

is

the

best

one

to

find

the

first

10

biggest elements in the 1000 unsorted elements?

(

B

)

(A) Quick-sort

(B) Heap sort

(C ) Insertion sort (D) Replacement selection

(10)

Assume

that

we

have

eight

records,

with

key

values

A

to

H,

and

that

they

are

initially

placed

in

alphabetical

order.

Now,

consider

the

result

of

applying

the

following access pattern: F D F G E G F A D F G E if the list is organized by the

Move-to-front heuristic, then the final list will be (

B

).

(A)

F G D E A B C H

(B)

E G F D A B C H

(C) A B F D G E C H

(D) E G F A C B D H

2. Fill the blank with correct C++ codes:

(16 scores)

(1)

Given an array storing integers ordered by distinct value without duplicate, modify the binary

search routines to return the position of the integer with the greatest value less than K when K

itself does not appear in the array. Return ERROR if the lest value in the array is greater than K:

(10 scores)

// Return position of greatest element < K

int newbinary(int array[], int n, int K) {

int l = -1;

int r = n;

// l and r beyond array bounds

while (l+1 != r) {

// Stop when l and r meet

___ int i=

（

l+r

）

/2_____;

// Look at middle of subarray

if (K < array[i])

_

_ r=i __

_;

// In left half

if (K == array[i])

return i

// Found it

if (K > array[i])

___ l=i _

__

// In right half

}

// K is not in array or the greatest value is less than K

if

K> array[0]

（

or l!= -1

）

// the lest value in the array is greater than K with l updated

return

l

// when K itself does not appear in the array

else

return

ERROR;

// the integer with the lest value greater than K

}

《

Data Structure

》

A

试卷

第

2

页

共

5

页