资源描述：
《2010年全国自考数据结构模拟试卷(二)及答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、2010年全国自考数据结构模拟试卷(二)一、单项选择题(本大题共15小题,每小题2分,共30分)在每小题列出的四个备选项目中只有一个是符号题目要求的,请将其代码填写的括号内.错选、多选或未选均无分。1.非空的循环单链表head的尾结点(由指针p所指)满足()A.p->next=NULLB.p=NULLC.p->next=headD.p=head答案：C2.邻接表存储结构下图的深度优先遍历算法结构类似于二叉树的()A.先序遍历B.中序遍历C.后序遍历D.按层遍历答案：A3.设图G采用邻接表存储，则拓扑
2、排序算法的时间复杂度为()A.O(n)B.O(n+e)C.O(n2)D.O(n×e)答案：B4.在Hash函数H(k)＝kMODm中，一般来讲，m应取()A.奇数B.偶数C.素数D.充分大的数答案：C5.对于一个具有N个顶点的图，如果我们采用邻接矩阵法表示，则此矩阵的维数应该是()A.(N-1)×(N-1)B.N×NC.(N+1)×(N+1)D.不确定答案：B6.快速排序在最坏情况下的时间复杂度是()A.AB.BC.CD.D答案：B7.已知一个单链表中有3000个结点，每个结点存放一个整数，()可
3、用于解决这3000个整数的排序问题且不需要对算法作大的变动。A.直接插入排序方法B.简单选择排序方法C.快速排序方法D.堆排序方法答案：D8.设计一个判别表达式中左、右括号是否配对出现的算法，采用()数据结构最佳。A.线性表的顺序存储结构B.栈C.队列D.线性表的链式存储结构答案：B9.顺序存储结构()A.仅适合于静态查找表的存储B.仅适合于动态查找表的存储C.既适合静态又适合动态查找表的存储D.既不适合静态又不适合动态查找表的存储答案：C10.用二分查找法对具有n个结点的线性表查找一个结点所需的平
4、均比较次数为()A.AB.BC.CD.D答案：D11.与其他查找方法相比，哈希查找法的特点是()A.通过关键字比较进行查找B.通过关键字计算记录存储地址进行查找C.通过关键字计算记录存储地址，并进行一定的比较进行查找D.通过关键字记录数据进行查找答案：C12.倒排文件的主要优点是()A.便于进行插入和删除运算B.便于进行文件的合并C.能大大提高基于非关键码数据项的查找速度D.能大大节省存储空间答案：C13.设数组A［0，m］作为循环队列sq的存储空间，front为队头指针，rear为队尾指针，则执行
5、入队操作的语句是()A.sq.front=(sq.front+1)%mB.sq.front=(sq.front+1)%(m+1)C.sq.rear=(sq.rear+1)%mD.sq.rear=(sq.rear+1)%(m+1)答案：D14.串是一种特殊的线性表，其特殊性体现在()A.可顺序存储B.数据元素是一个字符C.可链接存储D.数据元素可以是多个字符答案：B15.深度为k的二叉树，所含叶子的个数最多为()A.AB.BC.CD.D答案：C二、填空题（本大题共10小题，每小题2分，共20分）请在每
6、小题的空格中填写上正确答案。错填、不填均无分。1.从树的根结点到树中的其余结点之间的路径___惟一的。答案：是2.查找表中主关键字指的是___，次关键字指的是___。答案：能惟一标识数据元素的数据项不能惟一标识数据元素的数据项3.___的有向图，其全部顶点有可能排成一个拓扑序列。答案：存在入度为0的结点且没有回路4.如果一个图中有n条边，则此图的生成树含有___条边，所以生成树是图的边数___的连通图。答案：n-1最少5.在散列技术中，处理冲突的方法有：___和___。答案：开放定址法拉链法6.对于
7、一个长度为n的线性表，假设表中各结点的查找概率相同，则在查找成功的情况下，平均查找长度为___，如果k不在表中，则需要进行___次比较后才能确定查找失败。答案：(n+1)/2n+17.查找表按其所包括的运算的不同分为___查找表和___查找表。答案：静态动态8.给定一个具有n个元素的向量，建立一个有序单链表的时间复杂度是___。答案：9.设线性表(a1,a2，…，a500)元素的值由小到大排列。对一个给定的k值，用二分法检索查找表中与k相等的元素，在检索不成功的情况下，至多需比较___次。答案：91
8、0.设有一元多项式A(x)＝7+3x+10x30-4x100+13x101，用单链表给出A(x)的存储表示为___。答案：三、解答题（本大题共4小题，每小题5分，共20分）1.已知串S=‘(xyz)*’,t=‘(x+z)*y’,试利用串的基本运算将s串转化为t串，t串转化为s串。答案：t=CONCAT(Rep(sup(s,1,5),‘y’,‘+’),Rep(sub(s,6,1),‘*’,‘*y’))s=CONCAT(Rep(sub(t,1,5),‘+’,‘y’),Re
