北科大2003年《数据结构》考研真题.pdf

北科大计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解详见：网学天地(www.e-);咨询QQ:2696670126北京科技大学2003年硕士研究生入学考试试题一、(30分)回答下列各题：1.简述数据结构中线性结构、层次结构和网状结构的特点。2.在算法正确的情况下，应从哪几个方面来衡量一个算法的优劣性？3.设当前队列Q中有n(n1)个元素，即Q=(a1,a2,an),请画出队列Q的链式存储结构。4.设二叉树中结点数为n（n1)，树中第i（1in)个结点的出度为od(),请写出n与树中各结点度之间的关系。5.若一棵h层的完全二叉树中叶子结点数为n,且第h层的结点数2，则h=?6.一个有向图在计算机存储器中的映像（或表示）通常有哪几种方法？7.求一个有向无环图的拓扑序列时，其结果为何不惟一？8.将n(n1)个结点组织成何种形态的二叉排序树时，对其查找时的时间复杂度为最佳？9.在构造一个Hash表的过程中，简述如何用“链地址法”来解决冲突10.在“快捷排序”、“堆排序”和“归并排序”三个排序算法中、当只需获取前几个最小关键字记录时，选取何种排序算法为最佳？二、(20分)算法填空：CO建立在单链表上的一个C语司描述算法如下，其中L为链表结点的指钟，请填充算法中tw.e-stmdys下划线的空白之处，并简述算法完成的功能。(注：答案请写在答卷纸上)typedef struct nodeintdata;struct node*next;Lnode)*link:void Selectsort(link L)int temp,不p-Lnext;while(3)if(q-datadata)(4)q-q-next;北科大计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解详见：网学天地(www.e-);咨询QQ:2696670126if(5)temp-p-data;p-data=minp-data;minp-data=temp;(6)三、(16分)设矩阵0010302000A=00015(行列下标i、满足：1i,5)00010000081.若将A视为一个上三角矩阵时，请画出对A进行“按行优先存储”的压缩存储表S,并写出A中元素之下标i,与表S中元素之下标k(1k5)之间的关系：2.若将A视为一个稀疏矩阵时，请用C语言描述稀疏矩阵的三元组表，并画出A的三元组表结构。四、（18分，此题统考生做)设记录的关键字集合：K=12,3,14,30,6,77,28,21.请依次取K中各值，用插入的方法构造一棵3阶的B-树（插入的过程可省略，画出B-树的最后结构即可)：2.简述B树结构有哪些基本的特点。五、(18分)设考试科目为：英语(E)、数学(M)、程序设t数据结构(DS)、数据库(DB)一操作系统(OS参加考试的学生报名表如：姓名科自1科日2科目3EDS王二DBOS张三DSDB李四EMDSDBOS1,请根据报名表对考试时间安排的约束条件，构造以“考试科目”为数据元素集合的数据结构模型（提示：当某两个科目的考试不能同时进行时，将其连线，构造出的模型应是一种网状结构)，用图G表示：2.写出图G的邻接矩阵，画出图G的邻接表结构：3.从图G中科目E出发，分别写出按“深度优先”和“广度优先”搜索方法遍历图G所得到的顶点序列。北科大计算机考研全套视频和资料，真题、考点、典型题、命题规律独家视频讲解详见：网学天地(www.e-);咨询QQ:2696670126六、(18分)设记录的关键字(key)集合：K=15,25,26,4,5,20,3,12,2l.以K为权值集合，构造一棵Hluffman树，并回答如何利用遍历二叉树的算法求Huffman树的带权路径长度(WPL)。2.设Hash表表长m=l6,选取Hash函数的方法为“除留余数法”，处理冲突的方法为“线性探测再散列”，请依次取K中各值，构造出满足所给事实上条件的Hash表：3.写出对K按“2路归并排序”方法排序时，各趟排序结束时的结果，并将K调整成个堆顶元素取最小值的堆。七、(30分，此题统考生做)算法设计：l.设二叉树采用链式结构存储，根结点指针为bt,结点的左、右子指针域分别为Lchild和Rchild,.请采用中序非递归遍历二叉树的方法，用C语言函数形式写出求二叉树bt的最大层数（即深度）的算法：Btdep(bt)了(注：算法中可调用栈操作的基本函数)002.设有n个顶点的有向图G采用大字链表结构存储，请用C语言描述十字链表种的项点顶点表和弧结点，并出求图G冲第i(Iin个顶点度的算法；Degree(G,i)。(注：有向图中某个顶点湾义为该顶点的入度与出度之租的之此题单考生做)循环队列Q8的当前状态如下11+front其中a,(0i3)为欧列Q中的元素，front和rear分别为队头和队尾指针（元素的下标）。1.写出队列Q的队空、队满判定条件及进队、出队操作的C语言描述语句：2.画出元素ao,a1,a2,a3出队、元素a4,a5,a6,a进队后队列Q的状态。九、(30分，此题单考生做)算法设计：1.设n个十进制整数己存入数组An中，请利用栈技术，用C语言函数形式写出将An中各数据转换成八进制数并存入数组Bn的算法：Convert(A,B)。(注：算法中可调用栈操作的基本函数)2.设二叉树采用链式结构存储，根结点指针为bt,结点的左、右子指针域分别为Lchild和Rchild,请采用按层次遍历二叉树的方法，用C语言函数形式写出将二叉树中每一结点的左右子树相互交换的算法：Exchange(bt)。(注：算法中可调用队列操作的基本函数)