数据结构（绵阳师范学院）智慧树知到课后章节答案2023年下绵阳师范学院

数据结构（绵阳师范学院）智慧树知到课后章节答案2023年下绵阳师范学院绵阳师范学院

第一章测试

计算机算法是指解决问题的步骤序列,它必须具备（）、输入和输出5个特性。

A:可行性、可移植性、可扩充性B:确定性、有穷性、稳定性C:可行性、确定性、有穷性D:易读性、稳定性、安全性

答案:可行性、确定性、有穷性

当需要解决的问题的规模（以某种单位计算）由1增至n时，解决问题的算法所耗费的时间也以某种单位由f(1)增至f(n)，则该算法的时间代价是（）。

A:f(1)B:nC:1D:f(n)

答案:f(n)

下面关于算法说法错误的是（）。

A:算法是指令的有限序列B:算法必须在执行有穷步之后结束C:算法的可行性是指指令不能有二义性D:算法是对特定问题求解步骤的一种描述

答案:算法的可行性是指指令不能有二义性

从逻辑上可以把数据结构分为（）两大类。

A:顺序结构、链式结构B:动态结构、静态结构C:线性结构、非线性结构D:初等结构、构造型结构

答案:线性结构、非线性结构

程序可以采用自然语言、数学语言或者约定的符号语言来描述。

A:错B:对

答案:错

顺序存储设计时，存储单元的地址不一定连续。

A:对B:错

答案:错

数据结构的研究范围主要包括（）。

A:相应的运算B:编程语言C:物理结构D:逻辑结构

答案:相应的运算;物理结构;逻辑结构

对于n个元素可以构造的逻辑结构有（）。

A:集合B:有序表C:链表D:线性结构

答案:集合;线性结构

下述（）与数据的存储结构有关。

A:栈B:循环队列C:散列表D:双向链表

答案:循环队列;散列表;双向链表

以下说法错误的是（）。

A:数据元素是数据的最小单位B:数据结构是带有结构的数据元素的集合C:数据结构是带有结构的各数据项的集合D:数据项是数据的基本单位

答案:数据元素是数据的最小单位;数据结构是带有结构的各数据项的集合;数据项是数据的基本单位

第二章测试

下述（）是顺序存储结构的优点。

A:方便地运用于各种逻辑结构的存储表示B:插入运算方便C:按位查找方便D:删除运算方便

答案:按位查找方便

在一个长度为n的顺序表中删除第i(1<=i<=n)个元素时,需向前移动（）个元素。

A:i-1B:nC:n-i+1D:n-i

答案:n-i

对于顺序存储的线性表,其算法时间复杂度为O(1)的运算应该是（）。

A:改变第i（1<=i<=n）个元素的值B:将n个元素从小到大排序C:在第i（1<=i<=n）个元素后插入一个新元素D:删除第i（1<=i<=n）个元素

答案:改变第i（1<=i<=n）个元素的值

将两个有n个元素的有序表归并为一个有序表，最少比较次数为（）。

A:2n-1B:n-1C:nD:2n

答案:n

一个顺序表所占用的存储空间大小与表的长度无关。

A:错B:对

答案:错

一个链表最常用的操作是在末尾插入结点和删除结点,则选用带头结点的双循环链表最节省时间。

A:对B:错

答案:对

关于线性表顺序存储结构和链式存储结构的描述中，正确的是（）。

A:如频繁使用插入和删除结点操作，顺序存储结构更优于链式存储结构B:线性表的顺序存储结构优于其链式存储结构C:线性表的长度变化较大时，链式存储结构更优于顺序存储结构D:顺序存储结构和链式存储结构都可以进行顺序存取

答案:线性表的长度变化较大时，链式存储结构更优于顺序存储结构;顺序存储结构和链式存储结构都可以进行顺序存取

取线性表的第i个元素的时间与i的大小有关。

A:错B:对

答案:错

在n个元素的线性表的数组表示中,时间复杂度为O(1)的操作是（）。

