超星尔雅数据结构与算法答案,超星尔雅数据库及应用答案

数据结构与算法-进阶（十九）分治

分治，可以理解为分而治之，核心逻辑就是将原问题分解成若干个小问题，原问题和小问题在结构上是一致的，唯一的区别就是规模不同。然后再将小问题分解出更小的问题，直到无法再分解为止，也就是可以直接或者简单的计算得出问题的答案。最后利用小问题推导出原问题的解。

这个和 递归的思想类似 ，所以分治策略非常适合使用递归来处理，需要特别注意的是，分治策略中的子问题都是相互独立的。

可以应用到分治策略的有快速排序、归并排序和大数乘法等。

分治策略通常遵循这样的通用模式，解决规模为 n 的问题，就分解成 a 个规模为 frac{n}{b} 的子问题，然后在 O(n^d) 时间内将子问题的解给合并起来。

总结下来，算法运算的时间 T(n) = aT(frac{n}{b}) + O(n^d)，a 0，b 1，d geq 0。 继续简化运算时间的公式，有以下三个公式：

接下来通过求最大连续子序列和来进一步了解下分治策略。

当给定一个长度为 n 的整数序列，求它的最大连续子序列和，比如整数序列为 -2、1、-3、4、-1、2、1、-5、4，那么这个整数序列的最大连续子序列和是 4 + (-1) + 2 + 1 = 6。

那么最简单的实现，就是暴力求解，找出所有连续子序列的和，比较出最大的那个。如下代码所示，用三个 for 循环来找出所有的连续子序列，并比较出最大值。

看上面的代码，可以计算出空间复杂度是 O(1)，时间复杂度是 O(n^3)。函数中可以继续优化，重复使用前面计算出的 sum 值，代码如下所示：

优化后的函数，它的空间复杂度是 O(n)，时间复杂度减少为 O(n^2)。

现在用分治策略来求最大子序列和。先将序列均匀的分割成两个子序列 [begin, end) = [begin, mid) + [mid, end)，mid = (begin + end) 1。

假设 [begin, end) 的最大子序列是 S[i, j)，那么它就有三种可能情况：

当出现第3种情况时，继续往下分析：

所以用代码实现时，就是将这三种情况都给求解出来，然后比较这3种情况的解，其中最大的就是这个序列的连续子序列和。

先创建一个对外调用的函数，设置 nums 数组异常的处理，如下代码所示：

然后创建一个求连续子序列和的函数，传入 nums 的同时，也要传入 begin 和 end，在这个函数中要实现 S[i, j) 的三种情况，第一种情况用 maxSubArray(nums, begin, mid) 处理，第二种情况用 maxSubArray(nums, mid, end) 来处理。这种处理方式就是递归思想。

