vwqAAA数据结构练习题.pdf

单选、填空、判断为各章课后题。

下面列出项目四到项目八部分部分习题答案（说明：红色字为正确答案）

1.对于一个10阶对称矩阵，若按行序存储下三角（包括对角线）的元素，则矩阵第6行

3列的元素位置是一维数组中的第（18）个元素。

A.9

B.12

C.13

D.18

2.广义表（（a,b）,c,d）的表头是（c），表尾是（d）。

A.a

B.d

C.（a,b）

D.（c,d）

3.广义表（（a,（b，（）,c）,（（d），e）））的长度是（1）。

A.1

B.2

C.3

D.4

4.稀疏矩阵一般是指（D）。

A.非零元素和零元素都较少

B.非零元素较多

C.零元素较多

D.非零元素和零元素都较多

5.按照二叉树的定义，具有3个结点的二叉树有（5）中形态。

A.3

B.4

C.5

D.6

6.若一棵二叉树有n个结点，m个叶子及诶单，深度为h，则下面关系中正确的是（B）。

A.n=h+m

h

B.n=2-1

C.m=n/2

D.n=m+1

7.已知某二叉树的先序遍历序列为cedba，中序遍历序列为debac，则它的后序遍历序列

为（B）。

A.acbed

B.dabec

C.deabc

D.decab

8.有权值分别为3，8，6，5，2的叶子结点生成一棵哈夫曼树，则它的带权路径长度为（C）。

A.48

B.72

C.55

1/8

D.24

9.在一个具有n个顶点的无向图中，要连通全部顶点至少需要（B）条边。

A,n

B.n-1

C.n+1

D.2n

10.若具有n个顶点的无向图采用邻接矩阵存储方法，该邻接矩阵一定为一个（D）。

A.一般矩阵

B.稀疏矩阵

C.对角矩阵

D.对称矩阵

11.有向图的邻接表的第i个链表中的边界点数目是第i个顶点的（C）。

A.度数

B.入度

C.出度

D.边数

12.若无向图的任意一个顶点出发进行一次深度优先遍历便可以访问该图的所有顶点，则该

图一定是一个（B）图。

A.非连通

B.连通

C.强连通

D.子

13.在AOV网进行拓扑排序时，所有入度为0的顶点被链接称为一个（A）结点。

A.堆栈

B.队列

C.数组

D.线性表

14.已知某有向图G=（V，E），其中V={V0，V1，V2，V3，V4，V5}，E={V0，V1，

V0，V，V，V，V，V，V，V，V，V，V，V，V，

315202334414

V}，G的拓扑序列为（A）。

5

A.VVVVVV

203415

B.VVVVVV

230415

C.VVVVVV

023415

D.VVVVVV

032415

15.衡量查找算法性能好坏的主要标准是（D）。

A.参加比较的关键字值的多少

B.被查找的关键字值在关键字序列中的位置

C.关键字序列中是否存在被查找关键字的值

D.关键字的平均比较次数的多少

16.在一个具有15个数据元素的有序顺序表中，采用折半查找方法查找一个表中不存在的

记录，需要进行（B）次关键字的比较。

A.0

B.4

C.5

2/8

D.15

17.将数据元素{2，4，6，8，10，12，14，16，18，20}一次存放一个一维数组中，然后采

用折半查找元素12，被比较过的数据元素的下标依次为（C）。

A.10，16，12

B.10，12，16

C.4，7，5

D.4，5，7

填空题：

1.字符串是一个特殊的线性表，其特殊性体现在串中的元素为字符型数据

2.两个串相等的条件是两个串的长度相等，并且各个对应位置的字符都相等

3.从字符串的内部存储来看，常用的存储方法有定长顺序存储，堆存储和块链存储，