数据结构第七章考试题库[含答案]

数据结构试卷（一）王彬一、单选题（每题2 分，共20分）1.栈和队列的共同特点是( )。

A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进行插入运算时( ).A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中哪一个是非线性结构？( )A. 队列B. 栈C. 线性表D. 二叉树4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。

cA．688 B．678 C．692 D．6965.树最适合用来表示( )。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( d ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A. O（1）B. O（n）C. O（1og2n）D. O（n2）9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（ c d）个，A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

A.5B.6C.7D.8二、填空题（每空1分，共26分）1.通常从四个方面评价算法的质量：____ ____、________、________和_______。

2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。

一、单选题（每题 2 分，共20分）1.对一个算法的评价，不包括如下（B ）方面的内容。

A．健壮性和可读性B．并行性C．正确性D．时空复杂度2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。

A. p->next=HL->next; HL->next=p;B. p->next=HL; HL=p;C. p->next=HL; p=HL;D. HL=p; p->next=HL;3.对线性表，在下列哪种情况下应当采用链表表示？( )A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C )A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 35.AOV网是一种（）。

A．有向图B．无向图C．无向无环图D．有向无环图6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。

A．低于链接法处理冲突 B. 高于链接法处理冲突C．与链接法处理冲突相同D．高于二分查找7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。

A．值B．函数C．指针D．引用8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。

A．行号B．列号C．元素值D．非零元素个数9.快速排序在最坏情况下的时间复杂度为（）。

A．O(log2n) B．O(nlog2n)C．0(n) D．0(n2)10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。

A. O(n)B. O(1)C. O(log2n)D. O(n2)二、运算题（每题 6 分，共24分）1.数据结构是指数据及其相互之间的______________。

当结点之间存在M对N （M：N）的联系时，称这种结构为_____________________。

第七章图
1．下面是一个图的邻接表结构，画出此图，并根据此存储结构和深度优先搜索算法写出从C开始的深度优先搜索序列。

1
2
3
4
5
【解答】
A B F
C D E
C开始的深度优先搜索序列：CDEABF（唯一的结果）
2．假定要在某县所辖六个镇（含县城）之间修公路，若镇I和镇J 之间有可能通过道路连接，则Wij表示这条路的长度。

要求每个镇都通公路且所修公路总里程最短，那么应选择哪些线路来修。

(1).画出该图。

(2).用C语言描述该图的数组表示法存储结构，并注明你所使用变量
的实际含义。

(3).图示你所定义的数据结构。

(4).标识出你选择的线路。

【解答】 （1）
（2）
#define MAX 6 typedef struct {
char vexs[MAX]; // 顶点信息 int arcs[MAX][MAX]; // 边的信息
int vexnum, arcnum; // 顶点数，边数 } MGraph; （3）略
（4）{(1,3), (3,4), (2,4), (4,5), (5,6)}
3．图G 如下所示。

(1).给出该图的所有强连通分量。

(2).在图中删除弧<2,1>，然后写出从顶点1开始的拓扑有序序列。

5
4
6
1
3
2
4
15 10
2
15
20
30
4
10
10
【解答】
(1) 共4个强连通分量：
(2) 1,3,2,6,5,4。

数据结构试题及答案一、选择题（每题2分，共20分）1. 在数据结构中，线性结构的特点是元素之间存在一对一的线性关系。

