数据结构应试-1

1.

好像是错的

2.

n个元素，插入的可能有n+1个位置，所以n（n+1）/2*(n+1)=2/n

3.

4.

5.

6.

假设我们有一个循环队列，数组的长度为 n = 10，并且当前队头指针 f 的位置是 2，队尾指针 r 的位置是 8。我们需要计算队列中实际有多少个元素。

根据选项 D 的公式：队列中元素数量=(n+r−f)%n队列中元素数量=(n+r−f)%n

代入具体的值：队列中元素数量=(10+8−2)%10队列中元素数量=(10+8−2)%10 队列中元素数量=(16)%10队列中元素数量=(16)%10 队列中元素数量=6队列中元素数量=6

这意味着队列中有 6 个元素。

再来看另一个情况，假设队尾 r 已经绕过数组的末尾回到前面的位置，比如 f = 8 而 r = 2（队尾已经绕了一圈回到了 2），那么：

队列中元素数量=(10+2−8)%10队列中元素数量=(10+2−8)%10 队列中元素数量=(4)%10队列中元素数量=(4)%10 队列中元素数量=4队列中元素数量=4

这意味着队列中有 4 个元素。

这个公式能够正确处理两种情况：

当 r ≥ f 时，直接计算 r - f 得到元素数量。
当 r < f 时，计算 n - (f - r) 得到元素数量，然后加上 n 并对 n 取模，以确保结果在 [0, n-1] 的范围内。

这样，无论队尾指针是否已经绕过了数组的末尾，我们都可以通过选项 D 中的公式正确地计算出队列中元素的数量。

7.

8.

出栈顺序是这样是因为题干说容量至少是多少，所以从小容量依次看，只要合理就是最小容量

9.

注意：是初始栈顶指针

10.

11.

12.

13. 不会

14. 不会

15.

注意看1是原点还是0是

16.

对称矩阵是一种特殊的矩阵，其中主对角线两侧的元素是对称的，即如果矩阵 A 是对称矩阵，那么满足 A[i][j] = A[j][i]。因此，对于一个 n 阶的对称矩阵，只需要存储主对角线及其一侧的元素即可。

在压缩存储方式下，我们只存储对称矩阵的一半（通常存储上三角或下三角部分），以节省存储空间。假设我们存储的是下三角部分（包括主对角线元素），那么对于一个 n 阶的对称矩阵，存储的元素数量为：

N=n(n+1)2N=2n(n+1)

对于一个10阶的对称矩阵，存储的元素数量为：

N=10×(10+1)2=10×112=55N=210×(10+1)=210×11=55

这意味着压缩存储后的数组长度为55。

接下来我们需要确定 a85 的存储地址。因为是以行序为主存储，我们首先找出 a85 在原始矩阵中的位置，然后计算它在压缩存储数组中的位置。

a85 在第8行第5列，因此我们计算从第1行到第7行的元素总数，加上第8行的前4个元素，加上 a85 自身的位置：

第1行有1个元素。
第2行有2个元素。
第3行有3个元素。
第4行有4个元素。
第5行有5个元素。
第6行有6个元素。
第7行有7个元素。
第8行前4个元素。

总共的元素数为：

1+2+3+4+5+6+7+4+1=341+2+3+4+5+6+7+4+1=34

因为 a11 的地址为1，所以 a85 的地址为：

地址(a85)=1+(34−1)=34地址(a85)=1+(34−1)=34

但是我们需要减去1是因为 a11 本身已经占据了第一个位置，因此实际地址为：

地址(a85)=1+33=34地址(a85)=1+33=34

所以，正确答案是 C．33。

17. 不会

18.

为了计算数组 A[0…4, -1…-3, 5…7] 中元素的个数，我们需要分别计算每个维度的元素数量，然后将它们相乘。

数组 A 的维度如下：

第一维是从 0 到 4，共有 4 - 0 + 1 = 5 个元素。
第二维是从 -1 到 -3，共有 -3 - (-1) + 1 = 3 个元素。
第三维是从 5 到 7，共有 7 - 5 + 1 = 3 个元素。

计算各维度的元素数量：

第一维有 5 个元素。
第二维有 3 个元素。
第三维有 3 个元素。

因此，总的元素数量为这三个维度元素数量的乘积：

5×3×3=455×3×3=45

所以，数组 A 中含有 45 个元素。

正确答案是 B．45。

解释：共有 5 \times 3 \times 3 = 45 个元素。