2013年哈工大计算机科学与技术专业854考研真题 I．数据结构部分 一、单项选择题 1. 有一个100*90整型数的稀疏矩阵非0元素有10个，设每个整型数点2字节，则用三元组表示该矩阵时，所需的字节数为（1）。 A.60 B.66 C.180 D.33 2. 下列内部排序算法中，其比较次数与序列初始状态无关的是（2）。 A.快速排序 B.直接插入排序 C.二路归并 D.选择排序 3. 若度数为m的哈夫曼树中，其叶子结点的个数为n，则非叶子结点的个数为（3）。 A.n-1 B.n/(m-1) C.(n-1)/(m-1) D.(n+1)/(m+1)-1 4. 长度为12有序表，按折半查找法对该表进行查找，以等概率查找表内各元素，则查找成功时所需要的平均比较次数为（4）。 A.35/12 B.36/12 C.39/12 D.43/12 5. 设有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行（5）次探测。 A.K-1 B.K C.K+1 D.K(K+1)/2 6. 有n个初始归并段，采用K路归并时，所需要的归并遍数是（6）。 A.lognk B.log2k C.log2n D.logkn 7. 有n个顶点，e条边的有向图采用邻接存储，若删除与顶点Vi相关的所有边，其时间复杂度为（7）。 A.O(n) B.O(e) C.O(max(n, e)) D.O(n*e) 8. 在平衡二叉树中插入一个结点造成不平衡，设最低的不平衡结点为A，并已知插入后A的左子树根的平衡度为0，右子树根的平衡度为1，则应作（8）型的调整达到平衡。。 A.LL B.LR C.RL D.RR 9. 一棵具有n个非叶子结点完全二叉树的线索树，含有多少条线索（9）。 A.2n+1或2n B.2n+2或2n+1 C.2n+1或2n-1 D.2n+2或2n-2 10. 在某森林的二叉树表示中，结点M和结点N是同一父节点的左儿子和右儿子，则在该森林中（10）。 A.M、N具有同一双亲 B.M、N可能没有共同祖先 C.M是N的儿子 D.M是N的左兄弟 二、填空题 11. 高度为h的完全二叉树至少有（11）个结点。 12. N个结点的k叉树（k≥2）的k叉链表中有（12）空指针。 13. 对具有n个元素的顺序存储的有序表和顺序存储的无序表进行顺序查找，在等概率的情况下，查找不成功时的平均查找长度分别为（13-1）、（13-2）。 14. M阶B-树中，当有关键字插入导致相关结点分裂时，原结点上有（14）个关键字。 15. 以比较为基础的内部排序的时间复杂度的下界是（15）。 16. 完全二叉树的顺序存储序列为ABCDEFG，其后序遍历的序列为（16）。 17. 在AOE网络中，关键活动是指（17-1），缩短（17-2）活动的持续时间，可以提前完成工程。 18. 求最短路径的Dijkstra算法和最小生成树的Prim算法之间的主要区别（18）。 三、简答题 19. 从大规模数据（例如1亿个数）表中取前100个值，给出一种高效算法并描述算法思想，阐述选择该算法的理由。 20. 给出判断一个有向图是否存在拓扑排序的算法；给出图-1所示有向图的拓扑序列。 四、算法设计题 按下列要求设计算法： （1） 描述算法设计的基本思想； （2） 根据设计思想，采用C或C++或Java语言描述算法； （3） 分析算法时间复杂度和空间复杂度。 21. 二叉树采用左右链存储，完成下列算法，要求算法尽可能高效，分析算法时间和空间复杂度： （1） 判断二叉树是否为完全二叉树； （2） 输出二叉树从右向左数第K个叶结点。 22. 设计一种数据结构，满足栈的性质，实现下列3个操作： （1） Push(v)：将v加入到栈； （2） Pop()；删除栈顶元素并返回此元素； （3） Maxelement()：返回栈中最大元素； 让它们的时间复杂度都为O(1)。 II．计算机组成原理部分 五、填空题 1. 指令周期是 ，最基本的指令周期包括 和 。 2. 主存与Cache的地址映射有 、 和 三种方式，其中 的成本最高。 3. 若浮点数格式中基值一定，且尾数采用规格化表示，则浮点数的表示范围决定于 的位数，而精度取决于 的位数。 4. 在异步通信中，没有固定的总线传输周期，通信双方通过 信号联络。。 5. 已知[x]补=1.0000，则x= [2x]补= ，[2x]原= 。 6. 设相对寻址的转移指令占两个字节，第一个字节是操作码，第二个字节是相对位移量（用补码表示），若CPU每当从存储器取出一个字节时，即自动完成(PC)+1PC，设当前PC的内容为2009H，要转移到2002H，则该转移指令第二个字节的内容应为 。 7. 某机有4个中断源，优先顺序按123降序排列，若想将中断处理次序改为11 本文来源：https://www.wddqw.com/doc/41e71429e55c3b3567ec102de2bd960590c6d9bd.html