数据结构作业系统_第七章答案

《数据结构》填空作业题答案第 1 章绪论（已校对无误）1．数据结构包括数据的逻辑结构、数据的存储结构和数据的运算三方面的内容。

2．程序包括两个内容：数据结构和算法。

3.数据结构的形式定义为：数据结构是一个二元组：Data Structure =（ D， S）。

4.数据的逻辑结构在计算机存储器内的表示，称为数据的存储结构。

5.数据的逻辑结构可以分类为线性结构和非线性结构两大类。

6.在图状结构中，每个结点的前驱结点数和后继结点数可以有多个。

7.在树形结构中，数据元素之间存在一对多的关系。

8.数据的物理结构，指数据元素在计算机中的标识（映象），也即存储结构。

9.数据的逻辑结构包括线性结构、树形结构和图形结构 3 种类型，树型结构和有向图结构合称为非线性结构。

10. 顺序存储结构是把逻辑上相邻的结点存储在物理上连续的存储单元里，结点之间的逻辑关系由存储单元位置的邻接关系来体现。

11. 链式存储结构是把逻辑上相邻的结点存储在物理上任意的存储单元里，节点之间的逻辑关系由附加的指针域来体现。

12.数据的存储结构可用 4 种基本的存储方法表示，它们分别是顺序存储、链式存储、索引存储和散列存储。

13. 线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是一对多或多对多。

14.数据结构在物理上可分为顺序存储结构和链式存储结构。

15. 我们把每种数据结构均视为抽象类型，它不但定义了数据的表示方式，还给出了处理数据的实现方法。

16.数据元素可由若干个数据项组成。

17.算法分析的两个主要方面是时间复杂度和空间复杂度。

18.一个算法的时间复杂度是用该算法所消耗的时间的多少来度量的，一个算法的空间复杂度是用该算法在运行过程中所占用的存储空间的大小来度量的。

19.算法具有如下特点：有穷性、确定性、可行性、输入、输出。

20. 对于某一类特定的问题，算法给出了解决问题的一系列操作，每一操作都有它的确切的定义，并在有穷时间内计算出结果。

第一章绪论一、选择题1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。

1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像2 A.结构 B.关系 C.运算 D.算法2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。

1 A.算法 B.数据元素 C.数据操作 D.逻辑结构2 A.操作 B.映像 C.存储 D.关系3.在数据结构中，从逻辑上可以把数据结构分成。

A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。

A.随机存取 B.顺序存取 C.索引存取 D.散列存取5.算法分析的目的是1，算法分析的两个主要方面其一是指2，其二是指正确性和简单性。

1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性2 A.空间复杂度和时间复杂度 B.研究算法中的输入和输出的关系C.可读性和文档性D.数据复杂性和程序复杂性k6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。

1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。

A.正确 B.不正确8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。

A.必须连续的B.部分地址必须连续的C.一定是不续的D连续不连续都可以9.以下的叙述中，正确的是。

A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。

参考答案第一章、绪论一、选择题1 B；2 A； 3 B；4 C ；5 C； 6 B；7 C；8 C；9 D；10 B。

二、填空题1、存储；2、无，1，无，1；3、前驱，1，后继，任意多个；4、一对一，一对多，多对多；5、时间复杂度，空间复杂度；6、集合，线性结构，树形结构，图形结构；7、顺序结构，链式结构，索引结构，散列结构；8、顺序。

三、问答题与算法题1、3 ；2、T1 ( n ) = 5n 2 -O ( n ) ; T2 ( n ) = 3 n 2 + O ( n ) ; T3 ( n ) = 8 n 2 + O(log n) ;T4 ( n ) = 1.5 n 2 + O ( n ) 。

T4 ( n ) 较优，T3 ( n )较劣。

3、见课本。

第二章线性表一、选择题1C；2A；3D；4B；5D；6B；7C；8B；9A；10C；11D；12D；13C；14C.二、填空题1、O ( 1 ), O ( n )；2、单链表，双链表；3、地址，指针；4、4，2；5、便于访问尾结点和头结点；6、前驱；7、L->next== L且L->prior== L；8、顺序。

三、问答题与算法题1、头指针：结点或头结点的指针变量。

