东北大学数据结构期末复习共136页

一、算法（每 15 分，共 60 分）答要求：①用自然言明所采用算法的思想；② 出每个算法所需的数据构定，并做必要明；③写出的算法程序，并做必要的注。

1、有一个点的表，每个点包括两个域，一个是整型域 info ，另一个是指向下一个点的指域next 。

假表已建立，算法除表中所有重复出的点，使得 info 域相等的点只保留一个。

3、瑟夫（Josephus）是指号1、 2、⋯， n 的 n（ n>0）个人按方向坐成一圈，从第s 个人开始按方向数，数到第m 个人出列，然后从出列的下一个人重新开始数，数到第m 的人又出列，⋯，如此重复直到所有的人全部出列止。

要求采用循表构一个算法，模此程。

4、程表的就地逆置。

23．在数A[1..n]中有n个数据，建立一个有点的循表，指h，要求中数据从小到大排列，重复的数据在中只保存一个.5、一个尽可能的高效算法出表的倒数第K 个元素。

3、假以I 和 O 分表示入和出操作。

的初和均空，入和出的操作序列可表示由I 和 O 成的序列，称可以操作的序列合法序列，否称非法序列。

（15 分）（ 1）下面所示的序列中哪些是合法的？A. IOIIOIOOB. IOOIOIIOC. IIIOIOIOD. IIIOOIOO（ 2）通（ 1）的分析，写出一个算法，判定所的操作序列是否合法。

若合法，返回true，否返回false（假定被判定的操作序列已存入一数中）。

5、从入一整数的序列： a1, a2, a3，⋯， an, 写算法：用构存入的整数，当 ai ≠-1 ，将 ai ；当 ai=-1 ，出整数并出。

算法异常情况（入等）出相的信息。

有一个背包可以放入的物品重量S，有 n 件物品，重量分W1， W2， ... ，W n。

能否从 n 件物品中若干件放入背包，使得放入的重量之和正好是S。

布函数 Knap(S，n) 表示背包的解， W i(i=1,2,... ，n) 均正整数，并已序存地在数 W中。

数据结构期末复习汇总数据结构是计算机科学中十分重要的概念之一，它是指数据对象以及数据对象之间的关系、操作和操作规则的集合。

在计算机科学的学习中，掌握数据结构是至关重要的一步。

为了帮助大家复习期末考试，以下是一些数据结构的重要知识点的总结。

一、线性表线性表是最简单的一种数据结构，它是一种有序的数据元素集合。

线性表的特点是元素之间的关系是一对一的关系，每个元素都与它的前驱和后继相连接。

1.数组：数组是最常见的线性表结构，它由相同类型的数据元素组成，这些元素通过索引来访问。

2.链表：链表是另一种常见的线性表结构，它由节点组成，每个节点包含了数据以及一个指向下一个节点的指针。

二、栈和队列栈和队列是常用的线性结构，它们在操作上有一些限制。

1.栈：栈是一种具有后进先出（LIFO）特性的线性表。

栈中的元素只能在栈顶进行插入和删除操作。

2.队列：队列是一种具有先进先出（FIFO）特性的线性表。

队列中的元素只能在队尾进行插入操作，在队头进行删除操作。

三、树和二叉树树是一种非线性的数据结构，它由节点和边组成。

树的一个节点可以有多个子节点，但是每个节点只能有一个父节点。

1.二叉树：二叉树是一种特殊的树结构，每个节点最多只能有两个子节点。

2.二叉树：二叉树是一种特殊的二叉树，它满足左子树的所有节点的值都小于根节点的值，右子树的所有节点的值都大于根节点的值。

四、图图是一种非常重要的非线性结构，它由节点和边组成。

图的节点之间可以有多种不同的关系。

1.有向图：有向图是一种图结构，图的边有方向，从一个节点到另一个节点。

2.无向图：无向图是一种图结构，图的边没有方向。

五、排序和算法排序算法是对一组数据进行排序的算法，算法是找到目标元素在一组数据中的位置的算法。

