2022年数据结构与数据库技术复习题借鉴 .pdf

《2022年数据结构与数据库技术复习题借鉴 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构与数据库技术复习题借鉴 .pdf（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构与数据库技术复习题- 1 - 数据结构部分1、数据结构术语及其他们之间的关系，数据结构研究的内容。2、算法定义及5 个特征，对给定的一段程序要会求算法时间复杂度。3、线性表的特点，顺序存储结构和链式存储结构的特点，创建、插入、删除算法。4、栈、队列的特点，栈空、栈满条件，入栈、出栈动作描述，循环队列队空、队满的条件。5、二叉树的术语，二叉树的性质，二叉树存储结构，满二叉树和完全二叉树的特点，二叉树遍历，由遍历序列还原一棵二叉树。6、顺序查找和二分查找时元素需比较的次数，二分查找过程描述- 判定树。7、课堂讲过的每一种排序方法要求对给定的一组关键字都能给出每趟排序的结果，最后分析关键字比

2、较的次数及排序的稳定性。数据库技术部分1、数据管理系统的三个阶段的特点，数据库术语及其他们之间关系，数据库系统的体系结构- 三级模式和二级映射，数据独立性。2、实体联系模型（E-R 图） 、层次模型、网状模型、关系模型（二维表）， E-R 图，关系表的特点，关系模型的3 类完整性约束。关系模型包含的内容。3、关系代数 - 并、交、差、笛卡尔积、投影、选择、连接、自然连接。4、数据库设计4 个阶段， 每个阶段要完成的任务。ER 图向关系模型转换的原则、转换的方法。5、SQL 语句（创建、插入、修改、删除、查询），带条件的查询，简单的连接查询必须掌握。一、选择题1在计算机中，算法是指（C ） 。A

3、）查询方法B）加工方法C）解题方案的准确而完整的描述D）排序方法2在下列选项中，哪个不是一个算法一般应该具有的基本特征（C ） 。A）确定性B）可行性C）无穷性D）拥有足够的情报3下面叙述正确的是（C ） 。A）算法的执行效率与数据的存储结构无关B）算法的空间复杂度是指算法程序中指令（或语句）的条数（指的是算法所占用的空间）C）算法的有穷性是指算法必须能在执行有限个步骤之后终止D）以上三种描述都不对4算法的空间复杂度是指（D ） 。A）算法程序的长度B）算法程序中的指令条数C）算法程序所占的存储空间D）算法执行过程中所需要的存储空间5算法分析的目的是（D ） 。A）找出数据结构的合理性B）找出

4、算法中输入和输出之间的关系C）分析算法的易懂性和可靠性名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 19 页 - - - - - - - - - 数据结构与数据库技术复习题- 2 - D）分析算法的效率以求改进6算法的时间复杂度是指( C )。A）执行算法程序所需要的时间B）算法程序的长度C）算法执行过程中所需要的基本运算次数D）算法程序中的指令条数7算法一般都可以用哪几种控制结构组合而成( D )。A）循环、分支、递归B）顺序、循环、嵌套C）循环、递归、选择D）顺序、

5、选择、循环8数据的存储结构是指( B )。A）数据所占的存储空间量B）数据的逻辑结构在计算机中的表示C）数据在计算机中的顺序存储方式D）存储在外存中的数据9下列叙述中正确的是( A)。A）线性表是线性结构B）栈与队列是非线性结构C）线性链表是非线性结构D）二叉树是线性结构10数据在计算机内存中的表示称为（A） 。A）数据的存储结构B）数据的逻辑结构C）线性结构D）树形结构11在数据结构中，从逻辑上可以把数据结构分为（A） 。A）线性结构和非线性结构B）动态结构和静态结构C）外部结构和内部结构D）简单结构和复杂结构12以下数据结构中不属于线性数据结构的是( C )。A）队列B）线性表C）二叉树D

6、）栈13用链表表示线性表的优点是( A)。A）便于插入和删除操作B）数据元素的物理顺序与逻辑顺序相同C）花费的存储空间较顺序存储少D）便于随机存取14下列叙述中正确的是（B ）A）线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的B）线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构C）线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构D）上述三种说法都不对15用带头结点的链表表示线性表的好处是（C ） 。A）可以提高对表的访问速度B）可以随机访问C）使空表和非空表的处理方法统一D）节省存储空间16链表不具备的特点是（B ） 。名师资料总结 - - -精品资料欢迎下载

