《2014年哈工大计算机科学与技术专业854考研真题》由会员分享，可在线阅读，更多相关《2014年哈工大计算机科学与技术专业854考研真题（4页珍藏版）》请在金锄头文库上搜索。
1、2013年哈工大计算机科学与技术专业854 考研真题I. 数据结构部分一、单项选择题1. 有一个100*90整型数的稀疏矩阵非0元素有10个，设每个整型数点2 字节，则用三元 组表示该矩阵时，所需的字节数为（1）。A. 60 B.66 C.180 D.332. 下列内部排序算法中，其比较次数与序列初始状态无关的是（2）。A.快速排序B.直接插入排序C.二路归并D.选择排序3. 若度数为m的哈夫曼树中，其叶子结点的个数为n,则非叶子结点的个数为（3）。A. n-1B.n/（m-1）C.（n-1）/（m-1）D.（n+1）/（m+1）-14. 长度为 12 有序表，按折半查找法对该表进行查找，以等
2、概率查找表内各元素，则查找 成功时所需要的平均比较次数为（4）。A.35/12B.36/12C.39/12D.43/125. 设有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要 进行（ 5）次探测。A.K-1B.K C.K+1D.K（K+1）/26. 有n个初始归并段，采用K路归并时，所需要的归并遍数是（6）。A. lognkB. log2kC. log2nD. logkn7. 有n个顶点，e条边的有向图采用邻接存储，若删除与顶点Vi相关的所有边，其时间复 杂度为（7）。A.O（n）B.O（e）C.O（max（n, e）D.O（n*e）8. 在平衡二叉树中插入一个结点造
3、成不平衡，设最低的不平衡结点为A,并已知插入后A的左子树根的平衡度为0，右子树根的平衡度为1，则应作（8）型的调整达到平衡。 A.LLB.LRC.RLD.RR9. 一棵具有n个非叶子结点完全二叉树的线索树，含有多少条线索（9）。A. 2n+1 或 2nB. 2n+2 或 2n+1C. 2n+1 或 2n-1D. 2n+2 或 2n-210. 在某森林的二叉树表示中，结点M和结点N是同一父节点的左儿子和右儿子，则在该 森林中（10）。A. M、N具有同一双亲B. M、N可能没有共同祖先C. M是N的儿子D. M是N的左兄弟二、填空题11. 高度为 h 的完全二叉树至少有（11）个结点。12. N
4、个结点的k叉树（k2）的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 算法和最小生成树的 Pri
5、m 算法之间的主要区别（18）。三、简答题19. 从大规模数据（例如1亿个数）表中取前100个值,给出一种高效算法并描述算法思想, 阐述选择该算法的理由。20. 给出判断一个有向图是否存在拓扑排序的算法；给出图-1 所示有向图的拓扑序列。四、算法设计题按下列要求设计算法：（1）描述算法设计的基本思想；（2）根据设计思想，采用C或C+或Java语言描述算法；（ 3 ） 分析算法时间复杂度和空间复杂度。21. 二叉树采用左右链存储，完成下列算法，要求算法尽可能高效，分析算法时间和空间复 杂度：（ 1）判断二叉树是否为完全二叉树；（2）输出二叉树从右向左数第K个叶结点。22. 设计一种数据结构，满足
6、栈的性质，实现下列3个操作：（1）Push（v）:将v加入到栈；（2）Pop（）；删除栈顶元素并返回此元素；（3）Maxelement（）：返回栈中最大元素；让它们的时间复杂度都为O（1）。II.计算机组成原理部分五、填空题1. 指令周期是，最基本的指令周期包括和 。2. 主存与Cache的地址映射有、 和.三种方式，其中的成本最高。3. 若浮点数格式中基值一定，且尾数采用规格化表示，则浮点数的表示范围决定的位数，而精度取决于的位数。4. 在异步通信中，没有固定的总线传输周期，通信双方通 信号联络。5. 已知xl = 1.0000,则乂= 1xl = ，卩x = 。补2 补2 原6. 设相对寻
7、址的转移指令占两个字节，第一个字节是操作码，第二个字节是相对位移量（用补码表示），若CPU每当从存储器取出一个字节时，即自动完成（PC）+1TPC,设当前 PC的内容为2009H,要转移到2002H，则该转移指令第二个字节的内容应为。7. 某机有4个中断源，优先顺序按1T2T3T降序排列，若想将中断处理次序改为3T1T4T2,则1、2、3、4中断源对应的屏蔽字分别为、和。8. 若控制单元CU采用微程序设计方法实现，当指令取至指令寄存器后，每一条机器指令 微程序的入口地址根据，通过形成。六、简答题1. 串行传输和并行传输有什么区别？若某异步串行传输系统中，每秒传输 120 个数据帧， 其字符格式
8、为：1 位起始位、 8 位数据位、 1 位奇偶检验位、 1 位终止位，请问其波特率 是多少？。2. 某 CPU 执行一段程序时， Cache 完成存取的次数为 1800，主存完成存取的次数为 200 次，已知Cache存取周期为50ns,主存为250ns,请问题CPU在执行该程序时的Cache- 主存系统的命中率和平均访问时间是多少？。3. 在计算机系统中，多重中断是指什么？为了实现多重中断，需要具备哪些条件？4. 若磁盘采用DMA方式与主机交换信息，其传输速率为4MB/S,且DMA预处理需要的 时间需1000个时钟周期，DMA完成传输后处理中断需500个时钟周期、如果平均传输 的数据长度为4
9、KB，试问在硬盘工作时，500MHz的处理器需用多少时间比率进行DMA 辅助操作(预处理和后处理)？5. 某计算机字长为16位，采用单重分组先行进位方案，将4、4、4、4分组，并设C15为 最高进位， C 补为外来进位。请画出进位链框图，并指出每个小组的输入输出信号。七、综合题1. 求证：凶 “ + M =X + Y (mod2)。补 补 补2. 某机的指令系统共有10条指令,指令周期由取指周期、间指周期、执行周期、中断周期(程序断点存入主存的地址单元，且采用硬件向量法寻找入口地址)组成,CPU内部结 构包括MAR、MDR、PC、IR、CU、ALU、ACC,采用非总线结构链接，请写出间指 周期
10、和中断周期的微操作。如果该机采用微程序方式实现，其指令系统共有28个微指令、 6个互斥的可判定外部条 件，控制存储器容量为512*40位，试画出微指令格式并说明理由。3. 设CPU共有16根地址线，8根数据线，并用MMREQ作为访存控制信号(低电平有效)、 WTR作写控制信号,RD作读控制信号。现有下列存储芯片:1K*4位ROM, 2K*8位ROM, 2K*8RAM, 1K*8位RAM以及74138译码器和各种门电路，如图所示画出CPU与存储 器的连接图，要求：(1) 主存地址分配： 1000H13FFH 为系统程序区， 2000H2FFFH 为用户程序区， 要求用户程序采用模为4体的低位交叉编址方式来实现。(2) 合理选用上述存储芯片，要求存储芯片的数量最少，且不能有冗余的存储空间。请说明各选几片，并写出第片的二进制地址范围。3) 详细画出存储芯片的片选逻辑。