1.冒泡排序：冒泡排序是一种交换排序算法，其核心思想是比较相邻的元素并进行交换，将最大（或最小）元素逐渐“冒泡”到数组的末尾。

2.快速排序：快速排序是一种分治排序算法，其核心思想是通过选择一个基准元素，将数组划分为两个子数组，其中一个子数组的所有元素都小于基准元素，另一个子数组的所有元素都大于基准元素，然后对两个子数组进行递归排序。

东北师范大学22春“计算机科学与技术”《数据结构》期末考试高频考点版（带答案）一.综合考核(共50题)1.若哈希表(散列表)的负载因子l，则可避免冲突的产生。

()A.正确B.错误参考答案：B2.顺序文件采用顺序结构实现文件的存储，对大型的顺序文件的少量修改，要求重新复制整个文件，代价很高，采用()的方法可降低所需的代价。

A.附加文件B.按关键字大小排序C.按记录输入先后排序D.连续排序参考答案：A3.后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。

()A.错误B.正确参考答案：B4.在链队列中，假设f和r分别为队首和队尾指针，则删除一个结点的操作是()。

A.r=r->nextB.r=f->nextC.f=r->nextD.f=f->next参考答案：D稀疏矩阵常用的压缩存储方法有两种，它们是()。

A.散列和十字链表B.二维数组和三维数组C.三元组和散列D.三元组和十字链表参考答案：D6.二叉树结点的中序遍历序列与前序遍历序列可以唯一地确定该棵二叉树。

()A.错误B.正确参考答案：B7.二叉树在线索化后，仍不能有效求解的问题是()。

A.后序线索二叉树中求后序后继B.前序线索二叉树中求前序后继C.中序线索二叉树中求中序后继D.中序线索二叉树中求中序前驱参考答案：A8.线索二叉树是一种()结构。

A.逻辑B.物理C.逻辑和存储D.线性参考答案：B9.邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。

()参考答案：B10.快速排序的速度在所有排序方法中最快，而且所需附加空间也最少。

()A.错误B.正确参考答案：A11.一个队列的入队序列是a、b、c、d，则队列的输出序列是()。

A.dcbaB.cbdaC.adcbD.abcd参考答案：D12.下列描述中正确的是()。

A.选择合适的数据结构是解决应用问题的关键步骤B.线性表的逻辑顺序与存储顺序总是一致的C.每种数据结构都具备查找、插入和删除三种基本运算D.数据结构实质上包括逻辑结构和存储结构两方面的内容参考答案：A13.如果要求一个线性表既能较快地查找、又能适应动态变化的要求，则可采用的查找方法是()。

2020-2021学年《数据结构》期末考试复习试题一、单项选择题1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。

(A)、正确性(B). 可行性(C). 健壮性(D). 输入性2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（）。

for(i=n-1；i>=0；i--)for(j=0；j<i；j++) S；(A)、n2(B). O(nlgn) (C). O(n) (D). O(n2)3．折半查找法适用于（）。

（A）、有序顺序表（B）、有序单链表（C）、有序顺序表和有序单链表都可以（D）、无限制4．顺序存储结构的优势是（）。

（A）、利于插入操作（B）、利于删除操作（C）、利于顺序访问（D）、利于随机访问5．深度为k的完全二叉树，其叶子结点必在第（）层上。

（A）、k-1 （B）、k （C）、k-1和k （D）、1至k6．具有60个结点的二叉树，其叶子结点有12个，则度过1的结点数为（）（A）、11 （B）、13 （C）、48 （D）、377．图的Depth-First Search(DFS)遍历思想实际上是二叉树（）遍历方法的推广。

（A）、先序（B）、中序（C）、后序（D）、层序8．在下列链队列Q中，元素a出队的操作序列为（）（A）、p=Q.front->next; p->next= Q.front->next;（B）、p=Q.front->next; Q.front->next=p->next;（C）、p=Q.rear->next; p->next= Q.rear->next;（D）、p=Q->next; Q->next=p->next;9． Huffman树的带权路径长度WPL等于（）（A）、除根结点之外的所有结点权值之和（B）、所有结点权值之和（C）、各叶子结点的带权路径长度之和（D）、根结点的值10．线索二叉链表是利用（）域存储后继结点的地址。

