数据结构复习题(一).pdfVIP

《数据结构》复习题（一）

一、判断题（下列各题，你认为正确的，请在前面的括号内打√，错误的打×。

每题1分，共10分）

（）1.数据的存贮结构是数据的逻辑结构的存贮映象。

（）2.用顺序表来存储线性表时，不需要另外开辟空间来保存数据元素之间的相

互关系。

（）3.非线性结构中，至少存在一个元素不止一个直接前趋或不止一个直接后继。

（）4.树的最大特点是层次结构。

（）5.队列的特点是先进先出。

（）6.图的最小生成树是唯一的。

（）7.线性表是广义表的特殊形式。

（）8.后序序列和中序序列能唯一确定一棵二叉树。

（）9.散列表是一种链式存贮结构。

（）10.快速排序并非在任何情况下都比其它排序方法速度快。

二、填空题（每空2分，共20分）

1．数据的存贮结构的四种形式为存贮、存贮、存贮和存贮。

2．所有插入和删除都在表的一端进行的线性表称为。

3．n个结点的完全二叉树，其深度h=。

4．对于顺序循环队列Q[M]，下标从0到M-1，头尾指针分别为F和R，入队时，

队尾指针循环加1可表示为R=。

5．散列法既是一种查找方法，又是一种方法。

6．n个顶点的有向完全图具有条弧。

7．n个元素的顺序查找的平均查找长度为。

三、单选题（本题的每一备选答案中，只有一个是正确的，请把你认为正确的答

案的题号填入题干的括号内，多选不给分，每小题3分，共15分）。

1．若进栈序列为1，2，3，4，则不可能得到的出栈序列是（）

（1）3,2,1,4（2）3,2,4,1（3）4,2,3,1（4）2,3,4,1

2．对于下列二叉树，其后序序列为（）

（1）ABDECFG（2）DBEAFCG（3）DEBFGCA（4）GFCEBDA

3．对于下列AOV网，不能出现的拓扑序列为（）

（1）12345（2）12435（3）24135（4）21435

1/18

A13

BC5

24

DEFG

题三2图题三、3图

4．深度为k的完全二叉树所含叶结点的个数最多为（）

（1）2k（2）2k-1（3）k（4）2k

5．衡量查找算法效率的主要标准是（）

（1）元素个数（2）所需的存贮量

（3）平均查找长度（4）算法难易程度

四、应用题（25分）

1．将下列森林转化为二叉树。（3分）

AF

BCDG

E

2．对下图：

（1）写出其邻接矩阵。（2分）

（2）按Kruskal算法求其最小生成树；并写出相应的边集数组。（4分）

128

VV