7、- - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 19 页 - - - - - - - - - 数据结构与数据库技术复习题- 3 - A）不必事先估计存储空间B）可以随机访问任意结点C）插入元素不需要移动任何元素D）所需空间与其长度成正比17如果最常用的操作是取第i 个结点及其前趋，最节省时间的存储方式是（A） 。A）顺序表B）单链表C）双向链表D）单循环链表18与单链表相比，双向链表的优点之一是（B ） 。A）插入、删除操作更简单B）顺序访问相邻结点更加方便C）可以实现随机访问D）可以省略头指针19下列叙述中正确

8、的是（C ）A）在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化B）在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化C）在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化D）上述三种说法都不对20下列关于栈的叙述中正确的是( D )。A）在栈中只能插入数据B）在栈中只能删除数据C）栈是先进先出的线性表D）栈是先进后出的线性表21栈和队列的共同点是（A） 。A）只允许在端点处插入和删除元素B）都是先进后出C）都是后进先出D）没有共同点22向一个栈顶指针为HS 的链栈中插入一个指针为s 的结点，则应执行（C ） 。A）HSnext=s B）HSnext=snext C）snext

9、=HS； HS=s D） HSnext=s；HS=HSnext 23下列关于队列的叙述中正确的是( C )。A）在队列中只能插入数据B）在队列中只能删除数据C）队列是先进先出的线性表D）队列是先进后出的线性表24一个队列的入队顺序是1,2,3,4,5, 则队列的出队顺序是（B ） 。A）5，4，3，2，1 B）1，2，3，4，5 C）3，2，1，5，4 D）4，5，3， 2，1 25树适合用来表示（D ） 。A）有序的数据元素B）无序的数据元素C）元素之间无任何联系的数据D）元素之间具有层次关系的数据26下列有关树的概念描述错误的是（A） 。A）树的度为树中各结点的度数之和B）树中只有一个无前

10、趋的结点C）树中每个结点的度数之和为结点总数减1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 19 页 - - - - - - - - - 数据结构与数据库技术复习题- 4 - D）树中所有叶子结点无后继27在一棵二叉树上第5 层的结点数最多是( B )。A）8 B）16 C）32 D）15 28设一棵完全二叉树共有699 个结点，则在该二叉树中的叶子结点数为( B )。A）349 B）350 C）255 D）351 29在深度为5 的满二叉树中，叶子结点的个数为(

11、C )。A）32 B）31 C）16 D）15 30下面关于二叉树的叙述正确的是（A） 。A）任一棵二叉树中叶子结点的个数等于度为的结点个数加B）任一棵二叉树的结点个数均大于0 C）二叉树中任何一个结点如果不是叶子结点，就一定有两个子结点D）二叉树中任何一个结点的左子树和右子树个数一定相等31任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序（B ） 。A）发生改变B）不发生改变C）不能确定D）以上都不对32 已知二叉树后序遍历序列是dabec， 中序遍历序列是debac， 它的前序遍历序列是 （A）A）cedba B） acbed C）decab D）deabc 33对线性表进行

12、折半查找时，要求线性表必须（B ） 。A）以顺序方式存储B）以顺序方式存储且结点按关键字有序排列C）以链接方式存储D）以链接方式存储且结点按关键字有序排列34顺序查找适用于存储结构为（A）的线性表。A）顺序存储或链接存储B）索引存储C）压缩存储D）散列存储35对长度为 N 的线性表进行顺序查找，在等概率情况下所需要的平均比较次数为( C )。A）N+1 B）N C）(N+1)/2 D）N/2 36采用顺序查找法查找长度为n 的线性表，每个元素的平均查找长度为（A） 。A） （n+1）/2 B）n C） （n-1）/2 D）n/2 37排序方法中， 将整个无序的序列划分成若干个小的子序列，然后分

13、别进行插入排序的方法称为（D ） 。A）选择排序B）快速排序C）冒泡排序D）希尔排序38快速排序方法在（D ）情况下最不利于发挥其长处。A）要排序的数据量很大B）要排序的数据中有多个相同值C）要排序的数据量很小D）要排序的数据已经基本有序39已知数据表A 中每个元素距其最终位置不远，为节省时间，应采用的算法是(B )。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 19 页 - - - - - - - - - 数据结构与数据库技术复习题- 5 - A）堆排序B）直接插入排

