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

东北大学22春“计算机科学与技术”《数据库技术及应用Ⅱ》期末考试高频考点版（带答案）一.综合考核(共50题)1.SQL 中局部变量必须先用SET命令说明后才可使用。

()A.正确B.错误参考答案：B2.已知关系S(S#，SNAME，AGE，SEX)，SC(S#，C#，GRADE)，统计每一年龄段选修课程的学生人数的操作如下： SELECT AGE，COUNT(*) FROM S，SC WHERE S.S#=SC.S# GROUR BY ()：A.S.S#，SC.S#B.DISTINCT S.S#，SC.S#C.DISTINCT S.S#，AGED.S.S#，AGE参考答案：C3.文件系统的缺点之一表现在改变数据的逻辑结构就必须修改数据库。

()A.正确B.错误参考答案：B4.Application对象用来共享应用程序的所有用户信息。

()A.正确B.错误参考答案：A5.下面哪个不是数据库技术的主要特点()A.数据的结构化B.数据的冗余度小C.较高的数据独立性D.程序的标准化参考答案：D6.有两个实体集，并且它们之间存在着一个1∶1联系，那么根据ER模型转换成关系数据库的规则，这个ER结构转换成表的个数为()。

A.4B.3C.2D.1参考答案：C7.在登录日志文件时，应该()。

A.将更新数据库与登录日志文件两个操作按随机的先后顺序完成B.将更新数据库与登录日志文件两个操作同时完成C.先登录日志文件，后写数据库的更新D.先写数据库的更新，后登录日志文件参考答案：C8.DB是()。

A.数据库系统B.数据库管理系统C.数据库D.数据处理参考答案：C9.关系数据库中，关系称为二维表，元组称为记录，属性称为域。

()A.正确B.错误参考答案：B10.有两个实体集，并且它们之间存在着一个1：1联系，那么根据ER模型转换成关系数据库的规则，这个ER结构转换成表的个数为()个A.1B.2C.3D.4参考答案：B11.索引记录了索引列在数据表中的物理存储位置，实现了表中数据的逻辑排序。

2022年东北大学秦皇岛分校数据科学与大数据技术专业《计算机系统结构》科目期末试卷A(有答案）一、选择题1、外部设备打印机适合于连接到( )。

A.数组多路通道B.字节多路通道C.选择通道D.任意一种通道2、从计算机系统结构上讲，机器语言程序员所看到的机器属性是( )。

A.计算机软件所要完成的功能B.计算机硬件的全部组成C.编程要用到的硬件组织D.计算机各部件的硬件实现3、计算机系统结构不包括( )。

A.主存速度B.机器工作状态C.信息保护D.数据4、系列机软件应做到( )。

A.向前兼容，并向上兼容B.向后兼容，力争向上兼容C.向前兼容，并向下兼容D.向后兼容，力争向下兼容5、在尾数下溢处理方法中，平均误差最大的是（）A.截断法B.舍入法C.恒置"1"法D.ROM查表法6、与全相联映象相比，组相联映象的优点是( )A.目录表小B.块冲突概率低C.命中率高D.主存利用率高7、输入输出系统硬件的功能对（）是透明的。

A.操作系统程序员B.应用程序员C.系统结构设计人员D.机器语言程序设计员8、在计算机系统设计中，比较好的方法是( )A.从上向下设计B.从下向上设计C.从两头向中间设计D.从中间开始向上、向下设计9、下列关于虚拟存贮器的说法，比较正确的应当是( )A.访主存命中率随页面大小增大而提高B.访主存命中率随主存容量增加而提高C.更换替换算法能提高命中率D.在主存命中率低时，改用堆栈型替换算法，并增大主存容量，可提高命中率10、汇编语言程序经（）的（）成机器语言程序。

A.编译程序，翻译B.汇编程序，翻译C.汇编程序，解释D.编译程序，解释二、填空题11、软件和硬件成本由________和________组成。

12、Cache存贮器写操作时，只写入Cache，仅当需要块替换时，才将其写回主存。

称这种修改主存块内容的方法为________法。

13、一种机器的系统结构上实现另一种机器的指令系统，一般可采用________方法或________方法。

第一章问题 1The computer has experienced 4 generations, which are ( ).A. Transistors, SMI, Laser device, Optical mediumB. Vacuum Tubes, Transistors, SSI/MSI circuit, Laser deviceC. Vacuum Tubes, Digital tube, SSI/MSI circuit, Laser deviceD. Vacuum Tubes, Transistors, SSI/MSI circuit, LSI/VLSI circuit问题 2The components of CPU do not include ( ).A. Arithmetic unitB. memoryC. registerD. controller问题 3CPU can process information of external memory directly.A.对B.错问题 4MFLOPS is a performance index for express the speed of processing the floating point number.A.对B.错问题 5Although computer science and technology have changed tremendously both in hardware and in software, the basic model for computers has remained essentially the same, which was presented by ( ).A. EinsteinB. Von NeumannC. EdisonD. Newton问题 6In 8-bits micro-computer system, multiplication and division are realized by ( ).A. dedicated chipsB. firmwareC. softwareD. hardware问题 7Software is equivalent to hardware in logic function.A.对B.错问题 8Resources management of computer software and hardware is the duty of ( ).A. Operating SystemB. Language process programC. Database Management SystemD. Application program问题 9The reason of binary representation for information in a computer is it can easily process the information.A.对B.错问题 10The basic feature of Von Neumann computer is ( ).A. access memory by address and execute instruction in sequenceB. access memory by contentC. Multiple Instruction Stream Single Data Stream (MISD)D. operate stack问题 11Data and instructions are stored in ( ) when the program is running.A. memoryB. diskC. datapathD. operating system问题 12The operating system is appeared in ( ).A. the 4th generation computersB. the 2nd generation computersC. the 3rd generation computersD. the 1st generation computers问题 13The so called “PC” belongs to ( ).A. Medium computersB. MainframesC. Micro-computersD. Mini-computers问题 14Computer hardware consists of calculator, memory, controller and I/O devices.A.对B.错问题 15( ) is not belonged to system program.A. Database systemB. Operating systemC. Compiler programD. the above all问题 16The vast majority of computer systems used today are constructed on ( ) computer model.A. intelligentB. Von NeumannC. parallelD. real time processing问题 17The use of ( ) signified the development of micro-computer.A. softwareB. diskC. MicroprocessorD. OS问题 18The use of microprocessor signified the development of micro-computer.A.对B.错问题 19The reason why the binary system of representation is widely adopted in computer is ( ).A. computing speed fastB. convenience for information processingC. saving componentsD. the restriction of the nature of physical devices问题 20A full computer should consists of ( ).A. host and PeripheralB. calculator, memory and controllerC. host and programD. hardware and software system问题 21Host consists of CPU and I/O devices.A.对B.错问题 22In a computer based on the von Neumann model, instructions and data are all stored in memory, and CPU distinguish them according their address.A.对B.错问题 23System software is purchased, and applied software is edit by ourselves.A.对B.错问题 24Which of the following languages can be implemented directly and edited by Mnemonic(助记符): ①Assembly language;②machine language; ③High-level language; ④Operating system primitives; ⑤Regular languageA. ①, ④B. ②，①C. ②，⑤D. ①，③问题 25In computer terminology, CPU consists of calculator and controller.A.对B.错选择题答案：1-5.DBBAB 6-10.CAABA 11-15.ACCAA 16-20.BCADD 21-25.BABBA第二章问题 1If [X] 2’s complement = 0.1101010，then [X]sign-magnitude = ( )A. 0.0010110B. 1.0010110C. 1.0010101D. 0.1101010问题 2( ) is used to represent address in computer.A. 1’s complementB. unsigned numberC. 2’s complementD. sign magnitude问题 3Numbers X1, X2are integer, and 【X1】2’s compl= 10011011，【X2】2’s compl= 00011011, then their true value of decimal form are ________ and ________。

东北师范大学22春“计算机科学与技术”《数据结构》期末考试高频考点版（带答案）一.综合考核(共50题)1.顺序存储结构的主要缺点是不利于插入、删除操作。

()A.错误B.正确参考答案：B2.就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是()。

A.堆排序B.堆排序C.堆排序>归并排序>快速排序D.堆排序>快速排序>归并排序参考答案：A3.广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。

()A.正确B.错误参考答案：B4.head指向的带表头结点的单链表为空的判定条件是()。

A.head->next==headB.head->next==NULLC.head==NULLD.head!=NULL参考答案：B5.B.错误参考答案：A6.链表中的表头结点仅起到标识的作用。

()A.错误B.正确参考答案：A7.线索二叉树是一种()结构。

A.逻辑B.物理C.逻辑和存储D.线性参考答案：B8.对于3个结点a、b、c，可构成不同的二叉树的棵数为()。

A.32B.30C.28D.24参考答案：B9.插入、删除只能在同一端进行的线性表，称为()。

A.队列B.栈C.循环队列D.循环栈参考答案：B10.当待排序记录已经从小到大排序或从大到小有序时，快速排序的执行时间最省。

()A.错误B.正确参考答案：A11.有n个顶点的有向图的边数最多为()。

A.nB.n(n-1)C.n(n-1)/2D.2n参考答案：B12.()的遍历仍需要栈的支持。

A.前序线索二叉树B.中序线索二叉树C.后序线索二叉树D.前三种均需要参考答案：C13.判断线索二叉树中某结点p有左子女的条件是()。

A.p!=NULLB.p-lchild!=NULLC.p-ltag==0D.p-ltag==1参考答案：C14.在下面的排序方法中，其比较次数与待排序记录的初始排列状态无关的是()。

C.直接选择排序D.归并排序参考答案：C15.后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。

东北大学22春“计算机科学与技术”《计算机组成与系统结构》期末考试高频考点版（带答案）一.综合考核(共50题)1.用16位字长(其中1位符号位)表示定点整数时，所能表示的数值范围是______。

A、[0，216-1]B、[0，215-1]C、[0，214-1]D、[0，215]参考答案：B2.定点机算术运算会产生溢出是因为内存容量不够大。

()A.正确B.错误参考答案：B3.某机字长32位，存储容量64MB，若按字编址，它的寻址范围是()。

A.8MB.16MBC.16MD.8MB参考答案：C4.控制存储器用来存放实现全部2的所有微程序。

()A、错误B、正确参考答案：B周期挪用方式常用于()方式的输入/输出中。

A.DMAB.中断C.程序传送D.通道参考答案：A6.下列数中最大的数是______。

A、(10011001)2B、(227)8C、(98)16D、(152)10参考答案：A7.计算机操作的最小时间单位是()。

A.时钟周期B.指令周期C.CPU周期D.微周期参考答案：A8.74181ALU内部是串行进位的。

()A.正确B.错误参考答案：B9.用64位字长(其中1位符号位)表示定点整数时，所能表示的数值范围是______。

A、[0，264-1]B、[0，263-1]参考答案：B10.下列数中最小的数为()。

A.(101001)2B.(52)8C.(2B)16D.(44)10参考答案：A11.假定下列字符码中有奇偶校验位，但没有数据错误，采用奇校验的字符码有______。

(四个数为①10011010 ②11010000 ③11010111 ④10111100)A、①③B、①C、②④D、④参考答案：C12.目前的计算机，从原理上讲()。

A.指令以二进制形式存放，数据以十进制形式存放B.指令以十进制形式存放，数据以二进制形式存放C.指令和数据都以二进制形式存放D.指令和数据都以十进制形式存放参考答案：C13.算术/逻辑运算单元74181ALU可完成______。

东北大学22春“计算机科学与技术”《数据库技术》期末考试高频考点版（带答案）一.综合考核(共50题)1.下面的说法不确切的是()A.聚簇索引使表的物理顺序与索引顺序一致，一个表只能有一个群聚索引B.非聚簇索引与表的物理顺序无关，一个表应该建立多个非聚簇索引参考答案：B2.下列不属于结构数据模型的是()A.关系数据模型B.层次数据模型C.网络数据模型D.实体联系模型参考答案：D3.在数据库的三级模式结构中，内模式有()。

A.0个B.2个C.1个D.任意多个参考答案：C4.恢复机制的关键问题是建立冗余数据，最常用的技术是()。

A、数据镜像B、数据转储和登录日志文件参考答案：B在DB技术中“脏数据”是指()。

A、未回退的数据B、未提交随后又被撤消的数据参考答案：B6.SQL的标准库函数COUNT，SUM，AVG，MAX与MIN等，不允许在其中的命令是()A.GROUP......HAVINGB.WHERE参考答案：B7.SQL Server的中的文件位置可以很灵活，可以将数据文件存储在不同的地方，然后把他们作为一个单元来管理，完成这种功能的是()。

A.事务日志文件B.文件组参考答案：B8.SQL Server的内嵌表值函数的返回的结果()。

A、数据库表B、标志位参考答案：A9.在第一个事务以排他锁方式读写数据A时，其他事务对数据A可以是()。

A.实现排他锁的读B.读写等待参考答案：BA、属性B、表参考答案：B11.数据库系统中产生数据不一致性的根本原因是()。

A、没有严格保护数据B、未对数据进行完整性控制参考答案：B12.视图是一个“虚表”，视图的构造基于()A.基本表或视图B.数据字典参考答案：A13.现要查找缺少学习成绩(G)的学生学号(S#)和课程号(C#)，相应的SQL语句是SELECT S#，C# FROM SC WHERE ()A.G=NULLB.G IS NULL参考答案：B14.在SQL语言的查询语句中，实现投影操作命令的是()。

第10章排序一、选择题1．某内排序方法的稳定性是指( )。

【南京理工大学 1997 一、10（2分）】A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录C．平均时间为0（n log n）的排序方法 D．以上都不对2．下面给出的四种排序法中( )排序法是不稳定性排序法。

【北京航空航天大学 1999 一、10 （2分）】A. 插入B. 冒泡C. 二路归并D. 堆积3．下列排序算法中，其中（）是稳定的。

【福州大学 1998 一、3 (2分)】A. 堆排序，冒泡排序B. 快速排序，堆排序C. 直接选择排序，归并排序D. 归并排序，冒泡排序4．稳定的排序方法是（）【北方交通大学 2000 二、3（2分）】A．直接插入排序和快速排序 B．折半插入排序和起泡排序C．简单选择排序和四路归并排序 D．树形选择排序和shell排序5．下列排序方法中，哪一个是稳定的排序方法？（）【北方交通大学 2001 一、8（2分）】A．直接选择排序 B．二分法插入排序 C．希尔排序 D．快速排序6．若要求尽可能快地对序列进行稳定的排序，则应选（A．快速排序 B．归并排序 C．冒泡排序）。

【北京邮电大学 2001 一、5（2分）】7．如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。

（）就是不稳定的排序方法。

【清华大学 1998 一、3 (2分）】A．起泡排序 B．归并排序 C．Shell排序 D．直接插入排序 E．简单选择排序8．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（）排序为宜。

A．直接插入 B．直接选择 C．堆 D．快速 E．基数【中科院计算所 2000 一、5（2分）】9．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。

A. 快速排序B. 堆排序C. 归并排序D. 直接插入排序【中国科技大学 1998 二、4（2分）】【中科院计算所 1998 二、4（2分）】10．下面的排序算法中，不稳定的是（）【北京工业大学 1999 一、2 (2分)】A.起泡排序B.折半插入排序C.简单选择排序D.希尔排序E.基数排序F.堆排序。

东北大学“计算机科学与技术”《数据结构Ⅱ》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、时间复杂度和空间复杂度的计算。

要求能够计算出程序的执行次数。

2、各种概念：数据结构、数据项、数据元素第二章线性表1、单链表的各种操作，包括单链表的建立、插入、删除结点的操作语句序列2、单链表（带头结点、不带头结点、循环单链表）的逆置运算。

3、双链表的插入和删除操作语句序列。

4、单链表的直接插入排序运算。

5、静态单链表的插入和删除操作。

6、二个有序单链表的合并、一个单链表拆分为多个单链表第三章栈和队列1、栈的输入序列和输出序列、递归函数的输出结果2、循环队列的入队、出队操作以及有效元素个数的计算第四章串1、KMP算法中的next和nextval值的计算第五章数组和广义表1、二维数组任意元素地址的计算2、稀疏矩阵的转置算法3、广义表的两个操作函数：取表头和表尾第六章树和二叉树1、二叉树的性质（特别是完全二叉树的性质，例如求完全二叉树的深度等）2、二叉树的遍历（特别是中序和先序遍历，要求能够使用堆栈完成非递归遍历编程和递归算法编程，在遍历基础上的各种操作，例如求二叉树的叶子数、二叉树结点数等操作，包括有编程算法和编程填空题）3、线索二叉树（特别是中序线索化二叉树和中序线索化二叉树的中序遍历，包括编程算法和编程填空题，希望大家着重研究）4、哈夫曼编码（主要是应用题，包括哈夫曼的编码与解码，也包括哈夫曼树的特点）5、树与森林在转化成二叉树时，左右子树的结点数有何特点）6、树的层次遍历（使用队列完成、借助树的层次遍历可以判断二叉树是否为完全二叉树）、判断二叉树是否为排序二叉树等，可能有编程题或编程填空题）补充：二叉树的物理存储结构（链式和顺序存储）*第七章图1、图的两种物理存储方式（邻接矩阵与邻接表存储表示）2、图的生成树与最小生成树（生成树特点）、图的遍历3、求最小生成树的两种算法（重点是PRIM 算法，特别会写出用PRIM算法求最小生成树的过程）4、使用迪杰斯特拉算法求单源最短路径，写出求解过程5、拓扑排序6、求关键路径，要求写出事件和活动的最早和最晚开始时间，深刻理解关键路径的含义。

2022年东北大学秦皇岛分校数据科学与大数据技术专业《计算机系统结构》科目期末试卷B(有答案）一、选择题1、流水机器对全局性相关的处理不包括( )A.猜测法B.提前形成条件码C.加快短循环程序的执行D.设置相关专用通路2、属计算机系统结构考虑的是（）A.主存采用MOS还是TTLB.主存采用多体交叉还是单体C.主存容量和编址方式D.主存频宽的确定3、输入输出系统硬件的功能对（）是透明的。

A.操作系统程序员B.应用程序员C.系统结构设计人员D.机器语言程序设计员4、对机器语言程序员透明的是（）A.中断字B.主存地址寄存器C.通用寄存器D.条件码5、与全相联映象相比，组相联映象的优点是( )A.目录表小B.块冲突概率低C.命中率高D.主存利用率高6、对系统程序员不透明的应当是( )。

A.Cache存贮器XB.系列机各档不同的数据通路宽度C.指令缓冲寄存器D.虚拟存贮器7、计算机系统的层次结构按照由高到低的顺序分别为（）。

A.高级语言机器级，汇编语言机器级，传统机器语言机器级，微程序机器级B.高级语言机器级，应用语言机器级，汇编语言机器级，微程序机器级C.应用语言机器级，传统机器语言机器级，汇编语言机器级，操作系统机器级D.应用语言机器级，操作系统机器级，微程序机器级，传统机器语言机器级8、静态流水线是指( )A.只有一种功能的流水线B.功能不能改变的流水线C.同时只能完成一种功能的多功能流水线D.可同时执行多种功能的流水线9、最能确保提高虚拟存贮器访主存的命中率的改进途径是( )A.增大辅存容量B.采用FIFO替换算法并增大页面C.改用LRU替换算法并增大页面D.改用LRU替换算法并增大页面数10、对汇编语言程序员透明的是（）A.I/O方式中的DMA访问B.浮点数据表示C.访问方式保护D.程序性中断二、填空题11、评价存贮器性能的基本要求是大容量、________和低价格。

12、多功能流水线各功能段同时只能按某一种功能联接的称为________流水线。