考研数据结构B在线题库每日一练（七十三）

本文提供考研数据结构B在线题库每日一练，以下为具体内容

1、线性表的链式存储结构与顺序（连续）存储结构相比优点是（ ）。

A、便于插入和删除

B、便于随机存取

C、所有的操作/运算的算法简单

D、便于查找

2、设循环队列中数组的下标范围是0..n-1，其头指针front指向队首元素，rear指向队尾元素，则队列的长度为（ ）。

A、rear-front

B、rear-front+1

C、(rear-front+1)%(n+1)

D、(rear-front+n+1)%n

3、在长度为n且带头结点的链式存储实现的线性表的第i（0≤i≤n）个位置插入一个元素，需要查找运算（ ）次。

A、1

B、n-i

C、i

D、n-2

4、数组A中，每个元素A的长度为4个字节，行下标i从1到8，列下标j从1到10，从首地址S开始连续存放在存储器内，该数组按行优先存放时，元素A[5][6]的起始地址为（ ）。

A、S+160

B、S+180

C、S+220

D、S+140

5、已知完全二叉树有10个结点，则整棵二叉树有（ ）个度为1的结点？

A、2

B、1

C、0

D、不确定

1、试题答案：A

试题解析：

对于A，链式存储结构插入和删除不需要移动元素，仅需要修改指针，其操作的时间复杂度为O(1)，而顺序存储结构插入和删除均需要移动元素，其操作的时间复杂度为O(n)。对于B，链式存储结构不是随机存取结构而顺序表是随机存取结构，因此B错误；对于C和D，对于已知下标的查找，链表的查找操作需要从头开始，时间复杂度为O(n)，而顺序表可以通过下标直接访问，时间复杂度为O(1)，因此C和D错误，故本题选A。

2、试题答案：D

试题解析：

在本题中，front指向队首元素，rear指向队尾元素，因此元素个数应当为rear-front+1，因此A错误。再加n是为了保证当rear<front时，计算出的结果是非负数，因此B错误。数组的最大容量为n，因此C错误，故本题选D。

3、试题答案：C

试题解析：

链式存储结构不是随机存取结构，因此在本题中查找第i个位置的元素需要从链表的头开始遍历查找链表，查找到第i个链表需要查找运算i次，故本题选C。

4、试题答案：B

试题解析：

画出该数组如下（用绿色表示待存储的元素，用红色表示A[5][6]的位置）：

A[5][6]之前需要存放元素的个数=4*10+5=45。由于每个元素长度为4个字节，存储这些元素占据的总的存储空间为45*4=180。再加上首地址，则A[5][6]的地址为SA+180，故本题选B。

5、试题答案：B

试题解析：

由于树的结点数较少，可以采用画图法解决本题，画出10个结点的完全二叉树如下：

根据上图度为1的结点个数为1，故本题选B。