聊城大学东昌学院《数据结构》2021-2022学年期末模拟试卷.docxVIP

聊城大学东昌学院《数据结构》2021-2022学年期末模拟试卷

学校：__________姓名：__________班级：__________考号：__________

一、单项选择题

1．要将现实生活中的数据转化为计算机所能表示的形式，其转化过程依次为（）

A.逻辑结构、存储结构、机外表示 B.存储结构、逻辑结构、机外表示

C.机外表示、逻辑结构、存储结构 D.机外表示、存储结构、逻辑结构

2．若检索顺序文件各个记录的概率相同，设文件占用的页块数为n，则按关键字存取时的平均访问外存次数为（）

A．n/2 B．n

C．n/4 D．logn

3．从V1出发，对按广度优先有哪些信誉好的足球投注网站遍历，则可能得到的一种顶点序列为()

A.V1V2V3V5V4V6

B.V1V2V3V5V6V4

C.V1V5V2V3V6V4

D.V1V3V6V4V5V2

4．深度为k的二叉树至多有()

A.2k个结点B.2k-1个结点

C.2k-1个结点D.2k-1-1个结点

5．关于VSAM文件存取操作的说法，正确的是()

A.不能顺序存取，只能按关键字随机存取 B.不能顺序存取，不能按关键字随机存取

C.只能顺序存取，不能按关键字随机存取 D.既能顺序存取，也能按关键字随机存取

6．若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不超过()

A. B.n

C. D.n+1

7．m个叶结点的哈夫曼树中，其结点总数为

A.m B.2m+1

C.2m D.2m-1

8．在已知尾指针的单循环链表中，插入一个新结点使之成为首结点，其算法的时间复杂度为（）

A.O（1） B.O（log2n）

C.O（n） D.O(n2)

9．若线性表最常用的操作是存取第i个元素及其前趋的值，那么最节省操作时间的存储方式是()

A.单链表 B.双链表

C.单循环链表 D.顺序表

10．关于串的的叙述，不正确的是()

A.串是字符的有限序列

B.空串是由空格构成的串

C.替换是串的一种重要运算

D.串既可以采用顺序存储，也可以采用链式存储

11．稀疏矩阵是指()

A.元素少的矩阵 B.有少量零元素的矩阵

C.有少量非零元素的矩阵 D.行数、列数很少的矩阵

12．与串的逻辑结构不同的数据结构是()

A.线性表 B.栈

C.队列 D.树

13．关于串的叙述，正确的是()

A.串是含有一个或多个字符的有穷序列

B.空串是只含有空格字符的串

C.空串是含有零个字符或含有空格字符的串

D.串是含有零个或多个字符的有穷序列

14．在表长为100的顺序表中做插入运算，平均移动元素的次数为

A．25 B.33

C.50 D.100

15．关于栈和队列的说法中正确的是（）

A．栈和队列都是线性结构

B.栈是线性结构，队列不是线性结构

C.栈不是线性结构，队列是线性结构

D.栈和队列都不是线性结构

16．下述算法中，不稳定的排序算法是

A.直接插入排序 B.冒泡排序

C.堆排序 D.归并排序

17．对文件进行检索操作时，每次都要从第一个记录开始的文件是（）

A．顺序文件 B．索引文件

C．顺序索引文件 D．散列文件

18．顺序查找法与二分查找法对存储结构的要求是()

A.顺序查找与二分查找均只适用于顺序表

B.顺序查找与二分查找既适用于顺序表，也适用于链表

C.顺序查找只适用于顺序表

D.二分查找只适用于顺序表

19．将一棵有50个结点的完全二叉树按层编号，则对编号为25的结点x，该结点（）

A.无左、右孩子

B.有左孩子，无右孩子

C.有右孩子，无左孩子

D.有左、右孩子

20．循环队列用数组A［0..m-1］存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是()。

A.(rear-front+m)MODm

B.rear-front+1

C.rear-front-1

D.rear-front

二、填空题

21．从数据结构的观点，数据通常可分为三个层次，即：数据、数据元素和___________。

22．多关键字文件是指同时对__________两部分都建立索引的文件组织形式。

23．图主要采用___________两种存储结构存放。

24．三个结点可构成________种不同形态的二叉树。

25．对长度为n的顺序表执行删除操作，其删除算法在最坏情况下的时间复杂性为____