14、序C）快速排序D）直接选择排序40希尔排序法属于哪一种类型的排序法( B )。A）交换类排序法B）插入类排序法C）选择类排序法D）建堆排序法41在下列几种排序方法中，要求内存量最大的是( D )。A）插入排序B）选择排序C）快速排序D）归并排序42在数据管理技术的发展过程中，经历了人工管理阶段、文件系统阶段和数据库系统阶段。其中数据独立性最高的阶段是( A)。A）数据库系统B）文件系统C）人工管理D）数据项管理43在数据管理技术发展过程中，文件系统与数据库系统的主要区别是数据库系统具有( D )。A）数据无冗余B）数据可共享C）专门的数据管理软件D）特定的数据模型44下列叙述中正确的是( C

15、)。A）数据库是一个独立的系统，不需要操作系统的支持B）数据库设计是指设计数据库管理系统C）数据库技术的根本目标是要解决数据共享的问题D）数据库系统中，数据的物理结构必须与逻辑结构一致45下述关于数据库系统的叙述中，正确的是( A)。A）数据库系统减少了数据冗余B）数据库系统避免了一切冗余C）数据库系统中数据的一致性是指数据类型的一致D）数据库系统比文件系统能管理更多的数据46数据库系统的核心是（D ） 。A）软件工具B）数据模型C）数据库D）数据库管理系统47下列说法中，不属于数据模型所描述的内容的是( C )。A）数据结构B）数据操作C）数据查询D）数据约束48用树型结构来表示实体之间联系

16、的模型称为（A） 。A）层次模型B）关系模型C）数据模型D）网状模型49层次型、网状型和关系型数据库划分原则是（D ）A）记录长度B）文件的大小C）联系的复杂程度D）数据之间的联系方式50实体联系模型属于（D ） 。A）层次模型B）网状模型C）关系模型D）概念模型51数据库设计中反映用户对数据要求的模式是（C ）A）内模式B）概念模式C）外模式D）设计模式52下列模式中，能够给出数据库物理存储结构与物理存取方法的是( A)。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共

17、19 页 - - - - - - - - - 数据结构与数据库技术复习题- 6 - A）内模式B）外模式C）概念模式D）逻辑模式53将 E-R 图转换成关系模式时，实体与联系都可以表示成（D ） 。A）字段B）表C）关键字D）关系54对数据库中的数据可以进行插入、删除和修改等操作，这是因为数据库管理系统提供了（B ）功能。A）数据输入B）数据操纵C）数据输出D）数据控制55关系表中的每一横行称为一个( A)。A）元组B）字段C）属性D）码56在关系中的各元组的（B ） 。A）顺序不能任意排列一定要按照输入的顺序排列B）顺序可以任意排列C）顺序一定要按照关键字段值的顺序排列D）排列顺序不同统计处

18、理的结果就可能不同. 57对于关系的叙述，错误的是（D ） 。A）每个关系都只有一种记录类型B）关系中的每个属性是不可分的C）关系中任何两个元组不能完全相同D）任何一个二维表都是一个关系58在一个关系中，任意两个元组的值（C ） 。A）可以全同B）必须全同C）不能全同D）以上都不是59关系和关系进行自然连接时，要求关系间含有一个或多个公共（B ） 。A）行B）属性C）记录D）元组60关系数据库管理系统能实现的专门关系运算包括B )。A）排序、索引、统计B）选择、投影、连接C）关联、更新、排序D）显示、打印、制表61下列关系运算中，运算（D ）不要求关系R 与 S 具有相同的属性个数。A）R-S

19、 B）RS C）RS D）RS 62当两个子查询的结果（C ）时可以执行并、交、差操作。A）结构完全不一致时B）结构部分一致C）结构完全一致时D）主键一致63一个工作人员可以使用多台计算机，而一台计算机可被多个人使用，则实体工作人员、与实体计算机之间的联系是（C ）A）一对一B）一对多C）多对多D）多对一64 公司中有多个部门和多名职员，每个职员只能属于一个部门，一个部门可以有多名职员，职员与部门的联系类型是（C ） 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 19

