数据结构形考作业2答案

1.数据结构形考选择题

2.把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（ B ）。

a)A．逻辑结构 B．物理结构

b)C．算法的具体实现 D．给相关变量分配存储单元

3.下列说法中，不正确的是（ D ）。

A．数据元素是数据的基本单位

B．数据项是数据中不可分割的最小可标识单位

C．数据可有若干个数据元素构成

D．数据项可由若干个数据元素构成

4.一个存储结点存储一个（ B ）。

a)A．数据项 B．数据元素

b)C．数据结构 D．数据类型

5.数据结构中，与所使用的计算机无关的是数据的（ C ）。

a)A．存储结构 B．物理结构

b)C．逻辑结构 D．物理和存储结构

6.下列的叙述中，不属于算法特性的是（D ）。

a)A．有穷性 B．输入性

b)C．可行性 D．可读性

7.算法分析的目的是（C ）。

a)A．找出数据结构的合理性 B．研究算法中的输入和输出的关系

b)C．分析算法的效率以求改进 D．分析算法的易懂性和文档性

8.

第二章

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

习题一

一、单项选择题

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. 数据复杂性和程序复

第二学期“数据结构”考试试题（A）

姓名

学号(序号)_ 班号

要求：所有的题目的解答均写在答题纸上（每张答题纸上要写清楚姓名、班号和学号），需写清楚题目的序号。每张答题纸都要写上姓名和序号。

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

1．数据的运算a 。

A.效率与采用何种存储结构有关 B.是根据存储结构来定义的 C.有算术运算和关系运算两大类 D.必须用程序设计语言来描述 2. 链表不具备的特点是 a 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C.不必事先估计存储空间 D.所需空间与其长度成正比 3. 在顺序表中删除一个元素的时间复杂度为 c 。

A.O(1) B.O(log2n) C.O(n) D.O(n2)

4．以下线性表的存储结构中具有随机存取功能的是 d 。 A. 不带头结点的单链表 B. 带头结点的单链表 C. 循环双链表 D. 顺序表 。

5. 一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是 c 。 A.edcba

第二学期“数据结构”考试试题（A）

姓名

学号(序号)_ 班号

要求：所有的题目的解答均写在答题纸上（每张答题纸上要写清楚姓名、班号和学号），需写清楚题目的序号。每张答题纸都要写上姓名和序号。

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

1．数据的运算a 。

A.效率与采用何种存储结构有关 B.是根据存储结构来定义的 C.有算术运算和关系运算两大类 D.必须用程序设计语言来描述 2. 链表不具备的特点是 a 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C.不必事先估计存储空间 D.所需空间与其长度成正比 3. 在顺序表中删除一个元素的时间复杂度为 c 。

A.O(1) B.O(log2n) C.O(n) D.O(n2)

4．以下线性表的存储结构中具有随机存取功能的是 d 。 A. 不带头结点的单链表 B. 带头结点的单链表 C. 循环双链表 D. 顺序表 。

5. 一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是 c 。 A.edcba

数据结构习题

第一章 绪论

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

大工11秋《数据结构》在线作业2

一,单选题

1. difference(A,B,C)表示求集合A和B的差集C。若A={b,c,d},B={c,e},则difference(A,B,C)运算后C=( )。 A. {b,c,d,e} B. {c} C. {b,d} D. {b,c,c,d,e} 正确答案：C

2. 具有6个顶点的无向图至少应有（）条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 8 正确答案：A

3. min(A)，函数的返回值是集合A的所有元素中按线性序最小的那个元素。则min({2,3,4})=( ) A. 2

B. 3 C. 4 D. 0 正确答案：A

4. index(s,t)表示子串定位运算。若串t是串s的子串，则函数返回值是串t在串s中第一次出现的开始位置，否则返回值是0。若s=\则index(s,t)=( )。 A. 0 B. 1 C. 2 D. 3 正确答案：C

5. 在一棵二叉树上第5层的结点数最多为（）,设树根为第1层。 A. 16 B. 15 C. 8 D. 32 正确答案：A

6. intersection(A,B,C)表示求集合A和B的交集C。若A={b,c,d},B={c,e

一、绪论

a) 何谓程序设计？

程序=算法+数据结构 b) 数据结构的定义

是相互之间存在一种或多种特定关系的数据元素的集合 c) 数据、数据元素、数据对象的概念

数据：是对客观事物的符号表示 数据元素：是数据的基本单位

数据对象：是性质相同的数据元素的集合 d) 四种基本的数据结构类型

集合结构、线性结构、树型结构、图形结构 e) 两种存储结构（计算机中的实现方式）

顺序存储结构

特点：随机访问

优缺点：存取快，但插入元素复杂 适用情况：插入元素操作较多的情况 链式存储结构

特点：顺序访问

优缺点：访问元素麻烦，但是插入元素方便

适用情况：插入元素为主要操作而访问元素的操作较少

f) 数据类型、抽象数据类型

数据类型：用以刻画（程序）操作对象的特性

抽象数据类型：是指一个数学模型以及定义在该模型上的一组操作 g) 抽象数据类型的意义

ADT（abstract data type）着重数据结构的操作接口，不关心具体实现，主要是面向用户

ADT是数据结构设计所追求的目标 h) 何谓算法

算法是解决特定问题求解步骤的描述 i) 算法特征

①有穷性 ②确定性 ③可行性 ④输入 ⑤输出 j) 算法设计的要求

①正确性 ②可读性 ③健壮性 ④效率与低

浙江大学远程教育学院 《数据结构与算法》课程离线作业

姓名： 年级：

陈翠 2013秋

学 号： 学习中心：

713009014001 金华学习中心

————————————————————————————— 一、填空题：（【序号，章，节】。。。。。。）

【1，1，2】线性结构中元素之间存在一对一关系，树形结构中元素之间存在 一对多 关系，图形结构中元素之间存在 多对多 关系。

【2，1，2】为了最快地存取数据元素，物理结构宜采用 顺序存储 结构。

【3，1，2】存储结构可根据数据元素在机器中的位置是否一定连续分为 顺序存储结构___， 链式存储结构___。

【4，1，3】度量算法效率可通过 时间复杂度___来进行。

【5，1，3】设n 为正整数，下面程序段中前置以记号@的语句的频度是 n(n+1)/2 。

for (i=0; i

@ a[i][j]=0; }

【6，1，3】设n 为正整数，试确定下列各程序段中前置以记号@的语句的频度: (1) i=1; k=0;

while (i<=n-1){ i++;

@ k+=1