数据结构-形考作业3答案

(精华版)国家开放大学电大《数据结构》网络课形考网考作业及答案

(精华版)国家开放大学电大《数据结构》网络课形考网考作业及答案100%通过考试说明：2022年秋期电大把该网络课纳入到“国开平台”进行考核，该课程共有4个形考任务，针对该门课程，本人汇总了该科所有的题，形成一个完整的标准题库，并且以后会不断更新，对考生的复习、作业和考试起着非常重要的作用，会给您节省大量的时间。做考题时，利用本文档中的查找工具，把考题中的关键字输到查找工具的查找内容框内，就可迅速查找到该题答案。本文库还有其他网核及教学考一体化答案，敬请查看。课程总成绩=形成性考核×50%+终结性考试×50%形考任务1一、单项选择题（每小题3分，共60分） 题目1把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（）。

选择一项： D.物理结构题目2下列说法中，不正确的是（）。

选择一项： C.数据项可由若干个数据元素构成题目3一个存储结点存储一个（）。

选择一项： C.数据元素题目4数据结构中，与所使用的计算机无关的是数据的（）。

选择一项： C.逻辑结构题目5在线性表的顺序结构中，以下说法正确的是（）。

选择一项： D.逻辑上相邻的元素在物理位置上也相邻题目6对链表,以下叙述中正确的是（）。

选择一项： C.不能随机访问任一结点题目7下列的叙述中，不属于算法特性的是（）。 选择一项： C.可读性题目8算法的时间复杂度与（）有关。

选择一项： D.算法本身题目9设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），插入一个元素，则移动元素个数为（）。

选择一项： C.n-i+1题目10设有一个长度为n的顺序表，要删除第i个元素移动元素的个数为（）。

选择一项： C.n-i题目11在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（）。

11062227 李泽增

一、深度优先搜索

//构造结构体 图，该图为邻接表形式

struct Tu

{

int vexdata;

node first;

}

//构造链表结构体

struct node

{

int adjvex;

node next;

}

//遍历主函数

void search(Tu a[],int n)

{

int visited[n];

for(int i=0;i

for(int i=0;i

if(visited(i)==0) dfs(a,i,visited);

}

//遍历执行函数,递归调用

Void dfs(Tu a[],int i,int visited[])

{

node *p;

cout<

visited[i]=1;

p=a[i].first;

while(p!=NULL)

{

if(visited[p->adjvex]==0) dfs(a,p->adjvex,visited);

p=p->next;

}

}

<2>广度优先搜索

struct Tu

{

int vexdata;

node first;

}

struct node

{

int adjvex;

node next;

}

void search(Tu a[],int n)

{

int visited[n];

for(int i=0;i

for(int i=0;i

if(visited(i)==0) bfs(a,i,visited);

}

//使用队列dui[]数组完成广度优先搜索

void bfs(Tu a[],int i,int visited[])

{

node *p;

int dui[n];

s=0;t=0;

cout<

visited[i]=1;

dui[0]=i;

while(s<=t)

形考任务1答案

第 1 章 数据库系统概述（本章共20分）

一．单项选择题（每题1分，共10分）

1.数据库应用程序可以不经过数据库管理系统而直接读取数据库文件

2.将相关的数据存储在一个文件中，有利于用户对数据进行分类，因此也可以加快用户操作数据的效率

3.不会因为数据逻辑结构的变化而影响应用程序

4.操作系统

5.数据的独立性

6.模式

7.能够描述并发数据

8.数据结构、数据操作和数据完整性约束

9.一个联系可以不与任何实体有关

10.外模式到模式的映像以及模式到内模式的映像都是由DBMS实现的

二．判断题（每题1分，共5分）

11-15 对错对错对

三．简答题（本题共5分）

16.答：（1）相互关联的数据集合；（2）较少的数据冗；（4）保证数据的安全可靠；（5）最大限度地保证数据的正确性；（6）数据可以共享并能保证数据的一致性。

17.答：数据独立性包括逻辑独立性和物理独立性两部分。物理独立性是指当数据的存储结构发生变化时，不影响应用程序的特性；逻辑独立性是指当表达现实世界的信息内容发生变化时，不影响应用程序的特性。这两个独立性使用户只需关心逻辑层即可，同时增强了应用程序的可维护性。

18.答：实体是具有公共性质的并可相互区分的现实世界对象的集合。属性是实体所具有的特征或性质。联系是实体之间的关联关系。

第2章 关系数据库理论（本章共20分）

一．单项选择题（每题1分，共10分）

19.数据库管理系统

20.有m目x行数据的关系R和有n目y行数据的关系S进行笛卡尔积运算，其结果是有(m+n)目和(x+y)行数据的关系 21.进行自然连接的两个关系可以没有列名相同的列

22.进行并运算的两个关系的列个数必须相同，对应列的语义相同

23.维护数据的一致性

24.Y部分函数依赖于X

25.第三范式的关系模式一定不包含传递函数依赖，但可以包含部分函数依赖

26.第二范式

27.并运算

28.∏

一、 填空题

1．数据结构根据数据元素之间关系的不同特性，有四种基本结构：集合、线性结构、

和 。

2．数据结构的形式定义可用二元组表示，其成分分为数据元素的有限集，和

。

3．一个好的算法设计应满足正确性、 、健壮性和效率与低存储量需求。

4．数组是一种 存取的存储结构。

5．串中 组成的子序列称该串的子串。

6．稀疏矩阵存储时，常采用三元组表和 的表示方法。

7．设树T的度为4，其中度为1、2、3、4的结点个数分别为4、2、1、1，则T中叶子结点的个数是 。

8．指针pred 指向刚刚访问过的结点，p 指向当前访问的结点，结点的结构含有左指针lchild，右指针rchild，左标志ltag，右标志rtag，当结点的左指针为空时，线索化操作为：p->ltag=1；和 。

9．用图的顶点表示活动，用弧表示活动间的优先关系的有向图称为 网。

10．排序方法稳定的，是指排序后的序列中 的元素前后次序仍不变。

11．文件在存储介质（磁盘或磁带）上的组织方式称为文件的 。

12．索引文件是包括 和索引表两大部分的文件。

13．在算法是正确的前提下，评价算法的两个标准是 、 。

14．链表是一种 存取的存储结构。