20、 页 - - - - - - - - - 数据结构与数据库技术复习题- 7 - A）m : n B）1 : n C）n : 1 D）1 : 1 65有三个关系R、S 和 T 如下：R S T 则由关系 R 和 S 得到关系 T 的操作是（A） 。A）自然连接B）交C）投影D）并66在关系数据库中，用来表示实体之间联系的是( D )。A）树结构B）网结构C）线性表D）二维表67将 E-R 图转换到关系模式时，实体与联系都可以表示成( B )。A）属性B）关系C）键D）域68SQL 是（C ）的缩写。A）Standard Query Language B） Select Query Languag

21、e C）Structured Query Language D）以上都不是69SQL 中创建基本表应使用（C ）语句。A）CREATE VIEW B）CREATE DA TABASE C）CREATE TABLE D）CREATE FORM 70与 WHERE 年龄BETWEEN 32 AND 45 语句等价的子句是（D ） 。A）WHERE 年龄32 AND 年龄 =32 AND 年龄 32 AND 年龄 =32 AND 年龄 =45 二填空题1算法的复杂度主要包括_复杂度和空间复杂度。答：时间2数据的逻辑结构在计算机存储空间中的存放形式称为数据的_。答：物理结构3数据结构包括数据的_结构和

22、数据的存储结构。答：逻辑4线性结构中的数据元素之间存在着_的关系， 树型结构中的数据元素之间存在着的 _关系。答：一对一、一对多5实现算法所需的存储单元多少和算法的工作量大小分别称为算法的_。答：空间复杂度和时间复杂度A B C D c 3 1 4 A D c 4 A B C a 1 2 b 2 1 c 3 1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 19 页 - - - - - - - - - 数据结构与数据库技术复习题- 8 - 6数据结构包括数据的逻辑结构、

23、数据的_以及对数据的操作运算。答：存储结构7算法的基本特征是可行性、确定性、_和拥有足够的情报。答：有穷性8顺序存储方法是把逻辑上相邻的结点存储在物理位置_的存储单元中。答：相邻9栈的基本运算有三种：入栈、退栈和_。答：读栈顶元素或 读栈顶的元素或 读出栈顶元素10一个栈的初始状态为空。首先将元素5,4,3,2,1依次入栈，然后退栈一次，再将元素A,B,C,D 依次入栈，之后将所有元素全部退栈，则所有元素退栈（包括中间退栈的元素）的顺序为 _。答：1DCBA2345 11通常元素进栈的顺序是_ 。答：先移动栈顶指针，然后存入元素12循环队列是队列的_存储结构。答：顺序13深度为k 的完全二叉树

24、至少有_个结点，最多有_个结点。答：2k-1 、 2k-1 14一棵二叉树有10 个度为 1 的结点， 7 个度为 2 的结点，则该二叉树共有_个结点。答： 25 15在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为三种：前序遍历、_遍历和后序遍历。答：中序16设一棵完全二叉树共有500 个结点，则在该二叉树中有_个叶子结点。答：250 17在长度为n 的线性表中，寻找最大项至少需要比较_次。答：n-1 18每次从无序子表中取出一个元素，然后把它手稿到有序子表中的适当位置，此种排序方法称为 _排序。答： 插入19对 n 个元素的序列进行冒泡排序，最少的比较次数为_。答：n-1 2

25、0在最坏情况下，冒泡排序的时间复杂度为_。答： n(n-1)/2 或 O (n2) 21数据库系统中实现各种数据管理功能的核心软件称为_。答：数据库管理系统或 DBMS 22_是数据库应用的核心。答：数据库设计23数据库系统的三级模式分别为_模式、内部模式与外部模式。答：概念24数据模型按不同的应用层次分为三种类型，它们是 _数据模型、 逻辑数据模型和物理数据模型。答：概念25数据库管理系统常见的数据模型有层次模型、网状模型和_三种。答：关系模型26数据库保护分为：安全性控制、_、并发性控制和数据的恢复。答：完整性控制27一个项目具有一个项目主管，一个项目主管可管理多个项目，则实体“项目主管”

26、与实体“项目”的联系属于_的联系。答： 1 对多或 1：N 28如果一个工人可管理多个设施，而一个设施只被一个工人管理，则实体工人 与实体 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 19 页 - - - - - - - - - 数据结构与数据库技术复习题- 9 - 设备 之间存在 _联系。答：一对多或 1：N 或 1:n 29关系模型的完整性规则是对关系的某种约束条件，包括实体完整性、_和自定义完整性。参照完整性30 在关系模型中，表的行称为_，列称为属性。答：元组

