数据结构智慧树知到期末考试答案章节答案2024年上海海洋大学

数据结构智慧树知到期末考试答案+章节答案2024年上海海洋大学堆是完全二叉树，完全二叉树不一定是堆。（）

答案:对快速排序是排序算法中平均性能最好的一种排序。（）

答案:对如果两个关键字的值不等但哈希函数值相等，则称这两个关键字为同义词。（）

答案:对非空的双向循环链表中任何结点的前驱指针均不为空。（）

答案:对设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为O(log2n)。（）

答案:对设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。（）

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

答案:错不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。（）

答案:对设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（）。

答案:q=p->next；p->data=q->data；p->next=q->next；free(q)；对一棵二叉搜索树进行（）遍历时，得到的结点序列是一个有序序列。

答案:中序（）是有独立含义的最小单位，

答案:数据项在一个具有n个单元的顺序栈中，假定用top==n表示栈空，则向这个栈插入一个元素时，首先应执行（）语句修改top指针。

答案:top--假定一棵三叉树的结点数为50，则它的最小高度为（）。

答案:5在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为（）。

答案:rear==front数组就是矩阵，矩阵就是数组，这种说法（）。

答案:错误设散列空间为０到ｍ－１，ｋ为表项的关键码，散列函数采用除留余数法，即Hash（k）=k%p。为了减少发生冲突的频率，一般取p为（）。

答案:小于m的最大质数在闭散列表中，散列到同一个地址而引起的“堆积”问题是由于（）引起的。

答案:同义词或非同义词之间发生冲突。在一个具有n个顶点和e条边的有向图的邻接表中，保存顶点单链表的表头指针向量的大小至少为（）。

答案:n我们用一个有向图来表示航空公司所有航班的航线。下列哪种算法最适合解决找给定两城市间最经济的飞行路线问题？（）

答案:Dijkstra算法设单链表中结点的结构为（data,link），单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为（）。

答案:p->Link=m->Link->Link;下面程序的时间复杂为（）for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；}

答案:O(n2)假定对长度n=50的有序表进行折半查找，则对应的树高度为（）。

答案:6设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（）。

答案:O(n+e)用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R[1..n]，结点R[i]若有左孩子，其左孩子的编号为结点（）。

答案:R[2i]设用链表作为栈的存储结构，退栈操作（）。

答案:必须判别栈是否为空设某哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。

答案:100数据结构形式地定义为（D,S），其中D是数据元素的有限集合，S是D上的（）的有限集合。

答案:关系对一个长度为10的排好序的表用二分法查找，若查找不成功，至少需要比较的次数是（）。

答案:3一个子串在包含它的主串中的位置，它是指（）。

答案:子串的第一个字符在主串中首次出现的位置对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为（）。

答案:1从具有n个结点的二叉搜索树中查找一个元素时，在最坏情况下的时间复杂度为（）。

答案:O(n)栈的插入和删除操作在（）进行。

答案:栈顶使用二路归并排序对含n个元素的数组M进行排序时，二路归并操作的功能是：（）

答案:将两个有序表合并为一个新的有序表设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为（）。

答案:N1-1树最适合用来表示（）。

答案:元素之间具有分支层次关系的数据一个子串在包含它的主串中的位置是指（）。

答案:子串的第一个字符在主串中首次出现的位置栈和队列的共同特点是（）。

答案:只允许在端点处插入和删除元素在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行（）。

答案:p->next=HL->next;HL->next=p;中序遍历一棵二叉排序树可以得到一个有序的序列。（）

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

答案:对子串“ABC”在主串“AABCABCD”中的位置为2。（）

答案:对层次遍历初始堆可以得到一个有序的序列。（）

答案:错图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问过。（）

答案:对线性表中的所有元素都有一个前驱元素和后继元素。（）

答案:错有向图的邻接表和逆邻接表中表结点的个数不一定相等。（）

答案:错在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是（）。

答案:O(n)一棵平衡二叉搜索树中，每个结点的左子树高度与右子树高度之差的绝对值不超过（）。

答案:1采用开散列法解决冲突时，每一个散列地址所链接的同义词表中各个表项的（）相同。

答案:散列地址设有一个已排序的线性表（长度>=２），分别用顺序查找法和二分查找法找一个与K相等的元素，比较的次数分别是S和B，在查找不成功的情况下，S和B的关系是（）。

答案:S>=B在一棵高度平衡二叉搜索树中，每个结点的平衡因子的取值范围是（）。

答案:-11（）排序方法能够每次使无序表中的第一个记录插入到有序表中。

答案:直接插入设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（）。

答案:任一结点无右孩子稀疏矩阵可以采用（）的压缩存储方法。

答案:三元组设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（）。

答案:rear->next=s；rear=s；对于顺序存储的线性表，其算法的时间复杂度为O(1)的运算应是（）。

答案:查找第i个元素（1≤i≤n）在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（）个。

答案:6非空的循环单链表first的尾结点（由p所指向）满足：（）

答案:p->link==first；假定一个顺序表的长度为40，并假定查找每个元素的概率都相同，则在查找不成功情况下的平均查找长度（）。

答案:41由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。

答案:53设二维数组A[0…m-1][0…n-1]按行优先顺序存储在内存中，第一个元素的地址为p，每个元素占k个字节，则元素aij的地址为（）。

