2020年02142数据结构导论模拟试题（6）

自考生网为考生收集整理了“2020年02142数据结构导论模拟试题（6）”。

注：不同省份、不同专业的自考本科模拟试题，只要课程代码和课程名称相同，都可参考使用。

更多自考02142数据结构导论模拟试题可查看“自考02142数据结构导论模拟试题”栏目。

点击查看：02142数据结构导论模拟试题答案

一、选择题

1．关于算法的描述，不正确的是（）

A.算法最终必须由计算机程序实现

B.所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界

C.健壮的算法不会因非法的输入数据而出现莫名其妙的状态

D.算法的优劣与算法描述语言无关

2．若用一个有6个单元的数组来实现循环队列，rear和front的初值分别为0和3。则从队列中删除一个元素，再添加两个元素后，rear和front的值分别为（）

A.1和5 B.2和4

C.4和2 D.5和1

3．数据的四种基本逻辑结构是指（）。

A．数组、链表、树、图形结构B．线性表、链表、栈队列、数组广义表

C．线性结构、链表、树、图形结构D．集合、线性结构、树、图形结构

4．数据结构中，通常采用两种方法衡量算法的时间复杂性，即（）。

A．最大时间复杂性和最小时间复杂性

B．最好时间复杂性和最坏时间复杂性

C．部分时间复杂性和总体时间复杂性

D．平均时间复杂性和最坏时间复杂性

5．下列关于线性表的叙述中，不正确的是（）。

A．线性表是n个结点的有穷序列

B．线性表可以为空表

C．线性表的每一个结点有且仅有一个前趋和一个后继

D．线性表结点间的逻辑关系是1:1的联系

6．在一个单链表中，若p所指结点不是最后结点，则删除p所指结点的后继结点的正确操作是（）。

A．p=p->next B．p->next=p->next

C．p->next=p->next->next D．p->next=p

7．栈和队列（）。

A．共同之处在于二者都是先进先出的特殊的线性表

B．共同之处在于二者都是先进后出的特殊的线性表

C．共同之处在于二者都只允许在顶端执行删除操作

D．没有共同之处

8．一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，查找成功时的比较次数为（）

A.1 B.2

C.4 D.8

9．向一个栈顶指针为hs的链栈中插入一个*s结点时，应执行的操作为（）

A.hs—>next=s；B.s—>next=hs；hs=s；

C.s—>next=hs—>next；hs—>next=s；D.s—>next=hs；hs=hs—>next；

10．已知8个元素（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为（）

A.4 B.5

C.6 D.7

11．二维数组A[5][6]采用按列为主序的存储方式，每个元素占3个存储单元，若A[0][0]的存储地址是100，则A[4][3]的存储地址是（）。

A．127 B．142

C．150 D．157

12．深度为k的二叉树至多有（）。

A．2k个结点B．2k-1个结点C．2k-1个结点D．2k-1-1个结点

13．对于如下图所示二叉树采用中根遍历，正确的遍历序列应为（）。

题8图

A．ABCDEF B．ABECDF

C．CDFBEA D．CBDAEF

14．下面关于生成树的描述中，不正确的是（）。

A．生成树是树的一种表现形式

B．生成树一定是连通的

C．生成树一定不含有环

D．若生成树顶点个数为n，则其边数一定为n-1

15．图的邻接表如图所示，从顶点V1出发采用深度优先搜索法遍历该图，则可能的顶点序列是（）。

题10图

A．V1V2V3V4V5 B．V1V2V3V5V4

C．V1V4V3V5V2 D．V1V3V4V5V2

16．用于外存储器的数据组织结构散列文件，主要适用于（）。

A．顺序存取B．随机存取

C．索引存取D．以上三种都可以

17．堆排序属于一种选择排序，其时间复杂性为（）。

A．O（1）B．O（nlog2n）C．O（n）D．O（n2）

18．下列排序方法中，属于不稳定的排序方法是（）。

A．直接选择排序法B．冒泡排序法

C．基数排序法D．归并排序法

19．下列查找方法中，不属于动态的查找方法是（）。

A．二叉排序树法B．平衡树法

C．散列法D．斐波那契查找法

20．要解决散列引起的冲突问题，常采用的方法有（）。

A．数字分析法、平方取中法

B．数字分析法、线性探测法

C．二次探测法、平方取中法

D．二次探测法、链地址法

二、填空题

1．在一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较__(n+1)/2__个元素结点。

2.具有n个叶子结点的哈夫曼树，其结点总数为____2n-1____。

3．栈的插入与删除操作在____栈顶____进行。

4．一棵二叉树的广义表表示为a(b(c,d),e(f(,g)))，则e结点的双亲结点为___a___，左孩子结点为____f____，右孩子结点为____空结点____。

5．在一个具有n个顶点的无向完全图中，包含有____ n(n-1)/2____条边，在一个具有n个顶点的有向完全图中，包含有____ n(n-1)____条边。

6．表示图的三种存储结构为____邻接矩阵____、____邻接表____和____边集数组____。

7．对n个元素进行冒泡排序时，最少的比较次数为____n-1____。

8．在插入排序、冒泡排序、快速排序、归并排序等排序算法中，占用辅助空间最多的是___归并排序______。

9．以二分查找方法查找一个线性表时，此线性表必须是___顺序___存储的___有序____表。

10．每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做____快速____排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫做____归并____排序。

11．在双链表中，存储一个结点有三个域，一个是数据域，另两个是指针域，分别指向____直接前趋_____和_____直接后继____。

12．快速排序在平均情况下的空间复杂度为____ O(log2n)____，在最坏情况下的空间复杂度为____ O(n)____。

以上“2020年02142数据结构导论模拟试题（6）”内容由自考生网收集整理，以供参考。