27、31关系模型的数据操纵即是建立在关系上的数据操纵，一般有 _、增加、删除和修改四种操作。答：查询32关系数据库管理系统能实现的专门关系运算包括选择、连接和_。答：投影33数据库系统和文件系统的主要区别是_的方式不同。答：组织数据34数据库技术采用分级的方法将其结构划分为多个层次，其目的就是为了提高数据库的_。 答：逻辑独立性和物理独立性35层次模型、网状模型和关系模型的划分原则是_。答：数据之间的联系方式36. 在数据库系统中， 数据的独立性分为逻辑独立性和物理独立性。模式 / 内模式的映射为数据库提供了 _数据独立性。答：物理37数据库技术的主要特点是_，因此具有较高的数据和程序的独立性。答

28、：数据共享性38数据库设计的四个阶段是：需求分析，概念设计，逻辑设计，_。答：物理设计39数据库设计分为以下6 个设计阶段：需求分析阶段、_、逻辑设计阶段、物理设计阶段、实施阶段、运行和维护阶段。答：概念设计阶段或 数据库概念设计阶段40. 在数据库的E-R 图中，矩形框表示的是_。 答：实体三、判断题：在下列各小题后的括号里对的打“” ，错的打“ X”1算法的执行效率与数据的存储结构无关。（ X ）2栈与队列是非线性结构（X ）3算法的有穷性是指算法必须能在执行有限个步骤之后终止。（）4在栈中只能删除数据。 （ X ）5在栈中只能插入数据。 （ X ）6线性链表是非线性结构。（X ）7二叉树

29、是线性结构。 （ X ）8线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的（X ）9线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构（）10线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构（X ）11在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化（X ）12在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化（X ）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 19 页 - - - - - - - - - 数据结构与数据库技术复习

30、题- 10 - 13在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化（）13栈是先进先出的线性表（X ）14栈是先进后出的线性表（）15在队列中只能插入数据（X ）16在队列中只能删除数据（X ）17队列是先进先出的线性表（）18树的度为树中各结点的度数之和（X ）19树中只有一个无前趋的结点（）20树中每个结点的度数之和为结点总数减1（）21树中所有叶子结点无后继（）22任一棵二叉树中叶子结点的个数等于度为的结点个数加（）23任一棵二叉树的结点个数均大于0（ X ）24二叉树中任何一个结点如果不是叶子结点，就一定有两个子结点（X ）25二叉树中任何一个结点的左子树和右子树个数一定相等

31、（X ）26在数据库的三级模式结构中，内模式有任意多个。（ X ）27层次模型用树型结构表示实体及实体间的联系。（）28数据库是一个独立的系统，不需要操作系统的支持（X ）29数据库设计是指设计数据库管理系统（X ）30数据库技术的根本目标是要解决数据共享的问题（）31数据库系统中，数据的物理结构必须与逻辑结构一致（X ）32数据库系统减少了数据冗余（）33数据库系统避免了一切冗余（X ）34数据库系统中数据的一致性是指数据类型的一致（X ）35数据库系统比文件系统能管理更多的数据（X ）36每个关系都只有一种记录类型（）37关系中的每个属性是不可分的（）38关系中任何两个元组不能完全相同（）

32、39任何一个二维表都是一个关系（X ）40在关系数据库表中外键只有一个，但候选码可以有多个。（ X ）四、应用题1、给出下面的语句组所代表的算法的时间复杂度。i=1;k=0;n=100 do k=k+10*i; i+; while(i=n) ; 答：时间复杂度为：O(1) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 19 页 - - - - - - - - - 数据结构与数据库技术复习题- 11 - 2、根据给定的结点集合（10，15，7，75，34，61，3，9）

33、的顺序输入，构造一棵完全二叉树。解：完全二叉树为：3、设记录的关键字集合KEY= （15， 18，13，16，17，19，7，3，4，2） ，试写出对KEY进行希尔排序（ d=5，3，1）时，各趟排序结束后的结果。解初始关键字15 18 13 16 17 19 7 3 4 5 一趟排序后结果（d=5） 15 7 3 4 5 19 18 13 16 17 二趟排序后结果（d=3）4 5 3 15 7 16 17 13 19 18 三趟排序后结果（d=1）3 4 5 7 13 15 16 17 18 19 4、将下面给出的树转化为二叉树。解转化的二叉树如下：5、对长度为8 的有序顺序表，给出折半查

