返回试卷 在打印对话框中选择「另存为 PDF」即可下载

2026年04月高等教育自学考试《13003数据结构与算法》试题

13003数据结构与算法 / 历年真题　共 34 题　更新于 2026-09-28

一、单选题

下列每小题的选项中，只有一项是最符合题意的正确答案，多选、错选或不选均不得分。

1.
在数据结构中,从逻辑上可以把数据结构分成
  • A.动态结构和静态结构
  • B.紧凑结构和非紧凑结构
  • C.线性结构和非线性结构
  • D.内部结构和外部结构

参考答案C

解析数据结构从逻辑上可分为线性结构和非线性结构。动态与静态、紧凑与非紧凑是从存储角度划分，内部与外部并非逻辑分类。答案：C
2.
下列与算法的时间复杂度有关的是
  • A.问题规模
  • B.计算机硬件性能
  • C.编译程序质量
  • D.程序设计语言

参考答案A

解析算法的时间复杂度是指算法执行所需要的计算工作量，主要取决于问题规模。计算机硬件性能、编译程序质量、程序设计语言影响的是程序的实际执行时间，而非算法时间复杂度。答案选A。
3.
在n个结点的顺序表中,算法的时间复杂度是O（1）的操作是
  • A.访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
  • B.在第i个结点后插入一个新结点（1≤i≤n）
  • C.删除第i个结点（1≤i≤n）
  • D.将n个结点从小到大排序

参考答案A

解析顺序表可通过下标直接访问元素。访问第i个结点和求其直接前驱可直接通过下标计算，时间复杂度为O(1)。插入、删除结点需移动元素，时间复杂度是O(n)，排序的时间复杂度通常大于O(1)。答案选A。
4.
带头结点的单链表的头指针为head,表为空的判定条件是
  • A.head = NULL
  • B.head->next == NULL
  • C.head != NULL
  • D.head->next == head

参考答案B

解析带头结点的单链表，头结点本身存在，若表为空，意味着头结点之后无其他节点，即头结点的 next 指针为空。答案：B
5.
已知一个的进栈序列是1,2,3,…n,其输出序列是p₁,p₂,…,pₙ,若p₁=n,则pᵢ的值是
  • A.i
  • B.n-i
  • C.n-i+1
  • D.n+1

参考答案C

解析进栈序列是1,2,3…n，p₁ = n说明第一个出栈的是n，意味着1到n按顺序进栈后n先出栈。此时栈内元素从栈顶到栈底是n - 1，n - 2，…，1，所以出栈顺序是n，n - 1，n - 2，…，1，即pᵢ = n - i + 1。答案选C。
6.
若一个栈用数组data[1..n]存储,初始栈顶指针top为n+1,则以下元素x进栈的操作正确的是
  • A.top++; data[top]=x;
  • B.data[top]=x; top++;
  • C.top--; data[top]=x;
  • D.data[top]=x; top--;

参考答案C

解析初始栈顶指针top为n + 1，栈底在数组下标1处，进栈时栈顶指针应向栈底移动，即top减1，然后将元素放入新栈顶位置。答案：C
7.
在循环队列中元素的排列顺序与
  • A.元素进队的先后顺序有关
  • B.元素值的大小有关
  • C.队头和队尾指针的取值有关
  • D.队中数组大小有关

参考答案A

解析循环队列是按先进先出原则操作的，元素进入队列的先后顺序决定了其在队列中的排列顺序。答案是A。
8.
设二维数组a[1..5,1..8],若按列优先的顺序存放数组的元素,则a[4][6]前面元素的个数是
  • A.6
  • B.28
  • C.29
  • D.40

参考答案B

解析数组行下标1~5共5行，列下标1~8共8列，采用列优先存储，先依次存储每一列全部行元素再换下一列；a[4][6]前有完整的1至5列，完整列元素总数=(6-1)×5=25，第6列里a[4][6]前方还有1至3行共4-1=3个元素，二者相加25+3=28，所以a[4][6]前面元素个数为28，选B。
9.
对矩阵压缩存储是为了
  • A.方便运算
  • B.方便存储
  • C.提高运算速度
  • D.节省存储空间

