第九章查找
一、基本概念（共40分，每题4分）
1、具有12个关键字的有序表，折半查找的平均查找长度________.
A、3.1
B、4
C、2.5
D、5
2、下面关于折半查找的叙述正确的是________
A、表必须有序，表可以顺序方式存储，也可以链表方式存储
B、表必须有序，而且只能从小到大排列
C、表必须有序且表中数据必须是整型，实型或字符型
D、表必须有序，且表只能以顺序方式存储
3、与其他查找方法相比，散列查找法的特点是_______。
A．通过关键字的比较进行查找B．通过关键字计算元素的存储地址进行查找
C．通过关键字计算元素的存储地址并进行一定的比较进行查找D．以上都不是
4、适用于折半查找的表的存储方式及元素排列要求为______________。
A.链式方式存储，元素无序
B.链式方式存储，元素有序
C.顺序方式存储，元素无序
D.顺序方式存储，元素有序
5、已知一个有序表为{11,22,33,44,55,66,77,88,99}，则折半查找元素55需要比较______次。
A．1 B．2 C．3 D．4
6、已知一个有序表为{11,22,33,44,55,66,77,88,99}，则顺序查找元素55需要比较______次。
A．3 B．4 C．5 7、 D．6
7、若对数据集{23,44,48,36,52,73,64,58}建立散列表，采用H(k)=k MOD 13计算散列地址，并采用链地址法处理冲突，则元素64的散列地址为。
8、在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插到集合中。这种方式主要适合于_______。
A．静态查找表B．动态查找表
C．静态查找表与动态查找表D．两种表都不适合
9、在线性表的哈希存储中，处理冲突有________________和________________两种；
装填因子的值越大，存取元素时发生冲突的可能性就________________，
装填因子的值越小，存取元素时发生冲突的可能性就________________。
10、已知一个长度为16的顺序表，其元素按关键字有序排序，若采用折半查找法查找一个不存在的元素，则比较次数最多是______________。
二、综合计算（每题15分，共60分）
1、有一个有序序列3，4，6，7，8，9，13，16，21，26，35，请画出查找关键字7的折半查找过程。
2、画出在初始为空的AVL树中依次插入30, 45, 50, 46, 55, 49, 40时该树的生长全过程，并在有“旋转”时说出“旋转”的类型。
3、假设关键字输入顺序为20, 25, 19, 24, 12, 31, 14, 16, 17，已知散列表长为10（从0～
9进行编址），散列函数采用平方取中法，用线性探测再散列开放定址法解决冲突，
⑴、请画出插入所有关键字后得到的散列表，并指出发生碰撞的次数；
⑵、假设每个关键字的查找概率相同，请计算该散列表查找成功的平均查找长度。
4、画出在初始为空的二叉排序树中依次插入61, 48, 33, 82, 60, 94,43, 79, 58, 80时该树
的生长全过程；请画出在该二叉排序树中删除节点61后的处理结果（请说明删除结点操作的原理）。
习题1 一、单项选择题 A1.数据结构是指（）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 C2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 D3.树形结构是数据元素之间存在一种（）。 A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 B4.设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。 for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++; A.O(1) B.O(2n) C.O(n) D.O(3n) CA5.算法分析的目的是（1），算法分析的两个主要方面是（2）。 （1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6.计算机算法指的是（1），它具备输入，输出和（2）等五个特性。 （1） A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性 C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性 7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。 A.低 B.高 C.相同 D.不好说 8.数据结构作为一门独立的课程出现是在（）年。 A.1946 B.1953 C.1964 D.1968 9.数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。 A.正确 B.错误 C.前半句对，后半句错 D.前半句错，后半句对
第九章查找 一、基本概念（共40分，每题4分） 1、具有12个关键字的有序表，折半查找的平均查找长度________. A、3.1 B、4 C、2.5 D、5 2、下面关于折半查找的叙述正确的是________ A、表必须有序，表可以顺序方式存储，也可以链表方式存储 B、表必须有序，而且只能从小到大排列 C、表必须有序且表中数据必须是整型，实型或字符型 D、表必须有序，且表只能以顺序方式存储 3、与其他查找方法相比，散列查找法的特点是_______。 A．通过关键字的比较进行查找B．通过关键字计算元素的存储地址进行查找 C．通过关键字计算元素的存储地址并进行一定的比较进行查找D．以上都不是 4、适用于折半查找的表的存储方式及元素排列要求为______________。 A.链式方式存储，元素无序 B.链式方式存储，元素有序 C.顺序方式存储，元素无序 D.顺序方式存储，元素有序 5、已知一个有序表为{11,22,33,44,55,66,77,88,99}，则折半查找元素55需要比较______次。 A．1 B．2 C．3 D．4 6、已知一个有序表为{11,22,33,44,55,66,77,88,99}，则顺序查找元素55需要比较______次。 A．3 B．4 C．5 7、 D．6 7、若对数据集{23,44,48,36,52,73,64,58}建立散列表，采用H(k)=k MOD 13计算散列地址，并采用链地址法处理冲突，则元素64的散列地址为。 8、在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插到集合中。这种方式主要适合于_______。 A．静态查找表B．动态查找表 C．静态查找表与动态查找表D．两种表都不适合 9、在线性表的哈希存储中，处理冲突有________________和________________两种； 装填因子的值越大，存取元素时发生冲突的可能性就________________， 装填因子的值越小，存取元素时发生冲突的可能性就________________。 10、已知一个长度为16的顺序表，其元素按关键字有序排序，若采用折半查找法查找一个不存在的元素，则比较次数最多是______________。 二、综合计算（每题15分，共60分）
东北农业大学网络教育学院 数据结构作业题（一） 一、选择题（每题2分，共20分） 1．在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（）。 A、O(n) B、O (n/2) C、O (1) D、O (n2) 2．带头结点的单链表first为空的判定条件是（）。 A、first == NULL; B、first->link == NULL; C、first->link == first; D、first != NULL; 3．在一棵树中，（）没有前驱结点。 A、分支结点 B、叶结点 C、树根结点 D、空结点 4．在有向图中每个顶点的度等于该顶点的（）。 A、入度 B、出度 C、入度与出度之和 D、入度与出度之差 5．对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（）的值除以9。 A、20 B、18 C、25 D、22 6．下列程序段的时间复杂度为（）。 s=0； for(i=1；i 深圳大学-大学物理实验c-杨氏模量的测量 ————————————————————————————————作者: ————————————————————————————————日期： 得分教师签名批改日期深圳大学实验报告 课程名称: 大学物理实验（一) 实验名称： 学院: 指导教师: 报告人:组号： 学号实验地点 实验时间: 年月日 提交时间： 一、实验目的 １． 掌握用拉伸法测定金属丝的杨氏模量； 2. 学会用光杠杆测量长度的微小变化 3． 学会用逐差法处理数据。 二、实验原理 １. 胡克定律和杨氏弹性模量 当固体受外力作用时,它的体积和形状将要发生变化，这种变化,称为形变。物体的形变可分为弹性形变和塑性形变。固体材料的弹性形变又可分为纵向、切变、扭转、弯曲。当外力不太大时,物体的形变与外力成正比，且外力停止作用物体立即恢复原来的形状和体积，这种形变称弹性形变。当外力较大时,物体的形变与外力不成比例,且当外力停止作用后，物体形变不能完全消失，这种形变称为范性形变。范性形变的产生,是由于物体形变而产生的内应力（大小等于单位面积上的作用力）超过了物体的弹性限度(屈服极限）的缘故。如果再继续增大外力,当物体内产生的内应力超过物体的强度极限时,物体便被破坏了。胡克定律:在物体的弹性限度内，胁强于胁变成正比,其比例系数称为杨氏模量（记为Ｅ）。在数值上等于产生单位胁变时的胁强。它的单位是与胁强的单位相同。其中:单位面积上所受到的力称为协强，协变是指在外力作用下的相对形变,它反映了物体形变的大小。杨氏模量来描述材料抵抗纵向弹性形变的能力。 胡克定律指出，在弹性限度内,弹性体的应力和应变成正比。设有一根长为L ，横截面积为S 的钢丝,在外力F 作用下伸长了L ?，则 L L E S F ?= （5-1) 式中的比例系数E 称为杨氏模量，单位为Ｎ·m -２。设实验中所用钢丝直径为d ，则24 1d s π=, 将此公式代入上式整理以后得 L d FL E ?=2 4π （5-２） 上式表明,对于长度Ｌ,直径d 和所加外力Ｆ相同的情况下，杨氏模量Ｅ大的金属丝的伸长量L ?小。因而,杨氏模量是表征固体材料性质的一个重要的物理量,是工程设计上选用材料时常需涉及的重要参数之一,一般只与材料的性质和温度有关,与外力及物体的几何形状无关。对一定材料而言，E 是一个常数，它仅与材料的结构、化学成分及其加工制造的方法有关。杨氏模量的大小标志了材料的刚性。 为能测出金属丝的杨氏模量 E ，必须准确测出上式中右边各量。其中 Ｌ、d 、F 都可用一般方法测得，唯有 ΔL 是一个微小的变化量，用一般量具难以测准，为了测量细钢丝的微小长度变化,实验中使用了光杠杆放大法间接测量。利用光杠杆不仅可以测量微小长度变化，也可测量微小角度变化和形状变化。由于光杠杆放大法具有稳定性好、简单便宜、受环境干扰小等特点，在许多生产和科研领域得到广泛应用。 2、光杠杆和镜尺系统是测量微小长度变化的装置 光杠杆结构如图５－１(ａ) 所示,它实际上是附有三个尖足的平面镜。三个尖足的边线为一等腰三角形。前两足刀口与平面镜在同一平面内(平面镜俯仰方位可调)，后足在前两足刀口的中垂线上。镜尺系统由一把竖立的毫米刻度尺和在尺旁的一个望远镜组成。镜尺系统和光杠杆组成如图５-2(b) 所示的测量系统。 《数据结构》填空作业题答案 第 1 章绪论（已校对无误） 1．数据结构包括数据的逻辑结构、数据的存储结构和数据的运算三方面的内容。 2．程序包括两个内容：数据结构和算法。 3.数据结构的形式定义为：数据结构是一个二元组：Data Structure =（ D， S）。 4.数据的逻辑结构在计算机存储器内的表示，称为数据的存储结构。 5.数据的逻辑结构可以分类为线性结构和非线性结构两大类。 6.在图状结构中，每个结点的前驱结点数和后继结点数可以有多个。 7.在树形结构中，数据元素之间存在一对多的关系。 8.数据的物理结构，指数据元素在计算机中的标识（映象），也即存储结构。 9.数据的逻辑结构包括线性结构、树形结构和图形结构 3 种类型，树型结构和有向 图结构合称为非线性结构。 10. 顺序存储结构是把逻辑上相邻的结点存储在物理上连续的存储单元里，结点之间的逻辑 关系由存储单元位置的邻接关系来体现。 11. 链式存储结构是把逻辑上相邻的结点存储在物理上任意的存储单元里，节点之间的逻辑 关系由附加的指针域来体现。 12.数据的存储结构可用 4 种基本的存储方法表示，它们分别是顺序存储、链式存储、索引存储和散列存储。 13. 线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是一对多或多对多。 14.数据结构在物理上可分为顺序存储结构和链式存储结构。 15. 我们把每种数据结构均视为抽象类型，它不但定义了数据的表示方式，还给出了处理数 据的实现方法。 16.数据元素可由若干个数据项组成。 17.算法分析的两个主要方面是时间复杂度和空间复杂度。 18.一个算法的时间复杂度是用该算法所消耗的时间的多少来度量的，一个算法的空间复杂 度是用该算法在运行过程中所占用的存储空间的大小来度量的。 19.算法具有如下特点：有穷性、确定性、可行性、输入、输出。 20. 对于某一类特定的问题，算法给出了解决问题的一系列操作，每一操作都有它的确切 的定义，并在有穷时间内计算出结果。 21. 下面程序段的时间复杂度为㏒ 3n 。 1 习题1 一、单项选择题 1.数据结构是指（）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 3.树形结构是数据元素之间存在一种（）。 A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 4.设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。 for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++; A.O(1) B.O(2n) C.O(n) D.O(3n) 5.算法分析的目的是（1），算法分析的两个主要方面是（2）。 （1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6.计算机算法指的是（1），它具备输入，输出和（2）等五个特性。 （1） A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性 C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性 7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。 A.低 B.高 C.相同 D.不好说 8.数据结构作为一门独立的课程出现是在（）年。 A.1946 B.1953 C.1964 D.1968 9.数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。 A.正确 B.错误 C.前半句对，后半句错 D.前半句错，后半句对 1．数据的最小单位是（ A ）。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 2．下面关于线性表的叙述错误的是（D）。 (A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片连续的存储空间 (C) 线性表采用链式存储便于插入和删除操作的实现 (D) 线性表采用顺序存储便于插入和删除操作的实现 3．设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（C）。 (A) R-F (B) F-R (C) (R-F+M)％M (D) (F-R+M)％M 4．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（A）。 (A) BADC(B)BCDA (C) CDAB (D) CBDA 5．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（C）。 (A) 9 (B) 10 (C) 11(D) 12 6．下面程序的时间复杂为（B） for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；} (A) O(n) (B) O(n2)(C) O(n3) (D) O(n4) 7．设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（C）。 (A) q=p->next；p->data=q->data；p->next=q->next；free(q)； (B) q=p->next；q->data=p->data；p->next=q->next；free(q)； (C) q=p->next；p->next=q->next；free(q)； (D) q=p->next；p->data=q->data；free(q)； 8．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（C ）。 (A)O(n) (B) O(nlog2n) (C) O(1)(D) O(n2) 9．设一棵二叉树的深度为k，则该二叉树中最多有（D ）个结点。 (A) 2k-1 (B) 2k(C) 2k-1(D) 2k-1 10．设用链表作为栈的存储结构则退栈操作（ B ）。 (A) 必须判别栈是否为满(B) 必须判别栈是否为空 (C) 判别栈元素的类型(D) 对栈不作任何判别 11．函数substr(“DATASTRUCTURE”，5，9)的返回值为（A ）。 (A) “STRUCTURE”(B) “DATA” (C) “ASTRUCTUR”(D) “DATASTRUCTURE” 12．设某二叉树中度数为0的结点数为N0，度数为1的结点数为N l，度数为2的结点数为N2，则下列等式成立的是（ C）。 (A) N0=N1+1 (B) N0=N l+N2(C) N0=N2+1(D) N0=2N1+l 13．设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（B ）。 (A) 空或只有一个结点(B) 高度等于其结点数 (C) 任一结点无左孩子(D) 任一结点无右孩子 14. 深度为k的完全二叉树中最少有（ B ）个结点。 (A) 2k-1-1 (B) 2k-1(C) 2k-1+1(D) 2k-1 第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 第一章绪论 一、选择题 1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像 2 A.结构 B.关系 C.运算 D.算法 2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。 1 A.算法 B.数据元素 C.数据操作 D.逻辑结构 2 A.操作 B.映像 C.存储 D.关系 3.在数据结构中，从逻辑上可以把数据结构分成。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。A.随机存取 B.顺序存取 C.索引存取 D.散列存取 5.算法分析的目的是1，算法分析的两个主要方面其一是指2，其二是指正确性和简单性。1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2 A.空间复杂度和时间复杂度 B.研究算法中的输入和输出的关系 C.可读性和文档性 D.数据复杂性和程序复杂性k 6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。 1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。A.正确 B.不正确 8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。 A.必须连续的 B.部分地址必须连续的 C.一定是不续的D连续不连续都可以 9.以下的叙述中，正确的是。A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。A.正确B.不正确 二、填空题1.数据逻辑结构包括三种类型、和，树形结构和图形结构合称为。2.在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。3.算法的五个重要特性是、、、、。 4.下面程序段的时间复杂度是。 for( i = 0; i < n; i++) for( j = 0; j < m; j++) A[i][j] = 0; 5.下面程序段的时间复杂度是。 i = s = 0; while ( s < n) { i ++; /* i = i +1*/ s += i; /* s = s + i*/ } 6.下面程序段的时间复杂度是。 s = 0; for( i = 0; i < n; i++) for( j = 0; j < n; j++) s += B[i][j]; sum = s; 7.下面程序段的时间复杂度是。 i = 1; while ( i <= n ) i = i * 3; 深圳大学2015年操作系统期末考试复习提纲 红色字体部分为本学期考试大题涉及的内容，不包括选择题 本提纲内容搞懂了及部分概念背诵了既可以拿A 附加题考了固态硬盘，还用信号量同步 制作人：2012170150 吴少滨第一章 1.操作系统的定义 操作系统是一组控制和管理计算机硬件和软件资源、合理地对各类作业进行调度（有效性），以及方便用户（方便性）的程序的集合 2.操作系统的目标 方便性：配置OS后可使计算机更容易使用（不需要手工输入0,1码） 有效性：有效控制和管理计算机各种软硬件资源，提高资源的利用率 可扩充性：便于扩充新功能 开放性：不同机型可运行相同的程序 3.操作系统的作用： （1）从用户的角度看：OS是用户与计算机硬件系统之间的接口 （2）从计算机资源的角度看：OS是计算机系统资源的管理者 （3）从功能扩充的角度看：实现计算机资源的抽象，增加了OS的计算机，成为功能更强使用更方便的扩充机器或虚机器 4.单道批处理系统特征：自动性、顺序性、单道性。 5.多道批处理系统特征：多道性、无序性、调度性 6.分时系统特征：多路性、独立性、及时性、交互性目的：提高资源的使用方便性 7.操作系统的特征： 并发性：多道用户程序可在同一时间间隔中运行 共享性：系统资源可供内存中多个并发的进程共同使用（包括互斥共享和同时访问） 虚拟性：系统物理资源可虚拟为多个逻辑资源 异步性：内存中多个并发的进程以异步方式运行 8.操作系统的功能 （1）处理机管理：进程控制，进程同步，进程通信，进程调度 （2）存储器管理：内存分配，内存保护，地址映射、内存扩充 注：虚拟存储技术主要采用请求调入和置换功能实现内存扩充 （3）设备管理：缓冲管理，设备分配，设备处理，设备独立性，虚拟设备 （4）文件管理：文件存储空间管理，文件系统 （5）用户接口：命令接口，程序接口，图形接口 作业1. 线性表 编程作业： 1．将顺序表逆置，要求用最少的附加空间。 参考答案 #include <> #include <> #include <> #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; typedef int ElemType; typedef struct { ElemType *elem; int length; int listsize; }SqList; 立单链表 "); printf("2.取元素值 "); printf("3.查找 \n"); printf("4.插入 "); printf("5.删除 "); printf("6.显示\n"); printf("7.删除大于mink且小于maxk的元素值 "); printf("8.就地升序排序\n"); printf("9.就地逆置 "); printf("a.有序表插入 "); printf("q.退出\n"); printf("\n请选择操作："); fflush(stdin); scanf("%c",&choice); switch(choice) { case '1': printf("请输入单链表中结点个数："); scanf("%d",&n); Create_L2(L,n); break; case '2': printf("请输入元素位序："); scanf("%d",&i); GetElem_L(L,i,e); printf("元素值为：%d\n",e); break; case '3': printf("请输入要查找的元素："); scanf("%d",&e); if(dlbcz(L,e)) printf("查找成功！"); else printf("查找失败。"); break; case '4': printf("请输入插入位置："); scanf("%d",&i); printf("请输入要插入的元素："); scanf("%d",&e); if(ListInsert_L(L,i,e)) printf("插入成功！单链表为："); else printf("插入失败。"); break; case '5': printf("请输入删除位置："); scanf("%d",&i); if(ListDelete_L(L,i,e)) printf("删除成功！"); else printf("删除失败。\n"); break; case '6': printf("\n单链表为："); xsList(L); break; 深圳大学物理化学实验报告--燃烧热的测定--谢佳深圳大学物理化学实验报告实验者:谢佳澎苏竹实验时间:2000/3/5气温:24.5℃大气压:101.47kPa燃烧热的测定目的要求一,用氧弹热量计测定萘的燃烧热二,明确燃烧热的定义,了解恒压燃烧热与恒容燃烧热的差别三,了解热量计中主要部分的作用,掌握氧弹热量计的实验技术四,学会雷诺图解法校正温度改变值仪器与试剂氧弹卡计贝克曼温度计普通温度计压片器分析天平台秤万用电表点火丝剪刀直尺镊子扳手苯甲酸柴油氧气钢瓶氧气减压阀实验数据及其处理贝克曼温度计读数苯甲酸柴油苯甲酸柴油样品质量g序号初段末段初段末段W2W212.1573.4581.5283.4402.250039.176922.1623.4611.5333.480W1 W132.1693.4641.5383.5201.571838.539242.1753.4671.5413.550样重样重52.1803.4691.5423.5580.67820.637762.1853.4701.5443.561点火丝72.1903.4711.5463.568L2L282.1943.4721.5473.570202092.1983.4731.54 93.575L1L1102.2033.4751.5503.572165.8消耗消耗414.2初段斜率初段截距初段斜率初段截距0.00512.1530.00231.529末段斜率末段截距末段斜率末段截距0.00183.4580.01313.467升温中点12升温中点12.5中点低温中点高温中点低温中点高温2.2153.4801.5583.625温升1.265温升2.066水值J/℃14191热值J/g459204实验讨论固体样品为什么要压成片状？答：压成片状易于燃烧，和氧气充分接触，且易于称中。 2．在量热学测定中，还有哪些情况可能需要用到雷诺温度校正方法？答：实验中要用到温度差校正的都可以用。 深圳大学物理化学实验报告--实验一恒温水浴的组装及其性能测试--赖凯 After completing the work or task, record the overall process and results, including the overall situation, progress and achievements, and summarize the existing problems and future corresponding strategies. 某某管理中心 XX年XX月 深圳大学物理化学实验报告--实验一恒温水浴的组装及其性能测试--赖凯 涛、张志诚示范文本 使用指引：此报告资料应用在完成工作或任务后，对整体过程以及结果进行记录，内容包含整体情况，进度和所取得的的成果，并总结存在的问题，未来的对应策略与解决方案。，文档经过下载可进行自定义修改，请根据实际需求进行调整与使用。 深圳大学物理化学实验报告 实验者: 赖凯涛、张志诚实验时间: 2000/4/3 气温: 21.6 ℃大气压: 101.2 kpa 实验一恒温水浴的组装及其性能测试 目的要求了解恒温水浴的构造及其构造原理，学会恒 温水浴的装配技术；测绘恒温水浴的灵敏度曲线；掌握 贝克曼温度计的调节技术和正确使用方法。仪器与试剂5 升大烧杯贝克曼温度计精密温度计加热器 水银接触温度计继电器搅拌器调压变压器 实验步骤3.1 实验器材，将水银开关、搅拌器等安装 固定。按电路图接线并检查。 3.2 大烧杯中注入蒸馏水。调节水银开关至30℃左右，随即旋紧锁定螺丝。调调压变压器至220v，开动搅拌器（中速），接通继电器电源和加热电源，此时继电器白灯亮，说明烧杯中的水温尚未达到预设的30℃。一段时间后，白灯熄灭，说明水温已达30℃，继电器自动切断了加热电源。 调节贝克曼温度计，使其在30℃水浴中的读数约为2℃。安装好贝克曼温度计。关闭搅拌器。每1分钟记录一次贝克曼温度计的读数，一共记录12个。开动搅拌器，稳定2分钟后再每1分钟记录一次贝克曼温度计的读数，一共记录12个。将调压变压器调至150v（降低发热器的发热功率），稳定5分钟,后再每2分钟记录一次贝克曼温度计的读数，一共记录10个。实验完毕，将贝克曼温度计放回保护盒中，调调压变压器至0v。关闭各仪器电源并 《数据结构简明教程》练习题及参考答案 练习题1 1. 单项选择题 （1）线性结构中数据元素之间是（）关系。 A.一对多 B.多对多 C.多对一 D.一对一 答：D （2）数据结构中与所使用的计算机无关的是数据的（）结构。 A.存储 B.物理 C.逻辑 D.物理和存储 答：C （3）算法分析的目的是（）。 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 答：C （4）算法分析的两个主要方面是（）。 A.空间复杂性和时间复杂性 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 答：A （5）计算机算法指的是（）。 A.计算方法 B. 排序方法 C.求解问题的有限运算序列 D.调度方法答：C （6）计算机算法必须具备输入、输出和（）等5个特性。 A.可行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 答：B 2. 填空题 （1）数据结构包括数据的①、数据的②和数据的③这三个方面的内容。 答：①逻辑结构②存储结构③运算 数据结构简明教程 （2）数据结构按逻辑结构可分为两大类，它们分别是①和②。 答：①线性结构②非线性结构 （3）数据结构被形式地定义为（D,R），其中D是①的有限集合，R是D上的②有限集合。 答：①数据元素②关系 （4）在线性结构中，第一个结点①前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点②后继结点，其余每个结点有且只有1个后继结点。 答：①没有②没有 （5）在树形结构中，树根结点没有①结点，其余每个结点有且只有②个前驱结点；叶子结点没有③结点，其余每个结点的后继结点数可以是④。 答：①前驱②1 ③后继④任意多个 （6）在图形结构中，每个结点的前驱结点数和后继结点数可以是（）。 答：任意多个 （7）数据的存储结构主要有四种，它们分别是①、②、③和④存储结构。 答：①顺序②链式③索引④哈希 （8）一个算法的效率可分为①效率和②效率。 答：①时间②空间 3. 简答题 （1）数据结构和数据类型两个概念之间有区别吗？ 答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素的集合。数据类型不仅定义了一组数据元素，而且还在其上定义了一组操作。 （2）简述线性结构、树形结构和图形结构的不同点。 答：线性结构反映结点间的逻辑关系是一对一的，树形线性结构反映结点间的逻辑关系是一对多的，图在结构反映结点间的逻辑关系是多对多的。 （3）设有采用二元组表示的数据逻辑结构S=(D,R)，其中D={a,b,…,i}，R={(a,b),(a,c),(c,d),(c,f),(f,h),(d,e),(f,g),(h,i)}，问相对于关系R，哪些结点是开始结点，哪些结点是终端结点？ 答：该逻辑结构为树形结构，其中a结点没有前驱结点，称为根结点，b、e、g、i结点没有后继结点，是终端结点，也称为叶子结点。 （4）以下各函数是算法中语句的执行频度，n为问题规模，给出对应的时间复杂度： T1(n)=n log2n-1000log2n T2(n)=3 log2 n-1000log2n class ChainNode{ friend Chain Chain 深圳大学物理化学实验报告 深圳大学物理化学实验报告--燃烧热的测定--谢佳澎苏竹深圳大学物理化学实验报告--燃烧热的测定--谢佳澎苏竹深圳大学物理化学实验报告 实验者: 谢佳澎苏竹实验时间: 2000/3/5 气温: 24.5 ℃大气压: 101.47 kpa 燃烧热的测定 目的要求一,用氧弹热量计测定萘的燃烧热 二,明确燃烧热的定义,了解恒压燃烧热与恒容燃烧热的差别 三,了解热量计中主要部分的作用,掌握氧弹热量计的实验技术 四,学会雷诺图解法校正温度改变值 仪器与试剂氧弹卡计贝克曼温度计普通温度计压片器分析天平台秤万用电表点火丝剪刀直尺镊子扳手苯甲酸柴油氧气钢瓶氧气减压阀 实验数据及其处理贝克曼温度计读数 苯甲酸 柴油 苯甲酸 柴油 样品质量g 初段 末段 初段 末段 w2 w2 1 2.157 3.458 1.528 3.440 2.2500 39.1769 2 2.162 3.461 1.533 3.480 w1 w1 3 3.464 1.538 3.520 1.5718 38.5392 4 2.175 3.467 1.541 3.550 样重 样重 5 2.180 3.469 1.542 3.558 0.6782 0.6377 6 2.185 1.544 3.561 点火丝7 2.190 3.471 1.546 3.568 l2 l2 8 2.194 3.472 1.547 3.570 20 20 9 2.198 3.473 1.549 l1 l1 10 2.203 3.475 1.550 3.572 16 5.8 消耗 消耗 4 14.2 初段斜率初段截距初段斜率初段截距0.0051 2.153 0.0023 1.529 数据结构作业二（第5-6章：树与二叉树,数组和广义表）要求：请在2017年11月9日机房交，迟交适当减分。 一、单选题：（每题2分,共12分） 1、假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为______个。 A.15 B.16 C.17 D.47 2、在一棵二叉树上第4层的结点数最多为______。 A.2 B.4 C.6 D.8 3、任何一棵二叉树的叶子结点在先序中序和后序遍历序列中的相对次序___。 A.不发生改变 B.发生改变 C.不能确定 D.以上都不对 4、根据先序序列A B D C和中序序列DB A C确定对应的二叉树，该二叉树____。 A.是完全二叉树 B.不是完全二叉树 C.是满二叉树 D.不是满二叉树 5、设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为N1、N2 和N3。与森林F对应的二叉树根结点的右子树上的结点个数是_______。 A.N1 B.N1+N2 C.N2 D. N2+N3 6.一个广义表的表头总是一个_______。 A.广义表 B. 元素 C. 空表 D.元素或广义表 一、简答题：（每空2分,共30分） 1.对于一棵具有n个结点的树，该树中所有结点的度数之和为。 2.对于一棵二叉树，若一个结点的编号为i，若它的左孩子结点存在,右孩子结点存在,双亲结点存在,则编号分别为：。 3．设T是一棵二叉树，除叶子结点外，其它结点的度数皆为2，若T中有6个叶结点，则T树的最大深度和最小可能深度分别 为。 4．设给定权值总数有n个，其哈夫曼树的结点总数 为：。 5.若一棵完全二叉树具有35个结点，该树的深度为。 6.在一棵二叉树的二叉链表中，空指针域数是非空指针域数：。 7．由3个结点可以构造出种不同形态的二叉树，其中树高为3的二叉树有个。 8.线索二叉树中的线索指。 9.在哈夫曼编码中，若编码长度只允许小于或等于4，则除了已知两个字符编码为0和10外，还可以最多对个字符编码。 10.广义表A=((x,(a,B)),(x,(a,B),y))，则运算 h e a d(h e a d(t a i l(A)))的结果为。 11.若二维数组A[9][10]，从首地址L O C(a00)开始，按行优先顺序存储，每个元素占4个字节，则元素a[8][5]的地址是。 12.数组的存储结构采用存储方式；对矩阵压缩是为 了。 13.树的后序遍历等价于该树对应二叉树的。 二、应用题（共58分） 第1章 绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ The Short-Term Results Report By Individuals Or Institutions At Regular Or Irregular Times, Including Analysis, Synthesis, Innovation, Etc., Will Eventually Achieve Good Planning For The Future. 编订：XXXXXXXX 20XX年XX月XX日 深圳大学物理化学实验报告--实验一恒温水浴的组装及其性能测试--张子 深圳大学物理化学实验报告--实验一恒温水浴的组装及其性能测试--张子科、刘开鑫简易版 温馨提示：本报告文件应用在个人或机构组织在定时或不定时情况下进行的近期成果汇报，表达方式以叙述、说明为主，内容包含分析，综合，新意，重点等，最终实现对未来的良好规划。文档下载完成后可以直接编辑，请根据自己的需求进行套用。 深圳大学物理化学实验报告 实验者:张子科、刘开鑫实验时间: 2000/4/17 气温: 21.7 ℃大气压: 101.7 kpa 实验一恒温水浴的组装及其性能测试 1目的要求 了解恒温水浴的构造及其构造原理，学会 恒温水浴的装配技术；测绘恒温水浴的灵敏度 曲线；掌握贝克曼温度计的调节技术和正确使 用方法。 2仪器与试剂 5升大烧杯贝克曼温度计精密温度计加热器 水银接触温度计继电器搅拌器调压变压器 3数据处理: 实验时间 4/17/2000 室温℃ 21.7 大气压pa 101.7*10^3 1 2.950 2.840 2.770 2.640 2.510 2.650 2.620 2.530 2.420 2.310 2.560 2.510 2.420 2.310 2.200 2 3.130深圳大学大学物理实验c杨氏模量的测量
《数据结构》填空作业题(答案)
数据结构习题及参考答案 .
数据结构作业(附答案)
数据结构习题与答案
数据结构作业及答案
深圳大学操作系统复习提纲-吴少滨整理
数据结构作业答案
深圳大学物理化学实验报告--燃烧热的测定--谢佳
深圳大学物理化学实验报告--实验一 恒温水浴的组装及其性能测试--赖凯涛、张志诚示范文本
数据结构课程__课后习题答案
数据结构作业答案
深圳大学物理化学实验报告-2
深圳大学 数据结构 树作业
数据结构习题集答案解析_清华大学版
深圳大学物理化学实验报告--实验一 恒温水浴的组装及其性能测试--张子科、刘开鑫简易版
相关主题
文本预览