[计算机]考研计算机专业复习指导课讲义（精品资料）

《[计算机]考研计算机专业复习指导课讲义（精品资料）》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、2009年统考计算机考研真题一、单项选择题（每小题2分X10题）1•为解决计算机与打印机之间速度不匹配的问题，通常设置一个打卬数据缓冲区，主机将要输岀的数据依次写入该缓冲区，而打卬机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（）A.栈B・队列C・树D.图2•设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g依次进入栈S。若每个元索出栈后立即进入队列Q,且7个元素出队的顺序是bdcfeag,则栈S的容量至少是（）A.1B.2C.3D.43.给定二叉树如右图所示。设N代表二叉树的根，L代表

2、根结点的左子树，R代表根1结点的右子树。若遍历后的结点序列为3,1,7,5,6,2,4,则其遍历方式是（）（2）3A・LRNB.NRLC・RLND.RNL4•下列二义排序树中，满足平衡二义树定义的是（）5•己知一棵完全二义树的第6层（设根为第1层）有8个叶结点，则完全二义树的结点个数最多是（）A.39B.52C.lllD.1196•将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原來的森林中，u和v可能具有的关系是（）I.父子关系II•兄弟关系III.u的父结点与v的父结点是兄

3、弟关系A.只有IIB.I和IIC.I和IIID・I、II和III7•下列关于无向连通图特性的叙述中，正确的是（）I.所冇顶点的度Z和为偶数II.边数大于顶点个数减1III.至少有一个顶点的度为1A.只有IB.只有IIC.I和IID.I和III8.卜-列敘述中，不符合m阶B树定义要求的是（）A.根节点最多有m棵子树B・所有叶结点都在同一层上C・各结点内关键字均升序或降序排列D・叶结点之间通过指针链接9•已知关键序列5,8,12,19,28,20,15,22是小根堆（最小堆）,插入关键字3,调整后得到的小根堆是

4、（）A・3,5,12,8,28,20,15,22,19C・3,8,12,5,2(),15,22,2&19B・3,5,12,19,20,15,22,8,28D.3,12,5,8,2&2(),15,22,1910•若数据元素序列11,12,13,7,8,9,23,4,5是采用下列排序方法之一得到的第二趟排序示的结果，则该排序算法只能是（）A.起泡排序B.插入排序C・选择排序D.二路归并排序二、综合应用题（10分+15分）41.（10分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点

5、到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：①设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点；②选择离U最近且尚未在最短路径中的一个顶点V,加入到最短路径中，修改当前顶点③重复步骤②，直到U是目标顶点时为止。请问上述方法能否求得最短路径？若该方法可行，请证明之；否则，请举例说明。42.（15分）已知一个带有表头结点的单链表，结点结构为datalink假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能髙效的算法，查找链表中倒数第k

6、个位置上的结点（k为正整数）。若查找成功,算法输出该结点的data值,并返回1；否则,只返回0。要求:（1）描述算法的基木设计思想（2）描述算法的详细实现步骤（3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C或C++或JAVA语言实），关键之处请给出简要注释。2010年统考计算机考研真题一、单项选择题（每小题2分XII题）1・若元素a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替进行。但不允许连续三次进行退栈工作，则不可能得到的岀栈序列是（）A:dcebfaB:cbdaefC:dbcaef

7、D:afedcb2•某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的顺序是（）A：bacdeB:dbaceC：dbcaeD：ecbad3•下列线索二叉树屮（用虚线表示线索），符合后序线索树定义的是（）0=Null4•在下图所示的平衡二叉树中插入关键字4X后得到一棵新平衡二叉树，在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是（）A：13,48B：24,48C：24,53D：24,905•在一棵度为4的树T中，若冇20个度为4的结点，10个度为3的结点，1个度为

8、2的结点,1（）个度为1的结点，则树T的叶节点个数是（）A：41B：82C：113D：1226•对n（n^2）个权值均不相同的字符构成哈夫曼树，关于该哈弗曼树的叙述屮，错谋的是（）A：该树一定是一棵完全二叉树B：树中一定没有度为1的结点C：树中两个权值最小的结点一定是兄弟结点D：树中任一非叶结点的权值一定不小于下一任一结点的权值7•若无向图G=(V.E)屮含7个顶点，则保证图G在任何悄况下都是连通的，则需要的边数