数据结构考试题及答案.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.一棵完全二叉树共有360个结点，则在该二叉树中度为1的结点个数为（）

A.0B.1C.180D.181

5.对长度为n的线性表排序，在最坏情况下，比较次数不是n(n-1)/2的排序方法是（）

A.冒泡排序B.直接插入排序C.快速排序D.堆排序

6.哈希表的平均查找长度与（）有关。

A.哈希函数B.装填因子C.处理冲突的方法D.以上都有关

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

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

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

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

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

8.树最适合用来表示（）

A.有序数据元素B.无序数据元素

C.元素之间具有分支层次关系的数据D.元素之间无联系的数据

9.若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用（）存储方式最节省时间。

A.单链表B.双链表C.带头结点的双循环链表D.单循环链表

10.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（）

A.12345ABCDEB.EDCBA54321C.ABCDE12345D.54321EDCBA

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

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

A.栈B.队列C.二叉树D.链表

2.排序算法中，时间复杂度为O(n^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.以下关于图的说法正确的是（）

A.无向图中边是没有方向的

B.有向图中边是有方向的

C.图的存储结构有邻接矩阵和邻接表

D.图的遍历有深度优先遍历和广度优先遍历

8.对于顺序存储的线性表，在等概率情况下，插入和删除操作平均需要移动的元素个数与（）有关。

A.表长B.插入或删除位置C.元素类型D.存储密度

9.以下哪些操作是栈支持的（）

A.Push（入栈）B.Pop（出栈）C.GetTop（取栈顶元素）D.IsEmpty（判断栈是否为空）

10.关于树和二叉树的关系，正确的是（）

A.树和二叉树是两种不同的数据结构

B.二叉树是树的特殊情况

C.树可以转化为二叉树

D.二叉树可以转化为树

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

1.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（）

2.栈和队列都是限制存取点的线性表。（）

3.二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树。（）

4.对任何一棵二叉树，若其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。（）

5.快速排序在最坏情况下的时间复杂度为O(nlogn)。（）

6.哈希表是一种基于关键字直接访问的数据结构。（）

7.队列的操作原则是先进后出。（）

8.链表的每个结点中都恰好包含一个指针。（）

9.树的后根遍历序列和对应的二叉树的中序遍历序列相同。（