数据结构期末大作业

校园导游资讯系统

课 程 设 计 说 明 书

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

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

计算机科学与技术专业数据结构大作业

一、 实验内容概述

n个村庄之间的交通图用有向加权图表示，图中的有向边表示第i个村庄和第j个村庄之间有道路，边上的权表示这条道路的长度。现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院最近。

图1 医院选址加权有向图

测试数据：针对图1，输入以下数据： 输入顶点数： 5 输入顶点对和弧的权值：

1 2 1

2 3 2 3 4 2 3 5 4 4 2 1 4 3 3 5 4 5 0 0 0

1

计算机科学与技术专业数据结构大作业

二、 实验目的概述

“数据结构”是计算机科学与技术专业一门十分重要的专业技术基础课，计算机科学各领域及有关的应用软件都要使用到各种数据结构。在我国，“数据结构与算法”已经作为理工科非计算机专业必修的信息技术基础课程之一。世界上许多科技人员对学习、研究数据结构和算法都非常重视，对于从是计

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

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

每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

数据结构（本科）期末综合练习一（单选题）

单选题

1. 一个数组元素a[i] 与( )的表示等价。

A. *(a+i) B. a+i C. *a+i D. &a+i

2. 若需要利用形参直接访问实参，则应把形参变量说明为( )参数。 A. 指针 B. 引用 C. 传值 D. 常值

3. 下面程序段的时间复杂度为( )。 for(int i=0; i

for(int j=0; j

22

A. O(m) B. O(n) C. O(m*n) D. O(m+n)

4. 执行下面程序段时，执行S语句的次数为( )。 for(int i=1; i<=n; i++)

for(int j=1; j<=i; j++) S;

22

A. n B. n/2 C. n(n+1) D. n(n+1)/2

5. 下面算法的时间复杂度为( )。 int f(unsign

习题一

一、单项选择题

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

浙江大学宁波理工学院200_9_–2010_学年_二_学期

《数据结构（乙）》课程期末考试试卷（A）

开课分院： 信息分院 ，考试形式：开卷

考试日期：__ 2010___年__6__月__ 24__日，考试所需时间： 120 分钟

考生姓名 学号 考生所在分院： 专业班级： . 题序 题型 得分 评卷人 一 问答题 二 程序编写题 总 分 一、简答题（本大题共10小题，每小题2分，共60分）

1.设字符a,b,c,d,e,f,g的使用权值分别是15，5，36，2，22，12，8，画出Huffman树，并写出a,b,c,d,e,f,g的Huffman编码。（6分）

0371001015ae1022012f0702d15b2711518g63136c

2．已知二叉树的先序序列和中序序列分别为ABDHIEJKCFLMG和HDIBJEKALFMCG。（1）画出该二叉树；（2）画出（1）中求得的二叉树对应的森林。(10分)

命题（组）老师签名：____________________ 年 月 日

分院主管教学院长或首席主讲教授签名：___________

1. 数据的不可分割的基本单位是 ( A )。 A．元素 B．结点 C．数据类型 D．数据项 2. 计算机处理数据的最小单位是（ D ）。

A．元素 B．结点 C．数据类型 D．数据项 3. 算法是指 ( C )。

A．计算方法 B．排序方法 C．解决问题的有限运算步骤 D．查找方法

4. 顺序存储结构中数据元素之间的逻辑关系是由（ C ）表示的 A 线性结构 B 非线性结构 C 存储位置 D 指针 5. 单循环链表的主要优点是（ B ）。

A 不再需要头指针了 B 从表中任一结点出发都能扫描到整个链表； C 已知某个结点的位置后，能够容易找到它的直接前趋； D 在进行插入、删除操作时，能更好地保证链表不断开。

6. 一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是( C )。 A 54321 B 45321 C 43512 D 12345

此题的解决步骤是如果出现一个三元素顺序是a、b、c，且a>c>b,则为不可能序列 7. 常对数组进行的两种基本操作是( B ) A．建立和删除

B． 索引和修改

C．插入和修