34、找的判定树。答：6、已知序列（ 70，83，100，65，10，32，7，9） ，写出采用直接插入排序方法对该序列进行升序排序时的每一趟的结果。解：采用直接插入排序方法排序的各趟的结果如下：初始化：70 ，83，100，65，10，32，7，9 第一趟排序结果： 70，83 ，100，65，10，32， 7，9 第二趟排序结果：70， 83，100 ，65，10，32，7，9 第三趟排序结果：65， 70，83，100 ，10，32，7，9 第四趟排序结果：10， 65，70，83，100 ，32，7，9 10 7 61 3 15 75 9 34 a b c d e a b c d e 名师资

35、料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 19 页 - - - - - - - - - 数据结构与数据库技术复习题- 12 - 第五趟排序结果：10， 32，65，70，83，100 ，7，9 第六趟排序结果：7，10，32， 65，70，83，100 ，9 第七趟排序结果：7，9，10，32，65， 70，83，100 7、已知某二叉树的先序序列为ABDGHCEFI ，中序序列为GDHBAECIF ，画出该二叉树。解：8、已知某二叉树如下图所示，给出该二叉树的中序遍历

36、序列。解：该二叉树的中序序列为BDCAEF 。9、有一组关键字为：26， 05，37，01，62，11，59，15，采用快速排序方法对其进行由小到大的排序，请写出每趟排序结果。解：各趟的排序结果如下：初始化： 26，05，37，01，62，11，59，15 第一趟排序结果： 15 ，05，11，01， 26，62，59，37 第二趟排序结果： 01 ，05，11，15， 26， 37，59，62第三趟排序结果：01，05，11，15，26，37， 59，62排序结束，得到结果序列：01，05，11，15，26， 37，59，62 10、已知教学数据库中有三个基本表：学生信息表student 、

37、学生成绩表xscj 和课程表kcb如下所示。B C D E F A G H I B E D C F A 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 19 页 - - - - - - - - - 数据结构与数据库技术复习题- 13 - 要求使用SQL语句完成下列操作：（1） 要求把学生赵通的姓名改为赵彤。答： Update 学生 set 姓名 =赵彤 where 姓名 =赵通（2）查询男生所学课程的成绩，要求显示姓名，课程名，分数。答： Select 姓名，课程名，分

38、数 from 学生，选课 , 课程 where 性别 =男 and 课程 . 课程号 =选课 . 课程号 and 选课 . 学号 =学生 . 学号（3）查找北京学生的姓名及所在的班级。答：select 姓名，班级 from student where 出生地 =北京市（4）查找自动化981 班学生所学课程的课程名和任课教师。答：select distinct 课程名 ,任课教师 from student, xscj, kcb; where student.学号 =xscj. 学号 and xscj.课程号 =kcb. 课程号 ; and student.班级=自动化981（5）删除成绩为良的记

39、录。答：delete from xscj where 成绩 90 and 成绩 =80 （6）将所有不及格的成绩增加10 分。答：update xscj set 成绩 =成绩 +10 where 成绩 60 要求使用关系代数表达式实现下列功能：（1）列出成绩在75 分（包含 75 分）以上的所有记录。答：关系代数表达式为：成绩 75(xscj)（2）列出不及格学生的姓名和课程名。答：关系代数表达式为：姓名, 课程名( 成绩 next!=NULL) (G) /*p 指向第 i 个结点 */ i+; 2）将单链表就地逆置。void test2 (struct node *head) struct

40、node *p,*q; p=head-next; /*p 指向第一个数据结点*/ (I) /*将原链表置为空表H*/ while (p!=NULL) q=p; p=p-next; (A) /*将当前结点插到头结点的后面*/ head-next=q; 3）将单链表中值相同的多余结点删除。void test3(struct node *head) struct node *p,*q,*r; p=head; while (p!=NULL) r=p; (D) while (q!=NULL) if (q-data=p-data) (E) else r=q; q=q-next; (G) 4）将值为 y 的

