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

1、第 页2021知到答案【 数据结构（天津大学） 智慧树满分章节测试答案 第一章 章节测试 1、选择题:数据的存储结构是指（）选项：A:存储在外存中的数据B:数据的逻辑结构在计算机中的表示C:数据在计算机中的挨次存储方式D:数据所占的存储空间量答案: 【数据的逻辑结构在计算机中的表示】2、选择题:算法的空间简单度是指（）选项：A:算法程序的长度B:算法执行过程中所需要的存储空间C:算法程序中的指令条数D:算法程序所占的存储空间答案: 【算法执行过程中所需要的存储空间】3、选择题:下列叙述中正确的是（）选项：A:一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率B:一个逻辑数据结

2、构只能有一种存储结构C:一个逻辑数据结构可以有多种存储结构，各种存储结构不影响数据处理的效率D:数据的逻辑结构属于线性结构，存储结构属于非线性结构答案: 【一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率】4、选择题:程序执行的效率与数据的存储结构密切相关。选项：A:对B:错答案: 【对】5、选择题:算法计算量的大小称为计算的（）选项：A:简单性B:效率C:规模D:现实性答案: 【简单性】6、选择题:算法的优劣与算法描述语言无关，但与所用计算机有关。选项：A:对B:错答案: 【错】7、选择题:抽象数据类型可通过固有的数据类型来表示和实现。选项：A:对B:错答案: 【对】8、

3、选择题:算法是指令的有限序列。选项：A:错B:对答案: 【对】9、选择题:数据的不可分割的最小单位是数据元素。选项：A:对B:错答案: 【错】第二章 章节测试 1、选择题:下述哪个是挨次存储结构的优点？（ ）选项：A:存储密度大B:插入运算便利C:可便利的用于各种逻辑结构的存储表示D:删除运算便利答案: 【存储密度大】2、选择题:若某线性表最常用的操作是存取任一指定序号的元素和在最终进行插入和删除运算，则利用（ ）存储方式最节省时间。选项：A:挨次表B:循环链表C:双向链表答案: 【挨次表】3、选择题:设线性表有n个元素，以下操作中在挨次表上实现比在链表上实现效率更高是（）选项：A:交换第1个

4、与第2个元素的值B:输出与给定值x相等的元素在线性表中的序号C:输出第i（1in）个元素的值D:挨次输出这n个元素答案: 【输出第i（1in）个元素的值】4、选择题:在n个结点的线性表的挨次实现中，算法的时间简单度为O(1)的操作是（）。选项：A:在第i个结点后插入一个新结点B:以上都不对C:访问第i个结点和求第i个结点的直接前驱D:删除第i个结点答案: 【访问第i个结点和求第i个结点的直接前驱】5、选择题:循环链表H尾结点p的特点是()。选项：A:p=HB:p-next=HC:p-next=H-nextD:p=H-next答案: 【p-next=H】6、选择题:向一个长度为n的挨次表中的第i

5、个元素之前插入一个元素时，需要向后移动()个元素。选项：A:n-i+1B:1C:iD:n-i答案: 【n-i+1】7、选择题:在一个长度为n的挨次表中删除第i个元素时，需要向前移动()个元素。选项：A:iB:n-iC:1D:n-i+1答案: 【n-i】8、选择题:链表的每个结点中都只包含一个指针。选项：A:错B:对答案: 【错】9、选择题:链表的物理存储结构具有同链表一样的挨次。选项：A:错B:对答案: 【错】10、选择题:当删除链中某个结点后，计算机会自动地将后续的各个章向前移动。选项：A:对B:错答案: 【错】第三章 章节测试 1、选择题:对于栈操作数据的原则是（）。选项：A:先进先出B:

