最新版吉林大学内部绝密资料-数据结构总复习.pdf

第 1 章绪论课后习题讲解1. 填空⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

【解答】数据元素⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。

【解答】数据项，数据元素【分析】数据结构指的是数据元素以及数据元素之间的关系。

⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。

【解答】集合，线性结构，树结构，图结构⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。

【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。

【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。

【解答】自然语言，程序设计语言，流程图，伪代码，伪代码⑺在一般情况下，一个算法的时间复杂度是（）的函数。

【解答】问题规模⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。

【解答】Ο(1)，Ο(nlog2n)【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。

2. 选择题⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。

A 线性结构B 非线性结构C 存储位置D 指针【解答】C，D【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。

⑵假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。

则表示该遗产继承关系的最合适的数据结构应该是（）。

奥鹏吉林大学课程考试复习资料单选题1.在一个类中可以对一个操作符进行（）重载。

A.1 种B.2 种以下C.3 种以下D.多种【参考答案】: D2.若w=1,x=2,y=3,z=4,则条件表达式w＞x?w:z＞y?z:x的结果为_______。

A.4B.3C.2D.1【参考答案】: A3.文档负责将数据存储到永久存储介质中，通常是磁盘文件或数据库，存取过程称为（）。

A.文件访问B.串行化C.文件读写D.格式化【参考答案】: B4.更新菜单状态的消息是（）。

A.WM_COMMANDB.UPDATEC.ON_UPDATE_COMMAND_UID.INVALIDATE【参考答案】: C5.有如下类声明：class XA{ private: int x;public: XA(int n){ x=n;} };class XB: public XA{ private: int y;public: XB(int a,int b); };在构造函数XB的下列定义中，正确的是( )。

A.XB::XB(int a,int b): x(a),y(b){ }B.XB::XB(int a,int b): XA(a),y(b){ }C.XB::XB(int a,int b): x(a),XB(b){ }D.XB::XB(int a,int b): XA(a),XB(b){ }【参考答案】: B6.有关析构函数的说法，不正确的是（）。

A.析构函数有且仅有一个B.析构函数和构造函数一样可以有形参C.析构函数的功能是在系统释放对象之前作一些内存清理工作D.析构函数无任何函数类型【参考答案】: B7.已知：int m=10; 下列表示引用的方法中，（）是正确的。

A.int &x=m;B.int &y=10;C.int &z;D.float &t=&m;【参考答案】: A8.下面对模板的声明，正确的是（）。

吉大《计算机组成原理》（三）、第三章存储系统一、存储器与CPU的连接方法（1）低位地址线、数据线、电源线（不要求）直接相连（2）高位地址线；全译码方式，高位地址线经译码后产生片选信号CS；线译码方式，除片内寻址外的高位地址线直接分别连至各个芯片的片选端CS（3）控制总线组合形成读/写控制线WE或WE/OE二、动态存储器DRAM刷新方式有哪三种？（1）集中式刷新在允许的最大刷新间隔2ms内，按照存储器容量大小集中安排刷新时间，此刻要停止读/写操作。

如果对16384位的矩阵（128*128）进行刷新。

该存储器的存取周期为500ns。

（2）分散式刷新把系统的存取周期分成两部分。

前部分时间进行读/写或处于保持状态。

后部分时间进行刷新，在一个周期内刷新单元矩阵的一行。

对128*128矩阵，则需要128个周期后才能把全部单元刷新完毕。

如果芯片的存取时间是μs，那么机器的存取周期应安排两倍的时间即1μs。

（3）异步刷新采取2ms内分散地反128行刷新一遍，那么对于每一行平均刷新的时间间隔为2ms/128=μs，取μs提出一次刷新请求。

提出刷新请求时，有可能CPU正在访存，可待至 CPU交出控制权后，再安排刷新周期，所以称异步刷新方式。

而在刷新时间内把读/写操作封锁。

这样，对每行单元的刷新间隔仍为2ms。

但对分散式刷新而言，它减少了刷新次数：对集中方式来说，主机的“死区”又缩短很多。

因此，这种方式使用得比较多。

三、双端口存储器主要用于？1、在运算器中采用双端口芯片，作为通用寄存器组，能快速提供双操作数。

2、使用双端口存储器，让一个端口面向CPU, 另一个端口面向外设和I/O处理机，从而增大信息的吞吐量。

3、在多机系统中，常采用双端口或多端口，作为各CPU的共享存储器，实现多CPU之间的通信。

四、引入Cache的目的是什么？引入Cache的目的：为了弥补主存速度的不足，在处理机与主存之间设置一个高速小容量的缓冲存储器，称为高速缓存（Cache）。

数据结构复习题一、单项选择题1. 不带头结点的单链表head为空的判断条件是( )。