其作用是存放第一个结点或头结点的地址，从头指针出发可以找到链表中所有结点的信息。

头结点：是附加在链表的第一个结点之前的一个特殊结点，其数据域一般不存放信息。

其作用是为了简化运算，将空表与非空表统一起来，将第一个结点与其他结点的处理统一起来。

首结点：是链表的第一个结点。

2、(1)基于空间的考虑。

当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。

(2)基于时间的考虑。

若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。

《数据结构（C语言版第2版）》（严蔚敏著）第七章练习题答案第7章查找1．选择题（1）对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（）。

A．(n-1)/2B．n/2C．(n+1)/2D．n答案：C解释：总查找次数N=1+2+3+…+n=n(n+1)/2，则平均查找长度为N/n=(n+1)/2。

（2）适用于折半查找的表的存储方式及元素排列要求为（）。

A．链接方式存储，元素无序B．链接方式存储，元素有序C．顺序方式存储，元素无序D．顺序方式存储，元素有序答案：D解释：折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

（3）如果要求一个线性表既能较快的查找，又能适应动态变化的要求，最好采用()查找法。

A．顺序查找B．折半查找C．分块查找D．哈希查找答案：C解释：分块查找的优点是：在表中插入和删除数据元素时，只要找到该元素对应的块，就可以在该块内进行插入和删除运算。

由于块内是无序的，故插入和删除比较容易，无需进行大量移动。

如果线性表既要快速查找又经常动态变化，则可采用分块查找。

（4）折半查找有序表（4，6，10，12，20，30，50，70，88，100）。

若查找表中元素58，则它将依次与表中（）比较大小，查找结果是失败。

A．20，70，30，50B．30，88，70，50C．20，50D．30，88，50答案：A解释：表中共10个元素，第一次取⎣(1+10)/2⎦=5，与第五个元素20比较，58大于20，再取⎣(6+10)/2⎦=8，与第八个元素70比较，依次类推再与30、50比较，最终查找失败。

（5）对22个记录的有序表作折半查找，当查找失败时，至少需要比较（）次关键字。

A．3B．4C．5D．6答案：B解释：22个记录的有序表，其折半查找的判定树深度为⎣log222⎦+1=5，且该判定树不是满二叉树，即查找失败时至多比较5次，至少比较4次。

（6）折半搜索与二叉排序树的时间性能（）。

d
A. A. {d,e,c,f,a,g,b}
B. B. {f,e,g,d,a,c,b}
C. C. {e,f,d,g,b,c,a}
D. D. {c,d,b,e,f,a,g }
6.栈和队列都是____a__。【第三章_栈和队列的基本概念P44，需要理解】
A. A.限制存取位置的线性结构
B. B.顺序存储的线性结构
c
A. A.快速排序<归并排序<直接插入排序=冒泡排序
B. B.快速排序=归并排序
C. C. Shell排序<快速排序=归并排序<直接插入排序=冒泡排序
D. D.直接插入排序=冒泡排序< Shell排序<快速排序=归并排序
15.
在冒泡排序、快速排序、堆排序、归并排序中，______d___排序是稳定的。【第十章】
作业ID：82376
1.
以下哪个算法的时间复杂度表示是最慢的？___b____【第一章】
A. A. O(1)
B. B. O(log2n)
C. C. O(n)
D. D. O(n^2 )
2.在一个线性表中，假设第一个元素a1的存储地址是20，每个元素占用四个存储单元，则第8个数据元素a8的地址是_c___：【第二章】
B. B. {25, 36, 48, 72, 16, 23, 40, 79, 82, 35}
C. C. {25, 36, 48, 72, 16, 23, 35, 40, 79, 82}
D. D. {16, 23, 25, 35, 36, 40, 48, 72, 79, 82}
14.
直接插入排序、快速排序、冒泡排序、归并排序、Shell排序，当元素数量很大时，时间复杂度按从小到大的顺序是如何排列的？【第十章】

