《数据结构》试题(B卷 单选題[从供选择的答案中选岀正确的答案,将其编号填入下列叙述中的()內](每小題3分, 共24分) (1)向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移动(A)个 元素。 (2)设有一个二维数组Am[n],假设Ao[0]存放位置在64410),A[2][2]存放位置在67610,每个元 素占一个空间,则A[4[5]在(B)位置,(0表明用10进数表示 (3)一个有序顺序表有255个对象,采用顺序搜索法查表,平均搜索长度为(C)。 (4)含5个结点(元素值均不相同)的二叉搜索树有(D)种。 (5)在分析折半搜索的性能时常加入失败结点,即外结点,从而形成扩充的二叉树。若设失败结点i 所在层次为l,那么搜索失败到达失败结点时所做的数据比较次数是(E)。 (6)设有一个含200个表项的散列表,用线性探查法解决冲突,按关键码查询时找到一个表项的平均 探查次数不超过1.5,则散列表项应能够至少容纳(F)个表项。(设搜索成功的平均搜索长度为Sn 1+1/(1-a)}12,其中a为装填因子) (7)n个顶点的连通图至少有(G)条边。 (8)一个二叉树按顺序方式存储在一个一维数组中,如图 AB H 则结点E在二叉树的第(H)层 【供选择的答案】 70910 C:128 127 126 400 526 624 676 3 、阅读理解题[说明下列递归过程的功能](10分) int unknown( Bin TreNode *1)i ∥/指针t是二叉树的根指针 f(t==NULL )return 0 else if (t-lefi child==NULL && t-right Child== NULL)return 1; else return unknown(I-lefiChild)+ unknown( t-right Child ) 简答题(每小题10分,共30分) 1、如下所示的连通图,请画出 (1)以顶点①为根的深度优先生成树 (5分) (2)如果有关节点,请找出所有的关节点 (5分)
1 《数据结构》试题 （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、设散列表为HT0.12],即表的大小为m=13。采用双散列法解决冲突。散列函数和再散列函数分别为: o(key)=key%13;注:%是求余数运算(=mod) H=(H1+REV(key+1)%ll+1)%13; i=1,2,3,…,m-1 其中,函数RE(x)表示颠倒10进制数x的各位,如RE(37)=73,RE(7)=7等。若插入的关键码序列为 2,8,31,20,19,18,53,27}。试画出插入这8个关键码后的散列表 四、综合算法题 有一种简单的排序算法,叫做计数排序( count sorting)。这种排序算法对一个待排序的表(用数组 表示)进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所有待排序的关键码互不相 同。计数排序算法针对表中的每个记录,扫描待排序的表一趟,统计表中有多少个记录的关键码比该记录 的关键码小。假设针对某一个记录,统计出的计数值为c,那么,这个记录在新的有序表中的合适的存放 位置即为c。 (1)给出适用于计数排序的数据表定义 (2)使用C++语言编写实现计数排序的算法 (10分) (3)对于有n个记录的表,关键码比较次数是多少? (4分 五、填空题 下面给出的是一个在二叉树中查找值为x的结点,并打印该结点所有祖先结点的算法。在此算法中 假设值为x的结点不多于一个。此算法采用后序的非递归遍历形式。因退栈时需要区分其左、右子树是否 已经遍历,故在结点进栈时附带有一个标志,=0,进入左子树,=1,进入右子树。用栈ST保存结点指 针pr及其标志lag。op是栈顶指针。 void print( BinTreeNode I; Type &x)i stack ST; int i, top; ∥置空栈 while(tl=NULL&&t→ data=x‖!opl=0){ while(1!=NULL &&r-dataI=x)t ∥寻找值为x的结点 STItop]- ptr=t; ∥进栈 STitop. tag=O if (t 1=NULL &&1-data==x) ∥找到值为x的结点 cout < ST. ptr-data < endl;
2 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],lag==1)∥未找到值为x的结点 if( top>0)i STtop. tag=1; ∥转传向右子树 }/ print李/ (1)请将缺失的语句补上 (8分) ④4 (2)请给出对于右图所示的二叉树,使用上述算 法搜索值为9的结点和值为10的结点的结果 以及在栈ST中的变化。(1op是栈顶指针) (10分)
3 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 分）
试题解答 、单选题 【解答】 B E 、阅读理解题[说明下列递归过程的功能] 【解答】计算二叉树的叶结点的个数。 简答题 【解答】 1)该连通图从①出发做深度优先搜索,得到的深度优先生成树为: 结果不唯 (2)关节点为①、②、③、⑦、⑧ 2、【解答】答案是否定的。举个反例:看下图粗线所示的路径 Sl={15},S2={25,30,35,40},S3={40,50,65,70} 40∈S3,45∈S2,45<40不成立 3550 3、【解答】因为(13-1)%(4-1)=12%3=0,所以不需要添加空段。最佳归并树为 6⑨03)(2)00①0(20)(2030 WPL=(5+9+13+12+16+14+17+18+28+37+20+30)*2+42=480 4、【解答】
4 试题解答 一、单选题 【解答】 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、【解答】 30 35 15 40 70 25 65 45 50
散列表H∏0.12],散列函数与再散列函数为 Ho( key )=key mod 13: Hi=(Hi-1+ rEv(key+1)mod 11+ 1) mod 13; 插入关键码序列为{2,8,31,20,19,18,53,27} H(2)=2,比较次数为1Ho(8)=8,比较次数为1 H0(31)=5,比较次数为1H(20)=7,比较次数为1 H(19)=6,比较次数为1 H(18)=5,沖突,H=9,比较次数为2 H(53)=1,比较次数为1 H(27)=1,冲突,H=7,冲突,H=0,比较次数为3 插入8个关键码后的散列表 2□ 四、综合算法题 (1)数据表定义 【解答】 const int DefaulISize= 100; template class datalist ∥.据表的前视声明 template class Element t ∥数据表元素类的定义 private Type key; ∥关键码 field otherdata ∥其它数据成员 p Type getKey(i return key;) ∥取当前结点的关键码 void setKey( const Type x){key=x;}/将当前结点的关键码修改为x template class datalist i 用顺序表来存储待排序的元素,这些元素的类型是Type public: datalist( int MaxS== DefaulISize): MaxSize( Maxse ) Current Size(0) f Vector=new Element [MaxS=); 1 rivate Element*vector; ∥存储待排序元素的向量 int Max size currentSize ∥最大元素个数与当前元素个数 (2)计数排序的算法 【解答1】 template void countsort( datalist& initList, datalisT& resuItlist )& i,j, c; Type refer for (i=0; i< initList. CurrentSize; i++)i refer: = initList Vector[]. getKey (i for(j=0; j< initList Current Size; j++)
5 散列表 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 datalist //数据表的前视声明 template class Element { //数据表元素类的定义 private: Type key; //关键码 field otherdata; //其它数据成员 public: Type getKey ( ) { return key; } //取当前结点的关键码 void setKey ( const Type x ) { key = x; } //将当前结点的关键码修改为 x } template class datalist { //用顺序表来存储待排序的元素，这些元素的类型是 Type public: datalist ( int MaxSz = DefaultSize ) : MaxSize ( Maxsz ), CurrentSize (0) { Vector = new Element [MaxSz]; } private: Element * Vector; //存储待排序元素的向量 int MaxSize, CurrentSize; //最大元素个数与当前元素个数 } (2) 计数排序的算法 【解答 1】 template void countsort ( datalist & initList, datalist & 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(inmitList Vector]. getKey () refer )c++ resulIlist. Vectorc=initList Vector resultlist currentSize initlist current Size 【解答2】 template void countsort( datalisT& initList, datalist& resulIList)& for( int i=0; i< initList. CurrentSize; i++)cG=0; for(i=0; i<initList. CurrentSize-1; i++) for( int =i+l;j< initList Current Size;j++) if(initList Vector] getKey (<initList Vector a-getKey ()c0++ for(i=0; resulIList. Vector c]=initList Vector resultList CurrentSize initList CurrentSize (3)对于n个记录的表,【解答1】关键码比较次数为m2,【解答2】关键码比较次数为n(n-1)2。 五、填空题 【解答】 (1)请将缺失的语句补上 t= STItop) ptr→ right Child (2)搜索值为9的结 ① ptr lag 搜索值为10的结点 pIr tag g □□匚[□□
6 if (initList.Vector[j].getKey ( ) void countsort ( datalist & initList, datalist & 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】关键码比较次数为 n 2，【解答 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
pIr tag ptr tag g tr tag 7
7 → 0 → 1 1 1 → 0 → 1 0 0 1 1 1 1 1 1 ptr tag ptr tag ptr tag ptr tag ptr tag