《[自学考试密押题库与答案解析]数据结构自考题模拟10.docx》由会员分享，可在线阅读，更多相关《[自学考试密押题库与答案解析]数据结构自考题模拟10.docx（13页珍藏版）》请在三一文库上搜索。
1、自学考试密押题库与答案解析数据结构自考题模拟10自学考试密押题库与答案解析数据结构自考题模拟10数据结构自考题模拟10一、单项选择题在每小题列出的四个选项中只有一个选项是符合题目要求的问题:1. 如图所示二叉树的中序遍历序列是 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 c答案:C问题:2. 长度为12的有序表：Apr，Aug，Dec，Feb，Jan，Jul，Jun，Mar，May，Nov，Oct，Sep，按折半查找法对该表进行查找。在表内各元素等概率情况下查找成功所需的平均比较次数为A.35/12B.37/12C.39
2、/12D.43/12答案:B问题:3. 采用分治法进行排序的方法是A.快速排序B.插入排序C.堆排序D.希尔排序答案:A问题:4. 下面四种内排序方法中，要求内存容量最大的是A.插入排序B.选择排序C.快速排序D.归并排序答案:D问题:5. 设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点总数量少 个。A.k+1B.2kC.2k-1D.2k+1答案:C问题:6. 串是一种特殊的线性表，其特殊性体现在A.可顺序存储B.数据元素是一个字符C.可链接存储D.数据元素可以是多个字符答案:B问题:7. 一个长度为10的有序表，按照二分查找法对该表进行查找，在表内各元素等概率的情况下，
3、查找成功所需要的平均比较次数为A.25/10B.27/10C.29/10D.31/10答案:C问题:8. 从一个包含2000个结点的散列表A1.2000中查找结点的平均比较次数 从一个包含200个结点的散列表B1.200中查找结点的平均比较次数。A.大于B.小于C.等于D.不确定答案:D问题:9. 深度为k的二叉树，所含叶子的个数最多为A.2KB.KC.2K-1D.2K-1答案:C问题:10. 设有6个结点的无向图，该图至少应有 条边才能确保是一个连通图。A.5B.6C.7D.8答案:A问题:11. 对一棵非空二叉树进行中序遍历，则根结点的左边A.只有左子树上的所有结点B.只有右子树上的所有结
4、点C.只有左子树上的部分结点D.只有右子树上的部分结点答案:A问题:12. 索引非顺序文件是指A.主文件无序，索引表有序B.主文件有序，索引表无序C.主文件有序，索引表有序D.主文件无序，索引表无序答案:A问题:13. 由权值为4,2,8,7的四个叶子构成一棵哈夫曼树之后，此树的带权路径的长度为A.21B.42C.40D.44答案:C问题:14. 一棵二叉树满足下列条件：对任一结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。现采用 遍历方式就可以得到这棵二叉树所有结点的递增序列。A.先根B.中根C.后根D.层次答案:B问题:15. 将含100个结点的完
5、全二叉树从根这一层开始，每层从左到右依次对结点编号，根结点的编号为1。编号为71的结点的双亲的编号为A.34B.35C.36D.无法确定答案:B二、填空题问题:1. 在索引顺序文件中需建立一张指示逻辑记录和物理记录之间的一一对应关系的_。它通常采用_结构来组织。答案:索引 表树问题:2. 数组A1.10，-2.6，2.8以行优先顺序存储，设第一个元素的首地址是100，每个元素占3个存储长度的存储空间，则元素A5,0,7的存储地址为_。答案:913问题:3. 对磁带上的顺序文件进行更新某个记录时，必须_整个文件。而在顺序文件的最后添加新的记录时，则不必_整个文件。答案:复制 复制问题:4. 若二
6、叉树的一个叶子是某子树的中序遍历序列中的第一个结点，则它必是孩子树的后序遍历序中的_个结点。答案:第一问题:5. 文件的记录均存放在数据集中，数据集中的一个结点称为_，它是一个_操作的基本单位。答案:控制区间 I/0问题:6. 设线性表L=(a1，a2，an)(n2)，表中元素按值的递增顺序排列。对一个给定的值k，分别用顺序检索和二分法检索查找与k相等的元素，比较次数分别为s和b，若检索不成功，则s和b的数量关系是_。答案:sb问题:7. 在按照顺序存储方式存储的数组中，元素aij的存储地址应该是数组的_加上排在aij前面的元素所占用的单元数。答案:基地址问题:8. _查找法的平均查找长度与元
7、素个数n无关。答案:散列表问题:9. 在计算机软件系统中，有两种处理字符串长度的方法：一种是采用_，第二种是设置_。答案:固定长度 长度指针问题:10. 在顺序队列中，应该有队头和队尾两个指针来指示，队头指针和队尾指针的初值在队列的初始化时均应该设置为_，当对队列进行插入和删除的操作后，如果头指针和尾指针相等时，队列为_。答案:0 空三、解答题问题:1. 已知一棵具有2个结点的二叉树的前序遍历序列和后序遍历序列是AB和BA，请问：这棵二叉树是惟一的吗?如果树是不惟一的，请画出满足此条件的不同的二叉树，并简单分析一下。答案:满足这个条件是二叉树并不是惟一的，因为仅知道前序遍历序列和后序遍历序列并
8、不能惟一地确定一棵二叉树，满足此题条件的有两棵不同的二叉树，分别如下图所示： 这两棵二叉树的前序遍历序列都是AB，后序遍历序列是BA，但它们是两棵完全不同的二叉树。 问题:2. 对于下面的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() 答案:广义表对应的图形如下图所示，其中图1为树形结构，所以是纯表，图2中结点A为共享结点，则它属于再入表，图3中因为存在递归，则它属于递归表。 问题:3. 已知有如下一个关键字序列96,47,104,32,73,
9、136,15,38,90,180，按照上述插入顺序构造一棵二叉排序树，则请给出二叉排序树的构造过程，说明其深度，并在等概率的条件下求出平均查找长度。答案:根据二叉排序树的生成过程，我们可以得到如下二叉排序树的构造结果： 此二叉排序树的深度(即高度)为4，在二叉树上，要找到第i层上的结点恰好需要比较i次，而在此二叉排序树上，第1,2,3,4层上分别有1,2,3,4个结点，则在等概率的条件下，查找成功的平均查找长度为： 问题:4. 已知有一组长度为9的关键字序列为22,63,72,54,97,17,37,80,92，现在假设散列表的地址空间为T0.10，请用除余法构造散列函数，如果存在冲突问题，请
10、用线性探查法解决冲突，并给出相应的散列表。答案:因为散列函数为：h(key)=key%11，则根据此函数得到上述关键字序列的散列地址为：(0,8,6,10,9,6,1,3,4)，前5个关键字在插入时，其相应的地址是开放地址，可以直接插入到T0，T8，T6，T10，T9中，在插入到6个关键字时，其散列地址6已被关键字72占用，所以探查h1=(6+1)%11=7。此地址开放，所以将关键字17插入到T7中，然后再依次将关键字34，80，92插入到相应的散列地址中即可。则相应的散列袁为： 四、算法阅读题问题:1. 以下为单链表的建表算法，分析算法，请在_处填上正确的语句。 lklist create_
11、1klistl() /*通过调用intiate_lklist和insetr_lklist算法实现的建表算法。假定$是结束标志*/ ininiate_lklist(head); i=1; scanf(%,x); while(x!=$) _; _; scanf(%f,x); return(head); 该建表算法的时间复杂性约等于_，其量级为_。 答案:insert_lklist(head,x,i) i+ n(n-i)/2 O(n2)问题:2. 以下是图的深度优先搜索算法，请在_处填充适当的语句。 Dfs(GraphTp g,int v) ArcNodeTp*P; printf(%,v); vis
12、itedv=1; p=_; while(p!=NULL) if(!_)Dfs(g,padjvex); p=_; 答案:g.adjlistv.firstarc visitedpadjvex pnextarc问题:3. 以下为单链表的插入运算，分析算法，请在_处填上正确的语句。 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
13、=s; 答案:malloc(size) pnext问题:4. 根据文字说明，请在以下_处填充适当的语句。 采用静态链表作存储结构，设置一个大小为2n-1的数组，令数组的每个元素由四个域组成：wt是结点的权值；lehild、rchild分别为结点的左、右孩子指针；parent是结点的双亲在数组中的下标。其数组元素类型定义如下： typedef struet float wt; /*权值*/ int parent,lchild rchild; /*指针域*/ node; typedef node hftree2*n-1; 在这种存储结构上的哈夫曼算法可描述如下： void huffman(int
14、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.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)(Tj.parent=-1)n=m;y=_;m=_;x=j; else if(Tj.wtn)(Tj.parent=-1)n=Tj.wt;y=j;) Tx.par
15、ent=_;Ty.parent=_; Tk+i.wt=_; Tk+i.lchild=_;Tk+i.rchild=_; 答案:ik x Tj.wt k+i k+i m+n x y五、算法设计题问题:1. 从键盘上输入若干字符(每行长度不等)，输入后把它们存储到一磁盘文件中，再从该文件中读出这些数据，将其中小写字母转换成大写字母再进行屏幕输出。答案:本题的程序为： 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) stri=Z /*小写字母进行转换*/ stri=stri-32; printf(n%n,str); fclose(fp); /*main*/ 13 / 13