全国自考(数据结构)模拟试卷6_第1页
全国自考(数据结构)模拟试卷6_第2页
全国自考(数据结构)模拟试卷6_第3页
全国自考(数据结构)模拟试卷6_第4页
全国自考(数据结构)模拟试卷6_第5页
已阅读5页,还剩4页未读, 继续免费阅读

付费下载

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

全国自考(数据结构)模拟试卷6

一、单项选择题(本题共15题,每题1.0分,共15

分。)

1、在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的()

A、先序遍历

B、中序遍历

C、后序遍历

D、按层次遍历

标准答案:A

知识点解析:暂无解析

2、已知一个向量的第一个元素的存储地址是1。0,每个元素的长度为2,则第6个

元素的地址是()

A、120

B、112

C、110

D、114

标准答案:C

知识点解析:暂无解析

3、在单链表中,删除p所指结点的直接后继的操作是()

A、p—>ncxt=p->ncxt—>ncxt;

B、p=p->next;p—>next;p—>next—>next;

C、p->next=p—>next;

D、p=p>next>ncxt;

标准答案:A

知识点解析:哲无解析

4、深度为6(根的层次为1)的二叉树至多有()个结点。

A、31

B、32

C、63

D、64

标准答案:B

知识点解析:区无解析

5、设二叉树有F个结点,则其深度为()

A、n-1

B、n

c、51og2nj+l

D、不确定

标准答案:D

知识点解析:暂无解析

6、在图的邻接表存储结构上执行广度优先搜索遍历类似于二叉树上的()

A、先根遍历

B、中根遍历

C、后根遍历

D、按层次遍历

标准答案:D

知识点解析:暂无解析

7、一个栈的入栈序列为al.a2,a3,a4,a5,则此栈不可能的瑜出序列是()

A、a5,a4,a3,a2,al

B、a4,a5,a3,a2,al

C、a4,a3,a5.al,a2

al,a2,a3,a4,a5

标准答案:C

知识点解析:暂无解析

8、J殳rear是指向非空带头结点的循环单链表的尾指针,则删除起始结点的操作可

表示为()

A、s二rear;

B、rear=rear—>nexl;rear=rear—>next;free(rear);free(s);

C^rcar=rcar—>next—>ncxt;

D^s=rear—>next—>next:free(rear);rear—>next—>next=s—>next;free(s);

标准答案:D

知识点解析:暂无解析

9、以下有关数据结构的叙述,正确的是()

A、线性表的线性存储结构优于链式存储结构

B、二又树的第i层上有2i-l个结点,深度为K的二叉树上有2k-1个结点

C、二维数组是其数据元素为线性表的线性表

D、栈的操作方式是先进先出

标准比素.C

知识,解析:暂无解析

10、已知一个单链表中有3000个结点,每个结点存放一个整数,()可用于解决这

3000个整数的排序问题且不需要对算法作大的变动。

A、直接插入排序方法

B、简单选择排序方法

C、快速排序方法

D、堆排序方法

标准答案:D

知识点解析:暂无解析

11、二维数组M[i,j]的元素是4个字符(每个字符占一个存储单元)组成的串,行下

标i的范围从0到4,列下标j的范围从0到5。M按行存储时元素M[3,5]的起始

地址与M按列存储时元素()的起始地址相同。

A、M[2,4]

B、M[3,41

C、M[3,5]

D、M[4,4]

标准答案:B

知识点解析:暂无解析

12、在一棵二叉树中,第k层上最多有()个结点。

A、2k

B、2k-1

C、2k

D、2kd

标准答案:D

知识点解析:暂无解析

13、一棵二叉树如图所示,其中序遍历的序列为()

A、ABDGCEFH

B、DGBAECHF

C、GDBEHFCA

D、ABCDEFGH

标准答案:B

知识点解析:暂无解析

14、设计一个判别表:式中左、右括号是否配X,J出现的算法,采用()数据结构最

佳。

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

B、栈

C、队列

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

标准答案:B

知识点解析:暂无解析

15、设有一顺序栈S,元素S],S2,S3,S4,S5,S6依次进栈,如果6个元素出栈的