6、后进后出C:不分次序D:后进先出答案: 【后进先出】$2、选择题:队列的先进先出特征是指()。选项：A:最终插入队列的元素总是最终被删除B:每当有删除操作时，总要先做一次插入操作C:每次从队中删除的元素总是最早插入的元素D:当同时进行插入、删除操作时，总是插入操作优先答案: 【最终插入队列的元素总是最终被删除】3、选择题:栈和队列的共同点是（）。选项：A:都是后进后出B:无共同点C:都是先进先出D:只允许在端点处进行插入和删除答案: 【只允许在端点处进行插入和删除】4、选择题:设入栈序列为1,2,3,4,5,则可能得到的出栈序列为（）。选项：A:1,2,5,3,4B:3,1,2,5,4C:3,

7、2,5,4,1D: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、选择题:栈和链表是

8、两种不同的数据结构。选项：A:错B:对答案: 【错】10、选择题:栈和队列是一种非线性数据结构。选项：A:对B:错答案: 【错】 第四章 章节测试 1、选择题:串 ababaaababaa 的 next 数组为（ ）选项：A:012345678999B:012121111212C:011234223456D:0123012322345答案: 【011234223456】2、选择题:字符串ababaabab 的 nextval 为（ ）选项：A:0,1,0,1,0,1,0,1,1B:0,1,0,1,0,0,0,1,1C:0,1,0,1,0,4,1,0,1D:0,1,0,1,0,2,1,0,1答案

9、: 【0,1,0,1,0,4,1,0,1】3、选择题:空串与空格字符组成的串的区别在于（ ）选项：A:两串包含的字符不相同B:没有区别C:两串的长度不相等D:两串的长度相等答案: 【两串的长度不相等】4、选择题:字符串采用节点大小为1的链表作为其存储结构，是指（ ）选项：A:链表的每个链节点的数据域中不仅只存放了一个字符B:链表的每个链节点的数据域中只存放了一个字符C:链表的长度为1D:链表中只存放一个字符答案: 【链表的每个链节点的数据域中不仅只存放了一个字符】5、选择题:一个子串在包含它的主串中的位置是指（ ）选项：A:子串的第一个字符在主串中的位置B:子串的第一个字符在主串中首次消失的位

10、置C:子串的最终那个字符在主串中的位置D:子串的最终那个字符在主串中首次消失的位置答案: 【子串的第一个字符在主串中首次消失的位置】6、选择题:假如一个串中的全部字符均在另一串中消失，那么说明前者是后者的子串。（ ）选项：A:错B:对答案: 【错】7、选择题:求子串在串中首次消失位置的运算叫做串的模式匹配。（ ）选项：A:对B:错答案: 【对】8、选择题:一个长度为n（n0）的串的子串有n（n+1）/2个。（ ）选项：A:对B:错答案: 【对】9、选择题:假如两个串含有相同的字符集，则说两者相等。（ ）选项：A:对B:错答案: 【错】10、选择题:KMP算法的特点是在模式匹配时指示模式串的指针

11、不会变小。（ ）选项：A:对B:错答案: 【错】 第五章 章节测试 1、选择题:常对数组进行的两种基本操作是（ ）选项：A:索引与修改B:建立与删除C:查找与索引D:查找与修改答案: 【查找与修改】2、选择题:AN，N是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组TN(N+I)/2中，则对任一上三角元素aij对应Tk的下标k是( )。选项：A:i(j-i)/2+1B:j(i-l)/2+1C:j(j-l)/2+iD:i(i-l)/2+j答案: 【j(j-l)/2+i】3、选择题:所谓稀疏矩阵指的是( )选项：A:包含有零元素的矩阵B:零元素个数较多的矩阵C:零元素个数远远多于非零元素个

12、数且分布没有规律的矩阵D:零元素个数占矩阵元素中总个数一半的矩阵答案: 【零元素个数远远多于非零元素个数且分布没有规律的矩阵】4、选择题:广义表（a,b,c,d）的表头是（ ），表尾是（ ）。选项：A:（b,c,d）B: aC:（a,b,c,d）D:（）答案: 【（a,b,c,d）;（）】5、选择题:用数组 r 存储静态链表，结点的 next 域指向后继，工作指针 j 指向链中结点，使 j 沿链移动的操作为( )。选项：A:j=j-nextB:j=j+1C:j=rj.nextD:j=rj- next答案: 【j=rj.next】6、选择题:数组可看成线性结构的一种推广，因此与线性表一样，可以进

