一、选择题1.下列说法正确的是：（A）A.计算机网络是指将计算机与通信设备互相连接，以便实现资源共享和信息传递B.因特网是由全球范围的许多互联网所组成C.互联网是指将一个计算机与另一个计算机互相连接D.局域网是指建立在地理上相邻范围内的计算机互联网2.下列关于OSI参考模型的描述，不正确的是（B）A.会话层是在用户端进行处理的B.物理层对物理设备和媒体有着直接的控制作用C.表示层的主要功能是数据的转换编码格式D.应用层是网络服务与最终用户之间的接口层3.下列不属于传输层服务的是（B）A.可靠数据传输B.数据的加密与解密C.数据的传输D.会话复用与分解4.以下说法中错误的是（C）A.在计算机网络中，争用的信道采用的信道访问方式有ALOHA和CSMA等B.网络互连设备将LAN、MAN或WAN连接起来，是构成因特网的重要组成部分C.OnlySpanningTree协议能防止环路的产生D.使许多网络硬件实例连接在一起的设备是集线器5.在因特网中使用UDP协议工作的是（D）A.聊天室、网游B.电流新箱C.WWW D.文件传输6.在因

2012年考研计算机统考408真题一、单项选择题1.求整数n(n>=0)阶乘的算法如下,其时间复杂度是_1_。A.O(logzn)B.O(n)C.O(nlog2n)D.O(n*)2.已知操作符包括+'、'-、'*'、'/'、'(和')'。将中缀表达式a+b-a*((c+d/e-f)+g 转换为等价的后缀表达式ab+acd+e/f-*-g+时, 用栈来存放暂时还不能确定运算次序的操作符,若栈初始为空,则转换过程中同时保存在栈中的操作符的最大个数是2 2 A.5 B.7 C.8 D.11 3.若一棵二叉树的前序遍历序列为a,e,b,d,c, 后序遍历序列为b,c,d,e,a, 则根结点的孩子结点_3_。A.只有e B.有e,b C.有e,c D.无法确定4.若平衡二叉的高度为6,且所有非叶结点的平衡因子均为1,则该平衡二叉树的结点总数为_4。A.10 B. 20 C. 32 D.33 5.对有n个结点、e条边且使用邻接表存储的有向图进行广度优先遍历,其算法时间复杂度是_5_。A.O(n)B.O(e)C.O(n+e)D.O(n*e)6.若用邻接矩阵存储有向图,矩阵中主对角线以下的元素均为零,则关于该图拓扑序列的结论是_6_。A.存在,且唯一B.存在,且不唯一C.存在,可能不唯一D.无法确定是否存在7.对如下有向图带权图,若采用迪杰斯特位(D

单项选择题：1~40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项符合试题要求。 1.设n是描述问题规模的非负整数，下列程序段的时间复杂度是x=0； A.O(log n)B.O(n1/2)C.O(n)D.O(n2)2.若将一棵树T转化为对应的二又树BT，则下列对BT的遍历中，其遍历序列与T的后根遍历序列相同的是A.先序遍历B.中序遍历C.后序遍历D.按层遍历3.对n个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有115个结点，则n的值是A.56 B.57 C.58 D.60 4.在任意一棵非空平衡二又树(AVL树)T1中，删除某结点v之后形成平衡二又树T2，再将w插入T2形成平衡二又树T3。 综合应用题：41~47小题，共70分。41.(13分)设线性表L=(a1，a2，a，an-2，a-1，a。)采用带头结点的单链表保存，链表中结点定义如下：typedef struct node { int data； 请设计一个空间复杂度为O(1)且时间上尽可能高效的算法，重新排列L中的各结点，得到线性表L'=(a1，an，a2，an-1，a3，an-2)。要求：(1)给出算法的基本设计思想(2)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。 (3)说明你所设计的算法的时间复杂度。 42.(10分)请设计一个队列，要求满足：初始时队列为空；入队时，允许增加队列占用空间；出队后，出 单项选择题扇区号为(530×2)%200=60。 将簇号转换成磁盘物理地址的过程由磁盘驱动程序完成。 45.【答案要点】(1)计算f(l0)需要调用函数f1共10次执行第16行call 指令会递归调用f1。 (2)第12行jle指令是条件转移指令。第16行call指令、第20行jmp指令、第30行ret指令一定会使程序跳转执行。 (3)第16行call指令的下一条指令的地址为0040 综合应用题41.【答案要点】(1)算法的基本设计思想：算法分3步完成。第1步，采用两个指针交替前行，找到单链表的中间结点；第2步，将单链表的后半段结点原地逆置；第3步，从单链表前后两段中依次各取一个结点，按要求重排。 1025H+5=0040 102AH，故第17行指令的虚拟地址是0040 102AH。call指令采用相对寻址方式，即目标地址=(PC)+偏移量，call指令的目标地址为0040 1000H，所以偏移量=目标地址-(PC)=00401000H-0040 102AH=FFFF FFD6H。根据第16行call指令的偏移量字段为D6 FF FF FF，可确定M采用小端方式。 (4)因

计算机专业基础综合历年真题试卷汇编4(总分：70.00，做题时间：90分钟)一、单项选择题(总题数：27，分数：54.00)1.单项选择题1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_解析：2.下列关于中断IO方式和DMA方式比较的叙述中，错误的是_。（分数：2.00）A.中断IO方式请求的是CPU处理时间，DMA方式请求的是总线使用权B.中断响应发生在一条指令执行结束后，DMA响应发生在一个总线事务完成后C.中断IO方式下数据传送通过软件完成，DMA方式下数据传送由硬件完成D.中断IO方式适用于所有外部设备，DMA方式仅适用于快速外部设备解析：解析：中断处理方式：在IO设备输入每个数据的过程中，由于无需CPU干预，因而可使CPU与IO设备并行工作。仅当输完一个数据时，才需CPU花费极短的时间去做些中断处理。因此中断申请使用的是CPU处理时间，发生的时间是在一条指令执行结束之后，数据是在软件的控制下完成传送的。而DMA方式与之不同。DMA方式：数据传输的基本单位是数

90,120,130,110)6.设无向图G=(V,E)和G'=(V',E'),如果G'是G的生成树,则下面说法错误的是()。A.G'是G的子图B.G'是G的连通分量C.G'是G的极小连通子图且V=V'D.G'是G的一个无环子图7.若G是一个具有36条边的非连通无向简单图,则图G的结点数至少是()。A.11B.10C.9D.88.在有向图G的拓扑序列中,若顶点V;在顶点V_{j}.之前,则下列情形不可能出现的是()。A.G中有弧<V_{i},V_{j}>B.G中有一条从V,到V_{j}的路径C.G中没有弧<V_{i},V_{j}>D.G中有一条从V_{j}到V_{i}的路径9.具有12个关键字的有序表中,对每个关键字的查找概率相同,折半查找查找成功和查找失败的平均查找长度依次为()。A.37/12,49/13B.35/12.39/13C.37/13.49/13D.37/12,49/1210.设线性表中每个元素有两个数据项k1和k2,现对线性表按以下规则进行排序:先看数据项k1,k1值小的元素在前,大的在后;在k1值相同的情况下,再看k2,k2值小的在前,大的在后。满足这种要求的排序方法是()。A.先按k1进行直接插入排序,再按k2进行简单选择排序B.先按k2进行直接插入排序,再按k1进行简单选择排序C.先按k1进行简单选择排序,再按k2进