《数据结构》是计算机类专业的核心课程，也是计算机科学与技术专业的考研课程。通过本课程的教学，培养学生的计算思维能力和算法设计与分析能力，为后续课程的学习打下坚实的基础；掌握算法性能分析方法，具有评估和优化算法性能的能力，能在多种算法中分析其优劣性，找到最佳的解决方案。
岭南师范学院数据结构(2025春)测试题答案
第 1章 数据结构概述
- 数据结构是一门研究非数值计算的程序设计问题中计算机的____以及它们之间的____和运算等的学科。…
- 数据结构被形式地定义为(D, R),其中D是____的有限集合,R是D上的____有限集合。…
- 数据结构包括数据的____、数据的____和数据的____这三个方面的内容。 …
- 数据结构按逻辑结构可分为两大类,它们分别是____和____ 。 …
- 一个算法的效率可分为____效率和____效率。
- 非线性结构是数据元素之间存在一种( ) A 一对多关系 B 多对多关系 C 多对一关系 D 一对…
- 数据结构中,与所使用的计算机无关的是数据的( )结构; A 存储 B 物理 C 逻辑 D 物理和存…
- 算法分析的目的是( ) A 找出数据结构的合理性 B 研究算法中的输入和输出的关系 C 分析算法…
- 算法分析的两个主要方面是( ) A 空间复杂性和时间复杂性 B 正确性和简明性 C 可读性和文档…
- 计算机算法指的是( ) A 计算方法 B 排序方法 C 解决问题的有限运算序列 D 调度方法…
- 计算机算法必须具备输入、输出和( )等5个特性。 A 可行性、可移植性和可扩充性 B 可行性、确…
第 2 章 线性表
- 线性表中结点的集合是____的,结点间的关系是 ____的。
- 向一个长度为n的向量的第i个元素1≤i≤n+1之前插入一个元素时,需向后移动____个元素。 …
- 向一个长度为n的向量中删除第i个元素(1≤i≤n)时,需向前移动____个元素。 …
- 在顺序表中访问任意一结点的时间复杂度均为____ ,因此,顺序表也称为____的数据结构。 …
- 数据在计算机存储器内表示时,物理地址与逻辑地址相同并且是连续的,称之为:( ) A 存储结构 B …
- 一个向量第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是( ) A 110 B 108…
- 在n个结点的顺序表中,算法的时间复杂度是O(1)的操作是:( ) A 访问第i个结点(1≤i≤n)和求第i个…
- 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移动( )个元素 A 8 B …
- 链接存储的存储结构所占存储空间( ) A 分两部分，一部分存放结点值，另一部分存放表示结…
- 链表是一种采用( )存储结构存储的线性表; A 顺序 B 链式 C 星式 D 网状…
- 线性表若采用链式存储结构时,要求内存中可用存储单元的地址:( ) A 必须是连续的 B 部分地址…
- 线性表L在( )情况下适用于使用链式结构实现。 A 需经常修改L中的结点值 B 需不断对L进行删除…
- 单链表的存储密度( ) A 大于1 B 等于1; C 小于1 D 不能确定
- 设a1、a2、a3为3个结点,整数P0,3,4代表地址,则如下的链式存储结构称为(） A 循环链表 B 单…
第 3 章 栈与队列
- 栈是一种特殊的线性表,允许插入和删除运算的一端称为___
- ____是被限定为只能在表的一端进行插入运算,在表的另一端进行删除运算的线性表。…
- 向栈中压入元素的操作是先____,后____
- 从循环队列中删除一个元素时,其操作是先____,后____。
- 栈中元素的进出原则是( ) A 先进先出 B 后进先出 C 栈空则进 D 栈满则出 …
- 若已知一个栈的入栈序列是1,2,3,…,n,其输出序列为p1,p2,p3,…,pn,若p1=n,则pi为( ) A i B n…
- 判定一个栈ST(最多元素为m0)为空的条件是( ) A ST->top<>0B.ST->top=0 B ST->top=m0 C…
- 判定一个循环队列QU（最多元素为m0）为满队列的条件是（ ） A QU->rear － QU->front = = m0 B …
- 数组Q[n]用来表示一个循环队列,f为当前队列头元素的位置,r为队尾元素的下一个位置,假定队列中元…
第 4 章 串
- 设S=“A;/document/Mary.doc”,则strlen(s)=____, “/”的字符定位的位置为____。…
- 子串的定位运算称为串的模式匹配;____称为目标串,____称为模式。
- 设目标T=”abccdcdccbaa”,模式P=“cdcc”,则第____次匹配成功。
- 素A47的第一个字节地址为____。
- 设数组a[1…60, 1…70]的基地址为2048,每个元素占2个存储单元,若以列序为主序顺序存储,则元素a[3…
- 求下列广义表操作的结果: (1)GetHead【((a,b),(c,d))】===____; //头元素不必加括号 …
- 有一个二维数组A,行下标的范围是1到6,列下标的范围是0到7,每个数组元素用相邻的6个字节存储,存储…
- 假设有60行70列的二维数组a[1…60, 1…70]以列序为主序顺序存储,其基地址为10000,每个元素占2个…
- 设矩阵A是一个对称矩阵,为了节省存储,将其下三角部分(如下图所示)按行序存放在一维数组B[ 1, n(n…
- 设有两个串p和q,求q在p中首次出现的位置的运算称作:( ) A 连接 B 模式匹配 C 求子串 D …
- 设串s1=’ABCDEFG’,s2=’PQRST’,函数con(x,y)返回x和y串的连接串,subs(s, i, j)返回串s的从序…
第 5 章 数组和广义表
- 假设以行序为主序存储二维数组A=array[1..100,1..100]，设每个数据元素占2个存储单元，基地址为10，则L…
- 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存…
- 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占…
- 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数…
- 二维数组A的每个元素是由10个字符组成的串，其行下标i=0,1,…,8,列下标j=1,2,…,10。若A按行先存储…
- 设二维数组A[1.. m，1.. n]（即m行n列）按行存储在数组B[1.. m*n]中，则二维数组元素A[i,j]在一维数组B中…
- 数组A[0..4,-1..-3,5..7]中含有元素的个数（ ）。 A 55 B 45 C 36 D …
- 广义表A=(a,b,(c,d),(e,(f,g)))，则Head(Tail(Head(Tail(Tail(A)))))的值为（ ）。 A (g) …
- 设广义表L=((a,b,c))，则L的长度和深度分别为（ ）。 A 1和1 B 1和3 C 1和2 D 2和3…
- 广义表((a,b,c,d))的表头是____，表尾是____。
第 6 章 树
- 由3个结点所构成的二叉树有____种形态。
- 一棵深度为6的满二叉树有____)个分支结点和____个叶子。
- 一棵具有 2 5 7个结点的完全二叉树,它的深度为（____）。
- 设一棵完全二叉树有700个结点,则共有((____))个叶子结点。
- 用5个权值{3, 2, 4, 5, 1}构造的哈夫曼（Huffman）树的带权路径长度是 ____…
- 树是结点的有限集合，它____根结点，记为T。其余的结点分成为m（m≥0）个____ 的集合T1，T2，…，Tm，每个集合又…
- 二叉树____。在完全的二叉树中，若一个结点没有____，则它必定是叶结点。每棵树都能惟一地转换成与它…
- 把一棵树转换为二叉树后,这棵二叉树的形态是( )。 A 唯一的 B 有多种 C 有多种,但根…
第7章 图
- 在一个图中,所有顶点的度数之和等于图的边数的( )倍。 A 1/2 B 1 C 2 D 4…
- 在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的( )倍。 A 1/2 B 1 C 2 D 4…
- 有8个结点的无向图最多有( )条边。 A 14 B 28 C 56 D 112
- 有8个结点的有向完全图有( )条边。 A 14 B 28 C 56 D 112
- 用邻接表表示图进行广度优先遍历时,通常是采用( )来实现算法的。 A 栈 B 队列 C 树 D 图…
- 用邻接表表示图进行深度优先遍历时,通常是采用( )来实现算法的。 A 栈 B 队列 C 树 D 图…
- 深度优先遍历类似于二叉树的( ) A 先序遍历 B 中序遍历 C 后序遍历 D 层次遍历…
- 图有____ 、 ____ 等存储结构,遍历图有____ 、____等方法。
- 有向图G用邻接矩阵存储,其第i行的所有元素之和等于顶点i的____ 。 …
- n个顶点e条边的图,若采用邻接矩阵存储,则空间复杂度为____ 。
- n个顶点e条边的图,若采用邻接表存储,则空间复杂度为____ 。
- 设有一稀疏图G,则G采用____存储较省空间。
- 设有一稠密图G,则G采用____存储较省空间。
- 图的逆邻接表存储结构只适用于____图。
- 图的深度优先遍历序列____惟一的。
- 若要求一个稀疏图G的最小生成树,最好用____算法来求解。
- 若要求一个稠密图G的最小生成树,最好用____ 算法来求解。
- 拓扑排序算法是通过重复选择具有____ 个前驱顶点的过程来完成的。 …
第 8 章 查 找
- 在数据的存放无规律而言的线性表中进行检索的最佳方法是____。
- 线性有序表（a1，a2，a3，…，a256)是从小到大排列的,对一个给定的值k,用二分法检索表中与k相等的元素,在查…
- 假设在有序线性表a[20]上进行折半查找,则比较一次查找成功的结点数为1;比较两次查找成功的结点数…
- 折半查找有序表(4,6,12,20,28,38,50,70,88,100),若查找表中元素20,它将依次与表中元素____比较大…
- 在各种查找方法中,平均查找长度与结点个数n无关的查找方法是____。
- 哈希表存储的基本思想是由____决定数据的存储地址。
- 在表长为n的链表中进行线性查找,它的平均查找长度为( ) A ASL=n; B ASL=(n+1)/2; C ASL…
- 折半查找有序表(4,6,10,12,20,30,50,70,88,100)。若查找表中元素58,则它将依次与表中( …
- 链表适用于( )查找 A 顺序 B 二分法 C 顺序,也能二分法 D 随机…
- 要进行顺序查找，则线性表____；要进行二分查找，则线性表____；要进行散列查找，则线性表____。 某顺序存…
- 数据结构反映了数据元素之间的结构关系。链表是一种____，它对于数据元素的插入和删除____。通常查…
- 在二叉排序树中，每个结点的关键码值____ ，____一棵二叉排序，即可得到排序序列。同一个结点集合，可用…
- 哈希表存储的基本思想是根据____来决定 ____ ，碰撞（冲突）指的是____，处理碰撞的两类主要方法是 ____ …
- 考虑具有如下性质的二叉树：除叶子结点外，每个结点的值都大于其左子树上的一切结点的值。并小于等于…
- 假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题： （1） 画出描述折半查找过程的判定…
- 设哈希（Hash）表的地址范围为0～17，哈希函数为：H（K）＝K MOD 16。 K为关键字，用线性探测法再散列法处理冲…
- 在一棵空的二叉查找树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉查找树。…
第 9 章 排 序
- 以下给定的序列中( )是一个堆。 97,43,37,85,13,65 13,85,37,43,97,65 13,65,43,97,37,8…
- 排序时扫描待排序记录序列,顺次比较相邻的两个元素的大小,逆序时就交换位置。这 是( )排…
- 堆是一种特殊的数据结构,以下给定的序列中( )是一个大顶堆。 A 19,34,26,97,56,75 B 97…
- 外排序是指( )。 A 用机器指令直接对硬盘中需排序数据排序。 B 把需排序数据,用其他大…
- 以下给出的四种排序方法中,（ )是非稳定的排序方法。 A 直接插入排序 B 希尔(Shell)排序 …
- 给定一个递增有序的整型数组a,如下所示。 若用折半查找方法查找值为14的元素,则查找…
- 排序时扫描待排序序列,依次比较相邻的两个元素的大小,逆序时就交换位置。这是( )排序方法的…
- 给定元素序列(46,79,56,38,40,80),则以第一个元素为主元得到的第一趟快速排序后的结果为( )…
- 排序时,首先从待排序序列中选出一个元素作为枢轴元素,使得经过一趟特殊的分化处理后将原序列划分…
- 一组元素序列为(48,75,52,35,42,88),利用快速排序方法对其进行递增排序,以第一个元素为枢轴(主元…