1、数据结构-4 及答案解析(总分：100.00，做题时间：90 分钟)一、B单项选择题/B(总题数：15，分数：30.00)1.将含 100个结点的完全二叉树从根这一层开始，每层从左到右依次对结点编号，根结点的编号为 1。编号为 71的结点的双亲的编号为( )（分数：2.00）A.34B.35C.36D.无法确定2.下面四种内排序方法中，要求内存容量最大的是( )（分数：2.00）A.插入排序B.选择排序C.快速排序D.归并排序3.采用分治法进行排序的方法是( )（分数：2.00）A.快速排序B.插入排序C.堆排序D.希尔排序4.由权值为 4,2,8,7的四个叶子构成一棵哈夫曼树之后，此树的带权
2、路径的长度为( )（分数：2.00）A.21B.42C.40D.445.如图所示二叉树的中序遍历序列是( ) （分数：2.00）A.a b c d g e fB.d f e b a g cC.d b a e f c gD.d e f b a g c6.索引非顺序文件是指( )（分数：2.00）A.主文件无序，索引表有序B.主文件有序，索引表无序C.主文件有序，索引表有序D.主文件无序，索引表无序7.对一棵非空二叉树进行中序遍历，则根结点的左边( )（分数：2.00）A.只有左子树上的所有结点B.只有右子树上的所有结点C.只有左子树上的部分结点D.只有右子树上的部分结点8.一棵二叉树满足下列条件
3、：对任一结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。现采用【 】遍历方式就可以得到这棵二叉树所有结点的递增序列。（分数：2.00）A.先根B.中根C.后根D.层次9.串是一种特殊的线性表，其特殊性体现在( )（分数：2.00）A.可顺序存储B.数据元素是一个字符C.可链接存储D.数据元素可以是多个字符10.一个长度为 10的有序表，按照二分查找法对该表进行查找，在表内各元素等概率的情况下，查找成功所需要的平均比较次数为( )（分数：2.00）A.25/10B.27/10C.29/10D.31/1011.深度为 k的二叉树，所含叶子的个数最多为( )
4、（分数：2.00）A.2KB.KC.2K-1D.2K-112.长度为 12的有序表：Apr，Aug，Dec，Feb，Jan，Jul，Jun，Mar，May，Nov，Oct，Sep，按折半查找法对该表进行查找。在表内各元素等概率情况下查找成功所需的平均比较次数为( )（分数：2.00）A.35/12B.37/12C.39/12D.43/1213.设深度为 k的二叉树上只有度为 0和度为 2的结点，则这类二叉树上所含结点总数量少( )个。（分数：2.00）A.k+1B.2kC.2k-1D.2k+114.从一个包含 2000个结点的散列表 A12000中查找结点的平均比较次数( )从一个包含 200
5、个结点的散列表 B1200中查找结点的平均比较次数。（分数：2.00）A.大于B.小于C.等于D.不确定15.设有 6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。（分数：2.00）A.5B.6C.7D.8二、B填空题/B(总题数：10，分数：20.00)16.在索引顺序文件中需建立一张指示逻辑记录和物理记录之间的一一对应关系的_。它通常采用_结构来组织。（分数：2.00）填空项 1:_17.数组 A110，-26，28以行优先顺序存储，设第一个元素的首地址是 100，每个元素占 3个存储长度的存储空间，则元素 A5,0,7的存储地址为 1。（分数：2.00）填空项 1:_18.
6、对磁带上的顺序文件进行更新某个记录时，必须_整个文件。而在顺序文件的最后添加新的记录时，则不必_整个文件。（分数：2.00）填空项 1:_19.若二叉树的一个叶子是某子树的中序遍历序列中的第一个结点，则它必是孩子树的后序遍历序中的 1个结点。（分数：2.00）填空项 1:_20.文件的记录均存放在数据集中，数据集中的一个结点称为_，它是一个_操作的基本单位。（分数：2.00）填空项 1:_21.设线性表 L=(a1，a 2，a n)(n2)，表中元素按值的递增顺序排列。对一个给定的值 k，分别用顺序检索和二分法检索查找与 k相等的元素，比较次数分别为 s和 b，若检索不成功，则 s和 b的数量
7、关系是 1。（分数：2.00）填空项 1:_22.在按照顺序存储方式存储的数组中，元素 aij的存储地址应该是数组的 1 加上排在 aij前面的元素所占用的单元数。（分数：2.00）填空项 1:_23. 1查找法的平均查找长度与元素个数 n无关。（分数：2.00）填空项 1:_24.在计算机软件系统中，有两种处理字符串长度的方法：一种是采用_，第二种是设置_。（分数：2.00）填空项 1:_25.在顺序队列中，应该有队头和队尾两个指针来指示，队头指针和队尾指针的初值在队列的初始化时均应该设置为_，当对队列进行插入和删除的操作后，如果头指针和尾指针相等时，队列为_。（分数：2.00）填空项 1:
8、_三、B解答题/B(总题数：4，分数：20.00)26.已知一棵具有 2个结点的二叉树的前序遍历序列和后序遍历序列是 AB和 BA，请问：这棵二叉树是惟一的吗?如果树是不惟一的，请画出满足此条件的不同的二叉树，并简单分析一下。（分数：5.00）_27.对于下面的 3个广义表，请画出其图形表示式，并说明它们各属于什么类型的广义表。 (1)B(A(x,l(a,b),y) (2)C(A(x,l(a,b),B(A(x,l(a,b),y) (3)D(a,D(a,D()（分数：5.00）_28.已知有如下一个关键字序列96,47,104,32,73,136,15,38,90,180，按照上述插入顺序构造一
9、棵二叉排序树，则请给出二叉排序树的构造过程，说明其深度，并在等概率的条件下求出平均查找长度。（分数：5.00）_29.已知有一组长度为 9的关键字序列为22,63,72,54,97,17,37,80,92，现在假设散列表的地址空间为T010，请用除余法构造散列函数，如果存在冲突问题，请用线性探查法解决冲突，并给出相应的散列表。（分数：5.00）_四、B算法阅读题/B(总题数：4，分数：20.00)30.以下为单链表的建表算法，分析算法，请在_处填上正确的语句。 lklist create_1klistl() /*通过调用 intiate_lklist和 insetr_lklist算法实现的建表
10、算法。假定$是结束标志*/ ininiate_lklist(head); i=1; scanf(“%“, while(x!=$) _; _; scanf(“%f“, return(head); 该建表算法的时间复杂性约等于_，其量级为_。（分数：5.00）填空项 1:_31.以下是图的深度优先搜索算法，请在_处填充适当的语句。 Dfs(GraphTp g,int v) ArcNodeTp*P; printf(“%“,v); visitedv=1; p=_; while(p!=NULL) if(!_)Dfs(g,padjvex); p=_; （分数：5.00）填空项 1:_32.以下为单链表的插
11、入运算，分析算法，请在_处填上正确的语句。 void insert_lklist(lklist head,datatype x,int i) /*在表 head的第 i个位置上插入一个以 x为值的新结点*/ p=find_lklist(head,i-1); if(p=NULL)error(“不存在第 i个位置“); elses=_;sdata=x; snext=_; pnext=s; （分数：5.00）填空项 1:_33.根据文字说明，请在以下_处填充适当的语句。 采用静态链表作存储结构，设置一个大小为 2n-1的数组，令数组的每个元素由四个域组成：wt 是结点的权值；lehild、rchil
12、d 分别为结点的左、右孩子指针；parent 是结点的双亲在数组中的下标。其数组元素类型定义如下： typedef struet float wt; /*权值*/ int parent,lchild rchild; /*指针域*/ node; typedef node hftree2*n-1; 在这种存储结构上的哈夫曼算法可描述如下： void huffman(int k,float Wk,hftree T) /*求给定权值 W的哈夫曼树 T*/ int i,j,x,y; float m,n; for(i=0;i2*k-1;i+) Ti.parent=-1;Ti.lchild=-1;Ti.rc
13、hild=-1; if(_)Ti.wt=Wi; else Ti.wt=0 for(i=0;ik-1;i+) x=0;y=0;m=maxint;n=maxint; for(j=0;jk-i,j+) if(Tj.wtm)y=_;m=_;x=j; else if(Tj.wtn)y=j;) Tx.parent=_;Ty.parent=_; Tk+i.wt=_; Tk+i.lchild=_;Tk+i.rchild=_; （分数：5.00）填空项 1:_五、B算法设计题/B(总题数：1，分数：10.00)34.从键盘上输入若干字符(每行长度不等)，输入后把它们存储到一磁盘文件中，再从该文件中读出这些数据，
14、将其中小写字母转换成大写字母再进行屏幕输出。（分数：10.00）_数据结构-4 答案解析(总分：100.00，做题时间：90 分钟)一、B单项选择题/B(总题数：15，分数：30.00)1.将含 100个结点的完全二叉树从根这一层开始，每层从左到右依次对结点编号，根结点的编号为 1。编号为 71的结点的双亲的编号为( )（分数：2.00）A.34B.35 C.36D.无法确定解析：2.下面四种内排序方法中，要求内存容量最大的是( )（分数：2.00）A.插入排序B.选择排序C.快速排序D.归并排序 解析：3.采用分治法进行排序的方法是( )（分数：2.00）A.快速排序 B.插入排序C.堆排序
15、D.希尔排序解析：4.由权值为 4,2,8,7的四个叶子构成一棵哈夫曼树之后，此树的带权路径的长度为( )（分数：2.00）A.21B.42C.40 D.44解析：5.如图所示二叉树的中序遍历序列是( ) （分数：2.00）A.a b c d g e fB.d f e b a g cC.d b a e f c g D.d e f b a g c解析：6.索引非顺序文件是指( )（分数：2.00）A.主文件无序，索引表有序 B.主文件有序，索引表无序C.主文件有序，索引表有序D.主文件无序，索引表无序解析：7.对一棵非空二叉树进行中序遍历，则根结点的左边( )（分数：2.00）A.只有左子树上的
16、所有结点 B.只有右子树上的所有结点C.只有左子树上的部分结点D.只有右子树上的部分结点解析：8.一棵二叉树满足下列条件：对任一结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。现采用【 】遍历方式就可以得到这棵二叉树所有结点的递增序列。（分数：2.00）A.先根B.中根 C.后根D.层次解析：9.串是一种特殊的线性表，其特殊性体现在( )（分数：2.00）A.可顺序存储B.数据元素是一个字符 C.可链接存储D.数据元素可以是多个字符解析：10.一个长度为 10的有序表，按照二分查找法对该表进行查找，在表内各元素等概率的情况下，查找成功所需要的平均比较次
17、数为( )（分数：2.00）A.25/10B.27/10C.29/10 D.31/10解析：11.深度为 k的二叉树，所含叶子的个数最多为( )（分数：2.00）A.2KB.KC.2K-1 D.2K-1解析：12.长度为 12的有序表：Apr，Aug，Dec，Feb，Jan，Jul，Jun，Mar，May，Nov，Oct，Sep，按折半查找法对该表进行查找。在表内各元素等概率情况下查找成功所需的平均比较次数为( )（分数：2.00）A.35/12B.37/12 C.39/12D.43/12解析：13.设深度为 k的二叉树上只有度为 0和度为 2的结点，则这类二叉树上所含结点总数量少( )个。（
18、分数：2.00）A.k+1B.2kC.2k-1 D.2k+1解析：14.从一个包含 2000个结点的散列表 A12000中查找结点的平均比较次数( )从一个包含 200个结点的散列表 B1200中查找结点的平均比较次数。（分数：2.00）A.大于B.小于C.等于D.不确定 解析：15.设有 6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。（分数：2.00）A.5 B.6C.7D.8解析：二、B填空题/B(总题数：10，分数：20.00)16.在索引顺序文件中需建立一张指示逻辑记录和物理记录之间的一一对应关系的_。它通常采用_结构来组织。（分数：2.00）填空项 1:_ （正确答案
19、：索引 表树）解析：17.数组 A110，-26，28以行优先顺序存储，设第一个元素的首地址是 100，每个元素占 3个存储长度的存储空间，则元素 A5,0,7的存储地址为 1。（分数：2.00）填空项 1:_ （正确答案：913）解析：18.对磁带上的顺序文件进行更新某个记录时，必须_整个文件。而在顺序文件的最后添加新的记录时，则不必_整个文件。（分数：2.00）填空项 1:_ （正确答案：复制 复制）解析：19.若二叉树的一个叶子是某子树的中序遍历序列中的第一个结点，则它必是孩子树的后序遍历序中的 1个结点。（分数：2.00）填空项 1:_ （正确答案：第一）解析：20.文件的记录均存放在
20、数据集中，数据集中的一个结点称为_，它是一个_操作的基本单位。（分数：2.00）填空项 1:_ （正确答案：控制区间 I/0）解析：21.设线性表 L=(a1，a 2，a n)(n2)，表中元素按值的递增顺序排列。对一个给定的值 k，分别用顺序检索和二分法检索查找与 k相等的元素，比较次数分别为 s和 b，若检索不成功，则 s和 b的数量关系是 1。（分数：2.00）填空项 1:_ （正确答案：sb）解析：22.在按照顺序存储方式存储的数组中，元素 aij的存储地址应该是数组的 1 加上排在 aij前面的元素所占用的单元数。（分数：2.00）填空项 1:_ （正确答案：基地址）解析：23. 1
21、查找法的平均查找长度与元素个数 n无关。（分数：2.00）填空项 1:_ （正确答案：散列表）解析：24.在计算机软件系统中，有两种处理字符串长度的方法：一种是采用_，第二种是设置_。（分数：2.00）填空项 1:_ （正确答案：固定长度 长度指针）解析：25.在顺序队列中，应该有队头和队尾两个指针来指示，队头指针和队尾指针的初值在队列的初始化时均应该设置为_，当对队列进行插入和删除的操作后，如果头指针和尾指针相等时，队列为_。（分数：2.00）填空项 1:_ （正确答案：0 空）解析：三、B解答题/B(总题数：4，分数：20.00)26.已知一棵具有 2个结点的二叉树的前序遍历序列和后序遍历
22、序列是 AB和 BA，请问：这棵二叉树是惟一的吗?如果树是不惟一的，请画出满足此条件的不同的二叉树，并简单分析一下。（分数：5.00）_正确答案：()解析：满足这个条件是二叉树并不是惟一的，因为仅知道前序遍历序列和后序遍历序列并不能惟一地确定一棵二叉树，满足此题条件的有两棵不同的二叉树，分别如下图所示： 27.对于下面的 3个广义表，请画出其图形表示式，并说明它们各属于什么类型的广义表。 (1)B(A(x,l(a,b),y) (2)C(A(x,l(a,b),B(A(x,l(a,b),y) (3)D(a,D(a,D()（分数：5.00）_正确答案：()解析：广义表对应的图形如下图所示，其中图 1
23、为树形结构，所以是纯表，图 2中结点 A为共享结点，则它属于再入表，图 3中因为存在递归，则它属于递归表。 28.已知有如下一个关键字序列96,47,104,32,73,136,15,38,90,180，按照上述插入顺序构造一棵二叉排序树，则请给出二叉排序树的构造过程，说明其深度，并在等概率的条件下求出平均查找长度。（分数：5.00）_正确答案：()解析：根据二叉排序树的生成过程，我们可以得到如下二叉排序树的构造结果： 此二叉排序树的深度(即高度)为 4，在二叉树上，要找到第 i层上的结点恰好需要比较 i次，而在此二叉排序树上，第 1,2,3,4层上分别有 1,2,3,4个结点，则在等概率的条
24、件下，查找成功的平均查找长度为： 29.已知有一组长度为 9的关键字序列为22,63,72,54,97,17,37,80,92，现在假设散列表的地址空间为T010，请用除余法构造散列函数，如果存在冲突问题，请用线性探查法解决冲突，并给出相应的散列表。（分数：5.00）_正确答案：()解析：因为散列函数为：h(key)=key%11，则根据此函数得到上述关键字序列的散列地址为：(0,8,6,10,9,6,1,3,4)，前 5个关键字在插入时，其相应的地址是开放地址，可以直接插入到 T0，T8，T6，T10，T9中，在插入到 6个关键字时，其散列地址 6已被关键字 72占用，所以探查 h1=(6+
25、1)%11=7。此地址开放，所以将关键字 17插入到 T7中，然后再依次将关键字 34，80，92 插入到相应的散列地址中即可。则相应的散列袁为： 四、B算法阅读题/B(总题数：4，分数：20.00)30.以下为单链表的建表算法，分析算法，请在_处填上正确的语句。 lklist create_1klistl() /*通过调用 intiate_lklist和 insetr_lklist算法实现的建表算法。假定$是结束标志*/ ininiate_lklist(head); i=1; scanf(“%“, while(x!=$) _; _; scanf(“%f“, return(head); 该建表
26、算法的时间复杂性约等于_，其量级为_。（分数：5.00）填空项 1:_ （正确答案：insert_lklist(head,x,i) i+ n(n-i)/2 O(n 2)）解析：31.以下是图的深度优先搜索算法，请在_处填充适当的语句。 Dfs(GraphTp g,int v) ArcNodeTp*P; printf(“%“,v); visitedv=1; p=_; while(p!=NULL) if(!_)Dfs(g,padjvex); p=_; （分数：5.00）填空项 1:_ （正确答案：g.adjlistv.firstarc visitedpadjvex pnextarc）解析：32.以
27、下为单链表的插入运算，分析算法，请在_处填上正确的语句。 void insert_lklist(lklist head,datatype x,int i) /*在表 head的第 i个位置上插入一个以 x为值的新结点*/ p=find_lklist(head,i-1); if(p=NULL)error(“不存在第 i个位置“); elses=_;sdata=x; snext=_; pnext=s; （分数：5.00）填空项 1:_ （正确答案：malloc(size) pnext）解析：33.根据文字说明，请在以下_处填充适当的语句。 采用静态链表作存储结构，设置一个大小为 2n-1的数组，令
28、数组的每个元素由四个域组成：wt 是结点的权值；lehild、rchild 分别为结点的左、右孩子指针；parent 是结点的双亲在数组中的下标。其数组元素类型定义如下： typedef struet float wt; /*权值*/ int parent,lchild rchild; /*指针域*/ node; typedef node hftree2*n-1; 在这种存储结构上的哈夫曼算法可描述如下： void huffman(int k,float Wk,hftree T) /*求给定权值 W的哈夫曼树 T*/ int i,j,x,y; float m,n; for(i=0;i2*k-1
29、;i+) Ti.parent=-1;Ti.lchild=-1;Ti.rchild=-1; if(_)Ti.wt=Wi; else Ti.wt=0 for(i=0;ik-1;i+) x=0;y=0;m=maxint;n=maxint; for(j=0;jk-i,j+) if(Tj.wtm)y=_;m=_;x=j; else if(Tj.wtn)y=j;) Tx.parent=_;Ty.parent=_; Tk+i.wt=_; Tk+i.lchild=_;Tk+i.rchild=_; （分数：5.00）填空项 1:_ （正确答案：ik x Tj.wt k+i k+i m+n x y）解析：五、B算
30、法设计题/B(总题数：1，分数：10.00)34.从键盘上输入若干字符(每行长度不等)，输入后把它们存储到一磁盘文件中，再从该文件中读出这些数据，将其中小写字母转换成大写字母再进行屏幕输出。（分数：10.00）_正确答案：()解析：本题的程序为： includestdio.h main() /*输入字符串到文件，取出并将小写转换成大写*/ int i,flag; char str80,ch; fILE*fp; fp=fopen(“text“,“w“); for(flag=1:flag;)/*输入字符串*/ printf (“/n输入字符串：/n“) gets(str); fprintf(fp,“%t“,str); printf(“eoutinnue? Y/N“); if(ch=getchar()=“n“)!(ch=n) flag=0; getehar(); fseek(fp,0,0); while(fscanf(fp,“%s“,str)!=EOF) for(i=.0;stri=e;i=) if(stri=a) printf(“/n%/n“,str); fclose(fp); /*main*/
