数据结构作业题

《数据结构》填空作业题答案

第1章 绪论（已校对无误）

1．数据结构包括 数据的逻辑结构 、 数据的存储结构 和 数据的运算 三方面的内容。2．程序包括两个内容： 数据结构 和 算法 。

3. 数据结构的形式定义为：数据结构是一个二元组： Data Structure =（D，S） 。 4. 数据的逻辑结构在计算机存储器内的表示，称为数据的 存储结构 。 5. 数据的逻辑结构可以分类为 线性 结构和 非线性 结构两大类。 6. 在图状结构中，每个结点的前驱结点数和后继结点数可以 有多个 。 7. 在树形结构中，数据元素之间存在 一对多 的关系。

8. 数据的物理结构，指数据元素在 计算机 中的标识（映象），也即 存储结构 。 9. 数据的逻辑结构包括 线性结构 、 树形结构 和 图形结构 3种类型，树型结构和有向图结构合称为 非线性结构 。

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

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

《数据结构》填空作业题答案

第1章 绪论（已校对无误）

1．数据结构包括 数据的逻辑结构 、 数据的存储结构 和 数据的运算 三方面的内容。2．程序包括两个内容： 数据结构 和 算法 。

3. 数据结构的形式定义为：数据结构是一个二元组： Data Structure =（D，S） 。 4. 数据的逻辑结构在计算机存储器内的表示，称为数据的 存储结构 。 5. 数据的逻辑结构可以分类为 线性 结构和 非线性 结构两大类。 6. 在图状结构中，每个结点的前驱结点数和后继结点数可以 有多个 。 7. 在树形结构中，数据元素之间存在 一对多 的关系。

8. 数据的物理结构，指数据元素在 计算机 中的标识（映象），也即 存储结构 。 9. 数据的逻辑结构包括 线性结构 、 树形结构 和 图形结构 3种类型，树型结构和有向图结构合称为 非线性结构 。

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

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

第一章作业 一、选择题

1. 被计算机加工的数据元素不是孤立的，它们彼此之间一般存在某种关系，通常把数据元素之间的

这种关系称为( )。 A. 规则 B. 结构 C. 集合 D. 运算 2. 在Data_Structure=(D,S)中，D是( )的有限集合。

A. 数据元素 B. 算法 C. 数据操作 D.数据对象 3. 计算机所处理的数据一般具有某种关系，这是指( )之间存在的某种关系。

A. 数据与数据 B. 数据元素与数据元素 C. 元素内数据项与数据项 D. 数据文件内记录与记录 4. 顺序存储表示中数据元素之间的逻辑关系是由( )表示的。

A. 指针 B. 逻辑顺序 C. 存储位置 D. 问题上下文 5. 链接存储表示中数据元素之间的逻辑关系是由( )表示的。

A. 指针 B. 逻辑顺序 C. 存储位置 D. 问题上下文 6. 从逻辑上可将数据结构分为( )。

A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 内部结构和外部结构 D. 线性结构和非线性结构 7. 以下选项属于线性结构的是( )。

A. 广义表 B. 二叉树 C. 串 D. 稀疏数组 8. 以下选项属于非线性结构的是( )。

A. 广义表

东北农业大学网络教育学院 数据结构作业题（一）

一、选择题（每题2分，共20分）

1．在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（ ）。

2

A、O(n) B、O (n/2) C、O (1) D、O (n) 2．带头结点的单链表first为空的判定条件是（ ）。

A、first == NULL; B、first->link == NULL; C、first->link == first; D、first != NULL; 3．在一棵树中，（ ）没有前驱结点。

A、分支结点 B、叶结点 C、树根结点 D、空结点 4．在有向图中每个顶点的度等于该顶点的（ ）。 A、入度 B、出度 C、入度与出度之和 D、入度与出度之差

5．对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（ ）的值除以9。 A、20 B、18 C、25 D、22 6．下列程序段的时间复杂度为（ ）。 s=0；

