[自学考试密押题库与答案解析]数据结构自考题模拟7

1、自学考试密押题库与答案解析数据结构自考题模拟7自学考试密押题库与答案解析数据结构自考题模拟7数据结构自考题模拟7一、单项选择题在每小题列出的四个选项中只有一个选项是符合题目要求的。问题:1. 设有一个用线性探测法解决冲突得到的散列表： 散列函数为H(k)=Kmod 11 若要查找元素14，探测的次数(比较的次数)是 A.8B.9C.3D.6答案:D问题:2. 如果二叉树中任何一个结点的值都小于它的左子树上所有结点的值而大于右子树上所有结点的值，要得到各结点值的递增序列，应按下列哪种次序排列结点A.先根B.中根C.后根D.层次答案:B问题:3. 对含有 个结点的非空二叉树，采用任何一种遍历方式，

2、其结点访问序列均相同。A.OB.1C.2D.不存在这样的二叉树答案:B问题:4. 含N个顶点的连通图中的任意一条简单路径，其长度不可能超过A.1B.N/2C.N-1D.N答案:C问题:5. 顺序存储结构A.仅适合于静态查找表的存储B.仅适合干动态查找表的存储C.既适合静态又适合动态查找表的存储D.既不适合静态又不适合动态查找表的存储答案:C问题:6. 已知一采用开放地址法解决Hash表冲突，要从此Hash表中删除一个记录，正确的做法是A.将该元素所在的存储单元清空B.将该元素用一个特殊的元素替代C.将与该元素有相同Hash地址的后继元素顺次前移一个位置D.用与该无素有相同Hash地址的最后插入

3、表中的元素替代答案:B问题:7. 邻接表存储结构下图的广度优先遍历算法结构类似于树的A.先根遍历B.后根遍历C.按层遍历D.先序遍历答案:C问题:8. 下列说法中正确的是A.二叉树中任何一个结点的度都为2B.二叉树的度为2C.任何一棵二叉树中至少有一个结点的度为2D.一棵二叉树的度可以小于2答案:D问题:9. 已知一棵二叉树结点的先根序列为ABDGCFK，中根序列为DGBAFCK，则结点的后根序列为A.ACFKBDGB.GDBFKCAC.KCFAGDBD.ABCDFKG答案:B问题:10. 用二分查找法对具有n个结点的线性表查找一个结点所需的平均比较次数为A.O(n2)B.O(nlog2n)C

4、.O(n)D.O(log2n)答案:LOD问题:11. 与其他查找方法相比，哈希查找法的特点是A.通过关键字比较进行查找B.通过关键字计算记录存储地址进行查找C.通过关键字计算记录存储地址，并进行一定的比较进行查找D.通过关键字记录数据进行查找答案:C问题:12. 下列说法正确的是A.树的先根遍历序列与其对应的二叉树的先根遍历序列相同B.树的先根遍历序列与其对应的二叉树的后根遍历序列相同C.树的后根遍历序列与其对应的二叉树的先根遍历序列相同D.树的后根遍历序列与其对应的二叉树的后根遍历序列相同答案:A问题:13. 设串s1=ABCDEFG，s2=PQRST，函数con(x,y)返回x和y串的连

