南京大学金陵学院期末试卷2011~2012学年第一学期数据结构期末考试试题 A 09 1. 2 学号__________ 姓名_____________ 成绩___________一选择题（共15 题，每题2分，计30 分）在下列各题A)、B)、C)、D) 四个选项中，选择一个正确的选项，将其字母编号填写在括号中。

(1)下列哪个选项是错误的？（）A) 2n+n3 = O(2n) B) 2n+1 = O(2n)C) 22n = O(2n) D) O(n2) < O(2n)(2) 在下列4个选项中，声明一个向量数组的是( )A) vector<char> vex ; B) vector<char> vec(10) ;C) vector<cha> vex[10] ; D) vector<char > vex(10, 'a' );(3) 下列每组代码利用标准容器list建立一个表，然后逐个删除表中的元素。

其中那组代码是正确的？( )A)list<int> lst; B) list<int> lst;for( int i = 0;i<5;i++) lst.push_back(i); for( int i = 0;i<5;i++) lst.push_back(i);list<int>::iterator p; list<int>::iterator p=lst.begin();for( p=lst.begin() ; p!=lst.end() ; p++) lst.erase(p); while( !lst.empty() ) lst.erase(p);C) list<int> lst; D) list<int> lst;for( int i = 0;i<5;i++) lst.push_back(i); for( int i = 0;i<5;i++) lst.push_back(i);list<int>::iterator p=lst.begin(); list<int>::iterator p=lst.begin();while(p!=lst.end() ) lst.erase(p); while(p!=lst.end() ) p=lst.erase(p);(4) 字符a、b、c、d依次进入一个栈，按所有可能的次序出栈后组成一个长度是4的字符串，至多可以组成多少个不同的字符串？（）A) 4 B) 14 C) 24 D) 16(5）设有如下定义的数组Q：const int m=20 ；T Q[m]；//T为队列元素的类型Q存储一个环形队列。

quelen是队列中元素的个数，back 是实际队尾元素的位置，队列中第一个元素的实际位置是( )A) back+m-quelen B) back – quelenC) ( back+m – quelen +1) % m D) ( m – back +quelen) % m(6) C++标准模板库的“表”容器（list）是用双向链表实现的，对这种实现，下列叙述正确的是( )A) 元素的物理顺序与元素的逻辑顺序一定相同B) 一个表元素所占用的存储空间只用来存储表元素的值，不含其他附加信息C) 可以随机地访问元素D) 可以高效地进行插入和删除操作(7) 设一个长度为10的排好序的序列存储在数组int arr[10]中。

对一个给定的值k，用二分法查找与k相等的元素，若查找不成功，至少需要比较多少次？( )。

A) 3B) 4 C) 5D) 6(8) 设一棵树的度是4，其中度为0、1、2、3和4的结点个数分别是8、4、2、1和x，x是( ) 。

A) 4 B) 3 C) 2 D) 1(9) 下面关于二叉树的叙述正确的是( )。

A) 任何二叉树至少有一个结点B) 二叉树的度是2C) 在二叉树中，度为0的结点个数等于度为2的结点个数加1。

D) 在任何一棵完全二叉树中，没有度为1的结点。

(10) 一棵二叉树含有25个结点，这些结点要么是叶，要么是有两棵非空子的子树，此二叉树中有（）个非叶结点。

A) 11 B) 12 C) 13 D) 14(11) 设二叉树根结点的层次为0，一棵深度（高度）为k的满二叉树和同样深度的完全二叉树分别有f个结点和c个结点，下列关系式错误的是（）A) f ≥c B) c > f C) f = 2k+1－1 D) c ≤2k+1－1(12) 下列关于二叉搜索树的叙述，错误的是（）。

A) 二叉搜索树可以是空二叉树B) 向二叉搜索树中插入一个结点，该结点的度一定是0。

C) 对二叉搜索树进行中序遍历，将得到结点键值的递增序列。

D) 向二叉搜索树中插入一个结点，树的高度一定增加1。

(13) 考虑一棵二叉树结点的先序、中序和后序序列，所有叶结点的先后顺序关系是( )A) 都不相同B) 完全相同C) 先序和中序相同，而与后序不同D) 中序和后序相同，而与先序不同(14) 设有森林F，与F对应的二叉树是B。

