华师大数据结构期中考试试卷(含答案).doc

《华师大数据结构期中考试试卷(含答案).doc》由会员分享，可在线阅读，更多相关《华师大数据结构期中考试试卷(含答案).doc（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、. .华东师X大学期中试卷20072008学年第二学期课程名称：_数据结构_姓 名：_ 学 号：_专 业：_ 年级/班级：_课程性质：专业必修一二三四五六七八总分阅卷人签名一、 单项选择题(共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 first out2. A l

2、ist 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; Quiz(n - 1); cout 1; Quiz(n - 1)

3、; a)00011011 b)11100100 c)10011100 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) 2ib) 2i-1c) 2i-2d) 2i+15

4、. Given the recursive function int Func( /* in */ int i, /* in */ int j ) if (i 11) if (j 0) Func(n / 8); cout n % 8; 2. Give the output of the following program. _【2】_.template void print(List_entry &x)coutx ;void main( )List mylist;for(int i=0;i5;i+)mylist.insert(i,i);coutYour list have mylist.siz

5、e() elements:endl;mylist.remove(0,i);mylist.remove(2,i);mylist.insert(i,i);mylist.traverse(print);mylist.clear( );for(i=1;i3;i+)mylist.insert(i, i);mylist.traverse(print);3. Read the following program and fill the blank to plete the method.template struct Node / data membersNode_entry entry;Node *ne

6、xt;Node *back;/ constructorsNode( );Node(Node_entry item, Node *link_back = NULL, 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 . */if (

7、current_position back;4. Read the following program and fill the blank to plete the method.Error_code recursive_binary_2(const Ordered_list &the_list, const Key &target, int bottom, int top, int &position)/* Pre: The indices bottom to top define the range in the list to search for the target .Post:

8、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 position is undefined.Uses: recursive_binary_2, together with methods from the classes Ordered_list and R

9、ecord . */Record data;if (bottom = top) int mid = 【5】 ;the_list.retrieve (mid, data);if (data = target) 【6】 ;return success;else if (data target)return recursive_binary_2(the_list, target, 【7】 , top, position);elsereturn recursive_binary_2(the_list, target, bottom, 【8】 , position);else return not_pr

10、esent;5. The following program is the divide_from function of Merge Sort. Please fill the blank to plete the function. Node * divide_from (Node *sub_list)/* Post: The list of nodes referenced by sub_list has been reduced to its first half, and a pointer to the first node in the second half of the su

11、blist is returned. If the sublist has an odd number of entries, then its first half will be one entry larger than its second.*/Node *position, / traverses the entire list*midpoint, / moves at half speed of position to midpoint*second_half;if (midpoint = sub_list) = NULL) return NULL; / List is empty

12、.position = midpoint-next;while (【9】 ) / Move position twice for midpoints one move.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

13、the pivot in each sublist is chosen to be (a) the 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 = (cons

14、t Stack & s);2) bool Stack:operator += (const Stack & s);/ pushes the contents of the given stack onto this stack;3. （10分）Write the following function temple:Template void reverse(Queue & q);/ reverses the contents of the given queue;4. （18分）struct Node / data membersint entry;Node *next;/ construct

15、orsNode( );Node(int item, Node *link = NULL);f is the head pointer of a link list of nodes.Using recursion, implement the following functions:1) int Max (Node *f ); /return the max value in the link list.2) int Num (Node *f );/return the number of the nodes in the link list3) Node * Search ( Node *f

16、, int x );/Search the first occurrence of the x in the link list. If success returns the /pointer to the node, else returns NULL.数据结构期中考卷参考答案. .word. .一、 单项选择题(3618)1 c2 a3 e4 d5 a6 b二、 填空题(21122)【1】113【2】Your list have 5 elements:1 2 4 3【3】current = current-next【4】current_position-【5】(bottom + top)

17、/2【6】position = mid【7】mid + 1【8】mid 1【9】position != NULL【10】midpoint = midpoint-next;【11】midpoint-next. .word. . .word. .三、 编程题(162101860)1，a) P344 F8.12b)2. 1) bool Stack:operator=(const Stack &s)Stack s1=s, s2=*this;while (!s1.empty( )if (s1.top( )!= s2.top( ) return false;else s1.pop( ); s2.pop(

18、);2) bool Stack: operator+=(const Stack &s)Stack ss=s, s2;while (!ss.empty( )s2.push(ss.top( );ss.pop( );while (!s2.empty( )if(push(s2.top( ) = oute) return false;s2.pop( );3Template void reverse (Queue & q)Stack s; T data;while (!q.empty( ) q.retrieve(data ); s.push( data); q.serve( );while (!s.emp

19、ty( )q.append(s.top( );s.pop( );4. int Max (Node *f ) if ( f -next = NULL ) return f -entry;int temp = Max ( f -next );if ( f -data temp ) return f -entry;else return temp;int Num ( Node *f ) if ( f = NULL ) return 0;return 1+ Num ( f -next );Node * Search ( Node *f, int x ) if ( f = NULL)return NULL;else if ( f entry = x ) return f; else return Search( fnext , x);. .word.