算法与数据结构智慧树知到期末考试答案章节答案2024年兰州理工大学

算法与数据结构智慧树知到期末考试答案+章节答案2024年兰州理工大学满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（

）

答案:对.树中的结点和图中的顶点就是指数据结构中的数据元素。（

）

答案:对在图G的最小生成树G1中，可能会有某条边的权值超过未选边的权值。（

）

答案:对静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。（

）

答案:对入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。(

)

答案:对用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。（

）

答案:错邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形

式来存储它。（

）

答案:错用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，

而与图的边数无关。（

）

答案:对设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。（

）

答案:对设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（

）

答案:错图中有关路径的定义是（

）。

答案:由顶点和相邻顶点序偶构成的边所形成的序列在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（

）。

答案:G中有一条从Vj到Vi的路径分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是(

)。

答案:（100，60，

80，

90，

120，110，130）关键路径是事件结点网络中（

）。

答案:从源点到汇点的最长路径算法分析的主要任务是分析（

）

答案:算法的执行时间和问题规模之间的关系无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍

历，得到的顶点序列正确的是（

）。

答案:a,e,d,f,c,b下面关于算法说法错误的是（

）。

答案:都是错误的数据的最小单位是（

）

答案:数据项在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1,则应作哪种类型的调整以使其平衡（

）。

答案:RL在图采用邻接矩阵存储时，求最小生成树的

Prim

算法的时间复杂度为(

)。

答案:O(n2)设某哈夫曼树中有199个结点，则该哈夫曼树中有多少个叶子结点（

）。

答案:100设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（

）。

答案:n+1-in个结点的完全有向图含有边的数目（

）。

答案:n*（n－l）设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（

）。

答案:head==0对序列(15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为(4，9，-1,

8，20，7，15)，则采用的排序方法是(

)。

答案:希尔排序设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有多少个空指针域（

）。

答案:2m下列程序的时间复杂度为（

）。

i=1；k=100；

while（i答案:O（n）下列关于AOE网的叙述中，不正确的是（

）。

答案:任何一个关键活动提前完成，那么整个工程将会提前完成完全二叉树中的叶子结点只可能在最后两层中出现。（

）

答案:对静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。（

）

答案:对强连通图的各顶点间均可达。（

）

答案:对负载因子

(装填因子)是散列表的一个重要参数，它反映散列表的装满程度。（

）

答案:对线性表的顺序存储结构比链式存储结构更好。（

）

答案:错算法的优劣与算法描述语言无关，但与所用计算机有关。（

）

答案:错拓扑排序算法把一个无向图中的顶点排成一个有序序列。（

）

答案:错一个树的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。（

）

答案:对需要借助于一个队列来实现DFS算法。（

）

答案:错每次把待排序的元素划分为左、右两个子区间，其中左区间中元素的关键字均小于等于基准元素的关键字，右区间中元素的关键字均大于等于基准元素的关键字，则此排序方法叫做(

)。

答案:快速排序若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构（

）。

答案:顺序存储结构占用的额外空间的空间复杂度为0(1)的是哪种算法（

）。

答案:堆排序设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（

）。

答案:s->left=p；s->right=p->right；p->right->left=s；

p->right=s；设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（

）。

答案:空或只有一个结点一组记录的关键字为(45，80，55，40，42，85)，则利用快速排序的方法，以第一个记录为基准得到一次划分结果是(

)。

答案:(42，40，45，55，80，85)设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为（

）。

答案:N1-1下面关于哈希(Hash，杂凑)查找的说法正确的是(

)。

答案:不存在特别好与坏的哈希函数，要视情况而定设有一个二维数组A[m][n]，假设A[0][0]存放位置在644，A[2][2]存放位置在676，每个元素占一个空间，问A[3][3]存放在什么位置（

）。

答案:692n个结点的线索二叉树上含有的线索数为（

）

答案:n＋l线性表（

a1,a2,⋯,an）以链接方式存储时，访问第i位置元素的时间复杂性为（

）。

答案:O（n）栈和队列的共同特点是(

)。

答案:只允许在端点处插入和删除元素一组记录的关键字为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果为(

)。

答案:15，25，35，50，20，40，80，85，36，70设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为（

）。

答案:q->next=s；

s->next=p；散列函数有一个共同的性质，即函数值应当以什么概率取其值域的每个值（

）。

答案:同等概率从逻辑上可以把数据结构分为哪两大类（

）

答案:线性结构、非线性结构若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为多少

(1<=i<=n+1)

（

）。

答案:O(n)将两个各有n个元素的有序表归并成一个有序表，其最多的比较次数是(

)。

答案:2n-1当一棵具有n个叶子结点的二叉树的WPL值为最小时，称其树为Huffman树，且其二叉树的形状必是唯一的。（

）

答案:错一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。（

）

答案:错有n个顶点的无向图,

采用邻接矩阵表示,

图中的边数等于邻接矩阵中非零元素之和的一半。（

）

答案:对散列法的平均检索长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。（

）

答案:对若散列表的负载因子α<1，则可避免碰撞的产生。（

）

答案:错计算机中的查找方法是与数据的组织方式有着密切的关系。（

）

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

）

答案:对连通分量指的是有向图中的极大连通子图。（

）

答案:错Hash表的平均查找长度与处理冲突的方法无关。（

）

答案:错无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（

）

答案:错哈希函数的选取平方取中法最好。（

）

答案:错在散列检索中，“比较”操作一般也是不可避免的。（

）

答案:对二维数组和多维数组均不是特殊的线性结构。（

）

答案:错二分查找的前提是线性表有序。（

）

答案:对对链表进行插入和删除操作时不必移动链表中结点。(

)

答案:对在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面。（

）

答案:错算法既独立于数据的存储，又与数据的存储有一定的联系。（

）

答案:对只要算法是正确的，就一定会得到问题的解。（

）

答案:错栈和队列都是限制存取点的线性结构。（

）

答案:对若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。（

）

答案:对如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用哪种查找法（

）。

答案:分快查找数据序列(8，9，10，4，5，6，20，1，2)只能是下列哪种排序算法中的两趟排序后的结果（

）。

答案:直接插入排序设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（

）。

答案:BADC一棵完全二叉树上有1001个结点，其中叶子结点的个数是（

）。

答案:都不对一个排序算法的时间复杂度与(

)有关。

答案:所需比较关键字的次数某堆栈的输入序列为a,

b，c

，d,下面的四个序列中，不可能是它的输出序列的是（

）。

答案:d,

c，a，b设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（

）。

答案:45设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n(n+1)/2]中，对上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置为(

)。

