浙江理工大学938数据结构与数据库技术17-18年真题

数据结构试卷（一）王彬一、单选题（每题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进制表示。

cA．688 B．678 C．692 D．6965.树最适合用来表示( )。

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

A.5B.6C.7D.8二、填空题（每空1分，共26分）1.通常从四个方面评价算法的质量：____ ____、________、________和_______。

2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。

浙江省数据库技术三级考试历年试题2010年秋浙江省高等学校计算机等级考试试卷（三级数据库技术及应用）1．基础知识（共60分）（1）～（10）：判断题（共10分）（1）数据结构就是数据之间的逻辑结构。

（2）链式存储的线性表可以随机存储。

（3）后缀表达式“3 4 * 2 1 + -”的值是9。

（4）完全二叉树一定是正则二叉树。

（5）顺序查找的优点是对线性表结点的逻辑顺序没有要求，对线性表的存储结构也没有要求。

（6）层次模型是数据库系统中最早出现的数据模型，层次数据库系统采用层次模型作为数据的组织方式。

（7）在数据库三级模式结构中，外模式和内模式之间的映像实现数据的物理独立性。

（8）一个二维表就是一个关系，二维表的表名就是关系名。

（9）规范化过程主要是为克服数据库逻辑结构中的插入异常、删除异常以及结构不合理的缺陷。

（10）等值连接与自然连接相比较，等值连接的属性个数总大于自然连接的属性个数。

答案：×；×；√；×；√；√；×；×；×；√。

（11）～（35）（共50分）（11）A算法的时间复杂度为O（n3），B算法的时间复杂度为O（2n），说明（）。

A．对于任何数据量，A算法的时间开销都比B算法小。

B．对于任何数据量，A算法的时间开销都比B算法大。

C．随着问题规模n的增大，A算法比B算法有效。

D．随着问题规模n的增大，B算法比A算法有效。

（12）（）适合作为经常在首尾两端操作线性表的存储结构。

A．顺序表B．单链表C．循环链表D．双向链表（13）在一个单链表中，删除p所指的直接后继操作是（）。

A．p->next=p->next->next B．p= p->next->nextC．p=p->next D．p->next->next=p->next（14）在带有头结点的双链表l中，指针p所指结点是第一个结点的条件是（）。

浙江理工大学数据结构与算法期末样卷(1)模拟试卷二一、单选题（每题2分，共20分）1．在一个具有额外字段结点的单链表中hl中，若要向字段填入一个由指针p指向的结点，则继续执行()a.hl=p;p->next=hl;b.p->next=hl->next;hl->next=p;c.p->next=hl;p=hl;d.p->next=hl;hl=p;2．若顺序存储的循环队列的queuemaxsize=n,则该队列最多可以存储（）个元素a.nb.n-1c.n+1d.不确定3．下列哪一条就是顺序存储方式的优点？（）a.存储密度大b.插入和删除运算方便c.获取符合某种条件的元素方便d.查找运算速度快4．建有一个二维数组a[m][n]，假设a[0][0]放置边线在600(10)，a[3][3]放置边线在678(10)，每个元素占到一个空间，问a[2][3](10)存放在什么边线？(注释(10)则表示用10十进制则表示,m>3)a.658b.648c.633d.6535．下列关于二叉树遍历的叙述中，正确的是()a.若一个树叶就是某二叉树的中序结点的最后一个结点，则它必就是该二叉树的前序结点最后一个结点b.若一个点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点c.若一个结点就是某二叉树的中序结点的最后一个结点，则它必就是该二叉树的前序最后一个结点d.若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点6．k层二叉树的结点总数最多为()a.2k-1b.2k+1c.2k-1d.2k-17．对线性表展开二分法搜寻，其前提条件就是()a.线性表以链接方式存储，并且按关键码值排好序b.线性表以顺序方式存储，并且按关键码值的检索频率排好序c.线性表以顺序方式存储，并且按关键码值排好序d.线性表以链接方式存储，并且按关键码值的检索频率排好序8．对n个记录进行堆排序，所需要的辅助存储空间为()a.o（1og2n）b.o（n）c.o（1）d.o（n2）9．对于线性表（7，34，77，25，64，49，20，14）展开杂凑存储时，若采用h（k）=k%7做为杂凑函数，则杂凑地址为0的元素存有（）个，a.1b.2c.3d.410．以下关于数据结构的描述中，恰当的就是()a.数组就是相同类型值的子集b.递归算法的程序结构比迭代算法的程序结构更为精炼c.树是一种线性结构d.用一维数组存储一棵全然二叉树就是有效率的存储方法二、填空题（每空1分，共26分）1．数据的逻辑结构被分成_________、________、__________和___________四种。

考试科目：数据结构与数据库技术代码：9381234 758961234758963．已知单链表结构如下所示，头结点指针为head ，关键字域为key 。

试编写一个程序，采用单链表作为存储结构实现简单（直接）选择排序算法，并阐述该算法的时间复杂度与稳定性。

（本题25分）分） typedef struct node { int key; struct node *next; } lnode; 4．已知哈希（Hash ）函数H(k)=k%p （k 为线性表的关键字），用开放地址法处理冲突，其中：d 1=H(k)，d i =(d i-1+m)%p (i=2,3,…)；试编写程序算法，在H[0~p-1]的散列地址空间中，地址空间中，对关键字序列对关键字序列a[0],a[1],…,a[p a[0],a[1],…,a[p-1]-1]构造哈希表构造哈希表（假设每个关键字最终都能（假设每个关键字最终都能找到地址），并计算输出在等概率情况下查找成功的平均查找长度。

