数据结构与算法分析-复习题.doc

第PAGE2页/共NUMPAGES2页

系计算机科学与工程学院班级2007学号（9位）姓名

———————————阅————卷————密————封————装————订————线——————————

第PAGE1页/共NUMPAGES2页

《数据结构与算法分析》2012～2013学年第二学期

复习题

一、选择题

1．算法分析的目的是（）：

A.找出数据结构的合理性B.研究算法中的输入和输出的关系

C.分析算法的效率以求改进D.分析算法的易懂性和文档性

2.在数据结构中，逻辑上数据结构可分为________。

A．动态结构和静态结构 B．线性结构和非线性结构

C．紧凑结构和非紧凑结构 D．内部结构和外部结构

3．若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点（）。

A.正确 B.不正确

4．在一个单链表中，若删除p所指结点的后续结点，则执行：

A.p-next=p-next-nextB.p-next=p-nextC.p=p-next-nextD.p=p-next

5．从表中任一结点出发，都能扫描整个表的是（）。

A.单链表 B.顺序表 C.循环链表 D.静态链表

6．在一棵具有5层的满二叉树中结点总数为（）。

A.31 B.32 C.33 D.16

7．如果从无向图的任一顶点出发进行一次深度优先有哪些信誉好的足球投注网站即可访问所有顶点，则该图一定是（）。

A.完全图 B.连通图 C.有回路 D.一棵树

8．无向图的邻接矩阵是一个（）。

A.对称矩阵 B.零矩阵 C.上三角矩阵 D.对角矩阵

9．下列排序方法中（）方法是不稳定的。

A.冒泡排序 B.选择排序C.堆排序 D.直接插入排序

10．判断一个循环队列Q（最多n个元素）为满的条件是（）。

A.Q-rear==Q-front B.Q-rear==Q-front+1

C.Q-front=(Q-rear+1)%n D.Q-front==(Q-rear-1)%n

二、填空题

1、对稀疏矩阵进行压缩存储，常用的两种方法：①和②。

2、若对二叉排序树进行遍历，保证输出的所有结点序列按键值递增排序，对二叉排序树应进行③遍历。

3、队列的特点是④，栈的特点是⑤。

4、树内各结点度的⑥称为树的度。

5、一个图的⑦表示法是惟一的。

6、在散列函数H(key)=key％p中，p应取⑧。

7、具有相同函数值的关键字对哈希函数来说称为⑨。

8、数据结构的四种基本类型中，⑩的元素是一对多关系。

三、判断题

1．采用压缩存储之后，下三角矩阵的存储空间可以节约将近一半。（）

2．广义表的元素可以是子表，也可以是单元素。（）

3．树的后序遍历与其对应的二叉树的后序遍历序列相同。 （）

4．在具有头结点的单链表中，头指针指向链表的第一个数据结点。（）

5．链式存储的线性表可以随机存取。（）

6．以链表作为栈的存储结构，出栈操作必须判别栈空的情况。（）

7．图的深度优先有哪些信誉好的足球投注网站序列和广度优先有哪些信誉好的足球投注网站序列不是惟一的。（）

8．二叉树的先序遍历中，任意结点均处在其子女结点之前。（）

9．快速排序在所有排序方法中最快，而且所需附加空间也最少。（）

四、分析题

1、设ｎ为正整数，试确定如下