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

自考数据结构历年真题很不错

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

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

1. 非空的循环单链表head的尾结点(由指针p所指)满足()

A. p->next=NULL

B. p=NULL

C. p->next=head

D. p=head

答案：C

2. 邻接表存储结构下图的深度优先遍历算法结构类似于二叉树的()

A. 先序遍历

B. 中序遍历

C. 后序遍历

D. 按层遍历

答案：A

3. 设图G采用邻接表存储，则拓扑排序算法的时间复杂度为()

A. O(n)

B. O(n+e)

C. O(n2)

D. O(n×e)

答案：B

4. 在Hash函数H(k)＝k MOD m中，一般来讲，m应取()

A. 奇数

B. 偶数

C. 素数

D. 充分大的数

答案：C

5. 对于一个具有N个顶点的图，如果我们采用邻接矩阵法表示，则此矩阵的维数应该是()

A. (N-1)×(N-1)

B. N×N

C. (N+1)×(N+1)

D. 不确定

答案：B

6. 快速排序在最坏情况下的时间复杂度是()

自考数据结构历年真题很不错

A. A

B. B

C. C

D. D

答案：B

7. 已知一个单链表中有3000个结点，每个结点存放一个整数，()可用于解决这3000个整数的 排序问题且不需要对算法作大的变动。

简单选择排序方法

快速排序方法

堆排序方法

答案：D

A. B. C. D. 直接插入排序方法

8. 设计一个判别表达式中左、右括号是否配对出现的算法，采用()数据结构最佳。

A. 线性表的顺序存储结构

B. 栈

C. 队列

D. 线性表的链式存储结构

答案：B

9. 顺序存储结构()

A. 仅适合于静态查找表的存储

B. 仅适合于动态查找表的存储

C. 既适合静态又适合动态查找表的存储

D. 既不适合静态又不适合动态查找表的存储

答案：C

10. 用二分查找法对具有n个结点的线性表查找一个结点所需的平均比较次数为()

A

B

C

D

答案：D

A. B. C. D.

11. 与其他查找方法相比，哈希查找法的特点是()

A. 通过关键字比较进行查找

B. 通过关键字计算记录存储地址进行查找

自考数据结构历年真题很不错

C. 通过关键字计算记录存储地址，并进行一定的比较进行查找

D. 通过关键字记录数据进行查找

答案：C

12. 倒排文件的主要优点是()

A. 便于进行插入和删除运算

B. 便于进行文件的合并

C. 能大大提高基于非关键码数据项的查找速度

D. 能大大节省存储空间

答案：C

13. 设数组A［0，m］作为循环队列sq的存储空间，front为队头指针，rear为队尾指针，则执 行入队操作的语句是()

sq.rear=(sq.rear+1)%m

sq.rear=(sq.rear+1)%(m+1)

答案：D

A. B. C. D. sq.front=(sq.front+1)%m sq.front=(sq.front+1)%(m+1)

14. 串是一种特殊的线性表，其特殊性体现在()

A. 可顺序存储

B. 数据元素是一个字符

C. 可链接存储

D. 数据元素可以是多个字符

答案：B

15. 深度为k的二叉树，所含叶子的个数最多为()

A

B

C

D

答案：C

A. B. C. D.

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

1. 从树的根结点到树中的其余结点之间的路径___惟一的。

答案：是

自考数据结构历年真题很不错

2. 查找表中主关键字指的是___，次关键字指的是___。

答案：能惟一标识数据元素的数据项不能惟一标识数据元素的数据项

3. ___的有向图，其全部顶点有可能排成一个拓扑序列。

答案：存在入度为0的结点且没有回路

4. 如果一个图中有n条边，则此图的生成树含有___条边，所以生成树是图的边数___的连通图 。

答案：n-1 最少

5. 在散列技术中，处理冲突的方法有：___和___。

答案：开放定址法 拉链法

6. 对于一个长度为n的线性表，假设表中各结点的查找概率相同，则在查找成功的情况下，平 均查找长度为___，如果k不在表中，则需要进行___次比较后才能确定查找失败。

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

7. 查找表按其所包括的运算的不同分为___查找表和___查找表。

答案：静态 动态

8. 给定一个具有n个元素的向量，建立一个有序单链表的时间复杂度是___。

答案：

9. 设线性表(a1,a2， ，a500)元素的值由小到大排列。对

一个给定的k值，用二分法检索查找表中与k相等的元素，在检索不成功的情况下，至多需比较 ___次。

答案：9

10. 设有一元多项式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’),Rep(sub(t,6,2),‘*y’,‘*’))

自考数据结构历年真题很不错

2. 已知有一关键字序列为{486，79，596，34，900，120，789，179，703，307}，如果我们 采用基数排序方法对此序列进行排序(按照升序排列)，请给出每一趟的排序结果。

答案：基数排序的基本思想是：从低位到高位依次对kj(j=d-1,d-2 0)进行箱排序，根据基数排 序法的基本方法，我们得到如下的排序结果：

初始：486，79，596，34，900，120，789，179，703，307

