全国自考《数据结构导论》真题及_第1页
全国自考《数据结构导论》真题及_第2页
全国自考《数据结构导论》真题及_第3页
全国自考《数据结构导论》真题及_第4页
全国自考《数据结构导论》真题及_第5页
已阅读5页,还剩4页未读 继续免费阅读

下载本文档

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

文档简介

精品文档-下载后可编辑全国自考《数据结构导论》真题及全国自考《数据结构导论》真题解析

一、单选题(共30题,共60分)

1.在顺序表中查找第i个元素,时间效率最高的算法的时间复杂度为()

A.O(1)

B.O(√n)

C.O(log2n)

D.O(n)

2.树形结构中,度为0的结点称为()

A.树根

B.叶子

C.路径

D.二叉树

3.已知有向图G=(V,E),其中V={V1,V2,V3,V4,V5,V6,V7},E={},则图G的拓扑序列是()

A.V1,V3,V4,V6,V2,V5,V7

B.V1,V3,V2,V6,V4,V5,V7

C.V1,V3,V4,V5,V2,V6,V7

D.V1,V2,V5,V3,V4,V6,V7

4.有关图中路径的定义,表述正确的是()

A.路径是顶点和相邻顶点偶对构成的边所形成的序列

B.路径是不同顶点所形成的序列

C.路径是不同边所形成的序列

D.路径是不同顶点和不同边所形成的集合

5.串的长度是指()

A.串中所含不同字母的个数

B.串中所含字符的个数

C.串中所含不同字符的个数

D.串中所含非空格字符的个数

6.组成数据的基本单位是()

A.数据项

B.数据类型

C.数据元素

D.数据变量

7.程序段的时间复杂度为()

A.O(1)=

B.O(n)

C.O(n2

D.O(n3)

8.与串的逻辑结构不同的数据结构是()

A.线性表

B.栈

C.队列

D.树

9.二叉树的第i(i≥1)层上所拥有的结点个数最多为()

A.

B.2i

C.

D.

10.设单链表中指针p指向结点A,若要删除A的直接后继,则所需修改指针的操作为()

A.p-next=p-next-next

B.p=p-next

C.p=p-next-next

D.p-next=p

11.下列排序算法中,某一趟结束后未必能选出一个元素放在其最终位置上的是()

A.堆排序

B.冒泡排序

C.直接插入排序

D.快速排序

12.设字符串S1=″ABCDEFG″,S2=″PQRST″,则运算S=CONCAT(SUBSTR(S1,2,LENGTH(S2)),SUBSTR(S1,LENGTH(S2),2))后S的结果为()

A.″BCQR″

B.″BCDEF″

C.″BCDEFG″

D.″BCDEFEF″

13.在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为A,并且A的左孩子的平衡因子为-1,右孩子的平衡因子为0,则使其平衡的调整方法为()

A.LL型

B.LR型

C.RL型

D.RR型

14.如果结点A有3个兄弟结点,而且B为A的双亲,则B的度为()

A.1

B.3

C.4

D.5

15.数据表A中每个元素距其最终位置较近,则最省时间的排序算法是()

A.堆排序

B.插入排序

C.直接选择排序

D.快速排序

16.在表长为n的顺序表上做插入运算,平均要移动的结点数为()

A.n/4

B.n/3

C.n/2

D.n

17.顺序表中有19个元素,第一个元素的地址为200,且每个元素占一个字节,则第14个元素的存储地址为()

A.212

B.213

C.214

D.215

18.由顶点V1,V2,V3构成的图的邻接矩阵为,则该图中顶点V1的出度为(C)

A.0

B.1

C.2

D.3

19.元素的进栈次序为A,B,C,D,E,则退栈中不可能的序列是()

A.A,B,C,D,E

B.B,C,D,E,A

C.E,A,B,C,D

D.E,D,C,B,A

20.由带权为9,2,5,7的四个叶子结点构造一棵哈夫曼树,该树的带权路径长度为()

A.23

B.37

C.44

D.46

21.在已知尾指针的单循环链表中,插入一个新结点使之成为首结点,其算法的时间复杂度为()

A.O(1)

B.(log2n)

C.O(n)

D.O(n2)

22.已知一个有序表为(13,18,24,35,47,50,62,83,90,115,134),当二分查找值为90的元素时,查找成功时需比较的次数为()

A.1

B.2

C.3

D.4

23.在查找顺序表各结点概率相等的情况下,顺序按值查找某个元素的算法时间复杂度为()

A.O(1)

B.O(n)

C.O(√n)

D.O(log2n)

24.下列各项键值序列中不是堆的为()

A.{5,23,16,68,94,72,71,73}

B.{5,16,23,68,94,72,71,73}

C.{5,23,16,73,94,72,71,68}

D.{5,23,16,68,73,71,72,94}

25.在线性表的下列存储结构中进行插入、删除运算,花费时间最多的是()

A.单链表

B.双链表

C.顺序表

D.单循环链表

26.在栈中进行插入和删除操作的一端称为()

A.栈顶

B.栈底

C.任意位置

D.指定位置

27.用n个值构造一棵二叉排序树,它的最大高度为

A..n/2

B.n

C.√n

D.log2n

28.冒泡排序的时间复杂度是()

A.O(n2)

B.O(nlog2n)

C.O(n)

D.O(log2n)

29.设无向图的邻接表如题14图所示,则该图的边数为()

A.4

B.5

C.10

D.20

30.带表头结点链队列的队头和队尾指针分别为front和rear,则判断队空的条件为()

A.front==rear

B.front!=NULL

C.rear!=NULL

D.front==NULL

二、填空题(共13题,共26分)

31.下列程序段的时间复杂度为________

32.数据的逻辑结构被分为集合结构、________、树形结构和图状结构4种。

33.线性表中所含结点的个数称为________。

34.向一个栈顶指针为top的链栈中插入一个新结点*p时,应执行_____和top=p操作。

35.设一个顺序栈S,元素s1,s2,s3,s4,s5,s6依次进栈,如果6个元素的退栈顺序为s2,s3,s4,s6,s5,s1,则顺序栈的容量至少为_______。

36.若满二叉树的结点数为n,则其高度为______。

37.在一棵具有n个结点的完全二叉树中,从树根起,自上而下、从左到右地给所有结点编号。若编号为i的结点有父结点,那么其父结点的编号为________。

38.深度为k的二叉树,结点数最多有_______个。

39.某二叉树的后根遍历为ABKCBPM,则该二叉树的根为_____

温馨提示

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

评论

0/150

提交评论