【广开搜题】广东开放大学 数据结构期末考试押题试卷标准答案

广东开放大学 形成性考核 平时作业 参考答案 标准答案

关注【广开搜题】微信公众号 发送题目获取标准答案

单项选择题

1、为了实现图的深度优先搜索遍历，其非递归的算法中需要使用的一个辅助数据结构为（）（难度系数：易 ）（2 分）

A、图

B、表

C、树

D、栈

2、用邻接表表示图进行深度优先遍历时，通常借助（ ）来实现算法。（难度系数：易 ）（2 分）

A、栈

B、队列

C、树

D、图

3、由权值为（4,7,6,2）的叶子结点生成一棵哈夫曼树，其带权路径长度为（ ）。（难度系数：易 ）（2 分）

A、24

B、48

C、37

D、72

4、下面（　）算法适合构造一个稠密图G的最小生成树。（难度系数：易 ）（2 分）

A、Prim算法

B、Kruskal算法

C、Floyd算法

D、Dijkstra算法

5、若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（ ）图。（难度系数：易 ）（2 分）

A、非连通

B、连通

C、强连通

D、有向

6、一维数组A采用顺序存储结构，每个元素占用6个字节，第6个元素的存储地址为100，则该数组的首地址是（ ）。（难度系数：易 ）（2 分）

A、64

B、28

C、70

D、90

7、如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树称为（ ）。（难度系数：易 ）（2 分）

A、哈夫曼树

B、平衡二叉树

C、二叉树

D、完全二叉树

8、n个顶点的强连通图至少有（　　）条边。（难度系数：易 ）（2 分）

A、n

B、n+1

C、n-1

D、n×(n-1)

9、通常可以把某城市中各公交站点间的线路图抽象成（）状结构（难度系数：易 ）（2 分）

A、图

B、表

C、树

D、栈

10、具有n个顶点的无向图最多有（ ）条边。（难度系数：易 ）（2 分）

A、n/2

B、n(n-1)/2

C、n(n+1)

D、n2

11、设二叉树有n个结点，则其深度为（ ）。（难度系数：易 ）（2 分）

A、n-1

B、n

C、n+1

D、不能确定

12、在二叉树的链式存储结构中，通常每个结点中设置三个域，它们是值域、（ ）、右指针。（难度系数：易 ）（2 分）

A、左指针

B、左孩子

C、右孩子

D、双亲

13、若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1..(n(n+1))/2]中，则在B中确定aij（i（2 分）

A、i*(i-1)/2+j

B、j*(j-1)/2+i

C、i*(i+1)/2+j

D、j*(j+1)/2+i

14、图的BFS生成树的树高比DFS生成树的树高（ ）。（难度系数：易 ）（2 分）

A、小

B、相等

C、小或相等

D、大或相等

15、如果要求一个线性表既能较快的查找，又能适应动态变化的要求，最好采用( )查找法。（难度系数：易 ）（2 分）

A、顺序查找

B、折半查找

C、分块查找

D、哈希查找

16、在一个图中，所有顶点的度数之和等于图的边数的（ ）倍。（难度系数：易 ）（2 分）

A、1/2

B、1

C、2

D、4

17、广度优先遍历类似于二叉树的（ ）。（难度系数：易 ）（2 分）

A、先序遍历

B、中序遍历

C、后序遍历

D、层次遍历

18、若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为（ ）。（难度系数：易 ）（2 分）

A、X的双亲

B、X的右子树中最左的结点

C、X的左子树中最右结点

D、X的左子树中最右叶结点

19、在一棵度具有5层的满二叉树中结点总数为（ ）。（难度系数：易 ）（2 分）

A、31

B、32

C、33

D、16

20、具有n个顶点的有向图最多有（ ）条边。（难度系数：易 ）（2 分）

A、n

B、n(n-1)

C、n(n+1)

D、n的平方

21、对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为（ ）。（难度系数：易 ）（2 分）

A、n

B、n2

C、n-1

D、（n-1）2

22、将含有86个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为3的右孩子编号为（ ）（难度系数：易 ）（2 分）

A、7

B、8

C、9

D、6

23、设哈夫曼树中有199个结点，则该哈夫曼树中有（ ）个叶子结点。（难度系数：易 ）（2 分）

