数据结构期末考试补充复习题答案
之前发给大家的各章节练习题一定要做，这里再补充一些题目。
一、综合题
1. （8分）一无向网如图2所示，解答下列问题：
（1） 写出该无向网的邻接矩阵；
（2） 按步骤画出使用克鲁斯卡尔算法为图2构造的最小生成树。
参考解答：
（1） 用0、1表示的扣1分，只要是写对了权值的没扣分 ∞
∞∞∞∞∞∞∞∞∞
∞∞∞
∞∞∞625
6452777414435
5713
（2）最小生成树的长度刚好和步骤顺序相对应了，没标步骤的暂时没统一扣1分
V2
V5V4
V3
V6
V1
① 1② 2
③ 3
④ 4
⑤ 5
2. （10分）一有向网如图3所示，回答下列问题：
（1） 求出该有向网中每个顶点的入度和出度；
（2） 利用迪杰斯特拉算法求解该图从源点V 1到其它各顶点的最短路径及
其路径长度。
4
V 4
V 3 V 1
V 2 V 6
V 5
5 7
1 2
4 6 7
3
5 图2
参考解答： （1）5分 顶点 V 1
V 2
V 3
V 4
V 5
入度 0 2 1 3 2 出度
3
1
3
1
（2）Len 表示最短路径长度 5分 终点 从源点V 1到各终点的最短路径的求解过程
i=1 i=2 i=3
i=4
V 2
6 < V 1 V 2> 4
< V 1 V 3 V 2>
----- ----- V 3
1
< V 1 V 3>
----- ----- -----
V 4
∞ 11 < V 1 V 3 V 4> 8
< V 1 V 3 V 2 V 4>
7
< V 1 V 5 V 4>
V 5
6 < V 1 V 5> 6 < V 1 V 5> 6
< V 1 V 5> -----
V j ：len
V 3: 1 < V 1 V 3> V 2: 4 < V 1 V 3 V 2>
V 5: 6 < V 1 V 5>
V 4: 7 < V 1 V 5 V 4>
3. （10分）给定7个叶子结点，其权值分别为{7，6，25，13，4，12，9}，画出构造的哈夫曼树（权值小的为左孩子）并求出树的带权路径长度WPL 。
参考解答：
4 6
6
1 3 10
1 6
V 1 V 2
V 3
V 4
V 5
图3
76
22
1012
4625
4729
16
7
913
WPL ＝(13+25)*2+(7+9+12)*3+(4+6)*4=200 （2分）
4. （7分）利用算符优先算法对表达式2*（6－3）#求值，写出操作符栈和操作数栈在任意时刻的状态。 参考解答： 步骤 算符栈 操作数栈 表达式 0 # 2*（6－3）# 1 # 2 *（6－3）# 2 # * 2 （6－3）# 3 # * （ 2 6－3）# 4 # * （ 2 6 －3）# 5 # * （ － 2 6 3）# 6 # * （ － 2 6 3 ）# 7 # * （ 2 3 ）#
8 # * 2 3 # 9 # 6 # 10
6
5. （7分） (10分)已知一棵二叉树的后序遍历序列为DGEBCA ，中序遍历序列为DBEGAC 。画出这棵二叉树。 参考解答：
A C
B D
E
G
6．（10分）设有一组关键字(25，74，49，53，15)，采用哈希函数：H （key ）=key mod 7 ，表长为10，用开放地址法的线性探测再散列方法Hi=(H(key)+di) mod 10(di=1, 2, 3,…,)解决冲突。写出哈希表的详细构造过程。
参考解答： 地址
1 2 3 4 5 6 7 8 9 关键字 49
15
25
74
53
H(25) = 25 mod 7 = 4 H(74) = 74 mod 7 = 4
H1 = (H(74) + 1) mod 10 = 5 H(49) = 49 mod 7 = 0 H(53) = 53 mod 7 = 4
H1 = (H(53) + 1) mod 10 = 5 H2 = (H(53) + 2) mod 10 = 6 H(15) = 15 mod 7 = 1
7.已知一个有向图的邻接表如图1所示，顶点1的入度为( )，顶点2的出度为( )，从顶点1出发得到的深度优先遍历序列是( )，从顶点1出发得到的广度优先遍历序列是( )。
234
1∧
4231413
∧∧
∧1
∧
解答：( 2 )、( 1 )、( 1243 )、( 1234 )
8．给定序列（67，45，87，19，55，32，70，60，90，23），写出它的初始堆序列。
答：调整后的初始堆序列(小根堆)为：19，23，32，45，55，87，70，60，90，67
或者是大根堆：90, 67, 87, 60, 55, 32, 70, 45, 19, 23
19
23 32
45 55 87 70
60 90 67
9.
二、程序设计题
1．（4分）
Typedef struct LNode
{
ElemType data; // 数据域
struct Lnode *next; // 指针域
} LNode，* LinkList;
Status ListInsert_L(LinkList &L, int i, ElemType e)
{//带头结点的单链表L中，删除第i个元素，并由e返回其值
j = 0; p=L;
while ( p->next && j < i-1) // 寻找第 i 个结点
{
（1） //指针p后移
++j;
}
if (!p->next || j > i-1) return ERROR;
q = p->next;
（2） // 删除结点
（3） // e返回其值
（4） // 释放结点
return OK;
｝
参考解答：（1）p = p->next; (2)p->next=q->next
（3）e=q->data; （4）free(q);
每空一分，学生写出其他形式的正确答案也给分，比如（2）
p->next=p->next->next;
缺少分号不给分。完全正确才给分，不存在半对。
2．（10分）采用三元组表示的矩阵M，其转置矩阵为T。请写出线性时间复杂度的快速转置算法FastTranMat。
求解提示：
#define N 4
#define MaxSize 100
typedef int ElemType;
typedef struct
{ int r; /*行号*/
int c; /*列号*/
ElemType d; /*元素值*/
} TupNode; /*三元组定义*/
typedef struct
{ int rows; /*行数值*/
int cols; /*列数值*/
int nums; /*非零元素个数*/
TupNode data[MaxSize];
} TSMatrix; /*三元组顺序表定义*/
void CreatMat(TSMatrix &t,ElemType A[N][N])
{;//略…创建矩阵A的三元组t
}
void DispMat(TSMatrix t)
{;//略…按三元组显示出矩阵t
}
int main()
{
ElemType a1[N][N]={{1,0,3,0},{0,1,0,0},{0,0,1,0},{0,0,1,1}};
TSMatrix a,c;
CreatMat(a,a1);
printf("a的三元组:\n");DispMat(a);
TranMat(a,c);
printf("a转置为c\n");
DispMat(c);
FastTranMat(a,c);
printf("下面是快速转置矩阵得到的:\n");
DispMat(c);
}
void TranMat(TSMatrix M,TSMatrix &T)
{//采用三元组表存储表示，求矩阵M的转置矩阵T
//本算法的时间复杂度为O(nu*tu)，非线性的。
int p,q=0,v; /*q为tb.data的下标*/
T.rows=M.cols;T.cols=M.rows;T.nums=M.nums;
if (M.nums!=0)
{
for (v=0;v for (p=0;p if (M.data[p].c==v) { T.data[q].r=M.data[p].c; T.data[q].c=M.data[p].r; T.data[q].d=M.data[p].d; q++; } } } void FastTranMat(TSMatrix M,TSMatrix &T) {//采用三元组表存储表示，快速算法求矩阵M的转置矩阵T //本算法的时间复杂度是线性的，比如O(nu+tu). //请同学们写出本算法。 } 参考解答：10分 void FastTranMat(TSMatrix M,TSMatrix &T) { int i,j; int k,q; T.rows=M.cols;T.cols=M.rows;T.nums=M.nums; if(T.nums) { for(i=0; i for(j=0; j cpot[0]=0; for(i=1; i for(j=0; j { k=M.data[j].c; q=cpot[k]; T.data[q].r=M.data[j].c; T.data[q].c=M.data[j].r; T.data[q].d=M.data[j].d; ++cpot[k]; } } } 如果学生写出其他某种正确的算法，时间复杂度也是线性的，也可以哦。 3. typedef struct LNode { char data; // 数据域 struct LNode *next; // 指针域 } LNode，* LinkList; 请写出在带头结点的单循环链表head中查找第i个位置元素的值，将该值存放于x中的运算。 void FindLinkList(LinkList &head, int i， char &x){ p = head; j = 0; if(i<= 0) { printf(“查找位置错误！”); return;} while ( p->next != head && jnext; ++j; } if (j == i) x = p->data ; else printf(“没找到！”); return; } 4.（6分）二叉树采用二叉链表存储结构，每个结点结构如下： data lchild rchild （1）写出该结点结构的定义。 （2）写出二叉树的先序遍历递归算法： void PreOrder(BiTree T, void( *visit)(TElemType& e)) 参考解答 （1）3分 typedef struct BiTNode { TElemType data; struct BiTNode *lchild ;//左孩子指针 struct BiTNode *rchild; // 右孩子指针 } BiTNode，* BiTree; （2）3分 void PreOrder (BiTree T, void( *visit)(TElemType& e)) { // 先序遍历二叉树 if (T) { visit(T->data); // 访问根结点 PreOrder (T->lchild, visit); // 遍历左子树 PreOrder (T->rchild, visit); // 遍历右子树 } else return; } 2004-2005学年第二学期期末考试 C 2002级计算机科学与技术专业《数据库原理与应用》课程试题一、选择题（15分，每空1分）： 1．在数据库中，产生数据不一致的根本原因是____。 A．数据存储量太大 B．没有严格保护数据 C．未对数据进行完整性控制 D．数据冗余 2．相对于其他数据管理技术，数据库系统有①、减少数据冗余、保持数据的一致性、②和③的特点。 ①A．数据统一 B．数据模块化 C．数据结构化 D．数据共享 ②A数据结构化 B．数据无独立性 C．数据统一管理 D．数据有独立性 ③A．使用专用文件 B．不使用专用文件 C．数据没有安全与完整性保障 D．数据有安全与完整性保障 3．关系运算中花费时间可能最长的运算是____。 A．投影 B．选择 C．笛卡尔积 D．除 4．关系数据库用①来表示实体之间的联系，关系的数学定义是②。 ①A．层次模型 B．网状模型 C．指针链 D．二维表格数据 ②A．若干域（domain）的集合 B．若干域的笛卡尔乘积（Cartesian product） C．若干域的笛卡尔乘积的子集 D．若干元组（tuple）的集合 5．集合R与S的连接可以用关系代数的5种基本运算表示为________。 A．R-(R-S) B．σ F (R×S) C．空 D．空 6．在关系代数中，对一个关系做投影操作后，新关系的元组个数____原来关系的元组个数。 A．小于 B．小于或等于 C．等于 D．大于 7．下列SQL语句中，创建关系表的是____。 A．ALTER B．CREATE C．UPDATE D．INSERT 8．关系数据库设计中的陷阱（pitfalls）是指________。 A．信息重复和不能表示特定信息 B．不该插入的数据被插入 C．应该删除的数据未被删除 D．应该插入的数据未被插入 9．数据库的____是为了保证由授权用户对数据库所做的修改不会影响数据一致性的损失。 A．安全性 B．完整性 C．并发控制 D．恢复 10．事务是数据库进行的基本工作单位。如果一个事务执行成功，则全部更新提交；如果一个事务 《数据库原理》课程考试模拟题四 一、单项选择题(在每小题的四个备选答案中选出一个正确答案。本题共16分，每小题1分) 1. 在数据库中，下列说法（）是不正确的。 A．数据库中没有数据冗余 B．数据库具有较高的数据独立性 C．数据库能为各种用户共享 D．数据库加强了数据保护 2. 按照传统的数据模型分类，数据库系统可以分为( )三种类型。 A．大型、中型和小型 B．西文、中文和兼容 C．层次、网状和关系 D．数据、图形和多媒体 3. 在数据库的三级模式结构中，( )是用户与数据库系统的接口，是用户用到的那部分数据的描述。 A．外模式 B．内模式 C．存储模式 D．模式 4. 下面选项中不是关系的基本特征的是( )。 A. 不同的列应有不同的数据类型 B. 不同的列应有不同的列名 C. 没有行序和列序 D. 没有重复元组 5. SQL语言具有两种使用方式，分别称为交互式SQL和( )。 A．提示式SQL B．多用户SQL C．嵌入式SQL D．解释式SQL 6. 设关系模式R(ABCD)，F是R上成立的FD集，F={A→B，B→C},则(BD)+为( )。 A．BCD B．BC C．ABC D．C 7. E-R图是数据库设计的工具之一，它适用于建立数据库的( )。 A．概念模型 B．逻辑模型 C．结构模型 D．物理模型8. 若关系模式R(ABCD)已属于3NF，下列说法中( )是正确的。 A．它一定消除了插入和删除异常 B．仍存在一定的插入和删除异常C．一定属于BCNF D．A和C都是 9. 解决并发操作带来的数据不一致性普遍采用( )。 A．封锁技术 B．恢复技术 C．存取控制技术 D．协商 10. 数据库管理系统通常提供授权功能来控制不同用户访问数据的权限，这主要是为了实现数据库的( )。 A．可靠性 B．一致性 C．完整性 D．安全性 11. 一个事务一旦完成全部操作后，它对数据库的所有更新应永久地反映在数据库中，不会丢失。这是指事务的( ) 。 A. 原子性 B. 一致性 C. 隔离性 D. 持久性 12. 在数据库中，软件错误属于( )。 数据库期末考试试题及答案 一、选择题(每题1分，共20分) 1(在数据管理技术的发展过程中，经历了人工管理阶段、文件系统阶段和数据库系统阶段。 在这几个阶段中，数据独立性最高的是( A )阶段。 A. 数据库系统 B. 文件系统 C. 人工管理 D.数据项管理 2(数据库三级视图，反映了三种不同角度看待数据库的观点，用户眼中的数据库称为(D)。 A. 存储视图 B. 概念视图 C. 内部视图 D. 外部视图 3(数据库的概念模型独立于(A)。 A. 具体的机器和DBMS B. E-R图 C. 信息世界 D. 现实世界 4(数据库中，数据的物理独立性是指(C)。 A. 数据库与数据库管理系统的相互独立 B. 用户程序与DBMS的相互独立 C. 用户的应用程序与存储在磁盘上的数据库中的数据是相互独立的 D. 应用程序与数据库中数据的逻辑结构相互独立 5(关系模式的任何属性(A)。 A. 不可再分 B. 可再分 C. 命名在该关系模式中可以不惟一 D.以上都不是 6(下面的两个关系中，职工号和设备号分别为职工关系和设备关系的关键字: 职工(职工号，职工名，部门号，职务，工资) 设备(设备号，职工号，设备名，数量) 两个关系的属性中，存在一个外关键字为( C )。 A. 职工关系的“职工号” B. 职工关系的“设备号” C. 设备关系的“职工号” D. 设备关系的“设备号” 7(以下四个叙述中，哪一个不是对关系模式进行规范化的主要目的( C )。 A. 减少数据冗余 B. 解决更新异常问题 C. 加快查询速度 D. 提高存储空间效率 8(关系模式中各级范式之间的关系为( A )。 A. B. C. D. 9(保护数据库，防止未经授权或不合法的使用造成的数据泄漏、非法更改或破坏。这是指 数据的( A )。 A. 安全性 B.完整性 C.并发控制 D.恢复 10(事务的原子性是指( B )。 A. 事务一旦提交，对数据库的改变是永久的 B. 事务中包括的所有操作要么都做，要么都不做 C. 一个事务内部的操作及使用的数据对并发的其他事务是隔离的 D. 事务必须使数据库从一个一致性状态变到另一个一致性状态 11(下列哪些运算是关系代数的基本运算( D )。 A. 交、并、差 B. 投影、选取、除、联结 C. 联结、自然联结、笛卡尔乘积 D. 投影、选取、笛卡尔乘积、差运算 12(现实世界“特征” 术语, 对应于数据世界的( D )。 A(属性 B. 联系 C. 记录 D. 数据项 13(关系模型中3NF是指( A )。 A.满足2NF且不存在传递依赖现象 B.满足2NF且不存在部分依赖现象 试题一 一、单项选择题分)2分，共40（本大题共20小题，每小在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。）B 1. 数据库系统的核心是（ ．数据库管理系统B A．数据库 ．软件工具D C．数据模型 ）2. 下列四项中，不属于数据库系统的特点的是（C ．数据由统一管理和控制．数据结构化BA ．数据独立性高．数据冗余度大DC ）概念模型是现实世界的第一层抽象，这一类模型中最著名的模型是（D 3. ．关系模型B．层次模型 A -联系模型D．实体C．网状模型4. ）数据的物理独立性是指（ C ．数据库与数据库管理系统相互独立A ．用户程序与数据库管理系统相互独立B ．用户的应用程序与存储在磁盘上数据库中的数据是相互独立的C ．应用程序与数据库中数据的逻辑结构是相互独立的D A ）．要保证数据库的逻辑数据独立性，需要修改的是（5 B．模式与内模式之间的映象A．模式与外模式之间的映象D．三级模式 C．模式 ）关系数据模型的基本数据结构是（D 6．．关系C．索引 D A．树B．图 有一名为“列车运营”实体，含有：车次、日期、实际发车时间、实际抵7．）达时间、情况摘要等属性，该实体主码是（ C ．日期BA．车次+情况摘要日期D．车次C．车次+ ）S等价于（ B 和己知关系RS，R∩8. B. () A. () D. () C. () 学校数据库中有学生和宿舍两个关系：9． 宿舍（楼名，房间号，床位号，学号）学生（学号，姓名）和 假设有的学生不住宿，床位也可能空闲。如果要列出所有学生住宿和宿舍分配）的情况，包括没有住宿的学生和空闲的床位，则应执行（ A B. 全外联接A. 左外联接1 / 13 自然联接D. 右外联接C. 10．用下面的语句建立一个基本表：( (4) ,(8) ,(2),) D ）可以插入到表中的元组是（21 ，刘祥'，A. '5021'，'刘祥'，男， 21 B. ，''，，，男，C. '5021'，21 D. '5021'，'刘祥 C ）11. 把对关系的属性的修改权授予用户李勇的语句是（' A. 2017年数据结构期末考试题及答案 一、选择题（共计50分，每题2分，共25题） 1 ?在数据结构中，从逻辑上可以把数据结构分为 C 。 A. 动态结构和静态结构B?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2?数据结构在计算机内存中的表示是指 A ° A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D .数据元 素之间的关系 3.在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A. 逻辑B?存储 C.逻辑和存储 D.物理 4 .在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C ° A.数据的处理方法B?数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5. 在决定选取何种存储结构时，一般不考虑 A ° A.各结点的值如何B?结点个数的多少 C?对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6. 以下说法正确的是D ° A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据可以有相同的逻辑结构 7. 在以下的叙述中，正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出 8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一 个结点，则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点 的双循环链表 11. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点（由p所指向）满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点 一、单选题（共 10 道试题，共 50 分。）V 1. SQL Server中，保存着每个数据库对象的信息的系统表是（ C）。 A. sysdatabases B. Syscolumns C. Sysobjects D. Syslogs 2. 在存在下列关键字的SQL语句中，不可能出现Where子句的是（D ）。 A. Update B. Delete C. Insert D. Alter 3. 在查询语句的Where子句中，如果出现了“age Between 30 and 40”,这个表达式等同于（A ）。 A. age>=30 and age<=40 B. age>=30 or age<=40 C. age>30 and age<40 D. age>30 or age<40 4. 如果要在一张管理职工工资的表中限制工资的输入范围，应使用（D ）约束。 A. PDRIMARY KEY B. FOREIGN KEY C. unique D. check 5. 记录数据库事务操作信息的文件是（D ）。 A. 数据文件 B. 索引文件 C. 辅助数据文件 D. 日志文件 6. 要查询XSH数据库CP表中产品名含有“冰箱”的产品情况，可用（ C）命令。 A. SELECT * FROM CP WHERE 产品名称 LIKE ‘冰箱’ B. SELECT * FROM XSH WHERE 产品名称 LIKE ‘冰箱’ C. SELECT * FROM CP WHERE 产品名称 LIKE ‘%冰箱%’ D. SELECT * FROM CP WHERE 产品名称=‘冰箱’ 7. 储蓄所有多个储户，储户能够在多个储蓄所存取款，储蓄所与储户之间是（D ）。 A. 一对一的联系 B. 一对多的联系 C. 多对一的联系 D. 多对多的联系 8. SQL的聚集函数COUNT、SUM、AVG、MAX、MIN不允许出现在查询语句的（ D）子句之中。 A. SELECT B. HAVING C. GROUP BY… HAVING D. WHERE 9. 列值为空值（NULL），则说明这一列（ C）。 A. 数值为0 数据库期末考试试题 ━━━━━━━━━━━━━━━ 一、填空共30题（共计30分） ━━━━━━━━━━━━━━━ 第1题（分）题号:2385 ORDER BY 子句实现的是【1】. 答案： =======(答案1)======= 排序 第2题（分）题号:2374 如果列上有约束,要删除该列,应先删除【1】 答案： =======(答案1)======= 相应的约束 第3题（分）题号:2394 在每次访问视图时,视图都是从【1】中提取所包含的行和列. 答案： =======(答案1)======= 基表 第4题（分）题号:2372 1.在增加数据文件时,如果用户没有指明文件组,则系统将该数据文件增加到【1】文件组.答案： =======(答案1)======= 主 第5题（分）题号:2371 查看XSCJ数据库信息的存储过程命令是【1】 答案： =======(答案1)======= sp_helpdb 第6题（分）题号:2392 创建视图定义的T-SQL语句的系统存储过程是【1】. 答案： =======(答案1)======= sp_helptext 第7题（分）题号:2379 1.表的外键约束实现的是数据的【1】完整性. 答案： =======(答案1)======= 参照 第8题（分）题号:2390 要进行模糊匹配查询,需要使用【1】关键字来设置查询条件. 答案： =======(答案1)======= LIKE 第9题（分）题号:2380 定义标识列的关键字是【1】. 答案： =======(答案1)======= identity 第10题（分）题号:2383 在进行多表查询是,必须设置【1】条件. 答案： =======(答案1)======= 连接 第11题（分）题号:2363 联系两个表的关键字称为【1】 答案： =======(答案1)======= 外键 第12题（分）题号:2382 用【1】字句可以实现选择行的运算. 答案： 四、程序设计题（本大题共2小题，每小题15分，共30分） 1.对于教学数据库的三个基本表 学生student (sno,sname,sex,sage,sdept) 学习sc(sno,cno,grade) 课程course(cno,cname,cpno,ccredit) 试用SQL语句表示：下列语句。 （1）"查询全男同学信息情况" "select * from student where sex='男'" （2）"查询选修了1号课的学生的学号和成绩" "select sno,grade from sc where cno='1'" （3）"查询所有选修过课的学生的姓名，课程名及成绩" "select sname,cname,grade from student,sc,course where student.sno=sc.sno and https://www.doczj.com/doc/3f3266687.html,o=https://www.doczj.com/doc/3f3266687.html,o" （4）"查询选修了数据库原理课的最高成绩" "select max(grade) as '最高成绩' from student,sc,course where student.sno=sc.sno and https://www.doczj.com/doc/3f3266687.html,o=https://www.doczj.com/doc/3f3266687.html,o and cname='数据库原理'" （5）查询所有选修了1号课程的同学的姓名" " select sname from student where student.sno in (select sc.sno from sc where cno='1')" 2．设有一个SPJ数据库，包括S，P，J，SPJ四个关系模式（20分）供应商表S（SNO,SNAME,STATUS,CITY）; 零件表P(PNO,PNAME,COLOR,WEIGHT); 工程项目表J(JNO,JNAME,CITY); 供应情况表SPJ(SNO,PNO,JNO,QTY)；SPJ表 J表 S表 P表 请用关系代数完成如下查询： 1．求供应工程J1零件的供应商号 SNO 2．求供应工程J1零件P1的供应商号吗SNO 3．求供应工程J1零件为红色的供应商号码SNO 4．求没有使用天津供应商生产的红色零件的工程号JNO 5．求至少用了供应商S1所供应的全部零件的工程号JNO 1.∏sno（σJNO＝‘J1’（SPJ）） 2.∏sno（σJNO＝‘J1’ΛPNO=’P1’（SPJ）） 3.∏sno（σJNO＝‘J1’（SPJ）∞σcolor＝‘红’（P）） 4.∏jno（SPJ）-∏jno（∏sno（σcity＝‘天津’（S））∞∏sno，jno （SPJ）∞∏jno σcolor＝‘红’（P）） 5.∏jno, pno（SPJ）÷∏pno（σsno＝‘s1’（SPJ）） 五、分析题（本大题共2小题，每小题15分本大题共30分） 1. 学生运动会模型: (1)有若干班级,每个班级包括: 班级号,班级名,专业,人数 (2)每个班级有若干运动员,运动员只能属于一个班,包括:运动员号,姓名,性别,年龄 试题六 一、单项选择题 （本大题共10小题，每小题2分，共20分) 在每小题列出的四个备选项中只有一个是符合题目要 求的，错选、多选或未选均无分。 1. DB 、DBMS 和DBS 三者之间的关系是（ ）。 A ．D B 包括DBMS 和DBS B ．DBS 包括DB 和DBMS C ．DBMS 包括DB 和DBS D ．不能相互包括 2. 对数据库物理存储方式的描述称为（ ） A ．外模式 B ．内模式 C ．概念模式 D ．逻辑模式 3. 在数据库三级模式间引入二级映象的主要作用是（ ） 得 分 (考 生 答 题 不 得 超 过 此 线) A．提高数据与程序的独立性B．提高数据与程序的安全性 C．保持数据与程序的一致性D．提高数据与程序的可移植性 4. 视图是一个“虚表”，视图的构造基于（） A．基本表B．视图 C．基本表或视图D．数据字典 5．关系代数中的π运算符对应SELECT语句中的以下哪个子句？（）A．SELECT B．FROM C．WHERE D．GROUP BY 6．公司中有多个部门和多名职员，每个职员只能属于一个部门，一个部门可以有多名职员，从职员到部门的联系类型是（） A．多对多 B．一对一 C．多对一 D．一对多 7．如何构造出一个合适的数据逻辑结构是（）主要解决的问题。 A．关系系统查询优化B．数据字典 C．关系数据库规范化理论D．关系数据库查询 8. 将E-R模型转换成关系模型，属于数据库的（）。 A. 需求分析 B. 概念设计 C. 逻辑设计 D. 物理设计 9．事务日志的用途是（） A. 事务处理 B. 完整性约束 C. 数据恢复 D. 安全性控制 10．如果事务T已在数据R上加了X锁，则其他事务在数据R上（） A. 只可加X锁 B. 只可加S锁 C. 可加S锁或X锁 D. 不能加任何锁 第二章算法分析 1.算法分析是计算机科学的基础 2.增长函数表示问题（n）大小与我们希望最优化的值之间的关系。该函数表示了该算法的时间复杂度或空间复杂度。增长函数表示与该问题大小相对应的时间或空间的使用 3.渐进复杂度：随着n的增加时增长函数的一般性质，这一特性基于该表达式的主项，即n 增加时表达式中增长最快的那一项。 4.渐进复杂度称为算法的阶次，算法的阶次是忽略该算法的增长函数中的常量和其他次要项，只保留主项而得出来的。算法的阶次为增长函数提供了一个上界。 5.渐进复杂度：增长函数的界限，由增长函数的主项确定的。渐进复杂度类似的函数，归为相同类型的函数。 6.只有可运行的语句才会增加时间复杂度。 7. O() 或者大O记法：与问题大小无关、执行时间恒定的增长函数称为具有O（1）的复杂度。 增长函数阶次 t(n)=17 O(1) t(n)=3log n O(log n) t(n)=20n-4 O(n) t(n)=12n log n + 100n O(n log n) t(n)=3n2+ 5n - 2 O(n2) t(n)=8n3+ 3n2O(n3) t(n)=2n+ 18n2+3n O(2n) 8.所有具有相同阶次的算法，从运行效率的角度来说都是等价的。 9.如果算法的运行效率低，从长远来说，使用更快的处理器也无济于事。 10.要分析循环运行，首先要确定该循环体的阶次n，然后用该循环要运行的次数乘以它。（n 表示的是问题的大小） 11.分析嵌套循环的复杂度时，必须将内层和外层循环都考虑进来。 12.方法调用的复杂度分析： 如：public void printsum(int count){ int sum = 0 ; for (int I = 1 ; I < count ; I++) sum += I ; System.out.println(sun); } printsum方法的复杂度为O（n）,计算调用该方法的初始循环的时间复杂度，只需把printsum方法的复杂度乘以该循环运行的次数即可。所以调用上面实现的printsum方法的复 杂度为O（n2）。 13指数函数增长> 幂函数增长> 对数函数增长 2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（A） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B） A.（100,80,90,60,120,110,130） B.（100, 120, 110,130,80, 60,90） C.（100,60,80,90,120,110,130） D.（100,80, 60,90, 120, 130,110） 9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（B ） A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（D） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序 数据库期末考试复习题(附答案) 数据库系统概论 2011年期末考试复习题 一、选择题 ? 第（1）至（3）题基于以下的叙述：有关系模式A（C，T，H，R，S），基中各属性的含义是： ? C：课程T：教员H：上课时间R：教室S：学生 ? 根据语义有如下函数依赖集：? F={C→T，（H，R）→C，（H，T）→R，（H，S）→R} ? 1、关系模式A的码是（D） ? A. C B. （H，R）C.（H，T）D.H，S） ? 2、关系模式A的规范化程度最高达到（B） ? A. 1NF B. 2NF C. 3NFD. BCNF ? 3、现将关系模式A分解为两个关系模式A1（C，T），A2（H，R，S），则其中A1的规范化程度达到（D） ? A. 1NF B. 2NF C. 3NF D. BCNF ? 4.设有关系R（A，B，C）和S（C，D）。与SQL语句? select A,B,D from R,S where R.C=S.C ? 等价的关系代数表达式是（B） ? A. σR.C=S.C(πA,B,D(R×S)) ? B. πA,B,D(σR,C= S.C (R×S)) ? C. σR.C=S.C((πA,B R)×(πDS)) ? D. σR,C=S.C(πD((πA,BR)×S) ? 5、设关系R和关系S的元数分别是3和4，关系T是R与S的广义笛卡尔积，即：T=R×S，则关系T的元数是（C） ? A. 7 B. 9 C. 12 D. 16 ? 6、数据库设计阶段分为（B） ? A. 物理设计阶段、逻辑设计阶段、编程和调试阶段 ? B. 概念设计阶段、逻辑设计阶段、物理设计阶段、实施和调试阶段 ? C. 方案设计阶段、总体设计阶段、个别设计和编程阶段 ? D. 模型设计阶段、程序设计阶段和运行阶段 ? 7、设U是所有属性的集合，X、Y、Z都是U的子集，且Z=U-X-Y。下面关于多值依赖的叙述中，不正确的是(C) ? A. 若X→→Y，则X→→Z B. 若X→Y，则X→→Y ? C. 若X→→Y，且Y′?Y，则X→→Y′ D. 若Z=Φ，则X→→Y ? 8、查询优化策略中，正确的策略是（D） A．尽可能早地执行笛卡尔积操作B．尽可能早地执行并操作 C．尽可能早地执行差操作D．尽可能早地执行选择操作 ? 9、语句delete from sc 表明（A） A. 删除sc中的全部记录 B. 删除基本表sc? C. 删除基本表sc中的列数据 D. 删除基本表sc中的部分行 ? 10、在DB应用中，一般一条SQL 语句可产生或处理一组记录，而DB主语言语句一般一次只能处理一条记录，其协调可通过哪种技术实现（B） ? A. 指针 B. 游标 C. 数组 D. 栈 11、五种基本关系代数运算是( A ) ? A. ∪，-，×，π和σ B. ∪，-，?，π和σ 2017《数据结构》期末考试试题及答案 《数据结构》期末考试试题及答案 1 ................................................................. 2..试题 1 答案............................................................ 7..《数据结构》期末考试试题及答案 2 ................................................................. 9..试题 2 答案........................................................................ 1.. 4. 《数据结构》期末考试试题及答案 3 ............................................................... 1..6试题 3 答案........................................................................ 2.. 1. 数据结构》期末考试试题及答案 1 单选题（每题 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（io ）, A[2][2]存放 若有18个元素的有序表存放在一维数组 A[19]中，第一个元素放A[1]中, 现进行二分查找，则查找 A [3]的比较序列的下标依次为（ A. 1 ， 2， 3 B. 9， 5， 2， 3 C. 9， 5， 3 D. 9， 4， 2， 3 8. 对n 个记录的文件进行快速排序，所需要的辅助存储空间大致为 A. O （1） B. O （n ） C. O （ 1 og 2n ） D. O （n2） 9. 对于线性表（ 7， 34， 55， 25， 64， 46， 20， 10）进行散列存储时，若选 用 H （K ）=K %9 作为散列函数，则散列地址为 1 的元素有（ ）个， 位置在 676（10），每个元素占一个空间， 表示用 10 进制表示。 问 A[3][3] （10）存放在什么位置？脚注 （10） 5. A ．688 B ．678 C ． 692 D ． 696 树最适合用来表示 （ ）。 A.有序数据元素 B.无序数据元素 6. C.元素之间具有分支层次关系的数据 D .元素之间无联系的数据 二叉树的第 k 层的结点数最多为 （ ）. A ．2-1 B.2K+1 C.2K-1 D. 2k-1 7. 数据库期末考试复习题库(非常全面) 第一部分 第一章： 一选择题： 1．在数据管理技术的发展过程中，经历了人工管理阶段、文件系统阶段和数据库系统阶段。在这几个阶段中，数据独立性最高的是阶段。 A．数据库系统 B．文件系统 C．人工管理 D．数据项管理答案：A 2．数据库的概念模型独立于。 A．具体的机器和DBMS B．E-R图C．信息世界 D．现实世界答案：A 3．数据库的基本特点是。 A．(1)数据可以共享(或数据结构化) (2)数据独立性(3)数据冗余大，易移植(4)统一管理和控制 B．(1)数据可以共享(或数据结构化) (2)数据独立性(3)数据冗余小，易扩充(4)统一管理和控制 C．(1)数据可以共享(或数据结构化) (2)数据互换性(3)数据冗余小，易扩充(4)统一管理和控制 D．(1)数据非结构化 (2)数据独立性(3)数据冗余小，易扩充(4)统一管理和控制答案：B 4. 是存储在计算机内有结构的数据的集合。 A．数据库系统B．数据库C．数据库管理系统 D．数据结构答案：B 5．数据库中存储的是。 A．数据 B．数据模型C．数据以及数据之间的联系 D．信息答案：C 6. 数据库中，数据的物理独立性是指。 A．数据库与数据库管理系统的相互独立B．用户程序与DBMS的相互独立 C．用户的应用程序与存储在磁盘上数据库中的数据是相互独立的 D．应用程序与数据库中数据的逻辑结构相互独立答案：C 7. ．数据库的特点之一是数据的共享，严格地讲，这里的数据共享是指。 A．同一个应用中的多个程序共享一个数据集合 B．多个用户、同一种语言共享数据 C．多个用户共享一个数据文件 D．多种应用、多种语言、多个用户相互覆盖地使用数据集合答案：D 8.据库系统的核心是。 A．数据库B．数据库管理系统C．数据模型D．软件工具答案：B 9. 下述关于数据库系统的正确叙述是。 A．数据库系统减少了数据冗余 B．数据库系统避免了一切冗余 C．数据库系统中数据的一致性是指数据类型一致 D．数据库系统比文件系统能管理更多的数据答案：A 10. 数将数据库的结构划分成多个层次，是为了提 广东创新科技职业学院期末考试试题（标明A 卷、B 或C 卷） 2018 —2019 学年第二学期考试科目：《数据结构》 (闭（开）卷 90分钟) 院系____________ 班级____________ 学号___________ 姓名 __________ 一、选择题（每小题 2 分，共 40 分） 1.计算机识别、存储和加工处理的对象被统称为（）。 A ．数据 B ．数据元素 C ．数据结构 D ．数据类型 2.数据结构指的是数据之间的相互关系，即数据的组织形式。数据结构一般包括（）三方面内容。 A ．数据的逻辑结构、数据的存储结构、数据的描述 B ．数据的逻辑结构、数据的存储结构、数据的运算 C ．数据的存储结构、数据的运算、数据的描述 D ．数据的逻辑结构、数据的运算、数据的描述3．数据的逻辑结构包括（）。 A ．线性结构和非线性结构 B ．线性结构和树型结构 C ．非线性结构和集合结构 D ．线性结构和图状结构 4.（）的特征是：有且仅有一个开始结点和一个终端结点，且所有结点都最多只有一个直接前驱和一个直接后继。 A ．线性结构 B ．非线性结构 C ．树型结构 D ．图状结构 5. 评价一个算法时间性能的主要标准是（）。 A ．算法易于调试 B ．算法易于理解 C ．算法的稳定性和正确性 D ．算法的时间复杂度 6. 下述程序段①中各语句执行频度的和是（）。 s=0; ① for(i=1;i<=i;j++) s+=j; A ．n-1 B ．n C ．2n-1 D ．2n 7. 下面程序段的时间复杂度为（）。 for(i=0;i 贵州大学理学院数学系信息与计算科学专业 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 一、单项选择题 1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。 (A)、正确性(B). 可行性(C). 健壮性(D). 输入性 2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（）。 for(i=n-1；i>=0；i--) for(j=0；j 题型：选择 第一章 题型：名词解释 题目： 1）DB 答：DB是长期存储在计算机内、有组织的、统一管理的相关数据的集合。2）DBMS 答：DBMS是位于用户与OS之间的一层数据管理软件，它为用户或应用程序提供访问DB的方法。 3）DBS 答：DBS是实现有组织地、动态地存储大量关联数据，方便多用户访问的计算机硬件、软件和数据资源组成的系统，即采用数据库技术的计算机系统。4）数据独立性 答：应用程序和DB的数据结构之间相互独立，不受影响。 5）物理独立性 答：在DB的物理结构改变时，尽量不影响应用程序。 6）逻辑独立性 答：在DB的逻辑结构改变时，尽量不影响应用程序。 题型：问答 题目： 1）人工管理阶段的数据管理有哪些特点？ 答：人工管理阶段主要有4个特点：数据不保存在计算机内；没有专用的软件对数据进行管理；只有程序的概念，没有文件的概念；数据面向程序。2）文件系统阶段的数据管理有哪些特点？ 答：文件系统阶段主要有5个特点：数据以“文件”形式长期保存；数据的逻辑结构与物理结构有了区别；文件组织已多样化；数据面向应用；对数据的操作以记录为单位。 3）文件系统阶段的数据管理有些什么缺陷？试取例说明。 答：主要有3个缺陷：数据冗余；数据不一致性；数据联系弱。 例如：学校里教务处、财务处、保健处建立的文件中都有学生详细资料，如联系电话、家庭住址等，这就是“数据冗余”，如果某个学生搬家，就要修改3个部门文件中的数据，否则会引起同一数据在3个部门中不一致，产生上述问题的原因是这3个部门文件中的数据没有联系。 题型：填空 题目： 1）数据管理技术的发展，与________、________和________有密切的联系。 答：硬件、软件、计算机应用 2）文件系统中的数据独立性是指________独立性。 答：设备 3）文件系统的缺陷是：________、________和________。 答：数据冗余、数据不一致、数据联系弱 4）就信息处理的方式而言，在文件系统阶段，________处于主导地位，________只起着服从程序设计需要的作用；而在数据库方式下，________占据了中心位置。 数据库原理期末考试复习题一、单选题 1．在数据库中存储的是（）。 A. 数据 B. 数据模型 C. 数据及数据之间的联系 D. 信息 2．现有一个“教师”表，其中一个字段是教师的住址（字符型，20位长），如果不希望此字段包含空值，即某位教师现没有住址，则希望此字段自动填入“还没有”，应该（）。 A. 为此列创建一个check约束 B. 为此列创建一个foreign key约束 C. 为此列创建一个default约束 D. 为此列创建一个primary key约束 3．数据库系统包括（）。 A. DB、DBMS B. DB、DBA C. DB、DBMS、DBA、计算机硬件 D. DB、DBMS、DBA、OS、计算机硬件 4．假设同一名称的产品有不同的型号和产地，则计算每种产品平均单价的SQL语句是（）。 A. SELECT 产品名称,AVG(单价) FROM 产品 GROUP BY 单价 B. SELECT 产品名称,AVG(单价) FROM 产品 ORDER BY 单价 C. SELECT 产品名称,AVG(单价) FROM 产品 ORDER BY 产品名称 D. SELECT 产品名称,AVG(单价) FROM 产品 GROUP BY 产品名称 5．数据库中，数据的物理独立性是指（）。 A. 数据库与数据库管理系统的相互独立 B. 用户程序与DBMS的相互独立 C. 用户的应用程序与存储在磁盘上的数据库中的数据是相互独立的 D. 应用程序与数据库中数据的逻辑结构相互独立 6．关系数据库规范化是为解决关系数据库中（）问题而引入的。 A. 提高查询速度 B. 保证数据的安全性和完整性 C. 减少数据操作的复杂性 D. 插入异常、删除异常和数据冗余7．当前数据库应用系统的主流数据模型是（）。 A. 层次数据模型 B. 网状数据模型 C. 关系数据模型 D. 面向对象数据模型 8．如果两个实体集之间的联系是m:n，转换为关系时（）。 2005年－2006学年第二学期“数据结构”考试试题（A） 姓名学号(序号)_ 答案隐藏班号 要求：所有的题目的解答均写在答题纸上（每张答题纸上要写清楚姓名、班号和学号），需写清楚题目的序号。每张答题纸都要写上姓名和序号。 一、单项选择题（每小题2分，共20分） 1．数据的运算a 。 A.效率与采用何种存储结构有关 B.是根据存储结构来定义的 C.有算术运算和关系运算两大类 D.必须用程序设计语言来描述 答：A。 2. 链表不具备的特点是 a 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C.不必事先估计存储空间 D.所需空间与其长度成正比 答：参见本节要点3。本题答案为：A。 3. 在顺序表中删除一个元素的时间复杂度为 c 。 A.O(1) B.O(log2n) C.O(n) D.O(n2) 答：C。 4．以下线性表的存储结构中具有随机存取功能的是 d 。 A. 不带头结点的单链表 B. 带头结点的单链表 C. 循环双链表 D. 顺序表 解 D。 5. 一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是 c 。 A.edcba B.decba C.dceab D.abcde 答：C。 6. 循环队列qu的队空条件是 d 。 A. (qu.rear+1)%MaxSize==(qu.front+1)%MaxSize B. (qu.rear+1)%MaxSize==qu.front+1 C.(qu.rear+1)%MaxSize==qu.front D.qu.rear==qu.front 答：D。 7. 两个串相等必有串长度相等且 b 。 A.串的各位置字符任意 B.串中各位置字符均对应相等 C.两个串含有相同的字符 D.两个所含字符任意 答：B。 8. 用直接插入排序对下面四个序列进行递增排序，元素比较次数最少的是c 。 A.94,32,40,90,80,46,21,69 B.32,40,21,46,69,94,90, 80 C.21,32,46,40,80,69,90,94 D.90,69,80,46,21,32,94, 40 答：C。 9. 以下序列不是堆（大根或小根）的是 d 。 A.{100,85,98,77,80,60,82,40,20,10,66} B.{100,98,85,82,80, 77,66,60,40,20,10} C.{10,20,40,60,66,77,80,82,85,98,100} D.{100,85,40,77,80, 60,66,98,82,10,20}数据库期末考试习题及答案
数据库期末试题附答案
数据库期末考试试题及答案
数据库期末考试复习题及复习资料
2017年数据结构期末考试题及答案A
sql数据库期末考试题及答案
数据库期末考试试题及答案
数据库期末考试模拟试题及答案(一)
数据库期末考试复习题及答案共有套卷子
数据结构复习资料,java数据结构期末考试
《数据结构》期末考试题及答案
数据库期末考试复习题(附答案)
2017数据结构期末考试试题及答案
数据库期末考试复习题库
《数据结构》期末考试试卷
数据结构期末考试试题及答案
数据库期末考试部分试题
数据库原理与应用期末考试复习题
数据结构期末考试试题含答案
相关主题
文本预览