数据结构与算法作业(1)答案

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

姓名： 年级：

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

校园导游资讯系统

课 程 设 计 说 明 书

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

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、第一周的第

2.3 课后习题解答 2.3.2 判断题

1．线性表的逻辑顺序与存储顺序总是一致的。（×） 2．顺序存储的线性表可以按序号随机存取。（√）

3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。（×）

4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。（√）

5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（×）

6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（√）

7．线性表的链式存储结构优于顺序存储结构。（×）

8．在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。（√）

9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（√）

10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（×）

11．静态链表既有顺序存储的优点，又有动态链表的优点。所以它存取表中第i个元素的时间与i无关。（×）

12．线性表的特点是每个元素都有一个前驱和一个后继。（×）

2.3.3 算法设计题

1．设线性表存放在向量A[arrsize]的前

1. Fill the blank with correct C++ codes:

(1) Given an array storing integers ordered by distinct value without duplicate, modify the binary

search routines to return the position of the integer with the smallest value greater than K when K itself does not appear in the array. Return ERROR if the greatest value in the array is less than K: (12 scores)

// Return position of smallest element >= K int newbinary(int array[], int n, int K) { int l = -1;

int r = n; // l and r beyond array bounds while (l+1 !=

第一章 数据结构与算法

1.1.1 算法的基本概念

算法是指解题方案的准确而完整的描述。是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。 对于一个问题，如果可以通过一个计算机程序，在有限的存储空间内运行有限长的时间而得到正确的结果，则称这个问题是算法可解的。但算法不等于程序，也不等于计算方法。 程序的编制不可能优于算法的设计。 1．算法的基本特征

(1)可行性：算法中要执行的每一个步骤都可以在有限时间内完成，且正确，否则是不会得到满意结果的。

N=-10;

for( k=1;k<=n;k++ )

c=c+1;

(2)确定性：算法的确定性，是指算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。

X=a·b/c·d X=a·b/(c·d) X=a·(b/c)·d

(3)有穷性：算法的有穷性，是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。

算法的有穷性还应包括合理的执行时间的含义。 for( k=1;k<=n;k++ ) c=c+1;

下例是无限循环：

for( k=1;k<=-10;k++ ) c=c+1;

(4)拥有足够的情报：一个算法是否有效，还取决于为算法所提供的情报是否足够。 2，算法的基本要素

北理工《数据结构与算法》在线作业 试卷总分:100 得分:100 一、 单选题

1. 在数据结构中，与所使用的计算机无关的是数据的()结构 A. 逻辑 B. 存储

C. 逻辑和存储 D. 物理 正确答案:A

2.一个n*n对称矩阵，如果以行或列为主序存入内存，则其容量为()。 A. n*n B. n*n/2

C. n*（n+1）/2

D. （n+1）*（n+1）/2 正确答案:C

3.一个数组第一个元素的存储地址是100，每个数组元素的长度为2，则第5个元素的地址是()。 A. 110 B. 108 C. 100 D. 120 正确答案:B

4.如果结点a有三个兄弟，而且b为a的双亲，则b的度为()。 A. 3 B. 4 C. 5 D. 2

正确答案:B

5. 下面四种内排序方法中，要求容量最大的是()。 A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序 正确答案:D

6. 采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为()。 A. n B. n/2

C. （n-1）/2 D. （n+1）/2 正确答案:D

7. 图的存储结构不包括() A. 数组表示 B. 邻接表 C. 邻接多重表

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

姓名： 年级：

2014春

学 号： 学习中心：

7141 华家池

————————————————————————————— 一、填空题：

【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+=10 * i; // 语句的频度是________n-1______________。 }

北航《算法与数据结构》在线作业一 单选题

一、单选题（共 25 道试题，共 100 分。）

1. 排序方法中,从未排序序列中依次取出元素与己排序序列(初始时为空)中的元素进行比较,将其放入己排序序列的正确位置上的方法,称为（） A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序

-----------------选择：C

2. 设有1000个无序的元素,希望用最快的速度挑选出其中前10个最大的元素,最好（）排序法。

A. 起泡排序 B. 快速排序 C. 堆排序 D. 基数排序

-----------------选择：B 3. 以下说法正确的是 ( )

A. 因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况 B. 因顺序栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况 C. 对于链栈而言,在栈满状态下,如果此时再作进栈运算，则会发生“上溢” D. 对于顺序栈而言在栈满状态下如果此时再作迸栈运算，则会发生“下溢”。 -----------------选择：A

4. 对于数据结构课程的主要内容，以下解释正确的是

A. 数据结构的定义，包括逻辑结

在线作业自动判卷20171119 题目 评价排序算法好坏的标准主要是（ ）。 已知一栈的进栈序列为：1234，则下列序列中不可能的出栈序列是（ ）。 在数据结构中，与所使用的计算机无关的是数据的（ ）结构 在线性表顺序存储结构下，在第i个元素之前插入新元素一般需要( ) 线性表的顺序存储结构是一种（ ）的存储结构。 以下关于线性表的说法不正确的是（ ）。 队列是一种（ ）。 在表达式求值算法中，需要用几个栈？ 队列的操作特点是（ ）。 下列不属于栈基本运算的是（ ）。 类型 单选题 单选题 单选题 单选题 单选题 单选题 单选题 单选题 单选题 单选题 分值 10.0 10.0 10.0 10.0 10.0 10.0 10.0 10.0 10.0 10.0 正确答案 你的答案 4 4 1 1 1 3 1 3 1 2 批改 × × × × × × × × × × 本次作业总分值:100.0 得分:0.0 正确的题数：0 题目总数：10 正确率:0.0% 在线作业自动判卷 题目 在数据结构中，与所使用的计算机无关的是数据的（ ）结构 学习

A 装箱问题模拟（20）

源码：

#include #include using namespace std;

char box[1010];

int main() {

memset(box,100,sizeof(box)); int N; int t;

int num=0; cin>>N;

int temp = N; while(temp--) {

cin>>t;

for (int i=0;i

int a = box[i]; if (a>=t) {

if (a==100) num++;

box[i] -=t;

cout<

cout<

//system(\ return 0; }

B 表达式转换（25）

源码：

#include #include #include using namespace std;

stack sta;

int main() {

string s;

string anwser; cin>>s;

int i;

bool n