A、99

B、100

C、101

D、102

24、设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ ）个。（难度系数：易 ）（2 分）

A、n-1

B、n

C、n+1

D、n+2

25、利用n个值作为叶结点的权生成的哈夫曼树中共包含有( )个结点。（难度系数：易 ）（2 分）

A、n

B、n+1

C、2*n

D、2*n-1

26、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。（难度系数：易 ）（2 分）

A、1/2

B、1

C、2

D、4

27、如果结点A有3个兄弟，B是A的双亲，则结点B的度是（　 　）。（难度系数：易 ）（2 分）

A、唯一的

B、有多种

C、有多种，但根结点都没有左孩子

D、有多种，但根结点都没有右孩子

28、一个具有n个顶点的无向完全图包含（ ）条边。（难度系数：易 ）（2 分）

A、n（n-1）

B、n（n+1）

C、n（n-1）/2

D、n（n+1）/2

29、一个具有1025个结点的二叉树的高h为（ ）。（难度系数：易 ）（2 分）

A、11

B、10

C、11至1025之间

D、10至1024之间

30、将树中结点赋上一个有着某种意义的实数，称此实数为该结点的（ ）（难度系数：易 ）（2 分）

A、权

B、左

C、右·

D、无

多项选择题

31、线性表L=(a1，a2,……an)，下列说法错误的是（ ）。（难度系数：易 ）（2 分）

A、每个元素都有一个直接前驱和一个直接后继

B、线性表中至少有一个元素

C、表中诸元素的排列必须是由小到大或由大到小

D、除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。

32、线性表的顺序结构中，不正确的描述是（ ）。（难度系数：易 ）（2 分）

A、逻辑上相邻的元素在物理位置上不一定相邻

B、数据元素是不能随机访问的

C、逻辑上相邻的元素在物理位置上也相邻

D、进行数据元素的插入、删除效率较高

33、串下面关于串的的叙述中，（ ）是正确的。（难度系数：易 ）（2 分）

A、串是字符的有限序列

B、空串是由空格构成的串

C、模式匹配是串的一种重要运算

D、串既可以采用顺序存储，也可以采用链式存储

34、不是算法分析的目的是（ ）。（难度系数：易 ）（2 分）

A、找出数据结构的合理性

B、研究算法中的输入和输出的关系

C、分析算法的效率以求改进

D、分析算法的易懂性和文档性

35、以下说法不正确的是 ( )（难度系数：易 ）（2 分）

A、因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况

B、因顺序栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况

C、对于链栈而言,在栈满状态下,如果此时再作进栈运算，则会发生"上溢”

D、对于顺序栈而言在栈满状态下如果此时再作进栈运算，则会发生"下溢”。

判断题

36、线性表中的每个结点最多只有一个前驱和一个后继。（2 分）

正确

错误

37、广义表的深度是指广义表中元素的个数。（2 分）

正确

错误

38、使用三元组表存储稀疏矩阵的元素，有时并不能节省存储空间。（难度系数：易 ）（2 分）

正确

错误

39、若一个广义表的表头为空表，则此广义表亦为空表。（难度系数：易 ）（2 分）

正确

错误

40、最小生成树是指边数最少的生成树。（2 分）

正确

错误

41、线性表的链式存储表示优于顺序存储表示。（2 分）

正确

错误

42、在队列中，允许插入的一段称为对头。（难度系数：易 ）（2 分）

正确

错误

43、已知一棵二叉树的前序序列和中序序列可以唯一地构造出该二叉树（2 分）

正确

错误

44、树的先根遍历序列等同于该树对应的二叉树中序遍历序列。（2 分）

正确

错误

45、栈和队列都是操作受限制的线性表。（2 分）

正确

错误

46、哈夫曼树是带权值的树,且权值较大的结点离树较近。（2 分）

正确

错误

47、深度为h的非空二叉树的第i层最多有2h-1 个结点。（2 分）

正确

错误

48、二维数组是其数组元素为线性表的线性表。（2 分）

正确

错误

49、栈的特点是先进后出,队列的特点是先进先出。（2 分）

正确

错误

50、串中任意个字符组成的子序列称为该串的子串。（2 分）

正确

错误