顺序是S2,S3,S4,S5,S6,S[,则栈的容量至少应该是()

A、2

B、3

C、5

D、6

标准答案:B

知识点解析:暂无解析

二、填空题(本题共10题,每题1.0分,共10分。)

16、在直接插入和直接选择排序中,如果初始数据基本正序,则选用,若初

始数据基本反序,则选用。

标准答案:直接插入排序直接选择排序

知识点解析:暂无解析

17、设一个链栈的栈顶指针为1s,栈中结点两个字段分别为info和next,其中next

是指示后继结点的指针,栈空的条件是o如果栈不空,则退栈操作为p:

=ls;;dispose(p)o

标准答案:ls=nuH这是指琏栈没有设置头结点的情况,•般情况下也不必设置1s:

=lsf.next;这一操作让头指针指示下一个结点

知识点解析:暂无解析

18、在分块查找法中,首先查找,然后再查找相应的。

标准答案:索引表块

知识点解析:暂无解析

19、对于一个二维数组若按行序为主序存储,则任一元素相对于

A[0][0]的地址为0

标准答案:ixj+i全元素位置

知识点解析:暂无解析

20、在一个按行优先顺序存储的二维数组(MxN)中,假设数组的基地址是P,并且

数组的每一个元素所占的存储空间为d个字节,则a[ij的地址计算公式为0

标准答案:LOC(a[ij)=P+[ixN+j]xd

知识点解析:暂无解析

21、对角矩阵中,除了的元素之外,其余的元素都是零。则对于一个k对角

线矩阵(k为奇数)A是满足下面的条件的矩阵;如果,则元素ahj=O。

标准答案:主对角线和主对角线相临两侧的若干条对角线上i>k或j>k

知识点解析:暂无解析

22、中结点的最大度数允许大于2,而中结点的最大度数不允许大于

2o

标准答案:树二叉树

知识点解析:暂无解析

23、计算机软件系统中,有两种处理字符串长度的方法:一种是采用,第二

种是o

标准答案:固定长度设置K度指针

知识点解析:暂无解析

24、在单链表中,除了首元结点外,任一结点的存储位置是由______指示。

标准答案:其直接前趋结点的链域的值

知识点解析:暂无解析

25、大多数排序算法都有诙个基本操作,它们是和o

标准答案:比较两个关键字的大小改变指向记录的指针或者移动记录本身

知识点解析:暂无解析

三、解答题(本题共4题,每题7.0分,共4分。)

26、对于下面用三元组表示的稀疏矩阵,请分别写出它们所对应的稀疏矩阵。

554576

02304-1

14-1061

12120一19

4013245

433

(1)<2)

标准答案:从三元组表还原稀疏矩阵时,首先根据表的第1行得出稀疏矩阵的行数

和列数,否则,我们无法确定所求的稀疏矩阵的维数,然后根据三元组表所提供的

行号和列号在稀疏矩阵的对应位置上写上相应的元素的值,在其他地方补零即可,

根据上述原则,此题答案如图(1),(2)所示。

rO0300-10000-101-1

01000-19000000

0000000450000

10000_0003000

⑴(2)

知识点解析:暂无解析

27、假设有下面所示的稀疏矩阵,请写出其三元组表(按行优先的顺序)。

010o

021

3o0o

0

0o0o

0O2OO

00001J

标准答案:稀疏矩阵的三元组指的是矩阵中非零元素的行号、列号和其对应的元

素,而三元组表就是将其结点是三元组的线性表按照顺序结构进行存储,其表的结

构为:(其中i代表行号,j代表列号,v指的是相应的元素值)

555

011

103

141

322

441

知识点解析:暂无解析

28、假设有一个长度为n的有序序列,在进行查找时,可以借助二叉树来进行,请

结合二叉树的性质来分析二分查找的最坏性能和平均性能。

标准答案:假设判定树的内部结点的总数为产2k」。则判定树是深度为

h=lg(n+l)的满二叉树,树中第k层上的结点的个数为2卜”,查找它们所需要比较的

次数是k。则在等概率下,二分查找成功时的平均查找长度为:

n°,如果n很大,则可以用如下近似公式:lg(n+l)-l,作为二分查

找成功时的平均查找长度。二分查找在查找失败时所需要比较的关键字的个数不超

过判定树的深度,在最坏情况卜.杳找成功的比较次数也不超过判定树的深度。因为

判定树中度数小于2的结点只可能在最下面的两层上

知识点解析:暂无解析

29、已知一棵二叉树按照顺序结构存储,其存储结构如下:

10ABCDHEFJGM

012345678910111213141516171819

则请回答如下问题:(1)请画出此二叉树的树形结构。(2)请写出此二叉树的前序遍

历、中序遍历和后序遍历序列。(3)此二叉树的高度是多少?(4)结点F的双亲、孩

子,以及祖先分别是什么?[5)此树中,度数为1的结点共有几个?分别是哪几个?

(6)结点C有左孩子吗?如果有左孩子,则C的左孩子的编号应该是什么?

BC

DH

标准答案:(1)此二叉树如图所示:-GQOM(2)前序遍历序列

为:ABDEFGMCHJ中序遍历序列为:EDGFMBACHJ后序遍历序歹U为:

七GMFDBAJHCQ)此树的高度是5。(4)结点卜的双亲是D,孩子是G,M(其中G

是其左孩子,M是其右孩子),祖先是D,B,Ao(5)此树中度数为1的结点共有3

个,分别为B,C,Ho(6)结点C没有左孩子,如果它有左孩子,则左孩子的编号

为6(2x3=6)

知识点解析:暂无解析

四、算法阅读题(本题共4题,每题上0分,共4分。)

30、以下为单链表按序号杳找的运算,分析算法,请在处填上正确的语句。

pointerfin(J-lklist(lklisti){p=head;j=O;while(){p=p—>next:j++:)

if(i==j)return(p);elsei'eturn(NULL);}

标准答案:(p—>nexl!=NULL)&&(jVi)

知识点解析:暂无解析

31、以下算法实现若开散列表HP中存在键值为K的结点.,则将其删除。请分析程

序,并在______上填充合适的语句。voiddelete_openhash(keytypeK,openhashHP)

{i=H(K);if(HP[i]==NULL)&urn;/*空表则退出*/p=HV[i];if(p—>

kcy==K){=p->ncxt;frcc(p);rcturn;)/*表首结点为待删除结点时的删除*/

while(p—>next!=NULL)/*其他情况下的删除*/{q=p;p=p—>next;if(p—>

key==K)(=p->next;delete(p);return;)}}

标准答案:HP[i]q—>next

知识点解析:暂无解析

32、以下运算实现在循环队上的出队列,请在______处用适当的语句予以填充。

intOutCycQueue(CycqueueTp*sq,DataType*x){if(sq—>front==){error("队空

");relum(0);)else{;;return(l);}}

标准答案:sq—>rearsq—>front=(sq—>front+1)%maxsizc*x=sq—>data[sq—>

front]

知识点解析:暂无解析

33、以下为求单链表表长的运算,分析算法,请在

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论