广东工业大学计算机学院数据结构历年考研真题

广工数据结构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)。

目录
2014年广东工业大学计算机学院832计算机组成原理考研真题 (2)
2013年广东工业大学计算机学院832计算机组成原理考研真题 (7)
2012年广东工业大学计算机学院832计算机组成原理考研真题 (13)
2011年广东工业大学计算机学院832计算机组成原理考研真题 (18)
2005年广东工业大学计算机学院419计算机组成原理考研真题 (23)
2014年广东工业大学计算机学院832计算机组成原理考研真题
2013年广东工业大学计算机学院832计算机组成原理考研真题
2012年广东工业大学计算机学院832计算机组成原理考研真题
2011年广东工业大学计算机学院832计算机组成原理考研真题
2005年广东工业大学计算机学院419计算机组成原理考研真题。

广工数据结构答案【篇一：广工2015数据结构复习题目及答案】>第一章绪论单项选择题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．在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是____ __。

a. n2b. nlognc. nd. logn7．设使用某算法对n个元素进行处理，所需的时间是t(n)=100nlog2n+200n+2000，则该算法的渐近时间复杂度为____ ___。

a. o(1)b. o(n)c. o(200n)d. o(nlog2n)cdcbbdd第二章线性表单项选择题1．链表不具有的特点是____ ____。

a. 可随机访问任一元素b. 插入和删除时不需要移动元素c. 不必事先估计存储空间d. 所需空间与线性表的长度正比2．设顺序表的每个元素占8个存储单元。

第1个单元的存储地址是100，则第6个元素占用的最后一个存储单元的地址为。

a. 139b. 140c. 147d. 1483．在线性链表存储结构下，插入操作算法a. 需要判断是否表满b. 需要判断是否表空c. 不需要判断表满d. 需要判断是否表空和表满4．在一个单链表中，若删除p所指结点的后继结点，则执行。

数据结构复习样题答案一.单项选择题《共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逆置。