数据结构考试试题及答案.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.队列的“先进先出”特性是指（）

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

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

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

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

5.二叉树第i层（i≥1）上最多有（）个结点。

A.2iB.2^iC.2i-1D.2^(i-1)

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

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

7.若某完全二叉树的深度为h，则该完全二叉树中至少有（）个结点。

A.2^(h-1)B.2^(h-1)-1C.2^h-1D.2^h

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

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

9.下列排序算法中，平均时间复杂度最小的是（）

A.冒泡排序B.选择排序C.插入排序D.归并排序

10.具有n个顶点的无向图最多有（）条边。

A.n(n-1)B.n(n-1)/2C.n^2D.n

多项选择题（每题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.访问时间复杂度为O(1)B.访问时间复杂度为O(n)

C.插入时间复杂度为O(1)D.插入时间复杂度为O(n)

7.哈希冲突的解决方法有（）

A.开放定址法B.链地址法C.再哈希法D.建立公共溢出区

8.以下属于树的基本操作的有（）

A.插入结点B.删除结点C.查找结点D.遍历

9.关于队列描述正确的是（）

A.先进先出B.可以用数组实现C.可以用链表实现D.有队头和队尾指针

10.以下哪些是数据结构中常用的算法设计技术（）

A.分治法B.动态规划法C.贪心法D.回溯法

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

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

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

3.二叉树中每个结点的度不能超过2，所以二叉树是一种特殊的树。（）

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

5.哈希表是一种直接根据关键字值进行访问的数据结构。（）

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

7.对于一个具有n个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小是n×n。（）

8.插入排序是稳定的排序算法。（）

9.队列的插入操作在队头进行，删除操作在队尾进行。（）

10.数据结构中，逻辑结构与存储结构是一一对应的。（）

简答题（每题5分，共4题）

1.简述栈和队列的区别。

答：栈是先进后出，操作在栈顶进行；队列是先进先出，插入在队尾，删除在队头进行。

2.简述二叉树的性质。

答：二叉树第i层最多有2^(i-1)个结点；深度为k的二叉树最多有2^k-1个结点；对任何二叉树，度为0的结点比度为2的结点多1个。

3.简述选择排序的基本思想。

答：在未排序序列中找到最小（大）元素，存放到排序序列的