最后处理第三种情况，那么就要分别求解出 [i, mid) 和 [mid, j）中的连续子序列和，因为第三种情况是分布在 mid 左右，并且是连续的，所以这种情况的连续子序列的和就是 leftMax + rightMax。如下代码所示：

函数中最后的 return 后的代码就是比较这三种情况，并返回其中最大的值。因为是递归的方式，所以函数中一定要有结束递归的条件，if (end - begin 2) return nums[begin]; 就是递归基。

通过分治策略求连续最大子序列和的空间复杂度是 O(logn)，时间复杂度是 O(nlogn)，低于暴力求解的复杂度。

19年3月二级C--数据结构与算法

1.假设线性表的长度为n，则最坏情况下:

冒泡排序: 需要经过n/2遍的从前往后扫描和n/2遍从后往前扫描，需要比较的次数为n(n-1)/2。总的时间复杂度为O(n的平方)。

快速排序: 比较次数也是n(n-1)/2。总的时间复杂度为O(n的平方)。

直接插入排序: 所需要比较的次数为n(n-1)/2。总的时间复杂度为O(n的平方)。

希尔排序所需要比较的次数为O(n的1.5次方)。(时间复杂度小于以上三种)

堆排序: 最坏情况下，其时间复杂度为O(nlogn)。(小于O(n的平方))。

2.根据数据结构中各元素之间前后关系的复杂程度，一般数据结构分为两大类: 线性结构和非线性结构。

如果一个非空的数据结构满足下列两个条件，①有且只有一个根结点 ②每个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构，又称线性表。

3.算法时间复杂度与空间复杂度没有关系。

4.所谓算法的时间复杂度，是指执行算法所需要的计算工作量。

为了能够比较客观的反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所用的计算机程序设计语言，以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。

5.同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。

算法分析的目的在于选择合适算法和改进算法。

6.堆排序在平均情况下的时间复杂度与最坏情况下的时间复杂度都是O(nlogn)。

7.二叉链表: 以二叉链表作为树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和第一个孩子下的一个兄弟结点。

? 循环链表是链式存储结构，循环队列是线性存储结构。( 【×】循环链表是循环队列的链式存储结构)

? 双向链表也叫双链表，是链表的一种，它的每个数据结点都有两个指针，分别指向直接后继和直接前驱，所以从双链表中的任意一个结点开始都可以很方便地访问它的前驱结点和后继结点。

8.数据的逻辑结构由两个要素: 一是数据元素的集合，通常记为D。二是D上的关系，它反映了D中各元素之间的前后件关系，通常记为R。

即一个数据结构可以表示成B=(D,R)，其中B表示数据结构，为了反映D中各元素之间的前后件关系，一般用二元组来表示。例如，假如a与b是D中的两个数据，则二元组表示a是b的前件，b是a的后件。

? 线性结构用图形表示更加直观。例如: R=｛(5,1)，(7,9)，(1,7)，(9,3)｝，结构为: 5→1→7→9→3

9.快速排序法是一种互换类的排序方法，但由于比冒泡排序的速度快，因此称为快速排序。

其基本思想是从线性表中选择一个元素设为t，将线性表后面小于t的元素移到前面，而前面大于t的元素移到后面，结果就将线性表分成了两部分，t插入到分界线的位置处，这个过程称为线性表的分割。

? 简单插入排序法，是指将无序序列中的各元素依次插入到已经有序的线性表中。

? 冒泡排序法是一种最简单的交换类排序方法，它是通过相邻数据元素的交换，逐步将线性表变为有序。

? 后两种元素的移动过程中不会产生新的逆序。

10.程序可作为算法的一种描述。

11.为了降低算法的空间复杂度，要求算法尽量采用原地工作，所谓的原地工作是指执行算法时所使用的额外空间固定。

? 一个算法的空间复杂度一般是指执行这个算法所需要的内存空间，一个算法所占用的存储空间包括程序所占的空间，输入的初始数据所占的空间以及算法执行过程中所需要的额外空间。

12.能从任意一个结点开始没有重复的扫描到所有结点的数据结构是循环链表。

13.循环队列是队列的一种存储结构

14.算法的设计要求包括效率与低存储量，即要考虑算法的时间复杂度与空间复杂度。

? 算法的复杂度包括时间复杂度和空间复杂度。

? 时间复杂度: 是指执行算法所需要的计算工作量。

? 空间复杂度: 一般是指执行这个算法所需要的内存空间。

15.栈是一种特殊的线性表。链式结构把每一个存储结点分为数据域与指针域，带链的栈可以通过指针域的变化改变原有的栈的组织数据原则; 而顺序栈的栈底指针不变，栈顶指针改变。

16.堆排序在最坏的情况下需要比较nlogn次。

? 快速排序，在最坏情况下需要比较n(n-1)/2次。

? 顺序查找，在最坏情况下需要比较n次。

? 最坏情况下，二分查找需要log2n(小于n-1)

? 在长度为n的顺序表中寻找最大项/最小项时，比较次数最少为1，最多为n-1。

17.如果一个非空的数据结构满足下列两个条件，①有且只有一个根节点 ②每一个结点最多有一个前件，也最多有一个后件，则称该数据结构为线性结构。如果一个数据结构不是线性结构，则称为非线性结构。

18.带链栈空的条件是 top=bottom=NULL

19.满二叉树也是完全二叉树，完全二叉树不一定是满二叉树。对于满二叉树和完全二叉树来说，可以按照程序进行顺序存储，不仅节省了空间，又能方便地确定每一个结点的父结点等于左右子结点的位置，但顺序存储结构对于一般的二叉树不适用。

20.带链栈队头指针与队尾指针相同，且不为空时，队列元素个数为1; 若为空时，队列元素个数为0。

带链栈的栈底指针是随栈的操作而动态变化的。

21.二叉树的链式存储结构，也称为二叉链表。在二叉树中，由于每一个元素可以有两个后件，因此用于存储二叉树的存储结点的指针域有两个，所以二叉链表属于非线性结构。

22.线性表由一组元素数据元素构成，各元素的数据类型必须相同，矩阵是一个比较复杂的线性表，线性表除了插入和删除运算之外，还可以查找，排序，分解，合并等。数组是长度固定的线性表。

23.冒泡排序中，在互换两个相邻元素时，只能消除一个逆序; 快速排序及希尔排序中，一次交换可以消除多个逆序。

24.二分法检索的效率比较高，设线性表有n个元素，则最多的比较次数为log2n，最少检索次数为1。

25.循环链表的结构具有以下两个特点。一，在循环链表中，增加了一个表头结点，其数据域为任意或者根据需要来设置指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。二、循环链表中最后一个节点的指针域不是空，而是指向表头结点，即在循环链表中所有的结点指针构成一个环状链。

26.二叉树的存储结构是非线性结构，而完全二叉树是特殊形态的二叉树。采用顺序存储的完全二叉树属于非线性结构。

27.时间复杂度和计算机运行速度以及存储空间无关。

算法的空间复杂度和存储结构无关。

数据处理效率与数据的存储结构有关。

28.线性表，向量，栈，队列都属于线性结构的顺序存储。

29.循环队列是队列的存储结构。

? 循环链表是另一种形式的念式存储结构。

? (?循环链表是循环队列的链式存储结构。?)

30.完全二叉树的总结点为奇数时，叶子结点是总结点加一再除以二。

31.在实际处理中，可以用一位数组来存储堆序列中的元素，也可以用完全二叉树来直观的表示堆的结构。在用完全二叉树表示堆时，树中所有非叶子结点值均不小于其左，右子树的根结点值，因为堆顶元素必须为序列的n个元素的最大项，因此其中序并不是有序序列。

? 多重链表指表中每个结点由两个或两个以上的指针域的链表。如果一个非空的数据结构满足下列两个条件，①有且只有一个根结点，②每个结点最多有一个前件，也最多有一个后件，则称该数据结构为线性结构，所以多重链表不一定是非线性结构。

? 在计算机中二叉树通常采用链式存储结构，对于满二叉树和完全二叉树来说，可以按层次进行顺序存储。

? 排序二叉树的中序遍历序列是有序序列。

32.对于一个固定的规模，算法所执行的基本运算次数还可能与特定的输入有关。

33.在线性表中寻找最大项时，平均情况下和最坏情况下比较次数都是n-1。

34.在长度为n的顺序表中查找一 个元素， 假没需要查找的元素有一半的机会在表中，并且如果元素在表中，则出现在表中每个位置上的可能性是相

同的。则在平均情况下需要比较的次数大约为_

A.3n/4? ? B.n? ? C.n/2? D.n/4

本题的考查知识点是顺序表的存储结构。

因为需要查找的元素有一半机会在表中，所以二分之一的情况下平均比较次数为n/2，另二分之一的情况下平均比较次数为n。总的平均比较次数为(n/2+n) /2-3n/4。

故本题答案为A。

35.设数据结构B=(D, R)，其中

D={a,b,c,d，e，f}

R={(a，b)，(b，c)，(c，d)，(d，e)，(e，f)，(f,a)}该数据结构为

A.线性结构? ? B.循环队列

C.循环链表? ? D.非线性结构

本题的考查知识点是数据结构。

如果一个非控的数据结构满足下列两个条件: 1) 有且只有一个根节点; 2) 每一一个结点最多有一一个前件，也最多有一一个后件。则称该数据结构为线性结构。如果一个数据结构不是线性结构，则称之为非线性结构。