13、行插入删除等操作。（ ）选项：A:对B:错答案: 【错】7、选择题:一个稀疏矩阵Am*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。（ ）选项：A:对B:错答案: 【错】8、选择题:广义表的取表尾运算，其结果通常是个表，但有时也可是个章素值。（ ）选项：A:对B:错答案: 【错】9、选择题:有一个10090的稀疏矩阵，非0元素有10个，设每个整型数占两字节，则用三元组表示该矩阵时，所需的字节数是( )。选项：A:18000B:60C:66D:33答案: 【66】10、选择题:数组是一种简单的数据结构，数组元素之间的关系既不是线性

14、的，也不是树形的。（ ）选项：A:对B:错答案: 【错】 第六章 章节测试 1、选择题:以下说法错误的是（ ）选项：A:树形结构的特点是一个结点可以有多个直接前趋B:树(及一切树形结构)是一种分支层次结构C:任何只含一个结点的集合是一棵树D:树形结构中的一个结点至多只有一个直接后继答案: 【树形结构的特点是一个结点可以有多个直接前趋】2、选择题:设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ）。选项：A:M2+M3B:M1+M2C:M1D:M3答案: 【M2+M3】3、选择题:在完全二叉树中，若一个结点是叶结点，则

15、它没（ ）选项：A:左子结点B:左子结点，右子结点和兄弟结点C:右子结点D:左子结点和右子结点答案: 【左子结点和右子结点】4、选择题:一棵二叉树高度为h,全部结点的度或为0，或为2，则这棵二叉树最少有( )结点。选项：A:2h+1B:2hC:h+1D:2h-1答案: 【2h-1】5、选择题:已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历是（ ）。选项：A:cedba B:decabC:deabc D:acbed 答案: 【cedba 】6、选择题:二叉树的遍历只是为了在应用中找到一种线性次序。（ ）选项：A:错B:对答案: 【对】7、选择题:用链表(llink

16、-rlink)存储包含n个结点的二叉树，结点的2n个指针区域中有n-1个空指针。（ )选项：A:对B:错答案: 【错】8、选择题:中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。( )选项：A:错B:对答案: 【对】9、选择题:用一维数组存储二叉树时，总是以前序遍历挨次存储结点。( )选项：A:错B:对答案: 【错】10、选择题:非空二叉树上叶结点数等于双分支结点数加1。( )选项：A:错B:对答案: 【对】 第七章 章节测试 1、选择题:在一个图中，全部顶点的度数之和等于图的边数的（ )倍。选项：A:1B:2C:1/2 D:4答案: 【2】2、选择题:有8个结点的无向图最多有 条边。选

17、项：A:28B:56C:112D: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的生成树是该图的一个微小连通子图。

18、（ ）选项：A:对B:错答案: 【错】8、选择题:对任意一个图，从某顶点出发进行一次深度优先或广度优先遍历，可访问图的全部顶点。（ ）选项：A:对B:错答案: 【错】9、选择题:若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑序列必定存在。（ ）选项：A:错B:对答案: 【对】10、选择题:在n个顶点的无向图中，若边数大于n-1，则该图必是连通图。（ ）选项：A:对B:错答案: 【错】 第八章 章节测试 1、选择题:当在一个有序的挨次存储表上查找一个数据时，即可用折半查找，也可用挨次查找，但前者比后者的查找速度( )选项：A:必定快B:在大部分情况下要快C:不肯定D:取决于表递增还是

19、递减答案: 【在大部分情况下要快】2、选择题:若查找每个记录的概率均等，则在具有n个记录的连续挨次文件中采用挨次查找法查找一个记录，其平均查找长度ASL为( )。选项：A:n/2B:(n+1)/2C:(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:若

20、需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简洁的将该元素删去即可答案: 【不存在特殊好与坏的哈希函数，要视情况而定】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:该排序算法不允许有