数据结构与算法智慧树知到答案章节测试2023年中国民用航空飞行学院

绪论单元测试本课程中需要掌握数据结构的基本概念、基本原理和基本方法。

A:对

B:错

答案:A在本课程的学习中还需要掌握算法基本的时间复杂度与空间复杂度的分析方法，能够设计出求解问题的高效算法。

A:错

B:对

答案:B第一章测试算法的时间复杂度取决于（）。

A:算法的长短

B:问题的规模

C:执行算法的计算机性能的高低

D:待处理数据的初态

答案:B算法的计算量的大小称为算法的（）。

A:效率

B:现实性

C:难度

D:复杂度

答案:D算法的时间复杂度与（）有关。

A:编译后执行程序的质量

B:问题规模

C:源程序的长度

D:计算机硬件的运行速度

答案:B以下关于数据结构的说法中正确的是（）。

A:数据结构的逻辑结构独立于其存储结构

B:数据结构的逻辑结构唯一地决定了该数据结构的存储结构

C:数据结构仅由其逻辑结构和存储结构决定

D:数据结构的存储结构独立于该数据结构的逻辑结构

答案:A数据结构研究的内容是（）。

A:数据的逻辑结构

B:数据的存储结构

C:包括以上三个方面

D:建立在相应逻辑结构和存储结构上的算法

答案:C第二章测试线性表是具有n个（）的有限序列。

A:字符

B:数据元素

C:表元素

D:数据项

答案:B单链表又称为线性链表，在单链表上实施插入和删除操作（）。

A:不需移动结点，不需改变结点指针

B:只需移动结点，不需改变结点指针

C:既需移动结点，又需改变结点指针

D:不需移动结点，只需改变结点指针

答案:D单链表中，增加一个头结点的目的是（）。

A:标识表结点中首结点的位置

B:方便运算的实现

C:使单链表至少有一个结点

D:说明单链表是线性表的链式存储

答案:B单链表中，要将指针q指向的新结点插入到指针p指向的单链表结点之后，下面的操作序列中（）是正确的。

A:p->next=q->next;q=p->next;

B:p->next=q;q->next=p->next;

C:q=p->next;p->next=q->next;

D:q->next=p->next;p->next=q;

答案:D链表不具有的特点是（）。

A:不必事先估计存储空间

B:可随机访问任一元素

C:插入、删除不需要移动元素

D:所需空间与线性表长度成正比

答案:B第三章测试循环队列存储在A[0..m]中，则入队时的操作是（）。

A:rear=(rear+1)%(m-1)

B:rear=(rear+1)%(m+1)

C:rear=(rear+1)%m

D:rear=rear+1

答案:B关于循环队列，以下（）的说法正确。

A:循环队列不会产生假溢出

B:循环队列不会产生上溢出

C:A、B、C都不对

D:循环队列不会产生溢出

答案:A如果循环队列用大小为m的数组表示，队头位置为front、队列元素个数为size，那么队尾元素位置rear为（）。

A:front+size-1

B:front+size

C:(front+size)%m

D:(front+size-1)%m

答案:D若顺序栈的栈顶指针指向栈顶元素位置，则压入新元素时，应（）。

A:先移动栈顶指针

B:先后次序无关紧要

C:先存入元素，再移动栈顶指针

D:同时进行

答案:A设栈S和队列Q的初始状态均为空，元素{1,2,3,4,5,6,7}依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是{2,5,6,4,7,3,1}，则栈S的容量至少是：

A:4

B:1

C:3

D:2

答案:A栈操作数据的原则是（）。

A:后进后出

B:后进先出

C:先进先出

D:不分顺序

答案:B设一个栈的输入序列为a，b，c，d，则借助一个栈所得到的输出序列不可能是（）。

A:a，b，c，d

B:d，a，b，c

C:a，c，d，b

D:d，c，b，a

答案:B设一个堆栈的入栈顺序是1、2、3、4、5。若第一个出栈的元素是4，则最后一个出栈的元素必定是（）。

A:1

B:5

C:1或者5

D:3

答案:C栈可用于（）。

A:递归调用

B:表达式求值

C:A、B、C都是

