2026上半年软考中级软件设计师备考资料：第4章知识点分值分布及试题

2026上半年软考中级软件设计师第4章《数据结构》考试知识点分值分布及试题如下：

第4章 数据结构

一、分值分布

二、试题示例

1．顺序表与链表--3分

试题【2020年下半年软件设计师考试基础知识真题】

通过元素在存储空间中的相对位置来表示数据元素之间的逻辑关系，是（  ）的特点。

A.顺序存储

B.链表存储

C.索引存储

D.哈希存储

答案：A

解析：

本题考查数据结构与算法基础。

顺序存储时，通过元素在存储空间中的相对位置来表示数据元素之间的逻辑关系，元素的逻辑相对位置与物理相对位置是一致的。

链表存储：链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

索引存储：分别存放数据元素和元素间关系的存储方式。

哈希存储：哈希存储的基本思想是以关键字Key为自变量，通过一定的函数关系（散列函数或哈希函数），计算出对应的函数值（哈希地址），以这个值作为数据元素的地址，并将数据元素存入到相应地址的存储单元中。

综上所述，故本题选择A选项。

2．队列与栈--7分

试题【2022年下半年软件设计师考试基础知识真题】

设栈初始时为空，对于入栈序列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错。

3．字符串--2分

试题【2017年下半年软件设计师考试基础知识真题】

设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+5+6+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。