大连理工大学数据结构书面作业参考答案(第1章)
数据结构部分课后习题答案
第一章
1.1
数据的逻辑结构是从具体问题中抽象出来的数学模型，体现了事物的组成和事物之间的逻辑关系。
数据的存储结构主要用来解决各种逻辑结构在计算机中物理存储表示的问题。
1.2
事前分析和事后统计
事前分析：
优点，程序不必运行，所得结果只依赖于算法本身
缺点，不够精确
事后统计：
优点，精确
缺点，必须运行程序，所得结果依赖于硬件、环境等因素
考虑赋值、运算操作执行的次数
第3行赋值2次
第6行赋值执行n次，加法执行n次
所以，总共2n+2次操作，算法复杂度为O(n)
1.4
y= y + i * j 执行次数：
n?2i+1=n2
+
n
n
2
i=1 1.5
n!>3
2
n
>2
n
2>n?n3+7n5>n3>n2+log n>n log n>n>n+log n
>log n
大连理工大学结构优化复习总结
结构优化设计－基于结构分析技术，在给定的设计空间实现满足使用要求且具有最佳性能或最低成本的工程结构设计的技术 优化设计的三要素:设计变量;约束条件;目标函数 凸域:基于n维空间的区域s里，如果取任意两点x1和x2，连接这两点的线段也属于s，该区域称凸域（=αx1+(1-α)x2 ） 凸函数:如果函数f(x)定义在n维空间的凸域s上，而且对s中的任意两点x1和x2和任意常数α,0.0<=α<=1.0,有f[αx1+(1- α)x2]<=αf(x1)+(1- α)f(x2),则f(x)称为s上的凸函数 严格凸函数:上式小于严格成立 凸规划:如果可行域是凸域，目标函数是凸函数，这样构成的数学规划问题为凸规划问题。 准则设计法:依靠工程经验;效率高;缺乏严格数学基础 最优准则法基于库塔克（K-T）条件:需构造迭代求解算法;通用性不强 数学规划方法:有严格的数学基础，有较好的通用性，计算效率要考虑。 结构优化问题的求解布骤 I. 建立优化模型。给定初始设计方案。 II. 结构分析(有限元） III.优化（收敛性）检验。满足则结束程序，否则继续IV IV. 灵敏度分析 V. 求解优化问题，修改结构模型，返回II。 优化求解的两大类方法：准则法；数学规划法 准则设计方法：用优化准则代替原来的优化问题 同步失效准则设计的评价： {优点：简单、方便，特别是独立约束个数n=m时；工程实用；适合于构件设计。 缺点：只能处理简单构件设计；缩小了设计空间，不能保证最优解；若n < m ，可能无解； 当n > m时，确定哪些破坏模式应同时发生比较困难。 改进：为了弥补等式约束代替不等式约束的缺陷，引入松弛因子ψi σi (X ) =ψiσip , 0 ≤ψi ≤1, i =1,2,......n 启发：用准则代替原来的优化问题，准则法的基本思想；如果将桁架的每根杆看作一种可能的破坏模式，桁架看作一个元件。可以得到满应力准则 满应力方法的缺点：完全无视重量会漏掉最轻设计；中间点一般是不可行设计，对工程实际不利。希望得到可行的中间设计点。 齿形法：采用射线步进行可行性调整，适用于桁架一类刚度与设计变量成正比的结构。 将所有设计变量同时乘以一个常数ξ：A n i=ξA i o} 线性函数都是凸函数，线性规划是凸规划。
数据结构习题及参考答案
习题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.前半句错，后半句对
数据结构试题及答案10套
一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价,不包括如下（B ）方面的内容。 Ａ.健壮性和可读性Ｂ．并行性C。正确性Ｄ．时空复杂度 2.2．在带有头结点的单链表ＨL中,要向表头插入一个由指针p指向 的结点，则执行（A ). Ａ. p－〉ｎｅxt=HL->nexｔ; ＨL-〉nexｔ=p; B． p-〉next=HL；ＨL=p； Ｃ。p-＞ｎext=HＬ； p＝HL；Ｄ. HL=p; ｐ－〉next＝ＨL； 3.3．对线性表,在下列哪种情况下应当采用链表表示？( B ） Ａ.经常需要随机地存取元素 B。经常需要进行插入和删除操作 C。表中元素需要占据一片连续的存储空间D．表中元素的个数不变 4. 4.一个栈的输入序列为１ 2 3，则下列序列中不可能是栈的输出序 列的是( C ） A. 2 3 1 ??? B. ３ 2 1 C。 3 １ 2 ??? D. 1 ２３ 5. 5.AＯV网是一种（D ）。 A．有向图Ｂ．无向图Ｃ．无向无环图D．有向无环图 6.6。采用开放定址法处理散列表的冲突时,其平均查找长度（Ｂ)。 A．低于链接法处理冲突B．高于链接法处理冲突Ｃ.与链接法处理冲突相同 D。高于二分查找 7.7。若需要利用形参直接访问实参时，应将形参变量说明为（D ) 参数. Ａ。值Ｂ。函数 C.指针 D。引用 8.８．在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结 点都具有相同的（ A )。 A。行号 B.列号 C．元素值 D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为( D )。 A。O（loｇ 2n) B．Ｏ（nlog 2 n） C。０（n) D.0 （n2） 10.10.从二叉搜索树中查找一个元素时,其时间复杂度大致为( C ). Ａ．O(n） B. Ｏ(1） C。 O（log 2 n） D. O(n2)二、运算题（每题 6 分，共２４分）
大连理工大学城市学院建筑工程学院教师简介1
刘伟工程管理教研室主任讲师 2006年，毕业于哈尔滨工业大学营造与房地产系，研究生学历，硕士学位。毕业后，到大连理工大学城市学院任教。承担了工程管理专业建筑施工技术，基础工程，高层建筑施工等多门核心课程的教学工作。2008年获得校级“优秀员工”称号，2009年，获得学校优秀实践教育工作者称号。曾发表核心期刊论文2篇，省级期刊1篇，教育教学研究论文5篇。主要研究方向为工程项目管理，建筑施工技术。 刘海芳，2003年毕业于西北工业大学土木建筑工程系，获工学学士学位，2006年毕业于西安建筑科技大学土木工程学院结构工程专业，获工学硕士学位。现为大连理工大学城市学院建筑工程学院任课教师，主要讲授《工程结构》、《工程力学》、《房屋建筑学》、《CAD绘图》等课程，发表教育教学论文5篇。 邹颖 2005年毕业于大连理工大学工程力学系，研究生学历，硕士学位。毕业后，到大连理工大学城市学院任教。承担了工程管理和工程造价专业的基础课程及部分工程造价核心课程的教学工作。2008年获得校级“优秀员工”称号，曾发表核心期刊论文2篇，省级期刊1篇，教育教学研究论文1篇。主要研究方向为建筑结构力学、工程造价。 施林林工程管理教研室教师 2008年，毕业于吉林建筑工程学院土木工程学院，研究生学历，硕士学位。毕业后，到大连理工大学城市学院任教。承担了工程管理专业工程力学，工程材料，工程项目管理等多门基础课和核心课程的教学工作。读研期间，主要完成“在柱上板带梁施加预应力的大跨现浇空心楼盖结构性能和工程应用研究”，积极参与“配筋砌块砌体剪力墙新型结构体系工程设计应用研究”等科研项目，参加吉林省建筑结构学术年会并获得优秀论文奖，参加全国研究生数学建模竞赛并获得三等奖，曾发表省级期刊论文2篇，会议论文1篇。曾完成吉林新城市花园小区、今宇兰亭小区、东北亚框架结构厂房等结构设计工作。主要研究方向为新型结构。 徐锋建筑工程学院实验室主任 徐锋，男，中共党员1998年7月，毕业于辽宁工程技术大学测量工程专业，本科学历；毕业后到大连金源勘测技术有限公司任测量科科长，工程师；2005年4月，到大连理工大学城市学院任教，讲授工程测量、建筑材料、建筑工程合同等课程，同时负责实验、实践等教学与管理工作；2008年考取辽宁工程技术大学地理信息及制图专业，在读师资硕士。 来校前，本人熟练操作经纬仪、水准仪、全站仪，熟悉GPS，检校测量仪器，电子平板数字化地形图测绘，土方量及纵横断面计算，地籍测量，建筑物定位测量，计算机管理、熟练应用AUTOCADR14及2000、南方CASS绘图软件、北京道亨绘图软件4.0和山维绘图软件2003版。出色完成卧龙水库至净水厂五公里的地下管线地形图测量任务上千项工程。 来校后，于06年获大连理工大学城市学院“优秀员工”称号；07年获大连理工大学城市学院“优秀标兵”称号；07年和08年，均获大连理工大学城市学院“教育教学优秀奖”；06年、07年、08年在大连市“科力达杯”大学生测绘
数据结构作业题及参考答案
东北农业大学网络教育学院 数据结构作业题（一） 一、选择题（每题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 第一章绪论 一、选择题 1.组成数据的基本单位是（） （A）数据项（B）数据类型（C）数据元素（D）数据变量 2.数据结构是研究数据的（）以及它们之间的相互关系。 （A）理想结构，物理结构（B）理想结构，抽象结构 （C）物理结构，逻辑结构（D）抽象结构，逻辑结构 3.在数据结构中，从逻辑上可以把数据结构分成（） （A）动态结构和静态结构（B）紧凑结构和非紧凑结构 （C）线性结构和非线性结构（D）内部结构和外部结构 4.数据结构是一门研究非数值计算的程序设计问题中计算机的（①）以及它们之间的（②）和运算等的学科。 ① （A）数据元素（B）计算方法（C）逻辑存储（D）数据映像 ② （A）结构（B）关系（C）运算（D）算法 5.算法分析的目的是（）。 （A）找出数据结构的合理性（B）研究算法中的输入和输出的关系 （C）分析算法的效率以求改进（D）分析算法的易懂性和文档性 6.计算机算法指的是（①）,它必须具备输入、输出和（②）等5 个特性。 ① （A）计算方法（B）排序方法（C）解决问题的有限运算序列（D）调度方法 ② （A）可执行性、可移植性和可扩充性（B）可行性、确定性和有穷性 （C）确定性、有穷性和稳定性（D）易读性、稳定性和安全性 二、判断题 1.数据的机内表示称为数据的存储结构。（） 2.算法就是程序。（） 3.数据元素是数据的最小单位。（） 4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。（） 5.算法的时间复杂度取决于问题的规模和待处理数据的初态。（） 三、填空题 1.数据逻辑结构包括________、________、_________ 和_________四种类型,其中树形结构和图形结构合称为_____。 2.在线性结构中,第一个结点____前驱结点,其余每个结点有且只有______个前驱结点；最后一个结点______后续结点,其余每个结点有且只有_______个后续结点。 3.在树形结构中,树根结点没有_______结点,其余每个结点有且只 有_______个前驱结点；叶子结点没有________结点,其余每个结点的后续结点可以_________。 4.在图形结构中,每个结点的前驱结点数和后续结点数可以 _________。 5.线性结构中元素之间存在________关系,树形结构中元素之间存 在______关系,图形结构中元素之间存在_______关系。 6.算法的五个重要特性是_______、_______、______、_______、 《数据结构》填空作业题答案 第 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：底部剪力法。 钢筋混凝土5层框架经质量集中后计算简图如下图所示，各层高均为3m ， 集中于各楼层的重力荷载代表值分别为： 1500kN G =，2550kN G =，3580kN G =，4600kN G =，5450kN G =。结构阻尼比0.05ξ=，自振周期为10.55s T =，Ⅰ1类 场地类别，设计地震分组为第一组，抗震设防烈度为8度（设计基本地震加速度为0.30g ）。按底部剪力法计算结构在多遇地震时的水平地震作用及地震剪力。 3580kN =2550kN =1500kN =（a ）计算简图 4600kN =5450kN = 解：查《建筑设计抗震规范》表5.1.4知，8度多遇地震，αmax=设计地震分组为第一组， Ι类场地，取Tg= Tg=＜T1=＜5Tg= α1=（Tg/T1）r η2αmax =（）××=≈ 查《建筑设计抗震规范》表5.2.1知，T 1=＞=×= 取δn=T1+=×+= 总水平地震作用标准值： F EK =α1Geq=×（500+550+580+600+450）×85%= 各楼层水平地震作用标准值： Fi=G i H i F EK (1-δn)/∑G j H j (i=1,2,3n) ∑G j H j =500×3 +550×6+580×9+600×12+450×15=23970KN ·m F 1=[500×3××]/23970= F 2=[550×6××]/23970= F 3=[580×9××]/23970= F 4=[600×12××]/23970= F 5=[450×15××]/23970= 计算各楼层的层间地震剪力 V 1= F 1+ F 2+ F 3+ F 4+ F 5=++++= V 2= F 2+ F 3+ F 4+ F 5=+++=152KN V 3= F 3+ F 4+ F 5=++= V 4= F 4+ F 5=+= V 5=F 5= 题目3：怎样判断土的液化如何确定土的液化严重程度，并简述抗液化措施。 答：饱和松散的砂土或粉土（不含黄土），地震时易发生液化现象，使地基承载力丧失或减弱，甚至喷水冒砂，这种现象一般称为砂土液化或地基土液化。其产生的机理为：地下水位以下的饱和砂土和粉土颗粒在地震作用下，土颗粒之间有变密的趋势。因空隙水不能及时排出，土颗粒就处于悬浮状态，形成如同液体一样的现象，即所谓的土的液化现象。地基土液化判别过程可以分为初步判断和标准贯入试验判别两大步骤。下面分别予以介绍。 1、初步判断 饱和的砂土或粉土（不含黄土）当符合下列条件之一时，可初步判别为不液化或不考虑液化影响： （1）地质年代为第四纪晚更新世（Q3）及其以前时且处于烈度7度或者8度地区时可判为不液化土。 （2）粉土的粘粒（粒径<0.005mm ）含量百分率当烈度为7度时大于10％、当烈度为8度时大于13％、当烈度为9度时大于16％，可判为不液化土。 （3）浅埋天然地基，当地下水位深度和覆盖非液化土层厚度满足下式之一时，可不考虑液化影响。 03w b d d d >+- 02 u b d d d >+- 第1章算法 一、选择题 1.算法的时间复杂度是指（）。 A）执行算法程序所需要的时间 B）算法程序中的指令条数 C）算法执行过程中所需要的基本运算次数 D）算法程序的长度 2.算法的空间复杂度是指（）。 A）算法程序的长度 B）算法程序所占的存储空间 C）算法执行过程中所需要的存储空间 D）算法程序中的指令条数 3.下面（）的时间复杂度最好（即执行时间最短）。 log) A）O(n ) B）O(n 2 log ) D）O(n2) C）O(n n 2 4.下面累加求和程序段的时间复杂度为（）。 int sum(int a[],int n) { int i, s=0; for (i=0;i int i=0,s1=0,s2=0; while(i 习题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 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】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以及它们之间的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; 绪论部分： 2、简述环境问题的分类？（10分） 答：环境问题是多方面的，但大致可分为两类：原生环境问题和次生环境问题。由自然力引起的为原生环境问题，也称为第一环境问题。由于人类生产和生活引起生态系统破坏和环境污染，反过来又危及人类自身和生存和发展的现象，为次生环境问题，也叫第二环境问题。原生环境问题和次生环境问题很难截然分开，它们之间常常存在着某种程度的因果关系和相互作用。 4、什么是环境化学，学习环境化学有什么意义？（10分） 答：环境化学是一门研究有害化学物质在环境介质中的存在、化学特性、行为和效应及其控制的化学原理和方法的科学。 意义：用来掌握污染来源，消除和控制污染，确定环境保护决策，以及提供科学依据诸方面都起着重要的作用。 5、简述环境化学的分支学科。（10分） 答：主要包括6类。 ①环境分析化学：是研究化学品的形态、价态、结构、样品前处理和痕量分析的学科。 ②环境污染化学：大气、水体和土壤环境化学，元素循环的化学过程。 ③污染控制化学：主要研究与污染控制有关的化学机制及工艺技术中化学基础性问题。 ④污染生态化学：是研究化学污染物在生态系统中产生生态效应的化学过程的学科。 ⑤环境计算化学：主要利用有效的数学近似以及电脑程序计算分子的性质。 ⑥环境生物化学：是研究环境化学品对生命影响的学科。 第一章： 1、地球环境主要由哪些圈层构成？英文单词？各之间有什么联系？各有哪些性 质？（10分） 答：地球环境主要由大气圈（atmosphere）、水圈（hydrosphere）、土壤圈（pedosphere）、岩石圈（lithosphere）和生物圈（biosphere）构成。 联系：大气圈、水圈、土壤圈和生物圈共同组成了地球环境系统，每个圈层都离不开 第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={ 第一章 1．在数据结构中，从逻辑上可以把数据结构分为（C ） A．动态结构和静态结构 B. 紧凑结构和非紧凑结构 C．线性结构和非线性结构 D. 内部结构和外部结构 ● 2.在数据结构中,与所使用的计算机无关的是( A ) A. 逻辑结构 B. 存储结构 C. 逻辑和存储结构 D. 物理结构 3.下面程序的时间复杂度为____O（mn）_______。 for (int i=1; i<=m; i++) for (int j=1; j<=n; j++ ) S+=i 第二章线性表 ●链表不具备的特点是（A） A 可以随机访问任一结点（顺序） B 插入删除不需要移动元素 C 不必事先估计空间 D 所需空间与其长度成正比 2. 不带头结点的单链表head为空的判定条件为（A ），带头结点的单链表head为空的判定条件为（B ） A head==null B head->next==null C head->next==head D head!=null ●3.在线性表的下列存储结构中，读取元素花费时间最少的是（D） A 单链表 B 双链表 C 循环链表 D 顺序表 ● 4.对于只在表的首、尾两端进行手稿操作的线性表，宜采用的存储结构为(C) A 顺序表 B 用头指针表示的单循环链表 C 用尾指针表示的单循环链表 D 单链表 ● 5.在一个具有n 个结点的有序单链表中插入一个新的结点，并保持链表元素仍然有序， 则操作的时间复杂度为( D ) A O(1) B O(log2n) C O(n2) D O(n) ● 6.在一个长度为n (n>1)的单链表上，设有头和尾两个指针，执行(B)操作与链表的长 度有关 A 删除单链表中第一个元素 B 删除单链表中最后一个元素 C 在第一个元素之前插入一个新元素 D 在最后一个元素之后插入一个新元素 ●7.与单链表相比，双向链表的优点之一是(D) A 插入删除操作更简单 B 可以进行随机访问 C 可以省略表头指针或表尾指针 D 顺序访问相邻结点更容易 ●8.若list是某带头结点的循环链表的头结点指针，则该链表最后那个链结点的指针域 (头结点的地址)中存放的是( B ) A list的地址 B list的内容 C list指的链结点的值 D 链表第一个链结点的地址 ●9.若list1和list2分别为一个单链表与一个双向链表的第一个结点的指针，则( B ) A list2比list1占用更多的存储单元 B list1与list2占用相同的存储单元 C list1和list2应该是相同类型的指针变量 D 双向链表比单链表占用更多的存储单元 10.链表中的每个链结点占用的存储空间不必连续，这句话正确吗？ (不正确) 11. 某线性表采用顺序存储结构，元素长度为4，首地址为100，则下标为12的（第13个）元素的存储地址为148。V 100+4*12=148 11.在顺序表的（最后一个结点之后）插入一个新的数据元素不必移动任何元素。 12.若对线性表进行的操作主要不是插入删除，则该线性表宜采用（顺序）存储结构，若频繁地对线性表进行插入和删除操作，则该线性表宜采用( 链 )存储结构。 结构力学（一）辅导资料二 主题：第三章静定梁和静定平面刚架 第一节单跨静定梁计算 第二节多跨静定梁计算 学习时间：2010年4月26日－5月2日 内容： 这周我们将学习第三章静定梁和静定平面刚架。 第三章静定梁和静定平面刚架 第一节单跨静定梁计算 第二节多跨静定梁计算 本章的学习要求及需要掌握的重点内容如下： 1、熟练掌握用简易方法迅速绘制单跨静定梁的内力图； 2、掌握多跨静定梁的层次关系和内力图的绘制； 3、熟练区段叠加原理； 4、掌握斜梁与普通直梁受力的异同点。 基本概念：静定单跨梁的计算，叠加法绘制直杆弯矩图，简支斜梁的计算，静定多跨梁约束力的计算与几何组成，静定多跨梁内力图的绘制。 知识点：静定梁的内力分析、内力计算及内力图的绘制。 一、单跨静定梁计算 静定结构是指结构的约束反力及内力完全可由静力平衡条件唯一确定的结 构、其内力计算是结构位移和超静定结构内力计算的基础。静定单跨梁是组成各种结构的基本构件之一。是建筑工程中用得最多的一种结构型式。常见的静定单跨梁有简支梁、悬臂梁和伸臂梁，如图3．1所示。 1、用截面法求指定截面的内力 在任意荷载作用下，平面杆件的任一截面上一般有三个内力分量，轴力N，剪力Q和弯矩M，见图3.2。 计算指定截面内力的基本方法是截面法，即将指定截面切开，取截面任一侧部分为隔离体，利用隔离体的平衡条件可求出此截面的三个内力分量。 轴力等于截面一边所有的外力沿杆轴切线方向的投影代数和。轴力以拉为正，以压为负。 剪力等于截面一边所有外力沿杆轴法线方向的投影代数和。剪力以绕隔离体顺时针转者为正，反之为负。 弯矩等于截面一边所有外力对截面形心的力矩代数和。弯矩以水平梁下侧纤维受拉为正，反之为负。 作业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;数据结构习题及答案——严蔚敏
《数据结构》填空作业题(答案)
大连理工大学(工程抗震)大作业
数据结构习题及答案概论
数据结构习题及参考答案 .
数据结构习题与答案
数据结构作业(附答案)
数据结构作业及答案
大连理工大学-环境化学-所有作业答案
作业-《数据结构习题集(C语言版)严蔚敏》答案汇编
【免费下载】数据结构习题及答案
大工10春《结构力学(一)》辅导资料二
数据结构作业答案