例
a c G1
b d
vexdata firstarc adjvex next 1 4 ^ a 2 3 4 b c d 1 1 3 ^ ^ ^
19
7.3 图的遍历
深度优先遍历(DFS) 深度优先遍历
方法：从图的某一顶点 出发，访问此顶点； 方法：从图的某一顶点V0出发，访问此顶点；然后依 次从V 的未被访问的邻接点出发，深度优先遍历图， 次从 0的未被访问的邻接点出发，深度优先遍历图， 直至图中所有和V 相通的顶点都被访问到； 直至图中所有和 0相通的顶点都被访问到；若此时图 中尚有顶点未被访问， 中尚有顶点未被访问，则另选图中一个未被访问的顶 点作起点，重复上述过程， 点作起点，重复上述过程，直至图中所有顶点都被访 问为止。 问为止。
ω ij , 若(v i , v j )或 < v i , v j >∈ E(G) A[i, j ] = 0，其它
11
例
1 3
5
2
8 4 7 5 1 6 3 4 2
0 5 7 0 3
5 0 0 4 8
7 0 0 2 1
0 4 2 0 6
3 8 1 6 0
12
关联矩阵——表示顶点与边的关联关系的矩阵 表示顶点与边的关联关系的矩阵 关联矩阵
1
7.1 图的定义和术语
是由两个集合V(G)和E(G)组成的 组成的, 图(Graph)——图G是由两个集合 图 是由两个集合 和 组成的 记为G=(V,E) 记为
其中： 其中：V(G)是顶点的非空有限集 是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对或有序对 是边的有限集合， 是边的有限集合
有向图——有向图 是由两个集合 有向图G是由两个集合 有向图 有向图 是由两个集合V(G)和E(G)组成的 和 组成的

7.22③试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)。

注意：算法中涉及的图的基本操作必须在此存储结构上实现。

实现下列函数：Status DfsReachable(ALGraph g, int i, int j);/* Judge if it exists a path from vertex 'i' to *//* vertex 'j' in digraph 'g'. */ /* Array 'visited[]' has been initialed to 'false'.*/图的邻接表以及相关类型和辅助变量定义如下：Status visited[MAX_VERTEX_NUM];typedef char VertexType;typedef struct ArcNode {int adjvex;struct ArcNode *nextarc;} ArcNode;typedef struct VNode {V ertexType data;ArcNode *firstarc;} VNode, AdjList[MAX_VERTEX_NUM];typedef struct {AdjList vertices;int vexnum, arcnum;} ALGraph;Status DfsReachable(ALGraph g, int i, int j)/* Judge if it exists a path from vertex 'i' to *//* vertex 'j' in digraph 'g'. */ /* Array 'visited[]' has been initialed to 'false'.*/{int k;ArcNode *p;visited[i]=1;for(p=g.vertices[i].firstarc;p;p=p->nextarc){if(p){k=p->adjvex;if(k==j)return 1;if(visited[k]!=1)if(DfsReachable(g,k,j))return 1;}}return 0;}7.23③同7.22题要求。

《数据结构》填空作业题答案第1章绪论（已校对无误）1．数据结构包括数据的逻辑结构、数据的存储结构和数据的运算三方面的内容。

2．程序包括两个内容：数据结构和算法。

3. 数据结构的形式定义为：数据结构是一个二元组：Data Structure =（D，S）。

4. 数据的逻辑结构在计算机存储器内的表示，称为数据的存储结构。

5. 数据的逻辑结构可以分类为线性结构和非线性结构两大类。

6. 在图状结构中，每个结点的前驱结点数和后继结点数可以有多个。

7. 在树形结构中，数据元素之间存在一对多的关系。

8. 数据的物理结构，指数据元素在计算机中的标识（映象），也即存储结构。

9. 数据的逻辑结构包括线性结构、树形结构和图形结构3种类型，树型结构和有向图结构合称为非线性结构。

10. 顺序存储结构是把逻辑上相邻的结点存储在物理上连续的存储单元里，结点之间的逻辑关系由存储单元位置的邻接关系来体现。

11. 链式存储结构是把逻辑上相邻的结点存储在物理上任意的存储单元里，节点之间的逻辑关系由附加的指针域来体现。

12. 数据的存储结构可用4种基本的存储方法表示，它们分别是顺序存储、链式存储、索引存储和散列存储。

13. 线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是一对多或多对多。

14. 数据结构在物理上可分为顺序存储结构和链式存储结构。

