《数据结构》试题 （B卷） 一、单选题 [从供选择的答案中选出正确的答案，将其编号填入下列叙述中的( )内]（每小题3分，共24分） (1) 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ A ）个元素。 (2) 设有一个二维数组A[m][ n]，假设A[0][0] 存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，则A[4][5] 在（ B ）位置，(10)表明用10进数表示。 (3) 一个有序顺序表有255个对象，采用顺序搜索法查表, 平均搜索长度为（ C ）。 (4) 含5个结点（元素值均不相同）的二叉搜索树有（ D ）种。 (5) 在分析折半搜索的性能时常加入失败结点，即外结点，从而形成扩充的二叉树。若设失败结点i所在层次为li，那么搜索失败到达失败结点时所做的数据比较次数是（ E ）。 (6) 设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表项的平均探查次数不超过1.5，则散列表项应能够至少容纳（ F ）个表项。（设搜索成功的平均搜索长度为 Snl＝{ 1 + 1 / (1 -α) } / 2, 其中α为装填因子） (7) n个顶点的连通图至少有（ G ）条边。 (8) 一个二叉树按顺序方式存储在一个一维数组中, 如图 0  1  2  3  4  5  6  7  8  9  10  11  12  13  14   Ａ  Ｂ  Ｃ  Ｄ   Ｅ  Ｆ   Ｇ    Ｈ   Ｉ  Ｊ  则结点E在二叉树的第（ H ）层。 【供选择的答案】 A : ( 8 ( 63.5 ( 63 ( 7 B : ( 692(10) ( 626(10) ( 709(10) ( 724(10) C : ( 128 ( 127 ( 126 ( 255 D : ( 54 ( 42 ( 36 ( 65 F : ( li +1 ( li +2 ( li - 1 ( li G : ( 400 ( 526 ( 624 ( 676 I : ( n-1 ( n ( n+1 ( 0 J : ( 1 ( 2 ( 3 ( 4 二、阅读理解题 [说明下列递归过程的功能] （10分） int unknown ( BinTreNode * t ) { ////指针t是二叉树的根指针。 if ( t == NULL ) return 0; else if ( t→leftChild == NULL && t→rightChild == NULL ) return 1; else return unknown ( t→leftChild ) + unknown ( t→rightChild ); } 三、简答题 （每小题10分，共30分） 1、如下所示的连通图，请画出 (1) 以顶点①为根的深度优先生成树； （5分） (2) 如果有关节点，请找出所有的关节点。 （5分）  2、设有13个初始归并段，其长度分别为28，16，37，42，5，9，13，14，20，17，30，12，18。试画出4路归并时的最佳归并树，并计算它的带权路径长度WPL。 3、设散列表为HT[0..12]，即表的大小为m = 13。采用双散列法解决冲突。散列函数和再散列函数分别为： H0( key ) = key % 13; 注：%是求余数运算（= mod ） Hi = ( Hi-1 + REV ( key + 1) % 11 + 1) %13; i = 1, 2, 3, (, m-1 其中，函数REV(x)表示颠倒10进制数x的各位，如REV(37) = 73，REV(7) = 7等。若插入的关键码序列为{ 2, 8, 31, 20, 19, 18, 53, 27 }。试画出插入这8个关键码后的散列表。 四、综合算法题 有一种简单的排序算法，叫做计数排序（count Sorting）。这种排序算法对一个待排序的表（用数组表示）进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键码互不相同。计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小。假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。 (1) 给出适用于计数排序的数据表定义； （4分） (2) 使用C++ 语言编写实现计数排序的算法； （10分） (3) 对于有n个记录的表，关键码比较次数是多少？ （4分） 五、填空题 下面给出的是一个在二叉树中查找值为x的结点，并打印该结点所有祖先结点的算法。在此算法中，假设值为x的结点不多于一个。此算法采用后序的非递归遍历形式。因退栈时需要区分其左、右子树是否已经遍历，故在结点进栈时附带有一个标志，＝0，进入左子树，＝1，进入右子树。用栈ST保存结点指针ptr及其标志tag。top是栈顶指针。 void print ( BinTreeNode * t; Type &x ) { stack ST; int i, top; top = 0; //置空栈 while ( t != NULL && t→data != x || top != 0 ) { while ( t != NULL && t→data != x ) { //寻找值为x的结点 ① ;   ST [top].ptr = t; //进栈 ST [top].tag = 0; ② ;  } if ( t != NULL && t→data == x ) //找到值为x的结点 for ( i = 1;  ③ ; i++ )  cout << ST[i].ptr→data << endl; else { while ( top > 0 && ST [top].tag == 1 ) //未找到值为x的结点 top--; if ( top > 0 ) { ST [top].tag = 1; //转向右子树 ④ ;  } } } } /*print*/  (1) 请将缺失的语句补上 （8分） ( ( ( ( (2) 请给出对于右图所示的二叉树，使用上述算法搜索值为9的结点和值为10的结点的结果，以及在栈ST中的变化。（top是栈顶指针） （10分） 试题解答 一、单选题 【解答】 A : ( B : ( C : ( D : ( E : ( F : ( G : ( H : ( 二、阅读理解题 [说明下列递归过程的功能] 【解答】 计算二叉树的叶结点的个数。 三、简答题 1、【解答】 (1) 该连通图从①出发做深度优先搜索，得到的深度优先生成树为：  结果不唯一 (2) 关节点为①、②、③、⑦、⑧ 2、【解答】 答案是否定的。举个反例：看下图粗线所示的路径 S1 = { 15 }, S2 = { 25, 30, 35, 40 }, S3 = { 40, 50, 65, 70 } 40 ( S3，45 ( S2，45< 40不成立。 3、【解答】 因为 (13 - 1) % (4 - 1) = 12 % 3 = 0，所以不需要添加空段。最佳归并树为  WPL = ( 5 + 9 + 13 + 12 + 16 + 14 + 17 + 18 + 28 + 37 + 20 + 30 ) * 2 + 42 = 480 4、【解答】 散列表 HT[0..12]，散列函数与再散列函数为 H0( key ) = key mod 13； Hi = ( Hi-1 + REV ( key + 1 ) mod 11 + 1 ) mod 13; 插入关键码序列为 { 2, 8, 31, 20, 19, 18, 53, 27 } H0( 2 ) = 2, 比较次数为1 H0( 8 ) = 8, 比较次数为1 H0( 31 ) = 5, 比较次数为1 H0( 20 ) = 7, 比较次数为1 H0( 19 ) = 6, 比较次数为1 H0( 18 ) = 5, 冲突，H1 = 9，比较次数为2 H0( 53 ) = 1，比较次数为1 H0( 27 ) = 1，冲突，H1 = 7，冲突，H2 = 0，比较次数为3 插入8个关键码后的散列表 0 1 2 3 4 5 6 7 8 9 10 11 12  27 53  2   31 19 20  8 18      四、综合算法题 (1) 数据表定义 【解答】 const int DefaultSize = 100; template <class Type> class datalist //数据表的前视声明 template <class Type> class Element { //数据表元素类的定义 private: Type key; //关键码 field otherdata; //其它数据成员 public: Type getKey ( ) { return key; } //取当前结点的关键码 void setKey ( const Type x ) { key = x; } //将当前结点的关键码修改为x } template <class Type> class datalist { //用顺序表来存储待排序的元素，这些元素的类型是Type public: datalist ( int MaxSz = DefaultSize ) : MaxSize ( Maxsz ), CurrentSize (0) { Vector = new Element <Type> [MaxSz]; } private: Element <Type> * Vector; //存储待排序元素的向量 int MaxSize, CurrentSize; //最大元素个数与当前元素个数 } (2) 计数排序的算法 【解答1】 template <class Type> void countsort ( datalist<Type> & initList, datalist<Type> & resultList ) { int i, j, c; Type refer; for ( i = 0; i < initList.CurrentSize; i++ ) { c = 0; refer := initList.Vector[i].getKey ( ); for ( j = 0; j < initList.CurrentSize; j++ ) if (initList.Vector[j].getKey ( ) < refer ) c++; resultList.Vector[c] = initList.Vector[i] } resultList.CurrentSize = initList.CurrentSize; } 【解答2】 template <class Type> void countsort ( datalist<Type> & initList, datalist<Type> & resultList ) { int *c = new int[initList.CurrentSize]; for ( int i = 0; i < initList.CurrentSize; i++ ) c[i] = 0; for ( i = 0; i < initList.CurrentSize-1; i++ ) for ( int j = i+1; j < initList.CurrentSize; j++ ) if (initList.Vector[j].getKey ( ) < initList.Vector[i].getKey ( ) ) c[i]++; else c[j]++; for ( i = 0; i < initList.CurrentSize; i++ ) resultList.Vector[ c[i] ] = initList.Vector[i]; resultList.CurrentSize = initList.CurrentSize; } (3) 对于n个记录的表，【解答1】关键码比较次数为n2，【解答2】关键码比较次数为n(n-1)/2。 五、填空题 【解答】 (1) 请将缺失的语句补上 ( top++ ( t = t→leftChild ( i <= top ( t = ST[top].ptr→rightChild  (2) 搜索值为9的结点          → ( 0  → ( 0  ( 1   ( 0  ( 0   ( 0  ( 0   ptr tag ptr tag 搜索值为10的结点   → ( 0 → ( 1               ( 0  ( 0 → ( 1        → ( 0  ( 1  ( 1  ( 1    → ( 0   ( 0  ( 0  ( 0  ( 0 → ( 1  ( 0   ( 0  ( 0  ( 0  ( 0  ( 0  ( 1   ptr tag ptr tag ptr tag ptr tag ptr tag ptr tag                → ( 0 → ( 1            ( 1  ( 1 → ( 0 → ( 1      ( 0  ( 0  ( 1  ( 1      ( 1  ( 1  ( 1  ( 1      ptr tag ptr tag ptr tag ptr tag ptr tag