答案:j(j-l)/2+i数组A[0..4,-1..-3,5..7]中含有元素的个数（

）。

答案:45折半查找的时间复杂性为（

）

答案:O（logn）建立一个长度为n的有序单链表的时间复杂度为（

）。

答案:O(n2)若待排序的元素基本有序，则下列排序中平均速度最快的是(

)。

答案:直接插入排序二叉查找树的查找效率与二叉树的什么有关（

）。

答案:树型一个n个顶点的连通无向图，其边的个数至少为（

）。

答案:n-1有一组关键字序列(15，9，7，8，20，-1，7，4)，用堆排序的筛选方法建立的初始堆为(

)。

答案:-1，4，7，8，20，15，7，9设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（

）。

答案:O(1)在下列排序算法中，什么算法的效率与待排数据的原始状态无关（

）。

答案:基数排序10个顶点的连通图的深度优先生成树的边数为（

）。

答案:9若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为

(

)

。

答案:2和4设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用哪种存储结构最节省时间（

）

答案:带头结点的双循环链表下面哪一方法可以判断出一个有向图是否有环（回路）（

）。

答案:拓扑排序将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度（

）

答案:6假定N为待查找的数据元素数，查找功时二分法查找的平均比较次数为（

）。

答案:log2N在下列算法中，哪种算法可能会出现下列情况：初始数据有序时，花费的时间反而最多（

）。

答案:快速排序设计一个判别表达式中左，右括号是否配对出现的算法，采用哪种数据结构最佳（

）。

答案:栈在待排序文件已基本有序的前提下，下述排序方法中效率最高的是(

)。

答案:快速排序当采用分快查找时，数据的组织方式为

(

)。

答案:数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块一组关键字序列(49，38，65，97，76，25，43)，采用快速排序方法进行排序(用第一关键字作界值)得到的第一趟的结果为(

)。

答案:(43，38，25。49，76，97，65)二叉查找树在什么状态下时其查找效率最低（

）。

答案:呈单枝树将一个幻方的求解问题交由计算机来进行，就要关注哪两个方面（

）。

答案:选择合适的数据结构及设计求解算法设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（

）。

答案:rear->next=s；rear=s；栈可以应用在哪里（

）。

