数据结构期末考试试题及答案.docVIP

数据结构期末考试试题及答案

一、单项选择题（每题2分，共10题）

1.线性表采用顺序存储结构，访问第i个元素的时间复杂度为（）

A.O(1)B.O(n)C.O(logn)D.O(n^2)

2.栈的操作特性是（）

A.先进先出B.先进后出C.随机进出D.以上都不对

3.队列的“先进先出”特性是指（）

A.最早插入队列中的元素总是最后被删除

B.当同时进行插入、删除操作时，总是插入操作优先

C.每当有删除操作时，总是要先做一次插入操作

D.先插入的元素总是先被删除

4.具有n个结点的完全二叉树的深度为（）

A.?log?n?+1B.log?nC.?log?n?+1D.?log?n?

5.对一组数据(84,47,25,15,21)排序，数据的排列次序在排序的过程中的变化为：

(1)8447251521(2)1547258421(3)1521258447(4)1521254784

则采用的排序方法是（）

A.选择排序B.冒泡排序C.插入排序D.快速排序

6.在一个图中，所有顶点的度数之和等于所有边数的（）倍。

A.1B.2C.3D.4

7.散列表的平均查找长度（）

A.与处理冲突方法有关而与表的长度无关

B.与处理冲突方法无关而与表的长度有关

C.与处理冲突方法和表的长度都有关

D.与处理冲突方法和表的长度都无关

8.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）

A.必须是连续的B.部分地址必须是连续的

C.一定是不连续的D.连续或不连续都可以

9.已知广义表LS=((a,b,c),(d,e,f))，运用head和tail函数取出LS中原子e的运算是（）

A.head(tail(head(tail(LS))))B.head(head(tail(LS)))

C.tail(head(head(tail(LS))))D.head(tail(head(LS)))

10.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为（）

A.O(1)B.O(n)C.O(logn)D.O(n^2)

二、多项选择题（每题2分，共10题）

1.以下属于线性数据结构的有（）

A.线性表B.栈C.队列D.树

2.顺序存储结构的优点有（）

A.存储密度大B.插入操作方便

C.访问速度快D.删除操作方便

3.栈的应用场景包括（）

A.表达式求值B.递归调用C.深度优先有哪些信誉好的足球投注网站D.广度优先有哪些信誉好的足球投注网站

4.队列可用于（）

A.打印任务排队B.操作系统中的进程调度

C.广度优先有哪些信誉好的足球投注网站D.深度优先有哪些信誉好的足球投注网站

5.以下关于二叉树的说法正确的有（）

A.二叉树的每个结点最多有两个子树

B.满二叉树是完全二叉树

C.完全二叉树的叶子结点只可能在层次最大的两层上出现

D.二叉树的遍历方式有前序、中序、后序和层次遍历

6.图的存储结构有（）

A.邻接矩阵B.邻接表C.十字链表D.邻接多重表

7.以下排序算法中，时间复杂度为O(n^2)的有（）

A.冒泡排序B.选择排序C.插入排序D.快速排序

8.哈希函数的构造方法有（）

A.直接定址法B.除留余数法C.平方取中法D.折叠法

9.以下属于非线性数据结构的有（）

A.图B.树C.广义表D.栈

10.对线性表进行插入和删除操作时，在（）存储结构下效率较高。

A.顺序存储B.链式存储C.散列存储D.索引存储

三、判断题（每题2分，共10题）

1.线性表的顺序存储结构比链式存储结构更节省存储空间。（）

2.栈和队列都是特殊的线性表。（）

3.完全二叉树一定是满二叉树。（）

4.图的深度优先有哪些信誉好的足球投注网站和广度优先有哪些信誉好的足球投注网站都需要借助队列来实现。（）

5.快速排序在任何情况下的时间复杂度都是O(nlogn)。（）

6.散列表中冲突是不可避免的。（）

7.树中结点的度之和等于树的边数。（）

8.插入排序在数据基本有序时效率较高。（）

9.广义表的表头可以是原子也可以是子表。（）

10.线性表采用链式存储时，访问第i个元素的时间复杂度为O(1)。（）

四、简答题（每题