# 数据结构

> 来源：梦飞idc云平台 | 原文：https://www.mfisp.com/22060.html | 发布：2023-07-14 | 更新：2023-07-14 | 分类：建站教程

1.将N个数据按照从小到大顺序组织存放在一个单向链表中。如果采用二分查找，那么查找的平均时间复杂度是O(logN)。  
F

 

解析：  
 二分查找的平均复杂度是O（logN）没有错，一看到这个就跳坑了。然后知道陷阱来了！按顺序存放在单项链表中。二分查找是不可以用链表存储的：  
 这是由链表的特性决定的。链表是很典型的顺序存取结构，数据在链表中的位置只能通过从头到尾的顺序检索得到，即使是有序的，要操作其中的某个数据也必须从头开始。  
 这和数组有本质的不同。数组中的元素是通过下标来确定的，只要你知道了下标，就可以直接存储整个元素，比如a[5],是直接的。链表没有这个，所以，折半查找只能在数组上进行。

 

在单链表中，要访问某个结点，只要知道该结点的指针即可。因此，单链表是一种随机存取结构。  
 F

 

解析：  
 线性表分(顺序存储和链式存储)  
 顺序存储即数组,我们使用数组的时候申请的是连续的内存空间可以直接读取的，a[24],a[25]  
 链式存储即链表，链表中单个节点的内存地址不是连续的，而是散列在计算机中，通过next指针访问下一个节点，所以所必须遍历链表才能读取数据！  
 总结:  
 顺序表:顺序存储，随机读取  
 链式:随机存储,顺序读取(必须遍历)

 

取线性表的第i个元素的时间同i的大小有关。  
 F

 

解析：  
 线性表分顺序表和链表  
 顺序表最主要的特点是随机访问，即通过首地址和元素序号可以在O(1)的时间内找到指定的元素  
 线性表因为是按序号直接取值，所以没有关系，但如果是链式存储结构就有关系

 

4.在具有头结点的链式存储结构中，头指针指向链表中的第一个元素结点。F

 

解析：  
 头指针 指示链表中第一个结点（即第一个数据元素的存储映像）的存储位置。同时，由于最后一个数据元素没有直接后继，则线性链表中最后一个结点的指针为“空”（NULL）。  
 有时在单链表的第一个结点之前附设一个结点，称之为头结点 。 头结点的数据域可以不存储任何信息，也可以存储如线性表长度等类的附加信息，头结点的指针域存储指向第一个结点的指针（即第一个元素结点的存储位置）。单链表的头指针指向头结点。若线性表为空，则头结点的指针域为“空”。

 

有头结点的链表结构中，头指针指向链表的头结点，因为单链表不具有回溯性，即通过指针指向的节点不能找到该节点的前一个节点，只能找到后面的节点。

 

目的是便于链表的操作；比如删除第一个数据节点时，让头结点的指针域指向第二个数据节点即可。如果头指针指向的是第一个数据节点，那么通过此指针不能找到前一个节点，也就不能实现删除。

 

5.在一个设有头指针和尾指针的单链表中,执行删除该单链表中最后一个元素的操作与链表的长度无关F

 

解析：  
 必须要遍历到倒数第二个元素把它设为尾部（链表不是双向链表）

 

6.在用数组表示的循环队列中，front值一定小于等于rear值。F

 

解析：  
 rear在对max取余之后会从零开始，但这时front并不是零。所以会出现front>rear,（ >,=,<三种情况都有可能出现）  
 （可以这样理解：因为是循环的，所以可能rear由大变小，画个图就知道了。）

 

7.若采用“队首指针和队尾指针的值相等”作为环形队列为空的标志，则在设置一个空队时只需将队首指针和队尾指针赋同一个值，不管什么值都可以。T

 

解析：  
 判断队满的方式一：牺牲一个存储的单元来区分空队、满队

 

约定：当队头指针在队尾指针的下一个位置时，队满  
队空：q.frontq.rear  
队满：(q.rear+1)%MAXSIZEq.front  
队列中的元素个数：(q.rear-q.front+MAXSIZE)%MAXSIZE

 

在这里插入图片描述

 

答案：T  
 解析：注意题目中的字眼：“任一指定序号”“最后”，说明已经确定了位置，此时根据时间复杂度，顺序线性表的查找为 O(1) ,因为实在最后进行插入和删除的，所以不涉及元素的移动，（如果插入和删除的位置不在最后，则删除过后删除位置之后的元素要全部往前移，插入时要先将插入位置之后的元素全部往后移来腾出空间插入，所以这是插入和删除操作的时间复杂度就为 O(n) ）。 如果时线性链表，则每次取相应的元素时都要进行遍历，此时的时间复杂度为 O(n) 。插入和删除如果指明位置时时间复杂度为 O(1) ,如果没有指明位置则仍需要先遍历找到位置再操作，此时的时间复杂度为 O(n) 。

---
本页由 梦飞idc云平台（https://www.mfisp.com）提供。站点导航见 https://www.mfisp.com/llms.txt