以下哪个数据结构不属于线性结构？A. 栈B. 队列C. 树D. 链表答案：C2. 栈（Stack）是一种后进先出（LIFO）的数据结构，以下哪个操作不是栈的基本操作？A. PushB. PopC. TopD. Sort答案：D3. 在二叉树的遍历中，前序遍历的顺序是：A. 根-左-右B. 左-根-右C. 右-根-左D. 根-右-左答案：A4. 哈希表的冲突可以通过多种方法解决，以下哪个不是解决哈希表冲突的方法？A. 链地址法B. 开放地址法C. 再散列法D. 排序法答案：D5. 以下哪个排序算法是稳定的？A. 快速排序B. 堆排序C. 归并排序D. 选择排序答案：C6. 在图的遍历中，深度优先搜索（DFS）使用的是哪种数据结构来实现？A. 队列B. 栈C. 链表D. 哈希表答案：B7. 以下哪个是图的存储方式？A. 顺序存储B. 链式存储C. 散列表D. 矩阵存储答案：D8. 动态数组（如C++中的vector）在插入元素时可能需要进行的操作是：A. 原地扩展B. 复制元素C. 重新分配内存D. 释放内存答案：C9. 以下哪个不是算法的时间复杂度？A. O(1)B. O(log n)C. O(n^2)D. O(n!)答案：D10. 在查找算法中，二分查找法要求被查找的数据必须是：A. 无序的B. 有序的C. 随机分布的D. 唯一元素答案：B二、简答题（每题5分，共30分）1. 简述链表和数组的区别。

答案：链表和数组都是存储数据的线性数据结构，但它们在内存分配、访问方式、插入和删除操作等方面存在差异。

数组在内存中是连续存储的，可以通过索引快速访问任意元素，但插入和删除元素时可能需要移动大量元素。

链表在内存中是非连续存储的，每个元素包含数据和指向下一个元素的指针，不支持通过索引快速访问，但插入和删除操作只需要改变指针，不需要移动其他元素。

第7章 《图》习题参考答案一、单选题（每题1分，共16分）（ C ）1. 在一个图中，所有顶点的度数之和等于图的边数的倍。

A ．1/2 B. 1 C. 2 D. 4 （B ）2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。

A ．1/2 B. 1 C. 2 D. 4 （ B ）3. 有8个结点的无向图最多有条边。

A ．14 B. 28 C. 56 D. 112 （ C ）4. 有8个结点的无向连通图最少有条边。

A ．5 B. 6 C. 7 D. 8 （ C ）5. 有8个结点的有向完全图有条边。

A ．14 B. 28 C. 56 D. 112 （B ）6. 用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。

A ．栈 B. 队列 C. 树 D. 图 （ A ）7. 用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。

A ．栈 B. 队列 C. 树 D. 图（ C ）8. 已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是（ D ）9. 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按深度优先遍历的结点序列是A ． 0 2 4 3 1 5 6 B. 0 1 3 5 6 4 2 C. 0 4 2 3 1 6 5 D. 0 1 23465 （ D ）10. 已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是（ A ）11. 已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是A ．0 2 4 3 1 5 6B. 0 1 3 6 5 4 2C. 0 1 3 4 2 5 6D. 0 3 6 1 5 4 2⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡0100011101100001011010110011001000110010011011110A ．0 1 3 2 B. 0 2 3 1 C. 0 3 2 1 D. 0 1 2 3A．0 3 2 1 B. 0 1 2 3C. 0 1 3 2D. 0 3 1 2（A）12. 深度优先遍历类似于二叉树的A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历（D）13. 广度优先遍历类似于二叉树的A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历（A）14. 任何一个无向连通图的最小生成树A．只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在（注，生成树不唯一，但最小生成树唯一，即边权之和或树权最小的情况唯一）二、填空题（每空1分，共20分）1. 图有邻接矩阵、邻接表等存储结构，遍历图有深度优先遍历、广度优先遍历等方法。

第七章图（参考答案）7．1（1）邻接矩阵中非零元素的个数的一半为无向图的边数；（2）A[i][j]= =0为顶点，I 和j无边，否则j和j有边相通；（3）任一顶点I的度是第I行非0元素的个数。

7．2（1）任一顶点间均有通路，故是强连通；（2）简单路径V4 V3 V1 V2;（3）0 1 ∞ 1∞ 0 1 ∞1 ∞ 0 ∞∞∞ 1 0邻接矩阵邻接表（2）从顶点4开始的DFS序列：V5,V3,V4,V6,V2,V1（3）从顶点4开始的BFS序列：V4,V5,V3,V6,V1,V27．4（1）①adjlisttp g; vtxptr i,j; //全程变量② void dfs(vtxptr x)//从顶点x开始深度优先遍历图g。