（20分）第二部分：数据库技术（本部分共60分）二、解答题（下面10个小题中任选6小题解答，每小题10分，按得分最多的6小题计算分数，本题得分最多不超过60分）数据库Sales 用来存放某企业销售数据，用来存放某企业销售数据，它有它有4张表，张表，表表Products 用来存储产品基本信息；表Customers 用来存储客户基本信息；表Orders 用来存放订单信息；OrderItems 用来存放订单明细信息。

这4张表的结构如下：张表的结构如下：1． Products 表结构：表结构：列名类型 长度 规则 中文说明 ProductID 数值型数值型 8 主键主键 产品编码产品编码 ProductName 字符型字符型 30 非空非空 产品名称产品名称 Category 字符型字符型 20 非空 产品类别产品类别 QuantityPerUnit 字符型字符型 20 非空 规格型号规格型号 UnitPrice 数值型数值型8, 2 成本单价成本单价Products 表记录举例：表记录举例：ProductID ProductName Category QuantityPerUnit UnitPrice 1 Chai Beverages 10 boxes x 20 bags 18.20 2 Chang Beverages 24 – 12 oz bottles 19.50 3 Aniseed Syrup Condiments 12 – 550 ml bottles 10.25 4 Chef Anton’s Gumbo MixCondiments 36 boxes 21.35 5 Northwoods Cranberry Sauce Condiments 12 – 12 oz jars 40.00 6 Genen Shouyu Condiments 24 – 250 ml bottles 15.50 … …… … … 77 Escargots de Bourgogne Seafood 24 pieces 13.25 2. Customers表结构：表结构：列名类型长度规则中文说明CustomerID 字符型5 主键客户编码主键 客户编码CustomerName 字符型50 非空客户名称非空 客户名称Address 字符型60 单位地址单位地址 City 字符型20 所在城市所在城市 Customers表记录举例：表记录举例：CustomerID CustomerName Address City ALFKI Alfreds Futterkiste Obere Str. 57 Berlin n 222 MéANATR Ana Trujillo Emparedados y helados Avda. De la Constitución 222 xico D.F. México D.F. ANTON Antonio Moreno Taquería a Mataderos 2312 México D.F. México D.F. AROUT Around the Horn 120 Hanover Sq. London …………3. Orders表结构：表结构：列名类型长度规则中文说明OrderID 数值型订单编号数值型 8 主键主键 订单编号CustomerID字符型非空，外键 客户编码客户编码字符型 5 非空，外键OrderDate日期型订单日期日期型 8 非空订单日期RequiredDate日期型要货日期日期型 8 非空要货日期ShippedDate日期型发货日期日期型 8 非空发货日期Orders表记录举例：表记录举例：OrderID CustomerID OrderDate RequiredDate ShippedDate 10248 VINET 2006-07-04 2006-08-01 2006-07-26 10249 TOMSP 2006-07-05 2006-08-16 2006-07-30 10250 HANAR 2006-08-08 2006-09-05 2006-09-03 10251 VINET 2006-08-11 2006-09-15 2006-09-12 ……………4. OrderItems表结构：表结构：列名类型长度规则中文说明OrderID 数值型数值型 8 外键订单编号外键 订单编号ProductID数值型产品编码外键 产品编码数值型 8 外键UnitPrice数值型销售单价 数值型 8,2 两位小数，单价大于0销售单价Quantity数值型销售数量 数值型 8 非空，默认为0销售数量Amount 数值型销售额 数值型 12,2 计算列（=unitprice*quantity）销售额OrderItems表记录举例：表记录举例：OrderID ProductID UnitPrice Quantity Amount 10248 11 14 12.5 175.00 10248 42 9 10.4 93.60 10248 72 34 5.6 190.40 10249 14 18 9.5 171.00 10249 51 42 40.45 1698.90 10250 41 7 10.25 71.75 10250 51 42 35.25 1480.50 ……………1. 使用SQL语句，完成以下各项功能（注：必要时一个小题可以用多条语句去实现）：1)根据产品表Products中数据，列出单价排名最贵的前5个产品的名称及其单价。

2022年浙江理工大学信息管理与信息系统专业《数据库概论》科目期末试卷B（有答案）一、填空题1、在数据库系统封锁协议中，一级协议：“事务在修改数据A前必须先对其加X锁，直到事务结束才释放X锁”，该协议可以防止______；二级协议是在一级协议的基础上加上“事务T在读数据R之前必须先对其加S锁，读完后即可释放S锁”，该协议可以防止______；三级协议是在一级协议的基础上加上“事务T在读数据R之前必须先对其加S锁，直到事务结束后才释放S锁”，该协议可以防止______。

2、安全性控制的一般方法有____________、____________、____________、和____________视图的保护五级安全措施。

3、在RDBMS中，通过某种代价模型计算各种查询的执行代价。

在集中式数据库中，查询的执行开销主要包括______和______代价。

在多用户数据库中，还应考虑查询的内存代价开销。

4、以子模式为框架的数据库是______________；以模式为框架的数据库是______________；以物理模式为框架的数据库是______________。

5、在一个关系R中，若每个数据项都是不可再分割的，那么R一定属于______。

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

7、设有关系模式R（A，B，C）和S（E，A，F），若R.A是R的主码，S.A是S的外码，则S.A的值或者等于R中某个元组的主码值，或者______取空值，这是规则，它是通过______和______约束来实现的。

8、如果多个事务依次执行，则称事务是执行______；如果利用分时的方法，同时处理多个事务，则称事务是执行______。

9、关系数据库中基于数学的两类运算是______________和______________。