数据结构作业

数据结构习题

第一章 绪论

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

习题一

一、单项选择题

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

校园导游资讯系统

课 程 设 计 说 明 书

课程名称： 数据结构与算法 设计题目： 院 系： 计算机科学与信息工程学院 学生姓名： 丁守亮 学 号： 专业班级：指导教师： 闫怀平

2012年 6 月 15

日

校园导游资讯系统

课 程 设 计 任 务 书

校园导游资讯系统

(6)建立校园景点平面图； (7)对(2)(3)(4)(5)(6)功能函数调用函数。 、 、 、 、 其他方面： (1) 对编写完成的程序进行上机调试； (2) 运行程序； (3) 对运行结果进行分析； (4) 撰写课程设计说明书 (5) 完成设计答辩。 参考文献阅读：[1] 严蔚敏、吴伟民.据结构(c 语言版).北京：清华大学出版社.2009 [2] 谭浩强.C 程序设计(第四版).北京：清华大学出版社.2010 [3] 严蔚敏、吴伟民.据结构题集.北京：清华大学出版社.2009

工作计划：本次课程设计时间为 2011—2012 学年度第二学期的第 17、18 周 1、第一周的第一天：小组布置设计题目；说明进度安排。 2、第一周的第二天：小组审题，查阅资料，进行设计前的必要资料准备。 3、第一周的第

第一章作业 一、选择题

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. 广义表

一、选择题

1. 在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有 （ ） 个

前驱结点；最后一个结点没有后继结点，其余每个结点有且只有（ ）个后继结点。

A. 1 , 1 B. 1 , 2

C. 2 , 1

D. 2 , 2

2. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址___。

A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 连续或不连续都可以

3. 指针变量p指向单链表中的结点，若该结点是链表的尾结点，下面正确的说

法是( )。

A. p->next = = NULL B. p->next != NULL C. p = =NULL

D. p->next->next = =NULL

4. 设指针p所指结点不是单链表的尾结点，删除p所指结点的后继结点的操作

是（ ）。

A. p->next=p->next->next; delete p; delet p->next;

C. p->next=p-next->next; delet p->next; D. q=p->nex

数据结构

1

1.为解决计算机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。（全国统考2009） A．栈 B．队列 C．树 D．图

2.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后入队Q，若出队序列为e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是（ ）。（全国统考2009）

A．1 B．2 C．3 D．4

3.若元素abcdef依次进栈，允许进栈、出栈交替进行，不允许连续三次进行出栈操作，则不可能得到的出栈序列是（ ）。（全国统考2010）

A．dcebfa B．cbdaef C．dbcaef D．afedcb 4.某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的顺序是（ ）。（全国统考2010） A．bacde B．dbace C．dbcae D．ecbad

5.元素abcde依次进入初

数据结构

第8章 查找

第8章 查找8.1 查找的基本概念 8.2 静态查找表 8.3 动态查找表 8.4 哈希表

数据结构

第8章 查找

8.1 查找的基本概念关键字：数据元素的某个数据项的值，用它可以标识列表 中的一个或一组数据元素。如果一个关键字可以唯一标识列表 中的一个数据元素， 则称其为主关键字，否则为次关键字。

当数据元素仅有一个数据项时， 数据元素的值就是关键字。

数据结构

第8章 查找

查找：根据给定的关键字值，在查找表中确定一个其关键 字与给定值相同的数据元素，并返回该数据元素在查找表中的 位置。若找到相应的数据元素，则称查找是成功的，否则称查

找是失败的，此时应返回空地址及失败信息，并可根据要求插入这个不存在的数据元素。

数据结构

第8章 查找

8.2 静态查找表8.2.1 顺序查找法顺序查找法的过程是：从表中最后一个记录开始，逐个进 行记录的关键字和给定值的比较，若某个记录的关键字和给定 值比较相等，则查找成功，否则查找失败。存储结构通常为顺 序结构，也可为链式结构。

数据结构

第8章 查找

//静态查找表的顺序存储结构 typedef struct { ElemType *elem; //数据元素存储空间基址，建 //表时按实际长度分配，0号单

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

姓名： 年级：

陈翠 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