答案:p+[i*n+j]*k设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为（）。

答案:10，15，14，18，20，36，40，21设有广义表D=(a,b,D)，其深度为（）。

答案:无穷大假定一组记录为(46,74,53,14,26,38,86,65,27,34)，对其进行希尔排序，第一趟间隔为3，得到的排序结果为（）。

答案:14,26,27,34,65,38,46,74,53,86（）由某一数据元素的集合以及该集合中所有数据元素之间的关系组成。

答案:数据结构（）中的各个数据成员不在一个线性序列中，数据元素成员可能与零个或多个其他数据成员发生联系。

答案:非线性结构采用邻接表存储的图的深度优先遍历算法类似于二叉树的（）。

答案:前序遍历设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（）。

答案:O(n)

答案:(5,6)(4,6)(1,3)(1,2)(3,5)一个算法的时间复杂度为（3n2+2nlog2n+4n-7）/（5n），其数量级表示为：（）

答案:O（n）在解决散列法中出现的冲突问题常采用的方法是（）。

答案:线性探查法、双散列法、开散列法。（）排序方法采用的是二分法的思想。

答案:快速

答案:2,4,3,6,5,7下列广义表用链表来表示时，分支结点最多的是（）。

答案:L=((x,(a,B)),(x,(a,B),y))假定一个初始堆为(1,5,3,9,12,7,15,10)，欲把这组数从大到小排序，采用最小堆，则进行第一趟堆排序后得到的结果为（）。

答案:A.3,5,7,9,12,10,15,1在（）中的各个数据成员依次排列在一个线性序列中。

答案:线性结构设单链表中结点的结构为（data,link），单链表中指针p所指结点不是尾结点，若在*p之后插入结点*s，应执行（）操作。

答案:s->Link=p->Link;p->Link=s；线索二叉树是一种（）结构。

答案:物理（）排序方法能够每次从无序表中顺序查找出一个最小值。

答案:直接选择若一棵二叉树的前序遍历序列是{4,2,1,3,6,5,7}，中序遍历序列是{1,2,3,4,5,6,7}，则下列哪句是错的？（）

答案:6是3的父结点

答案:O（m*n）一个广义表的表尾总是一个（）。

答案:广义表对于长度为9的顺序存储的有序表，若采用折半查找，在等概率情况下的平均查找长度为（）的9分之一。

答案:25设数组S[]={93,946,372,9,146,151,301,485,236,327,43,892}，采用最低位优先（LSD）基数排序将S排列成升序序列。第1趟分配、收集后，元素372之前、之后紧邻的元素分别是：（）

答案:301，892平均时间复杂度为O(nlogn)且稳定的排序算法是（）。

答案:归并排序下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(NlogN)的是：（）

答案:堆排序将序列{2,12,16,88,5,10,34}排序。若前2趟排序的结果如下：第1趟排序后：2,12,16,10,5,34,88第2趟排序后：2,5,10,12,16,34,88则可能的排序算法是：（）

答案:快速排序解决散列法中出现的冲突问题常采用的方法是（）。

答案:线性探查法、双散列法、开散列法。在一棵平衡二叉搜索树中，每个结点的左子树高度与右子树高度之差的绝对值不超过（）。

答案:1用二分查找从100个有序整数中查找某数，最坏情况下需要比较的次数是：（）

答案:7已知线性表的关键字集合{21，11，13，25，48，6，39，83，30，96，108}，散列函数为h(key)=key%11，采用分离链接法解决冲突。则成功查找的平均查找长度为（）

答案:1.36若根据关键码建立长度为m的散列表，采用线性探测法处理冲突，假定对一个元素第一次计算的散列地址为d，则下一次的哈希地址为（）。

答案:(d+1)%m

答案:12和14若使用AOE网估算工程进度，则下列叙述中正确的是：（）

答案:关键路径是从源点到汇点路径长度最长的路径设有6个结点的无向图，该图至少应有（）条边才能确保是一个连通图。

答案:5

答案:abdfce

答案:(b,f),(b,d),(a,e),(c,e),(b,e)

答案:CDABEHFG对于无向图G=(V,E),下列选项中，正确的是：（）

答案:当∣V∣>∣E∣+1时，G一定是不连通的10.设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有（）个结点。

答案:2n-1线索二叉树中，结点p没有左子树的充要条件是（）。

答案:p->ltag=1设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（）。

答案:229两个字符串相等的充要条件是（）。

答案:同时具备(A)和(B)两个条件广义表A=((x,(a,B)),(x,(a,B),y))，则运算head(head(tail(A)))的结果为（）。

答案:x设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？（）脚注(10)表示用10进制表示。

答案:692在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。

答案:列号在一个链式队列中，假定front和rear分别为队头和队尾指针，则删除一个结点的操作为（）。

答案:front=front->next设用链表作为栈的存储结构则退栈操作（）。

答案:必须判别栈是否为空一个栈的输入序列为123，则下列序列中不可能是栈的输出序列的是（）

答案:312向一个栈顶指针为top的链式栈中插入一个s结点时，应执行（）。

答案:s->link=top;top=s;设单链表中结点的结构为（data,link），若要删除单链表中指针p指向结点的后一个结点（若存在），