数据结构与算法分析期末试题2011

1、。装。订。线。2011 年2012 年第 一 学期数据结构与算法分析时间共 120 分钟期末试卷 B 卷一、（10 分）Please translate the following termso Chi.abstract daype; stack; tree; sorting; recur; doublylinked list;dequeue; node; depth;balanced binary tree.二、（10 分）Please translate the following termso English.算法分析；尾指针；后进先出；推入栈；队尾；遍历；树根；层序；缩减增量排序；中位

2、数.三、（10 分）ni3 . PleaseHere is a simple program fragment to calculatealgorithm as carefully as you can.yze the time complexity of thisi1Sum(n )partialsum;partialsum=0;1234for(i = 1; i =n; i+ )Partialsum +=i*i*i;return partialSum;第 1 页 共 5 页得分阅卷人得分阅卷人得分阅卷人题号12345678910总分得分阅卷人四、（10 分）Describe informall

3、y as many (east two) algorithms assibletosolvetheSelectionProblem: Find the kth-largest number from a group of n numbers.五、（10 分）Describe what the following code does when started on the list consisting of 10, 9, 8, 7, 6, 5.template void removeEveryOtherItem( Container & lst )第 2 页 共 5 页得分阅卷人得分阅卷人ty

4、pename Container:iterator while( itr != lst.end( ) )itr = lst.erase( itr ); if( itr != lst.end( ) )+itr;itr=lst.begin();六、（10 分）(a) Write the order in which the nodes of the following tree are visited if preorder traversalis followed.What is the height of the tree?What is the depth of the node with

5、key 4?第 3 页 共 5 页得分阅卷人七、（10 分）Show the exprestree for the arithmetic expres(a + b) * (c + d * e) + h * f.八、（10 分）Exhibit an AVL tree with the fewest nodes of height 3.第 4 页 共 5 页得分阅卷人得分阅卷人九、（10 分）Show the result of inserting 2, 1, 4, 5, 9, 3, 6, 7o an initially empty AVL tree.十、（10 分）Shown below is

6、the code for some routine.template const Comparable & ?( vector & a,center = ( left + right ) / 2; if( a center a left )swap( a left , a center );if( a right a left )left,right)swap( a left , a right if( a right a center ) swap( a center , a right swap( a center , a rightreturn a right - 1 ;); );- 1 );What is