📚 真题库

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

13003数据结构与算法 历年真题 共 34 题 1059 次浏览 更新于 2026-09-28
下载试卷（PDF）

一、单选题

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

1
下列任何两个结点之间都没有逻辑关系的是（　）
  • A.图形结构
  • B.线性结构
  • C.集合
  • D.树形结构
2
下列选项中，定义抽象数据类型时不需要做的事情是（　）
  • A.给出类型的名字
  • B.定义类型上的操作
  • C.实现类型上的操作
  • D.用某种语言描述抽象数据类型
3
在单链表L 中，已知q 所指结点是p 所指结点的前驱结点，next 是结点的指针域，若在q 和p 之间插入s 所指结点，则执行的操作是（　）
  • A.s->next=p->next;p->next=s;
  • B.p->next=s->next;s->next=p;
  • C.p->next=s;s->next=q;
  • D.q->next=s;s->next=p;
4
元素a 、b 、c 、d和e 依次进入初始为空的栈中，在所有可能的出栈序列中，以元素d 开头的序列个数是（　）
  • A.3
  • B.4
  • C.5
  • D.6
5
读入数据元素序列a，b，c，d，e，f，g 并入栈。下列选项中，不可能是出栈序列的是（　）
  • A.f，e，g，d，a，c，b
  • B.c，d，b，e，f，a，g
  • C.e，f，d，g，c，b，a
  • D.d，e，c，f，b，g，a
6
若以1，2，3，4作为双端队列的输入序列，则既不能由输入受限的双端队列得到，又不能由输出受限的双端队列得到的输出序列是（　）
  • A.1，2，3，4
  • B.4，1，3，2
  • C.4，2，3，1
  • D.4，2，1，3
7
广义表A=（a，b，（c，d），（e，（f，g）））， 则 Head（Tail（Head（Tail（Tail（A））））） 的值为（　）
  • A.（g）
  • B.（d）
  • C.c
  • D.d
8
若串S="software"， 其子串的数目是（　）
  • A.8
  • B.9
  • C.36
  • D.37
9
带头结点的单链表的头指针为head，表为空的判定条件是（　）
  • A.head==NULL;
  • B.head->next==NULL;
  • C.head!=NULL;
  • D.head->next==head;
10
稀疏矩阵的存储结构中，除存储三元组线性表的所有元素外，还包括（　）
  • A.稀疏矩阵的所有零元素及其位置
  • B.稀疏矩阵的行数、列数及非零元素的个数
  • C.三元组线性表元素之间的关系
  • D.矩阵元素的数据类型
11
对n 个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（　）
  • A.（n+1）/2
  • B.n/2
  • C.n
  • D.（1+n）*n/2
12
某二叉树的先序遍历序列是abdgcefh， 中序遍历序列是dgbaechf， 则其后序遍历序列是（　）
  • A.gdbehfca
  • B.abcdefgh
  • C.gdbaefch
  • D.ghbcdefa
13
在一个具有n 个顶点的有向图中，所有顶点的出度之和为d，则所有顶点的入度之和为（　）
  • A.n
  • B.d-1
  • C.d
  • D.d+1
14
对线性表进行二分查找时，要求线性表必须（　）
  • A.以顺序方式存储
  • B.以顺序方式存储且元素有序
  • C.以链式方式存储
  • D.以链式方式存储且元素有序
15
下列排序方法中，辅助空间为O（n）的是（　）
  • A.希尔排序
  • B.堆排序
  • C.选择排序
  • D.归并排序

二、填空题

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

16
在数据结构中，_____ 是数据元素之间存在着先后次序关系的结构。
17
设顺序表的每个元素占8个存储单元。若第1个元素的存储首地址为100，则第 6个元素占用的最后一个存储单元的地址 _____。
18
在数组中保存的链表称为 _____。
19
在图的存储结构中，链式存储结构以_____ 为代表。
20
广义表 G=（a，b，（c，d， （e，f）），g） 的长度为 _____。
21
链式队列采用带头指针及尾指针的 _____作为队列的存储结构。
22
一棵二叉树共有20个结点，其中叶结点为5个，则度为1的结点的个数是_____。
23
影响排序效率的两个因素是关键字的 _____次数和记录的移动次数。
24
若用起泡排序方法对序列11，15，27，29，42，53进行降序排序，则需要进行比较操作的次数是_____。
25
若连通图的顶点个数是n， 则该图的最小生成树的边数是 _____。

三、问答题

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

26
构造哈希函数时通常考虑的因素有哪些？
27
简述算法的五个特性。
28
若无向图G 中含有n 个顶点和e 条边，则它的邻接矩阵中0的个数是多少？
29
设5个元素1、2、3、4、5依次入栈，以push（x）表示x 入栈，pop（x）表示x 出栈，写出得到出栈序列2、1、4、3、5的操作过程。
30
程序的功能是返回指针 curr指向结点的位置，请在空白处填上适当内容以将算法补充完整。
题目图片
31
已知线性表的存储结构为顺序表，阅读下列算法，并回答问题：
题目图片
（1）设线性表 L=（19，-6，-9，26，0，-21，74，35，-30）， 写出执行 func （&L）后的 L 状态；
（2）简述算法 func的功能。
32
已知顺序表的表结构定义如下：
题目图片
（1）若顺序表R 的关键字序列为（3，6，15，28，53，70，115），分别写出X. key=19 和X. key=28 时，执行函数调用func（R，X，0，6） 的函数返回值；
（2）简述算法func 的功能。
33
阅读下列算法，并回答问题：
题目图片
（1）这是哪一种插入排序算法？该算法是否稳定？
（2）设置r[0]的作用是什么？
34
题目图片