A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL2. 链表不具有的特点是( )。

A.可随机访问任一元素B.插入删除不需要移动元素C.不必事先估计存储空间D.所需空间与线性表长度成正比3. 单链表中，增加头结点的目的是为了（）。

A.方便运算的实现B.用于标识单链表C.使单链表中至少有一个结点D.用于标识起始点的位置4. 设输入序列为A,B,C,D,借助一个栈不可以得到的输出序列是( )。

A.A,B,C,DB.A,C,D,BC.D,C,B,AD.D,A,B,C5. 栈和队列都是（）。

A.顺序存储的线性表B.链式存储的线性表C.限制存取点的线性结构D.限制存取点的非线性结构6. 串的长度是（）。

A.串中不同字符的个数B. 串中不同字母的个数C.串中所含字符的个数且字符个数大于0D.串中所含字符的个数7. 栈和队列的主要区别在于（）。

A.它们的逻辑结构不一样B.它们的存储结构不一样C.所包含的运算个数不一样D.插入删除运算的限定不一样8. 从具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，平均需比较（）个结点。

A.nB.n/2C.(n-1)/2D.(n+1)/29. 线性表是具有n个（）的有限序列。

A. 表元素B. 字符C. 数据元素D. 信息项10. 某二叉树的前序和后序序列正好相同，则该二叉树一定是（）的二叉树。

A. 空或只有一个结点B. 高度等于其结点数C. 任一结点无左孩子D. 任一结点无右孩子11. 在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（）。

A. 2B. 1C. 0D. –112. 下列排序算法中,第一趟排序完毕后,其最大或最小元素一定在其最终位置上的算法是（）。

A. 归并排序B. 直接插入排序C. 快速排序D. 冒泡排序13. 深度为n的二叉树中所含叶子结点的个数最多为（）个。

2022年吉林大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、用有向无环图描述表达式(A+B)*((A+B)／/A)，至少需要顶点的数目为（）。

A.5B.6C.8D.92、下列排序算法中，占用辅助空间最多的是（）。

A.归并排序B.快速排序C.希尔排序D.堆排序3、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。

A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表4、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（）。

A.（rear+1）MOD n=frontB.rear=frontC.rear+1=frontD.（rear-1）MOD n=front5、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（）。

A.h->next=sB.s->next=hC.s->next=h;h->next=sD.s->next=h-next;h->next=s6、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。

假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。

初始时为空，下列判断队空和队满的条件中，正确的是（）。

A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod MB．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1）C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod MD．队空：end1＝＝（end2＋1）mod M；队满：end2＝＝（end1＋1） mod （M－1）7、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。

下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。

吉大《信息系统集成》（六）第四章计算机网络系统（二）一、局域网建设建立一个局域网需要考虑的内容较多，从管理、分析、设计、采购、施工等各方面需要一个技术全面的团队共同完成。

局域网的建设与系统集成密切相关，需要在系统集成的总体要求下进行，经过需求分析、网络规划设计、施工准备、布线和机房建设、设备安装、网络测试、网络试运行、交付使用、系统维护等过程。

（1）需求分析规划方需要理解该网络建设的目的和意义，了解和掌握网络的用途及性能要求，在理解和掌握网络信息服务及信息安全要求的基础上，了解当前企业网络的现状和设备现状，有针对性的掌握各关键信息节点的分布以及网络信息中心的建设情况，对网络环境进行部署。

在此基础上了解资金投入，利用现有资源做出更加经济实用的网络规划。

（2）网络的规划与施工对网络的功能和性能进行规划，要求规范书写任务书；规划和施工的原则和依据是企业的规定、文件和网络建设规范等；组网的规划制定采纳标准、结构、接口的规划等；信息点统计及分布图方面需要统计各信息点数量，根据要求绘制信息结构图；设备选择和设备清单方面需要对比同类产品并提供选择的依据；布线规划方面需要提供对主干系统、子系统等连接链路的设计；机房建设规划方面需要对机房的装修、内部布线和环境等方面进行设计；对施工图纸和施工说明需要提供对应的施工图纸和施工程序、方案和技术要求；施工参考标准和工艺要求应明确标示施工参考的各类技术标准；整个工程的建设管理需要建立管理小组，加强人员配置。

（3）施工的准备工作对现场进行整理，准备网络辅材和攻击，加强人员配置，按照要求对设备材料进行采购等工作。

（4）布线及机房建设按照施工图纸和技术要求、技术规范进行布线施工。

（5）设备安装包括配线架、交换机、路由器、防火墙、服务器等网络所需设备的安装配置。

（6）网络测试一般包括通断测试和性能测试，测试完成后提供完整的测试报告和技术报告。

（7）网络试运行测试工作结束后，在试运行期间根据用户的反馈意见进行调整。