《数据结构》期末考试试卷一、选择题（单选题，每小题3分，共33分）1．已知某二叉树的中序、层序序列分别为DBAFCE、FDEBCA，则该二叉树的后序序列为 B 。

A．BCDEAF B．ABDCEF C．DBACEF D．DABECF 2．在11个元素的有序表A[1…11]中进行折半查找（⎣⎦2/)low+），查找元素(highA[11]时，被比较的元素的下标依次是 B 。

A．6，8，10，11 B．6，9，10，11 C．6，7，9，11 D．6，8，9，113．由元素序列（27，16，75，38，51）构造平衡二叉树，则首次出现的最小不平衡子树的根（即离插入结点最近且平衡因子的绝对值为2的结点）为 D 。

A．27 B．38 C．51 D．754．利用逐点插入法建立序列（50，72，43，85，75，20，35，45，65，30）对应的二叉排序树以后，查找元素30要进行 B 次元素间的比较。

A．4 B．5 C．6 D．75．循环链表的主要优点是 D 。

A．不再需要头指针了B．已知某个结点的位置后，很容易找到它的直接前驱结点C．在进行删除后，能保证链表不断开D．从表中任一结点出发都能遍历整个链表6．已知一个线性表（38，25，74，63，52，48），假定采用散列函数h（key）=key%7计算散列地址，并散列存储在散列表A[0…6]中，若采用线性探测方法解决冲突，则在该散列表上进行等概率查找时查找成功的平均查找长度为 C 。

A．1．5 B．1．7 C．2．0 D．2．37．由权值为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为C 。

A．23 B．37 C．44 D．468．在最好和最坏情况下的时间复杂度均为O（nlogn）且稳定的排序方法是 D 。

A．基数排序B．快速排序C．堆排序D．归并排序9．无向图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）}。

东北大学“计算机科学与技术”《数据结构Ⅱ》23秋期末试题库含答案第1卷一.综合考核(共20题)1.对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用遍历方式是A.后序B.先序C.从根开始的层次遍历D.中序2.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是()。

A.栈B.队列C.树D.图3.4.树有先根遍历和后根遍历，树可以转化为对应的二叉树。

下面的说法正确的是A.树的后根遍历与其对应的二叉树的后根遍历相同B.树的后根遍历与其对应的二叉树的中根遍历相同C.树的先根遍历与其对应的二叉树的中根遍历相同D.以上都不对5.已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为()。

A.DEBAFCB.DEFBCAC.DEBCFAD.DEBFCA6.下列序列中，不构成堆的是()。

A.(1，2，5，3，4，6，7，8，9，10)B.(10，5，8，4，2，6，7，1，3)C.(10，9，8，7，3，5，4，6，2)D.(1，2，3，4，10，9，8，7，6，5)7.在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系()。

A.不一定相同B.都相同C.都不相同D.互为逆序8.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为A.n-i+1B.n-iC.i-1D.i9.下列陈述中正确的是A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分C.二叉树中最多只有两棵子树，并且有左右之分D.二叉树中必有度为2的结点10.连通图是指图中任意两个顶点之间()。

A.都连通的无向图B.都不连通的无向图C.都连通的有向图D.都不连通的有向图11.判断两个串大小的基本准则是()。

A.两个串长度的大小B.两个串中首字符的大小C.两个串中大写字母的多少D.对应的第一个不等字符的大小12.若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的()。

