2013年广东工业大学考研真题830数据结构与离散数学

广工数据结构anyview 80道上机题1.void Descend(int &x, int &y, int &z)/* 按从大到小顺序返回x，y和z的值*/ {int t;if(x<z){t=z;z=x;x=t;}if(y<z){t=y;y=z;z=t;}if(y>x){t=x;x=y;y=t;}}2.Status Fibonacci(int k, int m, int &f)/* 求k阶斐波那契序列的第m项的值f */ {int *a;int i=1;if(k<2||m<0) return ERROR;if(m<k){if(m==k-1) f=1;else f=0;return OK;}a=(int*)malloc((m+1)*sizeof(int));for(i=0;i<k-1;i++) a[i]=0;i=k+1;a[k-1]=1;a[k]=1;while(i<=m){a[i]=2*a[i-1]-a[i-k-1];i++;}f=a[m];return OK;}3.void Scores(ResultType *result, ScoreType *score)/* 求各校的男、女总分和团体总分, 并依次存入数组score *//* 假设比赛结果已经储存在result[ ]数组中, *//* 并以特殊记录{"", male, ' ', "", 0 }（域scorce=0）*//* 表示结束*/{int i;for(i=0;result[i].score!=0;i++){score[result[i].schoolname-'A'].totalscore+=result[i].score;if(result[i].gender==male)score[result[i].schoolname-'A'].malescore+=result[i].score;elsescore[result[i].schoolname-'A'].femalescore+=result[i].score;}}4Status Series(int ARRSIZE, int a[])/* 求i!*2^i序列的值并依次存入长度为ARRSIZE的数组a；*//* 若所有值均不超过MAXINT，则返回OK，否则返回OVERFLOW */{int i=1,b=1,na=1;while(i<=ARRSIZE){na*=i;b*=2;if(na*b>MAXINT) return OVERFLOW;a[i-1]=na*b;i++;if(i>ARRSIZE+1) return OVERFLOW;}return OK;}5float Polynomial(int n, int a[], float x)/* 求一元多项式的值P(x)。

830数据结构考试大纲Ⅰ考试形式一、试卷满分及考试时间本试卷满分为150分，考试时间为180分钟二、答题方式答题方式为闭卷、笔试Ⅱ考查目标1.理解数据结构的基本概念；掌握数据结构的逻辑结构、存储结构及其差异，以及各种基本操作的实现。

2.掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。

3.能够选择合适的数据结构和方法进行问题求解。

一、基本概念和术语（一）数据元素、数据结构、抽象数据类型等概念（二）算法设计的基本要求（三）语句的频度和估算时间复杂度二、线性表（一）线性表的定义和基本操作（二）线性表的实现1．顺序存储结构2．链式存储结构3．线性表的应用三、栈、队列和数组（一）栈和队列的基本概念（二）栈和队列的顺序存储结构（三）栈和队列的链式存储结构（四）栈和队列的应用（五）特殊矩阵的压缩存储四、树与二叉树栈（一）树的概念（二）二叉树1．二叉树的定义及其主要特征2．二叉树的顺序存储结构和链式存储结构3．二叉树的遍历4．线索二叉树的基本概念和构造5．二叉排序树6．平衡二叉树（三）树、森林1．树的存储结构2．森林与二叉树的转换3．树和森林的遍历（四）树的应用1．特价类问题2．哈夫曼(Huffman)树和哈夫曼编码五、图（一）图的概念（二）图的存储结构及基本操作1. 邻接矩阵2.邻接表（三）图的遍历1．深度优先搜索2．广度优先搜索（四）图的基本应用1．最小（代价）生成树2．拓扑排序3．关键路径4．最短路径六、查找（一）查找的基本概念（二）顺序查找法（三）折半查找法（四）B-树（五）散列(Hash)表及其查找（六）查找算法的分析及应用七、内部排序（一）排序的基本概念（二）插入排序1．直接插入排序2．折半插入排序（三）气泡排序（bubble sort）（四）简单选择排序（五）希尔排序（shell sort）（六）快速排序（七）堆排序（八）二路归并排序(merge sort)（九）基数排序（十）各种内部排序算法的比较（十一）内部排序算法的应用Ⅲ特别推荐1．严蔚敏、吴伟民, 数据结构（C语言版）,清华大学出版社出版2．严蔚敏, 吴伟民,《数据结构习题解析》,清华大学出版社出版。

广东工业大学广工大835材料科学基础2014考研真题答案2014年835真题答案详解一、填空1、【1】EIH【2】EIJ【3】9°2、【4】18（点阵几何点的数目）【5】8【6】0.343、【7】零维4、【8】Su3sb2【9】非稳态化合物5、【15】固溶体【16】中间相【17】电子浓度【18】原子尺寸【19】电负性【20】固溶体【21】电负性【22】金属化合物6、【23】吞并长大7、【24】铁素体【25】奥氏体二、判断题1、错非晶态材料，常被称为金属玻璃，其结构特点在于短程有序而长程无序。

2、对面心立方:（111），[110] 体心立方：（110），[111] 六方结构：（0001），[1̅1̅20]3、错扩散第一定律阐述了一个基本且恒定的物理现象，即扩散过程中的浓度变化率（或扩散通量）不随时间发生变化，保持恒定。

这一定律强调了扩散行为在特定条件下的稳定性和可预测性。

4、错淬火过程：淬火处理会导致材料内部晶格结构发生畸变，这种结构变化进而引起电阻率的增加，使得材料的导电性能下降。

退火效应：随后进行的退火处理，通过加热并缓慢冷却的方式，能够使淬火过程中产生的晶格畸变得到恢复，从而降低了电阻率。

这一变化直接提升了材料的导电性能，使其导电性变好。

冷加工影响：另一方面，冷加工（如冷轧、冷拉等）过程会引入额外的应力和缺陷到材料中，导致电阻率上升，进而使导电性能变差。

退火态与冷加工态对比：综上所述，相较于冷加工后的状态，退火态的材料因其更低的电阻率和更好的晶格完整性，展现出更优的导电性能。

因此，退火态材料比冷加工态材料的导电性更好。

5、对同2015.56、错 Cu与Ni在液态及固态条件下均能实现无限互溶，这一现象可通过匀晶相图来直观表示。

在匀晶相图中，Cu与Ni的混合展示了从一种纯金属（如纯Cu或纯Ni）逐渐过渡到另一种纯金属时，中间不形成任何新相（即化合物或中间相），而是保持固溶体状态，且溶解度在液固两相中均为无限大。

数据结构复习样题答案一.单项选择题《共12分〉I. B 2. A 3. A 4. D 5. C 6. D 7. B 8. C二.填空题（共12分）9.数据对象、数据关系、基本操作10.从表中任一结点出发均可找到表中其他结点II.字符依次对应相同且长度相同12.3313.各结点均无左孩子14.n-115.在排序过程中需要访问外存16.散列三.解答题（共36分〉成功的平均査找长度=42/1218. （10分）已知一个长度为12的表为（Jan, Feb, Mar, Apr, May, June，July, Aug, Sep, Oct, Nov, Dec）（1）试将表中元素依次插入到一棵初始为空的二叉排序树（字符串之间按字典顺序比较大小）。

画出该二叉排序树，并求出等概率情况下查找成功的平均查找长度。

（2）设哈希表长度为13,哈希函数H （k） =Li/2」，其中i为关键字k中第一个字母在字母表中的序号（例如A和D的序号分别为1和4）,用链地址法解决冲突。

请画出通过依次插入表中元素所构造的散列表，并求出在等概率情况下查找成功的平均查找长度。

0 1 23456789 10 11 1219.(5分)假设电文中仅由a到h共8个字母组成，字母在电文中出现的频度依次为7,19, 2, 6, 32, 3, 21, 10请画出由此构造的哈夫曼树(要求树中所有结点的左右孩子必须是左大右小)，并写出这8 个字母相应的哈夫曼编码。

20.(8分)若对序列(25, 19, 7, 41, 29, 12, 23, 26)按升序排序，请分别给出(1)步长为4的一趟希尔排序的结果；(2)初始大根堆。

答：(1) (12, 7, 25, 29, 19, 23, 26, 41)(2) (41, 26, 23, 25, 29, 12, 7, 19)字符哈夫曼码a111b010c01111d0110e00f OHIO810h110算法题（共30分〉22. （5分）函数f22定义如下，其中函数调用Insert （L, i, k）在顺序表L的第i位置插入k ovoid f22(SqList &L, int i) { if(i > 0) {f22(L, i-1);for (int k=l; k<=i; k++)Insert(L, i, k);}}设有空顺序表L =(),请写出调用递归函数f22(L,3)后(1)L的长度：6(2)L = ( 1, 2, 3, 2, 1, 1 )23. （5分）算法f23（L）将带头结点的单链表L逆置。