北科大2006年《计算机组成原理及数据结构》考研真题.pdf

北科大计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解详见：网学天地(www.e-)；咨询QQ:2696670126:4b-4三.(24分)设记录的关键字(key)集合K-11,2,13,27,6,15,5,11.以K为权集，构造一棵Huffman树，并求该树的带权路径长度WPL):2.设Hash表表长m=l6,选取Has函数的方法为“保留余数法”，处理冲突的方法为“线性探测再散列”，请依次取K中各值，构造满足所给尔件的Hsh表结构：并在等概率条件下，求对该表查找成功时的平均查找长度(ASL):3.设选取的增量序列为(4,2,1)，写出对K按“希尔(shl)排序”算法排序时，各趟排序结束时按升序排列的结果，四.(20分此题统考生做)含有两个连通分量的无向图G如下：y0v52v3com1.设顶点v0,v1,P的序号分别为0,1，,7,请写出图G的邻接矩阵，画出图G的邻接表结沟：2.若无向图采用邻接表结构存储，请利用“深度优先”搜索图的方法，用C语言函数形式写出求图中各连通分量顶点集的算法：CONNECT-COMP(Gnj)其中Gn为顷点表，n为风中顶点数。注：算法前应写出图的邻接表结构类型的描述；算法中可调用函数：firstadj(G,v)、nextadj(Gv,u),分别求图G中顶点v的第一邻接点和顶点v关于顶点山的下一邻接点。五.(20分此题单考生做)设一棵二叉树已用链式结构存储，根结点指针为BT,请采用先序非递归遍历二叉树的方法，用C语言函数形式写出求二叉树中吲子结点个数的算法：PREORDER-CL(BT)。注：算法前应写出二叉树结点类型的描述；算法中可调用栈操作的基本函数。第4页