2017数据结构与算法总复习

《数据结构与算法》一、选择题1. 组成数据的基本单位是( )。

(A) 数据项 (B)数据类型 (C)数据元素 (D)数据变量2. 线性表的链接实现有利于( )运算。

(A) 插入 (B)读表元 (C)查找 (D)定位3. 串的逻辑结构与( )的逻辑结构不同。

(A) 线性表 (B)栈 (C)队列 (D)树4. 二叉树第i（i≥1）层最多有( )个结点。

(A) 2i (B)2i (C) 2i-1 (D) 2i-15. 设单链表中指针p指向结点A，若要删除A后结点（若存在），则需要修改指针的操作为( )(A) p->next = p->next->next (B)p=p->next(C)p=p->next->next (D)p->next=p6、栈和队列的共同特点是( )。

(A)只允许在端点处插入和删除元素 (B)都是先进后出(C)都是先进先出 (D)没有共同点7、二叉树的第k层的结点数最多为( ).(A)2k+1 (B)2K+1 (C)2K-1(D) 2k-18、设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。

(A) BADC (B) BCDA (C) CDAB (D) CBDA9、设某完全无向图中有n个顶点，则该完全无向图中有（）条边。

(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-110、下面程序的时间复杂为（）for（i=1,s=0; i<=n; i++）{t=1;for(j=1;j<=i;j++)t=t*j;s=s+t;}(A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(n3)11、设某强连通图中有n个顶点，则该强连通图中至少有（）条边。

(A) n(n-1) (B) n+1 (C) n (D) n(n+1)12、设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）条有向边。

数据结构与算法复习题库含答案1. 问题描述：给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

答案：可以使用哈希表来解决此问题。

首先初始化一个空的哈希表，然后遍历数组中的每个元素。

对于每个元素，首先计算目标值与当前元素的差值，然后在哈希表中查找该差值。

如果找到了该差值，则说明存在两个数的和等于目标值，返回这两个数的下标；否则，将当前元素插入到哈希表中。

时间复杂度为O(n)，其中n为数组的长度。

2. 问题描述：给定一个字符串，找出其中不含重复字符的最长子串的长度。

答案：可以使用滑动窗口来解决此问题。

维护一个窗口，其中包含没有重复字符的子串。

遍历字符串中的每个字符，如果该字符不在窗口中，将其加入窗口；如果该字符在窗口中，移动窗口的左边界直到窗口中不包含重复字符。

记录窗口的最大长度。

时间复杂度为O(n)，其中n为字符串的长度。

3. 问题描述：给定一个字符串和一个单词列表，找出字符串中可以由单词列表中的单词组成的所有子串的起始位置。

答案：可以使用滑动窗口和哈希表来解决此问题。

首先统计单词列表中每个单词的出现次数。

然后遍历字符串中的每个位置作为子串的起始位置，维护一个滑动窗口。

在窗口中依次取出长度和单词列表中单词总长度相等的子串，在哈希表中统计子串中每个单词出现的次数。

如果窗口中的子串与单词列表中的单词出现次数一致，则记录该子串的起始位置。

时间复杂度为O(n*m)，其中n为字符串的长度，m为单词列表中的单词个数。

4. 问题描述：给定一个无序的整数数组，找出其中缺失的第一个正整数。

答案：可以使用原地哈希表来解决此问题。

遍历数组中的每个元素，将每个正整数放到数组中对应的位置上。

遍历数组中的每个元素，如果该位置上的数不等于数组索引加一，则该索引加一即为缺失的第一个正整数。

时间复杂度为O(n)，其中n为数组的长度。

5. 问题描述：给定一个字符串s，找到s中最长的回文子串。

答案：可以使用动态规划来解决此问题。

数据结构与算法复习提纲（1）数据结构与算法复习提纲线性表部分：1、顺序表的基本操作：创建、插⼊、删除、查找、修改、遍历、输出2、带头结点单链表的基本操作：创建、插⼊（头插、尾插、任意位置插⼊）、删除（头删、尾删、任意位置删除）、查找、修改、定位、输出、求表长、遍历的基本应⽤3、带头结点的循环单链表的基本操作：创建、插⼊（头插、尾插、任意位置插⼊）、删除（头删、尾删、任意位置删除）、查找、修改、定位、输出、求表长、遍历的基本应⽤4、线性表的应⽤：有序顺序表的插⼊；有序单链表的插⼊；顺序表的逆置、单链表的逆置；顺序表归并、单链表归并栈和队列部分：1、顺序栈的基本操作：创建、⼊栈、出栈、取得栈顶元素（注意top变量的取值）、判栈空、判栈满、遍历2、链栈的基本操作：创建、⼊栈、出栈、判栈空、遍历3、循环队列的基本操作：创建、⼊队、出队、队空队满的判定条件、求队列长度、遍历；4、链队列的基本操作：创建、⼊队、出队、队空、遍历5、表达式求值：栈中数据的变化过程树和⼆叉树1、⼆叉树的5个基本性质2、⼆叉树的顺序存储结构3、⼆叉链表存储，相关的基本操作：前中后三种遍历、层次遍历、创建、求结点个数、求叶⼦个数、求深度、基于遍历的应⽤4、树的孩⼦兄弟链表存储结构，相关的基本操作：创建、查找某个结点的孩⼦、插⼊⼀个结点、遍历输出5、树的孩⼦兄弟链表存储结构，相关的基本操作：创建、求深度、先根遍历、插⼊结点6、⼆叉树、树与森林的应⽤：由两种遍历序列确定⼀棵⼆叉树；⼆叉树的三种遍历序列；由两种遍历序列确定⼀棵树；树（森林）与⼆叉树之间的相互转换；7、哈夫曼树及其应⽤：构造哈夫曼树、哈夫曼编码、求wpl；注意：构造哈夫曼树过程相关存储结构的变化图的部分1、图的基本概念2、图的邻接矩阵存储结构：创建、深度遍历、⼴度遍历3、图的邻接表存储结构：创建、深度遍历、⼴度遍历4、最⼩⽣成树：prim算法、kruscal算法5、最短路径：迪杰斯特拉算法、floyd算法6、拓扑排序、关键路径查找与排序部分1、带哨兵的顺序查找：算法、ASL2、折半查找：算法、查找判定树、成功与不成功的ASL3、⼆叉排序树的构造、平衡⼆叉树的构造、成功与不成功的ASL4、哈希表：构造、线性探测、⼆次探测、拉链法；成功与不成功的ASL5、直接插⼊排序、希尔排序、冒泡排序、快速排序，⼀趟排序的结果。

数据结构与算法复习题+参考答案一、单选题（共100题，每题1分，共100分）1、设栈的顺序存储空间为 S(1:m)，初始状态为 top=0。

现经过一系列正常的入栈与退栈操作后，top=m+1，则栈中的元素个数为A、m+1B、mC、不可能D、0正确答案：C2、小张完成了毕业论文，现需要在正文前添加论文目录以便检索和阅读，最优的操作方法是：A、利用 Word 提供的“手动目录”功能创建目录。

B、不使用内置标题样式，而是直接基于自定义样式创建目录。

C、将文档的各级标题设置为内置标题样式，然后基于内置标题样式自动插入目录。

D、直接输入作为目录的标题文字和相对应的页码创建目录。

正确答案：C3、赵老师在 Excel 中为 400 位学生每人制作了一个成绩条，每个成绩条之间有一个空行分隔。

他希望同时选中所有成绩条及分隔空行，最快捷的操作方法是：A、直接在成绩条区域中拖动鼠标进行选择B、单击成绩条区域的某一个单元格，然后按Ctrl+A 组合键两次C、单击成绩条区域的第一个单元格，然后按Ctrl+Shift+End 组合键D、单击成绩条区域的第一个单元格，按下Shift 键不放再单击该区域的最后一个单元格正确答案：C4、设某棵树的度为 3，其中度为 3,1,0 的结点个数分别为 3,4,15。

则该树中总结点数为A、35B、不可能有这样的树C、30D、22正确答案：C5、在商场购物时，顾客可以购买不同的商品，而同样的商品也销售给不同的顾客，则实体顾客和实体商品之间的联系是A、一对一B、一对多C、多对多D、多对一正确答案：C6、在具有 2n 个结点的完全二叉树中，叶子结点个数为A、n/2B、n-1C、nD、n+1正确答案：C7、PowerPoint 演示文稿包含了 20 张幻灯片，需要放映奇数页幻灯片，最优的操作方法是：A、将演示文稿的偶数张幻灯片删除后再放映。

B、将演示文稿的偶数张幻灯片设置为隐藏后再放映。

C、将演示文稿的所有奇数张幻灯片添加到自定义放映方案中，然后再放映。

《数据结构与算法》复习题一、选择题。

1．在数据结构中，从逻辑上可以把数据结构分为 C 。

A．动态结构和静态结构 B．紧凑结构和非紧凑结构C．线性结构和非线性结构 D．内部结构和外部结构2．数据结构在计算机内存中的表示是指 A 。

A．数据的存储结构 B．数据结构 C．数据的逻辑结构 D．数据元素之间的关系3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。

A．逻辑 B．存储 C．逻辑和存储 D．物理4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。

A．数据的处理方法 B．数据元素的类型C．数据元素之间的关系 D．数据的存储方法5．在决定选取何种存储结构时，一般不考虑 A 。

A．各结点的值如何 B．结点个数的多少C．对数据有哪些运算 D．所用的编程语言实现这种结构是否方便。

6．以下说法正确的是 D 。

A．数据项是数据的基本单位B．数据元素是数据的最小单位C．数据结构是带结构的数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。

（1）A．找出数据结构的合理性 B．研究算法中的输入和输出的关系C．分析算法的效率以求改进 C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度 B．正确性和简明性C．可读性和文档性 D．数据复杂性和程序复杂性8．下面程序段的时间复杂度是 O(n2) 。

s =0;for( I =0; i<n; i++)for(j=0;j<n;j++)s +=B[i][j]; sum = s ;9．下面程序段的时间复杂度是 O(n*m) 。

for( i =0; i<n; i++)for(j=0;j<m;j++)A[i][j] ＝ 0;10．下面程序段的时间复杂度是 O(log3n) 。

i ＝ 0；while（i<=n）i = i * 3；11．在以下的叙述中，正确的是 B 。

数据结构与算法复习题集在计算机科学领域，数据结构与算法是非常重要的基础知识。

它们就像是建筑师手中的蓝图和工具，决定了程序的效率和性能。

为了帮助大家更好地掌握这部分内容，下面为大家整理了一份数据结构与算法的复习题集。

一、数据结构部分1、线性表请简述顺序表和链表的优缺点，并举例说明在什么情况下更适合使用顺序表，什么情况下更适合使用链表。

实现一个顺序表的插入和删除操作，并分析其时间复杂度。

2、栈和队列解释栈和队列的概念，并说明它们的应用场景。

用数组实现一个循环队列，并写出入队和出队的操作代码。

3、数组和字符串给定一个整数数组，找出其中出现次数超过数组长度一半的元素。

请给出算法思路和代码实现。

实现一个字符串匹配算法，判断一个字符串是否是另一个字符串的子串。

4、树简述二叉树的前序、中序和后序遍历的递归和非递归实现方法。

给定一个二叉搜索树，实现插入、删除和查找操作。

5、图解释图的深度优先搜索和广度优先搜索算法，并给出代码示例。

用邻接表存储一个无向图，实现图的遍历和最短路径算法（如迪杰斯特拉算法）。

二、算法部分1、排序算法比较冒泡排序、插入排序、选择排序、快速排序和归并排序的时间复杂度和空间复杂度，并分析它们的优缺点。

实现快速排序算法，并分析其在最坏情况下的性能。

2、查找算法简述顺序查找、二分查找和哈希查找的原理和适用场景。

设计一个哈希表，并实现插入、查找和删除操作。

3、动态规划解释动态规划的基本思想，并通过一个具体的例子（如背包问题）说明其求解过程。

用动态规划算法求解最长递增子序列问题。

4、贪心算法阐述贪心算法的概念和特点，并举例说明贪心算法可能得到非最优解的情况。

用贪心算法解决活动安排问题。

5、分治算法说明分治算法的基本步骤，并以归并排序为例解释其应用。

用分治算法求解最大子数组和问题。

三、综合应用1、假设有一个包含学生信息（学号、姓名、成绩）的链表，要求实现按照成绩从高到低排序的功能。

2、设计一个算法，判断一个二叉树是否是平衡二叉树。

2017《数据结构》期末考试试题及答案2017《数据结构》期末考试试题及答案《数据结构》期末考试试题及答案1 (2)试题1答案 (7)《数据结构》期末考试试题及答案2 (9)试题2答案 (14)《数据结构》期末考试试题及答案3 (16)试题3答案 (21)《数据结构》期末考试试题及答案1⼀、单选题（每题 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进制表⽰。

A．688 B．678 C．692 D．6965.树最适合⽤来表⽰( )。

A.有序数据元素B.⽆序数据元素C.元素之间具有分⽀层次关系的数据D.元素之间⽆联系的数据6.⼆叉树的第k层的结点数最多为( ).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的元素有（）个，A．1 B．2 C．3 D．410.设有6个结点的⽆向图，该图⾄少应有( )条边才能确保是⼀个连通图。

2017 ～2018学年度第2学期《数据结构》复习提纲1．在数据结构中，从逻辑上可以把数据结构分为_________两类。

A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构2．链表不具有的特点是_________。

A．可随机访问任一元素B．插入、删除不需要移动的元素C．不必事先估计存储空间D．所需空间与线性表长度成正比3．若线性表最常用的运算是存取第i个元素及其前驱元素，则采用_________存储方式节省时间。

A．单链表B．双链表C．循环单链表D．顺序表4．算法分析的目的是_________。

A．找出数据结构的合理性B．研究算法中的输入和输出关系C．分析算法的效率以求改进D．分析算法的易读性和文档性5．若一个栈用数组data[1..n]存储，初始栈顶指针top为0，则以下元素x进栈的操作正确的是_________。

A．top++; data[top]=x;B．data[top]=x; top++;C．top--; data[top]=x;D．data[top]=x; top--;6．表达式a*(b+c)-d的后缀表达式是_________。

A．abcd*+-B．abc+*d-C．abc*+d-D．-+*abcd7．递归函数f(1)=1，f(n)=f(n-1)+n(n＞1)的递归出口是_________。

A．f(1)=1B．f(1)=0C．f(0)=0D．f(n)=n8．将递归算法转换成对应的非递归算法时，通常需要使用_________保存中间结果。

A．队列B．栈C．链表D．树9．对稀疏矩阵采用压缩存储，其缺点之一是_________。

A．无法判断矩阵有多少行、多少列B．无法根据行、列号查找某个矩阵元素C．无法根据行、列号直接计算矩阵元素的存储地址D．使矩阵元素之间的逻辑关系更加复杂10．一个n阶上三角矩阵a按行优先顺序压缩存放在一维数组b中，则b中的元素个数是_________。

数据结构与算法复习提纲（详细版）数据结构与算法复习提纲第一章引论一、数学知识复习1、对数（重要公式：X A=B当且仅当A=log X B；关键思路：将对数转化成为指数分析）2、级数（重要公式：∑A i和∑i A；关键思路：同时乘上某个系数再相减）3、证明方法（数学归纳法和反证法：三个关键步骤（归纳基础、归纳假设、归纳证明））二、C++类1、构造函数（使用默认参数的构造函数；初始化列表）2、访问函数和修改函数（关键字const）3、接口与实现的分离（声明与实现必须精确匹配，两个例外：默认参数和explicit）三、C++细节1、参数传递（一般情形：单向传递/引用：双向传递/常引用：避免大对象的拷贝）2、★三大函数（当数据成员含有指针类型，三大函数必须显式给出；避免浅复制）⑴、析构函数（形式：~类名（）/作用：释放资源）⑵、复制构造函数（形式：类名（const 类名&rhs）/作用：利用已有对象复制一个新对象）⑶、operator=（形式：const 类名&operator=（const 类名&rhs）/作用：赋值）四、模板1、★函数模板定义（template 通用函数定义）2、★类模板⑴、定义（template class 类模板名）⑵、调用（class 类模板名<实际参数> 对象名（参数））3、函数对象（定义一个包含零个数据成员和一个成员函数的类，然后传递该类的实例）五、矩阵1、基本思想（矩阵利用向量的向量来实现，即vector array）2、典型代码分析（包括构造函数和operator[]重载）第二章算法分析一、数学基础1、重要定义⑴、f（N）=Ο（g（N））（若存在正常数C和n0，使得当N≥n0时，有f（N）≤Cg（N））⑵、f（N）=Ω（g（N））、f（N）=Θ（g（N））和f（N）=ο（g（N）））2、★重要工具⑴、性质：log k N=O（N）⑵、洛比塔法则：判断两个函数的相对增长率二、最大子列和问题1、算法Ⅰ⑴、算法思想（i表示序列起点，j表示序列终点，k从i扫描到j）⑵、★时间复杂度分析（注意分析方法：∑（i：0~N-1）∑（j：i~N-1）∑（k：i~j））⑶、★算法的缺陷（重复计算）2、算法Ⅱ算法思想（i表示序列起点，j表示序列终点（省略辅助变量k））3、算法Ⅲ⑴、★分治策略（递归程序：传递数组和左右边界，后者界定了数组要被处理的范围/单行驱动程序：传递数组和0，N-1而启动递归程序）⑵、算法思想（递归出口分析；最大子序列和的三种可能情况）⑶、★时间复杂度分析（重要公式：T（N）=2T（N/2）+N）4、算法Ⅳ（任何负的子序列不可能是最优子序列的前缀）三、折半搜索1、概念：折半查找（在已排好序的队列中查找数X）2、算法思想（关键是分析low、high和mid）第三章表、栈和队列一、STL中的向量和表（STL，Standard Template Library，标准模板库）1、STL定义了vector（向量）和list（双向链表）两个类模板2、★★迭代器（iterator）⑴、迭代器的作用（位置标记）⑵、迭代器的声明（典例：vecto r。