15. 我们把每种数据结构均视为抽象类型，它不但定义了数据的表示方式，还给出了处理数据的实现方法。

16. 数据元素可由若干个数据项组成。

17. 算法分析的两个主要方面是时间复杂度和空间复杂度。

18. 一个算法的时间复杂度是用该算法所消耗的时间的多少来度量的，一个算法的空间复杂度是用该算法在运行过程中所占用的存储空间的大小来度量的。

19. 算法具有如下特点：有穷性、确定性、可行性、输入、输出。

20. 对于某一类特定的问题，算法给出了解决问题的一系列操作，每一操作都有它的确切的定义，并在有穷时间内计算出结果。

数据库课后习题作业答案《数据库系统概论》课程习题及参考答案第⼀章绪论（教材37页）１.试述数据、数据库、数据库系统、数据库管理系统的概念。

答：数据：描述事物的符号记录称为数据。

数据的种类有⽂字、图形、图像、声⾳、正⽂等等。

数据与其语义是不可分的。

数据库：数据库是长期储存在计算机内、有组织的、可共享的数据集合。

数据库中的数据按⼀定的数据模型组织、描述和储存，具有较⼩的冗余度、较⾼的数据独⽴性和易扩展性，并可为各种⽤户共享。

数据库系统：数据库系统(DBS)是指在计算机系统中引⼊数据库后的系统构成。

数据库系统由数据库、数据库管理系统(及其开发⼯具)、应⽤系统、数据库管理员构成。

数据库管理系统：数据库管理系统(DBMS)是位于⽤户与操作系统之间的⼀层数据管理软件。

⽤于科学地组织和存储数据、⾼效地获取和维护数据。

DBMS 主要功能包括数据定义功能、数据操纵功能、数据库的运⾏管理功能、数据库的建⽴和维护功能。

２.使⽤数据库系统有什么好处？答：使⽤数据库系统的好处是由数据库管理系统的特点或优点决定的。

使⽤数据库系统的好处很多，例如可以⼤⼤提⾼应⽤开发的效率，⽅便⽤户的使⽤，减轻数据库系统管理⼈员维护的负担等。

为什么有这些好处，可以结合第 5题来回答。

使⽤数据库系统可以⼤⼤提⾼应⽤开发的效率。

因为在数据库系统中应⽤程序不必考虑数据的定义、存储和数据存取的具体路径，这些⼯作都由 DBMS来完成。

此外，当应⽤逻辑改变，数据的逻辑结构需要改变时，由于数据库系统提供了数据与程序之间的独⽴性。

数据逻辑结构的改变是 DBA的责任，开发⼈员不必修改应⽤程序，或者只需要修改很少的应⽤程序。

从⽽既简化了应⽤程序的编制，⼜⼤⼤减少了应⽤程序的维护和修改。

使⽤数据库系统可以减轻数据库系统管理⼈员维护系统的负担。

因为 DBMS 在数据库建⽴、运⽤和维护时对数据库进⾏统⼀的管理和控制，包括数据的完整性、安全性，多⽤户并发控制，故障恢复等等都由DBMS执⾏。

数据库系统第七章习题答案数据库系统第七章习题答案数据库系统是计算机科学中的一个重要分支，它研究如何存储、管理和检索大量结构化数据的方法和技术。

在数据库系统的学习过程中，习题是检验学生对知识掌握程度的重要方式之一。

本文将为读者提供数据库系统第七章习题的详细答案。

第一题：假设有一个名为"Students"的关系模式，包含学生的学号（Sid）、姓名（Name）和年龄（Age）三个属性。

请写出一个SQL语句，查询年龄大于20岁的学生的学号和姓名。

答案：SELECT Sid, Name FROM Students WHERE Age > 20;第二题：在上题的基础上，假设还有一个名为"Courses"的关系模式，包含课程的课程号（Cid）、课程名称（Cname）和学分（Credit）三个属性。

请写出一个SQL语句，查询选修了学号为"1001"的学生所选的所有课程的课程号和课程名称。

答案：SELECT Cid, Cname FROM Courses WHERE Cid IN (SELECT Cid FROM Selection WHERE Sid = '1001');第三题：在上题的基础上，假设还有一个名为"Selection"的关系模式，包含学生的学号（Sid）和所选课程的课程号（Cid）两个属性。

