数据结构课程的内容
第6章树和二叉树（Tree & Binary Tree ）6.1 树的基本概念6.2 二叉树6.3 遍历二叉树和线索二叉树6.4 树和森林6.5 赫夫曼树及其应用
特点：非线性结构，一个直接前驱，但可能有多个
直接后继（1：
n ）
6.1树的基本概念
1. 树的定义
2 若干术语
3. 逻辑结构
4.存储结构
5. 树的运算
1. 树的定义
注1：过去许多书籍中都定义树为n≥1，曾经有“空树不是树”的说法，但现在树的定义已修改。
注2：树的定义具有递归性，即树中还有树。
由一个或多个(n≥0)结点组成的有限集合T ，有且仅有一个结点称为根（root ），当n>1时，其余的结点分为m(m≥0)个互不相交的有限集合T1,T2，…，Tm 。每个集合本身又是棵树，被称作这个根的子树
。
树的表示法有几种：
?图形表示法
?嵌套集合表示法
?广义表表示法?目录表示法
?左孩子－右兄弟表示法
这些表示法的示意图
参见教材
P120树的抽象数据类型定义参见教材
P118-119
图形表示法：
教师学生其他人员
2003级2004级2005级2006级……
河南大学物理系计算机系化学系
……
叶子根
子树
广义表表示法
( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) 根作为由子树森林组成的表的名字写在表的左边data link 1link 2...link n
麻烦问题：应当开设多少个链域?
左孩子－右兄弟表示法A B C D
E F G H I J
K L M
数据
左孩子右兄弟( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) )
树的抽象数据类型定义（见教材P118-119）
ADT Tree{
数据对象D:数据关系R:基本操作P ：
}ADT Tree
若D 为空集，则称为空树；//允许n=0
若D 中仅含一个数据元素，则R 为空集；
其他情况下的R 存在二元关系：
①root 唯一//关于根的说明
②D j ∩D k = Φ //关于子树不相交的说明
③…… //关于数据元素的说明
D 是具有相同特性的数据元素的集合。
//至少有15个
2. 若干术语——即上层的那个结点(直接前驱)
——即下层结点的子树的根(直接后继)
——同一双亲下的同层结点（孩子之间互称兄弟）
——即双亲位于同一层的结点（但并非同一双亲）
——即从根到该结点所经分支的所有结点
——即该结点下层子树中的任一结点A
B C G E I D
H F J M L K 根叶子森林有序树无序树——即根结点(没有前驱)——即终端结点(没有后继)
——指m 棵不相交的树的集合(例如删除A 后的子树个数)
双亲孩子兄弟堂兄弟祖先子孙——结点各子树从左至右有序，不能互换（左为第一）——结点各子树可互换位置。
2. 若干术语（续）
——即树的数据元素
——结点挂接的子树数
（有几个直接后继就是几度
，亦称“次数”）结点结点的度结点的层次终端结点分支结点树的度树的深度(或高度)A B C G
E I D H F
J M L K ——从根到该结点的层数（根结点算第一层）——即度为0的结点，即叶子
——即度不为0的结点（也称为内部结点）——所有结点度中的最大值（Max{各结点的度}）——指所有结点中最大的层数（Max{各结点的层次}）问：右上图中的结点数＝；树的度＝；树的深度＝1334
3. 树的逻辑结构
(特点)：一对多（1:n），有多个直接后继（如家谱树、目录树等等），但只有一个根结点，
且子树之间互不相交。
4. 树的存储结构
讨论1：树是非线性结构，该怎样存储？————仍然有顺序存储、链式存储等方式。
讨论2：树的顺序存储方案应该怎样制定？
可规定为：从上至下、从左至右将树的结点依次存入内存。重大缺陷：复原困难（不能唯一复原就没有实用价值）。
讨论3：树的链式存储方案应该怎样制定？
可用多重链表：一个前趋指针，n个后继指针。
细节问题：树中结点的结构类型样式该如何设计？
即应该设计成“等长”还是“不等长”？
缺点：等长结构太浪费（每个结点的度不一定相同）；
不等长结构太复杂（要定义好多种结构类型）。
解决思路：先研究最简单、最有规律的树，然后设法把
一般的树转化为简单树。
二叉树
5. 树的运算
要明确：
1.普通树（即多叉树）若不转化为二叉树，则运
算很难实现。
2.二叉树的运算仍然是插入、删除、修改、查找、
排序等，但这些操作必须建立在对树结点能够“遍历”的基础上！
（遍历——指每个结点都被访问且仅访问一次，不遗漏不重复）。
本章重点：二叉树的表示和实现
6.2 二叉树
为何要重点研究每结点最多只有两个“叉”的树？
?二叉树的结构最简单，规律性最强；
?可以证明，所有树都能转为唯一对应的二叉树，不失一般性。
1. 二叉树的定义
2. 二叉树的性质
3. 二叉树的存储结构
（二叉树的运算见6.3节）
1. 二叉树的定义
定义：是n（n≥0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。逻辑结构：一对二（1：2）
基本特征:
①每个结点最多只有两棵子树（不存在度大于2的结点）；
②左子树和右子树次序不能颠倒（有序树）。
基本形态：
问：具有3个结点的二叉树可能有几种不同形态？普通树呢？
5种/2种
二叉树的抽象数据类型定义（见教材P 121-122）ADT BinaryTree{
数据对象D:数据关系R:基本操作P ：
}ADT BinaryTree
若D=Φ，则R= Φ ；
若D≠Φ，则R= {H}；存在二元关系：
①root 唯一//关于根的说明
②D j ∩D k = Φ //关于子树不相交的说明
③…… //关于数据元素的说明
④……//
关于左子树和右子树的说明
D 是具有相同特性的数据元素的集合。
//至少有20个
2. 二叉树的性质(3+2)讨论1：第i 层的结点数至多是多少？（利用二进制性质可轻松求出）性质1: 在二叉树的第i 层上至多有2i-1个结点（i>0）。性质2: 深度为k 的二叉树至多有2k -1个结点（k>0）。
2i-1个
提问：第i 层上至少有个结点？
1讨论2：深度为k 的二叉树，至多有多少个结点？（利用二进制性质可轻松求出）
2k -1
提问：深度为k 时至少有个结点？
k
讨论3：二叉树的叶子数和度为2的结点数之间有关系吗？
性质3: 对于任何一棵二叉树，若2度的结点数有n
2个，
则叶子数（n
）必定为n2＋1 （即n0=n2+1）
证明：
∵二叉树中全部结点数n＝n
+n1+n2(叶子数＋1度结点数＋2度结点数)又∵二叉树中全部结点数n＝B+1(总分支数＋根结点)
（除根结点外，每个结点必有一个直接前趋，即一个分支）
而总分支数B=n
1
+2n2(1度结点必有1个直接后继，2度结点必有2个)
三式联立可得：n
+n1+n2=n1+2n2+1,即n0=n2+1
实际意义：叶子数＝2度结点数＋1A
B C
G
E
D F
对于两种特殊形式的二叉树（满二叉树和完全二叉树），还特别具备以下2个性质：
性质4: 具有n 个结点的完全二叉树的深度必为[log 2n]＋1性质5: 对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i ，其右孩子编号必为2i ＋1；其双亲的编号必为i/2（i ＝1 时为根,
除外）。证明：根据性质2，深度为k 的二叉树最多只有2k -1个结点，且完全二叉树的定义是与同深度的满二叉树前面编号相同，即它的总结点数n 位于k 层和k-1层满二叉树容量之间，即2k-1-1 三边同时取对数，于是有：k-1≤log 2n 《数据结构》 学习中心： 专业： 学号： 姓名： 作业练习一 (第二章) 一、选择题 1、以下关于线性表的说法不正确的是( )。 A)线性表中的数据元素可以是数字、字符、记录等不同类型。 B)线性表中包含的数据元素个数不是任意的。 C)线性表中的每个结点都有且只有一个直接前趋和直接后继。 D)存在这样的线性表：表中各结点都没有直接前趋和直接后继。 2、线性表的顺序存储结构是一种( )的存储结构。 A)随机存取 B)顺序存取C)索引存取 D)散列存取 3、在顺序表中，只要知道( )，就可在相同时间内求出任一结点的存储地址。 A)基地址B)结点大小C)线性表大小D)基地址和结点大小 4、下面关于线性表的叙述中，错误的是哪一个？（） A)线性表采用顺序存储，必须占用一片连续的存储单元。 B)线性表采用顺序存储，便于进行插入和删除操作。 C)线性表采用链接存储，不必占用一片连续的存储单元。 D)线性表采用链接存储，便于插入和删除操作。 5、线性表采用链表存储时其存储地址要求（）。 A)必须是连续的；B)部分地址必须是连续的； C)必须是不连续的；D)连续和不连续都可以。 6、一个长度为n的顺序存储线性表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需要从后向前依次后移( )个元素。 A)n-i B)n-i+1 C)n-i-1 D)i 7、( )运算中，使用顺序表比链表好。 A)插入B)删除C)根据序号查找 D)根据元素值查找 8、个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是( )。 A) O(1) B) O(n) C) O(n2) D) O(log2n) 9、在一个长度为n的顺序存储线性表中，删除第i个元素(1≤i≤n+1)时，需要从前向后依次前移( )个元素。 A)n-i B)n-i+1 C)n-i-1 D)i 10、在一个长度为n的线性表中顺序查找值为x的元素时，查找时的平均查找长度（即x 同元素的平均比较次数，假定查找每个元素的概率都相等）为( )。 A)n B)n/2 C)(n+1)/2 D)(n-1)/2 11、在一个带头结点单链表HL中，若要向表头插入一个由指针p指向的结点，则 执行( )。 A)HL = p; p->next = HL;B)p->next = HL; HL = p; C)p->next = HL; p = HL; D)p->next = HL->next; HL->next = p; 12、在一个单链表HL中，若要在指针q所指的结点的后面插入一个由指针p所指的结点，则执行( )。 A)q->next = p->next ; p->next = q; B)p->next = q->next; q = p; 东北大学继续教育学院 数据结构II 试卷（作业考核线上1） A 卷 学习中心：奥鹏远程教育沈阳学习中心（直属）[32]院校学号：C09024011930344 姓名何家强 （共 6 页） [ A]1．抽象数据类型的三个组成部分分别为 A．数据对象、数据关系和基本操作 B．数据元素、逻辑结构和存储结构 C．数据项、数据元素和数据类型 D．数据元素、数据结构和数据类型 [ B]2．要求相同逻辑结构的数据元素具有相同的特性，其含义为 A. 数据元素具有同一的特点 B. 不仅数据元素包含的数据项的个数相同，而且其对应数据项的类型要一致 C. 每个数据元素都一样 D. 仅需要数据元素包含的数据项的个数相同 [ D]3．下列各式中，按增长率由小至大的顺序正确排列的是 A．n，n！，2n ，n3/2 B．n3/2，2n，n logn，2100 C．2n，log n，n logn，n3/2 D．2100，logn, 2n, n n [B ]4. 在下列哪种情况下，线性表应当采用链表表示为宜 A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 [ C]5．设指针p指向双链表的某一结点，则双链表结构的对称性是 A. p->prior->next=p->next->next; B. p->prior->prior=p->next->prior; C. p->prior->next=p-> next->prior; D. p->next->next= p->prior->prior; [D ]6. 已知指针p和q分别指向某带头结点的单链表中第一个结点和最后一个结点。假设指 针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为 A. s->next=q；p->next=s->next； B. s->next=p；q->next=s->next； C. p->next=s->next；s->next=q； D. q->next=s->next；s->next=p； [A ]7. 栈和队列的共同特点是 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 [D ]8. 对于链队列，在进行插入运算时. A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 [B ]9．设有一个顺序栈的入栈序列是1、2、3，则3个元素都出栈的不同排列个数为 A．4 B．5 C. 6 D. 7 [D ]10．设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是 A．A，B，C，D B．D，C，B，A C. A，C，D，B D. D，A，B，C [ C]11．表达式a*(b+c)-d的后缀表达式是 A．abcd*+- B．abc*+d- C．abc+*d- D．-+*abcd [B ]12．某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是 A. 空或只有一个结点 B.高度等于其结点数 C. 任一结点无左孩子 D.任一结点无右孩子 [ B]13．下面的说法中正确的是 (1)任何一棵二叉树的叶子结点在种遍历中的相对次序不变。 (2)按二叉树定义，具有三个结点的二叉树共有6种。 A．(1)，(2) B．(1) C．(2) D．(1)，(2)都错 [ B]14．树有先序遍历和后序遍历，树可以转化为对应的二叉树。下面的 说法正确的是 A．树的后序遍历与其对应的二叉树的先序遍历相同 B．树的后序遍历与其对应的二叉树的中序遍历相同 C．树的先序序遍历与其对应的二叉树的中序遍历相同 D．以上都不对 [D ]15．下列说法正确的是 (1)二又树按某种方式线索化后，任一结点均有前趋和后继的线索 (2)二叉树的先序遍历序列中，任意一个结点均处于其子孙结点前 (3)二叉排序树中任一结点的值大于其左孩子的值，小于右孩子的值 A．(1)(2)(3) B．(1)(2) C．(1)(3) D．都不对 [D ]16. 二叉树的第k层的结点数最多为 A．2k-1 B.2K+1 第一章软件体系结构概述（5分） 一、软件体系结构的定义 ●国内普遍接受的定义：软件体系结构包括构件、连接件和约束，它是可预制和可重 构的软件框架结构。 ●软件体系结构= 构件+ 连接件+ 约束 二、软件体系结构的优势 ●容易理解 ●重用 ●控制成本 ●可分析性 第二章软件体系结构风格（10分） 一、软件体系结构风格定义 ●软件体系结构风格是描述某一特定应用领域中系统组织方式的惯用模式。 An architectural style defines a family of systems in terms of a pattern of structural organization. ●体系结构风格定义了一个系统家族，即一个体系结构定义一个词汇表和一组约束。 词汇表中包含一些构件和连接件类型，而这组约束指出系统是如何将这些构件和连 接件组合起来的。 An architectural style defines a vocabulary of components and connector types, and a set of constraints on how they can be combined. 二、常见的体系结构风格 ●管道和过滤器 ?每个构件都有一组输入和输出，构件读输入的数据流，经过内部处理，然后产生输出数据流。 ?过滤器风格的连接件就像是数据流传输的管道，将一个过滤器的输出传到另一个过滤器的输入。 ●数据抽象和面向对象组织 ?数据的表示方法和它们的相应操作被封装在一个抽象数据类型或对象中。 ?这种风格的构件是对象或者说是抽象数据类型的实例。 ?对象通过函数和过程的调用来进行交互。 ●基于事件的隐式调用 ?构件不直接调用一个过程，而是触发或广播一个或多个事件。 ?事件的触发者并不知道哪些构件会被这些事件影响。 ●分层系统 ?组织成一个层次结构。 ?每一层都为上一层提供了相应的服务，并且接受下一层提供的服务。 ●仓库系统 ?构件：中心数据结构（仓库）和一些独立构件的集合。 ?仓库和在系统中很重要的外部构件之间的相互作用。 ●过程控制环路 ?源自于控制理论中的模型框架，将事务处理看成输入、加工、输出、反馈、再输入的一个持续的过程模型。 ?通过持续性的加工处理过程将输入数据转换成既定属性的“产品”。 ●C2风格 第一章 1.计算机由五部分构成：输入、运算器、存储器、控制器、输出 2.计算机三个子系统：处理器子系统、存储器子系统、输入输出子系统 3.输入输出通常被称为人机交互 4.哈佛结构将数据和程序分开存放 5。程序存储原理：程序被要求在执行前存放在存储器中，还要求程序和数据采用同样的存储格式 6.计算机系统是由计算机硬件和软件组成的 ①计算机硬件系统包括：处理器系统（主机）、存储器系统、外部设备（输入设备、输出设备） ②计算机软件系统包括：A.系统软件（操作系统、编程语言/计算机语言系统、工具软件）、 B.应用软件 7.计算机硬件史 ①第一代计算机：电子管 ②第二代计算机：晶体管 ③第三代计算机：集成电路（IC） ④第四代计算机（微型计算机、个人计算机）：大规模集成电路 8.计算机的类型 ①巨型计算机（超级计算机） ②大型计算机 ③小型计算机 ④微型计算机 9.硬件的三个子系统 计算机三个子系统：处理器子系统、存储器子系统、输入输出子系统 存储器子系统：存储数据、程序和参与运行程序 10.计算机软件 11.计算机如何运行 事实上，只要通电启动，机器就开始执行程序，直到关机为止 计算机通电后，CPU执行启动程序BIOS（基本输入/输出系统），其基本任务就是把存放在磁盘中的操作系统调入内存执行，此后将在操作系统的管理下直接操控计算机的硬件。12.信息系统 信息系统的基本功能是为需要者提供特定的信息，支持用户迅速、有效地输入、存储、处理和获取信息。 信息系统有以下6个要素： ①硬件 ②软件 ③数据/信息 ④用户 ⑤过程 ⑥通信 13.HTML:制作web的超文本置标语言 14.web浏览器为用户访问因特网提供了简单的方法，该系统基于超文本技术。 超文本（Hypertext）还包括视频、音频、动画、图片等其他数据。 1 （20分）简要回答下列问题 （注意：请将答案写在答题纸上，并注明题号） ①（3分） 内存中一片连续空间（不妨假设地址从1到m），提供给两个栈S1和S2使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。 ②（5分） 假设字符a,b,c,d,e,f的使用频度分别是0.07,0.09,0.12,0.22,0.23,0.27，写出a,b,c,d,e,f的Huffman（哈夫曼）编码。 ③（4分） 一棵共有n个结点的树，其中所有分枝结点的度均为k，求该树中叶子结点的子数。 ④（4分） 图1表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n-1条线路，画出所有可能的选择。 ⑤（4分） 在起泡（汽泡）排序过程中，有的关键字在某趟排序中可能朝着与最终排序相反的方向移动，试举例说明之。快速排序过程中有没有这种现象？ 2 （15分） 设有一个由正整数组成的无序（向后）单链表，编写完成下列功能的算法： ①找出最小值结点，且打印该数值； ②若该数值是奇数，则将其与直接后继结点的数值交换； ③若该数值是偶数，则将其直接后继结点删除； 3 （14分） 解答下列问题： ①(4分） 将算术表达式((a+b)+c*(d+e)+f)*(g+h) 转化为二叉树； ②(10分） 假设一个仅包含二元运算符的算术表达式以二叉链表形式存储在二叉树BT中，写出计算该算术表达式值的算法。 4（21） 解答下列问题： ①（5分） 画出有向图的十字链表存储结构中头结点和表结点的结点结构。 ②(4分） 下面哪一个方法可以判断出一个有向图中是否有环（回路）？ (1)深度优先遍历 (2)拓朴排序(3)求最短路径(4)求关键路径 ③(12分） 实验报告 实验课程：数据结构 实验项目：实验三互联网域名查询 专业：计算机科学与技术 班级： 姓名： 学号： 指导教师： 目录一、问题定义及需求分析 （1）问题描述 （2）实验任务 （3）需求分析 二、概要设计： (1)抽象数据类型定义 (2)主程序流程 (3) 模块关系 三、详细设计 (1)数据类型及存储结构 (2)模块设计 四、调试分析 (1)调试分析 (2)算法时空分析 (3)经验体会 五、使用说明 (1)程序使用说明 六、测试结果 (1)运行测试结果截图 七、附录 (1)源代码 一、问题定义及需求分析 （1）实验目的 互联网域名查询 互联网域名系统是一个典型的树形层次结构。从根节点往下的第一层是顶层域，如cn、com等，最底层（第四层）是叶子结点，如www等。因此，域名搜索可以看成是树的遍历问题。 （2）实验任务 设计搜索互联网域名的程序。 （3）需求分析： 1)采用树的孩子兄弟链表等存储结构。 2)创建树形结构。 3)通过深度优先遍历搜索。 4)通过层次优先遍历搜索。 二、概要设计： 采用孩子兄弟链表存储结构完成二叉树的创建； 主程序流程： 创建根节点域名输入域名拆分根据孩子兄弟链表表示的树进行插入调用层次优先遍历输出遍历结果调用深度优先遍历输出遍历结果结束程序 模块关系： 输入域名 创建孩子兄弟树 层次优先遍历输出结果 深度优先遍历输出结果 结束 三、详细设计 孩子兄弟链表结构： typedef struct CSNode{ ElemType data[10]; struct CSNode *firstchild, *nextsibling; }*CSTree; 数据结构试卷 第1页（共2页） 中南大学考试试卷 2012 --2013 学年 1 学期 时间100分钟 2013 年1 月 14日 数据结构 课程 48学时 3学分 考试形式： 闭 卷 专业年级： 通信工程11级 总分100分，占总评成绩 70 % 注：此页不作答题纸，请将答案写在答题纸上 一、线性结构题（5个小题，每个小题8分，共计40分） 1．在一个单链表中，若p 所指结点不是最后结点，s 指向已生成的新结点，则在p 之后插入s 所指结点的正确操作是如何表达？（8分） 2．设有字符串为3*-y ，试利用栈写出将其转换为3y-*的操作步骤。假定用X 代表扫描该字符串过程中顺序取一个字符进栈的操作，用S 代表从栈中取出一字符加入到新字符串尾的出栈操作。例如，ABC 变为BCA 的操作步骤XXSXSS 。（8分） 3．若front 和rear 分别表示循环队列Q 的头指针和尾指针，m0表示该队列的最大容量，则循环队列为空的条件是什么？循环队列为满的条件是什么？（8分） 4．二维数组A[20][20]采用按行为主序的存储方式，每个元素占4个字节的存储单元，若A[0][0]的存储地址为300，则[A][10][10]的地址是多少？（8分） 5．用二分查找法对一个长度为10的有序表{8,12,15,17,19,23,24,26,29,33}进行查找，填写查找每一元素需要的比较次数。（8分） 二、非线性结构题（5个小题，每个小题8分，共计40分） 1．现有某二叉树，按先根遍历的序列为ABDEFCGH ，按中根遍历的序列为DEFBGHCA ，试画出此二叉树。（8分） 2．已知无向图G 的邻接矩阵如下，假设对其每行元素访问时必须从右到左，请写出从V 0开始的深度优先搜索的序列。（8分） 4 v 3 v 2 v 1v 0 v 4 32100111010110110111110100110V V V V V ??? ???? ???????? ? 中南大学复习题及参考答案 软件工程 一、选择题： 1.下面哪些UML图描述系统行为（ A ） A.用例图 B.类图 C.对象图 2.属于概要设计活动的是（ A ） A.软件结构设计 B.数据结构设计 C.算法设计 3.属行为型设计模式的是（C） A.组合模式 B.工厂方法模式 C.观察者模式 4.下列说法正确的是（ B ）是软件开发方法是系统描述语言是软件开发过程 5. 根据程序流程图划分的模块通常是（ B ） A. 信息内聚的模块 B. 过程内聚的模块 C.逻辑内聚的模块 6.如果某程序中的比较个数是m，则其McCabe环形复杂度为（ C ） +1 7.按ISO9000-3的说明，下列属软件配置项的是（ C ） A.软件开发方法 B.软件开发组织管理制度 C.软件开发合同 8. 软件测试的目的是（ C ） A.证明软件无错 B.发现软件中的所有错误 C.尽可能发现软件系统中的错误 9.软件重构关注的是（ B ） A. 软件体系结构 B. 模块细节 C.软件性能 10.软件项目开发计划的内容有（ B ） A. 数据分析 B.风险分析 C.功能分析 11.在UML的类图中，描述整体与部分关系的有（ B ） A.泛化关系 B.聚合关系 C.依赖关系 12.软件过程能力成熟度模型CMM用以评价（A） A.软件过程能力 B.组织能力 C.学习能力 13. 因计算机硬件和软件环境的变化而作出的修改软件的过程称为（ C ） A. 完善性维护 B. 改正性维护 C.适应性维护 14. 对项目软件而言，软件功能需求信息主要由谁提供（ A ） A.软件用户 B.软件开发人员 C.软件项目管理人员 15. IDEF0图反映不出（C） A.系统做什么 B.系统功能由谁做 C.系统如何做 16. 原型模型是一种什么开发过程模型（B） A.自顶向上 B. 由外至内 C.增量式 17. 系统流程图描述（A） A.物理系统 B.逻辑系统 C.软件体系结构 18.需求规格说明书的内容不应该包括（ C ） A.软件确认准则 B.软件的性能描述 C.算法过程的详细描述 19.适合需求模糊或需求不确定系统开发的软件开发模型有（ C ） A. 瀑布模型 B. RAD模型 C.原型模型 图中描述系统结构的有（ A ） A. 组件图 B. 顺序图 C.状态图 21.面向对象方法是一种什么软件开发方法（ B ） A.层次化 B.迭代增量式 C.逐步求精 22.不可以用来衡量软件可维护性的有（） A.可靠性 B.可用性 C.可行性 23. 系统分析员在需求分析最后负责编写（） 浙江大学2007–2008学年秋季学期 《数据结构基础》课程期末考试试卷 开课学院：软件学院、计算机、竺可桢学院，考试形式：闭卷，允许带_ 无入场考试时间：_2007_年_11_月_17日, 所需时间： 120 分钟 考生姓名： ___学号：专业： ____教师：题序一二三四总分得分 评卷人 Answer Sheet Part I 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. Part II 1. c d e 2. c d 3. c d Part III 1. (a) (b) 1. (c) 2. (a) 2. (b) 3. 4. (a) 4. (b) Part IV void Dijkstra( Table T ) NOTE: Please write your answers on the answer sheet. 注意：请将答案填写在答题纸上。 I. Please select the answer for the following problems. (20 points) (1)The time complexity of the following piece of code is (2 points) for(i=0; i 实验三树和图应用 一、实验目的 光纤管道铺设施工问题 问题描述 设计校园内有N个教学楼及办公楼，要铺设校园光纤网，如何设计施工方案使得工程总的造价为最省。 二、实验要求 设计校园光纤网铺设的最小生成树模拟程序。 1)采用邻接表或邻接矩阵存储结构。 2)分别采用普利姆算法和克鲁斯卡尔算法实现。 输入形式 对应的教学楼、办公楼数目n，各边权值即每栋楼之间的距离 输出形式 最小生成树，即总路程最小的路 程序功能 设计校园光纤网铺设的最小生成树模拟程序 三、设计概要 流程图 抽象数据类型的定义 class prims { private: int n; //节点的个数 int graph_edge[99][4]; //图的边 int g; //图中边的个数 int tree_edge[99][4]; //树的边 int t; //树的边的个数 int s; //源节点 int T1[50],t1; // 第一部分 int T2[50],t2; //第二部分 public: void input(); int findset(int); void algorithm(); void output(); }; 各程序模块之间的调用关系 四、详细设计 定义prims类 private中进行对图的创建 public: void input(); int findset(int); void algorithm(); void output(); 开始界面 实现prims类中图的初始化 分别输入图中的顶点个数、图的边及其权值 算法构造 t=0;//初始化边的个数为0 t1=1; T1[1]=1; //资源节点 t2=n-1; int i; for(i=1;i<=n-1;i++) T2[i]=i+1; cout<<"\n\n*****运算开始*****\n\n\n"; while(g!=0 && t!=n-1) { int min=99; int p; int u,v,w; for(i=1;i<=g;i++) { if(findset(graph_edge[i][1])!=findset(graph_edge[i][2])) //如果u和v在不同的部分{ if(min>graph_edge[i][3]) { min=graph_edge[i][3]; u=graph_edge[i][1]; v=graph_edge[i][2]; w=graph_edge[i][3]; p=i; } } } for(int l=p;l 1?在数据库设计中，用E-R图来描述信息结构但不涉及信息在计算机中的表示，它属于数据库设计的（）阶段。 A需求分析 B概念设计 C逻辑设计 D物理设计 参考答案 B 数据库设计步骤： （1）规划（必要性、可行性，总目标） （2）需求分析（分析用户活动，产生业务流程图；确定系统范围，产生系统范围图；分析用户活动涉及的数据，产生数据流程图；分析系统数据，产生数据字典。）（3）概念设计（设计出独立于计算机硬件和DBMS的概念模式。E-R模型是主要设计工具） （4）逻辑结构设计（把概念设计阶段设计好的全局E-R模式转换成与选用的具体机器上的DBMS所支持的数据模型相符合的逻辑结构，包括数据库模式和外模式）（5）数据库的物理设计（对于给定的数据模型选取一个垠适合应用环境的物理结构的过程。数据库的物理结构主要指数据库的存储记录格式、存储记录安排和存取方法）（6）数据库的实现（建立实际数据库结构；装入试验数据对应用程序进行调试；装入实际数据，进入试运行状态） （7）数据库的运行与维护（维护数据库的安全性与完整性；监测并改善数据库运行性能; 根据用户要求对数据库现有功能进行扩充；及时改正运行中发现的系统错误） 2.关于数据库概念设计阶段的工作目标，下列说法错谋的是 A定义和描述应用系统涉及的信息结构和范围 B定义和描述应用系统中数据的属性特征和数据之间的联系 C描述应用系统的数据需求 D描述需要存储的记录及其数量 参考答案 3. SQL Server 2000的字符型系统数据类型主要包括（）。 A int、money、char B char> varchar、text C datetime、binary> int D char、varchar> int 参考答案 B 4. 具有联系的相关数据按一定的方式组织排列，并构成一定的结构，这种结构即（）。 A数据模型 B数据库 C关系模型 D数据库管理系统 参考答案 A 5. 在数据库系统中，下列哪个映像关系用于提供数据与应用程序间的逻辑独立性？ A外模式/模式 B模式/内模式 C外模式/内模式 D逻辑模式/内模式 参考答案 B 6. 关系模型的数据结构是 A树 B图 C表 D二维表 参考答案 D 7. 数据字典是数据库管理系统的重要组成部分，其中存储的各类信息通常由 A数据库管理员维护 B程序员维护 C数据库管理系统维护 D—般用户维护 参考答案 A 8. E-R图用于描述数据库的 中南大学考试试卷 2015--2016学年上学期期末考试试题时间100分钟 数据结构课程56学时3.5学分考试形式：闭卷 专业年级：计算机科学与技术10级总分100分，占总评成绩70% 姓名班级学号 （本试卷共四道大题，答案全部做在答题纸上！） 一、选择题(每题2分，共24分) 1.以下数据结构中，属于线性结构的是（） A．图B．栈 C．二分查找树D．森林 2.用二分法查找表(a0,a1,a2,a3,……a16)，需要比较2次才能找到的元素是（） A．a7和a16 B．a11和a13 C．a1和a14 D．a3和a12 3.用概率查找改进查找效率，是经过多次查找以后使得（） A．查找次数越少的元素查找速度越快 B．查找次数越少的元素越往前存放 C．查找次数越多的元素越往后存放 D．查找次数越多的元素查找速度越快 4.二分查找要求元素( ) A.有序、顺序存储 B.有序、链式存储 C.无序、顺序存储 D.无序、链式存储 5.已知pPre为指向链表中某结点的指针，pNew是指向新结点的指针，以下哪段伪码算 法是将一个新结点插入到链表中pPre所指向结点的后面？（） A．pPre->link = pNew; pNew = null; B．pPre->link = pNew->link; pNew->link = null; C．pNew->link = pPre->link; pPre->link = pNew; D．pNew->link = pPre->link; pPre->link = null; 6.在递归算法执行过程中，计算机系统必定会用到的数据结构是（） A．队列B．链表 C．栈D．二叉树 7.一个队列的入列序为ABCD，则队列的可能输出序列为（） A．DCBA B．ABCD C．ADCB D．CBDA 8.具有10个叶子结点的二叉树中有（）个度为2的结点 A．8B．9 C．10D．11 9.若A=10，B=4，C=6，D=4，E=15则后缀表达式“AB*CD+-E+”的值为( )。 A．45B．31 第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）。【北京邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（）【中科院计算所1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 【南京理工大学1999 一、1（2分）【武汉交通科技大学1996 一、1（4分）】4．一个算法应该是（）。【中山大学1998 二、1（2分）】 A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C. 5. 下面关于算法说法错误的是（）【南京理工大学2000 一、1（1.5分）】 A．算法最终必须由计算机程序实现 B. 为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（）【南京理工大学2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。【武汉交通科技大学1996 一、4（2分）】 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。【北方交通大学2000 二、1（2分）】 A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？【北方交通大学2001 一、1（2分）】 A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（）【北方交通大学2001 一、2（2分）】 A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学2001 一、10（3分）】 实 验 报 告 一、实验目的 1) 加深对图的表示法和图的基本操作的理解，并可初步使用及操作； 2) 掌握用图对实际问题进行抽象的方法，可以解决基本的问题； 3) 掌握利用邻接表求解非负权值、单源最短路径的方法，即利用Dijkstra 算法求最短 路径，同时掌握邻接表的建立以及使用方法，能够解决相关的问题； 4) 学会使用STL 中的map 抽象实际问题，掌握map ，List,，priority_queue 等的应 用。 二、实验内容与实验步骤 （1） 实验内容： 使用图这种抽象的数据结构存储模拟的欧洲铁路路线图，通过Dijkstra 算法求出欧洲旅行最少花费的路线。该实验应用Dijkstra 算法求得任意两个城市之间的最少路费，并给出路费最少的路径的长度和所经过的城市名。 （2） 抽象数据类型及设计函数描述 1) 抽象数据类型 class City ： 维护一个城市的信息，包括城市名name ，是否被访问过的标记visted ，从某个城市到达该城市所需的总费用total_fee 和总路径长度total_distance ，求得最短路径后路径中到达该城市的城市名from_city 。 class RailSystem ： 用邻接表模拟欧洲铁路系统，该邻接表使用数据结构map 实现，map 的key-value 课程名称：数据结构 班级： 实验成绩： 实验名称：欧洲旅行 学号： 批阅教师签字： 实验编号：实验二 姓名： 实验日期：2013 年6 月 18 日 指导教师： 组号： 实验时间： 值对的数据类型分别为string和list<*Service>，对应出发城市名和该城市与它能 够到达的城市之间的Service链表。 class Service： 为铁路系统模拟了两个城市之间的直接路线，包括两个城市之间直接到达的费用 fee，两城市之间的直接距离distance。 部分设计函数描述 ●RailSystem(const string& filename) 构造函数，调用load_services(string const &filename)函数读取数据 ●load_services(string const &filename) 读取传入的文件中的数据并建立上述两个map以模拟欧洲铁路路线图 ●reset(void) 遍历cities图，初始化所有城市的信息：visted未访问，total_distance最大 值，total_fee费用最大值，from_city为空 ●~RailSystem(void) 析构函数，用delete将两个map中所有使用new操作符开辟的空间删除 ●void output_cheapest_route(const string& from, const string& to, ostream& out); 输出两城市间的最少费用的路径，调用calc_route(string from, string to)函 数计算最少费用 ●calc_route(string from, string to) 使用Dijkstra算法计算from和to两个城市间的最少费用的路径 （3）采用的存储结构 1)map 第一章绪论习题练习答案 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。 ? 数据：指能够被计算机识别、存储和加工处理的信息载体。 ? 数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素 有时可以由若干数据项组成。 ? 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可以看作是程序设计语言中已实现的数据结构。 ? 数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容 :数据的逻辑结构、存储结构和数据的运算。 ? 逻辑结构：指数据元素之间的逻辑关系 ? 存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构 ? 线性结构：数据逻辑结构中的一类。它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都有且只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。 栈、队列、串等都是线性结构。 ? 非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。 试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。 答： 例如有一张学生体检情况登记表，记录了一个班的学生的身高、体重等各项体检信息。这张登记表中，每个学生的各项体检信息排在一行上。这个表就是一个数据结构。每个记录（有姓名，学号，身高和体重等 字段）就是一个结点，对于整个表来说，只有一个开始结点（它的前面无记录）和一个终端结点（它的后面无记录），其他的结点则各有一个也只有一个直接前趋和直接后继（它的前面和后面均有且只有一个记录）。这几 个关系就确定了这个表的逻辑结构是线性结构。 这个表中的数据如何存储到计算机里，并且如何表示数据元素之间的关系呢即用一片连续的内存单元来存放这些记录（如用数组表示）还是随机存放各结点数据再用指针进行链接呢这就是存储结构的问题。 在这个表的某种存储结构基础上，可实现对这张表中的记录进行查询，修改，删除等操作。对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。 常用的存储表示方法有哪几种 答： 常用的存储表示方法有四种 : ? 顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构，通常借助程序语言的数组描述。 ? 链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示。由此得到的存储表示称为链式存储结构,通常借助于程序语言的指针类型描述。 ? 索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。组成索引表的索引 项由结点的关键字和地址组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（Dense Index）。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引。 ? 散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。 设三个函数 f,g,h 分别为 f(n)=100n 3+n2+1000 , g(n)=25n3+5000n2 , h(n)=+5000nlgn 请判断下列关系是否成立：中南大学网络教育数据结构
40875][东北大学]20年7月考试《数据结构Ⅱ》考核作业(答案)
中南大学软件体系结构重要资料
浙江大学大计知识点整理
东北大学2000年数据结构试题
数据结构实验-互联网域名查询实验报告
数据结构试题(通信11级)
中南大学软件工程复习题及参考答案
浙大数据结构期末考试2007-2008
东北大学数据结构上机实验报告3
中南大学数据库考试题库
中南大学计算机数据结构试题参考答案
数据结构考试题库含参考答案
数据结构实验二-
中南大学数据结构与算法
相关主题
文本预览