1、C后进后出 D前出前进9深度为3（根的层次号为1）的满二叉树结点个数为（ ）A4 B6 C7 10不带头结点的单链表head为空的判定条件是（ ）Ahead=NULL Bhead-next=NULL Chead!=NULLDhead-next!11有一个有序表为2，3，8，10，30，当折半查找到8时，需要的比较次数为（ ）12栈的插入与删除操作在（ ）A栈顶 B栈底 C队头 D队尾13一个栈的入栈顺序是a,b,c，则该栈的不可能的输出序列是（ ）Aabc Bcba Cacb Dcab14设先序遍历某二叉树的序列为ABC，中序遍历该二叉树的序列为BAC，则后序遍历该二叉树的序列为（ ）AABC
2、 BCBA CACB DBCA15设一组初始记录关键字序列（5，2，6，3），以第一个记录关键字5为基准进行一趟快速排序的结果为（ ）A2，3，5，6 B5，2，3，6 C3，2，5，6 D2，3，6，516在计算机中配置操作系统的主要目的是（ ）A增强计算机的功能 B提高系统资源的利用率C提高系统的运行速度 D合理组织系统的工作流程17从静态角度讲，进程由程序段、数据段和（ ）组成，它是进程存在的唯一标志。AJCB BPCB CFCB D代码段18临界区是指（ ）A进程中用于访问共享资源的那段代码。B进程中用于实现进程同步的那段代码。C进程中用于实现进程互斥的那段代码。D进程中用于访问临界资
3、源的那段代码。19下面哪种情况不会引发进程调度？（ ）A进程正常结束或异常中止。B正在执行的进程因I/O请求而被阻塞。C某等待打印机的进程发现其它使用打印机的进程已经打印完毕。D在引入时间片的系统中，时间片用完。20内存管理的基本任务是提高内存的利用率，使多道程序能在不受干扰的环境中运行，这主要是通过下面哪种功能实现的？A内存分配 B内存扩充 C内存保护 D兑换21在一般大型系统中，主机对外围设备的控制可通过通道、控制器和设备三个层次来实现。从下述中选择一个正确的叙述。A通道控制控制器，设备在控制器控制下工作。B控制器可控制通道，设备在通道控制下工作。C通道和控制器分别控制设备。D控制器控制通
4、道和设备。22在文件系统中，必须为每个文件建立（ ）, 其中包括文件名和文件的物理地址等信息。A用户文件描述符表 B索引结点C文件控制块 D索引表23磁盘调度的策略主要是为了优化（ ）A交换时间 B寻道时间 C旋转延迟时间 D传输时间24动态重定位的主要目的是使作业在内存中移动，动态重定位发生在（ ）A编译过程 B装入过程 C链接过程 D运行过程25在命令行接口中，使命令的执行结果不在屏幕上显示，用于把第一条命令的输出作为第二条命令的输入，第二条命令的输出作为第三条命令的输入的功能设施称为（ ）A管道 B链接 C脱机输入 D联机输出二、简答题（每题5分，共60分）26计算程序段的时间复杂度。（
5、5分）for （i=1; i=n; i+）x+;27设给定权集W=2，3，4，7，试构造关于W的一棵赫夫曼树，并求其带权路径长度WPL。28设有一序列30,19,3,61，请按该序列构成一棵二叉排序树，并求其查找成功时的平均查找长度ASL。29写出下图所示二叉树的先序，中序和后序遍历序列。30什么是线性表? 线性表的元素之间的关系是什么?31已知待散列的线性表为（8，15，40，63），散列用的一维地址空间为0.6，假定选用的散列函数是H（K）= K mod 7，若发生冲突采用线性探查法处理，计算出每一个元素的散列地址并在下图中填写出散列表。12345632请画图说明进程的三种基本状态及各状态
6、间的转换，并说明引发状态转换的典型事件。33什么是操作系统，简述操作系统的主要功能。34什么是死锁，分析死锁发生的主要原因。35虚拟存储器的基本特征有哪些？为什么说请求分页系统是实现虚拟存储器是一种方式？36.什么是中断，描述CPU访问中断的一般过程。37在公共汽车上，司机与售票员的工作流程如下图所示。为保证乘客安全，司机和售票员必须密切配合协调工作，售票员在关车门之后向司机发送开车信号，司机接到开车信号后启动车辆，汽车正常行驶时售票员可以售票，到站时司机停车，售票员在停车后开门让乘客下车，请用信号量来实现司机与售票员之间的同步。三、综合题（每题10分，共40分）38编写一个函数，实现对数组a
7、（元素个数为n）中元素进行冒泡排序的算法。（10分）void bubblesort（int a）39编写两个函数，分别实现对二叉树的先序遍历（preorder）和中序遍历（inorder）的递归算法。二叉树结点的结构体为struct BiTreeNodeint data;struct BiTreeNode * leftChild;struct BiTreeNode * rightChild;typedef struct BiTreeNode Node;void preorder （Node * t） /*t为指向二叉树的根结点的指针*/void inorder （Node * t） /*t为指
8、向二叉树的根结点的指针*/40（本题10分）有四个进程P1,P2,P3,P4，它们进入就绪队列的先后顺序为P1,P2,P3,P4，它们的优先级和需要的处理机时间如下表。假定这四个进程在执行过程中不会发生等待事件，忽略进程调度所花费的时间，从某个时刻开始进程调度，请回答下面的问题：进程要求的处理时间优先级P18P2P322P4（1）采用“先来先服务”调度算法时，写出进程的执行顺序，计算各进程在就绪队列中等待的时间以及平均等待时间；（4分）（2）采用“非抢占式的优先级”调度算法时，写出进程的执行顺序，计算各进程在就绪队列中等待的时间以及平均等待时间；（3）说明采用“时间片轮转法”调度算法时，写出进
9、程的执行顺序，计算各进程在系统中停留的时间以及平均停留的时间。（2分）41（本题10分）某系统采用页式存储管理策略，请回答下面的问题：（1）若逻辑空间为32页，每页2K，物理空间1M，写出逻辑地址的格式。若不考虑访问权限等，进程的页表有多少项，每项至少多少位？如果物理空间减少一半，页表结构应相应地怎样变化。（6分）（2）假定页表放在内存中，如果访问内存需要，计算有效访问时间；（3）如果加一快表，且假定在快表中找到页表项的几率高达90%，则有效访问时间又是多少？2013年重庆理工大学计算机科学与工程学院809计算机学科专业基础综合考研真题809计算机学科专业基础综合（A卷）一、选择题1深度为2（
10、根结点的层次号为1）的满二叉树的叶子结点个数为（ ）B3 C4 D62栈的特点是（ ）C同进同出 D同出同进3双向链表的指针域的个数为（ ）4完全二叉树，按层次序列编号（根结点编号为1），则编号为2的结点的左孩子的编号为（ ）A3 C5 5具有 m个顶点的无向完全图的边的数目为（ ）Am（m+1）/2 Bm（m-1）/2 Cm（m-1） Dm（m+1）6顺序表的第1个元素存储地址是100，每个元素占用2个存储单元，则该顺序表的第3个元素地址是（ ）A102 B104 C106 D1087数据的存储结构可分为链式存储结构和（ ）A顺序存储结构 B哈希存储结构C索引存储结构 D表存储结构8数据元素
11、之间有四种基本逻辑结构，下列描述中是逻辑结构的是（）A圆形结构 B树形结构 C方形结构 D菱形结构9下列不属于线性结构的是（ ）B栈 C队列 10满二叉树，按层次序列编号（根结点编号为1），则编号为3的结点的双亲编号为（ ）11第二代计算机是以（ ）为主要器件的。A电子管 B晶体管 C二极管 D触发器12动态RAM基本电路单元是靠（ ）来寄存信息的。A电阻 B电容 D晶体管13主机、外设串行工作的方式是（ ）。A程序查询 B程序中断 CDMA DI/O处理机14以下有关运算器的叙述，正确的是（ ）。A只做加法运算 B只做算术运算C既做算术运算又做逻辑运算 D只做逻辑运算15指令周期是指（ ）。
12、ACPU从主存取出一条指令的时间BCPU从主存取出一条指令加上执行指令的时间C节拍周期时间D时钟周期时间16某存储器芯片规格为8K1位，则它的地址线和数据线共有（ ）根。A15 B14 C13 D1217Cache是为解决CPU与（ ）之间速度不匹配而采用的一项技术。A硬盘 B光盘 C总线 D内存18计算机系统I/O接口是（ ）之间的交接界面。ACPU与存储器 B主机与外设C系统总线与CPU DCPU与Cache19DMA用于高速数据块的传送，直接在（ ）和外设之间进行数据传送。A内存 B硬盘 CCPU DCache20在指令操作完成后，PC中存放的是（ ）。A下一条顺序执行的指令地址 B当前
13、指令的地址C转移指令的地址总线 D停机指令的地址总线21微程序存放在（ ）中。A控制存储器 C指令寄存器 D光盘22CPU响应中断的时间是（ ）。A任一机器周期结束时 B外设提出中断时C取指周期结束时 D一条指令执行结束时23能够改变程序执行顺序的（ ）。A数据传送指令 B加法操作指令C跳转指令 D输入输出指令24在主机中能对指令进行译码的器件是（ ）。AMAR BALU C控制器 DMDR25操作数在寄存器中的寻址方式称为（ ）寻址。A立即 B直接 C寄存器直接 D基址26操作系统的主要功能是管理计算机系统中的资源，其中包括（ ）管理和存储器管理，以及设备管理和文件管理。A存储器 B虚拟存储
14、器 C硬盘 D处理机27从用户的观点看，操作系统是（ ）A用户与计算机之间的接口B控制和管理计算机资源的软件C合理地组织计算机工作流程的软件D由若干层次的程序按一定的结构组成的有机体28多道程序设计是指（ ）。A在实时系统中并发运行多个程序B在分布式系统中同一时刻运行多个程序C在一台处理器上同一时刻运行多个程序D在一台处理器上并发运行多个程序29下列选择中，当（ ）时，进程的状态从运行状态转为就绪状态。A进程被进程调度程序选中 B进程时间片用完C进程等待I/O操作 D进程I/O操作完成30进程控制块是描述进程状态的数据结构，一个进程（ ）。A可以有多个进程控制块 B可以和其它进程共用一个进程控
15、制块C可以没有进程控制块 D只能有唯一的进程控制块31按照作业到达的先后顺序调度作业，排队等待时间最长的作业优先调度，这是指（ ）调度算法。A先来先服务 B短作业优先C响应比高优先 D时间片轮转32在下列存储管理方案中，不适应于多道程序设计的是（ ）。A单一连续区分配 B固定式分区分配C可变式分区分配 D段页式存储管理33访问磁盘的时间不包括（ ）。A寻道时间 BCPU调度时间C读写时间 D旋转等待时间34下面关于虚拟设备的论述中，正确的是（ ）A虚拟设备是指允许用户使用比系统中具有的物理设备更多的设备B虚拟设备是指允许用户以标准化方式来使用物理设备C虚拟设备是把一个物理设备变换成多个对应的逻
16、辑设备D虚拟设备是指允许用户程序不必全部装入内存便可使用设备系统中的设备。35文件系统的按名存取主要是通过（ ）来实现的。A存储空间管理 B目录管理C文件安全性管理 D文件读写管理36物理地址的长度是（ ）A16bit B32bit C48bit D128bit37下列传输介质中，传输光信号的是（ ）A双绞线 B光纤 C同轴电缆 D电话线38下列描述中，属于多路复用技术的是（ ）A双分复用技术 B频分复用技术C单分复用技术 D角分复用技术39数据通信线路的工作模式分为单工通信、全双工通信和（ ）A多播通信 B组播通信 C半双工通信 DP2P通信40下列协议中属于网络层协议的是（ ）ADNS B
17、SMTP CIP DHTTP二、综合题41计算程序段的时间复杂度（5分）t=0;for（i=1;i=N;i+）for（j=1;jj+）for（k=1;kk+）t+;42简答什么是栈？什么是队列？43假设二叉树采用如下的存储结构，其中lchild和rchild为分别指向左右孩子的指针。typedef struct nodeint data;struct node *lchild,*rchild;TwoTree;请编写一个算法，实现用递归方法求二叉树的深度。 （10分）int deeptree（TwoTree *bt）44什么是系统总线？按照传输信息的不同，它又可分为几类？是单向的还是双向的？（7
18、分）45简述CPU的基本组成与功能（8分）。46有三个进程P1,P2,P3并发工作。进程P1需要资源S3和S1，进程P2需要资源S1和S2，进程P3需要资源S2和S3。回答：（1）若对资源分配不加限制，会发生什么情况，为什么，举例说明。（2）为保证进程正确工作，应采取怎样的资源分配策略，为什么？（3分）47（1）在请求系统中，什么时候会发生缺页中断？（2）设系统为某进程分配了3个物理块，该进程共有5个页面，考虑如下的页面引用顺序：1,3,1,2,4,1,3，问：A按FIFO页面置换算法，访问第4号页面时，应淘汰第几号页面，共发生几次页面置换？B按LRU页面置换算法，访问第4号页面时，应淘汰第几
19、号页面，共发生几次页面置换？48简答什么是数据？什么是信号？49简答OSI七层参考模型中物理层、网络层、传输层和应用层的主要功能是什么？（8分）第二部分全国硕士研究生入学统一考试408计算机学科专业基础综合历年真题及详解2012年全国硕士研究生入学统一考试408计算机学科专业基础综合真题一、单项选择题：l40小题。每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1求整数n（n0）阶乘的算法如下，其时间复杂度是（ ）。AO（log2n）B0（n）CO（nlog2n）DO（n2）2已知操作符包括+、-、*、（和）。将中缀表达式a+b-a*（c+d）e-f）+g转换为
20、等价的后缀表达式ab+acd+ef-*-g+时，用栈来存放暂时还不能确定运算次序的操作符。若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是（ ）。A5B7C8D113若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b，c，d，e，a，则根结点的孩子结点（ ）。A只有eB有e、bC有e、cD无法确定4若平衡二叉树的高度为6，且所有非叶结点的平衡因子均为1，则该平衡二叉树的结点总数为（ ）。A12B20C32D335对有2个顶点e条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是（ ）。A0（n）B0（e）CO（n+e）DO（ne）6若用邻接矩阵存储有向图
21、，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是（ ）。A存在，且唯一B存在，且不唯一不唯一C存在，可能不唯一D无法确定是否存在7有向带权图如题7图所示，若采用迪杰斯特拉（Dijkstra）算法求从源点a到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是c，后续得到的其余各最短路径的目标顶点依次是（ ）。题7图有向带权图Ad, e, fBe，d，fCf，d，eDf，e，d8下列关于最小生成树的叙述中，正确的是（ ）。最小生成树的代价唯一 所有权值最小的边一定会出现在所有的最小生成树中 使用普里姆（Prim）算法从不同顶点开始得到的最小生成树一定
22、相同 使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树总不相同A仅B仅C仅、D仅、9设有一棵3阶B树，如题9图所示。删除关键字78得到一棵新B树，其最右叶结点所含的关键字是（ ）。题9图3二叉树图A60B60，62C62，65D6510排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（ ）。简单选择排序希尔排序快速排序堆排V二路归并排序A仅、B仅、C仅、D仅、11对同一待排序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是（ ）。A排序的总趟数B元素的移动次数C使用辅助空间的数
23、量D元素之间的比较次数12假定基准程序A在某计算机上的运行时间为l00秒，其中90秒为CPU时间，其余为I/O时间。若CPU速度提高50，I/O速度不变，则运行基准程序A所耗费的时间是（ ）。A55秒B60秒C65秒D70秒13假定编译器规定int和short类型长度分别为32位和16位，执行下列C语言语句：unsigned short X65530；unsigned int yX：得到y的机器数为（ ）。A00007FFAHB0000FFFAHCFFFF7FFAHDFFFFFFFAH14float类型（即IEEE754单精度浮点数格式）能表示的最大正整数是（ ）。A2126-2103B212
24、7-2104C2127-2103D2128-210415某计算机存储器按字节编址，采用小端方式存放数据。假定编译器规定int和short型长度分别为32位和16位，并且数据按边界对齐存储。某C语言程序段如下：若record变量的首地址为0xC008，则地址0xC008中内容及的地址分别为（ ）。A0x00、0xC00DB0x00、0xCOOEC0x11、0xC00DD0x11、0xC00E16下列关于闪存（FlashMemory）的叙述中，错误的是（ ）。A信息可读可写，并且读、写速度一样快B存储元由MOS管组成，是一种半导体存储器C掉电后信息不丢失，是一种非易失性存储器D采用随机访问方式，可替代计算机外部存储器17假设某计算机按字编址，Cache有4个行，Cache和主存之间交换的块大小为l个字。若Cache的内容初始为空，采用2路组相联映射方式和LRU替换算法，当访问的主存地址依次为0，4，8，2，0，6，8，6，4，8时，命中Cache的次数是（ ）。A1B2C318某计算机的控制器采用微程序控制方式，微指令中的操作控制字段采用字段直接编码法，共有33个微命令，构成5个互斥类，分别包含7、3、12、5和6个微命令，则操作控制字段至少有（ ）。A5位B6位C15位
