本文主要是介绍3.1 线性结构，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
令序列X、Y、Z的每个元素按顺序进栈，且每个元素进栈.出栈各一次，则不可能得到出栈序列（ ）。
A. XYZ
B. XZY
C. ZXY
D. YZX
正确答案是 C。
解析
ZXY不可能得到这个序列，因为当Z最先出栈，说明X、Y已经入栈，且x比Y先入栈，那么在出栈的时候，X比Y要后出栈，所以当X最先出栈，只能够得到Z、Y、X这样的出栈序列。
函数调用和返回控制是用（ ）实现的。
A. 哈希表
B. 符号表
C. 栈
D. 优先列队
正确答案是 C。
解析
当有多个函数构成嵌套调用时（如：递归调用），按照“后调用先返回”的原则，函数之间的信息传递和控制转移可以用“栈”来实现。
若某线性表中最常用的操作是在最后一个元素之前插入和删除元素，则采用（ ）最节省运算时间。
A. 单链表
B. 仅有头指针的单循环链表
C. 仅有尾指针的单循环链表
D. 双链表
正确答案是 D。
解析
链式存储有：单链表(线性链表）、循环链表、双向链表。
单链表从链表的第一个表元开始，将线性表的节点依次存储在链表的各表元中。链表的每个表元除要存储线性表节点信息外，还要一个成分用来存储其后继节点的指针。
循环链表是单链表的变形，其特点是表中最后一个节点的指针域指向头节点，整个链表形成一个环。因此，从表中的任意一个节点出发都可以找到表中的其他节点。循环链表中，从头指针开始遍历的结束条件不是节点的指针是否为空，而是是否等于头指针。为简化操作，循环链表中往往加入表头节点。
双向链表的节点中有两个指针域，其一指向直接后继，另一指向直接前驱，克服了单链表的单向性的缺点。
用某排序方法对一元素序列进行非递减排序时，若该方法可保证在排序前后排序码相同者的相对位置不变，则称该排序方法是稳定的。简单选择排序法排序方法是不稳定的，（ ）可以说明这个性质。
A. 21 48 21* 63 17
B. 17 21 21* 48 63
C. 63 21 48 21* 17
D. 21* 17 48 63 21
正确答案是 A。
解析
本题考查数据结构基础知识。
对选项A进行简单选择排序时，第一趟需交换17和21，导致21与21*的相对位置发生变化，最后的非递减序列为17 21* 21 48 63，说明简单选择排序是不稳定的排序方法。
对于一个长度为n(n>1）且元素互异的序列，令其所有元素依次通过一个初始为空的栈后，再通过一个初始为空的队列。假设队列和栈的容量都足够大，且只要栈非空就可以进行出栈操作，只要队列非空就可以进行出队操作，那么以下叙述中，正确的是（ ）。
A. 出队序列和出栈序一定互为逆序
B. 出队序列和出栈序列一定相同
C. 入栈序列与入队序列一定相同
D. 入栈序列与入队序列一定互为逆序
正确答案是 B。
解析
从题目的描述来看，出栈之后，直接入队，然后出队。所以：入队序列=出栈序列，又因为出队序列=入队序列。所以出队序列和出栈序列一定相同。
若元素以a,b，c,d,e的顺序进入一个初始为空的栈中，每个元素进栈、出栈各1次，要求出栈的第一个元素为d，则合法的出栈序列共有（ ）种。
A. 4
B. 5
C. 6
D. 24
正确答案是 A。
解析
一共5个元素a,b,c,d，e,而d被要求作为第一个元素出栈。当d出栈后的情况应为：
有一个元素e还未入栈，而栈中已有a,b,c。栈中的a,b,c出栈顺序是已无可变性，必须是：c,b,a,此时，只是分析e在什么位置出栈即可。
c,b，a，三个元素，有四个空位，所以可以产生的序列可能为：
(1) d, e, c, b, a
(2) d,c,e,b,a
(3) d, c, b, e, a
(4) d, c, b,a, e
"单选题
以下关于图的遍历的叙述中，正确的是（ ）。
A. 图的遍历是从给定的源点出发对每一个顶点仅访问一次的过程
B. 图的深度优先遍历方法不适用于无向图
C. 使用队列对图进行广度优先遍历
D. 图中有回路时则无法进行遍历
正确答案是 C。
解析
图的遍历是指，从某一个顶点出发，沿着某条搜索路径对图中的所有顶点进行访问且仅访问一次的过程，所以回路不影响遍历，D选项错误。
这里的访问是沿着某条搜索路径，并不是任意的。A选项错误。
图的深度优先可以用于有向图，也可以用于无向图，B选项错误。
广度优先遍历的特点是尽可能横向搜索，即最先访问的顶点的邻接顶点也先被访问。为此，引入队列来保存，能够先进先出，即当一个顶点被访问后，就将其放入队中，当队头顶点出队时，就访问其未被访问的邻接顶点并让这些顶点入队。队列的特点是先进先出，广度优先刚好合适，C选项正确。
设S是一个长度为n的非空字符串，其中的字符各不相同，则其互异的非平凡子串（非空且不同于S本身）个数为（ ）。
A. 2n-1
B. n²
C. n(n+1)/2
D. (n+2)(n-1)/2
正确答案是 D。
解析
比如S字符串为“abcdefg”，长度为7，则S中的包含的互不相同的字符串有如下一些：
1.长度为6的个数为2：“abcdef”和“bcdefg”
2.长度为5的个数为3:“abcde”,“bcdef”,“cdefg”
3.长度为1的个数为7：“a”,“b”，“c”，“d”，“e”，“f”，“g”个数总和就是2+3+4+56+7=（2+7）×（7-2+1）/2同理，字符串长度为n，一个字符的字符串个数为n，除原字符串外最长的字符串为n-1个字符，个数有2个，按照推理，共有：2+3+………+n=（2+n）（n-1）/2个。
其中：
等差数列{an}的通项公式为：an=a1+(n-1)d。
前n项和公式为：Sn=n×a1+n(n-1)d/2或Sn=n(a1+an)/2。
栈的特点是后进先出，若用单链表作为栈的存储结构，并用头指针作为栈顶指针，则（ ）。
A. 入栈和出栈操作都不需要遍历链表
B. 入栈和出栈操作都需要遍历链表
C. 入栈操作需要遍历链表而出栈操作不需要
D. 入栈操作不需要遍历链表而出栈操作需要
正确答案是 A。
解析
本题考查数据结构基础知识。
本题用单链表作为栈的存储结构，因为栈的操作是先进后出，因此无论是入栈还是出栈，都只对栈顶元素操作，而在单链表中用头指针作为栈顶指针，此时无论是出栈还是入栈，都只需要对头指针指向的栈顶指针操作即可，不需要遍历链表。
采用循环队列的优点是（ ）。
A. 入队和出队可以在队列的同端点进行操作
B. 入队和出队操作都不需要移动队列中的其他元素
C. 避免出现队列满的情况
D. 避免出现队列空的情况
正确答案是 B。
解析
本题考查数据结构循环队列的问题。
1、循环队列的优点：
可以有效的利用资源。用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的；循环队列也是一种数组，只是它在逻辑上把数组的头和尾相连，形成循环队列，当数组尾满的时候，要判断数组头是否为空，不为空继续存放数据。
2、循环队列的缺点：
循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front==rear来判别队列是“空"是"满”。
3、拓展知识：
为充分利用向量空间，克服“假溢出”现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列。
综上所述，C，D都不属于其优点，B选项是循环队列的优点，A是对栈的描述。
以下关于字符串的叙述中，正确的是（ ）。
A. 包含任意个空格字符的字符串称为空串
B. 字符串不是线性数据结构
C. 字符串的长度是指串中所含字符的个数
D. 字符串的长度是指串中所含非空格字符的个数
正确答案是 C。
解析
空格也是一个字符，所以包含空格的字符串不能称为空串，所以字符串的长度是指字符串所有字符个数的总和（包括空格）；字符串是线性结构。
设循环队列Q的定义中有front和size两个域变量，其中front表示队头元素的指针，size表示队列的长度，如下图所示(队列长度为3，队头元素为x，队尾元素为z）。设队列的存储空间容量为M，则队尾元素的指针为（ ）。
A. (Q.front+Q.size-1)
B. (Q.front+Q.size-1+M) %M
C. (Q.front-Q.size)
D. (Q.front-Q.size+M) %M
正确答案是 B。
解析
本题考查循环队列队尾指针的计算方法。
从图示可以看出，要得到z的值可进行Q.front+Q.size-1操作，但在此不容忽视的一个问题是，循环队列在进行了多次入队出队操作之后，Q.front+Q.size-1有可能大于M,如Q.front指向M-1空间时,Q.front+Q.size-1=M+1，这已超出队列长度，所以需要让其与M进行求模操作，修正位置号。
某双端队列如下所示，要求元素进出队列必须在同一端口，即从A端进入的元素必须从A端出、从B端进入的元素必须从B端出，则对于4个元素的序列e1、e2、e3、e4，若要求从前2个元素（e1、e2）从A端口按次序全部进入队列，后两个元素（e3、e4）从B端口按次序全部进入队列，则可能得到的出队序列是（ ）。
A. e1、 e2、e3、e4
B. e2、e3、 e4、e1
C. e3、e4、 e1、e2
D. e4、e3、e2、e1
正确答案是 D。
解析
e1、e2从A端口进入，e3、e4从B端口进入，如下图所示：
根据题意：从A端进入的元素必须从A端出、从B端进入的元素必须从B端出；则出队顺序中e2在e1前面，e4在e3前面。只有答案D满足。
若一个栈初始为空，其输入序列是1，2，3，…，n-1，n，其输出序列的第一个元素为k（1≤k≤ 「n/2]），则输出序列的最后一个元素是（ ）。
A. 值为n的元素
B. 值为1的元素
C. 值为n-k的元素
D. 不确定的
正确答案是 D。
解析
本题考查数据结构基础知识。
以n等于4举例说明。输入序列为1234，输出序列的第一个元素可以为1或2。若为1，则输出序列可能为1234、1243、1342、1324、1432；若为2,则输出序列为2134、2143、2314、2341、2431。
对于线性表，相对于顺序存储，采用链表存储的缺点是（ ）。
A. 数据元素之间的关系需要占用存储空间，导致存储密度不高
B. 表中结点必须占用地址连续的存储单元，存储密度不高
C. 插入新元素时需要遍历整个链表，运算的时间效率不高
D. 删除元素时需要遍历整个链表，运算的时间效率不高
正确答案是 A。
解析
链表最大的优点是没有大小限制不需要提前分配空间也就是说它是动态的。你可以任意添加大小，通过结构体你可以将很多相关的数据放到一起。但是因为链表在内存里存放是不连续的。所以你不能快速的查找和修改。链表存储的缺点为数据元素之间的关系需要占用存储空间，导致存储密度不高。
以下关于线性表存储结构的叙述，正确的是（ ）。
A. 线性表采用顺序存储结构时，访问表中任意一个指定序号元素的时间复杂度为常量级
B. 线性表采用顺序存储结构时，在表中任意位置插入新元素的运算时间复杂度为常量级
C. 线性表采用链式存储结构时，访问表中任意一个指定序号元素的时间复杂度为常量级
D. 线性表采用链式存储结构时，在表中任意位置插入新元素的运算时间复杂度为常量级
正确答案是 A。
解析
线性表采用顺序存储结构时，访问表中任意一个指定序号元素的时间复杂度为常量级，因为顺序存储结构访问元素时，能直接定位元素，这样，操作的时间复杂度为O（1）。而插入一个元素时，需要将其他的元素位置进行调整，因此任意位置插入新元素的时间复杂度为O（n）。
线性表采用链式存储结构时，访问表中的任意一个指定序号元素时，需要从起始位置，通过指针指向，直到到达指定位置，才能访问该元素，时间复杂度为O(n)。而插入一个新元素时，找到任意位置的时间复杂度为O（n），而插入可以直接通过改变指针指向进行插入，时间复杂度为O（1），因此任意位置插入新元素整个操作的时间复杂度为O（n）。
因此本题只有A选项是正确的。
队列的特点是先进先出，若用循环单链表表示队列，则（ ）。
A. 入队列和出队列操作都不需要遍历链表
B. 入队列和出队列操作都需要遍历链表
C. 入队列操作需要遍历链表而出队列操作不需要
D. 入队列操作不需要遍历链表而出队列操作需要
正确答案是 A。
解析
本题考查数据结构相关基础知识。
循环单链表中最后一个结点的指针域rear不仅仅是结束标志，还是指向整个链表的第一个结点，从而使链表形成一个环。
对于队列，先进先出，后进后出。
在循环单链表中，出队操作从表头开始删除，也就是rear→next指针直接指向下一个结点，即rear→next=rear→next→next,然后释放原rear→next指向的结点即可，不需要遍历。
在循环单链表中，入队操作从队尾开始插入，新结点s→next指向首元素,然后rear→next指向新的结点s,
最后调整尾指针rear指向新结点s即可，不需要遍历。
设栈S和队列Q的初始状态为空，元素a b c d e f g依次进入栈S。要求每个元素出栈后立即进入队列Q，若7个元素出队列的顺序为b d f e c a g，则栈S的容量最小应该是（ ）。
A. 5
B. 4
C. 3
D. 2
正确答案是 B。
解析
本题考查数据结构基础知识。
根据队列的特点，元素出队的顺序与入队的顺序相同，因此，可知这7个元素的出栈顺序为b d f e c a g。对于入栈序列abcdefg,得出出栈序列b d f e c a g的操作过程为：push（a入）、push（b入）、pop（b出）、push（c入）、push（d入）、pop（d出）、push（e入）、push（f入）、pop（f出）、pop（e出）、pop（c出）、pop（a出）、push（g入）、pop（g出），如下图所示，从中可知栈S中元素最多时为4。因此，S的容量最小为4。
设栈初始时为空，对于入栈序列1，2，3，….，n，这些元素经过栈之后得到出栈序列p1，p2，p3，…，Pn,若p3=4，则p1，p2不可能的取值为（ ）。
A. 6,5
B. 2,3
C. 3,1
D. 3,5
正确答案是 C。
解析
采用穷举法。
C选项中，当p1是3的时候，栈中从上到下是2，1。要想1出来，必须2先出来，所以p2不可能是1，所以C错。
设有栈S和队列Q且其初始状态为空，数据元素序列a，b，c，d，e，f依次通过栈S，且每个元素从S出栈后立即进入队列Q，若出队列的序列是b，d，f，e，c，a，则S中的元素最多时，从栈底到栈顶的元素依次为（ ）。
A. a,b,c
B. a,c,d
C. a,c,e,f
D. a,d,f,e
正确答案是 C。
解析
本题考查的是队列与栈相关知识。
出队序列与入队序列是一致的，出队的序列是b,d,f,e，c,a,即入队序列也为b,d,f,e,c,a。
此时出栈后即入队，即出栈顺序也为b，d,f,e,c,a，元素出栈时，栈内情况依次如下：
栈S中元素最多时，从栈底到栈顶的元素依次为a,c,e,f。本题选择C选项。
设散列函数为H（key）=key%11，对于关键码序列（23，40，91，17，19，10，31，65，26），用线性探查法解决冲突构造的哈希表为（ ）。
正确答案是 B。
解析
本题考查的是哈希表的线性探测法。
首先根据关键码序列，分别求取H（Key）=key%11。得到如下所示关键字散列值：
当关键码65对11取模余10的时候，此时10号位置已经存放了关键码10，因此放到下一个位置，即0号位置。
本题B选项正确。
这篇关于3.1 线性结构的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
