考研专业课：东北大学计算机真题（2002）

考研族

　　2014 考研专业课大纲已经发布，考生要对照大纲的变化好好复习，调整自己的规划。同时要关注各高校历年真题，利用真题和大纲做好考前的强化备考。文都教育 考研专业课频道为考生提供10大高校计算机复习考题，希望考生认真利用这些真题，仔细研究，寻找突破点，及时的查漏补缺，复习好计算机专业课，下面请看。
考研专业课：东北大学计算机真题（2002）
　　一、回答下列问题：(24分)
　　1， 如果用一个循环数组q[0..m-1]表示队列时，该队列只有一个队列头指针front，不设队列尾指针rear，而改置计数器count用以记录队列中结点的个数。
　　1) 编写实现队列的基本运算：判空、入队、出队(3分)
　　2) 队列中能容纳元素的最多个数是多少?(1分)
　　2、设有对角矩阵a[1..n,1..n]把非零元素按列存储在向量b[1..3*n-2]中，使得b[k]=a[I,j].
　　求：(1)用I,j表示k的下标变换公式(2分)
　　(2)用k表示I,j的下标变换公式(2分)
　　3、设二叉排序树中关键字由1到1000的整数组成，现要查找关键字为363的结点，下述评关键字序列哪一个不可能是在二叉排序树中找到的序列?说明原因。(4分)
　　(1)51，250，501，390，320，340，382，363
　　(2)24，877，125，342，501，623，421，363
　　4、设有n个无序元素，按非递减次序排序，但只想得到前面长度为k的部分序列，其中n>>k，最好采用什么排序方法?为什么?(2分)
　　如果有这样一个序列{59，11，26，34，17，91，25}，得到的部分序列是：{11，17，25}，对于该例使用所选择的方法实现时，共执行多少次比较?(3分)
　　5、在B-树和B+树中查找关键字时有什么不同?(2分)
　　6、写出对关键字序列{503，087，512，061，908，124，897，275，653，426}
　　建立一棵平衡二叉树的过程，并写出调整平衡时的指针变化。(5分)
　　二、解答下列问题：(10分)
　　1、 画出对长度为10的有序表进行二分查找的判定树并求其等概率时查找成功的平均查找长度(5分)。
　　2、 设有一组关键字{9，01，23，14，55，20，84，27}，采用哈希函数：H(key)=key mod 7 ，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di)mod10(di=1*1,2*2,3*3….)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度(5分)。
　　三、已知L为没有头结点的的单链表中第一个结点的指针，每个结点数据域存放一个字符，该字符可能是英文字母字符或数字字符或其他字符，编写算法构造三个以带头结点的单循环链表表示的线性表，使每个表中只含同一类字符。(要求用最少的时间和最少的空间)(15分)
　　四、对以二叉链表存储的非空二叉树，从右向左依次释放所有的叶子结点，释放的同时把结点值存放到一个向量中
　　要求：(1)用文字写出实现上述过程的基本思想(3分)
　　(2)写出算法(12分)
　　五、设二叉排序树已经以二叉链表的形式存储在内存中，使用递归方法，求各结点的平衡因子并输出。
　　要求：(1)用文字写出实现上述过程的基本思想(3分)
　　(2)写出算法(12分)
　　六、假设一个有向图g已经以右图所示的逆邻接表形式存储在内存中，
　　要求：(1)写出逆邻接表的存储结构定义(3分)
　　(2)用文字写出在逆邻接表上实现拓扑排序的基本思想(3分)
　　(3)写出在逆邻接表上实现拓扑排序的算法 (15分)。
　　上面是东北大学2002年考研专业课 计算机的真题，望考生通过做真题，考生能够发现自己的知识漏洞，及时的补充和纠正，争取精确、深度的把握专业课知识，打好专业课的基础。最后，都希望大家考研成功，加油!
　　更多考研专业课信息关注 文都教育