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

更多优质自考资料，请访问自考乐园俱乐部http://tieba.http://www.china-audit.com//club/5346389

2010年全国自考数据结构模拟试卷(五)

一、单项选择题(本大题共15小题,每小题2分,共30分)在每小题列出的四个备选项目中 只有一个是符号题目要求的,请将其代码填写的括号内.错选、多选或未选均无分。

1. 设矩阵A(aij,1≤i,j≤10)的元素满足：

aij≠0(i≥j,1≤i,j≤10) aij＝0(i

现将A的所有非0元素以行序为主序存放在首地址为2000的存储区域中，每个元素占4个单元，则 元素［9，5］的首地址为() 2164 2336 2340

答案：A

A. B. C. D.

2160

2. 循环队列用数组A［0…m-1］存放其元素值，已知其头尾指针分别是front和rear，则当前

队列中的元素个数是() rear-fomt+1 rear-fribt-1 rear-front

答案：A

A. B. C. D.

(rear-front+m)MOD m

3. 任何一个带权的无向连通图的最小生成树()

A. 只有一棵

B. 有一棵或多棵 C. 一定有多棵 D. 可能不存在

答案：B

4. 设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈

后即进入队列Q，若6个元素出列的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是() 4 3 2

答案：C

A. B. C. D.

6

5. 磁带适合存储的文件类型是()

A. 索引文件

更多优质自考资料，请访问自考乐园俱乐部http://tieba.http://www.china-audit.com//club/5346389

B. 顺序文件

C. 散列文件

D. 多关键字文件

答案：B

6. 带头结点的单链表head为空的判断条件是()

A. head=NULL

B. head->next=NULL C. head->next=head D. head!=NULL

答案：B

7. 在下图中，从顶点V1出发，按广度优选遍历图的顶点序列是()

V1V5V3V4V2V7V6 V1V7V2V6V4V5V3 V1V2V4V7V6V5V3

答案：A

A. B. C. D.

V1V5V3V4V2V6V7

8. 已知一棵二叉树结点的先根序列为ABDGCFK，中根序列为DGBAFCK，则结点的后根序列为()

A. ACFKBDG B. GDBFKCA C. KCFAGDB D. ABCDFKG

答案：B

9. C语言数组Data［m+1］作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针

，则执行出队操作的语句为()

A. front=front+1

更多优质自考资料，请访问自考乐园俱乐部http://tieba.http://www.china-audit.com//club/5346389

B. front=(front+1)%m C. rear=(rear+1)%m

D. front=(front+1)%(m+1)

答案：D

10. 任何一个带权的无向连通图的最小生成树()

A. 只有一棵

B. 有一棵或多棵 C. 一定有多棵 D. 可能不存在

答案：B

11. 将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右

的顺序对结点编号，那么编号为41的结点的双亲结点

编号为()

A. 42

B. 40 C. 21 D. 20

答案：D

12. 采用分治法进行排序的方法是()

A. 快速排序 B. 插入排序 C. 堆排序 D. 希尔排序

答案：A

13.

。

设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点总数量少()个

2k 2k-1 2k+1

答案：C

A. B. C. D.

k+1

14. 一个长度为10的有序表，按照二分查找法对该表进行查找，在表内各元素等概率的情况下

，查找成功所需要的平均比较次数为()

A. 25/10 B. 27/10 C. 29/10

更多优质自考资料，请访问自考乐园俱乐部http://tieba.http://www.china-audit.com//club/5346389

D. 31/10

答案：C

15. 索引非顺序文件是指()

A. 主文件无序，索引表有序

B. 主文件有序，索引表无序 C. 主文件有序，索引表有序 D. 主文件无序，索引表无序

答案：A

二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填写上正确 答案。错填、不填均无分。

1. 在B—树上进行删除操作分为两个步骤，即：___和___。

答案：在树上查找被删除关键字K所在的地点删除K

2. 在图的邻接表表示中，每个顶点邻接表中的顶点数，对于有向图来说是___，对于无向图来

说是___。

答案：出度数度数

3. 若一棵二叉树中只有叶结点和左、右子树皆非空的结点，设叶结点的个数为1，则左、右子

树皆非空的结点个数为___。 答案：1-1

4. 朴素的串匹配算法的特点是简单，但是其效率较低，其时间匹配算法的最坏时间是___(假

设模式串的长度是m,目标串的长度是n)。 答案：O(m+n)

5. 一个n×n的对称矩阵，如果以行为主序或以列为主序存入内存，则其容量为___。

答案：n×(n+1)/2

6. 假设在线索二叉树中，结点的标志域的值为0时，表示其指针域是指向孩子的指针，当结点

的标志域为1时，表示其指针域是指向前趋或者后继的线索，则一个结点是叶结点的充要条件是 ___。

答案：结点的左右标志都是1

7. 在分块查找法中，首先查找___，然后再查找相应的___。

答案：索引表 块

8. 对于一个二维数组A［m］［n］，若按行序为主序存储，则任一元素A［i］［j］相对于

A［0］［0］的地址为___。 答案：i×j+i全元素位置

9. 就文件而言，按用户的观点所确定的基本存储单元称为___。按外设的观点所确定的基本存

储单元称为___。