for(i=1；i

D、O (n2)

7．栈是一

《数据结构》课程大作业题目列表

《数据结构》课程大作业要求：

每3~4名同学一组，每组任选作业题目中的一题，组内同学一起进行分析，每个人负责题目中的一个模块进行设计和实现。最后一次上机时，在上机实验室现场，每组分别演示自己的程序，每个同学讲解自己设计的部分，由老师打分。该分数与平时作业和平时上机一起计算进总成绩中。

1. 航空客运订票系统 ................................................................................................................... 2 2. 全国交通咨询模拟 ................................................................................................................... 4 3. 五子棋的设计与实现 ..............................................................................................

数据结构习题

第一章 绪论

1.6 在程序设计中，常用下列三种不同的出错处理方式： 1) 用exit语句终止执行并报告错误； 2) 以函数的返回值区别正确返回或错误返回； 3) 设置一个整形变量的函数参数以区别正确返回或某种错误返回。 试讨论这三种方法各自的优缺点。

1.7 在程序设计中，可采用下列三种方法实现输出和输入： 1) 通过scanf和printf语句； 2) 通过函数的参数显示传递； 3) 通过全局变量隐式传递。 试讨论这三种方法的优缺点。

1.8 设n为正整数。试确定下列各程序段中前置以记号@的语句的频度： 5) for (i = 1; i <= n; i++ ) { for (j = 1; j <= i; j++) { for (k = 1; k <= j; k++) { @ x += delta; } } }

答案：n*(n+1)*(n+2)

=1+（1+2）+（1+2+3）+...+(1+2+3+...+n) =

i*(i?1)/2 ?i?1n =1/2*

i*i?i?i?1n

=n*(n+1)*(2n+1)/12 +n*(n+1)/4

=n*(n+1)*(n+2)/6 7) x = n; //n是不小于1的常数 y = 0; while (x >= (y + 1) * (y + 1)) { @ y++;

C 线性表

1. 初始化线性表L InitList(L) 2. 销毁线性表L DestoryList(L) 3. 清空线性表L ClearList(L) 4. 求线性表L的长度 ListLength(L) 5. 判断线性表L是否为空 IsEmpty(L)

6. 获取线性表L中的某个数据元素内容 GetElem(L,i,e) 7. 检索值为e的数据元素 LocateELem(L,e)

8. 在线性表L中插入一个数据元素 ListInsert(L,i,e) 9. 删除线性表L中第i个数据元素 ListDelete(L,i,e)

1. 初始化线性表L InitList(L)

Status InitList_Sq(SqList *L) //构造一个空的顺序表L {

L-> elem=new ElemType[MAXSIZE]; //为顺序表分配空间 if(! L-> elem) exit(OVERFLOW); //存储分配失败 L-> length=0; //空表长度为0

第二章

3. 头指针：指向整个链表首地址的指针，标示着整个单链表的开始。

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

#define OK 1

#define ERROR 0

Int 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; } }

7.（1）void reverse(SeqList L)

{

int i,j,tmp;

for(i=0, j=L.last; i

前五章习题算法

2.2

算法设计题

1.设计一个算法从一给定的有序顺序表L中删除元素值在X到Y(X<=Y)之间的所有元素,要求以较高的效率实现,要求算法的空间复杂度为O(1) void delete(SqList &L,ElemType x,ElemType y) {

int i=0,k=0;

while(i=x &&L.elem[i]

L.length=L.length-k; }

2设一个有序表L,含有2n个整数,其中n个位负数,n个为正数,设计一个算法将L中所有元素按正负相间排列. 要求算法的空间复杂度为O(1),时间复杂度为O(n) void move(SqList &L) {

int i=0,j=L.length-1; int temp;

while(i0)i++; while(i

while(i

} }

3.假设一两个元素依之=值递增有序排列的线性表A和B分别表示两个集合(同一 元素值各不相同),要求分别设计求A和B交并差集的算法,要求结果线形表中的元素依值递增有序排列,试对顺序表实现上述操作. 交集:

void intersection(SqList A,SqList B ,SqList &C) {

int i=0,j=0,k=0;

while(iB.elem[j]) j++; else { C.elem[k]=A.elem[i]; k++;i++;j++;} //共同

习题一

一、单项选择题

1．数据结构是一门研究非数值计算的程序设计问题中计算机的 ① 以及它们之间的 ② 和运算等的学科。

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

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

A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D. 内部结构和外部结构

4．算法分析的目的是 ① ，算法分析的两个主要方面是 ② 。

① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 ② A. 空间复杂度和时间复杂度 B. 正确性和简单性

C. 可读性和文档性 D. 数据复杂性和程序复