下载文档原格式
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. 请简要解释数组和链表的区别和应用场景。