2018数据结构总复习第一章概论1.1数据结构的定义和分类1.数据结构的定义数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。

2.数据结构包括的内容（1）逻辑结构：数据元素之间的逻辑关系。

（2）存储结构：数据元素及其关系在计算机存储器内的表示。

（3）操作：数据的运算（检索、排序、插入、删除、修改）。

1.2为什么学习数据结构1.学习数据结构的作用（1）计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。

（2）同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。

（3）程序设计的实质是对实际问题选择一个好的数据结构，加之设计一个好的算法。

而好的算法在很大程度上取决于描述实际问题的数据结构。

2.电话号码查询问题（1）要写出好的查找算法，取决于这张表的结构及存储方式。

（2）电话号码表的结构和存储方式决定了查找（算法）的效率。

1.3算法的概念和特点1.算法的概念和特点算法是由若干条指令组成的有穷序列，具有以下特点：（1）输入：具有0个或多个输入的外界量。

（2）输出：至少产生1个输出。

（3）有穷性：每一条指令的执行次数必须是有限的。

（4）确定性：每条指令的含义都必须明确，无二义性。

（5）可行性：每条指令的执行时间都是有限的。

2.算法与程序的区别（1）一个程序不一定满足有穷性，但算法一定。

（2）程序中的指令必须是机器可执行的，而算法无此限制。

（3）一个算法若用机器可执行的语言来描述，则它就是一个程序。

1.4算法分析1.时间复杂度算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n) / f(n) 的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。

记作T(n)=O(f(n))，称O(f(n)) 为算法的渐近时间复杂度，简称时间复杂度。

算法效率的度量，采用时间复杂度。

2023年吉林大学数据科学与大数据技术专业《数据库原理》科目期末试卷A（有答案）一、填空题1、安全性控制的一般方法有____________、____________、____________、和____________视图的保护五级安全措施。

2、数据仓库是______、______、______、______的数据集合，支持管理的决策过程。

3、DBMS的完整性控制机制应具备三个功能：定义功能，即______；检查功能，即______；最后若发现用户的操作请求使数据违背了完整性约束条件，则采取一定的动作来保证数据的完整性。

4、采用关系模型的逻辑结构设计的任务是将E-R图转换成一组______，并进行______处理。

5、从外部视图到子模式的数据结构的转换是由______________实现；模式与子模式之间的映象是由______________实现；存储模式与数据物理组织之间的映象是由______________实现。

6、在SQL语言中，为了数据库的安全性，设置了对数据的存取进行控制的语句，对用户授权使用____________语句，收回所授的权限使用____________语句。

7、主题在数据仓库中由一系列实现。

一个主题之下表的划分可按______、______数据所属时间段进行划分，主题在数据仓库中可用______方式进行存储，如果主题存储量大，为了提高处理效率可采用______方式进行存储。

8、对于非规范化的模式，经过转变为1NF，______，将1NF经过转变为2NF，______，将2NF经过转变为3NF______。

9、在数据库系统封锁协议中，一级协议：“事务在修改数据A前必须先对其加X锁，直到事务结束才释放X锁”，该协议可以防止______；二级协议是在一级协议的基础上加上“事务T在读数据R之前必须先对其加S锁，读完后即可释放S锁”，该协议可以防止______；三级协议是在一级协议的基础上加上“事务T在读数据R之前必须先对其加S锁，直到事务结束后才释放S锁”，该协议可以防止______。

1：38.邻接表的存储结构下图的深度优先遍历类似于二叉树（树）的( )。

1.先序遍历
2.中序遍历
3.后序遍历
4.按层遍历
2：44 下列排序算法中,第一趟排序完毕后,其最大或最小元素一定在其最终位置上的算法是( )。

1.归并排序
2.直接插入排序
3.快速排序
4.冒泡排序
3：5.线性表的长度是指（）
1.顺序存储方式下数组所占的空间大小
2.链式存储方式下所有结点占用的空间大小
3.表中的元素个数
4.所能存储的最大的结点个数
4：45．若表r在排序前已按元素键值递增顺序排列，采用( )方法比较次数较少。

1.直接插入排序
2.快速排序
3.归并排序
4.选择排序
5：18.设输入序列为的A,B,C,D,借助一个栈不可以得到的输出序列是( )。

1.A,B,C,D
2.A,C,D,B
3. D,C,B,A
4.D,A,B,C
6：11 若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用( )存储方式最节省空间。

1.单链表
2.双链表
3.带头结点的双循环链表
4.单循环链表
7：46 下列四个关键字序列中,( )不是堆。

1. {05,23,16,68,94,72,71,73}
2.{05,16,23,68,94,72,71,73}
3. {05,23,16,73,94,72,71,68}
4.{05,23,16,68,73,71,72,94}。