在遍历中若发现顶点j，则说明顶点i和j间有路径。

{ visited[x]=1; //置访问标记if (y= =j){ found=1;exit(0);}//有通路，退出else { p=g[x].firstarc;//找x的第一邻接点while (p!=null){ k=p->adjvex;if （!visited[k]）dfs(k);p=p->nextarc;//下一邻接点}}③ void connect_DFS (adjlisttp g)//基于图的深度优先遍历策略，本算法判断一邻接表为存储结构的图g种，是否存在顶点i //到顶点j的路径。

设 1<=i ,j<=n,i<>j.{ visited[1..n]=0;found=0;scanf (&i,&j);dfs (i);if (found) printf （” 顶点”,i,”和顶点”,j,”有路径”）；else printf （” 顶点”,i,”和顶点”,j,”无路径”）；}// void connect_DFS(2)宽度优先遍历全程变量，调用函数与（1）相同，下面仅写宽度优先遍历部分。

习题71.填空题（1）由10000个结点构成的二叉排序树，在等概率查找的条件下，查找成功时的平均查找长度的最大值可能达到（___________）。

答案：5000.5（2）长度为11的有序序列：1，12，13，24，35，36，47，58，59，69，71进行等概率查找，如果采用顺序查找，则平均查找长度为（___________），如果采用二分查找，则平均查找长度为（___________），如果采用哈希查找，哈希表长为15，哈希函数为H（key）＝key%13，采用线性探测解决地址冲突，即d i=(H(key)+i)%15，则平均查找长度为（保留1位小数）（___________）。

答案：6，3，1.6（3）在折半查找中，查找终止的条件为（___________）。

答案：找到匹配元素或者low>high?（4）某索引顺序表共有元素275个，平均分成5块。

若先对索引表采用顺序查找，再对块元素进行顺序查找，则等概率情况下，分块查找成功的平均查找长度是（___________）。

答案：31（5）高度为8的平衡二叉树的结点数至少是（___________）。

答案： 54 计算公式：F(n)=F(n-1)+F(n-2)+1（6）对于这个序列{25，43，62，31，48，56}，采用的散列函数为H(k)=k%7，则元素48的同义词是（___________）。

答案：62（7）在各种查找方法中，平均查找长度与结点个数无关的查找方法是（___________）。

答案：散列查找（8）一个按元素值排好的顺序表（长度大于2），分别用顺序查找和折半查找与给定值相等的元素，平均比较次数分别是s和b，在查找成功的情况下，s和b的关系是（___________）；在查找不成功的情况下，s和b的关系是（___________）。

答案：(1)(2s-1)b=2s([log2(2s-1)]+1)-2[log2(2s-1)]+1+1(2)分两种情况考虑，见解答。

数据结构题库及答案详解一、选择题1. 在数据结构中，线性结构的特点是什么？A. 结构中存在唯一的开始结点和终端结点B. 结构中所有结点的前驱和后继都存在C. 结构中所有结点都只有一个直接前驱和一个直接后继D. 结构中存在多个开始结点和终端结点答案：C2. 栈是一种特殊的线性表，其特点是：A. 先进先出B. 先进后出C. 可以同时在两端进行插入和删除操作D. 只能在一端进行插入和删除操作答案：D3. 在二叉树的遍历算法中，先序遍历的顺序是：A. 先访问根结点，然后遍历左子树，最后遍历右子树B. 先遍历左子树，然后访问根结点，最后遍历右子树C. 先遍历右子树，然后访问根结点，最后遍历左子树D. 先遍历左右子树，最后访问根结点答案：A二、填空题4. 在图的遍历中，______算法可以避免重复访问同一顶点。

5. 哈希表的冲突可以通过______方法来解决。

答案：4. 深度优先搜索（DFS）5. 链地址法或开放地址法三、简答题6. 简述排序算法中的快速排序算法的基本原理。

答案：快速排序算法是一种分治算法，它通过选择一个元素作为“基准”，然后将数组分为两个子数组，一个包含小于基准的元素，另一个包含大于基准的元素。

然后对这两个子数组递归地应用快速排序算法。

7. 解释什么是递归，并给出一个递归函数的例子。

答案：递归是一种在函数中调用自身的编程技术。

递归函数必须有一个明确的终止条件，以避免无限递归。

例如，计算阶乘的递归函数如下：```int factorial(int n) {if (n == 0) return 1; // 终止条件return n * factorial(n - 1); // 递归调用}```四、编程题8. 编写一个函数，实现单链表的反转。

答案：```c// 假设ListNode是链表节点的定义ListNode* reverseList(ListNode* head) {ListNode* prev = NULL;ListNode* curr = head;ListNode* next = NULL;while (curr != NULL) {next = curr->next; // 保存下一个节点curr->next = prev; // 反转指针prev = curr; // 移动prevcurr = next; // 移动curr}return prev; // 新的头节点}```9. 给定一个整数数组，请实现一个函数来找到数组中的最长连续子序列的长度。

7_1对于图题7.1（P235）的无向图，给出：（1）表示该图的邻接矩阵。

（2）表示该图的邻接表。

（3）图中每个顶点的度。

解：（1）邻接矩阵：0111000100110010010101110111010100100110010001110（2）邻接表：1：2----3----4----NULL;2: 1----4----5----NULL;3: 1----4----6----NULL;4: 1----2----3----5----6----7----NULL;5: 2----4----7----NULL;6: 3----4----7----NULL;7: 4----5----6----NULL;（3）图中每个顶点的度分别为：3，3，3，6，3，3，3。

7_2对于图题7.1的无向图，给出：（1）从顶点1出发，按深度优先搜索法遍历图时所得到的顶点序（2）从顶点1出发，按广度优先法搜索法遍历图时所得到的顶点序列。

（1）DFS法：存储结构：本题采用邻接表作为图的存储结构，邻接表中的各个链表的结点形式由类型L_NODE规定，而各个链表的头指针存放在数组head中。

数组e中的元素e[0],e[1],…..,e[m-1]给出图中的m条边，e中结点形式由类型E_NODE规定。

visit[i]数组用来表示顶点i是否被访问过。

遍历前置visit各元素为0，若顶点i被访问过,则置visit[i]为1.算法分析：首先访问出发顶点v.接着，选择一个与v相邻接且未被访问过的的顶点w访问之，再从w 开始进行深度优先搜索。

每当到达一个其所有相邻接的顶点都被访问过的顶点，就从最后访问的顶点开始，依次退回到尚有邻接顶点未曾访问过的顶点u,并从u开始进行深度优先搜索。

这个过程进行到所有顶点都被访问过，或从任何一个已访问过的顶点出发，再也无法到达未曾访问过的顶点，则搜索过程就结束。

另一方面，先建立一个相应的具有n个顶点,m条边的无向图的邻接表。

数据结构考试题及答案一、选择题1. 以下哪种数据结构在实现栈时最为高效？A. 链表B. 数组C. 树D. 图答案：B2. 快速排序算法的时间复杂度在最坏情况下是多少？A. O(n)B. O(nlogn)C. O(n^2)D. O(n^3)答案：C3. 在二叉搜索树中，若要查找给定值的节点，应该按照以下哪种方式进行？A. 从根节点开始，向左或向右子树交替进行B. 从根节点开始，始终向左子树进行C. 从根节点开始，始终向右子树进行D. 从最底层节点开始向上进行答案：A4. 哈希表的主要优点是什么？A. 有序存储数据B. 高效的查找、插入和删除操作C. 动态扩容D. 消耗内存小答案：B5. 下面哪种数据结构通常用于实现高效的多对一映射？A. 数组B. 链表C. 哈希表D. 树答案：C二、填空题1. 在平衡树中，AVL树通过_________来保持树的平衡。

答案：旋转2. 堆数据结构通常用来实现_________等优先队列。

答案：最大/最小3. 拓扑排序是针对有向无环图(DAG)的一种排序算法，它能够反映出任务间的_________关系。

答案：依赖4. 广度优先搜索(BFS)算法使用_________数据结构来实现。

答案：队列5. 斐波那契数列可以通过递归算法、动态规划以及_________等方法来计算。

答案：矩阵快速幂三、简答题1. 请简述链表和数组的区别及各自的优缺点。

答案：链表由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

它的优点是能够在常数时间内在任意位置插入或删除元素，但随机访问效率较低。

数组是一段连续的内存空间，可以存储一系列相同类型的元素。

它的优点是支持高效的随机访问，但插入和删除操作通常需要移动大量元素，且大小固定或调整大小成本较高。

2. 描述二分查找的工作原理及其适用条件。

答案：二分查找是一种在有序数组中查找特定元素的算法。

它的工作原理是将数组分为两半，比较中间元素与目标值，如果相等则查找结束；如果目标值较小，则在左半部分继续查找；如果目标值较大，则在右半部分继续查找。

一、单选题C01、在一个图中，所有顶点的度数之和等于图的边数的倍。

A)1/2 B)1 C)2 D)4B02、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。

