《数据结构》期末考试测试题【中】

---

往期练习题回顾：

《数据结构》期末考试测试题【上】
后续系列练习题：
《数据结构》期末考试测试题【下】

---

21.循环队列队空的判断条件为？

循环队列 ：将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。

• 当队列为空时，意味着没有任何元素在队列中。
• 在这种情况下，队头指针front和队尾指针rear应该指向同一个位置。
  • 因为没有元素，就不存在头和尾的间隔。
  • 所以队空的条件是rear == front

A选项：

• (rear + 1)%n==front：这是循环队列队满的判断条件，而不是队空的条件。
• 当队满时，尾指针的下一个位置（循环意义下）是头指针。

答案【C】

---

22. 单链表的存储密度比1？

存储密度 ：指数据元素本身所占的存储量和整个结点结构所占的存储量之比。

• 在单链表中，每个结点除了存储数据元素本身之外，还需要存储指向下一个结点的指针。

• 设数据元素所占的存储空间为D，指针所占的存储空间为P，那么一个结点所占的存储空间就是D + P

• 存储密度$=\frac{D}{D+P}$

• 由于$P>0，$所以$\frac{D}{D+P}<1$

所以：单链表的存储密度小于1

---

23.单链表的那些操作的效率受链表长度的影响？

A选项：

• 已知单链表设置了头指针，若要删除首元结点，只需要让头指针指向原首元结点的下一个结点。
• $（$假设头指针为$head，$原首元结点为$head->next，$操作$head=head->next）$
• 所以：删除单链表的首元结点，这个操作与单链表的长度$n$无关。

B选项：

• 因为单链表只有头指针和尾指针，要删除尾结点，需要先遍历单链表找到尾结点的前驱结点。
• 单链表的长度为$n，$遍历单链表找到尾结点的前驱结点需要$O(n)$的时间复杂度。
• 所以：删除单链表的尾结点，这个操作与单链表的长度有关。

C选项：

• 由于设置了头指针，要在首元结点之前插入新元素，只需要创建新结点，让新结点的$next$指针指向原首元结点，然后让头指针指向新结点。
• （假设头指针为$head，$原首元结点为$head->next，$新结点为$p，$操作$p->next=head->next，head=p）$
• 所以：在首元结点之前插入一个新元素，这个操作与单链表的长度$n$无关。

D选项：

• 因为设置了尾指针，尾指针直接指向尾结点。要在尾结点之后插入新元素，只需要修改尾指针指向新结点，新结点的$next$指针设为$NULL，$然后更新尾指针指向新结点。
• （假设尾指针为$rear，$新结点为$p，$操作$rear->next=p，p->next=NULL，rear=p），$这个操作与单链表的长度n无关。
• 所以：在尾结点之后插入一个新元素，这个操作与单链表的长度$n$无关。

答案【B】

---

24.顺序表中某元素的地址为？

顺序表中元素地址的计算方法：

第$i$个元素的地址$LOC(i)$与第一个元素地址$LOC(1)$的关系为：
$LOC(i)=LOC(1)+(i-1)\ast L$

• 其中$L$是每个元素的长度。

---

• 这里$LOC(1)=100，i=5，L=2$

• 根据上述公式$LOC(5)=100+(5-1)\ast 2$

答案【C】

---

25.m叉树第K层的结点数为？

满$m$叉树的结点个数规律：

• 第$1$层有$1=m^{1-1}$个结点。
• 第$2$层有$m=m^{2-1}$个结点。
• 第$3$层有$m^2=m^{3-1}$个结点。
• 以此类推，第$k$层有$m^{k-1}$个结点。

这里深度$h$是一个干扰条件，求第$k$层的结点个数与树的深度h无关（只要$1⩽k⩽$即可）

答案【A】

---

26. 在双向循环链表某节点的后面插入一个新节点的操作为？

• 第一步：要先让q的前驱指针q -> prior指向p，即q -> prior=p
  • 因为q要插入到p后面，所以q的前驱就是p
• 第二步：让q的后继指针q -> next指向p的后继p -> next，即q -> next=p -> next
  • 因为q要插入到p后面，所以q的后继就是p -> next
• 第三步：修改p原来的后继p -> next的前驱指针，让p -> next -> prior指向q，即p -> next -> prior=q
  • 因为q插入到了p和p -> next之间，所以p -> next的前驱就变成了q
• 第四步：最后让p的后继指针p -> next指向q，即p -> next=q
  • 因为q插入到了p和p -> next之间，所以p的后继就变成了q

---

在双向循环链表中，要在p指针所指的结点后插入q所指向的新结点的核心原理：

插入新节点的四步操作中只要保证：