D:子程序调用

答案:C表达式a(b+c)-d的后缀表达式是（）。

A:abc+d-

B:abcd*+-

C:-+*abcd

D:abc+*d-

答案:D第四章测试若串S=“software”，则其子串数目是____，其中空串和S串本身这两个字符串也算作S的字串

A:36

B:9

C:8

D:37

答案:D串的长度是指____。

A:串中所含非空格字符的个数

B:串中所含不同字符的个数

C:串中所含字符的个数

D:串中所含不同字母的个数

答案:C下面关于串的叙述中，哪一个是不正确的____。

A:串既可以采用顺序存储，也可以采用链式存储

B:模式匹配是串的一种重要运算

C:空串是由空格构成的串

D:串是字符的有限序列

答案:C串是一种特殊的线性表，其特殊性体现在____。

A:数据元素是多个字符

B:数据元素是一个字符

C:可以顺序存储

D:可以链式存储

答案:B在用KMP算法进行模式匹配时，模式串“ababaaababaa”的next数组值为____。

A:-1，0，1，2，1，2，1，1，1，1，2，1

B:-1，0，1，2，3，0，1，2，3，2，2，3

C:-1，0，1，2，3，4，5，6，7，8，9，9

D:-1，0，0，1，2，3，1，1，2，3，4，5

答案:D第五章测试若一个问题既可以用迭代方式也可以用递归方式求解，则____的方法具有更髙的时空效率。

A:递归

B:先递归后迭代

C:先迭代后递归

D:迭代

答案:D一个递归算法必须包括____。

A:迭代部分

B:递归部分

C:终止条件和迭代部分

D:终止条件和递归部分

答案:D设有一个递归算法如下

intfact(intn){

//n大于等于0

if(n

A:n-1

B:n

C:n+1

D:n+2

答案:C任何一个递归过程都可以转换成非递归过程。

A:错

B:对

答案:B下列说法中，正确的是（）。

A:对同一输入序列进行两组不同的合法入栈和出栈组合操作，所得的输出序列也一定相同

B:队列和栈都是运算受限的线性表，只允许在表的两端进行运算

C:通常使用队列来处理函数或过程调用

D:消除递归不一定需要使用栈

答案:D第六章测试稀疏矩阵一般的压缩存储方法有____两种。

A:三元组和十字链表

B:散列和十字链表

C:二维数组和三维数组

D:三元组和散列

答案:A设矩阵A是一个对称矩阵，为了节省存储空间，将其下三角部分按照行优先存放在一维数组B[0..n(n+1)/2-1]中，对于下三角部分的任一元素a_{i,j}(i>=j，i和j从0开始取值），在一维数组B中的下标k的值是____。

A:i(i+1)/2+j

B:i(i+1)/2+j-1

C:i(i-1)/2+j

D:i(i-1)/2+j-1

答案:A设二维数组A[1..m，1..n]（即m行n列）按行存储在数组B[1..m*n]中，则二维数组元素A[i,j]在一维数组B中的下标为____。

A:(i-1)n+j-1

B:jm+i-1

C:i(j-1)

D:(i-1)n+j

答案:D有一个二维数组A[6][8]，每个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组占用的存储空间大小是（）个字节。

A:48

B:252

C:96

D:288

答案:D二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为()。提示：是按列存放。

A:SA+225

B:SA+222

C:SA+141

D:SA+180

答案:D第七章测试对于一棵具有n个结点、度为4的树来说，（）。

A:至少在某一层上正好有4个结点

B:树的高度最多是n-3

C:第i层上最多有4(i-1)个结点

D:树的高度最多是n-4

答案:B假设每个结点值为单个字符，而一棵树的层次遍历序列为ABCDEFGHIJ，则其根结点的值是（

）。

A:B

B:A

C:J

D:A、B、C都不对

答案:B二叉树若用顺序方法存储，则下列4种运算中()最容易实现。

A:判断两个结点值分别为x、y的结点是不是在同一层上

B:求结点值为x的结点的所有孩子

C:层次遍历二叉树

D:先序遍历二叉树

答案:C若一棵二叉树的先序序列和后序遍历