华北计算技术研究所专业课试题及答案

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。华北计算技术研究所专业课试题参考答案一、填空题 ( 15 分 )1. 数据结构是相互之间存在一种或多种特定关系的数据元素 的集合。一般有下列四种基本结构 :集合 、线性结构、树状结构和 图状结构 ( 或网状结构 )。2. 在顺序表中插入或删除一个元素 , 需要平均移动 表中一半 ( 或 n/2 个) 元素 , 具体移动的元素个数与 表长和该元素在表中的位置 有关。3. 0 个字符的串称为空串 , 它的长度为 0 。4.矩阵压缩存储的基本思想是:值相同的多个元素只分配一个存储空间,零元素不分配空间。5.深度为 k 的二叉树至多有2k-1个结点 ,至少有k 个结点。6. 图的深度优先搜索遍历类似于树的 先根 遍历 ; 图的广度优先搜索遍历类似于树的 按层次 遍历。二、选择题 ( 20 分 )1. 时间复杂性最好 , 即执行时间最短的是 :B( A) O(n)( B) O(log2n)( C) O(nlog2n)( D) O(n2)2.具有6 个顶点的无向图至少有D条边才能确保是一个连通图。( A) 15( B) 7( C) 6( D) 53.在所有排序方法中,关键字比较的次数与记录的初始排列次序无关的是:D( A)希尔排序( B)起泡排序( C)插入排序( D)选择排序资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。4.若用一个大小为6 的数组来实现循环队列,且当前rear和 front的值分别为0 和3,当从队列中删除一个元素,再加入两个元素后, rear和front的值分别为:C。（ A ）1 和 5( B) 2和 4 ( C) 4和 2 ( D) 5和15.设栈的长度为 3,入栈序列为( A)A, B, C, D, E, F( C)C, B, A, F, E, DA、 B 、 C、 D、 E 、 F, ( B) B, A, D, C, F, E ( D) D, C, B, A, F, E不可能产生的出栈序列是:D。三、判断题。 ( 10 分)请判断下列说法的对错。1.数据元素是数据的最小单位。错2.串的三种存储表示方法为定长顺序存储表示、堆分配存储表示和块链存储表示。对3.一个稀疏矩阵的转置矩阵依然是稀疏矩阵。对4. 树状结构中 , 度为 0 的结点称为树根。 错5. 完全二叉树不一定是满二叉树 , 但满二叉树一定是完全二叉树。 对四、根据下列要求分别编写算法。( 20 分)1. 设计算法 , 判断一个算术表示式的圆括号是否正确配对。参考答案 :#include #include ”stack.h ”Int PairBracket(char *S)/ 检查表示式中括号是否配对int i;资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。SeqStack T;/定义一个栈InitStack (&T);for(i=0;idata=sa.elem1;T=ptr1;for(i=2;idata=sa.elemi;j=i/2;if(i-j*2) ptrj-rchild=ptri; /I是 j 的右孩子else ptrj-lchild=ptri;/I是 j 的左孩子return OK;五、回答问题。 ( 20 分)1. 设有上三角矩阵 (a ij ) nxn, 将其上三角元素逐行存于数组 Bm 中( m充分大 ) , 使得 Bk=a ij且 k=f1(i)+f2(j)+c 。试推导出函数 f , f2和常数 c(要求 f和 f中不含常数项 ) 。112参考答案 :kni( nj )i (i 1)j )1, (i2则得 :f1 (i )(n1 )i1 i 2f 2 ( j )j22c(n1)2.写出下图中所示的二叉树的先序序列、中序序列和后序序列。1234567参考答案 :89资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。前序 :中序 :后序 :六、下图是一个有向图 , 其中每条弧段上的数字表示该弧段的权值。利用 Dijkstra 算法求图中从顶点 a 到其它各顶点间的最短路径 , 写出执行算法过程中各步的状态。 ( 15 分)b4156e89a2cg410125fd3参考答案 :终点cdefgSbDist15212a,cK=1(a,c)(a,d)(a,b)1512106a,c,fK=2(a,d)(a,c,e)(a,c,f)(a,b)15111016a,c,f,eK=3(a,c,f,d)(a,c,e)(a,c,f,g)(a,b)151116a,c,f,e,d K=4(a,c,f,d)(a,c,f,g)(a,b)1514a,c,f,e,d,gK=5(a,c,f,d,g)(a,b)15a,c,f,e,d,g,bK=6(a,b)资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。故 :a 到各点最短路径分别为 :bcdefg1521110614七、假设按下述递归方法进行顺序表的查找 : 若表长 =10, 则进行顺序查找 , 否则进行折半查找。试画出对表长 n=50 的顺序表进行上述查找时 , 描述该查找的判定树 , 并求出在等概率情况下查找成功的平均查找长度。( 20 分 )参考答案 :251238618314417131926323945281420273340465111723303643492437其等概率查找时查找成功的平均查找长度为:ASLsucc1 (1 1 2 2 3 4 (4 5 67 8) 8 9 3) 5.6850八、将下列 C+程序的类定义和主函数分离,改成多文件结构。主函数使用类的方式采取包含类定义头文件的方法。并写出运行结果。( 15 分 )#include class Cat资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。public:int GetAge( );void SetAge(int age);void Meow( ); /喵喵叫protected:int itsAge;int Cat:GetAge( )returen itsAge;void Cat:SetAge(int age)itsAge=age;void Cat:Meow( )cout ”Meow.n”;void main( )Cat frisky;Frisky.SetAge(5);Frisky.Meow( );