5、(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的con(subs(s1，2，len(s2)，subs(s1，len(s2)，2)的结果串是A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF答案:D问题:14. 设二叉树根结点的层次为0，一棵高度为h的满二叉树中的结点个数是A.2hB.2h-1C.2h-1D.2h+1-1答案:D问题:15. 顺序查找法适用于存储结构为 的线性表。A.散列存储B.压缩存储C.顺序存储或链接存储D.索引存储答案:C二、填空题问题:1. 在直接插入和直接选择排序中，如果初始数据基本正序，则选用_，若初始数据基本反序

6、，则选用_。答案:直接插入排序 直接选择排序问题:2. 设一个链栈的栈顶指针为ls，栈中结点两个字段分别为info和next，其中next是指示后继结点的指针，栈空的条件是_。如果栈不空，则退栈操作为p：=ls；_；dispose(p)。答案:ls=null这是指链栈没有设置头结点的情况，一般情况下也不必设置ls：=ls.next；这一操作让头指针指示下一个结点问题:3. 在分块查找法中，首先查找_，然后再查找相应的_。答案:索引表块问题:4. 对于一个二维数组Amn，若按行序为主序存储，则任一元素Aij相对于A00的地址为_。答案:ij+i全元素位置问题:5. 在一个按行优先顺序存储的二维数

7、组(MN)中，假设数组的基地址是P，并且数组的每一个元素所占的存储空间为d个字节，则aij的地址计算公式为_。答案:LOC(aij)=P+iN+jd问题:6. 对角矩阵中，除了_的元素之外，其余的元素都是零。则对于一个k对角线矩阵(k为奇数)A是满足下面的条件的矩阵；如果_，则元素aij=0。答案:主对角线和主对角线相临两侧的若干条对角线上 ik或jk问题:7. _中结点的最大度数允许大于2，而_中结点的最大度数不允许大于2。答案:树 二叉树问题:8. 计算机软件系统中，有两种处理字符串长度的方法：一种是采用_，第二种是_。答案:固定长度 设置长度指针问题:9. 在单链表中，除了首元结点外，任

8、一结点的存储位置是由_指示。答案:其直接前趋结点的链域的值问题:10. 大多数排序算法都有两个基本操作，它们是_和_。答案:比较两个关键字的大小 改变指向记录的指针或者移动记录本身三、解答题问题:1. 对于散列文件来说，其存储单位是什么?对于一个能存储m个桶，若需要存放的同义词大于m，则需要如何处理?现在假设一个文件有18个记录，其关键字分别为：30,11,27,04,19,86,73,89,32,05,103,58,45,67,77,81,08,48，假设桶的容量m=3，桶数b=7，现在要求用除余法做散列函数H(key)=key%7，请给出该散列文件的表示方法。答案:磁盘上的文件记录通常是成

9、组存放的，若干个记录组成一个存储单位，在散列文件中，这个存储单位叫做桶。 如果一个桶能放m个记录，则如果现在已经存放了m个记录时，继续存放记录就会产生“溢出”，当发生“溢出”时，一般采用拉链法，就是将第m+1个同义词存放在另外_个桶中，通常此桶就称为“溢出桶”，相应的前m个同义词存放的桶就称为是“基桶”，溢出桶和基桶大小相同。 根据散列函数，得到对应的关键字的散列地址为：2,4,6,4,5,2,3,5,4,5,5,2,3,4,0,4,1,6，则得到的散列文件表示如下： 问题:2. 已知下面的一个图，请根据普里姆算法构出它的一棵最小生成的树。 答案:构造最小生成树的过程如下： 问题:3. 假设在

10、树中，如果结点x是结点y的双亲时，用(x,y)来表示树边，已知一棵树的树边的集合为(i,m)，(i,n)，(e,i)，(b,e)，(b,d)，(a,b)，(g,j)，(g,k)，(c,g)，(c,f)，(h,l)，(c,h)，(a,c)，请用树形结构画出此树，并回答下面的问题。 (1)哪个是根结点? (2)哪些是叶结点? (3)哪个是g的双亲? (4)哪些是g的祖先? (5)哪些是g的孩子? (6)哪些是e的子孙? (7)哪些是e的兄弟? (8)树的深度是多少? (9)树的度数是多少? 答案:树的结构如下图所示： (1)a是根结点 (2)m,n,d,f,l,j,k是叶结点 (3)c是g的双亲

11、(4)a和e是g的祖先 (5)j,k是g的孩子 (6)i,m,n是e的子孙 (7)d是e的兄弟 (8)树的深度是5 (9)树的度数是3 问题:4. 对于如图所示的二叉树，请画出其顺序存储结构图。 答案:二叉树的顺序存储就是将二叉树的结点按编号存在向量B0,n中，其中B0用来存放结点T数，如果树中某些编号对应的结点不存在，则对应存储空间为“空”，根据上述规则，我们得到： 四、算法阅读题问题:1. INITIATE()的功能是建立一个空表。请在_处填上正确的语句。 lklist initiate_lklist() /*建立一空表*/ _; _; return(t); 答案:t=malloc(siz

12、e) tnext=NULL问题:2. 以下运算实现在顺序栈上的退栈，请在_处用适当的语句予以填充。 int Pop(SqStackTp*sq,DataType*x) if(sqtop=0)error(下溢);return(0);) else*x=_; _; return(1); 答案:sqdatasqtop sqtop-问题:3. 以下算法在开散列表HP中查找键值等于K的结点，成功时返回指向该点的指针，不成功时返回空指针。请分析程序，并在_上填充合适的语句。 pointer research_openhash(keytype K,openhash HP) i=H(K); /*计算K的散列地址*

13、/ p=HPi; /*i的同义词子表表头指针传给P*/ while(_)p=pnext; /*未达到表尾且未找到时，继续扫描*/ _; 答案:(P!=NULL)(*b).nu=a.mu;(*b).tu=a.tu if(a.tu) q=1; for(col=1;_;col+) for(p=1;p=a.tu;p+) if(_)=col) (*b).dataq.i=a.datap.j; (*b).dataq.j=a.datap.i; (*b).dataq.v=a.datap.v; _; 答案:col=a.nu a.datap.j q+五、算法设计题问题:1. 写出向某个有序文件中插入一个记录的程序。

14、答案:所谓有序文件是指文件的记录按关键字由小到大(或由大到小)顺序存放。为方便起见，可设文件的每一个记录是一个整数，文件上数据是按由小到大顺序存放。设插入数据是命令行的第3个参数，且设为d。若原文件中没有数据，则d写入文件；若有数据，则找到第1个比d大的数据i，先写入d，再将i和其后各数据写回文件中，可通过调用fseek函数采实现插入。相应程序为： #includestdio.h #includestdlib.h #includeio.h #includefcntl.h #define LEN sizeof(int) void main(int argi,char*argc) int fp,i,d; if(argi3) printf(filename int11) exit(0); d=atoi(argc2); fp=open(argc1,O_GREAT| O_RDWRI O_BINARY,s_IREAD| S_IWRI