数据结构智慧树知到期末考试答案章节答案2024年哈尔滨商业大学

数据结构智慧树知到期末考试答案+章节答案2024年哈尔滨商业大学“DT”是“DATA”的子串。（）

答案:错下面的叙述不正确的是（）。

答案:线性表在顺序存储时，查找第i个元素的时间同i的值成正比###线性表在链式存储时，查找第i个元素的时间同i的值无关若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。

答案:顺序表计算算法的时间复杂度是属于一种（）。

答案:事前分析估算的方法计算机中数据文件组织采用的结构是（）。

答案:树为实现快速排序算法，待排序序列采用的存储方式是（）。

答案:顺序存储下列内部排序算法中，排序的平均时间复杂度为O(nlogn)的是（）。

答案:堆排序###2-路归并排序###快速排序排序的稳定性指排序算法中的比较次数保持不变，且算法能够终止。（）

答案:错对给定的关键字序列110,119,007,911,114,120,122进行基数排序，则第2趟分配收集后得到的关键字序列是（）。

答案:007,110,911,114,119,120,122归并排序要求的辅助空间最多。（）

答案:对基数排序只适用于以数字为关键字的情况，不适用以字符串为关键字的情况。（）

答案:错已知关键字序列5,8,12,19,28,20,15,22是小根堆（小顶堆），插入关键字3，调整后得到的小根堆是（）。

答案:3,5,12,8,28,20,15,22,19排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。

答案:简单选择排序###快速排序###堆排序下列排序算法中，稳定的是（）。

答案:归并排序，冒泡排序下列内部排序算法中，其比较次数与序列初态无关的算法是（）。

答案:简单选择排序###2-路归并排序已知一个长度为16的顺序表L，其元素按关键字有序排列。若采用折半查找法查找一个L中不存在的元素，则关键字的比较次数最多是（）。

答案:5在平衡二叉树中插入一个结点后造成了不平衡，需要进行平衡化旋转，调整类型有（）。

答案:RL型###LL型###LR型###RR型对于二叉排序树，下面的说法错误的是（）。

答案:二叉排序树是动态树表，查找不成功时插入新结点时，会引起树的重新分裂和组合###对二叉排序树进行层序遍历可得到有序序列###在二叉排序树中进行查找，关键字的比较次数不超过结点数的1/2对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（）。

答案:95,22,91,24,94,71对一棵二叉排序树按先序方法遍历得出的结点序列是从小到大的序列。（）

答案:错有n个数存放在一维数组A[1..n]中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同。（）

答案:错在构造哈希表方面，下面的说法正确的是（）。

答案:哈希函数选的好可减少冲突现象###在哈希表中进行查找也需要关键字的比较AVL树是一棵二叉树，该树上任一结点的平衡因子的绝对值不大于1。（）

答案:对若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为（）。

答案:(n+1)/2用线性探测再散列处理冲突时，可能出现聚集现象。下列选项中，会受聚集现象直接影响的是（）。

答案:平均查找长度

答案:1273645

答案:23

答案:3->5->4->6

答案:在十字链表中，既容易找到以顶点i为尾的弧，也容易找到以i为头的弧。（）

答案:对用普里姆(Prim)算法求一个连通图的带权图的最小生成树，在算法执行过程中，已选取的顶点集合U={A，B}，已选取的边的集合TE={（A，B）}，要选取下一条权值最小的边，应当从下列哪组中选取？（

）

答案:{（A，C），（A，E），（B，D）}

答案:邻接多重表用两个边结点表示一条边。（）

答案:错

答案:ABCDE在一个无向图中，所有顶点的度数之和等于图的边数的多少倍？（）

答案:2含有10个结点的二叉树中，度为0的结点数为4，则度为2的结点数为（）。

答案:3将一个递归算法改为对应的非递归算法时，通常需要使用队列。（）

答案:错一棵二叉树的广义表表示为a(b(c,d),e(,f(g)))，则得到的层次遍历序列为（）。

答案:abecdfg一棵有16个结点的完全二叉树，对它按层编号，则对编号为7的结点X，它的（）。