• q -> next=p -> next和p -> next -> prior=q操作

• 在p -> next=q操作之前即可

A选项：

q -> prior = p;
q -> next = p -> next;
p -> next -> prior = q;
p -> next = q;

这个操作顺序是正确的，按照我们前面分析的插入步骤进行操作。

B选项：

p -> next = q;
p -> next -> prior = q;
q -> prior = p;
q -> next = p -> next;

• 这里第一步p -> next = q就破坏了链表原来的结构。
• 在还没有处理好q与其他节点的关系之前就修改了p的后继指针，导致后续操作无法正确进行。

C选项：

q -> prior = p;
q -> next = p -> next;
p -> next = q;
p -> next -> prior = q;

• 其中第三步p -> next = q和第四步p -> next -> prior = q顺序错误。
• 应该先修改p -> next -> prior再修改p -> next

D选项：

p -> next = q;
q -> prior = p;
p -> next -> prior = q;
q -> next = p -> next;

• 第一步p -> next = q破坏了链表结构。

答案【A】

---

27.顺序表中时间复杂度为$O(1)$的操作为？

A选项：

将$n$个结点从小到大排序，常见的排序算法如冒泡排序、插入排序、快速排序等，它们的时间复杂度都不是$O(1)$

• 例如冒泡排序的时间复杂度为$O(n^2)$
• 快速排序平均时间复杂度为$O(nlogn)$

B选项：

• 在顺序表中删除第$i$个结点，需要将第$i+1$个结点到第$n$个结点依次向前移动一位。
• 这个操作平均需要移动$n-i$个结点，时间复杂度为$O(n)$，而不是$O(1)$

C选项：

• 在顺序表中第$i$个结点后插入一个新结点，需要将第$i+1$个结点到第$n$个结点依次向后移动一位。
• 这个操作平均需要移动$n-i$个结点，时间复杂度为$O(n)$，而不是$O(1)$

D选项：

• 访问第$i$个结点$(1\le i\le n)$，因为顺序表是一种随机存取结构，直接通过数组下标就可以访问到第$i$个结点，时间复杂度为$O(1)$
• 求第$i$个结点的直接前驱$(2\le i\le n)$，在顺序表中，第$i$个结点的直接前驱是第$i-1$个结点，同样可以直接通过数组下标访问，时间复杂度为$O(1)$

答案【D】

---

28.关于线性表的链式存储描述正确的为？

链式存储结构的概念：

• 链式存储结构是通过指针将各个数据节点连接起来的一种存储方式。
• 每个节点包含数据部分和指向下一个节点的指针部分。

在链式存储结构中，节点在内存中的存储位置并不需要严格按照顺序：

• 例如，第一个节点可以存储在内存地址100的位置，第二个节点可以存储在内存地址200的位置，它们通过指针相互关联。
• 当然，这些节点也可以连续存储，比如第一个节点在100，第二个节点在104（假设每个节点占用4个字节）

所以：线性表若采用链式存储结构时，内存中可用存储单元的地址连续或不连续都可以

答案【B】

---

29.单向循环链表删除第一个元素的操作为？

A选项：

q=h->next;
h->next=q->next;
if(p==q)
{p=h; 
}
free(q);

• 第一步： q = h->next; 这里的目的是让 q 指向要删除的第一个结点。
  • 因为 h 是头结点， h->next 就是第一个实际的数据结点。
• 第二步： h->next = q->next; 这一步是将头结点 h 的 next 指针指向原来第一个结点（ q 所指向的结点）的下一个结点。
  • 这样就把第一个结点从链表中“断开”了。
• 第三步：if(p == q)
  • 因为 p 是尾指针，如果要删除的结点 q 就是尾结点（在单循环链表中这种情况是可能的）
  • 那么在删除 q 后，尾指针 p 应该指向头结点 h ，所以 p = h;
• 第四步： free(q);释放 q 所指向的结点（也就是原来的第一个结点）的内存空间。

B选项：

h->next=h->next->next;
q=h->next;
free(q);

• 第一步： h->next = h->next->next; 这一步确实将头结点 h 的 next 指针指向了原来第一个结点的下一个结点。
  • “断开”了第一个结点。
• 第二步：q = h->next;，此时 q 指向的是原来第一个结点的下一个结点，而不是要删除的第一个结点。
  • 这就导致 free(q); 释放的是错误的结点。

C选项：

q=h->next;
h->next=q->next;
if(p!=q)
{p=h;
}
free(q);

• 这个选项中的语句if(p ！= q)，导致无法进行正确的删除操作。

D选项：

q=h->next;
h->next=h->next->next;
free(q);