(整理)数据库系统重要知识点目录数据库系统重要知识点 (1)第一章：数据库系统概论 (3)1．基本概念（数据库，数据库管理系统，数据库系统） (3)2．数据库阶段数据管理的特点 (3)3．数据模型的三个组成部分 (3)4．数据模型的两个不同层次 (4)5．概念模型中用于描述信息结构的概念 (4)6．利用E-R模型描述信息结构 (4)7．数据库的三级模式结构 (5)8．三级模式之间的二级映像 (6)9．DBMS的主要功能 (6)第二章：关系模型和关系理论 (6)1．关系模型的基本概念（关系，属性，码，主码，三类关系，基本关系的性质，关系模式，关系数据库，关系数据库的型和值） (6)2．关系操作和关系操作语言（常用的关系操作有哪些；关系语言有哪些） (7)3．关系模型的完整性规则（实体完整性，参照完整性，用户定义的完整性） (7)4．E-R模型向关系模型转化的规则 (7)5．关系代数：传统的集合运算，专门的关系运算 (7)第三章：关系数据库标准语言SQL (7)1．基本表的创建，修改和撤销 (7)2．视图的创建和撤销 (7)3．索引的创建和撤销 (8)4．SQL的数据查询 (8)5．视图的创建和撤销，视图的作用 (8)6．SQL的并发控制 (8)7．定义关系完整性约束的方法，实体完整性的违约处理，参照完整性的违约处理 (8)8．触发器的定义和删除 (8)第四章：数据库编程 (8)1．嵌入式SQL的运行环境 (8)2．嵌入式SQL的使用规定 (8)第五章：数据库设计 (9)1．函数依赖，平凡（非平凡）函数依赖，部分函数依赖，传递函数依赖，多值依赖 (9)2．1NF，2NF，3NF，BCNF，4NF (9)3．数据依赖的公理系统 (9)4．模式分解 (9)5．数据库设计的基本步骤 (9)6．从E-R模型向关系模型转化的规则 (9)第六章：数据库实现技术 (10)1．查询优化的一般准则 (10)2．关系代数表达式的优化算法 (10)3．优化的一般步骤 (10)4．事务，事务的开始和结束，事务的特性（ACID） (10)5．数据库故障的种类（事务内部的故障，系统故障，介质故障）和恢复方法 (10)6．数据转储，登记日志文件 (10)7．并发操作带来的数据不一致性 (10)8．封锁，基本封锁类型 (10)9．死锁的诊断与解除 (10)10．并发调度的可串行性 (10)11．两段锁协议 (10)第一章：数据库系统概论1．基本概念（数据库，数据库管理系统，数据库系统）●数据库：数据库是以一定组织方式储存在一起的，能为多个用户共享的，具有尽可能小的冗余度的、与应用彼此独立的相互关联的数据集合。

数据结构II试题期末考试备战题集（线上）一、单选题（每小题2分，共6分）1．抽象数据类型的三个组成部分分别为A．数据对象、数据关系和基本操作B．数据元素、逻辑结构和存储结构C．数据项、数据元素和数据类型D．数据元素、数据结构和数据类型2．下列各式中，按增长率由小至大的顺序正确排列的是A．n，n！，2n ，n3/2 B．n3/2，2n，n logn，2100C．2n，log n，n logn，n3/2 D．2100，logn, 2n, n n 3. 已知指针p和q分别指向某单链表中第一个结点和最后一个结点。

假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为A. q->next=s->next；s->next=p；B. s->next=p；q->next=s->next；C. p->next=s->next；s->next=q；D. s->next=q；p->next=s->next；参考正确选项：1、A2、D3、A二、填空题（每小题1分，共10分）1.下面程序段中带下划线的语句的执行次数的数量级是( )。

i=1；WHILE(i<n)i=i*2;2．假设带头结点的非空单循环链表中仅设尾指针L，则在第1个结点之前插入指针s所指结点的语句依次是（）。

3．无表头结点的链队列Q为空的条件是（）。

4．设Q[0..N-1]为循环队列，其头、尾指针分别为P和R，则队Q中当前所含元素个数为（）。

5．一棵含999个结点的完全二叉树的深度为（）。

6．在 AOV网中，存在环意味着某项活动以自己为先决条件；对程序的数据流图来说，它表明存在（）。

7. 有向图G可拓扑排序的判别条件是( )。

