智慧树知到《数据结构》章节测试答案
智慧树知到《数据结构》章节测试答案
第一章单元测试
1、计算机算法是指解决问题的步骤序列 ，它必须具备（）、输入和输出5个特性。
A.易读性、稳定性、安全性
B.可行性、可移植性、可扩充性
C.可行性、确定性、有穷性
D.确定性、有穷性、稳定性
正确答案：可行性、确定性、有穷性
2、算法的时间复杂度取决于（）。
A.其余选项都不对
B.问题的规模
C.待处理数据的初态
D.A和B
正确答案：A和B
3、下面关于算法说法错误的是（）。
A.其余选项都不对
B.算法的可行性是指指令不能有二义性
C.为解决某问题的算法同为该问题编写的程序含义是相同的
D.算法最终必须由计算机程序实现
正确答案：其余选项都不对
4、从逻辑上可以把数据结构分为（）两大类。
A.初等结构、构造型结构
B.线性结构、非线性结构
C.顺序结构、链式结构
D.动态结构、静态结构
正确答案：线性结构、非线性结构
5、算法的计算量的大小称为算法的复杂性。
A.正确
B.错误
正确答案：正确
6、连续存储设计时，存储单元的地址不一定连续。
A.正确
B.错误
正确答案：错误
7、数据结构的研究范围主要包括（）。
A.相应的运算
B.编程语言
C.物理结构
D.逻辑结构
正确答案：相应的运算；物理结构；逻辑结构
8、对于n个元素可以构造的逻辑结构有（）。
A.集合
B.链表
C.线性结构
D.有序表
正确答案：集合；线性结构
9、下述（）与数据的存储结构有关。
A.栈
B.双向链表
C.线索树
D.循环队列
E.散列表
正确答案：双向链表；线索树；循环队列；散列表
10、以下说法错误的是（）。
A.数据项是数据的基本单位
B.数据结构是带有结构的各数据项的集合
C.数据结构是带有结构的数据元素的集合
D.数据元素是数据的最小单位
正确答案：数据项是数据的基本单位；数据结构是带有结构的各数据项的集合；数据元素是数据的最小单位
第二章单元测试
1、下述（）是顺序存储结构的优点。
A.插入运算方便
B.按位查找方便
C.删除运算方便
D.方便地运用于各种逻辑结构的存储表示
正确答案：按位查找方便
2、在一个长度为n的顺序表中删除第i（1<=i<=n）个元素时，需向前移动（）个元素.
A.n-i+1
B.n
C.n-i
D.i-1
正确答案：n-i
3、对于顺序存储的线性表，其算法时间复杂度为O（1）的运算应该是（）。
A.删除第i（1<=i<=n）个元素
B.将n个元素从小到大排序
C.在第i（1<=i<=n）个元素后插入一个新元素
D.改变第i（1<=i<=n）个元素的值
正确答案：改变第i（1<=i<=n）个元素的值
4、将两个有n个元素的有序表归并为一个有序表，最少比较次数为（）
A.2n
B.n-1
C.2n-1
D.n
正确答案：n
5、一个顺序表所占用的存储空间大小与表的长度无关。
A.正确
B.错误
正确答案：错误
6、一个链表最常用的操作是在末尾插入结点和删除结点，则选用带头结点的双循环链表最节省时间。
A.正确
B.错误
正确答案：正确
7、关于线性表顺序存储结构和链式存储结构的描述中，正确的是（）。
A.如频繁使用插入和删除结点操作，顺序存储结构更优于链式存储结构
B.线性表的长度变化较大时，链式存储结构更优于顺序存储结构
C.顺序存储结构和链式存储结构都可以进行顺序存取
D.线性表的顺序存储结构优于其链式存储结构
正确答案：线性表的长度变化较大时，链式存储结构更优于顺序存储结构；顺序存储结构和链式存储结构都可以进行顺序存取
8、在n个元素的线性表的数组表示中，时间复杂度为O（1）的操作是（）。
A.删除第i个结点
B.在最后一个结点后插入一个新值
C.访问第i（1<；i<；n）个结点和求第i（2<；i<；n）个结点的直接前驱
D.在第i（1<；i<；n）个结点后插入一个结点
正确答案：在最后一个结点后插入一个新值；访问第i（1<；i<；n）个结点和求第i（2<；i<；n）个结点的直接前驱
9、取线性表的第i个元素的时间与i的大小有关。
A.正确
B.错误
正确答案：错误
10、在n个元素的线性表中，删除第1个结点时间复杂度为O（1）。
A.正确
B.错误
正确答案：错误
第三章单元测试
1、栈和队列具有相同的（）。
A.存储结构
B.抽象数据类型
C.逻辑结构
D.运算
正确答案：逻辑结构
2、栈和队列的主要区别在于（）。
A.它们的存储结构不一样
B.插入，删除操作的限定不一样
C.它们的逻辑结构不一样
D.所包含的元素不一样
正确答案：插入，删除操作的限定不一样
3、栈的应用不包括（）。
A.缓冲区
B.递归
C.进制转换
D.迷宫求解
正确答案：缓冲区
4、元素 a，b，c，d，e依次进入初始为空的栈中，若元素进栈后；可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是（）。
A.6
B.3
C.5
D.4
正确答案：4
5、删除栈顶元素不是栈的基本操作。（）
A.正确
B.错误
正确答案：错误
6、表达式a*（b+c）-d的后缀表达式是abc+*d-。（）
A.正确
B.错误
正确答案：正确
7、有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪些是合法的出栈序列？（）。
A.3 4 6 5 2 1
B.5 4 3 6 1 2
C.4 5 3 1 2 6
D.2 3 4 1 5 6
正确答案：5 4 3 6 1 2；4 5 3 1 2 6；2 3 4 1 5 6
8、对于栈操作数据的原则不是以下哪些（）。
A.先进先出
B.后进后出
C.不分顺序
D.后进先出
正确答案：先进先出；后进后出；不分顺序
9、不允许对队列进行的操作有（）。
A.取出最近进队的元素
B.在队列元素之间插入元素
C.对队列中的元素排序
D.删除队头元素
正确答案：取出最近进队的元素；在队列元素之间插入元素；对队列中的元素排序
10、栈是一种受限的线性表，允许在其两端进行操作。（）
A.正确
B.错误
正确答案：错误
第四章单元测试
1、两个字符串相等的条件是（）。
A.都是非空串
B.两个串的长度相等且对应位置的字符相同
C.含有相同的字符集
D.串的长度相等
正确答案：两个串的长度相等且对应位置的字符相同
2、下面关于串的叙述中，正确的是（）。
A.空串就是空白串
B.串的长度必须大于零
C.串中元素只能是字母
D.串是一种特殊的线性表
正确答案：串是一种特殊的线性表
3、若串s=“World”，其子串的个数是（）。
A.6
B.16
C.15
D.5
正确答案：16
4、字符串str=“software”，若采用动态分配的顺序存储方法需要（）个字节（设每种数据均占用2个字节）。
A.16
B.32
C.8
D.动态产生，视情况而定
正确答案：16
5、串采用节点大小为2的链表作为其存储结构，是指（）。
A.链表中每个节点的数据域中只存放2个字符
B.链表中只存放2个字符
C.链表的长度为2
D.其余选项都不对
正确答案：链表中每个节点的数据域中只存放2个字符
6、设有两个串T和S，其中T是S的子串，则求T在S中首次出现位置的算法称为（）。
A.串联接
B.求子串
C.模式匹配
D.求串长
正确答案：模式匹配
7、在串的简单模式匹配中，当模式串位j与目标串位i比较时，两字符不相等，则i的位移方式是（）。
A.i++
B.i=j+1
C.i=j-i+1
D.i=i-j+1
正确答案：i=i-j+1
8、在KMP模式匹配中，用next数组存放模式串的部分匹配信息。当模式串位j与目标串位i比较时，两字符不相等，则i的位移方式是（）。
A.j不变
B.i不变
C.i=next[j]
D.j=next[j]
正确答案：i不变
9、在KMP模式匹配中，用next数组存放模式串的部分匹配信息。当模式串位j与目标串位i比较时，两字符不相等，则j的位移方式是（）。
A.j=next[j]
B.i不变
C.j不变
D.i=next[j]
正确答案：j=next[j]
10、空格串是由一个或多个空格字符组成的串，其长度为1。
A.正确
B.错误
正确答案：错误
第五章单元测试
1、设有10×6的数组A，数组下标从0，0开始，其每个元素占2个字节，按列优先顺序存储，若已知A[3][4]在内存中的地址是1086，则A[4][5]的地址是（）。
A.1140
B.1054
C.1296
D.1108
正确答案：1108
2、以下物理结构中，不能够对数据元素进行随机访问的是（）
A.三元组顺序表
B.对称矩阵的压缩存储
C.数组的顺序存储
D.三对角矩阵的压缩存储
正确答案：三元组顺序表
3、若对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+j
B.j（j+1）/2+i
C.j（j-1）/2+i
D.i（i-1）/2+j
正确答案：j（j-1）/2+i
4、经常对数组进行的两种基本操作是（）。
A.索引和修改
B.查找和修改
C.建立与删除
D.查找与索引
正确答案：查找和修改
5、将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，元素A[66][65]在B数组中的位置K为（）。
A.198
B.196
C.197
D.195
正确答案：195
6、下面说法不正确的是（）。
A.广义表难以用顺序存储结构进行存储
B.广义表的表头总是一个广义表
C.一个非空广义表的表尾总是一个广义表
D.广义表可以是一个多层次的结构
正确答案：广义表的表头总是一个广义表
7、广义表（（a，b，c，d））的表尾是（）。
A.（b，c，d）
B.a
C.（）
D.（a，b，c，d）
正确答案：（）
8、广义表（a，（b，c），d，e）的表头为（）。
A.a，（b，c）
B.（a，（b，c））
C.（a）
D.a
正确答案：a
9、数组是一种非线性结构，除了插入与删除操作外，数组的基本操作还有存取、修改、检索和排序等操作。
A.正确
B.错误
正确答案：错误
10、稀疏矩阵中非零元素的个数远小于矩阵中元素的总数。
A.正确
B.错误
正确答案：正确
第六章单元测试
1、树最适合用来表示（）的数据。
A.有序
B.任意元素之间具有多种联系
C.元素之间具有分支层次关系
D.无序
正确答案：元素之间具有分支层次关系
2、具有10个叶子结点的二叉树中有（）个度为2的结点。
A.8
B.11
C.9
D.10
正确答案：9
3、一棵有n个结点的树的所有结点的度数之和为（）。
A.2n
B.n+1
C.n
D.n-1
正确答案：n-1
4、已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是（）。
A.52
B.111
C.119
D.39
正确答案：111
5、二叉排序树是动态树表，查找失败时插入新结点，会引起树的重新分裂和组合。
A.正确
B.错误
正确答案：错误
6、哈夫曼树具有最小的带权路径长度。
A.正确
B.错误
正确答案：正确
7、在下列关于二叉树遍历的说法中，错误的是（）。
A.若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点
B.若有一个叶子结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点
C.若有一个结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点
D.若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点
正确答案：若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点；若有一个结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点；若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点
8、下列关于树的说法中，错误的是（）。
A.高度为h（h>0）的完全二叉树对应的森林所含的树的个数一定是hIV.一棵树中的叶子数一定是h
B.一对于有n个结点的二又树，其高度为log.n
C.完全二叉树中，若一个结点没有左孩子，则它必是叶结点
D.一棵树中的叶子数一定等于与其对应的二叉树的叶子数
正确答案：高度为h（h>0）的完全二叉树对应的森林所含的树的个数一定是hIV.一棵树中的叶子数一定是h；一对于有n个结点的二又树，其高度为log.n；完全二叉树中，若一个结点没有左孩子，则它必是叶结点
9、将森林转换为对应的二又树，若在二叉树中，结点u是点v的父结点的父结点， 则在原来的森林中，u和v可能具有的关系是（）。
A.兄弟关系
B.父子关系
C.u的父结点与v的父结点是兄弟关系
正确答案：兄弟关系；父子关系
10、设X是树T中的一个非根结点，B是T所对应的二又树.在B中，X是其双亲结点的右孩子，下列结论中错误的是（）。
A.在树T中，X一定无右边兄弟
B.在树T中，X一定有左边兄弟
C.在树T中，X一定是叶子结点
D.在树T中，X是其双亲结点的第一个孩子
正确答案：在树T中，X一定无右边兄弟；在树T中，X一定是叶子结点；在树T中，X是其双亲结点的第一个孩子
第七章单元测试
1、对此图进行深度优先遍历正确的有（）
A.0，1，2，5，4，3
B.0，3，5，2，1，4
C.0，2，1，4，5，3
D.0，1，2，5，3，4
正确答案：0，1，2，5，4，3；0，3，5，2，1，4；0，2，1，4，5，3；0，1，2，5，3，4
2、对此无向图进行广度优先遍历正确的有（）
A.0，2，1，3，5，4
B.0，1，2，3，5，4
C.0，1，2，3，4，5
D.0，2，3，1，4，5
正确答案：0，2，1，3，5，4；0，1，2，3，4，5
3、在一个具有n个顶点的无向连通图中至少有（）条边。
A.n
B.n/2
C.n+1
D.n-1
正确答案：n-1
4、非空无向图的邻接矩阵是一个（）。
A.对角矩阵
B.对称矩阵
C.零矩阵
D.上三角矩阵
正确答案：对称矩阵
5、如果从无向图的任一顶点出发进行一次广度优先遍历即可访问所有顶点，则该图一定是（）。
A.一棵树
B.完全图
C.有回路
D.连通图
正确答案：连通图
6、一个有向图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，3
B.0，1，2，3，4
C.0，1，3，4，2
D.0，1，2，4，3
正确答案：0，1，2，4，3
7、强连通图是任何顶点到其他所有顶点都有边。
A.正确
B.错误
正确答案：错误
8、有向图中任一顶点的入度等于出度。
A.正确
B.错误
正确答案：错误
9、对任何有向图调用一次广度优先遍历算法便可访问所有的顶点。
A.正确
B.错误
正确答案：错误
10、对任何非强连通图必须2次或以上调用广度优先遍历算法才可访问所有的顶点。
A.正确
B.错误
正确答案：正确
第八章单元测试
1、采用折半搜索算法搜索长度为n的有序表时，元素的平均搜索长度为
A.O（log2n）
B.O（n log2n）
C.O（n2）
D.O（n）
正确答案：O（log2n）
2、对包含n 个元素的散列表进行搜索，平均搜索长度为
A.不直接依赖于n
B.O（n）
C.O（log2n）
D.其余都不对
正确答案：不直接依赖于n
3、折半（二分）查找有序表（3，4，5，10，13，14，20，30），若查找元素30，则被比较的元素依次为（）
A.10，14，20，30
B.10，14，30
C.13，30
D.10，20，30
正确答案：10，14，20，30
4、对线性表进行折半搜索时，要求线性表必须
A.以链接方式存储且结点按关键码有序排列
B.以链接方式存储
C.以数组方式存储
D.以数组方式存储且结点按关键码有序排列
正确答案：以数组方式存储且结点按关键码有序排列
5、哈希函数处理冲突的方法有
A.线性探测法
B.拉链法
C.随机探查法
D.开放定址法
正确答案：拉链法；开放定址法
6、构造（Hash）函数的方法有
A.线性探测法
B.随机探查法
C.链地址法
D.除留取余法
正确答案：线性探测法；随机探查法；除留取余法
7、以折半搜索方法搜索一个线性表时，此线性表必须是顺序存储的有序表。
A.正确
B.错误
正确答案：正确
8、在索引表中，每个索引项至少包含有关键码值域和子表地址域这两项。
A.正确
B.错误
正确答案：正确
9、在散列存储中，装载因子α又称为装载系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则α等于n/m。
A.正确
B.错误
正确答案：正确
10、顺序查找的平均查找长度是n/2。
A.正确
B.错误
正确答案：错误
第九章单元测试
1、设一组初始记录关键字序列为（25，50，15，35，80，85，20，40，36，70），其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（）。
A.15，25，35，50，20，40，80，85，36，70
B.15，25，35，50，80，85，20，36，40，70
C.15，25，35，50，80，20，85，40，70，36
D.15，25，35，50，80，20，36，40，70，85
正确答案：15，25，35，50，20，40，80，85，36，70
2、若用冒泡排序对关键字序列{18，16，14，12，10，8}，进行从小到大的排序，所需进行的关键字比较总次数是（）。
A.10
B.21
C.15
D.34
正确答案：15
3、对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为
（1）84 47 25 15 21 （2）15 47 25 84 21
（3）15 21 25 84 47 （4）15 21 25 47 84
则采用的排序是（）。
A.快速
B.插入
C.选择
D.冒泡
正确答案：选择
4、对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15）；则采用的是（）排序。
A.希尔
B.快速
C.选择
D.冒泡
正确答案：希尔
5、数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中（）的两趟排序后的结果。
A.堆排序
B.冒泡排序
C.选择排序
D.插入排序
正确答案：插入排序
6、以下属于内排序方法的是（）。
A.基数排序
B.拓扑排序
C.快速排序
D.冒泡排序
正确答案：基数排序；快速排序；冒泡排序
7、下列排序算法中，（）算法是稳定的。
A.直接插入排序
B.快速排序
C.冒泡排序
D.基数排序
正确答案：直接插入排序；冒泡排序；基数排序
8、当待排序元素序列的初始排列基本有序时，希尔排序比直接插入排序快。
A.正确
B.错误
正确答案：错误
9、向具有n个结点的堆中插入一个新元素的时间复杂度为O（㏒2n）。
A.正确
B.错误
正确答案：正确
10、按排序策略分类，起泡排序属于选择排序。对n个元素的序列进行排序时，如果待排序元素序列的初始排列已经全部有序，则起泡排序过程中需进行n-1次元素值的比较，0次元素值的交换。如果待排序元素序列的初始排列完全逆序，则起泡排序过程中需进行n（n-1）/2次元素值的比较，n（n-1）/2次元素的交换。
A.正确
B.错误
正确答案：正确
第一章单元测试
1、计算机算法是指解决问题的步骤序列 ，它必须具备（）、输入和输出5个特性。
A.易读性、稳定性、安全性
B.可行性、可移植性、可扩充性
C.可行性、确定性、有穷性
D.确定性、有穷性、稳定性
正确答案：可行性、确定性、有穷性
2、算法的时间复杂度取决于（）。
A.其余选项都不对
B.问题的规模
C.待处理数据的初态
D.A和B
正确答案：A和B
3、下面关于算法说法错误的是（）。
A.其余选项都不对
B.算法的可行性是指指令不能有二义性
C.为解决某问题的算法同为该问题编写的程序含义是相同的
D.算法最终必须由计算机程序实现
正确答案：其余选项都不对
4、从逻辑上可以把数据结构分为（）两大类。
A.初等结构、构造型结构
B.线性结构、非线性结构
C.顺序结构、链式结构
D.动态结构、静态结构
正确答案：线性结构、非线性结构
5、算法的计算量的大小称为算法的复杂性。
A.正确
B.错误
正确答案：正确
6、连续存储设计时，存储单元的地址不一定连续。
A.正确
B.错误
正确答案：错误
7、数据结构的研究范围主要包括（）。
A.相应的运算
B.编程语言
C.物理结构
D.逻辑结构
正确答案：相应的运算；物理结构；逻辑结构
8、对于n个元素可以构造的逻辑结构有（）。
A.集合
B.链表
C.线性结构
D.有序表
正确答案：集合；线性结构
9、下述（）与数据的存储结构有关。
A.栈
B.双向链表
C.线索树
D.循环队列
E.散列表
正确答案：双向链表；线索树；循环队列；散列表
10、以下说法错误的是（）。
A.数据项是数据的基本单位
B.数据结构是带有结构的各数据项的集合
C.数据结构是带有结构的数据元素的集合
D.数据元素是数据的最小单位
正确答案：数据项是数据的基本单位；数据结构是带有结构的各数据项的集合；数据元素是数据的最小单位
第二章单元测试
1、下述（）是顺序存储结构的优点。
A.插入运算方便
B.按位查找方便
C.删除运算方便
D.方便地运用于各种逻辑结构的存储表示
正确答案：按位查找方便
2、在一个长度为n的顺序表中删除第i（1<=i<=n）个元素时，需向前移动（）个元素.
A.n-i+1
B.n
C.n-i
D.i-1
正确答案：n-i
3、对于顺序存储的线性表，其算法时间复杂度为O（1）的运算应该是（）。
A.删除第i（1<=i<=n）个元素
B.将n个元素从小到大排序
C.在第i（1<=i<=n）个元素后插入一个新元素
D.改变第i（1<=i<=n）个元素的值
正确答案：改变第i（1<=i<=n）个元素的值
4、将两个有n个元素的有序表归并为一个有序表，最少比较次数为（）
A.2n
B.n-1
C.2n-1
D.n
正确答案：n
5、一个顺序表所占用的存储空间大小与表的长度无关。
A.正确
B.错误
正确答案：错误
6、一个链表最常用的操作是在末尾插入结点和删除结点，则选用带头结点的双循环链表最节省时间。
A.正确
B.错误
正确答案：正确
7、关于线性表顺序存储结构和链式存储结构的描述中，正确的是（）。
A.如频繁使用插入和删除结点操作，顺序存储结构更优于链式存储结构
B.线性表的长度变化较大时，链式存储结构更优于顺序存储结构
C.顺序存储结构和链式存储结构都可以进行顺序存取
D.线性表的顺序存储结构优于其链式存储结构
正确答案：线性表的长度变化较大时，链式存储结构更优于顺序存储结构；顺序存储结构和链式存储结构都可以进行顺序存取
8、在n个元素的线性表的数组表示中，时间复杂度为O（1）的操作是（）。
A.删除第i个结点
B.在最后一个结点后插入一个新值
C.访问第i（1<；i<；n）个结点和求第i（2<；i<；n）个结点的直接前驱
D.在第i（1<；i<；n）个结点后插入一个结点
正确答案：在最后一个结点后插入一个新值；访问第i（1<；i<；n）个结点和求第i（2<；i<；n）个结点的直接前驱
9、取线性表的第i个元素的时间与i的大小有关。
A.正确
B.错误
正确答案：错误
10、在n个元素的线性表中，删除第1个结点时间复杂度为O（1）。
A.正确
B.错误
正确答案：错误
第三章单元测试
1、栈和队列具有相同的（）。
A.存储结构
B.抽象数据类型
C.逻辑结构
D.运算
正确答案：逻辑结构
2、栈和队列的主要区别在于（）。
A.它们的存储结构不一样
B.插入，删除操作的限定不一样
C.它们的逻辑结构不一样
D.所包含的元素不一样
正确答案：插入，删除操作的限定不一样
3、栈的应用不包括（）。
A.缓冲区
B.递归
C.进制转换
D.迷宫求解
正确答案：缓冲区
4、元素 a，b，c，d，e依次进入初始为空的栈中，若元素进栈后；可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是（）。
A.6
B.3
C.5
D.4
正确答案：4
5、删除栈顶元素不是栈的基本操作。（）
A.正确
B.错误
正确答案：错误
6、表达式a*（b+c）-d的后缀表达式是abc+*d-。（）
A.正确
B.错误
正确答案：正确
7、有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪些是合法的出栈序列？（）。
A.3 4 6 5 2 1
B.5 4 3 6 1 2
C.4 5 3 1 2 6
D.2 3 4 1 5 6
正确答案：5 4 3 6 1 2；4 5 3 1 2 6；2 3 4 1 5 6
8、对于栈操作数据的原则不是以下哪些（）。
A.先进先出
B.后进后出
C.不分顺序
D.后进先出
正确答案：先进先出；后进后出；不分顺序
9、不允许对队列进行的操作有（）。
A.取出最近进队的元素
B.在队列元素之间插入元素
C.对队列中的元素排序
D.删除队头元素
正确答案：取出最近进队的元素；在队列元素之间插入元素；对队列中的元素排序
10、栈是一种受限的线性表，允许在其两端进行操作。（）
A.正确
B.错误
正确答案：错误
第四章单元测试
1、两个字符串相等的条件是（）。
A.都是非空串
B.两个串的长度相等且对应位置的字符相同
C.含有相同的字符集
D.串的长度相等
正确答案：两个串的长度相等且对应位置的字符相同
2、下面关于串的叙述中，正确的是（）。
A.空串就是空白串
B.串的长度必须大于零
C.串中元素只能是字母
D.串是一种特殊的线性表
正确答案：串是一种特殊的线性表
3、若串s=“World”，其子串的个数是（）。
A.6
B.16
C.15
D.5
正确答案：16
4、字符串str=“software”，若采用动态分配的顺序存储方法需要（）个字节（设每种数据均占用2个字节）。
A.16
B.32
C.8
D.动态产生，视情况而定
正确答案：16
5、串采用节点大小为2的链表作为其存储结构，是指（）。
A.链表中每个节点的数据域中只存放2个字符
B.链表中只存放2个字符
C.链表的长度为2
D.其余选项都不对
正确答案：链表中每个节点的数据域中只存放2个字符
6、设有两个串T和S，其中T是S的子串，则求T在S中首次出现位置的算法称为（）。
A.串联接
B.求子串
C.模式匹配
D.求串长
正确答案：模式匹配
7、在串的简单模式匹配中，当模式串位j与目标串位i比较时，两字符不相等，则i的位移方式是（）。
A.i++
B.i=j+1
C.i=j-i+1
D.i=i-j+1
正确答案：i=i-j+1
8、在KMP模式匹配中，用next数组存放模式串的部分匹配信息。当模式串位j与目标串位i比较时，两字符不相等，则i的位移方式是（）。
A.j不变
B.i不变
C.i=next[j]
D.j=next[j]
正确答案：i不变
9、在KMP模式匹配中，用next数组存放模式串的部分匹配信息。当模式串位j与目标串位i比较时，两字符不相等，则j的位移方式是（）。
A.j=next[j]
B.i不变
C.j不变
D.i=next[j]
正确答案：j=next[j]
10、空格串是由一个或多个空格字符组成的串，其长度为1。
A.正确
B.错误
正确答案：错误
第五章单元测试
1、设有10×6的数组A，数组下标从0，0开始，其每个元素占2个字节，按列优先顺序存储，若已知A[3][4]在内存中的地址是1086，则A[4][5]的地址是（）。
A.1140
B.1054
C.1296
D.1108
正确答案：1108
2、以下物理结构中，不能够对数据元素进行随机访问的是（）
A.三元组顺序表
B.对称矩阵的压缩存储
C.数组的顺序存储
D.三对角矩阵的压缩存储
正确答案：三元组顺序表
3、若对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+j
B.j（j+1）/2+i
C.j（j-1）/2+i
D.i（i-1）/2+j
正确答案：j（j-1）/2+i
4、经常对数组进行的两种基本操作是（）。
A.索引和修改
B.查找和修改
C.建立与删除
D.查找与索引
正确答案：查找和修改
5、将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，元素A[66][65]在B数组中的位置K为（）。
A.198
B.196
C.197
D.195
正确答案：195
6、下面说法不正确的是（）。
A.广义表难以用顺序存储结构进行存储
B.广义表的表头总是一个广义表
C.一个非空广义表的表尾总是一个广义表
D.广义表可以是一个多层次的结构
正确答案：广义表的表头总是一个广义表
7、广义表（（a，b，c，d））的表尾是（）。
A.（b，c，d）
B.a
C.（）
D.（a，b，c，d）
正确答案：（）
8、广义表（a，（b，c），d，e）的表头为（）。
A.a，（b，c）
B.（a，（b，c））
C.（a）
D.a
正确答案：a
9、数组是一种非线性结构，除了插入与删除操作外，数组的基本操作还有存取、修改、检索和排序等操作。
A.正确
B.错误
正确答案：错误
10、稀疏矩阵中非零元素的个数远小于矩阵中元素的总数。
A.正确
B.错误
正确答案：正确
第六章单元测试
1、树最适合用来表示（）的数据。
A.有序
B.任意元素之间具有多种联系
C.元素之间具有分支层次关系
D.无序
正确答案：元素之间具有分支层次关系
2、具有10个叶子结点的二叉树中有（）个度为2的结点。
A.8
B.11
C.9
D.10
正确答案：9
3、一棵有n个结点的树的所有结点的度数之和为（）。
A.2n
B.n+1
C.n
D.n-1
正确答案：n-1
4、已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是（）。
A.52
B.111
C.119
D.39
正确答案：111
5、二叉排序树是动态树表，查找失败时插入新结点，会引起树的重新分裂和组合。
A.正确
B.错误
正确答案：错误
6、哈夫曼树具有最小的带权路径长度。
A.正确
B.错误
正确答案：正确
7、在下列关于二叉树遍历的说法中，错误的是（）。
A.若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点
B.若有一个叶子结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点
C.若有一个结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点
D.若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点
正确答案：若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点；若有一个结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点；若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点
8、下列关于树的说法中，错误的是（）。
A.高度为h（h>0）的完全二叉树对应的森林所含的树的个数一定是hIV.一棵树中的叶子数一定是h
B.一对于有n个结点的二又树，其高度为log.n
C.完全二叉树中，若一个结点没有左孩子，则它必是叶结点
D.一棵树中的叶子数一定等于与其对应的二叉树的叶子数
正确答案：高度为h（h>0）的完全二叉树对应的森林所含的树的个数一定是hIV.一棵树中的叶子数一定是h；一对于有n个结点的二又树，其高度为log.n；完全二叉树中，若一个结点没有左孩子，则它必是叶结点
9、将森林转换为对应的二又树，若在二叉树中，结点u是点v的父结点的父结点， 则在原来的森林中，u和v可能具有的关系是（）。
A.兄弟关系
B.父子关系
C.u的父结点与v的父结点是兄弟关系
正确答案：兄弟关系；父子关系
10、设X是树T中的一个非根结点，B是T所对应的二又树.在B中，X是其双亲结点的右孩子，下列结论中错误的是（）。
A.在树T中，X一定无右边兄弟
B.在树T中，X一定有左边兄弟
C.在树T中，X一定是叶子结点
D.在树T中，X是其双亲结点的第一个孩子
正确答案：在树T中，X一定无右边兄弟；在树T中，X一定是叶子结点；在树T中，X是其双亲结点的第一个孩子
第七章单元测试
1、对此图进行深度优先遍历正确的有（）
A.0，1，2，5，4，3
B.0，3，5，2，1，4
C.0，2，1，4，5，3
D.0，1，2，5，3，4
正确答案：0，1，2，5，4，3；0，3，5，2，1，4；0，2，1，4，5，3；0，1，2，5，3，4
2、对此无向图进行广度优先遍历正确的有（）
A.0，2，1，3，5，4
B.0，1，2，3，5，4
C.0，1，2，3，4，5
D.0，2，3，1，4，5
正确答案：0，2，1，3，5，4；0，1，2，3，4，5
3、在一个具有n个顶点的无向连通图中至少有（）条边。
A.n
B.n/2
C.n+1
D.n-1
正确答案：n-1
4、非空无向图的邻接矩阵是一个（）。
A.对角矩阵
B.对称矩阵
C.零矩阵
D.上三角矩阵
正确答案：对称矩阵
5、如果从无向图的任一顶点出发进行一次广度优先遍历即可访问所有顶点，则该图一定是（）。
A.一棵树
B.完全图
C.有回路
D.连通图
正确答案：连通图
6、一个有向图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，3
B.0，1，2，3，4
C.0，1，3，4，2
D.0，1，2，4，3
正确答案：0，1，2，4，3
7、强连通图是任何顶点到其他所有顶点都有边。
A.正确
B.错误
正确答案：错误
8、有向图中任一顶点的入度等于出度。
A.正确
B.错误
正确答案：错误
9、对任何有向图调用一次广度优先遍历算法便可访问所有的顶点。
A.正确
B.错误
正确答案：错误
10、对任何非强连通图必须2次或以上调用广度优先遍历算法才可访问所有的顶点。
A.正确
B.错误
正确答案：正确
第八章单元测试
1、采用折半搜索算法搜索长度为n的有序表时，元素的平均搜索长度为
A.O（log2n）
B.O（n log2n）
C.O（n2）
D.O（n）
正确答案：O（log2n）
2、对包含n 个元素的散列表进行搜索，平均搜索长度为
A.不直接依赖于n
B.O（n）
C.O（log2n）
D.其余都不对
正确答案：不直接依赖于n
3、折半（二分）查找有序表（3，4，5，10，13，14，20，30），若查找元素30，则被比较的元素依次为（）
A.10，14，20，30
B.10，14，30
C.13，30
D.10，20，30
正确答案：10，14，20，30
4、对线性表进行折半搜索时，要求线性表必须
A.以链接方式存储且结点按关键码有序排列
B.以链接方式存储
C.以数组方式存储
D.以数组方式存储且结点按关键码有序排列
正确答案：以数组方式存储且结点按关键码有序排列
5、哈希函数处理冲突的方法有
A.线性探测法
B.拉链法
C.随机探查法
D.开放定址法
正确答案：拉链法；开放定址法
6、构造（Hash）函数的方法有
A.线性探测法
B.随机探查法
C.链地址法
D.除留取余法
正确答案：线性探测法；随机探查法；除留取余法
7、以折半搜索方法搜索一个线性表时，此线性表必须是顺序存储的有序表。
A.正确
B.错误
正确答案：正确
8、在索引表中，每个索引项至少包含有关键码值域和子表地址域这两项。
A.正确
B.错误
正确答案：正确
9、在散列存储中，装载因子α又称为装载系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则α等于n/m。
A.正确
B.错误
正确答案：正确
10、顺序查找的平均查找长度是n/2。
A.正确
B.错误
正确答案：错误
第九章单元测试
1、设一组初始记录关键字序列为（25，50，15，35，80，85，20，40，36，70），其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（）。
A.15，25，35，50，20，40，80，85，36，70
B.15，25，35，50，80，85，20，36，40，70
C.15，25，35，50，80，20，85，40，70，36
D.15，25，35，50，80，20，36，40，70，85
正确答案：15，25，35，50，20，40，80，85，36，70
2、若用冒泡排序对关键字序列{18，16，14，12，10，8}，进行从小到大的排序，所需进行的关键字比较总次数是（）。
A.10
B.21
C.15
D.34
正确答案：15
3、对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为
（1）84 47 25 15 21 （2）15 47 25 84 21
（3）15 21 25 84 47 （4）15 21 25 47 84
则采用的排序是（）。
A.快速
B.插入
C.选择
D.冒泡
正确答案：选择
4、对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15）；则采用的是（）排序。
A.希尔
B.快速
C.选择
D.冒泡
正确答案：希尔
5、数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中（）的两趟排序后的结果。
A.堆排序
B.冒泡排序
C.选择排序
D.插入排序
正确答案：插入排序
6、以下属于内排序方法的是（）。
A.基数排序
B.拓扑排序
C.快速排序
D.冒泡排序
正确答案：基数排序；快速排序；冒泡排序
7、下列排序算法中，（）算法是稳定的。
A.直接插入排序
B.快速排序
C.冒泡排序
D.基数排序
正确答案：直接插入排序；冒泡排序；基数排序
8、当待排序元素序列的初始排列基本有序时，希尔排序比直接插入排序快。
A.正确
B.错误
正确答案：错误
9、向具有n个结点的堆中插入一个新元素的时间复杂度为O（㏒2n）。
A.正确
B.错误
正确答案：正确
10、按排序策略分类，起泡排序属于选择排序。对n个元素的序列进行排序时，如果待排序元素序列的初始排列已经全部有序，则起泡排序过程中需进行n-1次元素值的比较，0次元素值的交换。如果待排序元素序列的初始排列完全逆序，则起泡排序过程中需进行n（n-1）/2次元素值的比较，n（n-1）/2次元素的交换。
A.正确
B.错误
正确答案：正确