下载文档原格式
青岛科技大学信息科学技术学院简介信息科学技术学院（网站）现有计算机科学与技术、信息工程、通信工程、集成电路设计与集成系统、软件工程、物联网工程6个本科专业，拥有计算机科学与技术和软件工程2个一级学科硕士点，软件工程和计算机技术2个专业硕士点。
信息工程专业和计算机科学与技术专业为山东省特色专业。
学院有省级、校级精品课程6门，校级优秀课程6门。
学院拥有山东省服务外包人才培训资质，由计算机基础实验中心、计算机软件技术实验中心、数字技术实验中心、通信技术实验中心以及大学生科技创新实验室等六大中心组建的计算机与信息通信教学实验中心为校级教学示范中心，建有信号与图像处理、现代通信技术、计算机软件与理论、计算机应用技术、计算机体系结构5个研究室。
计算机科学技术实验室为山东省首批骨干学科重点实验室，信息科学实验室为中央和地方共建实验室，学院还建有青岛市工业信息化重点实验室。
目前，学院在籍本专科生2000余人，研究生90余人。
现有教师112人，其中教授10人，副教授38人，具有博士学位37人，硕士生导师33人。
近几年，主持国家自然科学基金项目11项，省、市级以上纵向项目37项，企事业单位横向项目100余项，获市、省部级二等奖以上奖励8项。
在国内外发表论文700多篇，其中被SCI、EI 和ISTP收录300多篇，出版专著及教材10余部。
学院坚持“教学质量是生命线”和“以学生成才为本，促学生和谐发展”的教育教学理念，通过专业模块、导师制、校企合作、实习基地建设、实验室开放等，培养了一大批适应社会发展需要、具有创新精神的IT行业的工程型技术人才。
在“挑战杯”大学生课外学术科技作品大赛、“创青春”大学生创业大赛、齐鲁软件大赛、电子设计大赛等中获得一等奖7项。
学院在国际交流合作方面积极拓展，与美国休斯敦大学、韩国光云大学等多所国际一流大学建立起本科生和研究生交流互访及科研交流与合作项目。
面对新的发展时期和机遇，作为国家发展的7大新型产业之首的信息产业的支撑学科专业，在国家大力发展信息产业的大背景下，基于“CDIO”工程型教育理念，学院的学科建设和教育教学改革将全面贯彻学校的科学发展、内涵发展、特色发展、开放发展、创新发展的战略方针，坚持“校企融合、重点突破、特色发展、扩大影响”十六字方针，大力提升人才培养质量和教学科研水平，努力建成教学研究型名牌学院。
七（上）第1单元信息与信息技术第1课信息的特征第2课现代信息技术与生活第3课计算机探秘第4课使用计算机管理文件第5课信息安全与信息道德单元小结第2单元我的新学期第1课欢迎参加辩论会第2课为运动员加油第3课我心中的班级第4课文学社新成员第5课班级风采单元小结第3单元畅游齐鲁第1课策划准备第2课设计外观第3课组稿编辑（一）第4课组稿编辑（二）第5课播放展示与发布单元小结七（下）第1单元数据处理第1课数据计算第2课数据分析第3课数据的图表化第4课工作表的格式化与打印单元小结第2单元网络技术基础第1课计算机网络基础第2课互联网基础第3课互联网的基本服务第4课互联网的应用单元小结第3单元多媒体素材的采集与加工第1课亲密接触多媒体第2课图像处理(一)第3课图像处理(二)第4课图像处理(三)第5课音频采集与处理第6课视频采集与处理单元小结八（上）第1单元 网站设计与制作 第1课 创建站点第2课 设计网站首页 第3课 网页中的表格 第4课 网页的美化 第5课 建立超链接 第6课 网站的发布与维护 第7课 制作表单网页单元小结第2单元 FLASH 动画制作 第1课 认识FLASH MX 第2课 图层与元件 第3课 运动渐变动画 第4课 形状渐变动画 第5课 引导层动画 第7课 遮罩动画第8课 声音处理与作品发布 单元小结单元小结八（下）第1单元 算法思想初步 第1课 算法基础知识 第2课 利用E 语言程序解决 高斯问题第3课 E 语言程序设计基础 第4课 分支结构 第5课 循环结构 第6课 枚举法第7课 算法的优化示例单元小结第2单元 VB 程序设计 第1课 大熊猫的两个愿望 第2课 自我介绍 第3课 谜语大擂台(一) 第4课 节约用水算水价 第5课 谜语大擂台(二) 第6课 会计小助理 第7课 欲与珠峰试比高第8课 我的媒体播放器单元小结单元小结九（上）第1单元感测技术第1课感测技术概述第2课感测技术的应用单元小结第2单元控制技术第1课控制技术概述第2课控制技术的应用单元小结第3单元通信技术第1课通信技术概述第2课通信技术的应用单元小结第4单元智能机器人第1课认识机器人第2课欢迎进入AS—MII的世界第3课 VJC1.5编程软件第4课让机器人动起来第5课让机器人走四边形第6课让机器人具有智能第7课程序的基本结构第8课高级编程第9课机器人比赛项目单元小结九（下）第1单元关注信息社会第1课走进信息世界第2课信息技术综述第3课审视信息社会单元小结第2单元把握未来际遇第1课信息的获取与分析第2课赢在网络时代第3课网络信息检索单元小结第3单元体验数码生活第1课计算机的奥妙第2课数据存储未来第3课信息资源检索第4课信息安全概论单元小结第4单元成就美好明天第1课文本信息加工第2课表格信息处理第3课多媒体信息集成单元小结。
七年级下册信息技术教案青岛版第一章：网络的基本概念与使用1.1 教学目标了解网络的基本概念，掌握网络的使用方法。
1.2 教学内容1. 网络的定义与分类2. 网络的使用方法1.3 教学步骤1. 讲解网络的定义与分类2. 演示网络的使用方法3. 学生实践操作1.4 教学评价通过学生实践操作，检查学生对网络的基本概念和使用方法的掌握程度。
第二章：信息的搜索与处理2.1 教学目标掌握信息搜索的方法，了解信息处理的基本技巧。
2.2 教学内容1. 信息搜索的方法2. 信息处理的基本技巧2.3 教学步骤1. 讲解信息搜索的方法2. 演示信息处理的基本技巧3. 学生实践操作2.4 教学评价通过学生实践操作，检查学生对信息搜索方法和信息处理技巧的掌握程度。
第三章：电子表格的使用3.1 教学目标掌握电子表格的基本操作，了解电子表格的应用。
3.2 教学内容1. 电子表格的基本操作2. 电子表格的应用3.3 教学步骤1. 讲解电子表格的基本操作2. 演示电子表格的应用3. 学生实践操作3.4 教学评价通过学生实践操作，检查学生对电子表格的基本操作和应用的掌握程度。
第四章：演示文稿的制作与展示4.1 教学目标掌握演示文稿的制作方法，能够进行有效的演示文稿展示。
4.2 教学内容1. 演示文稿的制作方法2. 演示文稿的展示技巧4.3 教学步骤1. 讲解演示文稿的制作方法2. 演示演示文稿的展示技巧3. 学生实践操作4.4 教学评价通过学生实践操作，检查学生对演示文稿的制作方法和展示技巧的掌握程度。
第五章：计算机的基本维护与安全5.1 教学目标了解计算机的基本维护方法，掌握计算机的基本安全知识。
5.2 教学内容1. 计算机的基本维护方法2. 计算机的基本安全知识5.3 教学步骤1. 讲解计算机的基本维护方法2. 演示计算机的基本安全知识3. 学生实践操作5.4 教学评价通过学生实践操作，检查学生对计算机的基本维护方法和基本安全知识的掌握程度。
青岛科技大学信息科学技术学院研究生学业奖学金评定细则为激励研究生勤奋学习、潜心科研、积极进取、勇于创新，在国家全面实行研究生教育收费制度的情况下更好地支持研究生顺利完成学业，根据《青岛科技大学研究生学业奖学金管理暂行办法》（青科大字【2014】27号）的要求和相关规定，结合我院的实际情况，特制定我院研究生学业奖学金评定细则。
一、评选对象2014年9月起入校的纳入全国研究生招生计划的全日制研究生（有固定工资收入的除外），具有中华人民共和国国籍。
二、奖励比例、标准学业奖学金分为新生奖学金和综合奖学金，第一学年评选新生奖学金，第二、三学年评选综合奖学金。
学院根据研究生学业成绩、科研成果、社会服务等因素，按照学校要求，确定研究生学业奖学金比例及奖励标准（见附件1），具体人数以研究生处分配名额为准。
三、评选基本条件研究生学业奖学金基本申请条件：热爱社会主义祖国，拥护中国共产党的领导；遵守宪法和法律，遵守学校规章制度；诚实守信，品学兼优；积极参与科学研究和社会实践。
研究生有以下情况之一者不得参加学业奖学金的评定：因考试作弊等违反校纪受到警告以上（包括警告）处分者；学术行为不端者；在科研工作及学习实践中，造成重大责任事故及损失者；参与非法组织及活动者；本学年有课程考试不及格者；未通过研究生中期考核者；未按时交纳学费者；延期毕业的研究生。
四、评选程序1.个人申请新生奖学金不需要申请，由学院研究生学业奖学金工作领导小组根据评审依据直接进行评审。
综合奖学金的评审，需要研究生根据学校、学院制定的具体评定细则，结合自己实际情况，填写研究生奖学金申请表。
导师应对申请者的年度学习成绩、科研状况及其综合表现给出评价意见，无导师意见者，视为无效申请。
2.学院评审成立信息学院研究生学业奖学金工作领导小组，负责研究生学业奖学金的具体评定过程。
学院研究生学业奖学金评定工作组成员人数为9人，组成原则：院长、党总支书记、分管研究生副院长和副书记、硕士生导师代表、研究生管理人员、学生代表组成。
青岛科技大学信息科学技术学院研究生国家奖学金评审实施细则(试行)根据学校关于开展2014年研究生国家奖学金评选工作的通知要求，特制定我院研究生国家奖学金评审实施细则。
一、评选基本条件（一）热爱社会主义祖国，拥护中国共产党的领导；（二）遵守宪法和法律，遵守学校规章制度；（三）诚实守信，学风严谨，道德品质优良；（四）学习态度端正，成绩优异，必修课平均成绩80分以上或排名在本学科10%之内，且所有修读课程未出现过不及格现象。
国家英语六级考试成绩425分以上（含425）；（五）科研成果突出，至少满足下列条件之一：1.在本学科或相近学科领域发表高水平的学术论文至少一篇；2.获得国家专利授权；3.在国际性、全国性学术、科技、文化竞赛中获得三等奖及以上奖励者。
以上科研成果均要求第一单位为青岛科技大学，研究生是第一作者；或其导师为第一作者，研究生为第二作者，其余无效。
4.在国家级出版社正式出版的专著、教材中承担主要编写任务，超过5万字以上。
（六）积极参与社会实践、科技创新、学术文化活动，表现优秀。
（七）研究生出现以下任一情况，不具备当年研究生国家奖学金评选资格：1.评选学年违反国家法律、校纪校规受到纪律处分者；2.评选学年有抄袭剽窃、弄虚作假等学术不端行为经查证属实的；3.评选学年因个人原因学籍状态处于休学或其他保留学籍情况的；4.修读年限超过3年的；5.当年毕业的研究生。
二、组织领导学院成立研究生国家奖学金评审委员会（11人），由学院院长任主任委员，研究生导师代表、行政管理人员代表、学生代表，负责学院研究生国家奖学金的申请组织、初步评审工作。
三、评审程序对符合获奖基本条件的学生，院研究生国家奖学金评审委员会将根据《关于开展2014年研究生国家奖学金评选工作的通知》的要求组织评审。
四、评审方法1、课程平均成绩的计算：学生必修课平均成绩（不含实践教学）。
2、评选按照科研情况综合得分排名。
科研情况根据“青岛科技大学研究生科研成果量化标准”计算得分。
智慧校园管理系统的设计与实现（凤祥一璐晴团队）徐长祥（青岛科技大学信息科学与技术学院，山东青岛崂山区，266061）摘要：在对大赛要求及现实情况进行深入分析的基础上，我们小组给出了一种综合应用物联网技术、串口通信技术、IIS+SQL server+ASP 开发环境、开发环境、B/S B/S 结构的智慧校园管理系统的设计方案，并进行了实现。
该系统实现了大赛要求的主要功能：允许用户通过PC 终端查询所有教室的实时使用情况，所有教室的实时使用情况，以及其他所需信息和服务以及其他所需信息和服务以及其他所需信息和服务（如我们小组设计的预定教室、（如我们小组设计的预定教室、（如我们小组设计的预定教室、自习找自习找座、教室寻人等功能）。
全面体现物联网的整体构架（一二三层皆予以实现）尤其实现了硬件设备与我们系统之间的连接、真正实现了教室实时使用情况信息的动态更新是该系统的主要特色。
关键词：物联网；智慧校园；RFID ；上位机；接口；RS232串口通信；实时更新1 引言初入科大，就感到了科大人对知识的渴望，就像科大的自习室，时常爆满，自习圣地图书馆根本难寻一席之地。
常常出现这种情况：一个人肩背很沉的书包，游走于教学楼之间，寻找一块自习之地，也常出现这种情况：好不容易在一教觅得一块宝地，不料刚坐一小时，成群的学生涌入教室，跟着是提着包的教授，上课铃一响，你只有两种无奈的选择：忍受“市井喧闹”，坚守阵地，或者一走了之。
于是，我们针对这个问题开发了这套系统，通过这个系统你可以网上预订教室、追踪定位寻人、查询青岛科技大学各个教室的使用情况，位寻人、查询青岛科技大学各个教室的使用情况，哪间有课，哪间有课，哪间有课，哪间没课，哪间下节课即将被哪间没课，哪间下节课即将被占用，哪间将一直空闲到深夜，哪间将一直空闲到深夜，甚至这套系统可以让你看到全科大的自习室占用率，甚至这套系统可以让你看到全科大的自习室占用率，甚至这套系统可以让你看到全科大的自习室占用率，图书馆图书馆的座位哪有空闲。
11/121 编译原理A信息科学技术学院 计算（答案写在答题纸上，写在试题纸上无效）一、简答题(50’)1(10’)计算机执行用高级语言编写的程序有哪些途径?它们之间的主要区别是什么?答：计算机执行用高级语言编写的程序主要途径有两种，即解释与编译。
像Basic 之类的语言，属于解释型的高级语言。
它们的特点是计算机并不事先对高级语言 进行全盘翻译，将其变为机器代码，而是每读入一条高级语句，就用解释器将其翻译为 一条机器代码，予以执行，然后再读入下一条高级语句，翻译为机器代码，再执行，如 此反复。
总而言之，是边翻译边执行。
像C ，Pascal 之类的语言，属于编译型的高级语言。
它们的特点是计算机事先对高级语言 进行全盘翻译，将其全部变为机器代码，再统一执行，即先翻译，后执行。
从速度上看， 编译型的高级语言比解释型的高级语言更快2(12’)有语言L={w|w ∈{0,1}+,并且w 中至少有两个1，又在任何两个1之间有偶数个0}，试构造接受该语言的DFA,并对其进行化简。
3(10’)分别构造表达式5+7×6-2+7×6的抽象语法树与DAG 图 4(10’).把下面的语句翻译成四元式序列while A<C and B<D doif A=1 thenC:=C+1elsewhile A ≤D doA:=A+25(8’).写一个文法，使其语言为L(G)={a n b m |2n>m ≥n ≥1}.二、应用题(50’)6(12’).对下面的文法G[S]:S->SaA|bB A->aB|c B->Bb|d1)消去该文法的左递归2)计算消除左递归后的文法的每个非终结符的FIRST 集和课程考试试题 学期学年 拟题学院（系）: 适 用 专 业:FOLLOW集3)判断文法是否为LL(1)文法；若是，请构造它的预测分析表。
7(8’).文法G[S]:S->bTc S->a T->R R->R/S R->S,其中S为开始符号。
第九章查找本章中介绍下列主要内容：静态查找表及查找算法：顺序查找、折半查找动态查找表及查找算法：二叉排序树哈希表及查找算法第一节基本概念查找表用于查找的数据元素集合称为查找表。
查找表由同一类型的数据元素（或记录）构成。
静态查找表若只对查找表进行如下两种操作：（1）在查找表中查看某个特定的数据元素是否在查找表中，（2）检索某个特定元素的各种属性，则称这类查找表为静态查找表。
静态查找表在查找过程中查找表本身不发生变化。
对静态查找表进行的查找操作称为静态查找。
动态查找表若在查找过程中可以将查找表中不存在的数据元素插入，或者从查找表中删除某个数据元素，则称这类查找表为动态查找表。
动态查找表在查找过程中查找表可能会发生变化。
对动态查找表进行的查找操作称为动态查找。
关键字是数据元素中的某个数据项。
唯一能标识数据元素（或记录）的关键字，即每个元素的关键字值互不相同，我们称这种关键字为主关键字；若查找表中某些元素的关键字值相同，称这种关键字为次关键字。
例如，银行帐户中的帐号是主关键字，而姓名是次关键字。
查找在数据元素集合中查找满足某种条件的数据元素的过程称为查找。
最简单且最常用的查找条件是"关键字值等于某个给定值"，在查找表搜索关键字等于给定值的数据元素（或记录）。
若表中存在这样的记录，则称查找成功，此时的查找结果应给出找到记录的全部信息或指示找到记录的存储位置；若表中不存在关键字等于给定值的记录，则称查找不成功，此时查找的结果可以给出一个空记录或空指针。
若按主关键字查找，查找结果是唯一的；若按次关键字查找，结果可能是多个记录，即结果可能不唯一。
查找表的存储结构查找表是一种非常灵活的数据结构，对于不同的存储结构，其查找方法不同。
为了提高查找速度，有时会采用一些特殊的存储结构。
本章将介绍以线性结构、树型结构及哈希表结构为存储结构的各种查找算法。
查找算法的时间效率查找过程的主要操作是关键字的比较，所以通常以"平均比较次数"来衡量查找算法的时间效率。
（信息技术）第九章查找欢迎光临青岛科技大学信息科学技术学院第九章查找本章中介绍下列主要内容：静态查找表及查找算法：顺序查找、折半查找动态查找表及查找算法：二叉排序树哈希表及查找算法第壹节基本概念查找表用于查找的数据元素集合称为查找表。
查找表由同壹类型的数据元素（或记录）构成。
静态查找表若只对查找表进行如下俩种操作：（1）于查找表中查见某个特定的数据元素是否于查找表中，（2）检索某个特定元素的各种属性，则称这类查找表为静态查找表。
静态查找表于查找过程中查找表本身不发生变化。
对静态查找表进行的查找操作称为静态查找。
动态查找表若于查找过程中能够将查找表中不存于的数据元素插入，或者从查找表中删除某个数据元素，则称这类查找表为动态查找表。
动态查找表于查找过程中查找表可能会发生变化。
对动态查找表进行的查找操作称为动态查找。
关键字是数据元素中的某个数据项。
唯壹能标识数据元素（或记录）的关键字，即每个元素的关键字值互不相同，我们称这种关键字为主关键字；若查找表中某些元素的关键字值相同，称这种关键字为次关键字。
例如，银行帐户中的帐号是主关键字，而姓名是次关键字。
查找于数据元素集合中查找满足某种条件的数据元素的过程称为查找。
最简单且最常用的查找条件是"关键字值等于某个给定值"，于查找表搜索关键字等于给定值的数据元素（或记录）。
若表中存于这样的记录，则称查找成功，此时的查找结果应给出找到记录的全部信息或指示找到记录的存储位置；若表中不存于关键字等于给定值的记录，则称查找不成功，此时查找的结果能够给出壹个空记录或空指针。
若按主关键字查找，查找结果是唯壹的；若按次关键字查找，结果可能是多个记录，即结果可能不唯壹。
查找表的存储结构查找表是壹种非常灵活的数据结构，对于不同的存储结构，其查找方法不同。
为了提高查找速度，有时会采用壹些特殊的存储结构。
本章将介绍以线性结构、树型结构及哈希表结构为存储结构的各种查找算法。
查找算法的时间效率查找过程的主要操作是关键字的比较，所以通常以"平均比较次数"来衡量查找算法的时间效率。
第二节静态查找正如本章第壹节所述：静态查找是指于静态查找表上进行的查找操作，于查找表中查找满足条件的数据元素的存储位置或各种属性。
本节将讨论以线性结构表示的静态查找表及相应的查找算法。
1．顺序查找1.1顺序查找的基本思想顺序查找是壹种最简单的查找方法。
其基本思想是将查找表作为壹个线性表，能够是顺序表，也能够是链表，依次用查找条件中给定的值和查找表中数据元素的关键字值进行比较，若某个记录的关键字值和给定值相等，则查找成功，返回该记录的存储位置，反之，若直到最后壹个记录，其关键字值和给定值均不相等，则查找失败，返回查找失败标志。
1.2顺序表的顺序查找下面是顺序表的类型定义：#defineMAX_NUM100//用于定义表的长度typedefstructelemtype{keytypekey;anytypeotherelem;}Se_List[MAX_NUM],Se_Elem;假设于查找表中，数据元素个数为n（n<MAX_NUM），且分别存放于数组的下标变量a[1]~a[n]中。
下面我们给出顺序查找的完整算法。
intseq_search(Se_Lista，keytypek){//于顺序表中查找关键字值等于k的记录，//若查找成功，返回该记录的位置下标序号，否则返回0i=1;while(i<=n&&a[i].key!=k)i++;if(i<=n)retruni;elsereturn0;}改进算法：intseq_search2(Se_Lista，keytypek){//设置了监视哨的顺序表查找，查找关键字值等于指定值k的记录，//若查找成功，返回记录存放位置的下标值，否则返回0i=n;a[0].key=k;while(a[i].key!=k)i--;return(i);}1.3链表的顺序查找链表的顺序查找是指将查找表作为线性表且以链式存储结构存储，用顺序查找方法查找和指定关键字值相等的记录。
链表的类型定义如下所示：typedefstructlinklist{keytypekey;//结点的关键字类型anytypeotherelem;//结点的其他成分structlinklist*next;//指向链表结点的指针}Link_Linklist,*Link;将查找表中的数据元素用这种结构的结点表示，且以指向头结点的指针标识。
对链表实现顺寻查找就是于有头结点的链式查找表中查找关键字值等于给定值的记录，若查找成功，返回指向相应结点的指针，否则返回空指针。
Link_Linklist*link_search(Linkh,keytypek){//link为带头结点链表的头指针，查找关键字值等于k的记录，//查找成功，返回指向找到的结点的指针，查找失败返回空指针p=h->next;while((p!=NULL)&&(p->key!=k))p=p->next;returnp;}顺序查找算法简单，对表的结构无任何要求；可是执行效率较低，尤其当n较大时，不宜采用这种查找方法。
2．折半查找2.1折半查找的基本思想折半查找要求查找表用顺序存储结构存放且各数据元素按关键字有序（升序或隆序）排列，也就是说折半查找只适用于对有序顺序表进行查找。
折半查找的基本思想是：首先以整个查找表作为查找范围，用查找条件中给定值k和中间位置结点的关键字比较，若相等，则查找成功，否则，根据比较结果缩小查找范围，如果k的值小于关键字的值，根据查找表的有序性可知查找的数据元素只有可能于表的前半部分，即于左半部分子表中，所以继续对左子表进行折半查找；若k的值大于中间结点的关键字值，则能够判定查找的数据元素只有可能于表的后半部分，即于右半部分子表中，所以应该继续对右子表进行折半查找。
每进行壹次折半查找，要么查找成功，结束查找，要么将查找范围缩小壹半，如此重复，直到查找成功或查找范围缩小为空即查找失败为止。
2.2折半查找过程示例。
2.3折半查找算法假设查找表存放于数组a的a[1]~a[n]中，且升序，查找关键字值为k。
折半查找的主要步骤为：（1）置初始查找范围：low=1，high=n;（2）求查找范围中间项：mid=(low+high)/2（3）将指定的关键字值k和中间项a[mid].key比较若相等，查找成功，找到的数据元素为此时mid指向的位置；若小于，查找范围的低端数据元素指针low不变，高端数据元素指针high更新为mid-1;若大于，查找范围的高端数据元素指针high不变，低端数据元素指针low更新为mid+1;（4）重复步骤（2）、（3）直到查找成功或查找范围空（low>high），即查找失败为止。
（5）如果查找成功，返回找到元素的存放位置，即当前的中间项位置指针mid；否则返回查找失败标志。
折半查找的完整算法如下：intbin_search(Se_Lista,keytypek){low=1;high=n;//置初始查找范围的低、高端指针while(low<=high){mid=(low+high)/2;//计算中间项位置if(k==a[mid].key)break;//找到，结束循环elseif(k<a[mid].key)high=mid-1;//给定值k小elselow=mid+1;//给定值k大}if(low<=high)returnmid;//查找成功elsereturn0;//查找失败}第三节动态查找1．二叉排序树二叉排序树是壹种常用的动态查找表，下面首先给出它的非递归形式。
二叉排序树是壹棵二叉树，它或者为空，或者具有如下性质：（1）任壹非终端结点若有左孩子，则该结点的关键字值大于其左孩子结点的关键字值。
（2）任壹非终端结点若有右孩子，则该结点的关键字值小于其右孩子结点的关键字值。
二叉排序树也能够用递归的形式定义，即二叉排序树是壹棵树，它或者为空，或者具有如下性质：（1）若它的左子树非空，则其左子树所有结点的关键字值均小于其根结点的关键字值。
（2）若它的右子树非空，则其右子树所有结点的关键字值均大于其根结点的关键字值。
（3）它的左右子树均是二叉排序树。
例如，由关键字值序列（62,15,68,46,65,12,57,79,35）构成的壹棵二叉排序树如图7-4所示。
如果对上述二叉排序树进行中根遍历能够得到壹个关键字有序序列（12,15,35,46,57,62,65,68,79），这是二叉排序树的壹个重要特征，也正是由此将其称为"二叉排序树"。
2．二叉排序树的查找二叉排序树的结构定义中可见到：壹棵非空二叉排序树中根结点的关键字值大于其左子树上所有结点的关键字值，而小于其右子树上所有结点的关键字值，所以于二叉排序树中查找壹个关键字值为k的结点的基本思想是：用给定值k和根结点关键字值比较，如果k小于根结点的值，则要找的结点只可能于左子树中，所以继续于左子树中查找，否则将继续于右子树中查找，依此方法，查找下去，至直查找成功或查找失败为止。
二叉排序树查找的过程描述如下：（1）若二叉树为空树，则查找失败，（2）将给定值k和根结点的关键字值比较，若相等，则查找成功，（3）若根结点的关键字值小于给定值k，则于左子树中继续搜索，（4）否则，于右子树中继续查找。
假定二叉排序树的链式存储结构的类型定义如下：typedefstructlinklist{keytypekey;anytypeotherelem;structlinklist*lchild；structlinklist*rchild;}Bin_Sort_Tree_Linklist,*Bin_Sort_Tree；二叉排序树查找过程的描述是壹个递归过程，若用链式存储结构存储，其查找操作的递归算法如下所示：Bin_Sort_Tree_Linklist*bt_search(Bin_Sort_Treebt,keytypek){//于根指针为bt的二叉排序树上查找壹个关键字值为k的结点，//若查找成功返回指向该结点的指针，否则返回空指针if(bt=NULL)||(bt->key==k)returnbt;elseif(k<bt->key)returnbt_search(bt->lchild,k);//于左子树中搜索elsereturnbt_search(bt->rchild,k);//于右子树中搜索}这个过程也能够用非递归算法实现，算法描述如下：Bin_Sort_Tree_Linklist*bt_search1(Bin_Sort_Treebt,keytypek){p=bt;//指针p指向根结点，搜索从根结点开始while(p!=NULL&&p->key!=k){if(k<p->key)p=p->lchild;elsep=p->rchild;}return(p);}3．二叉排序树的插入于壹棵二叉排序树中插入壹个结点能够用壹个递归的过程实现，即：若二叉排序树为空，则新结点作为二叉排序树的根结点；否则，若给定结点的关键字值小于根结点关键字值，则插入于左子树上；若给定结点的关键字值大于根结点的值，则插入于右子树上。