参考答案D

解析矩阵压缩存储是把多个相同值或零元素只存一次，主要目的是节省存储空间。答案：D
10.
串是一种特殊的线性表,其特殊性体现在
  • A.可以顺序存储
  • B.数据元素是一个字符
  • C.可以链式存储
  • D.数据元素可以是多个字符

参考答案B

解析串是由零个或多个字符组成的有限序列，它与一般线性表的区别在于其数据元素是一个字符。顺序存储和链式存储是线性表通用的存储方式，并非串的特殊性。所以答案选B。
11.
设森林F中有3棵树,第一、第二和第三棵树的结点个数分别为m1、m2和m3。与森林F对应的二叉树根结点的右子树上的结点个数是
  • A.m1
  • B.m3
  • C.m1+m2
  • D.m2+m3

参考答案D

解析森林转二叉树时，第一棵树构成根和左子树，其余树构成右子树，所以右子树结点个数是除第一棵树外其他树的结点数之和，即m2 + m3。答案：D
12.
下列选项中,均为稳定排序方法的是
  • A.堆排序和起泡排序
  • B.快速排序和希尔排序
  • C.简单选择排序和归并排序
  • D.归并排序和起泡排序

参考答案D

解析稳定排序是指排序前后相同元素的相对顺序不变。归并排序和起泡排序是稳定排序，堆排序、快速排序、希尔排序、简单选择排序是不稳定排序。所以答案选D。
13.
在下列排序方法中,某一趟结束后未必能选出一个元素放在其最终位置上的是
  • A.堆排序
  • B.冒泡排序
  • C.直接插入排序
  • D.快速排序

参考答案C

解析堆排序每趟能确定一个最大或最小元素位置；冒泡排序每趟把最大或最小元素移到一端；快速排序每趟能确定基准元素最终位置；而直接插入排序是将未排序元素插入已排序序列，某一趟结束后未必能使元素处于最终位置。答案：C
14.
有100个元素的有序表,采用折半查找方法,不成功时最多的比较次数是
  • A.7
  • B.10
  • C.25
  • D.50

参考答案A

解析折半查找不成功时最多比较次数为题目图片，n = 100，题目图片。答案选A。
15.
哈希表中出现哈希冲突是指
  • A.两个元素具有相同的序号
  • B.两个元素的关键字不同,而其他属性相同
  • C.数据元素过多
  • D.两个元素的关键字不同,而对应的哈希函数值相同

参考答案D

解析哈希冲突就是不同关键字经哈希函数计算得到相同的哈希函数值。答案选D。

二、填空题

请输入正确的答案，多个答案中间用分号隔开。

16.
算法的每一个步骤都必须有确切的含义,这个特性是算法的______。

参考答案确定性

17.
在计算机科学中,______是指所有能输入计算机并被计算机处理的符号的集合。

参考答案数据

18.
线性表是一个有限序列,组成线性表的是n（n≥0）个______。

参考答案元素

19.
一维数组a采用顺序存储方式,下标从0开始,每个元素占4个存储单元,a[8]的起始地址为100,则a[11]的起始地址为______。

参考答案112

20.
可以进行拓扑排序的有向图一定是______。

参考答案无环图

21.
数据序列（8,7,6,5,4,3,2,1）采用二路归并排序方法进行递增排序,所需要的关键字比较次数是______。

参考答案12

22.
对含有n个元素的数据序列进行简单选择排序,总的关键字比较次数是______。

参考答案n（n-1）/2

23.
归并排序是一个______算法,可以使用非递归或递归的方式实现。

参考答案分治

24.
为了实现分块查找,线性表必须采用______方法存储。

参考答案索引

25.
哈希表的查找效率使用______来度量。