• 第一步：q = h->next;让 q 指向要删除的第一个结点。
• 第二步： h->next = h->next->next; 将头结点 h 的 next 指针指向原来第一个结点的下一个结点。
  • “断开”了第一个结点。
  • 但是没有考虑如果要删除的结点 q 是尾结点时尾指针 p 的更新情况，所以这个选项是不完整的。

答案【A】

---

30.有序单链表中查找操作的平均查找节点数为？

长度为$n$有序单链表查找值等于$x$的结点：

• 在最好的情况下，也就是要查找的元素在表头，只需要比较$1$次。
• 在最坏的情况下，要查找的元素在表尾，则需要比较$n$次。

对于有序单链表的查找，其查找成功时的平均查找长度（ASL）计算方式与顺序表的折半查找不同，这里它是一个线性查找过程。

• 因为每个元素查找成功的概率是相等的，设为$1/n。$查找第i个元素时，需要比较$i$次。
• 那么平均查找长度长度为$ASL={\sum }_{i=1}^{n}i\times \frac{1}{n}$
• 根据等差数列求和公式${\sum }_{i=1}^{n}i=\frac{n(n+1)}{2}，$所以$ASL=\frac{1}{n}\times \frac{n(n+1)}{2}=\frac{n+1}{2}$

答案【A】

---

31.某哈夫曼树的叶子结点树为？

• 对于哈夫曼树：结点总数 = 叶子结点个数+ 度为2的结点个数（哈夫曼树并且不存在度为1的结点）
• 二叉树的性质： 叶子结点个数=度为2的结点个数 + 1

哈夫曼树的性质：

• 结点总数 = 2 * 度为2的结点个数 + 1
• 结点总数 = 2 * 度为0的结点个数 - 1

答案【C】

---

32.某字符串的子串的个数为？

子串的概念：

• 空串是任何串的子串。
• 对于一个长度为$n$的串$S，$其 非空子串的个数 为$\frac{n(n+1)}{2}$

---

• 这里串$S=“software”，$其长度$n=8，$所以非空子串的个数为$36$

• 但是不要忘记空串也是子串，所以子串的总个数应该是$36+1=37$

答案【D】

33.某栈的第i次出栈元素为？

• 已知入栈序列是$1,2,3,\cdots ,n$
• 且$p1=n，$即第一个出栈的是$n，$同时它也是最后入栈的元素。
• 这意味着$1,2,3,\cdots ,n$这些元素是先全部入栈，然后再开始出栈操作。

栈是一种后进先出（LIFO）的数据结构

• 那么第二个出栈的元素$p2，$就是在$n$入栈之前最后入栈的元素，也就是$n-1$
• 第三个出栈的元素$p3$就是$n-2$
• 按照这个规律，第$i$个出栈的元素$pi，$就是$pi=n-(i-1)=n-i+1$

答案【C】

---

34.在顺序表中插入一个新元素需要后移的元素数？

在顺序表的第$i$个元素$（1\le i\le n+1）$之前插人一个新元素时。

• 需从最后一个元素即第$n$个元素开始，依次向后移动一个位置，直至第$i$个元素。

总计共$n-i-1$个元素。

答案【B】

---

35.创建一个有序单链表的时间复杂为？

对于创建一个有序单链表，每插入一个节点都需要在已有的链表中找到合适的位置进行插入。

• 当插入第一个节点时，不需要比较，时间复杂度为$O(1)$
• 当插入第二个节点时，最多需要比较$1$次找到合适的插入位置，时间复杂度为$O(1)$
• 当插入第三个节点时，最多需要比较$2$次找到合适的插入位置，时间复杂度为$O(2)$
• 以此类推，当插入第$n$个节点时，最多需要比较$n-1$次找到合适的插入位置，时间复杂度为$O(n-1)$

---

• 总的比较次数为$1+2+\cdots +(n-1)$
• 根据等差数列求和公式$S=\frac{n(n-1)}{2}，$这里n表示项数。
• 时间复杂度的大O表示法忽略常数和低阶项$，\frac{n(n-1)}{2}$的最高阶是$n^2，$所以时间复杂度为$O(n^2)$

答案【C】

---

36.两个有序表合并为一个有序表的最少比较次数为？

对于将两个各有$N$个元素的有序表归并成一个有序表的情况，要使比较次数最少，就是： 当一个表的最大元素小于另一个表的最小元素时

• 例如，有表$A=[a_1,a_2,\cdots ,a_N]$和表$B=[b_1,b_2,\cdots ,b_N]$
• 若$a_N<b_1，$那么只需要将表$A$的$N$个元素依次与$b_1$比较后放入新的有序表，比较次数就是$N$次。

答案【A】

---

37.与哈希表的查找效率无关的为？