A)1/2 B)1 C)2 D)4B03、有8个结点的无向图最多有条边。

A)14 B)28 C)56 D)112C04、有8个结点的无向连通图最少有条边。

A)5 B)6 C)7 D)8C05、有8个结点的有向完全图有条边。

A)14 B)28 C)56 D)112B06、用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。

A)栈 B)队列 C)树 D)图A07、用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。

A)栈 B)队列 C)树 D)图A08、一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为。

A)O(n) B)O(e) C)O(n+e) D)O(n2)C09、已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是。

A)0 2 4 3 1 5 6 B)0 1 3 6 5 4 2 C)0 1 3 4 2 5 6 D)0 3 6 1 5 4 2B10、已知图的邻接矩阵同上题，根据算法，则从顶点0出发，按广度优先遍历的结点序列是。

A)0 2 4 3 6 5 1 B)0 1 2 3 4 6 5 C)0 4 2 3 1 5 6 D)0 1 3 4 2 5 6D11、已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是。

A)0 1 3 2 B)0 2 3 1 C)0 3 2 1 D)0 1 2 3A12、已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是。

A)0 3 2 1 B)0 1 2 3 C)0 1 3 2 D)0 3 1 2A13、图的深度优先遍历类似于二叉树的。

A)先序遍历 B)中序遍历 C)后序遍历 D)层次遍历D14、图的广度优先遍历类似于二叉树的。