第五章接口技术与硬件设计一、I2C总线操作I2C规程运用主/从双向通讯。

器件发送数据到总线上，则定义为发送器，器件接收数据则定义为接收器。

主器件和从器件都可以工作于接收和发送状态。

总线必须由主器件（通常为微控制器）控制，主器件产生串行时钟（SCL）控制总线的传输方向，并产生起始和停止条件。

SDA 线上的数据状态仅在SCL为低电平的期间才能改变，SCL为高电平的期间，SDA状态的改变被用来表示起始和停止条件。

控制字节在起始条件之后，必须是器件的控制字节，其中高四位为器件类型识别符（不同的芯片类型有不同的定义，EEPROM一般应为1010），接着三位为片选，最后一位为读写位，当为1时为读操作，为0时为写操作。

写操作写操作分为字节写和页面写两种操作，对于页面写根据芯片的一次装载的字节不同有所不同。

读操作读操作有三种基本操作：当前地址读、随机读和顺序读。

图4给出的是顺序读的时序图。

应当注意的是：最后一个读操作的第9个时钟周期不是“不关心”。

为了结束读操作，主机必须在第9个周期间发出停止条件或者在第9个时钟周期内保持SDA为高电平、然后发出停止条件。

I2C总线应用目前有很多半导体集成电路上都集成了I2C接口。

带有I2C接口的单片机有：CYGNAL的 C8051F0XX系列，三星的S3C24XX系列，PHILIPSP87LPC7XX系列，MICROCHIP的PIC16C6XX系列等。

很多外围器件如存储器、监控芯片等也提供I2C接口。

举常I2C器件/I2C Device1、存储器类： ATMEL公司的AT24CXX系列EEPROM；（1）、I2C总线8位并行IO口扩展芯片PCF8574/JLC1562；（2）、I2C接口实时时钟芯片DS1307/PCF8563/SD2000D/M41T80/ME901/ISL1208/；（3）、I2C数据采集ADC芯片MCP3221（12bitADC）/ADS1100（16bitADC）/ADS1112（16bitADC）/MAX1238（12bitADC）/MAX1239（12bitADC）；（4）、I2C接口数模转换DAC芯片DAC5574（8bitDAC）/DAC6573（10bitDAC）/DAC8571（16bitDAC）/；（5）、I2C接口温度传感器TMP101/TMP275/DS1621/MAX6625USB转I2C专用芯片：USB2I2C USB2I2C是一个USB总线转I2C总线I2C/IIC/TWI/SMBUS的接口芯片，通过USB2I2C芯片可以非常方便地实现PC机USB总线和下位机端I2C接口（即IIC或TWI总线：SCL 线、SDA 线）之间的通信。

第五章存储层次知识点汇总存储器层次结构、存储层次性能参数（平均每位价格、命中率、平均访存时间）、存储层次4个问题、CPU 访存地址分割、全相联映像、直接映像、组相联映像、查找方法、替换算法（随机、先进先出、最近最少使用法）、写直达法、写回法、按写分配、不按写分配、Cache性能分析、3C失效（强制失效、容量失效、冲突失效）、Victim Cache、伪相联映像Cache、硬件预取、编译器优化（数组合并、内外循环交换、循环融合、分块）、写缓冲合并、单字宽存储器、多字宽存储器、多体交叉存储器、存储体、虚拟存储器（页式、段式）、快表（TLB）简答题1.单级存储器的主要矛盾是什么？通常采取什么方法来解决？（知识点：多级存储器）答：主要矛盾：(1) 速度越快，每位价格就越高。

(2) 容量越大，每位价格就越低。

(3) 容量越大，速度越慢。

采取多级存储层次方法来解决。

2.“Cache-主存”和“主存-辅存”层次的主要区别是什么？（知识点：存储层次）3.在存储层次中应解决哪四个问题？（知识点：存储层次的四个问题）答：（1）映像规则：当把一个块调入高一层存储器时，可以放到哪些位置上。

（2）查找算法：当所要访问的块在高一层存储器中时，如何找到该块。

（3）替换算法：当发生失效时，应替换哪一块。

（4）写策略：当进行写访问时，应进行哪些操作。

4.地址映像方法有哪几种？它们各有什么优缺点？（知识点：地址映像）（1）全相联映像。

实现查找的机制复杂，代价高，速度慢。

Cache空间的利用率较高，块冲突概率较低，因而Cache的失效率也低。

（2）直接映像。

实现查找的机制简单，速度快。

Cache空间的利用率较低，块冲突概率较高，因而Cache 的失效率也高。

（3）组相联映像。

组相联是直接映像和全相联的一种折中。

5.Cache的3C失效是哪三种失效？针对每种失效给出一种降低失效率的方法。

（知识点：3C失效）答：强制性失效、容量失效、冲突失效。