下载文档原格式
7.1 选择题1. 对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为()A) O(n)B)O(n+e)C) O(n*n)D)O(n*n*n)【答案】B2. 设无向图的顶点个数为n,则该图最多有()条边。
A) n-1B)n(n-1)/2C)n(n+1)/2【答案】B3. 连通分量指的是()A) 无向图中的极小连通子图B) 无向图中的极大连通子图C) 有向图中的极小连通子图D) 有向图中的极大连通子图【答案】B4. n 个结点的完全有向图含有边的数目()A) n*n B) n(n+1) C) n/2【答案】D5. 关键路径是()A) AOE网中从源点到汇点的最长路径B) AOE网中从源点到汇点的最短路径C) AOV网中从源点到汇点的最长路径D) n2D) n* (n-1)D) AOV网中从源点到汇点的最短路径【答案】 A 6．有向图中一个顶点的度是该顶点的()A)入度B)出度C)入度与出度之和D)(入度+出度)12【答案】C7．有e 条边的无向图，若用邻接表存储，表中有()边结点。
A) e B) 2eC) e-1D) 2(e-1)【答案】B8．实现图的广度优先搜索算法需使用的辅助数据结构为()A)栈B)队列C)二叉树D)树【答案】B9．实现图的非递归深度优先搜索算法需使用的辅助数据结构为()A)栈B)队列C)二叉树D)树【答案】 A 10．存储无向图的邻接矩阵一定是一个()A)上三角矩阵B)稀疏矩阵C)对称矩阵D)对角矩阵【答案】C11．在一个有向图中所有顶点的入度之和等于出度之和的()倍A) B) 1C) 2D) 4答案】B12．在图采用邻接表存储时，求最小生成树的Prim 算法的时间复杂度为(A) O(n)B) O(n+e)C 0(n2)D) 0(n3))【答案】B13 .下列关于AOE网的叙述中，不正确的是()A) 关键活动不按期完成就会影响整个工程的完成时间B) 任何一个关键活动提前完成，那么整个工程将会提前完成C) 所有的关键活动提前完成，那么整个工程将会提前完成D) 某些关键活动提前完成，那么整个工程将会提前完成【答案】B14. 具有10 个顶点的无向图至少有多少条边才能保证连通()A ) 9B) 10C) 11D) 12【答案】A15. 在含n 个顶点和e 条边的无向图的邻接矩阵中，零元素的个数为()A)e B)2eC)n2-e D)n2-2e【答案】D7.2 填空题1 .无向图中所有顶点的度数之和等于所有边数的________________ 倍。
7.1选择题1．对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为（）A）O(n)B）O(n+e)C）O(n*n)D）O(n*n*n)【答案】B2．设无向图的顶点个数为n，则该图最多有（）条边。
A）n-1B）n(n-1)/2C）n(n+1)/2【答案】B3．连通分量指的是（）A）无向图中的极小连通子图B）无向图中的极大连通子图C）有向图中的极小连通子图D）有向图中的极大连通子图【答案】B4．n个结点的完全有向图含有边的数目（）A）n*n B）n（n+1）C）n/2【答案】D5．关键路径是（）A）AOE网中从源点到汇点的最长路径B）AOE网中从源点到汇点的最短路径C）AOV网中从源点到汇点的最长路径D）n2D）n*（n-1）D）AOV网中从源点到汇点的最短路径【答案】A6．有向图中一个顶点的度是该顶点的（）A）入度B）出度C）入度与出度之和D）（入度+出度）/2【答案】C7．有e条边的无向图，若用邻接表存储，表中有（）边结点。
A）e B）2eC）e-1D）2(e-1)【答案】B8．实现图的广度优先搜索算法需使用的辅助数据结构为（）A）栈B）队列C）二叉树D）树【答案】B9．实现图的非递归深度优先搜索算法需使用的辅助数据结构为（）A）栈B）队列C）二叉树D）树【答案】A10．存储无向图的邻接矩阵一定是一个（）A）上三角矩阵B）稀疏矩阵C）对称矩阵D）对角矩阵【答案】C11．在一个有向图中所有顶点的入度之和等于出度之和的（）倍A）B）1C）2D）4【答案】B12．在图采用邻接表存储时，求最小生成树的Prim 算法的时间复杂度为（A）O(n)B）O(n+e)C）O(n2)D）O(n3)）【答案】B13．下列关于AOE网的叙述中，不正确的是（）A）关键活动不按期完成就会影响整个工程的完成时间B）任何一个关键活动提前完成，那么整个工程将会提前完成C）所有的关键活动提前完成，那么整个工程将会提前完成D）某些关键活动提前完成，那么整个工程将会提前完成【答案】B14．具有10个顶点的无向图至少有多少条边才能保证连通（）A）9B）10C）11D）12【答案】A15．在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）A）e B）2eC）n2-e D）n2-2e【答案】D7.2填空题1．无向图中所有顶点的度数之和等于所有边数的_____________倍。
数据结构习题（7,8,9章）第七章图⼀．选择题1．n个顶点，e条边的有向图的邻接矩阵中⾮零元素有个。
A.nB.2eC.eD.n+e2．⽤邻接表存储图所⽤的空间⼤⼩（）A．与图的顶点数和边数都有关B．只与图的边数有关C．只与图的顶点数有关D．与边数的平⽅有关3．有n 条边的⽆向图的邻接表存储法中，链边中结点的个数是（）个。
A．n B．2n C．n/2 D．n*n4．⼀个带权⽆向连通图的最⼩⽣成树（）。
A．有⼀棵或多棵. B．只有⼀棵C．⼀定有多棵D．可能不存在5．若⼀个图中包含有k个连通分量，若要按照深度优先搜索的⽅法访问所有顶点，则必须调⽤( )次深度优先搜索遍历的算法。
A．k B．1 C．k-1 D．k+1⼆．如下所⽰有向图：1．请给出每个顶点的度，⼊度和出度。
2．请画出其邻接矩阵、邻接表、逆邻接表、⼗字链表。
三．试对下图所⽰的AOE⽹络，解答下列问题。
1．求每个事件的最早发⽣时间ve [i]和最迟发⽣时间vl[i]。
2．求每个活动的最早开始时间ee(s)和最迟开始时间el(s)。
3．指出哪些活动加速可使整个⼯程提前完成。
四．写出下图所⽰的AOV⽹的所有拓扑有序序列。
第⼋章查找⼀．填空题1．采⽤⼆分法进⾏查找的查找表，应选择____________________⽅式的存储结构2．设在有序表A[0……9]中进⾏⼆分查找，⽐较⼀次查找成功的结点数为_____，⽐较⼆次查找成功的结点数为______，⽐较三次查找成功的结点数为_____，⽐较四次查找成功的结点数为_____，⽐较五次查找成功的结点数为_____，平均查找长度为______。
⼆．选择题1．对线性表进⾏⼆分查找时，要求线性表必须（）A．键值有序的链接表B．键值有序的顺序表C．链接表但键值不⼀定有序D．顺序但键值不⼀定有序2．有⼀个有序表{1，4，6，10，18，35，42，53，67，71，78，84，92，99},当⽤⼆分查找法查找键值为84的结点时，经（）⽐较后查找成功。
数据结构练习题习题1 绪论1.1 单项选择题1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①、数据信息在计算机中的②以及一组相关的运算等的课程。
① A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象② A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是①的有限集合，R是D上的②有限集合。
① A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象② A．操作Ｂ．映象Ｃ．存储Ｄ．关系3. 在数据结构中，从逻辑上可以把数据结构分成。
A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构4. 算法分析的目的是①，算法分析的两个主要方面是②。
① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进D. 分析算法的易懂性和文档性② A. 空间复杂性和时间复杂性 B. 正确性和简明性C. 可读性和文档性D. 数据复杂性和程序复杂性5. 计算机算法指的是①，它必具备输入、输出和②等五个特性。
① A. 计算方法 B. 排序方法C. 解决问题的有限运算序列D. 调度方法② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性C. 确定性、有穷性和稳定性D. 易读性、稳定性和安全性1.2 填空题（将正确的答案填在相应的空中）1. 数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。
2. 在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。
3. 在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。
4. 在图形结构中，每个结点的前驱结点数和后续结点数可以。
5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。
第七章图一、选择题1．图中有关路径的定义是（）。
A．由顶点和相邻顶点序偶构成的边所形成的序列B．由不同顶点所形成的序列C．由不同边所形成的序列D．上述定义都不是2．设无向图的顶点个数为n，则该图最多有（）条边。
A．n-1 B．n(n-1)/2 C．n(n+1)/2 D．0 E．n23．一个n个顶点的连通无向图，其边的个数至少为（）。
A．n-1 B．n C．n+1 D．nlogn；4．要连通具有n个顶点的有向图，至少需要（）条边。
A．n-l B．n C．n+l D．2n5．一个有n个结点的图，最少有（B ）个连通分量，最多有（D ）个连通分量。
A．0 B．1 C．n-1 D．n6. 下列说法不正确的是（）。
A．图的遍历是从给定的源点出发每一个顶点仅被访问一次C．图的深度遍历不适用于有向图B．遍历的基本算法有两种：深度遍历和广度遍历D．图的深度遍历是一个递归过程7．无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。
A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b8. 在图采用邻接表存储时，求最小生成树的Prim 算法的时间复杂度为( )。
A. O(n)B. O(n+e)C. O(n2)D. O(n3)9. 求解最短路径的Floyd算法的时间复杂度为( )。
A．O（n） B. O（n+c） C. O（n*n）D. O（n*n*n）10．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓扑序列是（）。
《数据结构》第1-2章练习题一、选择1、通常从正确性、易读性、健壮性、高效性等四个方面评价算法(包括程序)的质量。
以下解释错误的是( )A、正确性算法应能正确地实现预定的功能(即处理要求)B、易读性算法应易于阅读和理解以便于调试修改和扩充C、健壮性当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需要的运行结果D、高效性即达到所需要的时间性能2、以下说法正确的是 ( )A、数据元素是数据的最小单位B、数据项是数据的基本单位C、数据结构是带有结构的各数据项的集合D、数据结构是带有结构的数据元素的集合3、对于顺序表，以下说法错误的是（）A、顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址B、顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列C、顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻D、顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中数组的下标可以看成是元素的相对地址4、对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（）为标准操作A、条件判断B、结点移动C、算术表达式D、赋值语句5、对于顺序表的优缺点，以下说法错误的是（）A、无需为表示结点间的逻辑关系而增加额外的存储空间B、可以方便地随机存取表中的任一结点C、插入和删除运算较方便D、容易造成一部分空间长期闲置而得不到充分利用6、链表不具有的特点是：A、可随机访问任一个元素B、插入删除不需要移动元素C、不必事先估计存储空间D、所需空间与线性表长度成正比7、若线性表最常用的操作是存取第i个元素及其前驱的值，则采用（）存储方式节省时间A、单链表B、双向链表C、单循环链表D、顺序表顺序表可以随机存取8、设指针P指向双链表的某一结点，则双链表结构的对称性可用（）式来刻画A、p->prior->next->==p->next->nextB、p->prior->prior->==p->next->priorC、p->prior->next->==p->next->priorD、p->next->next==p->prior->prior9、以下说错误的是（）A、对循环来说，从表中任一结点出发都能通过前后操作而扫描整个循环链表B、对单链表来说，只有从头结点开始才能扫描表中全部结点C、双链表的特点是找结点的前趋和后继都很容易D、对双链表来说，结点*P的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针域中。
一、选择题1. 已知某算法的执行时间为（n3+n2+n）log2(n+2)，n为问题规模，则该算法的时间复杂度是（）。
A．O(n) B．O(n2) C．O(log2n) D．O(n3log2n)2．设有二维数组A[50][60]，其元素长度为1字节，按列优先顺序存储，首元素A[0][0]的地址为200，则元素A[10][20]的存储地址为( )。
A．820 B．720 C．1210 D．14103．设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6先后进入栈S，一个元素出栈后即进入队列Q，若6个元素的出队顺序是e2,e4,e3,e6,e5,e1，则栈S至少可以容纳（）个元素。
A．3 B．4 C．5 D．64．串是。
A）不少于一个字母的序列B）任意个字母的序列C）不少于一个字符的序列D）有限个字符的序列5．A，B，C，D依次入栈，则不可能的出栈序列是。
A）A，B，C，D C）D，C，B，AB）A，C，D，B D）D，A，B，C6．栈和队列的共同点是。
A）都是先进后出B）都是先进先出C）只允许在端点处插入和删除D）都采用顺序方式存储7．下面关于线性表的叙述中，错误的是。
A）线性表采用顺序方式存储，必须占用一片连续的存储单元B）线性表采用链式存储，便于进行插入和删除操作C）线性表采用链式存储，不必占用一片连续的存储单元D）线性表采用顺序方式存储，便于进行插入和删除操作8．广义表A=（（a,b,c），（d,e,f）），从A中取出原子e的运算是。
A）tail(head(A)) B）head(tail(tail(head(A))))C）head(tail(A)) D）head(tail(head(tail(A))))9．判定一个指针ST指向的顺序栈（栈中最多元素为M个）为栈满的条件是。
A）ST->top!=0 B）ST->top==0C）ST->top!=M-1 D）ST->top==M-110．指针head指向一个非空循环单链表的头结点，指针p指向该链表的尾结点的条件是。
数据结构章节练习题第一章绪论一、单选题1.一个数组元素a[i]与________的表示等价。
A、 *(a+i)B、 a+iC、 *a+iD、 &a+i2.下面程序段的时间复杂度为____________。
for(int i=0; i<m; i++)for(int j=0; j<n; j++)a[i][j]=i*j;A、 O(m2)B、 O(n2)C、 O(m*n)D、 O(m+n)3.执行下面程序段时，执行S语句的次数为____________。
for(int i=1; i<=n; i++)for(int j=1; j<=i; j++)S;A、 n2B、 n2/2C、 n(n+1)D、 n(n+1)/24.下面算法的时间复杂度为____________。
int f( unsigned int n ){ if ( n==0 || n==1 ) return 1; else return n*f(n-1); }A、 O(1)B、 O(n)C、 O(n2)D、 O(n!)二、填空题1.数据的逻辑结构被分为__________、_________、__________和__________四种。
2.数据的存储结构被分为__________、和__________两种。
3.在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着________、________和________的联系。
4.一种抽象数据类型包括__________和__________两个部分。
5.当一个形参类型的长度较大时，应最好说明为_________，以节省参数值的传输时间和存储参数的空间。
6.当需要用一个形参访问对应的实参时，则该形参应说明为__________。
7.在函数中对引用形参的修改就是对相应__________的修改，对__________形参的修改只局限在该函数的内部，不会反映到对应的实参上。
数据结构练习题(含答案)数据结构练习题(含答案)一、单项选择题1. 在数组中插入和删除元素最慢的时间复杂度是：A. O(1)B. O(log n)C. O(n)D. O(n^2)答案：C2. 在链表中插入和删除元素最慢的时间复杂度是：A. O(1)B. O(log n)C. O(n)D. O(n^2)答案：A3. 下列哪种数据结构采用了“先进先出”的存储方式：A. 栈B. 队列D. 二叉树答案：B4. 下列哪种数据结构采用了“先进后出”的存储方式：A. 栈B. 队列C. 哈希表D. 二叉树答案：A5. 以下哪种排序算法的时间复杂度最好：A. 冒泡排序B. 插入排序C. 快速排序D. 选择排序答案：C二、填空题1. 假设有一个长度为10的数组arr，要访问第7个元素，应该使用arr[]表示。
2. 栈的特点是后进先出，所以从栈中取出第一个元素需要调用的操作是。
答案：pop3. 结点的度可以理解为：答案：与该结点相连的边的数目4. 图中的结点称为：答案：顶点5. 在二叉树中，度为 2 的结点称为。
答案：内部结点三、编程题1. 使用Python编写代码，实现冒泡排序算法，并对以下数组进行排序：[5, 2, 9, 1, 3, 6, 8, 7, 4]答案：```pythondef bubble_sort(arr):n = len(arr)for i in range(n):for j in range(0, n-i-1):if arr[j] > arr[j+1]:arr[j], arr[j+1] = arr[j+1], arr[j]arr = [5, 2, 9, 1, 3, 6, 8, 7, 4]bubble_sort(arr)print(arr)```2. 使用Java编写代码，实现队列的基本操作：入队（enqueue）、出队（dequeue）、查看队首元素（peek）。
答案：```javaimport java.util.LinkedList;import java.util.Queue;public class QueueExample {public static void main(String[] args) {Queue<Integer> queue = new LinkedList<>();// 入队queue.offer(1);queue.offer(2);queue.offer(3);// 出队System.out.println(queue.poll()); // 1// 查看队首元素System.out.println(queue.peek()); // 2}}```四、问答题1. 请简要解释数组和链表的区别和应用场景。
第7章排序算法1. 请简述排序的作用。
排序的作用是将一个待排序元素集合按关键字递增（或递减）顺序整理为一个有序序列。
2. 请简述稳定排序和不稳定排序的含义。
若采用某种排序算法对任一组元素进行排序，在排序前后，那些具有相同关键字值的元素之间的相对次序都保持不变，则将这种排序算法称为是稳定的，否则称为是不稳定的。
3. 请简述各种排序算法的适用范围。
排序算法的适用范围如下：（a）直接插入排序、简单选择排序和冒泡排序都是简单排序算法，它们的时间复杂度和空间复杂度分别为O(n2)和O(1)。
若待排序元素数量n较小，可以选用直接插入排序和冒泡排序。
另外，当待排序元素基本有序时，也应选用直接插入排序和冒泡排序，此时时间复杂度都能达到O(n)。
若元素本身数据量较大，元素移动操作代价较高，则应选用平均移动元素次数最少的简单选择排序。
希尔排序是对直接插入排序算法的改进，大大降低了时间复杂度，但它是一种不稳定的排序算法。
（b）堆排序、快速排序和归并排序主要适用于待排序元素数量n较大的情况，当待排序元素数量n较小时，它们的性能有可能劣于简单排序算法。
因此，在实际应用时，快速排序算法和归并排序算法经常与简单排序算法结合使用（例如，可以先用快速排序算法将集合划分为规模更小的子集合，对于元素数量较小的子集合，则用直接插入排序算法进行排序）。
在所有平均时间复杂度为O(nlog2n)的算法中，尽管快速排序在最坏情况下时间复杂度较高，但它通常被认为是平均性能最好的一种算法，并且通过优化可以降低最坏情况出现的概率。
归并排序是一种稳定的排序算法，其时间性能一般要优于堆排序，但它所需要的辅助空间较多，当应用环境要求排序前后具有相同值的元素相对次序不能改变时可以考虑使用。
堆排序所需的辅助空间最少，当可用空间非常有限时可以考虑使用。
（c）箱排序和基数排序的时间复杂度最低，但它们的空间复杂度最高。
箱排序主要适用于待排序元素长度（即d值）较小的情况，在实际中应用不多；基数排序是箱排序的改进，主要适用于整数或字符串的排序，或者与其他排序算法结合进行实数的排序（例如，可以先用基数排序算法按整数部分将元素分成若干个子集合，再对每个子集合应用直接插入排序算法进行排序）。
数据结构练习题一、线性表1. 判断题（1）线性表是线性结构，只能顺序存储。
（2）循环链表中有一个节点的指针指向头节点。
（3）在单链表中，删除节点的时间复杂度为O(1)。
（4）双向链表中的节点包含两个指针，分别指向前一个节点和后一个节点。
2. 选择题A. 数组B. 链表C. 树D. 栈（2）在一个长度为n的线性表中，删除第i个元素的时间复杂度为？A. O(1)B. O(n)C. O(n^2)D. O(log n)A. 栈是一种先进先出（FIFO）的数据结构B. 栈是一种先进后出（LIFO）的数据结构C. 栈的插入和删除操作都在栈顶进行D. 栈的插入和删除操作都在栈底进行二、树与二叉树1. 判断题（1）一个二叉树的节点个数与其高度成正比。
（2）完全二叉树中，叶子节点只可能在两层出现。
（3）二叉树的遍历方式有前序遍历、中序遍历和后序遍历三种。
2. 选择题A. 二叉树B. 线段树C. 平衡树D. 堆A. 二叉树的节点最多有两个子节点B. 二叉树的节点至少有一个子节点C. 二叉树可以为空树D. 二叉树的节点包含数据域和两个指针域A. 根节点 > 左子树 > 右子树B. 左子树 > 根节点 > 右子树C. 右子树 > 根节点 > 左子树D. 左子树 > 右子树 > 根节点三、图1. 判断题（1）图的遍历方式有深度优先遍历和广度优先遍历两种。
（2）在无向图中，边的数量等于节点的度数之和。
（3）有向图的邻接矩阵是对称的。
2. 选择题A. 数组B. 链表C. 栈D. 队列A. 图中的节点称为边B. 图中的边称为节点C. 图分为有向图和无向图D. 图中的边有权重和无权重之分A. 深度优先搜索（DFS）B. 广度优先搜索（BFS）C. Dijkstra算法D. Floyd算法四、排序与查找1. 判断题（1）冒泡排序是一种稳定的排序算法。
（2）快速排序的最坏时间复杂度为O(n^2)。
数据结构练习题及答案数据结构练习题及答案数据结构是计算机科学中非常重要的一个概念，它涉及到如何组织和存储数据以及如何有效地操作这些数据。
在学习数据结构的过程中，练习题是非常关键的一部分，通过解决练习题可以加深对数据结构的理解和运用能力。
本文将分享一些常见的数据结构练习题及其解答，希望能够帮助读者更好地掌握数据结构。
1. 数组反转题目：给定一个整型数组，将数组中的元素反转，要求不使用额外的空间。
解答：可以使用双指针的方法，一个指针指向数组的首部，一个指针指向数组的尾部，然后依次交换两个指针所指向的元素，直到两个指针相遇为止。
2. 链表倒数第K个节点题目：给定一个单向链表和一个正整数K，找出链表中倒数第K个节点的值。
解答：可以使用快慢指针的方法，首先让快指针先走K步，然后快慢指针同时向前移动，直到快指针到达链表尾部，此时慢指针所指的节点即为倒数第K个节点。
3. 栈的应用：括号匹配题目：给定一个字符串，判断其中的括号是否配对合法。
解答：可以使用栈来解决该问题，遍历字符串的每个字符，如果是左括号则入栈，如果是右括号则判断栈顶元素是否为对应的左括号，如果是则出栈，否则返回括号不合法。
4. 队列的应用：滑动窗口最大值题目：给定一个整型数组和一个滑动窗口的大小，求出每个滑动窗口中的最大值。
解答：可以使用双端队列来解决该问题，遍历整个数组，对于每个元素，如果队列不为空且队列尾部的元素小于当前元素，则将队列尾部的元素出队，重复该操作直到队列为空或者队列尾部的元素大于等于当前元素。
然后将当前元素入队。
同时，如果队列头部的元素已经不在当前滑动窗口的范围内，则将其出队。
每次滑动窗口移动时，队列头部的元素即为当前窗口的最大值。
5. 二叉树的遍历题目：给定一个二叉树，实现其前序、中序和后序遍历。
解答：可以使用递归的方法来实现二叉树的遍历。
前序遍历的顺序为根节点-左子树-右子树，中序遍历的顺序为左子树-根节点-右子树，后序遍历的顺序为左子树-右子树-根节点。
第 7 页 共 10 页 一、单项选择题 1. 逻辑关系是指数据元素间的（ ） A． 类型 B． 存储方式 C．结构 D． 数据项 2. 对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( ) A．顺序表 B.用头指针表示的单循环链表 C. 用尾指针表示的单循环链表 D. 单链表 3. 设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（ ）
A．front=front+1 B．front=(front+1)%(m-1)
C．front=(front-1)%m D．front=(front+1)%m 4. 在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为( )。 A．rear％n==front B．(front+l)％n==rear C．rear％n-1==front D．(rear+l)％n==front 第 7 页 共 10 页
5. 在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为( )。 A．rear％n==front B．front+l=rear C．rear==front D．(rear+l)％n=front 6. 已知一颗二叉树上有92个叶子结点，则它有____个度为2的结点。( ) A. 90 B. 91 C. 92 D. 93 7. 在一棵非空二叉树的中序遍历序列中，根结点的右边_____。 A. 只有右子树上的所有结点 B. 只有右子树上的部分结点 C. 只有左子树上的所有结点 D. 只有左子树上的部分结点 8. 有n条边的无向图的邻接表存储法中，链表中结点的个数是( )个。 A. n B. 2n C. n/2 D. n*n 9. 判断有向图是否存在回路，除了可利用拓扑排序方法外，还可以利用（ ）。 A. 求关键路径的方法 B.求最短路径的方法 C. 深度优先遍历算法 D.广度优先遍历算法 10. 对线性表进行二分查找时，要求线性表必须( )。 A.键值有序的顺序表 B.键值有序的表 C.表但键值不一定有序 D.顺序表但键值不一定有序 第 7 页 共 10 页
第一章绪论一、选择题1．数据结构是一门研究非数值计算的程序设计问题中计算机的⑴以及它们之间的⑵和运算等的学科。
⑴A操作对象B计算方法C逻辑存储D数据映像⑵A结构B关系C运算D算法2．数据结构被形式定义为（K，R），其中K是⑴的有限集，R是K上的⑵有限集。
⑴A算法B数据元素C数据操作D逻辑结构⑵A操作B映象C存储D关系3．在数据结构中，从逻辑上可以把数据结构分成⑴。
A动态结构和表态结构B紧凑结构和非紧凑结构C线性结构和非线性结构D内部结构和外部结构4．线性结构的顺序存储结构是一种⑴的存储结构，线性表的链式存储结构是一种⑵的存储结构。
⑴A随机存取B顺序存取C索引存取D散列存取⑵A随机存取B顺序存取C索引存取D散列存取5．算法分析的目的是⑴，算法分析的两个主要方面是⑵。
⑴A找出数据结构的合理性B研究算法中的输入和输出的关系C分析算法的效率以求改进D分析算法的易懂性和文档性⑵A空间复杂度和时间复杂度，正确性和简单性B可读性和文档性C数据复杂性和程序复杂性6．计算机算法指的是⑴，它必须具备输入、输出和⑵等5个特性。
⑴A计算方法B排序方法C解决问题的有限运算序列D调度方法⑵A可行性、可移植性和可扩充性B可行性、确定性和有穷性C确定性、有穷性和稳定性D易读性、稳定性和安全性7．线性表的逻辑顺序与存储顺序总是一致的，这种说法⑴。
⑴A正确B不正确8．线性表若采用链式存储结构时，要求内存中可用存储单元的地址⑴。
⑴A必须是连续的B部分地址必须是连续的C一定是不连续的D连续不连续都可以9．在以下的叙述中，正确的是⑴。
⑴A线性表的线性存储结构优于链表存储结构B二维数组是其数据元素为线性表的线性表C栈的操作方式是先进先出D队列的操作方式是先进后出10．每种数据结构都有具备三个基本运算：插入、删除、和查找，这种说法⑴。
⑴A正确B不正确二、填空题1．数据结构包括、和三种类型，树形结构和图形结构全称为。
2．在线性结构中，第_____个结点没有前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。
第8章查找算法1. 请简述查找的作用。
查找的作用是根据给定值从一个数据集合中搜索某个元素。
若某个元素的关键字值与给定值相等，则查找成功；否则查找失败。
2. 请简述静态查找和动态查找的含义。
静态查找只根据给定值在数据集合中按关键字查找匹配元素、访问匹配元素的属性，而不对数据集合进行插入元素、删除元素等操作；而动态查找可能会在查找过程中向数据集合中插入一个新元素或从数据集合中删除一个已有元素。
3. 请简述各种查找算法的适用范围。
各种查找算法的适用范围：（a）顺序查找虽然查找效率最低，但其对待查找数据集合的存储结构无特别要求，在对数据集合进行增、删、改等操作时效率较高，因此，根据那些不需要经常作查找操作的关键字进行查找时，一般采用顺序查找算法。
若经常作查找操作，则应使用效率较高的其他查找算法。
（b）折半查找和分块查找主要适用于数据集合增、删、改等操作较少的情况；二叉排序树查找则适用于数据集合变化较频繁的情况。
（c）哈希查找虽然在理论上具有最短的平均查找长度，但它占用的存储空间较多，且在实际中只有哈希函数构造得好才能达到常量级的平均查找长度。
而要想构造出好的哈希函数，必须以大量数据为基础，因此，哈希查找主要适用于数据分布已知的情况。
4. 请简述顺序查找对待查找数据集合的要求及顺序查找的具体步骤。
顺序查找是一种最简单、直观的查找算法，适用于采用任何存储结构的数据集合，其具体步骤为：（a）按预先规定的顺序依次将数据集合中每个元素的关键字与给定值进行比较，若某个元素的关键字与给定值相同，则查找成功；（b）若遍历所有元素后，仍没有找到关键字与给定值相同的元素，则查找失败。
5. 请简述折半查找对待查找数据集合的要求及折半查找的具体步骤。
折半查找，又称二分查找，它要求数据集合采用顺序表存储结构，且数据集合中的元素是按关键字大小有序排列的。
假设数据集合的元素按关键字递增排列，折半查找算法的具体步骤为：（a）对于包含n个元素的递增数据集合R={R[1], R[2], …, R[n]}（R[i]≤R[i+1]），根据给定元素K进行折半查找，初始化待查找数据集合的下标起始位置low=1和结束位置high=n。
