2010年全国自考数据结构模拟试卷(三)及答案.doc

2010年全国自考数据结构模拟试卷(三) 一、单项选择题(本大题共15小题,每小题2分,共30分)在每小题列出的四个备选项目中 只有一个是符号题目要求的,请将其代码填写的括号内.错选、多选或未选均无分。 1. 如果要求一个线性表适应动态变化的要求，又必须能尽快地进行查找，则可以选择采用 ()查找方法。 A. 分块 B. 二分 C. 顺序 D. 散列 答案：A 2. 若已知一个栈的输入序列为1，2，3…，n，其输出序列为P1，P2，…，Pn。若P1＝n，则 P1为() A. i B. n＝i C. n-i+1 D. 不确定 答案：C 3. 如果一个队列的入队顺序是1，2，3，4，5，则此队列的出队顺序是() A. 5，4，3，2，1 B. 4，5，1，2，3 C. 1，2，3，4，5 D. 不确定 答案：C 4. 下面关于线性表的叙述错误的是() A. 线性表采用顺序存储，必须占用一片连续的存储单元 B. 线性表采用顺序存储，便于进行插入和删除操作 C. 线性表采用链接存储，不必占用一片连续的存储单元 D. 线性表采用链接存储，不便于插入和删除操作 答案：A 5. 设有两个串p和q，求q在p中首次出现的位置的运算称为() A. 连接 B. 模式匹配 C. 求子串 D. 求串长 答案：B  6. 对于shell排序来说，给定的一组排序数值为 49，38，65，97，13，27，49，55，04 则第二趟排序后的结果为() A. 04，13，27，49，49，38，55，65，76，97 B. 04，13，27，38，49，49，55，65，76，97 C. 13，04，49，38，27，49，55，65，97，76 D. 13，27，49，55，04，49，38，65，97，76 答案：C   7. 一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是() A. e d c b a B. d e c b a C. d c e a b D. a b c d e 答案：C 8. 在图的邻接表存储结构上执行广度优先有哪些信誉好的足球投注网站遍历类似于二叉树上的() A. 先根遍历 B. 中根遍历 C. 后根遍历 D. 按层次遍历 答案：D 9. 设串s1=′ABCDEFG′,s2=′PQRST′,函数con(x,y)返回x和y串的连(s,i,j)返回串s的从序 号i的字符开始的j个字符组成的子串，len(s)返回串s的 con(subs(s1,2,len(s2)),subs(s1,len(s2),2)的结果串是() A. BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF 答案：D 10. 对采用二分查找法进行查找运算的查找表，要求按()方式进行存储。 A. 顺序存储 B. 链式存储 C. 顺序存储且结点按关键字有序 D. 链式存储且结点按关键字有序 答案：C 11. 对于一个具有N个结点和E条边的无向图，若采用邻接表示，则表头向量的大小是() A. N B. N+1  C. N-E D. N-1 答案：A   12. 判断一个有向图是否存在回路，除了可以利用拓扑排序方法，还可以利用() A. 求关键路径的方法 B. 求最短路径的Dijkstra方法 C. 广度优先遍历方法 D. 深度优先遍历方法 答案：D 13. 链栈与顺序栈相比，有一个比较明显的优点即（） A. 插入操作更加方便 B. 通常不会出现栈满的情况 C. 不会出现栈空的情况 D. 删除操作更加方便 答案：B 14. 串是任意有限个() A. 符号构成的集合 B. 符号构成的序列 C. 字符构成的集合 D. 字符构成的序列 答案：D 15. 如图所示二叉树的中序遍历序列是() A. a b c d g e f B. d f e b a g c C. d b a e f c g D. d e f b a g c 答案：B 二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填写上正确 答案。错填、不填均无分。 1. 已知广义表A=((a,b,c),(d,e,f)),则运算head(head(tail(tail(A))))=___. 答案：e 2. 记录的___结构是数据在物理存储器上的存储方式。 答案：物理 3. 数组的长度是___，线性表的长度是___。  答案：固定的 可变的   4. 在线性表的顺序存储中，假设每个结点所占用的存储空间为c,且第一个单元的存储地址则 是该结点的存储地址，设开始结点a1的存储地址是LOC(a1)，则结点a1存储地址LOC(a1)可以通过 下式得到___。 答案：LOC(a1)=LOC(a1)+(i-1)*c 5. 树的结点数目至少为___，二叉树的结点数目至少为___。 答案：1