博文
02_抽象数据类型的表示和实现(2006-08-15 21:07:00)
摘要：第二课
本课主题： 抽象数据类型的表示与实现
教学目的： 了解抽象数据类型的定义、表示和实现方法
教学重点： 抽象数据类型表示法、类C语言语法
教学难点： 抽象数据类型表示法
授课内容：
一、抽象数据类型定义（ADT）
作用：抽象数据类型可以使我们更容易描述现实世界。例：用线性表描述学生成绩表，用树或图描述遗传关系。
定义：一个数学模型以及定义在该模型上的一组操作。
关键：使用它的人可以只关心它的逻辑特征，不需要了解它的存储方式。定义它的人同样不必要关心它如何存储。
例：线性表这样的抽象数据类型，其数学模型是：数据元素的集合，该集合内的元素有这样的关系：除第一个和最后一个外，每个元素有唯一的前趋和唯一的后继。可以有这样一些操作：插入一个元素、删除一个元素等。
抽象数据类型分类
原子类型
值不可分解，如int
固定聚合类型
值由确定数目的成分按某种结构组成，如复数
可变聚合类型
值的成分数目不确定如学生基本情况
抽象数据类型表示法：
一、
三元组表示：（D，S，P）
其中D是数据对象，S是D上的关系集，P是对D的基本操作集。
二、书中的定义格式：
ADT 抽象数据类型名{
数据对象：<数据对象的定义>
数据关系：<数据关系的定义>
基本操作：<基本操作的定义>
}ADT 抽象数据类型名
例：线性表的表示
名称
线性表
数据对象
D={ai| ai(-ElemSet,i=1,2,...,n,n>=0}
任意数据元素的集合
数据关系
R1={<ai-1,ai>| ai-1,ai(- D,i=2,...,n}
除第一个和最后一个外，每个元素有唯一的直接前趋和唯一的直接后继
基本操作
ListInsert(&L,i,e)
L为线性表，i为位置，e为数据元素。
ListDelete(&L,i,e)
...
二、类C语言语法
类C语言语法示例
1、预定义常量和类型
#define TRUE 1
#define FAL......
01_数据结构及基本概念(2006-08-15 21:05:00)
摘要：转自（http://www.cstudyhome.com/datastruct1/class01/class01.htm）
第一课
本课主题：数据结构的基本概念和术语
教学目的：了解数据结构的基本概念，理解常用术语
教学重点：基本概念：数据与数据元素
教学难点：数据元素间的四种结构关系。
授课内容：
一、数据、数据元素、数据对象、数据结构的定义
1、数据的定义
定义一：数据是客观事物的符号表示。
学号
姓名
语文
数学
C语言
6201001
张三
85
54
92
6201002
李四
92
84
64
6201003
王五
87
74
73
6201004
...
例：张三的C语言考试成绩为92分，92就是该同学的成绩数据。
定义二：能输入到计算机中并被计算机程序处理的符号的总称。
例：图像、声音等。
总结：现实世界信息的分析、复制、传播首先要符号化，这样才便于处理，尤其是便于计算机的处理。家长、社会要了解一个学生的学习成绩和能力，要看他的学习档案，而学习档案即是说明该学生学习情况的数据。
2、数据元素、数据项
数据元素是数据的基本单位，它也可以再由不可分割的数据项组成。如图示：
3、数据对象
是性质相同的数据元素的集合。如上例：一个班级的成绩表可以看作一个数据对象。
4、数据结构
定义一、数据元素集合（也可称数据对象）中各元素的关系。
定义二、相互之间存在特定关系的数据元素集合。
数据结构的种类：
特征
示例
集合
元素间为松散的关系
线性结构
元素间为严格的一对一关系
如上面的成绩表中各元素
树形结构
元素间为严格的一对多关系
图状结构（或网状结构）
元素间为多对多关系
数据结构的形式定义：
数据结构名称=（D，S）
其中D为数据元素的有限集，S是D上关系的......
二级C程序修改举例~(2006-08-15 11:55:00)
摘要： 二级C程序修改1
试题说明 :
给定程序MODI1.C中函数 fun 的功能是：将在字符串s中出现、
而未在字符串t中出现的字符形成一个新的字符串放在u中，u中字
符按原字符串中字符顺序排列，不去掉重复字符。
例如：当s = "AABCDE"，t = "BDFG"时，
u中的字符串为"AACE"。
请改正函数fun中的错误，使它能得出正确的结果。注意：不
要改动main函数，不得增行或删行，也不得更改程序的结构！
===============================================================================
程序 :
#include
#include
#include
/************found************/
void fun (char *s, char *t, char u)
{ int i, j, sl, tl;
sl = strlen(s); tl = strlen(t);
for (i=0; i { for (j=0; j if (s[i] == t[j]) break;
/************found************/
if (j>tl)
*u++ = s[i];
}
*u = '\0';
)
main()
{ char s[100], t[100], u[100];
clrscr();
printf("\nPlease enter string s:"); scanf("%s", s);
printf("\nPlease enter string t:"); scanf("%s", t);
fun(s, t, u);
printf("the result is: %s\n", u);
}
所需数据 :
#2
@1 001010 ......
04年4月二级C笔试题(2006-08-15 11:51:00)
摘要： 一、 选择题（（1）~（40）每题1分，（41）~（50）每题2分，共60分）
1、 1MB等于（D）
A)1000字节 B)1024字节 C)1000*1000字节 D)1024*1024字节
2、与十六进制数200等值得十进制数为（B）
A)256 B)512 C)1024 D)2048
3、 所谓"裸机"是指（C）
A)单片机 B)单板机 C)不装备任何软件的计算机 D)只装备操作系统的计算机
4、 能将高级语言编写的源程序转换为目标程序的是（C）
A)链接程序 B)解释程序 C)编译程序 D)编辑程序
5、 在64为计算机中，一个字长所占字节数为（B）
A)64 B)8 C)4 D)1
6、 在Windows环境下，当一个应用程序窗口被最小化后，该应用程序（A）
A)继续在后台运行 B)继续在前台运行
C)终止运行 D)暂停运行
7、在Windows环境下，能实现窗口移动的操作是（D）
A)用鼠标拖动窗口中的任何部位 B)用鼠标拖动窗口的边框
C)用鼠标拖动窗口的控制按钮 D)用鼠标......
C语言基础知识(2006-08-15 11:37:00)
摘要： 常量和变量
1.常 量: 程序执行过程中,值不变的量。 3 ，'a'
变 量：值可以改变的量。
一个变量有一个名字，在内存中有一定的存储单元，存放变量的值。
2.常量类型：
a.整 型：12，0，-3
b.实 型：4.6,-1.2
c.字 符 型: 'a','d'
d.符号常量: #define PRICE 30 (PRICE不能再被赋值且要大写)
3.变 量: 先定义,后使用。一个变量只能被指定为一确定类型。
4.标识符：标识变量名，符号常量名，函数名，数组名，类型名，文件名的有效字符数列。
a.由字母、数字、下划线三种字符组成，第一个字符必须为字母或下划线。
b.大写字母、小写字母被认为是两个不同的字符。
c.长度一般小于8个。
数据类型
一.整 型:
1.整型常量
a.十 进 制:12,-3,0
b.八 进 制:以0开头。
c.十六进制:以0x开头。
2.整型变量
a. int -32768——32767
b. short int -32768——32767
c. long int
d. unsigned int 0——65535
......
05年计算机考试二级C之填空题(2006-08-15 11:34:00)
摘要：填空题（每空2分，共40分）
（1）某二*树中，度为2的结点有18个，则该二*树中有 19 个叶子结点。
（2）在面向对象的方法中，类的实例称为 对象 。
（3）诊断和改正程序中错误的工作通常称为 程序调试 。
（4）在关系数据库中，把数据表示成二维表，每一个二维表称为 关系 。
（5）问题处理方案的正确而完整的描述称为 算法 .
（6）以下程序运行时若从键盘输入：10 20 30<回车>。输出结果是 10 30 0 .
#include <stdio.h>
main()
{ int i=0,j=0,k=0;
scanf("%d%*d%d",&i,&j,&k);
printf("%d%d%d\n",i,j,k);
}
(7)以下程序运行后的输出结果是 81 .
#define S(x) 4*x*x 1
main()
{
int i=6,j=8;
printf("%d\n",S(i j));
}
(8)以下程序运行后的输出结果是 4599
main()
{
int a=3,b=4,c=5,t=99;
if(b<a&&a<c) t=a;a=c;c=t;
if(a<c&&b<c) t=b;b=a;a=t;
printf("%d%d%d\n",a,b,c);
}
(9)以下程序运行后的输出结果是 10 20 0
main()
{
int a,b,c
a=10;b=20;c=(a%b<1)||(a/b>1);
printf("%d %d %d\n",a,b,c);
}
(10)以下程序运行后的输出结果是0918273645
main()
{
char c1,c2;
for(c1='0',c2='9';c1<c2;c1 ,c2--)
printf("%c%c",c1,c2);
printf("\n");
}
(11)已知字符A......
05年计算机考试二级C之选择题(2006-08-15 11:32:00)
摘要：一、选择题（（1）-（10）每小题2分，（11）-（50）每小题1分，共60分）
下列各题A）、B）、C）、D）四个选项中，只有一个选项是正确的。请将正确选项真涂在答题卡相应位置上，答在试卷上不得分。
（1）数据的存储结构是指 D
A）存储在外存中的数据
B）数据所占的存储空间量
C）数据在计算机中的顺序存储方式
D）数据的逻辑结构中计算机中的表示
（2）下列关于栈的描述中错误的是 B
A）栈是先进后出的线性表
B）栈只能顺序存储
C）栈具有记忆作用
D）对栈的插入与删除操作中，不需要改变栈底指针
（3）对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是 D
A）冒泡排序为n/2
B）冒泡排序为n
C）快速排序为n
D）快速排序为n(n-1)/2
(4)对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为 C
A）log2n
B) n/2
C) n
D) n 1
(5)下列对于线性链表的描述中正确的是 A
A）存储空间不一定是连续，且各元素的存储顺序是任意的
B）存储空间不一定是连续，且前件元素一定存储在后件元素的前面
C）存储空间必须连续，且前件元素一定存储在后件元素的前面
D）存储空间必须连续，且各元素的存储顺序是任意的
（6）下列对于软件的描述中正确的是 C
A）软件测试的目的是证明程序是否正确
B）软件测试的目的是使程序运行结果正确
C）软件测试的目的是尽可能多地发现程序中的错误
D）软件测试的目的是使程序符合结构化原则
（7）为了使模块尽可能独立，要求 B
A）模块的内聚程序要尽量高，且各模块间的耦合程序要尽量强
B）模块的内聚程序要尽量高，且各模块间的耦合程序要尽量弱
C）模块的内聚程序要尽量低，且各模块间的耦合程序要尽量弱
D）模块的内聚程序要尽量低，且各模块间的耦合程序要尽量强
（8）下列描述中正确的是 D
A）程序就是软件
B）软件开发不受计算机系统的限制
C）软件既是逻辑实体......
如何备战NOIP?（转帖）(2006-08-10 10:14:00)
摘要：如何备战NOIP?
想一想，这些问题本身也许就可以引起你的思考。选出你认为最重要的，你又最差的方面集中训练。
1.你参加过复赛吗?
2.你做过以前的竞赛题吗？(没有做过就在本站下载一份去做嘛！)
3.你知道复赛如何评分吗？
4.在算法十分熟悉的情况下，你平均输入100行代码需要多少时间？
5.你对那类题目最有把握？
6.你对那类题目最头痛？
7.程序编完后，调试成功需要的时间平均是编程时间的几分之几？
8.你满以为正确的程序，结果测试下来有错误的情况有多少？
9.你满以为正确的程序，结果测试下来几乎得0分的情况有多少？
10.你看完题目（包括验证样例数据）的平均时间是多少？
11.从看完题目到脑子里浮现出第一个算法的平均时间是多少？
12.从看完题目到最后决定采用哪种算法的平均时间是多少？
13.从决定算法到开始编码，你会先在做准备工作(eg.写伪代码)吗？需要多少时间？
14.在实现算法的时候突然发现算法是错误的，这种情况有多少？
15.程序编完后测试一些数据后发现算法是错误的，这种情况有多少？
16.程序写着写着写不下去了,因为觉得代码还需要写那么那么多...这种情况有多少？
17.程序写着写着写不下去了,因为不知道下一步该写什么了，这种情况有多少？
18.程序写着写着写不下去了,因为刚刚写过的代码突然看不懂了，这种情况有多少？
19.程序写完了，运行失败，你先静态查错，还是直接调试？
20.调试通一个100行代码的程序，你用的时间平均是多少？
21.调试了一段时间，仍然通不过，不知道该怎么办，这种情况有多少？
22.调试了半天，终于找到错误了。但竟发现是笔误！这种情况是多少？
23.对于竞赛题，你有把握同时通过的程序有几分之几？这种“把握”通常是正确的吗？
24.你测试程序吗？是否只是使用样例数据？
25.测试时死机。这种情况有多少？
26.测试大数据时才发现你的程序效率存在严重问题，这种情况有多少？
27.测试大数据时才发现你的程序空间问题没有解决好，这种情况有多少？
28.测试一个数据失败，调试通以后你是否进行回归测试？
29.一般的题目你会花多少时间测试？
30.做一道简......
NOIP初赛谈（转帖）(2006-08-10 09:43:00)
摘要：NOIP初赛谈
Ø 知识是基础，能力最重要
NOIP初赛考的知识点，大纲上有3块：计算机基本常识、计算机基本操作、程序设计基本知识。具体来说：选择题考查的是计算机基本常识、基本操作和程序设计中的一些基本数据结构与基本算法；而填空题更加重视能力（尤其是队列、栈、二叉树等数据结构、数学问题、归纳法、数列和逻辑推理等）的考查；读程序写运行结果考察的是对程序的理解和跟踪，重在分析推理能力。读程序的4条题目往往有一定的层次，试卷中给出程序的并不复杂，语句的含义容易明白，但是悟性好的选手总是很快就能体会到程序的设计思路并得出正确的答案，机械模仿计算机手工逐步算出结果的同学往往做的很慢，造成时间不够，而且容易失误；完善程序更是考察程序设计能力，尤其是在明确算法和数据结构的条件下，如何编程。读程序和完善程序，需要在平时的学习中提高，经常阅读、讨论和研究别人的优秀程序，提高自己的理解力和速度。
Ø 各种题型的解题经验（以2002、2001年试题为例）
选择题（30分=20*1.5）
一般是比较容易得分的，不可错过！
程序设计方面的知识多是平时计算机课堂教学或课外活动中学到的，建议大家找全国计算机等级考试（一、二级）的题目做做，一般不超过二级的知识点，知识要复习的系统一些。新大纲和最近两年的考试不再考DOS，但有DOS经验的选手可能会占一点便宜，因为有些题目可以根据经验判断。另外，往更高层次发展的过程中，必要的DOS知识和命令还是必须的。
Ø 分布：5-6个数据结构或算法方面的基本知识（高中组更多一些！！！）；
2002年初中组（16）：一个向量第一个元素的存储地址是100,每个元素的长度是2,则第5个元素的地址是( B )
A) 110 B) 108 C) 100 D) ......
NOIP初赛准备(转帖)(2006-08-10 09:33:00)
摘要： NOIP初赛准备
初赛考的知识点，大纲说：计算机基本常识，基本操作和程序设计基本知识。选择题考查的是知识，而问题解决题、填空更加重视能力的考查。
一般说来，选择题是不需要单独准备的 -- 也无从准备。只要多用心积累就可以了。到是问题解决题目比较固定，大家应当多作以前的题目。写运行结果需要多作题目，培养良好的程序阅读和分析能力，而完善程序最好总结一下以前题目常常要你填出来的语句类型。
1.选择题 一般它们是比较容易得分的，一共30分，不可错过！
近几年来，初赛的考查范围有了很大的变化，越来越紧跟潮流，需要大家有比较广泛的知识，包括计算机硬件，软件，网络，数据结构（例如栈，队列，排序算法），程序设计语言以及一些基本的数学知识和技巧（例如排列组合等）。
2.填空、问题解决
这部分题目对数学要求要高一点，往往考查的是代数变形，数列（一般是考递推），也考查 一些算法和数据结构知识。建议大家多花一点时间做，尽量做对。
3. 阅读程序写出运行结果
占的分数多，但得分率却不高，较易失分，一旦结果不正确，将丢失全分。
这种题型主要考察选手：
① 程序设计语言的掌握能力
② 数学运算能力
③ 耐心、细心的心理品质一般做这类题目的关键在于能够分析程序的结构及程序段的功能，找出程序目的，即这个程序想干什么。
完成这类题目的一般方法和步骤是：
① 从头到尾通读程序，大致掌握程序的算法；
② 通过给程序分段，清理程序的结构和层次，达到读懂程序的目的；
③ 阅读程序中特别注......