数据结构B=(D, R)中， 每一个结点均有一个前件，不符合“有且只有一个根节点”的条件，所以为非线性结构。故本题答案选D。

36.某带链的队列初始状态为front=rear=NULL。经过一系列正常的入队与退队操作后，front=rear=10。 该队列中的元素个数为_

A.1? ? B.0? ? C.1或0? ? D.不确定

本题的考查知识点是带链队列。

在初始状态为front=rear=NULL的带链队列入队时，如果插入的结点既是队首结点又是队尾结点，则rear和front同时指向这个结点;否则在循环队列的队尾加入一一个新元素，rear指向新增结点的数据域，rear+1, front不变。 退队时，在循环队列的排头位置退出一个元素并赋给指定的变量，front指向第二个结点的数据域，front+1, rear不变。当front=rear=10时， front和rear同时指向这个唯一 元素，所以该队列中的元素个数为1。

故本题答案为A。

37.若二叉树没有叶子结点，则为空二叉树。

38.某带链栈的初始状态为top=bottom=NULL, 经过一系列正 常的入栈与退栈操作后，top=10, bottom=20。 该栈中的元素个数为_____。

A.不确定? ? B. 10? ? C.1? ? D.0

本题考查的知识点是栈。

带链的栈是具有栈属性的链表，线性链表的存储单元是不连续的，为把存储空间中一-些离散的空闲存 储结点利用起来，把所有空闲的结点组织成一个带链的栈，称为可利用栈。

线性链表执行删除操作运算时， 被删除的结点可以”回收到可利用栈，对应于可利用栈的入栈运算;线性链表执行插入运算时，需要一个新的结点，可以在可利用栈中取栈顶结点，对应于可利用栈的退栈运算。

