考研专业课：北京工业大学计算机真题（2000）

考研族

　　2014 考研专业课大纲已经发布，考生要对照大纲的变化好好复习，调整自己的规划。同时要关注各高校历年真题，利用真题和大纲做好考前的强化备考。文都教育 考研专业课频道为考生提供10大高校计算机复习考题，希望考生认真利用这些真题，仔细研究，寻找突破点，及时的查漏补缺，复习好计算机专业课，下面请看。
　　北京工业大学2000年考研试题
　　注意：试题中编程一律要求采用类PASCAL语言。
　　一、选择(单选、多选)与填空题
　　1.(10分 每问2分)下列内部排序算法中：
　　A.快速排序 B. 直接插入排序 C. 二路归并排序 D. 简单选择排序
　　E. 起泡排序 F. 堆排序
　　① 其比较次数与序列初态无关的是( )
　　② 不稳定的排序是( )
　　③ 在初始序列已基本有序(除去n个元素中的某个k元素后即呈有序，k
　　④ 排序的平均时间复杂度为O(n?logn)的算法是( )为O(n?n)的是( )
　　2.(3分)在用败者树进行k路平衡归并的外部排序算法，其总的归并效率与k ( )
　　A 有关 B 无关
　　3.(4分)在m阶B-树的某结点中插入一个关键字而引起的结点分裂，则其中原有( )个关键字;从m阶B-树的某结点中删除一个关键字而引起的结点合并，则其中原有(　　)个关键字
　　二、简答题
　　1.(9分)对角矩阵A(n*n)按行主序压缩存储于一维数组B中，其中A[i,j]=B[k]，请求出用i,j表示的k以及用k表示的i和j.
　　2.(6分)画出广义表的存储结构示意图(两种结构中的任意一种皆可，要求共享相同子表)。A=(c,(a,b),(d,(c,(a,b))),((c,(a,b)),((()))))
　　3.(5分)求含有n个结点、采用顺序存储结构的完全二叉树中的序号最小的叶子结点的下标。要求写出简要步骤。
　　三、(8分)采用哈希函数H(k)=3*k mod 13并用线性探测开放地址法处理冲突，在数列地址空间[0..12]中对关键字序列22，41，53，46，30，13，67，51(1)构造哈希表(画示意图，并求：(2)装填因子;等概率下(3)成功的和(4)不成功的平均查找长度。
　　四、(15分)循环链表a和b的结点值为字母，其中a表非递减有序，下面的程序欲构造一个递增有序的循环连表c，其中结点的值为同时在a，b两链表中出现的字母，且c中字母不重复，请补上程序中空缺的部分，并估计算法的时间复杂度。(设a，b的结点数分别为m，n)
　　TYPE
　　link=^node;
　　node=record
　　key:char;
　　next:link
　　end;
　　proc jj(a,b:link; var c:link);
　　bar p,q,r,s:link;
　　begin
　　new(c);c^.next:=c;
　　q:=a; p:=a^.next;
　　while pa do
　　[填空①
　　while p^.key=p^.next^.key do [q:=p; p=p^.next];{跳过相同字母｝
　　r:=b^.next ; 填空②;
　　while r^.key p^.key do r:=r^.next;
　　if rb then
　　[ s:=p; q^.next:=p^.next; 填空③;
　　s^.next:=c^.next; c^.next:=s; c:=s ]
　　else [ q:=p; p:=p^.next ]
　　]; c:=c^.next
　　end; 　　　　　　　　　算法时间复杂度为0(填空④)
　　五、(10分)编程求以孩子兄弟表示法存储的森林的叶子结点数。要求描述结构。
　　六、(20分)已有邻接表表示的有向图，请编程判断从第u顶点至第v顶点是否有简单路径，若有则印出该路径上的顶点。要求：先描述图的存储结构，并简述算法思路;查找邻接点等图的运算要自己实现。(尽量采用非递归算法，满分15分)
　　七、(10分)编写程序段，利用中序全线索树求其中任意结点p^的前序后继点，结果仍用p指出。要求先描述结构和算法思路。设线索树不带头结点，其中序序列第一结点的左标志和最后结点的右标志皆为0(非线索)，对应指针皆为空。
　　上面是北京工业大学2000年考研专业课 计算机的计算机组成原理真题，望考生通过做真题，考生能够发现自己的知识漏洞，及时的补充和纠正，争取精确、深度的把握专业课知识，打好专业课的基础。最后，都希望大家考研成功，加油!
　　更多考研专业课信息关注 文都教育