请写出一个SQL语句，查询选修了课程号为"C001"的课程的学生的学号和姓名。

答案：SELECT Sid, Name FROM Students WHERE Sid IN (SELECT Sid FROM Selection WHERE Cid = 'C001');第四题：在上题的基础上，假设还有一个名为"Scores"的关系模式，包含学生的学号（Sid）和课程的课程号（Cid）两个属性，以及学生在该课程中的成绩（Score）属性。

第一章习题答案2、××√3、（1）包含改变量定义的最小范围（2）数据抽象、信息隐蔽（3）数据对象、对象间的关系、一组处理数据的操作（4）指针类型（5）集合结构、线性结构、树形结构、图状结构（6）顺序存储、非顺序存储（7）一对一、一对多、多对多（8）一系列的操作（9）有限性、输入、可行性4、（1）A（2）C（3）C5、语句频度为1+（1+2）+（1+2+3）+…+（1+2+3+…+n）第二章习题答案1、（1）一半，插入、删除的位置（2）顺序和链式，显示，隐式（3）一定，不一定（4）头指针，头结点的指针域，其前驱的指针域2、（1）A（2）A：E、AB：H、L、I、E、AC：F、MD：L、J、A、G或J、A、G（3）D（4）D（5）C（6）A、C3、头指针：指向整个链表首地址的指针，标示着整个单链表的开始。

头结点：为了操作方便，可以在单链表的第一个结点之前附设一个结点，该结点的数据域可以存储一些关于线性表长度的附加信息，也可以什么都不存。

首元素结点：线性表中的第一个结点成为首元素结点。

4、算法如下：int Linser(SeqList *L,int X){ int i=0,k;if(L->last>=MAXSIZE-1){ printf(“表已满无法插入”)；return(0);}while(i<=L->last&&L->elem[i]<X)i++;for(k=L->last;k>=I;k--)L->elem[k+1]=L->elem[k];L->elem[i]=X;L->last++;return(1);}5、算法如下：#define OK 1#define ERROR 0Int LDel(Seqlist *L,int i,int k){ int j;if(i<1||(i+k)>(L->last+2)){ printf(“输入的i，k值不合法”);return ERROR;}if((i+k)==(L->last+2)){ L->last=i-2;ruturn OK;}else{for(j=i+k-1;j<=L->last;j++)elem[j-k]=elem[j];L->last=L->last-k;return OK;}}6、算法如下：#define OK 1#define ERROR 0Int Delet(LInkList L,int mink,int maxk){ Node *p,*q;p=L;while(p->next!=NULL)p=p->next;if(mink<maxk||(L->next->data>=mink)||(p->data<=maxk)) { printf(“参数不合法”);return ERROR;}else{ p=L;while(p->next-data<=mink)p=p->next;while(q->data<maxk){ p->next=q->next;free(q);q=p->next;}return OK;}}9、算法如下：int Dele(Node *S){ Node *p;P=s->next;If(p= =s){printf(“只有一个结点，不删除”)；return 0;}else{if((p->next= =s){s->next=s;free(p);return 1;}Else{ while(p->next->next!=s)P=p->next;P->next=s;Free(p);return 1;}}}第三章习题答案2、（1）3、栈有顺序栈和链栈两种存储结构。