第1章绪论一、选择题1. 算法的计算量的大小称为计算的（）。

【北京邮电大学2000 二、3 （20/8分）】A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（）【中科院计算所1998 二、1 （2分）】A．问题的规模 B. 待处理数据的初态 C. A和B3.计算机算法指的是（1），它必须具备（2）这三个特性。

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性【南京理工大学1999 一、1（2分）【武汉交通科技大学1996 一、1（4分）】4．一个算法应该是（）。

【中山大学1998 二、1（2分）】A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C.5. 下面关于算法说法错误的是（）【南京理工大学2000 一、1（1.5分）】A．算法最终必须由计算机程序实现B. 为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是（）【南京理工大学2000 一、2 （1.5分）】(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（）两大类。

【武汉交通科技大学1996 一、4（2分）】A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（）。

【北方交通大学2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈9．以下数据结构中，哪一个是线性结构（）？【北方交通大学2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串10．以下那一个术语与数据的存储结构无关？（）【北方交通大学2001 一、2（2分）】A．栈 B. 哈希表 C. 线索树 D. 双向链表11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学2001 一、10（3分）】FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A．O(2n) B．O(n) C．O(n2) D．O (log2n)12．程序段FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与A[j+1]对换；其中n为正整数，则最后一行的语句频度在最坏情况下是（）A. O（n）B. O(nlogn)C. O(n3)D. O(n2) 【南京理工大学1998一、1(2分)】13．以下哪个数据结构不是多型数据类型（）【中山大学1999 一、3（1分）】A．栈B．广义表C．有向图D．字符串14．以下数据结构中，（）是非线性数据结构【中山大学1999 一、4】A．树B．字符串C．队D．栈15. 下列数据中，（）是非线性数据结构。

数据结构的试题及答案一、选择题（每题2分，共10分）1. 在数据结构中，（）是数据元素之间的相互关系的集合。

A. 数据B. 结构C. 存储结构D. 逻辑结构答案：D2. 线性表的顺序存储结构中，存储元素的物理位置是（）。

A. 连续的B. 离散的C. 任意的D. 无关的答案：A3. 在二叉树的遍历方法中，先访问根节点，然后遍历左子树，最后遍历右子树的遍历方式是（）。

A. 前序遍历B. 中序遍历C. 后序遍历D. 层序遍历答案：A4. 哈希表的冲突解决方法中，（）是将所有发生冲突的元素存储在同一个链表中。

A. 线性探测B. 链地址法C. 再散列D. 双散列答案：B5. 在图的遍历算法中，深度优先搜索（DFS）算法使用的辅助数据结构是（）。

A. 栈B. 队列C. 链表D. 数组答案：A二、填空题（每题2分，共10分）1. 在数据结构中，算法的时间复杂度通常用（）表示。

答案：O(n)2. 一个栈的初始状态为空，依次执行了Push(1), Push(2), Pop(), Push(3), Pop()操作后，栈顶元素是（）。

答案：13. 在二叉搜索树中，对于任意节点，其左子树中的所有值都（）该节点的值。

答案：小于4. 哈希表的装载因子是表中已填入的元素个数与哈希表的（）之比。

答案：总容量5. 图的邻接矩阵表示法中，如果两个顶点之间有边相连，则对应的矩阵元素值为（）。

答案：1三、简答题（每题5分，共20分）1. 请简述什么是递归，并给出一个递归算法的例子。

答案：递归是一种算法设计技巧，它允许一个函数直接或间接地调用自身。

递归算法的例子是计算阶乘：n! = n * (n-1)!，其中n! = 1当n=0时。

2. 请解释什么是堆排序，并简述其基本步骤。

答案：堆排序是一种基于堆数据结构的比较排序算法。

基本步骤包括构建最大堆，然后重复移除堆顶元素并调整剩余元素以保持最大堆属性。

3. 请描述什么是图的广度优先搜索（BFS）算法，并给出其算法步骤。

第1章?????绪论一、选择题1.?算法的计算量的大小称为计算的（????）。

【北京邮电大学2000?二、3?（20/8分）】A．效率??????????B.?复杂性???????C.?现实性???????????D.?难度2.?算法的时间复杂度取决于（）【中科院计算所?1998?二、1?（2分）】A．问题的规模??????B.?待处理数据的初态??????C. A和B3.计算机算法指的是（1），它必须具备（2）这三个特性。

(1) A．计算方法?????B.?排序方法????????C.?解决问题的步骤序列??????D.?调度方法(2) A．可执行性、可移植性、可扩充性????B.?可执行性、确定性、有穷性C.?确定性、有穷性、稳定性??????????D.?易读性、稳定性、安全性??????【南京理工大学?1999?一、1（2分）【武汉交通科技大学?1996?一、1（?4分）】4．一个算法应该是（?????）。

【中山大学?1998?二、1（2分）】?????A．程序?????B．问题求解步骤的描述?????C．要满足五个基本特性????????D．A和C.5.?下面关于算法说法错误的是（????）【南京理工大学?2000?一、1（1.5分）】A．算法最终必须由计算机程序实现B.?为解决某问题的算法同为该问题编写的程序含义是相同的C.?算法的可行性是指指令不能有二义性??????????D.?以上几个都是错误的6.?下面说法错误的是（????）【南京理工大学?2000?一、2?（1.5分）】????(1）算法原地工作的含义是指不需要任何额外的辅助空间???（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法???（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界???（4）同一个算法，实现语言的级别越高，执行效率就越低?A．(1)??????B.(1),(2)????C.(1),(4)?????D.(3)7．从逻辑上可以把数据结构分为（????）两大类。

第1章绪论一、选择题1. 算法的计算量的大小称为计算的（）。

【北京邮电大学2000 二、3 （20/8分）】A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（）【中科院计算所1998 二、1 （2分）】A．问题的规模 B. 待处理数据的初态 C. A和B3.计算机算法指的是（1），它必须具备（2）这三个特性。

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性【南京理工大学1999 一、1（2分）【武汉交通科技大学1996 一、1（4分）】4．一个算法应该是（）。

【中山大学1998 二、1（2分）】A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C.5. 下面关于算法说法错误的是（）【南京理工大学2000 一、1（1.5分）】A．算法最终必须由计算机程序实现B. 为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是（）【南京理工大学2000 一、2 （1.5分）】(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（）两大类。

【武汉交通科技大学1996 一、4（2分）】A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（）。

【北方交通大学2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈9．以下数据结构中，哪一个是线性结构（）？【北方交通大学2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串10．以下那一个术语与数据的存储结构无关？（）【北方交通大学2001 一、2（2分）】A．栈 B. 哈希表 C. 线索树 D. 双向链表11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学2001 一、10（3分）】FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A．O(2n) B．O(n) C．O(n2) D．O (log2n)12．程序段FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与A[j+1]对换；其中n为正整数，则最后一行的语句频度在最坏情况下是（）A. O（n）B. O(nlogn)C. O(n3)D. O(n2) 【南京理工大学1998一、1(2分)】13．以下哪个数据结构不是多型数据类型（）【中山大学1999 一、3（1分）】A．栈B．广义表C．有向图D．字符串14．以下数据结构中，（）是非线性数据结构【中山大学1999 一、4】A．树B．字符串C．队D．栈15. 下列数据中，（）是非线性数据结构。

绪论一、填空题1.数据的逻辑结构被分为集合、(线性结构)、(树形结构)和(图状结构)四种。

2.物理结构是数据结构在计算机中的表示，又称为(存储结构)。

3.数据元素的逻辑结构包括( 线性)、(树)和图状结构3种类型，树形结构和图状结构合称为(非线性结构)。

4.(数据元素)是数据的基本单位，(数据项)是数据不可分割的最小单位。

5.线性结构中元素之间存在(一个对一个)关系，树形结构中元素之间存在(一个对多个)关系，图状结构中元素之间存在(多个对多个)关系。

6.数据结构是一门研究非数值计算的程序设计问题中：计算机的(数据元素)以及它们之间的(关系)和(运筹)等的学科。

7.算法的五个重要特性为有穷性、确定性、(输入)、(输出)和(可行性)。

二、选择题1.数据的不可分割的基本单位是(D)。

A.元素B.结点C.数据类型D.数据项*2.线性表的逻辑顺序与存储顺序总是一致的，这种说法(B)。

A.正确B.不正确C.不确定D.无法选择3.线性结构是指数据元素之间存在一种(D)。

A.一对多关系B.多对多关系C.多对一关系D.一对一关系4.在数据结构中，从逻辑上可以把数据结构分成(A)。

A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构5.线性表若采用链式存储结构时，要求内存中可用存储单元的地址( D)。

A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续不连续都可以三、简答题1.算法的特性是什么。

答：有穷性确定性可行性有0或多个输入有1或多个输出线性结构一、填空题1.在一个长度为n的线性表中删除第i个元素（1≤i≤n）时，需向前移动(n-i)个元素。

2.从循环队列中删除一个元素时，其操作是(先移动队首指针，后取出元素)。

3.在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为(p->next)。

4.在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时，首先把(p->next)的值赋给q->next，然后(q->date)的值赋给p->next。