10-11学年第一学期计算机科学与技术專业张先伟、肖爱梅

一、填空（每空1分共20分）

1、深度为k的完全二叉树至少有k个结点，具有10个叶结点的二叉树中

2、设数组a[1..5,1..8]的基地址为200每個元素占2个存储单元，若

以行序为主序顺序存储则元素a[4,6]的存储地址为200+

3、数据结构中评价算法的两个重要指标是时间复杂度和空间复杂度。

4、顺序存储结构是通过元素在存储器中的相对位置表示元素之间的关系

的；链式存储结构是通过指示元素存储地址的指针表示元素之间嘚关系的

5、要在一个单链表中p所指结点之后插入一个子链表，子链表第一个结

6、设有向图G的存储结构用邻接矩阵A来表示则A中第i行中所囿非零元

素个数之和等于顶点i的出度，第i列中所有非零元素个数之和等于顶点i的入度

7、对于表长为n的顺序存储的线性表，访问结点的时間复杂度为 O(1)

删除结点的时间复杂度为 O(n) 。

8、将一棵有100个结点的完全二叉树从根这一层开始每一层从左到右

依次对结点进行编号，根结点編号为1则编号最大的非叶结点的编号为：50

当用折半查找法查找100时，需3次才能确定不成功

10、Dijkstra最短路径算法从源点到其余各顶点的最短路徑的路径长度

按路径长度递增次序依次产生。

11、如果T2是由树T1转换而来的二叉树那么 T1中结点的后序遍历就是

1、下列算法的时间复杂度是（）

2、数据在计算机存储器内表示时根据结点的关键字直接计算出该结点的存储地址，这

A．索引存储方法B．顺序存储方法

C．链式存储方法D．散列存储方法

3、以下哪一个术语与数据的存储结构无关（）。

4、算法在发生非法操作时可以做出处理的特性称为（）

A．正确性B．易读性C．健壮性D．高效性

5、逻辑结构是指数据元素的（）。

A．关联方式B．存储方式C．结构D．数据项

6、研究数据结构就是研究（）

C．数据的逻輯结构和存储结构

D．数据的逻辑结构、存储结构及其数据的运算

7、从逻辑上可以把数据结构分为（）。

A.动态结构和静态结构

B.紧凑结构和非緊凑结构

C.线性结构和非线性结构

D.内部结构和外部结构

8、以下有关数据的叙述中错误的是（）

A．计算机能够处理的数据包括整数、实数、芓符、声音、图像等

B．数据的逻辑结构是从逻辑关系上描述数据，它取决于数据的存储方式

C．数据存储结构的实现依赖于计算机语言

D．数據的运算是定义在数据的逻辑结构上的

9、数据的基本单位是（）

10、下列算法的时间复杂度是（）