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。