大连理工大学软件学院2014数据结构期末考试)
一、选择(2’×15=30’)
1.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时
间复杂度为( )
A.O(0)
B.O(1)
C.O(n)
D.O(n2)
2.用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾
结点，则在进行删除操作时( )
A.仅修改队头指针
B.仅修改队尾指针
C.队头、队尾指针都不修改
D.队头、队尾指针都可能要修改
3.设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g依次进入栈S，若每个元素出栈
后立即进入队列Q，且7个元素出队的顺序是b,d,c,f,e,a,g，则栈S的容量至少是( )
A.1
B.2
C.3
D.4
4.对n(n≥2)个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是( )
A.该树一定是一棵完全二叉树
B.树中一定没有度为1的结点
C.树中两个权值最小的结点一定是兄弟结点
D.树中任一非叶结点的权值一定不小于下一层任一结点的权值
5.一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是( )
A.CABDEFG
B.ABCDEFG
C.DACEFBG
D.ADCFEG
6.下列线索二叉树中（用虚线表示线索），符合后序线索二叉树定义的是( D)
7.下面关于二分查找的叙述正确的是( )
A.表必须有序，表可以顺序方式存储，也可以链表方式存储
B.表必须有序，且表中数据必须是整型，实型或字符型
C.表必须有序，而且只能从小到大排列
D.表必须有序，且表只能以顺序方式存储
8.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受
数据初始特性影响的是( )
A.直接插入排序
B.快速排序
C.直接选择排序
D.堆排序
9.下列关于无向连通图特性的叙述中，正确的是( )
I.所有顶点的度之和为偶数
II.边数大于顶点个数减1
III.至少有一个顶点的度为1
A.只有I
B.只有II
C.I和II
D.I和III
10.在下列所示的平衡二叉树中插入关键字48后，得到一棵新平衡二叉树，在新平衡二
叉树中，关键字37所在结点的左、右子结点保存的关键字分别是( )
A.13,48
B.24,48
C.24,53
D.24,90
11.若数据元素序列11,12,13,7,8,9,23,4,5是采用下列排序方法之一得到的第二趟排序后
的结果，则该排序算法只能是( )
A.冒泡排序
B.插入排序
C.选择排序
D.二路归并排序
12.下列排序算法中，其中( )是稳定的
A.堆排序，冒泡排序
B.快速排序，堆排序
C.直接选择排序，归并排序
D.归并排序，冒泡排序
13.下列叙述中，不符合m阶B-树定义要求的是( )
A.根节点最多有m棵子树
B.所有叶结点都在同一层上
C.各结点内关键字均升序或降序排列
D.叶结点之间通过指针链接
14.已知关键序列5,8,12,19,28,20,15,22是小根堆（最小堆），插入关键字3，调整后得到
的小根堆是( )
A.3,5,12,8,28,20,15,22,19
B.3,5,12,19,20,15,22,8,28
C.3,8,12,5,20,15,22,28,19
D.3,12,5,8,28,20,15,22,19
15.下列AOE网表示一项包含8个活动的工程，通过同时加快若干活动的进度可以缩短
整个工程的工期，下列选项中，加快其进度就可以缩短工程工期的是( )
A.c和e
B.d和e
C.f和d
D.f和h
二、简答(60’)
1.(10’)用序列(46,88,45,39,70,58,101,10,66,34)建立一棵二叉搜索树，画出该树，并求在
等概率情况下查找成功和查找不成功的平均查找长度，画出依次删除46,58后的二叉搜索树
2.(8’)设字符a,b,c,d,e,f 的使用频度分别为25,20,6,14,28,7，求a,b,c,d,e,f 的哈夫曼编码并给出相应的哈夫曼树，计算带权路径长度
3.(10’)设G=(V,E)的邻接表存储如下所示，试画出该图，给出深度优先和广度优先搜索序列，并画出深度优先和广度优先生成树
4.(6’)已知一个森林的先序序列和后序序列如下，请构造出该森林
先序序列：ABCDEFGHIJKLMNO
后序序列：CDEBFHIJGAMLONK
5.(6’)图的邻接矩阵如下，试给出弗洛伊德算法求各点间最短距离的矩阵序列A 1,A 2,A 3,A 4
A = [0 2 ∞ ∞
∞ 0 1 65 ∞ 0 4
3 ∞ ∞ 0
] 6.(10’)一组记录的关键码为{45,81,67,36,40,85,52,43}，按照递增序进行排序
⑴.分别给出冒泡排序、快速排序（以第一个元素为轴）、二路归并排序的第一趟排序结果
⑵.画出初始的最大堆（给出调整过程）
7.(10’)选择哈希函数H(Key)=Key%13，用开放定址法处理冲突，探查的地址序列为H(Key),H(Key)+1,H(Key)+3,H(Key)+5,……试构造给定关键字序列{22,31,40,03,47,69,14, 27,15,01,61,55,78}的哈希表；查找27,15各要比较多少呢？计算在等概率的条件下查找成功时的平均查找长度
三、算法设计(10’)
简要描述Dijkstra 算法的思想；
设带权有向图G 的邻接矩阵为A ，给出利用Dijkstra 算法，计算G 中一点到其余各顶点的最短路径及最短路径长度的程序代码
2014级《数据库理论与技术》课程期中试卷
宁波工程学院2015–2016学年第2学期 《数据库理论与技术》课程期中考试卷 一、单项选择题（每小题1分，共20分） 1. （ B ）是长期存储在计算机内、有组织的、可共享的数据集合。 A．数据库系统 B．数据库 C．关系数据库 D．数据库管理系统 2. 下面哪个不是数据库系统必须提供的数据控制功能（B ）。 A．安全性 B．可移植性 C．完整性 D．并发控制 3. 通过修改（ C ）可以保证数据库的逻辑独立性。 A．模式 B．外模式 C．外模式/模式映射 D．模式/内模式映射 4. 学生社团可以接纳多名学生参加，但每个学生只能参加一个社团，从社团到学生之间的联系种类是( D )。 A.多对多 B.一对一 C.多对一 D. 5. 结构数据模型的三个组成部分中，不包括（ C ）。 A．完整性规则 B．数据结构 C．恢复 D．数据操作 6. SQL中，下列涉及空值的操作，不正确的是（ C ）。 A．AGE IS NULL B．AGE IS NOT NULL C．AGE=NULL D．NOT（AGE IS NULL）
7. 设有关系模式R （A ，B ，C ），其关系r 如右表所示： 下面叙述正确的是（ B ）。 A ．函数依赖 A → B 在上述关系中成立 B ．函数依赖 B C → A 在上述关系中成立 C ．函数依赖 B → A 在上述关系中成立 D ．函数依赖 A → BC 在上述关系中成立 8. 关系数据库规范化是为了解决关系数据库中（ A ）。 A ．插入、删除和数据冗余问题而引入的 B ．提高查询速度问题而引入的 C ．减少数据操作的复杂性问题而引入的 D ．保证数据的安全性和完整性问题而引入的 9. 实现关系代数选择运算的SQL 子句是（ D ）。 A ．SELECT B ．ORDER BY C ．FROM D ．WHERE 10.设关系R 和S 的属性个数分别为2和3，则与关系代数表示式 12R S >等价的是（ B ）。 A ．12(R S)σ>? B ．14(R S)σ>? C ．14(R S)σ> D ．12(R S)σ> 11.在关系模式R(A,B,C,D)中，有函数依赖集F={A→B,B→C,C→D}，则R 能达到（ B ）。 A ．1NF B ．2NF C ．3NF D ．以上三者都不行 12.SQL 的视图是从（ C ）中导出的。 A ．基本表 B ．视图 C ．基本表或视图 D ．数据库 13.在关系数据库中，实现数据之间联系的是（ B ）。 A ．主键码 B ．外键码 C ．域 D ．指针 14.下面列出的选项，哪项是关系数据库的基本特征？ ①.不同的列应有不同的数据类型；②.不同的列应有不同的列名；③.与行的次序无关；④.与列的次序无关。（ C ）
数据结构习题集(积分)
第一章绪论 1．下面是几种数据的逻辑结构S=(D，R)，分别画出对应的数据逻辑结构，并指出它们分别属于何种结构。 D={a，b，c，d，e，f} R={r} (a) r={ 南阳理工学院2013-2014学年第2学期试卷（A卷） 课程：《数据结构》课程号：1504108130 考核方式：（闭卷）课程性质：专业必修课适用对象：12级软件工程专业 题号一二三四五总分复核人 满分20 20 10 30 20 100 得分 评卷人得分 一、选择题：（每题2 分，共20 分） 1.设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06， 07，08，09}，R={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03， 07>，<03，08>，<03，09>}，则数据结构A是（）。 A.线性结构 B.树型结构 C.物理结构 D.图型结构 2.栈和队列的共同特点是（）。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 3.在头指针为head的循环链表中，判断指针变量P指向尾结点的条件是（）。 A.p->next->next==head B.p->next==head C.p->next->next==NULL D.p->next==NULL 4.在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（）。 A.s->next=p+1; p->next=s; B.(*p).next=s; (*s).next=(*p).next; C.s->next=p->next; p->next=s->next; D.s->next=p->next; p->next=s; 5.数组Q[n]用来表示一个循环队列，f为当前队列头元素的前一位置，r为队尾 元素的位置，假定队列中元素的个数小于n，计算队列中元素个数的公式为 （）。 A.r-f B.(n+f-r)%n C.n+r-f D.（n+r-f)%n 6.设有数组A[0..7][0..9]，数组的每个元素长度为2字节，数组从内存首地址 1000开始顺序存放，当用以行为主存放时，元素A[5][8]的存储首地址为（）。 A.1116 B.1094 C.1138 D.1120 7.若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上 所有元素)依次存放于一维数组B[1..n(n+1)/2]中，则在B中确定a ij（i 全国2014年4月高等教育自学考试互联网数据库试题 (课程代码 00911) 一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。 1．在数据模型的三个要素中，用于描述系统静态特性的是B A．数据操作B．数据结构 C．数据完整性约束D．数据参照 2．SQL语言中的REVOKE语句的主要作用是C A．结束程序B．返回系统 C．收回权限D．提交事务 3．JDBC包含多个类，其中Java．sql．Time类属于A A．Java JDBC类B．Java JDBC接口 C．Java JDBC异常D．Java JDBC控制 4．在CGI程序中，如果采用GET方法传递参数，用来传递查询条件参数的环境变量是D A．ENV-STRING B．CONDITION-STRING C．CONTENT-STRING D．QUERY-STRING 5．在SQL语句中，与X BETWEEN 60 AND 90等价的表达式是B A．X>60 AND X<90 B．X>=60 AND X< =90 C．X>60 AND X< =90 D．X>=60 AND X<90 →， 6．如果关系模式R(U，F)中不存在候选码X、属性组Y以及非属性Z(Z?Y)，使得X Y →和Y→Z成立，则R属于A Y X A．3 NF B．4 NF C．5 NF D．BCNF 7．在目前的并行数据库体系结构中，实现技术最容易的是C A．SN B．SD C．SM D．SK 8．在ASP的内置对象中，从客户端用户提取信息的是C A．Session对象B．System对象 C．Request对象D．Application对象 9．实体完整性规则规定基本关系中的D A．元组不能取空值B．属性不能取空值 C．外码不能取空值D．所有主属性都不能取空值 10．保护数据以防止未经授权或不合法的使用造成的数据泄露、更改或破坏，是指数据库的B 枣庄学院信息科学与工程学院 课程设计任务书 题目：企业工资管理系统 学号： 姓名： 专业：网络工程 课程：数据库系统概论 指导教师：职称： 完成时间： 20 11 年 12 月----2011 年 12 月 枣庄学院信息科学与工程学院制 年月日 课程设计任务书及成绩评定 目录 第一章目的 《数据库系统概论》课程设计对于巩固数据库知识，加强学生的实际动手能力和提高学生综合素质十分必要。本课程设计实验主要围绕两方面内容：数据库设计和基本数据库编程实践。通过本实验，使学生了解数据库系统的理论，掌握数据库的设计方法及数据库的运用和基本开发技术。 1. 掌握数据库设计的基本方法，熟悉数据库设计的步骤； 2. 通过设计数据库系统应用课题，进一步熟悉数据库管理系统的操作技术，提高动手能力，提高分析问题和解决问题的能力； 3. 学习基本数据库编程方法。 第二章引言 企业工资管理系统是一个中小型企业单位不可缺少的部分,它的内容对于中小企业的决策者和管理者来说都至关重要,所以企业工资管理系统应该能够为用户提供充足的信息和快捷的查询手段。但一直以来人们使用传统人工的方式管理文件工资，这种管理方式存在着许多缺点,如:效率低、保密性差,另外时间一长,将产生大量的文件和数据,这对于查找、更新和维护都带来了不少的困难。 随着科学技术的不断提高,计算机科学日渐成熟,其强大的功能已为人们深刻认识,它已进入人类社会的各个领域并发挥着越来越重要的作用。 作为计算机应用的一部分,使用计算机对员工工资信息进行管理,具有着手工管理所无法比拟的优点.例如:检索迅速、查找方便、可靠性高、存储量大、保密性好、寿命长、成本低等。这些优点能够极大地提高企业工资管理的效率,也是企业的科学化、正规化管理,与世界接轨的重要条件。 第1章 绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 数据库应用试卷及答案 数据库及应用（B卷） 一、选择题（从备选答案中选1 个正确的答案，每题2分、共24分） 1．支持所有用户建立、存储数据库的软件系统是。 A．数据库系统 B．数据库管理系统 C．应用程序 D．操作系统2．DB的三级模式结构中最接近外部存储器的是。 A.子模式 B.外模式 C.概念模式 D.内模式 3．在关系模式R中，函数依赖X→Y的语义是。 A．在R的某一关系中，若两个元组的X值相等，则Y值也相等 B．在R的每一关系中，若两个元组的X值相等，则Y值也相等 C．在R的某一关系中，Y值应与X值相等 D．在R的每一关系中，Y值应与X值相等 4． DBA是________的简称。 A．系统分析员 B．应用程序员 C．数据库管理员 D.数据录入员 5． _____是长期存储在计算机内的有组织,可共享的数据集合. A．数据库管理系统B．数据库系统 C．数据库D．文件组织6．数据库系统的核心是。 A. 数据库 B. 数据库管理系统 C. 数据模型 D. 软件工具 7．客观存在并可相互区别的事物叫________。 A．码 B．属性 C．实体 D. 实体集 8．数据库的完整性是指数据的_____和_____。 (1)正确性(2)合法性(3)不被非法存取 (4)相容性 (5)不被恶意破坏 A． (1)和(3) B． (2)和(5) C． (1)和(4) D． (2)和(4) 9．一组具有相同数据类型的值的集合称为________。 A．关系 B．属性 C．分量 D．域 10.以下______封锁违反两段锁协议。 A．Slock A … Slock B … Xlock C …… Unlock A … Unlock B … Unlock C 工资管理系统的数据库 设计 LEKIBM standardization office【IBM5AB- LEKIBMK08- LEKIBM2C】 工资管理系统 课程：数据库 学号：2 姓名：孔洁 教师：张福安 目录 1 系统概述 (1) 2 系统数据流程图和数据字典 (3) 用户需求调查 (3) 系统数据流程图 (4) 系统数据字典 (7) 3 数据库结构设计 (13) 概念结构设计 (12) 逻辑结构设计 (12) 数据库结构的详细设计 (14) 4 物理设计 (15) 5 用户的子模式（外模式）设计（没做） (19) 6 总结 (19) 1 系统概述 本文按照数据库系统设计的基本步骤，采取了事先进行需求分析，然后进行数据库的概念设计和逻辑结构设计，最后进行数据库详细设计的方法，完成了一个工资管理系统数据库系统的设计。最终，在Acess 2010完成的工资管理系统，可以实现添加和修改员工的个人详细信息、记录公司内部的人事调动情况、实现员工考勤记录查询和员工工资查询，整个系统重点放在工资管理上。 2 系统数据流程图和数据字典 用户需求调查 通过对现行工资管理系统的调查，明确了工资管理系统由员工信息查询，员工人事变更记录，员工考勤记录查询，员工工资查询组成。系统功能的主要描述如下。 （1）员工信息查询 ?对公司里所有员工进行统一编号；将每一位员工的信息保存在员工档案记录中。 ?对新聘用的员工，将其信息加入到员工档案记录中；对于解聘的员工，将其信息从员工档案记录中删除。 ?当员工的信息发生变动时，修改员工档案记录中相应的属性。 （2）员工人事变更记录管理 对公司里所有员工的职务记录进行统一编号；登记员工调动前后的具体职务，以及调动时间。 （3）考勤管理 ?对员工上班刷卡的记录进行统一编号；登记员工上班时间、签到类型（准时、迟到）。 程序复杂性 3、具有线性结构的数据结构是（ D ）。 A. 图 B. 树 C. 广义表 D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（B）等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是（C）。 for(i=0;i ； 数据库及应用（B卷） 一、选择题（从备选答案中选1 个正确的答案，每题2分、共24分） 1．支持所有用户建立、存储数据库的软件系统是。 A．数据库系统 B．数据库管理系统 C．应用程序 D．操作系统2．DB的三级模式结构中最接近外部存储器的是。 A.子模式 B.外模式 C.概念模式 D.内模式 3．在关系模式R中，函数依赖X→Y的语义是。 A．在R的某一关系中，若两个元组的X值相等，则Y值也相等: B．在R的每一关系中，若两个元组的X值相等，则Y值也相等 C．在R的某一关系中，Y值应与X值相等 D．在R的每一关系中，Y值应与X值相等 4． DBA是________的简称。 A．系统分析员 B．应用程序员 C．数据库管理员 D.数据录入员 5． _____是长期存储在计算机内的有组织,可共享的数据集合. A．数据库管理系统B．数据库系统 C．数据库D．文件组织6．数据库系统的核心是。 《 A. 数据库 B. 数据库管理系统 C. 数据模型 D. 软件工具 7．客观存在并可相互区别的事物叫________。 A．码 B．属性 C．实体 D. 实体集8．数据库的完整性是指数据的_____和_____。 (1)正确性(2)合法性(3)不被非法存取 (4)相容性 (5)不被恶意破坏 A． (1)和(3) B． (2)和(5) C． (1)和(4) D． (2)和(4) 9．一组具有相同数据类型的值的集合称为________。 \ A．关系 B．属性 C．分量 D．域 10.以下______封锁违反两段锁协议。 A．Slock A … Slock B … Xlock C …… Unlock A … Unlock B … Unlock C B．Slock A … Slock B … Xlock C …… Unlock C … Unlock B … Unlock A C．Slock A … Slock B … Xlock C …… Unlock B … Unlock C … Unloc k A D．Slock A …Unlock A …Slock B … Xlock C …… Unlock B … Unlock C 11. “日志”文件用于保存________。 一、数据字典---基础资料 表 名：GZ_Ftlx 中文名：分摊类型 说 明：设置工资的费用分摊类型 主 键：gsdm、lbdm、ftlxdm 索 引： 序号 中文字段名 字段名 类型、长度 说明 1 公司代码 gsdm Char(12) PK、NOT NULL、DEFAULT（''） 2 类别代码 lbdm char(2) PK、NOT NULL 3 类别名称 lbmc Char(30) NOT NULL 4 分摊类型代码 ftlxdm Smallint PK、NOT NULL 5 分摊类型 ftlx Char(30) NOT NULL 6 工资总额 gzze Varchar（255） NULL 7 提取比例 tqbl Numeric（6，4） 表 名：GZ_Grsds 中文名：个人所得税 说 明：设置个人所得税税率 主 键：gsdm、jc 索 引： 序号 中文字段名 字段名 类型、长度 说明 1 公司代码 Gsdm Char(12) PK、NOT NULL、DEFAULT('') 2 级次 Jc Smallint PK、NOT NULL 3 下限 Xx Int NULL 4 上限 Sx Int NULL 5 基数 Js Int NULL、DEFAULT（0） 6 附加费 Fjf Int NULL、DEFAULT（0） 7 税率 Sl Numeric(8,5) NOT NULL 8 扣除数 Kcs Numeric(10,2)NOT NULL 表 名：GZ_Ztcs 中文名：账套参数 说 明：设置工资系统的账套参数信息 主 键： 索 引： 序号 中文字段名 字段名 类型、长度 说明 1 启用日期 Qyrq Char(8) NULL 2 职工类型分级 Zglxfj Char(20) NULL 3 凭证类型代码 Pzlxdm Char(4) NULL、DEFAULT（'ZZ'） 4 凭证类型名称 Pzlxmc Char(4) NULL、DEFAULT（'转帐'） 数据结构习题 第一章绪论 数据结构是一门研究非数值计算的程序设计问题中计算机的___①__以及它们之间的__②_ 和运算等的学科。 ①A.数据元素 B.计算方法 C.逻辑存储 D.数据映像 ②A.结构 B.关系 C.运算 D.算法 算法分析的目的是___①__ ，算法分析的两个主要方面是__②___ 。 ① A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求该进 D.分析算法的易懂性和文档性 。 ② A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 计算机算法指的是__①__ ，它必须具备输入、输出和__②_ 等5个重要特性。 ① A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 ② A.可读性、可移植性和可扩展性 B. 可读性、可移植性和有穷性 C.确定性、有穷性和可行性 D.易读性、稳定性和安全性 数据元素是数据处理的基本单位；数据项是数据处理的_最小单位。 数据结构是研究数据的逻辑结构___和__物理结构__，并对这种结构定义相适应的运算，设计出相应的算法，分析算法的效率。算法的效率包括时间和空间两个方面，分别称为_空间复杂度和时间复杂度。数据的逻辑结构是指_数据元素之间的关系__；包括线性结构、树形结构和图形结构三种类型,其中树形结构和图状结构合称为__非线性结构__。 线性结构中元素之间存在_一对一___ 关系，树形结构中元素之间存在_一对多___ 关系，图状结构中元素之间存在__多对多__ 关系。 | 数据结构在计算机中的表示称为数据的物理（或存储）结构，数据的物理结构可以采用_顺序存储和_链式存储__两种存储方法。 顺序存储方法是把逻辑上相邻的元素存储在物理位置相邻的内存单元中；链式存储方法中元素间的关系是由__指针来表示_的。 第二章线性表 链表不具备的特点是____ 。 A.可随机访问任一结点 B.插入删除不需移动元素 C.不必事先估计存储空间 D.所需空间与其长度成正比 不带头结点的单链表head 为空的判定条件是____。 A. head==null B. head->next==null C. head->next==head D. head !=null , 带头结点的单链表head 为空的判定条件是____。 A. head==null B. head->next==null C. head->next==head D. head!=null 非空的循环单链表head 的尾结点（由p所指向）满足____。 A. p->next==null B. p==null C. p->next==head D. p==head 在一个具有n 个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是____。 数据库程序设计试题 1一、判断题（每题1分，共10分） 1、DB、DBMS、DBS三者之间的关系是DBS包括DB和DBMS。( ) 2、数据库的概念结构与支持其的DB的DBMS有关。( ) 3、下列式子R∩S=R—（R—S）成立。( ) 4、数据存储结构改变时逻辑结构不变，相应的程序也不变，这是数据库系统的逻辑独立 性。（） 5、关系数据库基本结构是三维表。( ) 6、在嵌入式SQL语句中，主语句向SQL语句提供参数，主要用游标来实现。( ) 7、规范化的投影分解是唯一的。( ) 8、不包含在任何一个候选码中的属性叫做非主属性。( ) 9、在 Transact-SQL 语句的WHERE子句中，完全可以用IN子查询来代替OR逻辑表达式。 （ ) 10、封锁粒度越大，可以同时进行的并发操作越大，系统的并发程度越高。（） 二、填空题(每空0.5分，共10分) 1、两个实体间的联系有联系，联系和联系。 2、select命令中，表达条件表达式用where子句，分组用子句，排序用 子句。 3、数据库运行过程中可能发生的故障有、和三类。 4、在“学生-选课-课程”数据库中的三个关系如下： S(S#，SNAME，SEX，AGE)，SC(S#，C#，GRADE)，C(C#，CNAME，TEACHER)。 现要查找选修“数据库技术”这门课程的学生姓名和成绩，可使用如下的SQL语句：SELECT SNAME,GRADE FROM S,SC,C WHERE CNAME= 数据库技术AND S.S#=SC.S# AND。 5、管理、开发和使用数据库系统的用户主要有、、 。 6、关系模型中可以有三类完整性约束：、 和。 7、并发操作带来数据不一致性包括三类：丢失修改、和。 8、事务应该具有四个属性：原子性、、隔离性和持续性。 9、数据库运行过程中可能发生的故障有事务故障、和三类。 10、在“学生-选课-课程”数据库中的三个关系如下：S(S#，SNAME，SEX，AGE)，SC(S#，C#，GRADE)，C(C#，CNAME，TEACHER)。 现要查找选修“数据库技术”这门课程的学生姓名和成绩，可使用如下的SQL语句：SELECT SNAME,GRADE FROM S,SC,C WHERE CNAME= ‘数据库技术’AND S.S#=SC.S# AND。 11、数据库设计包括、、逻辑结构设计、物理结构设计、数据库实施、数据库运行和维护。 12、MS SQL Server提供多个图形化工具，其中用来启动、停止和暂停SQL Server的图形 化工具称为_________。 13 、SELECT语句中进行查询 , 若希望查询的结果不出现重复元组 , 应在SELECT子 句中使用____________保留字。 14、如果一个关系不满足2NF，则该关系一定也不满足__________(在1NF、2NF、3NF 范围内)。 15、数据库的物理设计主要考虑三方面的问题：______、分配存储空间、实现存取路径。 三、单选题(每题1分，共20 分) 1、在SQL中，关系模式称为（） A、视图 B、对象 C、关系表 D、存储文件 2、要保证数据库逻辑数据独立性，需要修改的是( ) 4、4数据库设计 4、1数据库分析 通过系统管理，能够增强员工之间得沟通,更好地协调员工之间得协作关系；对员工基础信息管理与薪资管理更加科学；能够全程跟踪员工得培训,通过信息得记录,更好地作出员工培训方案.在设计工资管理信息系统时，主要从模块组成、数据连接、功能实现、应用意义等方面着手。模块组成主要包括该工资管理信息系统得主要组成模块以及每个模块所要达到得功能。每个模块基本上脱离不了数据,所以在数据库设计时，要充分考虑数据得高效性,减少数据冗余，保证系统运行速度。 ４、2数据库概念设计 根据以上各节对系统所做得需求分析与系统设计,规划出本系统中使用得数据库实体分别为管理员实体、招聘人员实体、员工信息管理实体、薪资管理实体、培训信息实体及部门信息实体。系统总体ER图如图所示: 下面将介绍几个关键实体得E－R图. 1、管理员实体 管理员实体包括管理员帐号、管理员密码及管理员级别属性.其中管理员级别信息中，１代表系统管理员，0代表普通管理员。 图 5-1 管理员实体 2、员工信息管理实体 员工信息管理实体包括员工编号、员工姓名、员工年龄、员工性别、出生日期、员工身份证号、民族、婚姻状况、政治面貌、籍贯、联系电话、家庭住址、员工毕业学校、员工所学专业、文化程度、上岗时间、部门名称、部门工种、登记人、登记时间及备注信息属性。 3、薪资管理实体 薪资管理实体包括员工编号、工资发放时间、基本工资、加班次数、工龄、全勤奖、旷工费及保险费等属性。 4、3数据库逻辑结构 数据得概念结构设计完之后,可以将上面得数据库概念结构转化为某种数据库系统所支持得实际数据模型,也就就是数据库得逻辑结构.系统数据库中各表得详细ＳQL语句。 CRＥATE TＡBLＥ｀ｄｅp` ( //部门表 `iｄ` ｉｎｔ(10） unsｉｇned ＮOＴＮＵLL auto_ｉnｃｒeｍent MENT ’自动编号’， `dep_id` varchar（1６） dｅfauｌｔＮULL MENT '部门编号＇， `dｅp_ｎaｍe` ｖaｒchar(16）ｄｅｆauｌｔNＵLL MENT '部门名称＇，`deｐ_info` ｖarchar(５１2） dｅfａｕlt NULL ＭENT ’部门简介’, 数据结构题集 第一章绪论 一、单选题 1.在数据结构中，从逻辑上可以把数据结构分成【C 】。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 2.数据结构在计算机内存中的表示是指【A 】。 A.数据的存储结构 B.数据结构 C.数据结构的逻辑结构 D.数据元素之间的关系 3. 【A 】是数据的最小单位，【B 】是数据的基本单位。 A.数据项 B.数据元素 C.信息项 D.表元素 4. 计算机所处理数据一般具有某种内在联系，这是指【B 】。 A.数据与数据之间存在某种关系 B.数据元素与数据元素之间存在某种关系 C.元素内部存在某种结构 D.数据项与数据项之间存在某种关系 5.算法分析的目的是【C 】。 A.找出数据结构的合理性 B.研究输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性 6.在存储数据时，不仅要考虑存储各数据元素的值，而且还要存储【C 】。 A.数据处理的方法 B.数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 7.算法分析的主要任务是分析【D 】。 A.算法是否具有较好的可读性 B.算法中是否存储语法错误和逻辑错误 C.算法的功能是否符合设计要求 D.算法的执行时间与问题规模之间的关系。 8.数据的运算【A 】。 A.效率与采用何种存储结构有关 B.是根据存储结构来定义的 C.有算术运算和关系运算两大类 D.必须用程序设计语言来描述 9.算法的计算量的大小称为算法的【B 】。 A.效率 B.时间复杂度 C.现实性 D.难度 10.连续存储分配时，存储单元的地址【A 】。 A.一定连续 B.一定不连续 C.不一定连续 D.部分连续，部分不连续 二、判断题 1.数据元素是数据结构的最小单位【.×】。 2.数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构【×.】。 3.数据的逻辑结构指数据元素的各数据项之间的逻辑关系【×.】。 4.算法的优劣与算法的描述语言无关，但与使用的计算机有关【.×】。 华南农业大学期末考试试卷（A卷）2014-2015学年第一学期考试科目：数据库系统 考试类型：闭卷考试时间：120 分钟 学号姓名年级专业 Question 1: true-false question (15 points) For each of the following statements, indicate whether it is TRUE or FALSE (Using √for TRUE and ×for FALSE). You will get 1 point for each correct answer, -0.5 point for each incorrect answer, and 0 point for each answer left blank. Be sure to write your answer in the answer sheet. 1. A primary key is a field (or group of fields) that uniquely describes each record in the database. 2.Data redundancy improves the integrity of a database. 3.SQL is the language used by relational databases to create objects and to manipulate and retrieve data. 4. A relational database management system does not include tools for backing up & restoring databases. 5.An attribute is also known as a row in most databases. 6.An association between entities is known as a relationship. 7.Integrity constraints limit the number of entities that can be placed in a table or database. 8.The Entity-Relationship data model is often used in the physical design phase. 9.The concept “relation” in relation model is exactly the same as the concept “relationship” in ER model. 10.Most relationship sets in a database system involves two entity sets. 11.The closure of an attribute set contains that attribute set. 12.Lossless decomposition is necessary in a decomposition algorithm. 13.If A →B and C →D hold, then AC →BD also holds. 14.It is not necessary that a legal schedule preserves the order in which the instructions appear in each individual transaction. 15.Update operations in database must be written into log before updating database. Question 2 single-choice question (2 points for each problem, 30 points in total) 1. is the only one incorrect description from the followings: A. R=(R-S)∪(R∩S) B. R-S=R-(R∩S) C. R∩S=S-(R-S) D. R∩S=S-(S-R) SQL数据库员工工资管理系统设计 实验七：数据库设计 数据库名称：职职员资治理系统 姓名：胡少帅 班级：2011级网络工程 学号：20110441021024 1 需求分析 工资治理系统是提供工资治理人员和职工工资进行治理的系统。它能自动对不同职务，不同出勤及各个月份的工资进行治理并生成财务表。 工资治理系统的用户需求要紧功能有： 1各部门的信息情形 2各职工的信息情形 3考勤信息情形 4工资信息情形 5定义登陆用户和用户的权限 2 概念分析 部门E-R图 职工信息E-R图 职务信息E-R图 考勤信息E-R图 用户E-R图 工资情形E-R图 总E-R图 3 逻辑设计 关系模型： 部门（部门编号（主键），部门名称，经理，电话） 职工信息（职工编号（主键），职务编号，姓名，性不，电话，住址，部门编号（外键）） 考勤情形（职工编号（主键），出勤天数，加班天数，出勤奖金，月份）职务（职务编号（主键），职务名称（主键），差不多工资） 工资运算（职工编号（主键），考勤情形，工资，月份） 用户（用户名，密码，权限） 4 物理设计 1 给职工信息表建立非集合索引“职工” /*给职工信息表非建立集合索引*/ create nonclustered index 职工on 职工信息(职工编号) go SELECT * FROM sys.indexes WHERE name='职工' 2给工资表建立唯独索引“工资” /*给工资表建立唯独索引“工资”*/ create unique index 工资on 工资情形(职工编号) go SELECT * FROM sys.indexes WHERE name='工资' Go 3给考勤信息表建立集合索引“考勤” /*给考勤信息表建立非集合索引*/ create nonclustered index 考勤on 考勤信息(职工编号) go SELECT * FROM sys.indexes WHERE name='考勤' 5 实施过程 创建表结构 1 职工信息表 create table 职工信息 第一章绪论 1.16 void print_descending(int x,int y,int z)//按从大到小顺序输出三个数 { scanf("%d,%d,%d",&x,&y,&z); if(x2014(1)数据结构-A-试题
2014年4月互联网数据库试题和答案
企业工资管理系统 数据库
数据结构习题集答案解析_清华大学版
数据库应用试卷及答案
工资管理系统的数据库设计
大数据结构试题集(含答案)
数据库应用试卷及答案
U8R10工资系统数据库结构
数据结构习题集(答案)
数据库期末试卷和答案
工资管理系统数据库设计
数据结构题集答案
2014数据库系统期末试题及答案
SQL数据库员工工资管理系统设计
严蔚敏数据结构习题集答案
- 大连理工大学数据结构 课后题答案(1-3章)
- 大连理工大学软件学院2014数据结构期末考试(学长手抄整理)
- 大工数据结构课程考试模拟试卷a
- 大工20春《数据结构》在线作业2答卷
- 大工《数据结构》课程考试模拟试卷A
- 大工19春《数据结构》在线作业31答案
- 大工《数据结构》在线作业1答案
- 大工20春《数据结构》在线作业1答卷
- 数据结构作业答案(大连理工大学)
- 大工数据结构课程考试模拟试卷A
- 大工14秋《数据结构》在线作业3答案
- 2014.3大工《高电压技术》课程考试模拟试卷B答案
- 大工18秋《数据结构》在线作业2(满分题)
- 大工20春《数据结构》在线作业2答卷
- 数据结构作业答案(大连理工大学)
- 大工19秋《数据结构》在线作业3(参考答案)
- 大连理工大学《数据结构》作业 参考答案
- 大工20秋《数据结构》在线作业2【答案】
- 大工20春《数据结构》在线作业3答卷
- 大工19秋《数据结构》期末考试复习题