内容发布更新时间 : 2024/7/4 2:16:35星期一 下面是文章的全部内容请认真阅读。

华东师范大学期中试卷 2007—2008学年第二学期

课程名称：______数据结构_____

姓 名：___________________ 学 号：__________________ 专 业：___________________ 年级/班级：__________________ 课程性质：专业必修 一 二 三 四 五 六 七 八 总分 阅卷人签名

一、 单项选择题(共18分，每题3分)

1. Stack has the property called last in and first out, then which of the following describes the property of Queue? a) Last in and first out b) First in and last out c) First in and first out

2. A list of items from which only the item most recently added can be removed is known as a ( )

a) stack b) queue

c) circular linked list d) list

3. If the following function is called with a value of 2 for n, what is the resulting

output? void Quiz( int n ) { if (n > 0) { cout << 0; Quiz(n - 1); cout << 1; Quiz(n - 1); } }

a) 00011011 b) 11100100 c) 10011100 d) 01100011 e) 001101

4. A heap is a list in which each entry contains a key, and, for all positions i in the list, the key at position i is at lease as large as the keys in positions 2i+2 and ( ), provided these positions exist in the list. a) 2i b) 2i-1 c) 2i-2 d) 2i+1

5. Given the recursive function int Func( /* in */ int i, /* in */ int j ) { if (i < 11) if (j < 11) return i + j; else return j + Func(i, j - 2); else return i + Func(i - 1, j); }

what is the value of the expression Func(12, 15) ? a) 81 b) 62 c) 19 d) 72

e) none of the above

6. Shell sort finally perform an ordinary ( )? a) Heap sort b) Insertion sort c) Selection sort d) Quick sort

二、 填空题（共22分，每空2分）

1. If the following function is called with a value of 75 for n, the resulting output is _______【1】_________.

void Func( /* in */ int n ) { if (n > 0) { Func(n / 8); cout << n % 8; } }

2. Give the output of the following program. ________【2】__________. template void print(List_entry &x){ cout<

void main( ){

List mylist;

for(int i=0;i<5;i++)mylist.insert(i,i);

cout<<\ mylist.remove(0,i); mylist.remove(2,i); mylist.insert(i,i);

mylist.traverse(print); mylist.clear( );

for(i=1;i<3;i++)mylist.insert(i, i); mylist.traverse(print); }

3. Read the following program and fill the blank to complete the method. template struct Node { // data members Node_entry entry;

Node *next; Node *back; // constructors Node( );

Node(Node_entry item, Node *link_back = Node *link_next = NULL); };

template

void List :: set_position(int position) const

/* Pre: position is a valid position in the List : 0 <=position < count . Post: The current Node pointer references the Node at position . */ {

NULL,