可利用栈的入栈运算和退栈运算只需要改动top指针即可。因为是不连续的存储空间，所以top指针将不会有规律地连续变化，因此无法据此判断栈中的元素个数。

所以本题答案为A。

以下计算机中数据结构与算法的问题答案是什么？

（1） 用线性探测开放地址法处理冲突；

H(Jan)=10/2=5;

H(Feb)=6/2=3;

H(Mar)=13/2=6;

H(Apr)=1/2=0;

H(May)=13/2=6;冲突;H1=6+1=7;

H(June)=10/2=5;冲突;H1=5+1=6;冲突;H2=7;H3=8;

H(July)=5;H1=6;H2=7;H3=8;H4=9

H(Aug)=0;H1=1;

H(Sep)=9;H1=10;

H(Oct)=7;H1=8;H2=9;H3=10;H4=11;

H(Nov)=7;H1=8;H2=9;H3=10;H4=11;H5=12

H(Dec)=2

ASL=(1+2+1+1+1+1+2+4+5+2+5+6)/12=31/12

(2） 用链地址法处理冲突

H(Jan)=5;

H(Feb)=3;

H(Mar)=6;

H(Apr)=0;

H(May)=6

H(June)=5;

H(July)=5;

H(Aug)=0;;

H(Sep)=9;

H(Oct)=7;

H(Nov)=7;

H(Dec)=2

0-Apr-Aug

1-

2-Dec

3-Feb

4-

5-Jan-June-July

6-Mar-May

7-Oct-Nov

8-

9-Sep

ASL=(1+2+1+1+1+2+3+1+2+1+2+1)/12=18/12

(52) 栈和队列的共同点是______。 A. 都是先进后出 B. 都是先进先出 C. 只允许在端点处插入和删除元素 D.

[答案]C

[考点]数据结构与算法

解析：

栈是先进后出的，队列是先进先出的，共同点是只允许在端点处插入和删除元素。栈都是在一端进与出，而队列是在一端进在另一端出。

在计算机领域，堆栈是一个不容忽视的概念，堆栈是一种数据结构。堆栈都是一种数据项按序排列的数据结构，只能在一端(称为栈顶(top))对数据项进行插入和删除。

在单片机应用中，堆栈是个特殊的存储区，主要功能是暂时存放数据和地址，通常用来保护断点和现场。要点对比：指令队列，先进先出（FIFO—first in first out）。堆栈，先进后出 (FILO—First-In/Last-Out) 。

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。

扩展资料：

在队列的形成过程中，可以利用线性链表的原理，来生成一个队列。

基于链表的队列，要动态创建和删除节点，效率较低，但是可以动态增长。

队列采用的FIFO(first in first out)，新元素（等待进入队列的元素）总是被插入到链表的尾部，而读取的时候总是从链表的头部开始读取。每次读取一个元素，释放一个元素。所谓的动态创建，动态释放。因而也不存在溢出等问题。由于链表由结构体间接而成，遍历也方便。

参考资料来源：百度百科-堆栈

参考资料来源：百度百科-队列

数据结构与算法 2-3树是一种特殊的树，它满足两个条件

设 h 为树的高度，也就是根到叶子的边数。

如果所有内部结点都有 2 个子结点，那么叶子数是：2^h

如果所有内部结点都有 3 个子结点，那么叶子数是：3^h

现在有 9 个叶子，也就是：2^h = 9 = 3^h

所以：h=3 或 2

当 h=2 时，所有的内部结点都有 3 个子结点。

每层的结点数分别为：1、3、9。所以内部结点数是：1+3 = 4

当 h=3 时，叶子数是 9，比所有内部结点都有 2 个子结点（满二叉树）的多了 1 个。

满二叉树每层的结点数是：1、2、4、8

满二叉树每层的结点数，是任意 2-3 树每层结点的最小数目。

设我们 9 个叶结点的 2-3 树每层结点数为：1、a、b、9

显然，b = 4，否则就有一个结点的子结点数 =1 了。

所以，b = 4，因为满二叉树规定了第 2 层最小结点数是：2^2 = 4。

同理，a = 2，否则又会有一个结点的子结点数 =1。

所以，a = 2，因为满二叉树规定了第 1 层最小结点数是：2^1 = 2。

所以我们 9 个叶结点的 2-3 数每层结点数为：1、2、4、9

所以内部结点数是：1+2+4 = 7

所以答案是：4 或 7

这个数据结构和算法的题答案为什么是1120？

A[3，2]和A[2，3]指向的都是同一元素，根据前后地址不同发现相差2个地址位，所以按规律 A[1，4]地址就是原地址+2=1120