若已知F有m个非叶结点，B中有n个结点的右子树是空二叉树，对m和n，下列等式成立的是（）A) m = n B) m = n - 1 C) m = n + 1 D) m =n - 2(15）考虑下列4种排序方法，不稳定的方法是（）A) 直接插入排序B) 二分法插入排序C) 归并排序D) 快速排序二、填空题（共10 题，每题3分，计30 分）请将下列各题的答案填写在横线上（1）一个抽象数据类型由一组值的集合以及定义在这组值上的一组组成。

(2) 利用STL的向量容器vector定义二维向量vv如下：vector< vector<int> > vv ; // 二维向量vv执行循环语句：for ( int i = 1 ; i<=3 ; i++ ) vv.push_back( vector<int> (i , 2*i ) ) ;后，向量vv的元素vv[1]是_______________________(3) 对下列函数mystery ( int n )，参数n是2的正整数幂(n=2k , k=1 ,2 , 3 ,…)，用参数n表示函数执行结束时的count 值：count=___________________________。

int mystery ( int n){int x = 2 , count = 0 ;while ( x < n ){x *= 2 ;count ++ ;}return count ;}(4) 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后立即进入队列，若6个元素出队列顺序是e2，e5，e6，e4，e3，e1，在操作过程中，栈S的最大长度（size）是多少? ______________(5) 可以高效地在两端进行插入和删除操作的队列称为_____________队列。

(6) 广义表D=( ()，(e)，( a，(b，c，d) ) )，则：D的长度是_________, D的表头Head(D)是________ ,D的表尾Tail(D)是_______________(7) 设森林F有3棵树，第一、第二和第三棵树的结点个数分别是t1、t2和t3，与森林对应的二叉树根结点的左子树有___________ 个结点。

(8) 在一棵中序线索树中，一个结点p有两棵非空的子树，它的中序前驱结点的度至多是____________。

(9) 在n个结点的完全二叉树中，叶结点的个数是。

(10)对一棵二叉树进行先序和中序遍历的结果分别是先序序列： A D B G E F C中序序列： B G D A F E C则这棵二叉树根结点的左子女和右子女分别是_________和___________ 。

三、解答题（共 5 题，每题5分，计25 分）请按照题意解答下列各题。

(1) 函数func()对表alist进行什么操作？template<typename T>void func( list<T>& alist ){list<T>:: iterator iter = alist.begin() ;while ( iter != alist.end() ){alist.push_front( * iter ) ;alist.erase ( iter++) ; // 本句也可改用p=alist.erase(iter);}}(2) 设整型数组arr[]的长度为n，元素已按值递增的顺序排好序，函数Bsearch ()在数组中查找与给定值target相等的元素，若查找成功，返回元素在数组中的位置，否则返回-1。

实现代码如下：int Bsearch (int const *arr , int n , const int& target ){bool found = false ;int first = 0, last = n-1, m ;while ( first <= last && !found ){m = ( first + last ) / 2 ; // 二等分int mid = arr[m] ;if ( target == mid ) found = true ;elseif ( target > mid ) first = m ;else last = m ;}if ( found ) return m ; // 查找成功，返回元素在数组中的位置else return -1 ; // 查找失败，返回-1}无任是查找成功或查找失败，函数是否总能正确地工作？如果不能，请举例说明。

(3)删除一棵二叉搜索树中的一个结点，然后再插入这个结点，所得的结果二叉树是否与原先的二叉树一定相同？举例说明你的结论。

(4) 设被排序的初始序列为{ 26, 28, 41, 57, 14, 10, 35, 22 }，用快速排序方法进行排序，以第一个元素26作为划分的基准，写成第一次划分后所得到的两个序列。

//本题不宜作为考题，因为划分的具体算法不同会得到不同结果。

(5) 假设一则电文中仅出现6个不同的字母a，b，c，d，e和f，每个字母在电文中出现的频率分别是3，10，12，7，4和20。

试为这6个字母设计哈夫曼编码。

四．编程题( 共2题，第（1）题5 分，第(2)题10 分，计15 分)（1）对下列单链表写一个递归函数，反向输出单链表中的结点，即依次输出a n ，a n-1，……，a 2，a 1 单链表的结点类型定义如下： struct node {int data ; node* next ; };函数的原型: void Print( Node* head); // 函数写在下面(2) 若序列 { h 0, h 1, h 2,...... , h n-1 } 中的元素满足下列关系：h i ≥ h 2i+1 并且 h i ≥ h 2i+2 ( i = 0, 1 , 2 , .... , ⎥⎦⎥⎢⎣⎢-22n ) 则该序列是一个堆(heap)。