智慧树知到《数据结构（天津大学）》章节测试答案

智慧树知到《数据结构（天津大学）》章节测试答案
第一章单元测试
1、数据的存储结构是指（）
A.存储在外存中的数据
B.数据的逻辑结构在计算机中的表示
C.数据在计算机中的顺序存储方式
D.数据所占的存储空间量
正确答案：数据的逻辑结构在计算机中的表示
2、算法的空间复杂度是指（）
A.算法程序的长度
B.算法执行过程中所需要的存储空间
C.算法程序中的指令条数
D.算法程序所占的存储空间
正确答案：算法执行过程中所需要的存储空间
3、下列叙述中正确的是（）
A.一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率
B.一个逻辑数据结构只能有一种存储结构
C.一个逻辑数据结构可以有多种存储结构，各种存储结构不影响数据处理的效率
D.数据的逻辑结构属于线性结构，存储结构属于非线性结构
正确答案：一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率
4、程序执行的效率与数据的存储结构密切相关。
A.正确
B.错误
正确答案：正确
5、算法计算量的大小称为计算的（）
A.复杂性
B.效率
C.规模
D.现实性
正确答案：复杂性
6、算法的优劣与算法描述语言无关，但与所用计算机有关。
A.正确
B.错误
正确答案：错误
7、抽象数据类型可通过固有的数据类型来表示和实现。
A.正确
B.错误
正确答案：正确
8、算法是指令的有限序列。
A.正确
B.错误
正确答案：正确
9、数据的不可分割的最小单位是数据元素。
A.正确
B.错误
正确答案：错误
第二章单元测试
1、下述哪个是顺序存储结构的优点？（）
A.存储密度大
B.插入运算方便
C.可方便的用于各种逻辑结构的存储表示
D.删除运算方便
正确答案：存储密度大
2、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。
A.顺序表
B.循环链表
C.双向链表
正确答案：顺序表
3、设线性表有n个元素，以下操作中在顺序表上实现比在链表上实现效率更高是（）
A.交换第1个与第2个元素的值
B.输出与给定值x相等的元素在线性表中的序号
C.输出第i（1≤i≤n）个元素的值
D.顺序输出这n个元素
正确答案：输出第i（1≤i≤n）个元素的值
4、在n个结点的线性表的顺序实现中，算法的时间复杂度为O（1）的操作是（）。
A.在第i个结点后插入一个新结点
B.以上都不对
C.访问第i个结点和求第i个结点的直接前驱
D.删除第i个结点
正确答案：访问第i个结点和求第i个结点的直接前驱
5、循环链表H尾结点p的特点是（）。
A.p==H
B.p->next==H
C.p->next==H->next
D.p==H->next
正确答案：p->next==H
6、向一个长度为n的顺序表中的第i个元素之前插入一个元素时，需要向后移动（）个元素。
A.n-i+1
B.1
C.i
D.n-i
正确答案：n-i+1
7、在一个长度为n的顺序表中删除第i个元素时，需要向前移动（）个元素。
A.i
B.n-i
C.1
D.n-i+1
正确答案：n-i
8、链表的每个结点中都只包含一个指针。
A.正确
B.错误
正确答案：错误
9、链表的物理存储结构具有同链表一样的顺序。
A.正确
B.错误
正确答案：错误
10、当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。
A.正确
B.错误
正确答案：错误
第三章单元测试
1、对于栈操作数据的原则是（）。
A.先进先出
B.后进后出
C.不分次序
D.后进先出
正确答案：后进先出
2、队列的先进先出特征是指（）。
A.最后插入队列的元素总是最后被删除
B.每当有删除操作时，总要先做一次插入操作
C.每次从队中删除的元素总是最早插入的元素
D.当同时进行插入、删除操作时，总是插入操作优先
正确答案：最后插入队列的元素总是最后被删除
3、栈和队列的共同点是（）。
A.都是后进后出
B.无共同点
C.都是先进先出
D.只允许在端点处进行插入和删除
正确答案：只允许在端点处进行插入和删除
4、设入栈序列为1，2，3，4，5，则可能得到的出栈序列为（）。
A.1，2，5，3，4
B.3，1，2，5，4
C.3，2，5，4，1
D.1，4，2，3，5
正确答案：3，2，5，4，1
5、假设栈初始为空，将中缀表达式a/b+（c*d-e*f）/g转化为等价的狗追表达式的过程中，当扫描到f时，栈中的元素依次是（）
A./+-*
B.+（*-
C.+（-*
D./+（*-*
正确答案：+（-*
6、栈和队列的存储方式既可是顺序方式，也可是链接方式。
A.正确
B.错误
正确答案：正确
7、在表结构中最常用的是线性表，栈和队列不太常用。
A.正确
B.错误
正确答案：错误
8、对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。
A.正确
B.错误
正确答案：正确
9、栈和链表是两种不同的数据结构。
A.正确
B.错误
正确答案：错误
10、栈和队列是一种非线性数据结构。
A.正确
B.错误
正确答案：错误
第四章单元测试
1、串 ‘ababaaababaa’ 的 next 数组为（）
A.012345678999
B.012121111212
C.011234223456
D.0123012322345
正确答案：011234223456
2、字符串‘ababaabab’ 的 nextval 为（）
A.0，1，0，1，0，1，0，1，1
B.0，1，0，1，0，0，0，1，1
C.0，1，0，1，0，4，1，0，1
D.0，1，0，1，0，2，1，0，1
正确答案：0，1，0，1，0，4，1，0，1
3、空串与空格字符组成的串的区别在于（）
A.两串包含的字符不相同
B.没有区别
C.两串的长度不相等
D.两串的长度相等
正确答案：两串的长度不相等
4、字符串采用节点大小为1的链表作为其存储结构，是指（）
A.链表的每个链节点的数据域中不仅只存放了一个字符
B.链表的每个链节点的数据域中只存放了一个字符
C.链表的长度为1
D.链表中只存放一个字符
正确答案：链表的每个链节点的数据域中不仅只存放了一个字符
5、一个子串在包含它的主串中的位置是指（）
A.子串的第一个字符在主串中的位置
B.子串的第一个字符在主串中首次出现的位置
C.子串的最后那个字符在主串中的位置
D.子串的最后那个字符在主串中首次出现的位置
正确答案：子串的第一个字符在主串中首次出现的位置
6、如果一个串中的所有字符均在另一串中出现，那么说明前者是后者的子串。（）
A.正确
B.错误
正确答案：错误
7、求子串在串中首次出现位置的运算叫做串的模式匹配。（）
A.正确
B.错误
正确答案：正确
8、一个长度为n（n>；0）的串的子串有n（n+1）/2个。（）
A.正确
B.错误
正确答案：正确
9、如果两个串含有相同的字符集，则说两者相等。（）
A.正确
B.错误
正确答案：错误
10、KMP算法的特点是在模式匹配时指示模式串的指针不会变小。（）
A.正确
B.错误
正确答案：错误
第五章单元测试
1、常对数组进行的两种基本操作是（）
A.索引与修改
B.建立与删除
C.查找与索引
D.查找与修改
正确答案：查找与修改
2、A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+I）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（）。
A.i（j-i）/2+1
B.j（i-l）/2+1
C.j（j-l）/2+i
D.i（i-l）/2+j
正确答案：j（j-l）/2+i
3、所谓稀疏矩阵指的是（）
A.包含有零元素的矩阵
B.零元素个数较多的矩阵
C.零元素个数远远多于非零元素个数且分布没有规律的矩阵
D.零元素个数占矩阵元素中总个数一半的矩阵
正确答案：零元素个数远远多于非零元素个数且分布没有规律的矩阵
4、广义表（（a，b，c，d））的表头是（），表尾是（）。
A.（b，c，d）
B.a
C.（a，b，c，d）
D.（）
正确答案：（a，b，c，d）；（）
5、用数组 r 存储静态链表，结点的 next 域指向后继，工作指针 j 指向链中结点，使 j 沿链移动的操作为（）。
A.j=j->；next
B.j=j+1
C.j=r[j].next
D.j=r[j]->； next
正确答案：j=r[j].next
6、数组可看成线性结构的一种推广，因此与线性表一样，可以进行插入删除等操作。（）
A.正确
B.错误
正确答案：错误
7、一个稀疏矩阵Am*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。（）
A.正确
B.错误
正确答案：错误
8、广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（）
A.正确
B.错误
正确答案：错误
9、有一个100×90的稀疏矩阵，非0元素有10个，设每个整型数占两字节，则用三元组表示该矩阵时，所需的字节数是（）。
A.18000
B.60
C.66
D.33
正确答案：66
10、数组是一种复杂的数据结构，数组元素之间的关系既不是线性的，也不是树形的。（）
A.正确
B.错误
正确答案：错误
第六章单元测试
1、以下说法错误的是（）
A.树形结构的特点是一个结点可以有多个直接前趋
B.树（及一切树形结构）是一种"；分支层次"；结构
C.任何只含一个结点的集合是一棵树
D.树形结构中的一个结点至多只有一个直接后继
正确答案：树形结构的特点是一个结点可以有多个直接前趋
2、设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。
A.M2+M3
B.M1+M2
C.M1
D.M3
正确答案：M2+M3
3、在完全二叉树中，若一个结点是叶结点，则它没（）
A.左子结点
B.左子结点，右子结点和兄弟结点
C.右子结点
D.左子结点和右子结点
正确答案：左子结点和右子结点
4、一棵二叉树高度为h，所有结点的度或为0，或为2，则这棵二叉树最少有（）结点。
A.2h+1
B.2h
C.h+1
D.2h-1
正确答案：2h-1
5、已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历是（）。
A.cedba
B.decab
C.deabc
D.acbed
正确答案：cedba
6、二叉树的遍历只是为了在应用中找到一种线性次序。（）
A.正确
B.错误
正确答案：正确
7、用链表（llink-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n-1个空指针。（）
A.正确
B.错误
正确答案：错误
8、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（）
A.正确
B.错误
正确答案：正确
9、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（）
A.正确
B.错误
正确答案：错误
10、非空二叉树上叶结点数等于双分支结点数加1。（）
A.正确
B.错误
正确答案：正确
第七章单元测试
1、在一个图中，所有顶点的度数之和等于图的边数的（）倍。
A.1
B.2
C.1/2
D.4
正确答案：2
2、有8个结点的无向图最多有 ； 条边。
A.28
B.56
C.112
D.14
正确答案：28
3、用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法的。
A.队列
B.图
C.栈
D.树
正确答案：队列
4、图的深度优先遍历类似于二叉树的（）。
A.中序遍历
B.层次遍历
C.先序遍历
D.后序遍历
正确答案：先序遍历
5、求最短路径的Dijkstra算法的时间复杂度是（） ；（）。
A.O（n2）
B.O（n）
C.O（n+e）
D.O（n*e）
正确答案：O（n2）
6、一个有向图的邻接表和逆邻接表中的结点个数一定相等。（）
A.正确
B.错误
正确答案：正确
7、图G的生成树是该图的一个极小连通子图。（）
A.正确
B.错误
正确答案：错误
8、对任意一个图，从某顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点。（）
A.正确
B.错误
正确答案：错误
9、若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑序列必定存在。（）
A.正确
B.错误
正确答案：正确
10、在n个顶点的无向图中，若边数大于n-1，则该图必是连通图。（）
A.正确
B.错误
正确答案：错误
第八章单元测试
1、当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度（）
A.必定快
B.在大部分情况下要快
C.不一定
D.取决于表递增还是递减
正确答案：在大部分情况下要快
2、若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为（）。
A.n/2
B.（n+1）/2
C.（n-1）/2
D.n
正确答案：（n+1）/2
3、二分法查找的时间复杂性为（）。
A.O（n2）
B.O（logn）
C.O（n）
D.O（nlogn）
正确答案：O（logn）
4、下面关于哈希（Hash，杂凑）查找的说法正确的是（）
A.哈希函数构造的越复杂越好，因为这样随机性好，冲突小
B.不存在特别好与坏的哈希函数，要视情况而定
C.除留余数法是所有哈希函数中最好的
D.若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可
正确答案：不存在特别好与坏的哈希函数，要视情况而定
5、设二叉排序树中有n个结点，则在二叉排序树的平均查找长度为（）。
A.O（log2n）
B.O（n）
C.O（n2）
D.O（1）
正确答案：O（log2n）
6、负载因子（装填因子）是哈希表的一个重要参数，它反映哈希表的装满程度。（）
A.正确
B.错误
正确答案：正确
7、查找相同结点的效率二分查找总比顺序查找高。（）
A.正确
B.错误
正确答案：错误
8、对无序表用二分法查找比顺序查找快。（）
A.正确
B.错误
正确答案：错误
9、二叉搜索树按照中序遍历将各结点打印出来，将得到按照从小到大的排列。（）
A.正确
B.错误
正确答案：正确
10、二叉搜索树一定是满二叉树。（）
A.正确
B.错误
正确答案：错误
第九章单元测试
1、某排序方法的稳定性是指（）
A.该排序算法不允许有相同的关键字记录
B.以上都不对
C.平均时间为0（nlogn）的排序方法
D.该排序算法允许有相同的关键字记录
正确答案：以上都不对
2、下面四种排序方法中，排序过程中的比较次数与排序方法无关的是（）
A.快速排序法
B.插入排序法
C.选择排序法
D.堆积排序法
正确答案：选择排序法
3、下列排序方法中，哪一个是稳定的排序方法？（）
A.希尔排序
B.直接选择排序
C.快速排序
D.二分法插入排序
正确答案：二分法插入排序
4、对一组数据（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.冒泡
正确答案：选择
5、堆的形状是一棵（）。
A.二叉排序树
B.判定树
C.完全二叉树
D.满二叉树
正确答案：完全二叉树
6、直接选择排序算法在最好情况下的时间复杂度为O（N）。（）
A.正确
B.错误
正确答案：错误
7、当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省。（）
A.正确
B.错误
正确答案：错误
8、归并排序辅助存储为O（1）。（）
A.正确
B.错误
正确答案：错误
9、堆不一定是一棵平衡二叉树。（）
A.正确
B.错误
正确答案：正确
10、排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（）
A.正确
B.错误
正确答案：错误