41、结点插入到值为x的结点之后，如果值为x 的结点不存在，则将其插入到单链表的表尾。void test4(struct node *head,int x, int y) struct node *p,*q,*r; r=(struct node *)malloc(sizeof(struct node); r-data=y; p=head-next; while (p!=NULL& p-data!=x) (C) p=p-next; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共

42、 19 页 - - - - - - - - - 数据结构与数据库技术复习题- 16 - if (p=NULL) (J) else （ H）q-next=r; 本题选项：(A)q-next=head-next; (B) p=head; (C)q=p; (D) q=p-next; (E) r-next=q-next; (F)p-next=head; (G)p=p-next; (H)r-next=p; (I)head-next=NULL; (J)r-next=NULL;（二）完善算法1）出栈算法int Pop_SeqStack (SeqStack *s, datatype x) if ( s-top

43、= -1 ) /*判断栈空 */return 0; else x = s-datas-top; /*取栈顶元素*/s-top+; /*修改栈顶指针*/return 1; 2）入栈算法int Push_SeqStack (SeqStack *s, datatype x) if （s-top=MAXSIZE-1 ) /*判断栈满 */return 0; else s-top+; /*修改栈顶指针 */s-datas-top=x; return 1; 3）入队算法int In_SeQueue ( c_SeQueue *q , datatype x) if ( q-front=(q-rear+1) %

44、 MAXSIZE ) /*判队满 */ printf( 队满 ); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 19 页 - - - - - - - - - 数据结构与数据库技术复习题- 17 - return -1; else q-rear=(q-rear+1) % MAXSIZE; /*修改队尾指针*/ q-dataq-rear=x; /*入队元素 */ return 1; 4）有序表的折半查找算法int Binary_Search(S_TBL tbl，KeyT

45、ype kx) int low, high, mid ，flag=0；low=1 ；high=tbl.length ；/* 设置初始区间*/ while(low=high) /* 表空测试*/ mid=(low+high)/2 ；/* 得到中点*/if(kxtbl.elemmid.key) low=mid+1 ；/* 调整到右半区*/ else flag=mid;break; /* 查找成功，元素位置设置到flag 中 */ return flag; 六、综合题1假定一个教学数据库包括以下的实体及属性：教师：教师编号，姓名，年龄，性别；课程：课程编号，课名，课程性质；课程组：编号，名称，负责人

46、；每个课程组有若干教师，每个教师可参加若干个课程组；教师参加课程组有“参加时间”。每个课程组管理若干门课程，每门课程只属于一个课程组。请解答如下问题: (1) 根据给定语义画出E-R 图，并在图上注明属性、联系类型、实体标识符。(2) 将 E-R 图转换成等价的关系模式, 并注明每个关系模式的主键，外键。答： (1)名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 19 页 - - - - - - - - - 数据结构与数据库技术复习题- 18 - （2）假设课程组名称不

47、唯一课程组（编号，名称，负责人）主键：编号外键：负责人教师（教师编号，姓名，性别，年龄）主键：教师编号课程（课程编号，课名，课程性质，编号）主键：课程编号外键：编号参加（编号，教师编号，参加时间）主键：（编号，教师编号） 外键：编号；教师编号号2假定一个部门的数据库包括以下的实体及属性：职工：职工号、姓名、住址。部门：部门名、经理。产品：产品编号、产品名。制造商：名称、地址、电话。其中：一个部门可以包括多名职工、一个职工只能在一个部门工作；一个部门可以销售多种产品，一种产品可由多个部门销售，每个部门销售每种产品，有月销售量；一个制造商可以生产多种产品，一种产品可以由多个制造商生产；制造商生产的

48、每种产品都有型号、价格属性。完成如下设计：（1）设计该计算机管理系统的实体-关系（ ER）图；并在图上注明属性、联系类型、实体。答：该管理系统的E R 图如下：n 课程组名称编号负责人教 师m 参加教师编号姓名年龄性别参加时间n 从属1 课程课名课程编号课程性质名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 19 页 - - - - - - - - - 数据结构与数据库技术复习题- 19 - （2）将该 E-R 图转换为关系模型；并注明每个关系模式的主码，外码。答：该

49、E-R 图转换的关系模型如下：职工（职工号，姓名，地址，部门名）主键：职工号，外键：部门名部门（部门名，经理）主键：部门名产品（产品编号，产品名）主键：产品编号销售（部门名，产品编号，月销售量）主键：（部门名，产品编号）外键：部门名；产品编号生产（产品编号，名称，型号，价格）主键： （产品编号，名称）外键：产品编号；名称制造商（名称，地址）主键：名称月销售量1 m n 销 售制造商生产职工部门产品从 属n m n 名称地址职工号姓名地址部门名经理产品名产品编号型号价格电话名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 19 页 - - - - - - - - -