参考答案平均查找长度

三、问答题

主观题不参与评分，请参考答案自行评分。

26.
简述递推法的思想。

参考答案根据递推关系,能从已求得的问题规模为1,2,...,i-1的一系列解,构造出问题规模为i的解。求解规模为i的解时,有时可能仅需规模为1,2,...,i-1的系列解中的一部分,而不是全部。

27.
简述二叉树与度为2的树之间的差别。

参考答案二叉树的子树有严格的左右之分,其次序不能任意颠倒,某个结点即使只有一棵子树,也区分是左子树还是右子树,而在度为2的树中,某个结点只有一棵子树时,是不区分左右的。除此之外,二叉树可以是空树,而度为2的树至少有一个度为2的结点,所以不能为空树。

28.
有一棵树的括号表示为A（B,C（E,F（G））,D）,回答下面的问题:
（1）指出树的根结点。
（2）指出这棵树的所有叶子结点。
（3）结点C的度是多少?
（4）这棵树的高度是多少?
（5）结点C的孩子结点是哪些?

参考答案（1）根结点是A。<br />（2）叶子结点是B、E、G、D。<br />（3）度是2。<br />（4）高度是4。<br />（5）C的孩子结点是E、F。

29.
简述顺序查找方法的基本思想。

参考答案顺序查找方法的基本思想是从顺序表头开始,用给定的目标与表中各记录的关键字值逐个进行比较。如果表中存在目标,则进行若干次比较后,一定能够找到目标。如果表中不存在目标,则比较到表尾也不会出现相等的情况。

四、算法阅读题

主观题不参与评分，请参考答案自行评分。

30.
阅读下列关于单链表L的算法,并回答问题:
题目图片
（1）指出fun（L）算法的功能。
（2）当L=（1,2,3,4,5,6,7,8,9）时,执行fun（L）后L的结果是什么?

参考答案（1）算法的功能是从前向后将单链表L中的奇数序号结点和相邻的偶数序号结点交换。<br />（2）L=（2,1,4,3,6,5,8,7,9）。

31.
阅读下列算法,并回答问题:
题目图片
（1）指出算法fun的功能。
（2）若a[0⋯7]={1,2,3,4,5,6,7,8},执行fun（a,8）后数组a的结果是什么?

参考答案（1）算法的功能是将含有n个整数的数组a中的所有奇数元素移到偶数元素的前面。<br />（2）数组a的结果是a[0⋯7]={1,3,5,7,2,4,6,8}。

32.
阅读下列算法（顺序栈的元素类型为ElemType）,并回答问题:
题目图片
（1）写出算法的执行步骤。
（2）指出算法的功能。

参考答案（1）步骤如下:建立一个临时栈tmps并初始化。退栈st中的所有元素,将不为x的元素进栈到tmps中。退栈tmps中的所有元素,并进栈到st中。销毁栈tmps。<br />（2）算法的功能是如果栈st中存在元素x,将其从栈中清除。

33.
阅读下列关于排序的算法,并回答问题:
题目图片
题目图片
（1）指出fun（a,n）算法的功能。
（2）当a[]={5,1,3,6,2,7,4,8}时,fun（a,8）共执行几趟排序?各趟的排序结果是什么?

参考答案（1）算法的功能是采用增量递减为1/3的希尔排序方法对a数组中的元素进行递增排序。<br />（2）执行两趟排序。<br />第一趟:2,1,3,6,4,7,5,8<br />第二趟:1,2,3,4,5,6,7,8

五、算法设计题

主观题不参与评分，请参考答案自行评分。

34.
假设无向图采用邻接表存储,设计一个算法,以深度优先搜索来求连通分量的个数并输出各连通分量的顶点集。

参考答案<img src="https://img.huikao8.com/huixue_img/importSubject/2065302572188700672.jpeg" alt="题目图片" style="max-width:100%;height:auto;vertical-align:middle;">