1、判定一个有向图是否存在回路，除了利用拓扑排序方法外，还可以利用（ ）A 、求关键路径的方法B 、求最短路径的Dijkstra 方法C 、宽度优先遍历算法D 、深度优先遍历算法 2.图中有关路径的定义是（ ）oA. 由顶点和相邻顶点序偶构成的边所形成的序列B. 由不同顶点所形成的序列C. 由不同边所形成的序列D.上述定义都不是3. 一个n 个顶点的连通无向图，其边的个数至少为（）4. 当一个有N 个顶点的无向图用邻接矩阵 A 表示时，顶点Vi 的度是（）5. 下列说法不正确的是（ ）oA. 图的遍历是从给定的源点出发每一个顶点仅被访问一次B. 遍历的基本算法有两种：深度遍历和广度遍历C. 图的深度遍历不适用于有向图D. 图的深度遍历是一个递归过程6. 无向图 G=(V,E)，其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)},对该图进行深度优先遍历，得到的顶点序 列正确的是( )oA . a,b,e,c,d,fB . a,c,f,e,b,dC . a,e,b,c,f,dD . a,e,d,f,c,b 7. 设图如右所示，在下面的5个序列中，符合深度优先遍历的序列有多少？（a e d f cb a e f dc b C . 3个&在图采用邻接表存储时，求最小生成树的A. O （n ） B O （n+e ） 9.已知有向图 G=(V,E)，其中 V={V 1,V 2,V 3,V 4,V 5,V 6,V 7},E={VV 1,V 2>,VV 1,V 3>,VV 1,V 4>,VV 2,V 5>,VV 3,V 5>,VV 3,V 6>,VV 4,V 6>,VV 5,V 7>,VV 6,V 7>},A . n-1B . nC . n+1D . nlogn ；nZ A[i, j]A. i 4nZ A 【,j]B. 订nZ A[j,i]C . VnnS A[i, j]迟 Aj,i]D. v + vPrim 算法的时间复杂度为（23C. O （n ）D. O （n ） )oa eb d f cB . 4个G 的拓扑序列是（）。

第一章绪论一、选择题1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。

1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像2 A.结构 B.关系 C.运算 D.算法2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。

1 A.算法 B.数据元素 C.数据操作 D.逻辑结构2 A.操作 B.映像 C.存储 D.关系3.在数据结构中，从逻辑上可以把数据结构分成。

A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。

A.随机存取 B.顺序存取 C.索引存取 D.散列存取5.算法分析的目的是1，算法分析的两个主要方面其一是指2，其二是指正确性和简单性。

1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性2 A.空间复杂度和时间复杂度 B.研究算法中的输入和输出的关系C.可读性和文档性D.数据复杂性和程序复杂性k6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。

1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。

A.正确 B.不正确8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。

A.必须连续的B.部分地址必须连续的C.一定是不续的D连续不连续都可以9.以下的叙述中，正确的是。

A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。

树形结构中元素之间存在一对多_关系。（第一章）
2
n
3.一个算法的最基本的原操作执行次数为(3n +2nlog2 +4n-7)/(7n),则该算法的时间
复杂度为_ O(n)______。（第一章）
4.链式存储结构用一组地址任意的存储单元依次存放数据元素，数据元素之间的逻辑
关系通过__指针________间接地反映。（第二章）
答 顺序表的优点势可以随机访问数据元素；缺点是大小固定，不利于增减结点（增 减操作需要移动元素）。链表的优点是采用指针方式增减结点，非常方便（只需要改 变指针指向，不移动结点）。其缺点是不能进行随机访问，只能顺序访问；另外，每
第５页 共 10 页
个结点上增加指针域，造成额外存储空间增大。
2. （第二章）在一个单链表 HL 中删除指针 p 所指结点，应执行如下关键操作： if(________) HL = HL->next; else { q = HL; while(________) q = q->next; _____________; } delete p;
件是_____B_____。（第五章）
a 空或只有一个结点
b 高度等于其结点数
c 任一结点无右孩子
d 任一结点无左孩子
21. 树的基本遍历策略分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序
遍历、中序遍历和后序遍历。结论___A_______是正确的。（第五章）
a.树的先根遍历序列与其对应的二叉树的先序遍历序列相同
08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，