第1趟：(按个位进行排序)：120，900，703，34，486，596，307，79，179，389

第2趟：(按十位进行排序)：307，703，900，120，34，79，179，486，789，596

第3趟：(按百位进行排序)：34，79，120，179，307，486，596，703，789，900

3. 对于散列文件来说，其存储单位是什么?对于一个能存储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，请给出该散列文件的表示方法 。

答案：磁盘上的文件记录通常是成组存放的，若干个记录组成一个存储单位，在散列文件中，这 个存储单位叫做桶。

如果一个桶能放m个记录，则如果现在已经存放了m个记录时，继续存放记录就会产生“溢出 ”，当发生“溢出”时，一般采用拉链法，就是将第m+1个同义词存放在另外一个桶中，通常此 桶就称为“溢出桶”，相应的前m个同义词存放的桶就称为是“基桶”，溢出桶和基桶大小相同 。

根据散列函数，得到对应的关键字的散列地址为

：2，4，6，4，5，2，3，5，4，5，5，2，3，4，0，4，1，6，则得到的散列文件表示如下：

4. 假设在树中，如果结点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的双亲

(4)a和c是g的祖先

(5)j,k是g的孩子

(6)i,m,n是e的子孙

(7)d是e的兄弟

(8)树的深度是5

(9)树的度数是3

四、算法阅读题（本大题共4小题，每小题5分，共20分）

1. 请将下面的程序改成递归的过程。

voide ditui (int n)

{int i;

i=n;

while(i>1)

prinft(i--);

}

自考数据结构历年真题很不错

答案：此递推过程可以改写成如下递归过程：

voide ditui (int j)

{if(i>1)

{printf(j);

digui(j-1);

}

}

2. 以下为单链表的建表算法，分析算法，请在___处填上正确的语句。

lklist create-lklist2()/*直接实现的建表算法。*/

{ head=malloc(size);

p=head;

scanf(″%f″,&x);

while(x!=′$′)

{ q=malloc(size);

q->data=x;

p->next=q;

___;

scanf(″%f″,&x);

}

___;

return(head);

}

此算法的量级为___。

答案：p=q p->next=NULL O(n)

3. 下列算法用于判断带头结点的循环双链表A是否对称相等，请在算法中的___处填上正确的 语句。

int dlink_symmetry (dlklist s)

｛ j=true;

p=s->next;

q=s->prior;

while(p!=q)&(___)

if(p->data=q->data)

｛ (___);

(___);

｝

else

j=false;

return(j);

｝

自考数据结构历年真题很不错

答案：p->prior! =q‖q->next! =p p=p->next q=q->prior。

4. 以下将ah, am,和am+1, an,两个有序序列(它们相应的关键字值满足

Kh≤Km,Km+1≤ Kn,)合并成一个有序序列Rh, ，Rn,(使其关键字值

满足Kh,′≤ ≤Kn,′)。请分析算法，并在___上填充适当的语句。

void merge(list a,list R,int h,int m,int n)

{i=h;k=h;j=m+1;

while((i<m)&&(j<=n))

{ if(a［i］.key<=a［j］.key){ R［k］=___;___ ;}

else{ R［k］=___; ___;}

k++;

}

while(i<=___){R［k］=a［i］;i++;k++;}

while(j<=___){R［k］=a［j］;j++;k++;}

}

此算法的执行时间为___。

答案：a［i］ i++ a［j］ j++ m n O(n-h+1)

五、算法设计题（本题10分）

1. 假设在表示一棵二叉树的二叉链表上增加两个域，双亲域用于指示其双亲结点，标志域 flag(可取，0 2)的值，用以区分在遍历过程中到达该结点时继续向左或向右或访问该结点。试 以此存储结构编写不用栈进行后序遍历的递推形式的算法。

答案：要解答该题必须分析结点所在的状态，这可以通过结点的标志域来进行。对一个结点来说 ，当前的结点可能由：(1)其双亲结点转换；(2)其左子树遍历结束转换；(3)其右子树遍历结束 转换。所以算法主要执行按这三种状态进行处理或处理当前结点切换结点的状态。从而可将算法 描述为：

void postorder (r) /*后序遍历此二叉树*/

bitree *t /*设为bitree类型的结点含四个域：flag,parent,lchild,rchild,其中flag的域初值 为0，指针t指向根结点*/

{ bitree *p;

p=t;

while(p!=Null)

switch(->flag)

{ case0:p->flag=1;

if (p->lchild!=Null)

p=p->lchild;

break;

case1:p->flag=2

自考数据结构历年真题很不错

更多优质自考资料尽在百度贴吧自考乐园俱乐部

（/club/5346389）欢迎 加入...欢迎 交流...止不住的惊喜等着你.........

if (jp->rchild!=Null)

p=p->rchild;

break;

case2:p->flag=0;

printf(p->data);

p=jp->parent;

break;

default;

}

}/*postorder*/

自考乐园,自考学习交流、资料共享的好去处！

自考乐园,自考人自己的家园....

俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id,可以

直接进入俱乐部

本文来源：https://www.bwwdw.com/article/wxu1.html