智慧树知到《算法与数据结构》章节测试答案文档格式.docx
《智慧树知到《算法与数据结构》章节测试答案文档格式.docx》由会员分享，可在线阅读，更多相关《智慧树知到《算法与数据结构》章节测试答案文档格式.docx（23页珍藏版）》请在冰点文库上搜索。
8、描述非数值计算问题的数学模型不再是数学方程，而是数据结构（）。
表
树
图
集合
表,树,图,集合
9、数据结构是一门研究（）程序设计问题中计算机的（）以及它们之间的（）和（）等的学科。
非数值计算
操作对象
操作
非数值计算,操作对象,关系,操作
10、顺序存储结构:
借助元素在存储器中的（）来表示数据元素间的逻辑关系。
地址
相对位置
数值
第一章
1、（）是一种最简单的线性结构。
线性表
2、（）线性表的数据元素可以由所描述对象的各种特征的数据项组成。
有序存储
散列存储
链式存储
顺序存储
3、已知单向链表中指针p指向结点A，（）表示删除A的后继结点（若存在）的链操作（不考虑回收）。
p->
next=p
p=p->
next
next->
next=p->
4、已知last指向单向简单链表的尾结点，将s所指结点加在表尾，不正确的操作是。
s->
next=NULL,last->
next=s,last=s;
next=s,s=last;
last->
next=s,s->
next=NULL,last=s;
next=s,last=s,last->
next=NULL;
5、已知h是指向单向加头链表的首指针，删除表头结点的操作是_。
p=h->
next;
free（p）;
h=h->
free（h->
next）;
p=h,h=p->
next,h->
6、有N个元素组成的线性表，我们说此线性表的长度为（）
n
n+1
n-1
7、对线性表中的数据元素进行（）和（）等操作，实现表的长度的增长或缩短。
插入
遍历
访问
删除
插入,删除
8、线性表的抽象数据类型定义
数据对象
函数关系
数据关系
基本操作
数据对象,数据关系,基本操作
9、我们使用（），实现线性表的顺序存储。
函数
数组
10、线性表的基本操作是用C语言中的（）对其进行表示的。
循环语句
结构体
条件语句
11、在链表中第i个结点之前插入新的元素e，表的逻辑结构不变。
12、在单链表中插入结点只需要（）。
但同时，若要在第（）个结点之前插入元素，修改的是第（）个结点的指针。
i
修改指针
i+1
i-1
i,修改指针,i-1
13、单链表和线性表中所有基本操作相同，且编程实现方法相同。
14、数字钟程序中使用的时间，可以是系统时间。
15、和单链表的差别仅在于，判别链表中最后一个结点的条件不再是（），而是（）。
"
后继是否为头结点"
前继是否为头结点"
前继是否为空"
后继是否为空"
"
16、双向链表的"
删除"
时需要同时修改两个方向上的指针,改变结点之间的逻辑关系。
17、双向链表的"
插入"
时不需要同时修改两个方向上的指针,改变结点之间的逻辑关系。
18、双向链表中，当指针p指向非空表中的非头尾结点时，以下哪个式子是正确的（）
prior=p
next=p->
prior
prior->
prior=p,p=p->
19、双向链表中，当指针p指向非空表中的非头尾结点时，以下哪个式子是正确的（）
next=p->
prior=p->
20、双向链表需要在结点中设两个指针域（）
parent指针域
prior指针域
数据域
next指针域
prior指针域,next指针域
第二章
1、队列是一种（）的线性表。
先进先出
先进后出
只能插入
只能删除
2、设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（）。
front->
next=s；
front=s；
s->
next=rear；
rear=s；
rear->
next=front；
rear->
3、栈操作数据的原则是（）。
后进先出
后进后出
不分顺序
4、栈与队列是一种特殊操作的线性表（）
5、和链栈类似，用单链表来实现链队。
根据队的先入先出（FIFO）原则，为了操作上的方便，使用一个（）和（）。
头指针
尾指针
指针域
头指针,尾指针
6、队列的顺序存储结构用C语言中（）数据类型实现。
一维数组实现
二维数组实现
枚举型
7、栈和队列不能进行再分配了。
8、队列允许在表的一端进行插入操作和删除操作。
9、入栈需要修改地址指针。
10、链栈主要的运算，如插入、删除是在栈顶执行的。
链表的头部作栈顶是最方便的，需要像单链表那样为了运算方便附加一个头结点。
11、链栈的结点结构与单链表的结点结构相同，由（）和（）组成。
指针域双亲域
数据域指针域
孩子域指针域
双亲域
12、构造一个空栈S时，不需要用动态存储空间分配函数。
13、顺序栈中数据元素与栈顶指针的变化：
非空栈中的栈顶指针top始终在的（）下一个位置
栈中任意元素
栈顶元素
栈底元素
栈中元素
14、在初始化空顺序栈时一般不限定栈的最大容量，因为，栈在使用过程中所需最大空间的大小很难估计。
15、利用（）的存储单元依次存放自栈底到栈顶的数据元素，这种形式的栈称为顺序栈。
一组地址相同
一组地址不连续
一组地址连续
一组地址断开
第三章
1、串（即字符串）是一种特殊的线性表，它的数据元素是（）。
数字
单个字符
B
2、包含零个字符（n=0）的串称为空串，通常记为Ф，其长度为零；
空串是任意串的子串。
A
3、空串与空格串相同
4、串比较是按字符的ASCII值比较的，而不是按串的长度比较的。
StrCompare（'
data'
'
structures'
）____0；
大于
等于
小于
小于等于
C
5、SubString（sub,'
commander'
1,9）求得sub='
___'
；
commanr
coander
commander
comander
C
6、串的基本操作中，操作对象大多为"
串的整体"
。
7、在串的表示和实现过程中，用一组地址不连续的存储单元存储串值中的字符序列，称为串的定长顺序存储方式。
8、在顺序串中，用一个指针来指向最后一个字符，C语言的表示如下：
typedefstruct{chardata[MAXSIZE];
intcurlen;
}SeqString;
请定义一个串变量：
structgs
typedefstructs；
SqStrings；
SeqStrings；
D
9、在C语言中，存在一个称为"
堆"
的自由存储区，并由C语言的动态分配函数____来管理。
malloc（）
malloc（）和free（）
free（）
main（）
10、堆分配存储结构的串有顺序存储结构的特点，在操作中对串长又没有任何限制，因而在串处理的应用程序中常被选用。
第四章
1、设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（）。
2i+1
2i
i/2
2i-1
2、设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（）。
空或只有一个结点
高度等于其结点数
任一结点无左孩子
任一结点无右孩子
3、二叉树的第k层的结点数最多为（）
2的k次幂-1
2K+1
2K-1
2的k-1次幂
4、设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。
BADC
BCDA
CDAB
CBDA
5、满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。
（）
6、设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。
7、深度为k的完全二叉树中最少有（）个结点。
2k-1-1
2k-1+1
2k-1
8、设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（）。
N0=N1+1
N0=Nl+N2
N0=N2+1
N0=2N1+l
9、设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（）。
任一结点无左孩子
10、树的带权路径长度定义为，树中所有叶子结点的带权路径长度之和（对所有叶子结点）。
（）
第五章
1、设某无向图有n个顶点，则该无向图的邻接表中有（）个表头结点。
2n
n/2
n（n-1）
2、设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（）。
第i行非0或非∞元素的个数之和
第i列非0或非∞元素的个数之和
第i行0元素的个数之和
第i列0元素的个数之和
3、设某完全无向图中有n个顶点，则该完全无向图中有（）条边
n（n-1）/2
n（n-1）
n的2次幂
n的2次幂-1
4、子串"
ABC"
在主串"
AABCABCD"
中的位置为2。
5、对链表进行插入和删除操作时不必移动链表中结点。
6、深度为k的完全二叉树中最少有（）个结点。
2k-1-1
7、设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（）。
8、设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（）。
第i列0元素的个数之和
9、简单回路就是回路。
10、图中任两点有路径相通，该图称为连通图（）
第六章
1、时间复杂度不受数据初始状态影响而恒为O（nlog2n）的是（）。
堆排序
冒泡排序
希尔排序
快速排序
2、设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（）。
20
30
40
45
3、设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（）
4、连通图的最小生成树的边上的权值之和是唯一的。
5、设某无向图有n个顶点，则该无向图的邻接表中有（）个表头结点。
6、设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（）。
7、以数据集{1，3，5，7}为叶结点的权值，构造一棵哈夫曼树，求出带权路径长度WPL（）。
26
28
29
8、设某完全无向图中有n个顶点，则该完全无向图中有（）条边
9、查找表可分为两类（）
动态查找表
顺序查找表
静态查找表
起泡查找表
AC
10、使用折半方法进行查找的表是一个有序表。
第七章
1、执行一趟快速排序能够得到的序列是（）。
[41，12，34，45，27]55[72，63]
[45，34，12，41]55[72，63，27]
[63，12，34，45，27]55[41，72]
[12，27，45，41]55[34，63，72]
2、排序分稳定排序和不稳定排序。
4、冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。
5、设一组初始记录关键字序列为（45，80，55，40，42，85），则以第一个记录关键字45为基准而得到一趟快速排序的结果是（）。
40，42，45，55，80，83
42，40，45，80，85，88
42，40，45，55，80，85
42，40，45，85，55，80
6、设一组初始记录关键字序列为（25，50，15，35，80，85，20，40，36，70），其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（）。
15，25，35，50，20，40，80，85，36，70
15，25，35，50，80，20，85，40，70，36
15，25，35，50，80，85，20，36，40，70
15，25，35，50，80，20，36，40，70，85
7、设一组初始记录关键字序列为（50，40，95，20，15，70，60，45），则以增量d=4的一趟希尔排序结束后前4条记录关键字为（）。
40，50，20，95
15，40，60，20
15，20，40，45
45，40，15，20
8、执行一趟快速排序能够得到的序列是（）。
[41，12，34，45，27]55[72，63]
[63，12，34，45，27]55[41，72]
9、队列的顺序存储结构用C语言中（）数据类型实现。
10、时间复杂度不受数据初始状态影响而恒为O（nlog2n）的是（）。
升级会员 