第二十页，编辑于星期五：九点 九分。
例子
【例】已知关系R〈U，F〉，其中U={A，B，C，D，E}， F={AB→C，B→D，C→E，EC→B，AC→B}，求(AB)F+。 设X=AB ∵ XF(0)=AB XF(1)=ABCD
XF(2)=ABCDE
XF(3)= XF(2)=ABCDE ∴ (AB)F+=ABCDE={A，B，C，D，E}
XF+={ Ai | Ai∈U，X→Ai∈F+}
第十九页，编辑于星期五：九点 九分。
(2) 属性集闭包XF+的求法
1) 选X作为闭包XF+的初值XF(0)。 2) XF(i+1)是由XF(i)并上集合A所组成，其中A为F中存在 的函数依赖Y→Z，而AZ，YXF(i)。 3) 重复步骤2)。一旦发现XF(i)= XF(i+1)，则XF(i)为所求 XF+。
1) 合并规则：由X→Y，X→Z，有X→YZ。 2) 伪传递规则：由X→Y，WY→Z，有XW→Z。 3) 分解规则：由X→Y及ZY，有X→Z。
第十八页，编辑于星期五：九点 九分。
3. 函数依赖集闭包F+和属性集闭包XF+
(1) 函数依赖集闭包F+和属性集闭包XF+的定义 定义：在关系模式R〈U，F〉中，为F所逻辑蕴含的函数 依赖的全体叫做F的闭包，记作F+。 定义：设有关系模式R〈U，F〉，X是U的子集，称所有 从F推出的函数依赖集X→Ai中Ai的属性集为X的属性闭 包，记作XF+。即：
第八页，编辑于星期五：九点 九分。
完全函数依赖、传递函数依赖
2) 在R〈U〉中，如果X→Y，并且对于X的任何一个真子集X’，
都有X’ Y，则称Y对X完全函数依赖，记作：X→Y；若XF →Y，

第七章习题解答和解析1. 试述数据库设计过程。

答：这里只概要列出数据库设计过程的六个阶段:(1) 需求分析;(2) 概念结构设计;(3) 逻辑结构设计;(4) 数据库物理设计;(5) 数据库实施;(6) 数据库运行和维护。

这是一个完整的实际数据库及其应用系统的设计过程。

不仅包括设计数据库本身,还包括数据库的实施、运行和维护。

设计一个完善的数据库应用系统往往是上述六个阶段的不断反复。

解析：希望读者能够认真阅读《概论》7.1 的内容,了解并掌握数据库设计过程。

2.试述数据库设计过程中结构设计部分形成的数据库模式。

答：数据库结构设计的不同阶段形成数据库的各级模式,即:(1) 在概念设计阶段形成独立于机器特点,独立于各个DB MS 产品的概念模式,在本篇中就是E-R 图;(2) 在逻辑设计阶段将E-R 图转换成具体的数据库产品支持的数据模型,如关系模型,形成数据库逻辑模式,然后在基本表的基础上再建立必要的视图(View), 形成数据的外模式;(3) 在物理设计阶段,根据DB MS 特点和处理的需要,进行物理存储安排,建立索引,形成数据库内模式。

读者可以参考《概论》上图7.4。

图中概念模式是面向用户和设计人员的,属于概念模型的层次;逻辑模式、外模式、内模式是DBMS 支持的模式,属于数据模型的层次,可以在DBMS 中加以描述和存储。

3.需求分析阶段的设计目标是什么? 调查的内容是什么?答需求分析阶段的设计目标是通过详细调查现实世界要处理的对象(组织、部门、企业等),充分了解原系统(手工系统或计算机系统)工作概况,明确用户的各种需求,然后在此基础上确定新系统的功能。

调查的内容是“数据”和“处理”,即获得用户对数据库的如下要求:(1) 信息要求,指用户需要从数据库中获得信息的内容与性质,由信息要求可以导出数据要求,即在数据库中需要存储哪些数据;(2) 处理要求,指用户要完成什么处理功能,对处理的响应时间有什么要求,处理方式是批处理还是联机处理;(3) 安全性与完整性要求。

第一章作业一、选择题1. 算法的计算量的大小称为计算的（ B ）。

A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（ C）A．问题的规模 B. 待处理数据的初态 C. A和B3.计算机算法指的是（C），它必须具备（B）这三个特性。

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性4．一个算法应该是（ B ）。

A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C.5. 下面关于算法说法错误的是（ D ）A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是（ A ）(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（ C ）两大类。

A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构8．在下面的程序段中，对x的赋值语句的频度为（ c ）FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A． O(2n) B．O(n) C．O(n2) D．O(log2n)9．程序段 FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOif A[j]>A[j+1]A[j]与A[j+1]对换；其中 n为正整数，则最后一行的语句频度在最坏情况下是（D ）A. O（n）B. O(nlogn)C. O(n3)D. O(n2)二、判断题1. 数据元素是数据的最小单位。