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

《全国自考数据结构模拟试卷(一)及答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2010年全国自考数据结构模拟试卷(一)一、单项选择题(本大题共15小题,每小题2分,共30分)在每小题列出的四个备选项目中只有一个是符号题目要求的,请将其代码填写的括号内.错选、多选或未选均无分。1.若用冒泡排序法对序列18，14，6，27，8，12，16，52，10，26，47，29，41，24从小到大进行排序，共要进行()次比较。A.33B.45C.70D.912.假定一棵二叉树的结点为18个，则此二叉树的最大高度为()，最小高度为()A.4B.5C.6D.183.一个具有N个顶点的有向图最多有()条边。A.N

2、(N-1)/2B.N(N-1)C.N(N+1)D.N(N+1)/24.设一个数组中，行下标i的范围是从1到8，列下标的范围是从1到10，假设此数组的初始存储地址是A，则如果将此数组按照列优先的顺序连续存放，则元素Q［5］［8］的起始地址是()A.1B.23C.24D.5295.下面程序的时间复杂性是()for(i=1;i<=n;i++)for(j=1;j<=m;j++){A［i］［j］=i*j;}A.AB.BC.CD.D6.在下面的排序方法中，不需要通过比较关键字就能进行排序的是()A.箱排序B.快速排序C.插入排

3、序D.希尔排序7.设散列函数为H(k)＝kmod7，一组关键码为23，14，9，6，30，12和18，散列表T的地址空间为0.6，用线性探测法解决冲突，依次将这组关键码插入T中，得到的散列表为()A.AB.BC.CD.D8.排序的重要目的是为了以后对已排序的数据元素进行()A.打印输出B.分类C.查找D.合并9.线性表L＝(a1，a2，…，a1，…，an)，下列说法正确的是()A.每个元素都有一个直接前趋和直接后继B.线性表中至少要有一个元素C.表中诸元素的排列顺序必须是由小到大或由大到小的D.除第一个元素和最后一

4、个元素外，其余每个元素都有一个且仅有一个直接前趋和直接后继10.邻接表存储结构下图的广度优先遍历算法结构类似于树的()A.先根遍历B.后根遍历C.按层遍历D.先序遍历11.下列说法中正确的是()A.二叉树中任何一个结点的度都为2B.二叉树的度为2C.任何一棵二叉树中至少有一个结点的度为2D.一棵二叉树的度可以小于212.在一个具有n个单元的顺序栈中，假设栈底是存储地址的高端，现在我们以top作为栈顶指针，则作退栈操作时，top的变化是()A.top=top-1B.top=top+1C.top不变D.top不确定13.

5、堆排序的最坏时间复杂度为()A.AB.BC.CD.D14.如果待排序的记录的规模很大，则在下面的排序方式中，我们最好不要选择使用()A.快速排序B.直接插入排序C.堆排序D.归并排序15.将含100个结点的完全二叉树从根这一层开始，每层从左到右依次对结点编号，根结点的编号为1。编号为71的结点的双亲的编号为()A.34B.35C.36D.无法确定二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填写上正确答案。错填、不填均无分。1.严格地讲，二维数组不是一种线性表，但数组可以看成是线性表在下述含

6、义上的扩展：二维数组的数据元素是___的线性表。答案：线性表2.设二维数组A［10··20，5··10］按行优先存储，每个元素占4个存储单元，A［10，5］的存储地址是1000，则A［15，10］的存储地址是___。答案：17003.在线性表的顺序存储中，元素之间的逻辑关系是通过___决定的；在线性表的链接存储中，元素之间的逻辑关系是通过___决定的。答案：相邻位置链接指针4.多维数组和广义表是一种非常复杂的非线性结构，它们的逻辑特点是___。答案：一个数据元素可能有多个直接前趋和多个直接后继5.数组0［1……n］表

7、示一个环形队列，设f的值为队列中第一个元素的位置，r的值为队列中实际队尾元素的位置加1，并假定队列中至多只有n-1个元素，则计算队列中元素个数的公式为___。答案：(n+r-f)modn6.在具有n个单元的循环队列中，队满时共有___个元素。答案：n-17.内部排序的方法可以分为五类：___、___、___、___、___。答案：插入排序选择排序交换排序归并排序分配排序8.在单链表中，除了首元结点外，任一结点的存储位置是由___指示。答案：其直接前趋结点的链域的值9.拓扑排序指的是找一个有向图的___的过程。答案：拓

8、扑序列10.在双向链表中，每个结点含有两个指针域，一个指向其___结点，另一个指向___结点。答案：前趋后继三、解答题（本大题共4小题，每小题5分，共20分）1.答案：(1)第一种表示需要n+2个实数存储单元，其中n为多项式的最高幂数；第二种表示需要2m+1个实数存储单元，其中m为非零系数的个数。显然，当非零系数较少时(m＜（n+1）/2)，第