答案:左孩子编号为14###双亲编号为3设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树的结点个数为n，则森林F中第一棵树的结点个数是m-n。（）

答案:对一棵先序序列为1,2,3,4的二叉树，其中序序列可能是（）。

答案:2,4,3,1###4,3,2,1###3,4,2,1下列存储形式中，（）是树的存储形式。

答案:孩子兄弟表示法###双亲表示法###孩子表示法已知完全二叉树有80个结点，则该二叉树有（）个度为1的结点。

答案:1已知一棵完全二叉树的第5层有7个结点，则其有（）个叶子结点。

答案:11完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达。（）

答案:对广义表B=（a,(b,c,d)），则它的表尾是(）。

答案:(b,c,d)广义表A=(a,b,(c,d),(e,(f,g)))，则表达式Head(Tail(Head(Tail(Tail(A)))))的值为（）。

答案:d一个一维数组A的长度为500，起始（A[0]）地址为2000，每个元素占4个字节，则A[80]的地址是（）。

答案:2320广义表L=((a,b,c,d))的表尾是（）。

答案:()设有一个10阶的对称矩阵A，采用压缩存储，以行序为主序存储，a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。

答案:33数组A[0..4,-1..-3,5..7]中含有元素的个数为（）。

答案:45稀疏矩阵一般的压缩存储方法有（）两种。

答案:三元组和十字链表一个5*5的对称矩阵采用压缩存储，需要存储（）个元素。

答案:15对下述矩阵进行压缩存储后，失去随机存取功能是（）。

答案:稀疏矩阵设广义表L=（a,（b,c,d）），则L的长度和深度分别为（）。

答案:2和2空串与空格串（）。

答案:不相同设有两个串p和q，Concat(p,q)操作是（）。

答案:连接下列哪一个不是串的存储方法（）。

答案:十字表存储设SUBSTR（S,i,k）是求S中从第i个字符开始的连续k个字符组成的子串操作，则对于S=‘Beijing&Nanjing’，SUBSTR(S,4,5)=()。

答案:‘jing&’串中不能含有数字。（）

答案:错串是一种数据对象和操作都特殊的线性表。（）

答案:对字符串S="Todayis30July2005"，其长度是()。

答案:21两个串相等就是两个串含有相同字符。（）

答案:错若串str=“Software”，其子串的个数是（）。

答案:37循环队列也存在空间溢出问题。（）

答案:对在链队列中，即使不设置尾指针也能进行入队操作。（）

答案:对消除递归不一定需要使用栈。（）

答案:对栈和队列的存储方式都可以采用顺序方式存储。（）

答案:对向一个栈顶指针为top的链栈中插入一个S所指结点时，则执行()。

答案:S-＞next=top;top=S；若用链表来表示队列，则应该选用（）。

答案:带尾指针的循环链表若用一个大小为5的数组来实现循环队列，且当前rear和front的值分别为0和2，当从队列中删除2个元素，再加入1个元素后，rear和front的值分别为多少()。

答案:1和4设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b,d,c,f,e,a,g，则栈S的容量至少是()。

答案:3某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素a,b,c,d,e依次入此队列后再进行出队操作，则不可能得到的出队序列是()。

答案:dbcae若输入序列为1,2,3,4,5,6，则出栈序列不可能是3,2,5,6,4,1。（）

答案:错设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用()最节省时间。

答案:带头结点的双循环链表线性表是具有n个（）的有限序列（n＞0）。

答案:数据元素若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（）存储方式最节省运算时间。

答案:带头结点的双循环链表下面关于线性表的叙述中，错误的是哪一个？（）。

答案:线性表采用顺序存储，便于进行插入和删除操作下述哪一条是顺序存储结构的优点？（）。

答案:存储密度大链表不具有的特点是（）。

答案:可随机访问任一元素静态链表中指针表示的是（）。

答案:下一元素地址某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。

答案:仅有尾指针的单循环链表算法的时间复杂度取决于（）。

答案:问题的规模和待处理数据的初态数据结构的抽象操作的定义与具体实现有关。（）

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

答案:复杂性数据的逻辑关系是指数据元素的（）。

答案:关联算法和程序没有区别，所以在数据结构中二者是通用的。（）

答案:错数据结构是带有结构的数据元素的结合。（）

答案:对可以用（）定义一个完整的数据结构。

答案:抽象数据类型数据元素是数据的最小单位。（）

答案:错数据结构的基本任务是（）。

答案:数据结构的设计与实现在孩子表示法的链表中，结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。（）

答案:错在一个长度为n的顺序表中删除第i个元素时，需向前移动n+1个元素。（）

答案:错为解决某问题的算法等同于对应的程序。（）

答案:错图的邻接矩阵存储结构是唯一的。（）

答案:对遍历二叉树是以一定规则将二叉树中结点排列成一个非线性序列。（）

答案:错在堆排序中，首先要进行的操作是建堆。（）

答案:对拓扑排序实质是将非线性结构转换成线性结构。（）

答案:对在大根堆中，堆中任一结点的关键字均大于它的左、右孩子的关键字。（）

答案:对对二叉排序树的查找都是从根结点开始的，则查找失败一定落在叶子结点上。（）

答案:错二叉排序树的任意一颗子树也是二叉排序树。（）

答案:对逻辑结构不同的数据必须采用不同的存储方法来存储。（）

答案:错在平衡二叉排序树中，以每个分支结点为根的子树都是平衡的。（）

答案:对在线索二叉树中，结点的lchild域指向该结点的左孩子或者指向该结点的后继。（）

答案:错简单选择排序是不稳定排序。（）

答案:对树的带权路径长度为树中所有分支结点的带权路径长度之和。（）

答案:错在链队列做出队操作时，会改变front指针的值。（）

答案:对设有一个顺序栈S，元素A,B,C,D,E,F,依次进栈，如果六个元素出栈的顺序是B,D,C,F,E,A，则栈的容量至少应是3。（）

答案:对顺序查找只能在顺序存储结构上进行。（）

答案:错邻接表是图的一种链式存储结构。（）

答案:对构造哈希表时发生冲突，是指同一个关键字的记录对应多个不同的哈希地址。（）

答案:错线性表就是顺序表。()

答案:错顺序存储结构适用于完全二叉树。（）

答案:对数据对象是一组任意数据元素的集合。（）

答案:错一个以h为头的单循环链中，p指针指向链尾的条件是p-＞next=h。（）

答案:对深度为k的二叉树中，所含叶子的个数最多为2k-1。（）

答案:错一个含有两个或以上顶点的无向图有可能不存在生成树。（）

答案:错若数据元素序列11,12,13,7,8,9,23,4,5是某种排序方法得到的第二趟排序后的结果，则这个排序方法是插入排序。（）

答案:对若把堆看成是一棵完全二叉树，则该树一定是一棵二叉排序树。（）

答案:错线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。()

答案:对在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点。（）

答案:对在待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省。（）

答案:错赫夫曼树就是带权路径长度最小的二叉树。（）

答案:对森林可以转换为二叉树。（）

答案:对从逻辑结构上看，n维数组的每个元素均属于n个向量。（）

答案:对中序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则，中序遍历左子树，中序遍历右子树，最后访问根结点。（）

答案:错如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序方法是不稳定的。（）

答案:对折半查找适合在有序的双链表上进行。（）

答案:错无向图的连通分量是指极小连通子图。（）

答案:错强连通图可以进行拓扑排序。（）

答案:错在一个长度为n的顺序表中删除第i个元素，下列叙述正确的是（）。

答案:需向前移动n-i个元素###平均移动（n-1）/2个元素广义表((a,b),(c,d))的表尾不正确的是()。

答案:(c,d)###(d)###d排序趟数与序列的初始状态有关的排序方法有（）。

答案:冒泡排序###快速排序已知一个栈的进栈序列是a1,a2,a3…an，其输出序列为1,2,3…n，若a3=1,则a1为（）。

答案:不可能是2###可能是3以下论断错误的是()。

答案:"BEIJING"是"BEIJING"的子串###"BIT"="BITE"###"something"＜"Somethig"可以判断一个有向图中含有回路的方法是（）。

答案:深度优先遍历###拓扑排序已知广义表LS＝((a,b,c),(d,e,f))，运用head和tail函数取出LS中原子e，以下()操作不能完成上述运算。

答案:head(tail(tail(head(LS))))###head(tail(LS))###tail(head(LS))有5个结点的二叉树，可能有（）个叶子结点。

答案:2###1###3设循环队列中数组的下标范围是１～ｎ，其头尾指针分别为ｆ和ｒ，则其元素个数不可能是（）。

答案:(r-f)mod(n+1)###r-f+1###r-f下面（）属于特殊矩阵。

答案:对称矩阵###对角矩阵###上三角矩阵###下三角矩阵设二叉排序树中关键字由1到1000的整数构成，现要查找关键字为363的结点，下述关键字序列中，在二叉排序树上查找的可能序列是（）。

答案:2,399,387,219,266,382,381,278,363###2,252,401,398,330,344,397,363###924,220,911,244,898,258,363若一个栈以数组V[1..n]存储，初始栈顶指针top设为n+1，元素x进栈，以下操作错误的是（）。

答案:V[top]=x;top++###V[top]=x;top--###top++;V[top]=x下列关于图的深度优先搜索遍历序列的说法，正确的是（）。

答案:图的深度优先搜索遍历序列可以唯一###图的深度优先搜索遍历序列可以不唯一有关希尔排序叙述正确的是（）。

答案:子序列中进行直接插入排序###相隔某个“增量“的记录分成一个子序列###缩小增量排序###每趟排序时，子序列中的记录跳跃式移动现在有一棵无重复关键字的平衡二叉树（AVL树），对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是（）。

答案:树中最小元素一定是无右子树###树中最大元素一定是无左子树二叉树由3个基本单元组成（）。

答案:左子树###右子树###根结点循环队列存储在数组A[0..m]中，以下不是入队时的队尾指针操作为（）。

答案:rear=rear+1###rear=(rear+1)%m###rear=(rear+1)%(m-1)

答案:4###5假定一棵树的广义表表示法为A(B,C(E,F,G),H(I,J))，则度为3的结点有（）。

答案:结点A###结点C树是n个结点的有穷集合，以下说法错误的有（）。

答案:树至少含有一个根结点和一个叶子结点###树至少含有一个根结点和两个叶子结点###树至少含有一个根结点，不能为空查找表是一种非常灵活的数据结构，对它经常进行的操作有（）。

答案:查询某个“特定的“数据元素是否在查找表中###在查找表中插入一个数据元素###从查找表中删去某个数据元素###检索某个“特定的“数据元素的各种属性除了需要存放数据元素本身的数据信息以外，还需要占用存储空间存储数据元素之间逻辑关系信息的存储方式是（）。

答案:动态链表###静态链表###循环链表下面关于无向图的连通分量说法正确的是（）。

答案:连通分量是原图的子图###无向图中的极大连通子图称为图的连通分量。###连通分量已经是最大，不能再大，再大要么不是原图的子图，要么不连通###连通分量是连通图为提高哈希表的查找效率，可以采取的正确措施有（）。

答案:处理冲突时避免产生聚集现象###设计冲突少的哈希函数线性表有顺序表和链表两种存储结构，下列排序方法适合顺序表的有（）。

答案:希尔排序###快速排序###堆排序有n(n＞100)个十进制正整数进行基数排序，其中最大的整数为5位，则基数排序过程中临时建立的队列个数不可能是（）。

答案:5###50###n若表R的初始数据接近正序排列，则（）方法的比较次数最少。

答案:直接插入排序线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（）。

答案:O(n)在决定选取何种存储结构时，一般不考虑（）。

答案:各结点的值如何在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（）。

答案:s-＞next=p-＞next;p-＞next=s;对数据序列（15,9,7,8,20,-1,4）进行排序，一趟后的数据排序变为（4,9,-1,8,20,7,15），则采用的是（）。

答案:希尔排序设有一稀疏图G，则G采用（）存储方式存储较省空间。

答案:邻接表算