A:在第i(1B:在最后一个结点后插入一个新值C:访问第i(1D:删除第i(1

答案:在最后一个结点后插入一个新值;访问第i(1

在n个元素的线性表中,删除第1个结点时间复杂度为O(1)。

A:对B:错

答案:错

第三章测试

栈和队列具有相同的（）。

A:运算B:逻辑结构C:抽象数据类型D:存储结构

答案:逻辑结构

栈和队列的主要区别在于（）。

A:所包含的元素不一样B:插入，删除操作的限定不一样C:它们的存储结构不一样D:它们的逻辑结构不一样

答案:插入，删除操作的限定不一样

栈的应用不包括（）。

A:迷宫求解B:图的广度优先遍历C:递归D:进制转换

答案:图的广度优先遍历

元素a,b,c,d,e依次进入初始为空的栈中,若元素进栈后，可停留、可出栈,直到所有元素都出栈,则在所有可能的出栈序列中,以元素d开头的序列个数是（）。

A:6B:3C:4D:5

答案:4

删除栈顶元素不是栈的基本操作。

A:错B:对

答案:错

表达式1*(2+3)+a的后缀表达式是123+*a+。

A:对B:错

答案:对

有六个元素6，5，4，3，2，1的顺序进栈，问下列哪些是合法的出栈序列（）?

A:543612B:346521C:453126D:234156

答案:543612;453126;234156

对于栈操作数据的特点不正确的是（）。

A:先进先出B:不分顺序C:后进先出D:后进后出

答案:先进先出;不分顺序;后进后出

栈是一种受限的线性表,允许在其两端进行操作。

A:对B:错

答案:错

不允许对队列进行的操作有（）。

A:对队列中的元素排序B:取出最近进队的元素C:删除队头元素D:在队列元素之间插入元素

答案:对队列中的元素排序;取出最近进队的元素;在队列元素之间插入元素

第四章测试

两个字符串相等的条件是（）。

A:含有相同的字符集B:串的长度相等C:都是非空串D:两个串的长度相等且对应位置的字符相同

答案:两个串的长度相等且对应位置的字符相同

下面关于串的叙述中，正确的是（）。

A:串的长度必须大于零B:空串就是空白串C:串中元素只能是字母D:串是一种特殊的线性表

答案:串是一种特殊的线性表

若串s=“World”，其子串的个数是（）。

A:6B:15C:5D:16

答案:16

字符串str=“software”，若采用动态分配的顺序存储方法需要（）个字节（设每种数据均占用2个字节）。

A:32B:动态产生，视情况而定C:8D:16

答案:16

串采用节点大小为2的链表作为其存储结构，是指（）。

A:链表中每个节点的数据域中只存放2个字符B:其余选项都不对C:链表的长度为2D:链表中只存放2个字符

答案:链表中每个节点的数据域中只存放2个字符

设有两个串T和S，其中T是S的子串，则求T在S中首次出现位置的算法称为（）。

A:串联接B:模式匹配C:求子串D:求串长

答案:模式匹配

在串的简单模式匹配中，当模式串位j与目标串位i比较时，两字符不相等，则i的位移方式是（）。

A:i=j-i+1B:i=j+1C:i++D:i=i-j+1

答案:i=i-j+1

在KMP模式匹配中，用next数组存放模式串的部分匹配信息。当模式串位j与目标串位i比较时，两字符不相等，则i的位移方式是（）。

A:j=next[j]B:i不变C:j不变D:i=next[j]

答案:i不变

在KMP模式匹配中，用next数组存放模式串的部分匹配信息。当模式串位j与目标串位i比较时，两字符不相等，则j的位移方式是（）。

A:i=next[j]B:i不变C:j=next[j]D:j不变

答案:j=next[j]

空格串是由一个或多个空格字符组成的串，其长度为1。

A:错B:对

答案:错

第五章测试

设有10×6的数组A，数组下标从0,0开始，其每个元素占2个字节，按列优先顺序存储，若已知A[3][4]在内存中的地址是1086，则A[4][5]的地址是（）。

A:1108B:1140C:1054D:1296

答案:1108

以下物理结构中，不能够对数据元素进行随机访问的是（）

A:对称矩阵的压缩存储B:数组的顺序存储C:三元组顺序表D:三对角矩阵的压缩存储

答案:三元组顺序表

若对n阶对称矩阵A，下标从1开始，以行序为主序方式将其下三角形的元素依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定a[i][j](1≤i，j≤n，且i≤j)的位置k的计算公式为()。

A:i(i+1)/2+jB:j(j+1)/2+iC:j(j-1)/2+iD:i(i-1)/2+j

答案:j(j-1)/2+i

经常对数组进行的两种基本操作是()。

A:查找与索引B:查找和修改C:建立与删除D:索引和修改

答案:查找和修改

将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，元素A[66][65]在B数组中的位置K为（）。

A:195B:198C:197D:196

答案:195

下面说法不正确的是()。

A:广义表的表头总是一个广义表B:广义表可以是一个多层次的结构C:一个非空广义表的表尾总是一个广义表D:广义表难以用顺序存储结构进行存储

答案:广义表的表头总是一个广义表

广义表（（a,b,c,d））的表尾是（）。

A:（）B:（b,c,d）C:（a,b,c,d）D:a

答案:（）

广义表（a,(b,c),d,e）的表头为（）。

A:(a,(b,c))B:a,(b,c)C:(a)D:a

答案:a

数组是一种非线性结构，除了插入与删除操作外，数组的基本操作还有存取、修改、检索和排序等操作。

A:对B:错

答案:错

稀疏矩阵中非零元素的个数远小于矩阵中元素的总数。

A:对B:错

答案:对

第六章测试

一棵有n个结点的树的所有结点的度数之和为（）。

A:2nB:n+1C:nD:n-1

答案:n-1

已知一棵完全二叉树的第6层(设根为第1层）有8个叶结点,则该完全二叉树的结点个数最多是（）。

A:111B:119C:39D:52

答案:111

二叉排序树是动态树表,查找失败时插入新结点,会引起树的重新分裂和组合

A:错B:对

答案:错

哈夫曼树具有最小的带权路径长度

A:错B:对

答案:对

在下列关于二叉树遍历的说法中,错误的是（）。

A:若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点,则它一定是该子树的前序遍历结果序列的最后一个结点B:若有一个叶子结点是二叉树中某个子树的中序遍历结果序列的最后一个结点,则它一定是该子树的前序遍历结果序列的最后一个结点C:若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点,则它一定是该子树的前序遍历结果序列的最后一个结点D:若有一个结点是二叉树中某个子树的前序遍历结果序列的最后一个结点,则它一定是该子树的中序遍历结果序列的最后一个结点

答案:若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点,则它一定是该子树的前序遍历结果序列的最后一个结点;若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点,则它一定是该子树的前序遍历结果序列的最后一个结点;若有一个结点是二叉树中某个子树的前序遍历结果序列的最后一个结点,则它一定是该子树的中序遍历结果序列的最后一个结点

下列关于树的说法中,错误的是（）。

A:一棵树中的叶子数一定等于与其对应的二叉树的叶子数B:高度为h(h>0）的完全二叉树对应的森林所含的树的个数一定是hIV.一棵树中的叶子数一定是hC:一对于有n个结点的二又树,其高度为log.nD:完全二叉树中,若一个结点没有左孩子,则它必是叶结点

答案:高度为h(h>0）的完全二叉树对应的森林所含的树的个数一定是hIV.一棵树中的叶子数一定是h;一对于有n个结点的二又树,其高度为log.n;完全二叉树中,若一个结点没有左孩子,则它必是叶结点

将森林转换为对应的二又树,若在二叉树中,结点u是点v的父结点的父结点,则在原来的森林中,u和v可能具有的关系是（）。

A:兄弟关系B:u的父结点与v的父结点是兄弟关系C:父子关系

答案:兄弟关系;父子关系

设X是树T中的一个非根结点,B是T所对应的二又树.在B中,X是其双亲结点的右孩子,下列结论中错误的是（）。

A:在树T中,X一定无右边兄弟B:在树T中,X一定是叶子结点C:在树T中,X是其双亲结点的第一个孩子D:在树T中,X一定有左边兄弟

答案:在树T中,X一定无右边兄弟;在树T中,X一定是叶子结点;在树T中,X是其双亲结点的第一个孩子

第七章测试

在一个具有n个顶点的无向连通图中至少有（）条边。

A:nB:n/2C:n-1D:n+1

答案:n-1

非空无向图的邻接矩阵是一个（）。

A:上三角矩阵B:零矩阵C:对称矩阵D:对角矩阵

答案:对称矩阵

如果从无向图的任一顶点出发进行一次广度优先遍历即可访问所有顶点，则该图一定是（）。

A:一棵树B:有回路C:连通图D:完全图

答案:连通图

一个有向图G=(V，E)，V={0，1，2，3，4}，E={<0，1>，<1，2>，<0，3>，

<2，1>，<1，4>，<2，4>，<4，3>}，现按深度优先遍

历算法遍历，从顶点0出发，所得到的顶点序列是（）

A:0，1，4，2，3B:0，1，2，4，3C:0，1，3，4，2D:0，1，2，3，4

答案:0，1，2，4，3

强连通图是任何顶点到其他所有顶点都有边。

A:对B:错

答案:错

有向图中任一顶点的入度等于出度。

A:错B:对

答案:错

对任何有向图调用一次广度优先遍历算法便可访问所有的顶点。

A:对B:错

答案:错

对任何非强连通图必须2次或以上调用广度优先遍历算法才可访问所有的顶点

A:错B:对

答案:对

树最适合用来表示（）的数据。

A:元素之间具有分支层次关系B:有序C:任意元素之间具有多种联系D:无序

答案:元素之间具有分支层次关系

具有10个叶子结点的二叉树中有（）个度为2的结点。

A:9B:11C:10D:8

答案:9

第八章测试

采用折半搜索算法搜索长度为n的有序表时，元素的平均搜索长度为

A:O（nlog2n）B:O（log2n）C:O（n2）D:O（n）

答案:O（log2n）

对包含n个元素的散列表进行搜索，平均搜索长度为

A:不直接依赖于nB:其余都不对C:O（n）D:O（log2n）

答案:不直接依赖于n

折半(二分)查找有序表(3,4,5,10,13,14,20,30),若查找元素30,则被比较的元素依次为（）

A:10,20,30B:10,14,30C:10,14,20,30D:13,30

答案:10,14,20,30

对线性表进行折半搜索时，要求线性表必须

A:以链接方式存储且结点按关键码有序排列B:以数组方式存储且结点按关键码有序排列C:以数组方式存储D:以链接方式存储

答案:以数组方式存储且结点按关键码有序排列

哈希函数处理冲突的方法有

A:随机探查法B:线性探测法C:拉链法D:开放定址法

答案:拉链法;开放定址法

构造（Hash）函数的方法有

A:随机探查法B:链地址法C:线性探测法D:除留取余法

答案:随机探查法;线性探测法;除留取余法

以折半搜索方法搜索一个线性表时，此线性表必须是顺序存储的有序表。

A:对B:错

答案:对

在索引表中，每个索引项至少包含有关键码值域和子表地址域这两项。

A:对B:错

答案:对

在散列存储中，装载因子α又称为装载系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则α等于n/m

A:对B:错

答案:对

顺序查找的平均查找长度是n/2

A:错B:对

答案:错

第九章测试

设一组初始记录关键字序列为(12，24，18，36，19，38，20，40，35，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为()。

A:12，24，18，36，19，38，20，40，35，70B:12，18，19，20，24，36，35，38，40，70C:12，18，19，20，24，36，38，40，35，70D:12，18，24，36，19，20，38，40，35，70

答案:12，18，24，36，19，20，38，40，35，70

若用冒泡排序对关键字序列{17，15，13，11，10，6}，进行从小到大的排序，所需进行的关键字比较总次数是(