数据结构选择题

1.将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（）

A.100

B.40

C.55

D.80

正确答案：C

对于10阶对称矩阵，其上三角矩阵（包括对角线）共有 (（10+1）*10/2=55 ) 个元素。由于是对称矩阵，我们可以将其压缩存储到一维数组中，只需存储上三角部分的元素加上对角线的元素，即 ( 45 + 10 = 55 ) 个元素。

参考答案：主对角线都存：10个，剩下的90个只存一半45个，共55个

知识点：数组

2.执行以下代码段(程序已包含所有必需的头文件)会输出什么结果。()

A.4

B.5

C.6

D.7

正确答案：C

官方解析：

从题目可知，二维数组a初始定义两行三列，所以其占用内存空间大小为6，与其赋值无关。

在C语言中，数组的大小是以其元素的数量来计算的，而不是以字节为单位。因此，数组a的总大小是2行乘以3列，等于6个元素。在printf函数中，使用%d格式化符号来输出sizeof(a)的结果，即数组a的大小。因此，输出的结果为6。

3.下列叙述中正确的是（ ）。

A.有一个以上根结点的数据结构不一定是非线性结构

B.只有一个根结点的数据结构不一定是线性结构

C.循环链表是非线性结构

D.双向链表是非线性结构

正确答案：B

在计算机科学中，数据结构通常分为线性结构和非线性结构。线性结构如数组、链表等，它们的元素之间是一对一的关系；而非线性结构如树、图等，它们的元素之间是一对多或者多对多的关系。

选项A描述的是有一个以上根结点的数据结构，这在标准的数据结构分类中并不存在，因为根结点通常指的是树或图结构的起始点，而一个结构中只能有一个起点。

选项C和D分别提到了循环链表和双向链表。循环链表是一种特殊的线性链表，其中最后一个节点指向第一个节点，形成一个环。双向链表则是每个节点都有两个指针，一个指向下一个节点，另一个指向前一个节点。虽然它们的结构比较特殊，但它们仍然是线性结构，因为它们的元素之间是一对一的关系。

因此，正确答案是B，只有一个根结点的数据结构不一定是线性结构，这可能指的是树或图结构，它们是非线性结构。

官方解析：

线性结构应满足：有且只有一个根结点与每个结点最多有一个前件，也最多有一个后件，所以 B 正确。所以有一个以上根结点的数据结构一定是非线性结构，所以 A 错误。循环链表和双向链表都是线性结构的数据结构。

知识点：数组

单选题

4.设循环队列中数组的下标范围是1~n，其头尾指针分别为f和r，则其元素个数为（）。

A.r-f

B.r-f+1

C.(r-f) mod n +1

D.(r-f+n) mod n

正确答案：D

其中 r 是尾指针，f 是头指针，n 是队列的容量。模运算确保了结果在 1 到 n 的范围内，这与循环队列的下标范围相匹配。所以正确答案是 D. (r-f+n) mod n。

假设循环队列的数组容量 n = 5，初始时头尾指针 f = 1, r = 1，此时队列中只有一个元素 'a'，其下标为 1。

接着，我们向队列中添加新元素，假设依次添加了元素 'b', 'c', 'd', 'e'，对应的下标分别为 2, 3, 4, 5。此时，尾指针 r 移动到了 5 的位置，而头指针 f 仍然在 1 的位置。

现在，我们再次添加一个元素 'f'，其下标为 1（因为队列是循环的），此时尾指针 r 回到了 1 的位置。这时，我们可以看到头尾指针再次相邻，但队列中仍然有 5 个元素。

根据循环队列的元素个数公式 (r - f + n) mod n，我们可以计算出此时的元素个数：

(1 - 1 + 5) mod 5 = 5 mod 5 = 0

由于结果为 0，我们需要在前面加上 n，即 5，得到最终的元素个数为 5。这与我们实际添加的元素个数相符。

知识点：数组、队列

5.以下能对二维数组 a 进行正确初始化的语句是（）

A.int a[2][]={{1,0,1},{5,2,3}};

B.int a[][3]={{1,2,3},{4,5,6}};

C.int a[2][4]={1,2,3},{4,5},{6}};

D.int a[][3]={{1,0,1},{},{1,1}};

正确答案：BD

题目选自牛客网