華師大數(shù)據(jù)結構期中考試試卷(含答案)

1、華師大數(shù)據(jù)結構期中考試試卷(含答案)華東師范大學期中試卷20072008學年第二學期課程名稱：_數(shù)據(jù)結構_ 姓 名：_ 學 號：_專 業(yè)：_ 年級/班級：_課程性質：專業(yè)必修一二三四五六七八總分閱卷人簽名一、 單項選擇題(共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 outb) first in and last outc) first in and

2、 first out2. 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) list3. 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; q

3、uiz(n - 1); cout << 1; quiz(n - 1); a)00011011 b) c) d)01100011 e)0011014. 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)

4、2ib) 2i-1c) 2i-2d) 2i+15. 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 above6. she

5、ll sort finally perform an ordinary ( )a) heap sortb) insertion sortc) selection sortd) 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 o

6、utput of the following program. _【2】_.template <class list_entry>void print(list_entry &x)cout<<x<<" "void main( )list<int> mylist;for(int i=0;i<5;i+)(i,i);cout<<"your list have "<<()<<" elements:"<<endl;(0,i);(2,i)

7、;(i,i);(print);( );for(i=1;i<3;i+)(i, i);(print);3. read the following program and fill the blank to complete the method.template <class node_entry>struct node post: the current node pointer references the node at position . */if (current_position <= position)for ( ; current_position !=

8、position; current_position+) 【3】 ;elsefor ( ; current_position != position; 【4】 )current = current->back;4. read the following program and fill the blank to complete the method.error_code recursive_binary_2(const ordered_list &the_list, const key &target, int bottom, int top, int &pos

9、ition)/* pre: the indices bottom to top define the range in the list to search for the target .post: if a record in the range from bottom to top in the list has key equal to target , then position locates one such entry, and a code of success is returned. otherwise, not_present is returned, and posi

10、tion is undefined.uses: recursive_binary_2, together with methods from the classes ordered_list and record . */record data;if (bottom <= top) int mid = 【5】 ; (mid, data);if (data = target) 【6】 ;return success;else if (data < target)return recursive_binary_2(the_list, target, 【7】 , top, positio

11、n);elsereturn recursive_binary_2(the_list, target, bottom, 【8】 , position);else return not_present;5. the following program is the divide_from function of merge sort. please fill the blank to complete the function. node<record> * divide_from (node<record> *sub_list)/* post: the list of n

12、odes referenced by sub_list has been reduced to its first half, and a pointer to the first node in the second half of the sublist is returned. if the sublist has an odd number of entries, then its first half will be one entry larger than its second.*/node<record> *position, position = midpoint

13、->next;while (【9】 ) position = position->next;if (position != null) 【10】 ;position = position->next; second_half = 【11】 ;midpoint->next = null;return second_half;三、 編程題（共60分）1. （16分）apply quicksort to the following list of 14 names, where the pivot in each sublist is chosen to be (a) the

14、 first key in the sublist and (b) the last key in the sublist. in each case, draw the tree of recursive call.tim dot eva roy tom kim guy amy jon ann jim kay ron jan2. （16分）write the following overload operator for stacks:1) bool stack:operator = (const stack & s);2) bool stack:operator += (const

15、 stack & s);using recursion, implement the following functions:int max (node *f ); int num (node *f );if success returns the 數(shù)據(jù)結構期中考卷參考答案9一、 單項選擇題(3×618)1 c2 a3 e4 d5 a6 b二、 填空題(2×1122)【1】113【2】your list have 5 elements:1 2 4 3【3】current = current->next【4】current_position-【5】(bottom

16、 + top)/2【6】position = mid【7】mid + 1【8】mid 1【9】position != null【10】midpoint = midpoint->next;【11】midpoint->next三、 編程題(16×2101860)1，a) p344 b)2. 1) bool stack:operator=(const stack &s)stack s1=s, s2=*this;while (!( )if ( )!= ( ) return false;else ( ); ( );2) bool stack: operator+=(cons

17、t stack &s)stack ss=s, s2;while (!( )( );( );while (!( )if(push( ) = outcome) return false;( );3template <class t> void reverse (queue<t> & q)stack<t> s  t data;while ( !( ) (data ); ( data); ( );while (!( )( );( );4. int max (node *f ) if ( f ->next = null ) return f ->entry;int temp = max ( f ->ne