南开18秋学期（1709、1803、1809）《数据结构》在线作业[答案]满分答案
18秋学期（1709、1803、1809）《数据结构》在线作业-0001
试卷总分:100 得分:0
一、 单选题 (共 30 道试题,共 60 分)
1.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。
A.1/2
B.1
C.2
D.4
2.设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有()个
A.n-1
B.n
C.n+1
D.n+2
3.
已知图的邻接矩阵，根据算法，则从顶点0出发，按广度优先遍历的结点序列是（）
A.0 2 4 3 1 6 5
B.0 1 3 5 6 4 2
C.0 1 2 3 4 6 5
D.0 1 2 3 4 5 6
4.
已知图的邻接矩阵，根据算法，则从顶点0出发，按广度优先遍历的结点序列是（）
A.0 2 4 3 6 5 1
B.0 1 3 6 4 2 5
C.0 4 2 3 1 5 6
D.0 1 3 4 2 5 6
5.设有两个串p和q，求q在p中首次出现的位置的运算称作（）
A.连接
B.模式匹配
C.求子串
D.求串长
6.用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法的
A.栈
B.队列
C.树
D.图
7.排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为()
A.希尔排序
B.冒泡排序
C.插入排序
D.选择排序
8.用邻接表表示图进行深度优先遍历时，通常是采用()来实现算法的
A.栈
B.队列
C.树
D.图
9.判定一个栈ST（最多元素为m0）为空的条件是（）
A.ST->top<>0
B.ST->top=0
C.ST->top<>m0
D.ST->top=m0
10.已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为()
A.CBEFDA
B.FEDCBA
C.CBEDFA
D.不定
11.链接存储的存储结构所占存储空间（）
A.分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
B.只有一部分，存放结点值
C.只有一部分，存储表示结点间关系的指针
D.分两部分，一部分存放结点值，另一部分存放结点所占单元数
12.在表长为ｎ的链表中进行线性查找，它的平均查找长度为（ ）
A.ＡＳＬ＝ｎ
B.ＡＳＬ＝（ｎ＋１）／２
C.
D.
13.
已知图的邻接矩阵，根据算法，则从顶点0出发，按深度优先遍历的结点序列是（ ）
A.0 2 4 3 1 5 6
B.0 1 3 5 6 4 2
C.0 4 2 3 1 6 5
D.0 1 3 4 2 5 6
14.将5个不同的数据进行排序，至多需要比较()次
A.8
B.9
C.10
D.25
15.链表是一种采用 存储结构存储的线性表
A.顺序
B.链式
C.星式
D.网状
16.判定一个队列QU（最多元素为m0）为满队列的条件是（）
A.QU->rear － QU->front = = m0
B.QU->rear － QU->front －1= = m0
C.QU->front = = QU->rear
D.QU->front = = QU->rear+1
17.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）
A.必须是连续的
B.部分地址必须是连续的
C.一定是不连续的
D.连续或不连续都可以
18.深度优先遍历类似于二叉树的()
A.先序遍历
B.中序遍历
C.后序遍历
D.层次遍历
19.具有n(n>0)个结点的完全二叉树的深度为（ ）
A.
B.
C.
D.
20.一棵具有 n个结点的完全二叉树的树高度（深度）是（ ）
A.
B.
C.
D.
21.线性表Ｌ在（）情况下适用于使用链式结构实现。
A.需经常修改Ｌ中的结点值
B.需不断对Ｌ进行删除插入
C.Ｌ中含有大量的结点
D.Ｌ中结点结构复杂
22.任何一个无向连通图的最小生成树()
A.只有一棵
B.一棵或多棵
C.一定有多棵
D.可能不存在
23.有8个结点的有向完全图有（）条边
A.14
B.28
C.56
D.112
24.二叉树是非线性数据结构，所以（）
A.它不能用顺序存储结构存储
B.它不能用链式存储结构存储
C.顺序存储结构和链式存储结构都能存储
D.顺序存储结构和链式存储结构都不能使用
25.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是()
A.110
B.108
C.100
D.120
26.
设a1、a2、a3为3个结点，整数P0，3，4代表地址，则如下的链式存储结构称为（）
A.循环链表
B.单链表
C.双向循环链表
D.双向链表
27.对22个记录的有序表作折半查找，当查找失败时，至少需要比较()次关键字。
A.3
B.4
C.5
D.6