哈希表（Hash Table） ：也称为散列表

是一种通过哈希函数将键（Key）映射到表中一个位置以便快速访问记录的数据结构。

---

具体来说，哈希表的查找效率受以下几个因素影响：

哈希函数 ：

• 良好的哈希函数能够将输入的不同值均匀地映射到哈希表的不同索引位置上，从而减少冲突，提高查找效率。

装载因子 ：装载因子是哈希表中已存储键值对的数量除以哈希表的长度。

• 装载因子的增加会导致哈希冲突的增加，从而降低查找效率。
• 因此，通过调整哈希表的长度或使用动态哈希表等方式来控制负载因子可以提高查找效率。

冲突处理方法 ：

• 哈希表采用链地址法（Chaining）和开放地址法（Open Addressing）来解决哈希冲突。
• 合理的冲突解决策略能够减少冲突的发生，从而提高查找效率。

答案【A】

---

38.判断哪个关键字序列是堆？

堆分为大根堆和小根堆。

• 大根堆 ：要求每个节点的值都不大于其父节点的值。

• 小根堆 ：要求每个节点的值都不小于其父节点的值。

---

这里我们可以将这些序列看作完全二叉树的层次遍历序列来进行分析：

答案【D】

---

39.排序算法中是稳定的排序算法的为？

稳定排序 ：如果两个相等的元素在排序前后的相对顺序不变，那么这种排序算法就是稳定的排序算法。

不稳定的排序方法包括：快速排序、希尔排序、堆排序。

稳定的排序方法包括：直接插人排序、折半插人排序、冒泡排序、简单选择排序、归并排序、基数排序。

---

记忆小窍门 ：不稳定的三个排序方法可以简记为快些(希)堆

• 可以想成当我们试图将很多材料堆积起来时，如果只为了追求“快一些”，可能会导致堆积起来的材料不稳定，容易倒塌。

• 除了简记为“快些(希)堆”的三个排序方法，其他所有的排序方法都是稳定的。

A选项：

希尔排序 ：按照一定的增量对数据进行分组插入排序的改进算法。

• 在希尔排序的过程中，相同元素可能会因为分组和不同的增量而改变相对顺序，所以希尔排序是不稳定的排序方法。

B选项：

快速排序 ：通过选择一个基准元素，将数组分为两部分，左边部分小于基准元素，右边部分大于基准元素，然后递归地对左右两部分进行排序。

• 在快速排序的过程中，相等元素的相对顺序可能会因为划分操作而改变，所以快速排序是不稳定的排序方法。

C选项：

归并排序 ：将数组不断地分成两半，对每一半进行排序，然后再将排好序的两半合并起来。

• 在合并的过程中，如果遇到相等的元素，会按照原来的顺序依次放入合并后的数组中，所以相等元素的相对顺序不会改变，归并排序是稳定的排序方法。

D选项：

堆排序 ：利用堆这种数据结构进行排序的算法。

• 在调整堆的过程中，相同元素的相对顺序可能会发生改变，所以堆排序是不稳定的排序方法。

答案【C】

---

40.在10000个元素中最快的找到其中最大的10个元素的排序算法为？

A选项：

冒泡排序 ：相邻元素两两比较，将较大的元素逐步“冒泡”到数组的末尾。

• 对于$10000$个元素的数组，如果要找出最大的$10$个元素，冒泡排序需要对几乎整个数组进行多次比较和交换操作。
• 它的时间复杂度在最坏情况下为$O(n^2)（n=10000），$即使只找最大的$10$个元素，也需要大量的比较操作，效率较低。

B选项：

快速排序 ：通过选择一个基准元素，将数组分为两部分，左边的元素都小于基准元素，右边的元素都大于基准元素，然后递归地对左右两部分进行排序。

• 快速排序的平均时间复杂度为$O(nlogn)，$但如果要找出最大的$10$个元素，它仍然需要对整个数组进行较多的划分和比较操作，不能高效地只针对最大的$10$个元素进行处理。

C选项：

简单选择排序 ：每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。

• 它的时间复杂度为$O(n^2)，$要找出最大的$10$个元素，需要进行大量的比较操作，效率不高。

D选项：

堆排序 ：

• 对于求最大的$10$个元素，可以构建一个大小为$10$的最小堆，然后遍历剩下的$10000-10=9990$个元素。如果元素大于堆顶元素，则替换堆顶元素，并调整堆。
• 这样只需要对$10000$个元素进行一次遍历，每次调整堆的时间复杂度为$O(log10)$（因为堆的大小为$10$），总的时间复杂度接近$O(n)（n=10000），$相比其他算法，在只找出最大的$10$个元素时最节省时间。

答案【D】