答案:A，Ｂ，Ｃ设无向图的顶点个数为n，则该图最多有多少条边（

）。

答案:n(n-1)/2设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（

）。

答案:top=top->next;假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测(

)

。

答案:k（k+1）/2次一组关键字序列为：265

301

751

129

628

863

742

694

706

438，经过多少趟直接插入排序后可得到如下序列：129

265

301

751

628

863

742

694

706

438（

）。

答案:3设一棵二叉树的深度为k，则该二叉树中最多的结点个数为（

）。

答案:2k-1设某棵三叉树中有40个结点，则该三叉树的最小高度为（

）。

答案:4求解最短路径的Floyd算法的时间复杂度为(

)。

答案:O（n*n*n）在直接选择排序中，记录比较次数为什么数量级（

）。

答案:O(n2)将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数为(

)。

答案:n设有一个小顶堆，其元素个数为n，顺序存储在数组A[1…n]中，则其具有最大值的元素可能在(

)位置。

答案:A[(n+1)/2...n]对整数序列(179，208，93，306，55，859，984，9，271，33)使用基数排序，一趟分配收集之后的结果是(

)。

答案:（271，93，33，984，55，306，208，179，859，9)对序列（15，9，7，8．20，-1，4）)进行排序，进行二趟后数据的排列变为{7，9，15，

8，20，-1，4}，则采用的排序方法是(

)。

答案:直接插入排序对一组数据(84，47，25，15，21)排序，数据的排序次序在排序的过程中的变化为：84

47

25

15

21，15

47

25

84

21，15

21

25

84

47，15

21

25

47

84，则采用的排序方法是(

)。

答案:简单选择排序有些排序算法在每趟排序过程中，都会有一个元素被放置在其最终的位置上，下列情况不会出现在(

)排序算法中。

答案:希尔排序若用冒泡排序方法对序列（10，14，26，29，41，52）从大到小排序，需进行(

)次比较。

答案:15设有关键字初始序列(Q，H，C，Y，P，A，M，S，R，D，F，X)，新序列(F，H，C，D，P，A，M，Q，R，S，Y，X}是采用(

)方法对初始序列进行第一趟扫描的结果。

答案:以第一元素为界值元素的快速排序对于长度为n的有序表，二分查找算法的时间复杂度为O(log2n)（

）

答案:对常见的散列函数的有（

）

答案:除基取余法###平方取中法###舍入乘法散列过程中，可以安全的避免冲突就必须满足哪些条件（

）

答案:选择合适的散列函数。###|U|≤m；拉链法中，同义词结点通常链接成一个单链表，链表的头指针被放置于散列表T[0..m-1]中。（

）

答案:对贪婪算法的特点。（

）

答案:贪婪策略主张所做的选择在当时是最好的选择。###这种策略通常是不能保证找到所求解问题的全局最优解。###可以得到局部最优解。###在算法的每一步，必须做出若干可能的选择中的一个。当图是稠密图时，即边数|E|很接近顶点的平方|V|2。（

）

答案:对在拓扑排序过程中，要利用一个辅助的数据结构来进行排序，这个结构是什么（

）

答案:队列如果一个有向图中，任意两个顶点之间都有有向路径相通，那么这个有向图就是强连通的。（

）

答案:对将n个顶点连在一起最多需要n-2条边。（

）

答案:错对图的每一个顶点访问一次且只访问一次的过程称为图的遍历。（

）

答案:对生成树就是将n个顶点连接在一起，且无环的一棵树。（

）

答案:对一个具有1025个结点的二叉树的高h为（

）

答案:11至1025之间完全二叉树一定存在度为1的结点。（

）

答案:错下面几个符号串编码集合中，不是前缀编码的是（

）。

答案:{11,10,001,101,0001}设树T的度为4，其中度为1、2、3和4的结点个数分别为4,2,1,1，则T中的叶子结点数为

（

）

答案:8某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E

则前序序列是（

）

答案:E,A,C,B,D,G,F深度为h的满m叉树的第k层的结点结点个数有多少，(1=答案:mk-1按二叉树的定义，具有3个结点的二叉树有几种（

）

答案:5稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。（

）

答案:对数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是(

)。

答案:1175设二维数组A[1..

m，1..

n]（即m行n列）按行存储在数组B[1..

m*n]中，则二维数组元素A[i，j]在一维数组B中的下标为(

)。

答案:（i-1）*n+j将一个A[1..100，1..100]的三对角矩阵，按行