8．如果结点A有 3个兄弟，而且B是A的双亲，则B的度是（）。

9．应用回溯与分支限界法解决实际问题时，在搜索过程中利用判定函数，也称为（）。

一、单项选择题（10 小题，每小题 1 分，共 10 分）1． 在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该是一个（B ）结构。

B ．队列A ．栈C ．数组D ．线性表）。

D ．123． 设输入序列为 1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为(2． 设某棵二叉树中有 2000 个结点，则该二叉树的最小高度为（A ．9B ．10C ．11CB)。

A ．5，3，4，6，1，2C ．3，1，2，5，4，6B ．3，2，5，6，4，1D ．1，5，4，6，2，34． 设指针变量 p 指向单链表中结点 A ，若删除单链表中结点 A ，则需要修改指针的操作序列为()。

AA. q=p->next ；p->data=q->data ；p->next=q->next ；free(q)；B. q=p->next ；q->data=p->data ；p->next=q->next ；free(q)；C. q=p->next ；p->next=q->next ；free(q)；D. q=p->next ；p->data=q->data ；free(q)；5． 对于 n 个关键字序列{k ，k ，…，k }，当且仅当满足关系 k ≤k 且 k ≤k 2 i+1（2i ≤n, 2i+1≤n ）12n i 2i i 称其为小根堆，反之，当且仅当满足关系 k ≥k 且 k ≥k 2i+1（2i≤n, 2i+1≤n ）则为大根堆，以下i 2i i 序列中(C)不符合堆的定义。

A ．（4,10,15,72,39,23,18）C ．（4,10,18,72,39,23,15）B ．（58,27,36,12,8,23,9）D ．（58,36,27,12,8,23,9）6． 程序段for(i=n-1;i>=1;i--)for(j=1;j<=i;j++)if(A[j]>A[j+1])A[j]与 A[j+1]对换；其中 n 为正整数，则最后一行的语句频度在最坏情况下是( B )。

东北师范大学“计算机科学与技术”《数据结构》23秋期末试题库含答案第1卷一.综合考核(共20题)1.在下列情况中，可称为二叉树的是()。

A.每个结点至多有两棵子树的树B.哈夫曼树C.每个结点至多有两棵子树的有序树D.每个结点只有一棵右子树2.下列描述中正确的是()。

A.选择合适的数据结构是解决应用问题的关键步骤B.线性表的逻辑顺序与存储顺序总是一致的C.每种数据结构都具备查找、插入和删除三种基本运算D.数据结构实质上包括逻辑结构和存储结构两方面的内容3.在排序方法中，从未排序序列中挑选记录，并将其依次放入已排序序列(初始时为空)的一端的方法，称为()。

A.希尔排序B.插入排序C.归并排序D.选择排序4.最佳二叉排序树是AVL树(平衡二叉排序树)。

()A.正确B.错误5.在二叉树中插入结点，则此二叉树便不再是二叉树了。

()A.正确B.错误6.连通分量是无向图中的极大连通子图。

()A.错误B.正确7.稀疏矩阵压缩存储后，必会失去随机存取功能。

()A.正确B.错误8.无向图的邻接矩阵可用一维数组存储。

()A.正确B.错误9.栈和队列都是限制存取点的线性结构。

()A.正确B.错误10.设散列地址空间为0~m-1，key为关键字，用p去除key，将得到的余数作为key的散列地址，即h(key)=key%p。

为了减少发生冲突的频率，一般取p为()。

A.小于等于m的最大奇数B.小于等于m的最大偶数C.小于等于m的最大素数D.小于等于m的最大合数11.12.邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。

()A.正确B.错误13.所谓取广义表的表尾就是返回广义表中最后一个元素。

()A.错误B.正确14.任何一棵二叉树的叶结点在前序、中序和后序遍历序列中的相对次序()。

A.稍有改变B.发生改变C.不能确定D.不发生改变15.将一个A[1..100，1..100]的三对角矩阵，按行优先次序存入一维数组B[1..298]中，A中元素A[66，65]在数组B中的位置K为()。