广工anyview数据结构第一章

/**********

【题目】试写一算法，如果三个整数a，b和c的值 不是依次非递增的，则通过交换，令其为非递增。 ***********/

void Descend(int &a, int &b, int &c) /* 通过交换，令 a >= b >= c */ {

if(c<=b&&b<=a) return; else {

if(a

void swap(int &a,int &b) {

int temp; temp=a; a=b; b=a; }

/**********

【题目】试编写算法求一元多项式 P(x) = a0 + a1x + a2x^2 + ... + anx^n

的值P(x0)，并确定算法中每一语句的执行次数和整个算法 的时间复杂度。 **********/

float Polynomial(int n, int a[], float x)

/* 求一元多项式的值P(x)。 */ /* 数组a的元素a[i]为i次项的系数，i=0,...,n */ {

float answer =a[0]; float temp= 1.0; for(int

数据结构第一章课件

西安科技大学精品课程

第一章 绪论主要内容： 数据结构的定义；数据结构研究的范围；研究数据结构采用的方法； 算法描述的工具；算法性能的评价。 教学目的： 使学生掌握数据结构中涉及的基本概念，为以后各章的学习打好基础。 重点： 数据结构的定义；算法描述的工具；算法性能的评价； 难点： 算法性能的评价；

数据结构第一章课件

西安科技大学精品课程

1.1 数据结构的基本概念一、数据结构的概念计算机可以处理： a、数值计算 b、非数值计算数据结构复杂，关系 无法用数学方程描述

用计算机解决一个具体问题的步骤：抽象数学模型 设计算法 编制程序,上机调试 寻求数学模型： 分析问题 提取操作对象 找操作对象之间关系 用数学的 语言描述

数据结构第一章课件

西安科技大学精品课程

二、有关术语简介1. 数据(Data)数据——所有能被输入到计算机中，并能被计算机处理的符号集合。是计 算机操作对象的总称。

数据是信息的载体，是计算机程序加工处理的原料。 2. 数据元素(Data Element)数据元素——是数据的基本单位, 在计算机中通常作为一个整体进行考 虑和处理。 eg:学生信息检索系统 3. 数据项(Data Item) 数据项------具有独立含义

《数据结构》第一章练习题

1、单项选择题

1.1数据结构是一门非数值计算的程序设计问题中计算机的（ ）以及它们之间的（ ）和运算等的学科。

①A数据元素 B计算方法 C逻辑存储 D数据映像 ②A结构 B关系 C运算 D算法

1.2数据结构被形式的定义为（K,R），其中K是（ ）的有限集，R是K上的（ ）有限集。

①A算法B数据元素C数据操作D逻辑结构 ②A操作B映像C存储D关系

1.3在数据结构中，从逻辑上可以把数据结构分为（ ）。 A动态结构和静态结构 B紧凑结构和非紧凑结构 C线性结构和非线性结构 D内部结构和外部结构 1.4数据结构在计算机内存中的表示是指（ ）。 A数据的存储结构 B数据结构

C数据的逻辑结构 D数据元素之间的关系

1.5在数据结构中，与所使用的计算机无关的是数据的（ ）结构。 A逻辑 B存储 C逻辑和存储 D物理

1.6算法分析的目的是（)，算法分析的两个主要方面是（ ）。 ①A找出数据结构的合理性 B研究算法中输入与输出的关系 C

第一章 绪论

一、选择题

1.以下数据结构中哪一个是非线性结构？( )

A. 队列 B. 栈 C. 线性表 D. 二叉树

2．设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是（ ）。 A. 线性结构 B. 树型结构 C. 物理结构 D. 图型结构 3．下面程序的时间复杂为（ ）

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) 4．数据的最小单位是（ ）。

A.数据项 B. 数据类型 C.数据元素 D. 数据变量

5．程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的时间复杂度为（ ）。

23

A. O(n) B. O(nlog2n) C. O(n) D. O(n/2) 6．下列程序段的时间复杂度为（ ）。

for(i=0； i

for(i=0； i

A. O(m*n*t) B. O(m+n+t) C. O(m+n*t) D. O(m*t+n) 7．下列程序段的时间复杂度为（ ）。

i=0，s=0； while (s

A. O(n1/2) B. O(n1/3) C. O(n) D. O(n2

1. AUB 将所有在Lb中但不在La中的数据元素插入到La中 Void Union（ List &La， List Lb） ｛ La_len=ListLength（La）； Lb_len=ListLength（Lb）； For（i=1；i<=Lb_len；i++） ｛

GetElem（Lb，i，&e）;

If（！LocateElem（La，e，equal）） ListInsert（La，++La_len，e）; ｝ ｝

2. La，Lb中的数据元素按值非递减有序排列，现要求将La，Lb归并为一个新的线性表Lc，且Lc的数据元素仍为递减有序排列。 Void MergeList（List La，List Lb，List &Lc） ｛

InitList（Lc）； i=j=1； K=0；

La_len=ListLength（La）； Lb_len=ListLength（Lb）； While（（i<=La_len）&&（j<=Lb_len））｛//La，Lb均为非空 GetElem（La，i，&ai）; GetElem（Lb，j，&bj）;

if（ai<=bj）

｛ ListInsert（Lc，++k，ai）; ++i ； ｝ else

｛ ListInsert（Lc，++k，bj）; ++j ； ｝ ｝

While（i<=La_len）｛ GetElem（La，i++，ai）; While（j<=Lb_len）｛ GetElem（Lb，j++，bj）; ｝

3. 顺序表的存储结构静态描述：

#defin

《数据结构》第一章习题

一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”）

1、一些表面上很不相同的数据可以有相同的逻辑结构。（√ ） 2、用C语言等高级语言实现的算法就是程序。（ × ） 3、课本P37 1.5题 4、课本P37 1.6题

二、单项选择题

1、从逻辑上可以把数据结构分为（ C ）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 2、程序段 for(int i = n-1; i >= 1; i--) for(int j = 1; j <= i; j++) if(A[j]>A[j+1])

A[j]←→A[j+1]； // A[j]与A[j+1]交换值

其中n为正整数，则最后一行的语句频度在最坏情况下是（ A ）。 A．O(n) B．O(nlogn) C．O(n3) D．O(n2) 3、下面说法错误的是（ c ）

（1）算法原地工作的含义是指不需要任何额外的辅助空

/**********

【题目】试写一算法，如果三个整数a，b和c的值 不是依次非递增的，则通过交换，令其为非递增。 ***********/

void Descend(int &a, int &b, int &c) /* 通过交换，令 a >= b >= c */ { int t;

if(a<=b){t=a;a=b;b=t;} if(b<=c){t=b;b=c;c=t;} if(a<=b){t=a;a=b;b=t;} }

/**********

【题目】试编写算法求一元多项式 P(x) = a0 + a1x + a2x^2 + ... + anx^n

的值P(x0)，并确定算法中每一语句的执行次数和整个算法 的时间复杂度。 **********/

float Polynomial(int n, int a[], float x)

/* 求一元多项式的值P(x)。 */ /* 数组a的元素a[i]为i次项的系数，i=0,...,n */ { int i,j;float p=0,t=1; for(i=0;i<=n;i++) {

p=a[i]*t+p; t=t*x ; } return p; }

/**********

【题目】已知k阶裴波那契序列的定义为 f(0)=0, f(1)=0, ..., f(k-2)=0, f

第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. 下面说法错误的是（）【南京理工大学20

固体物理教程答案 1

第一章、 晶体的结构

1． 以刚性原子球堆积模型，计算以下各结构的致密度分别为：

（1）简立方，

?6; （2）体心立方,

32?; （3）面心立方，?; 86（4）六角密积，[解答]

23?; （5）金刚石结构，?; 616设想晶体是由刚性原子球堆积而成，一个晶胞中刚性原子球占据的体积与晶胞体积的比值称为结构的致密度，

4n?r33设 n为一个晶胞中的刚性原子球数,r表示刚性原子球半径，V表示晶胞体积，则致密度?=

V（1）

子球将依次相切，因为

对简立方晶体，任一个原子有6个最近邻，若原子以刚性球堆积，如图1.2所示，中心在1，2，3，4处的原

3a?4r,V?a3,

面1.2 简立方晶胞

433?(a)2晶胞内包含1个原子，所以 ?=

a3??6

（2）对体心立方晶体，任一个原子有8个最近邻，若原子刚性球堆积，如图1.3所示，体心位置O的原子8个角顶位置的原子球相切，因为晶胞空间对角线的长度为

3a?4r,V?a3,晶胞内包含2个原子，所以

?=

2*43?(a33a34)?3? 8 图1.3 体心立方晶胞

（3）对面心立方晶体，任一个原子有12个最近

第一章 晶体的结构

测 试 题

1.以堆积模型计算由同种原子构成的同体积的体心和面心立方晶体中的原子数目之比. 2.解理面是面指数低的晶面还是面指数高的晶面？为什么？

3.与晶列垂直的倒格面的面指数是什么？

4.高指数的晶面族与低指数的晶面族相比，对于同级衍射，哪一晶面族衍射光弱？为什么？

5.以刚性原子球堆积模型，计算以下各结构的致密度分别为：

（1）简立方，π /6 ； （2）体心立方， ；

（3）面心立方，； （4）六角密积， ；

（5）金刚石结构， 。

6.试证面心立方晶格子是体心立方；体心立方的倒格子是面心立方.

7.六角晶胞的基矢基矢。

. 求其倒格

8.求晶格长数为a的面心立方和体心立方晶体晶面族

第一章 晶体的结构

习题解答

的面间距.

1. 以堆积模型计算由同种原子构成的同体积的体心和面心立方晶体中的原子数目之

比.

1

[解答]

设原子的半径为R,体心立方晶胞的空间对角线为4R,胞的边长为为

,一个晶胞包含两个原子，一个原子占的体积为

;面心立方晶胞的边长为

,晶胞的体积

,单位体

,晶胞的体积为

,单位体积晶

积晶体中的原子数为

,一个晶胞包含四个原子，一个原子占的体积为

体中的原子数为为 ：

=0.