清华大学2001年计算机专业考研真题

一、单项选择题： 1-40 题，每题 20 分共 80 分。

在每个小题给出的四个选项中 选正确答案。

1 、若元素 a 、b 、c 、d 、e 、f 依次进栈，允许进栈、退栈操作交替进行，但不允 许连续三次进行退栈工作，则不可能得到的出栈序列是（）某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可 能得到的顺顺序是（）下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是（） 在下列所示的平衡二叉树中插入关键字 48后得到一棵新平衡二叉树， 在新平 衡二叉树中，关键字 37 所在结点的左、右子结点中保存的关键字分别是（）在一棵度数为4的树T 中，若有20个度为4的结点，10个度为3的结点，1 个度为2的结点，10个度为1的结点，则树T 的叶结点个数是（） A 、 dcebfa B 、 cbdaef C 、 bcaefd D 、afedcb 2、 A 、 bacde B 、 dbace C 、 dbcae D 、ecbad 3、4、A 、 13， 48B 、 24， 48C 、 24， 53D 、24， 90 5、A 、 41B 、 82C 、113D 122 &对n （n>=2）个权值均不相同的字符构成哈弗曼树，关于该树的叙述中，错误的是（）该树一定是一棵完全二交叉树中任一非叶结点的权值一定不小于下一层任一结点的权值若无向图G=（V.E ）中含7个顶点，则保证图G 在任何情况下都是连通的, 则需要的边数最少是（）A 、21对下图进行拓扑排序，可以得到不同的拓扑序列的个数是（）B 、C 、已知一个长度为16的顺序表L ,其元素按关键字有序排列，若采用折半查找 法查找一个不存在的元素，则比较次数最多的是（）B 、C 、B 、 树中一定没有度为1的结点C 、 树中两个权值最小的结点一定是兄弟结点7、 B 、 15 C 、16 8、 9、10、采用递归方式对顺序表进行快速排序， 下列关于递归次数的叙述中，正确的 是 递归次数于初始数据的排列次数无关每次划分后，先处理较长的分区可以减少递归次数（勤思考研）递归次数与每次划分后得到的分区处理顺序无关第一趟：2, 12, 16, 5, 第二趟：2, 12, 5, 10, 第三趟：2, 5, 10, 12, 则采用的排序方法可能是 A. 冒泡排序法 B. 希尔排序法 C. 归并排序法D. 基数排序法 12.下列选项中，能缩短程序执行时间的措施是（） 1.提高CPU 时钟频率2.优化通过数据结构3.优化通过程序 A. 仅1和2 B. 仅1和3 C, 仅2和3 D. 1,2,313. 假定有4个整数用8位补码分别表示r 仁FEH r2=F2H, r3=90H , r4=F8H,若将运算结果存放在一个8位寄存器中，则下列运算会发生益处的是（）A. r1 x r2B. r2 x r3C. r1 x r4D. r2 x r4 14.假定变量i ,f,d 数据类型分别为int, float,double （i nt 用补码表示，float和double 用IEEE754单精度和双精度浮点数据格式表示），已知i=785 ,()B 、C 、 每次划分后，先处理较短的分区可以减少递归次数11、对一组数据（2，12, 16, 88, 5, 10）进行排序，若前三趟排序结果如下：（）10， 16, 8888 88f=1.5678e3 , d=1.5e100,若在32位机器中执行下列关系表达式，则结果为真的是（）(I)i==( in t)(float)l (ll)f==(float)(i nt)f (lll)f==(float)(double)f(IV)(d+f)-d==fA. 仅l和llB. 仅l和lllC. 仅ll和lllD. 仅lll和lV15.假定用若干个2K x 4位芯片组成一个8K x 8为存储器，则0B1FH所在芯片的最小地址是（）A.OOOOHB.0600HC.0700HD.0800H16.下列有关RAM和ROM得叙述中正确的是（） l RAM是易失性存储器，ROM是非易失性存储器II RAM和ROM都是采用随机存取方式进行信息访问Ill RAM 和ROlW可用做CacheIV RAM和ROMP需要进行刷新A.仅I和IIB.仅II 和IllC.仅I , II , Ill精选文库D.仅II , III , IV17.下列命令组合情况，一次访存过程中，不可能发生的是（）A.TLB未命中，Cache未命中，Page未命中B.TLB未命中，Cache命中，Page命中C.TLB命中，Cache未命中，Page命中D.TLB命中，Cache命中，Page未命中18.下列寄存器中，反汇编语言程序员可见的是（）A.存储器地址寄存器（MAR）B.程序计数器（PC）C.存储区数据寄存器（MDR）D.指令寄存器（IR）19.下列不会引起指令流水阻塞的是（）A.数据旁路B.数据相关C.条件转移D.资源冲突20.下列选项中的英文缩写均为总线规范的是（）A. PCI、CRT USB EISAB. ISA、CPI、VESA EISAC. ISA、SCSk RAM MIPSD. ISA、EISA、PCI、P CI-Ex press21、单级中断系统中, 中断服务程序执行顺序是（）I保护现场II开中断III关中断IV保存断点V中断事件处理VI恢复现场VII 中断返回A、I->V->VI->II->VIIB、III->I->V->VIIC、III->IV->V->VI->VIIIV->I->V->VI->VII22、假定一台计算机的显示存储器用DRAMS片实现，若要求显示分辨率为1600*1200,颜色深度为24位，帧频为85HZ现实总带宽的50卿来刷新屏幕, 则需要的显存总带宽至少约为（）A、245Mb psB、979Mb psC、1958Mb ps7834Mb ps23、下列选项中，操作S提供的给应程序的接口是（）A、系统调用B、中断C、库函数原语24、下列选项中，导制创进新进程的操作是（）I用户登陆成功II设备分配III启动程序执行A、仅I和IIB 、仅 II 和 IIIC 、仅I 和IIID I 、 II 、 III25、设与某资源相关联的信号量初值为 3,当前值为1,若M 表示该资源的可用 个数， 0，1, 2,26、下列选项中，降低进程优先权级的合理时机是（） 进程长期处于就绪列队 进程从就绪状态转为运行状态27、进行PO 和P1的共享变量定义及其初值为（） booleam flag[2] 。

清华计算机考研试题《数据结构》一、选择题123 给了一序列比如6.7.4.8.9.3.散列函数是H(key)=key%11.一问成功时的平均搜索长度二问不成功的平均搜索长度4 哪种数据结构，从某一个结点到根结点的路径序列组成一个降序排列a. b.最大堆 c.最小堆 d5 还有一个题是关于关键路径的，答案选项是49/B -C \A /F\ \\D-E H\G/6 什么是数据结构？ A B C定义在一个数据集合上的属性和操作 D7 高度为h的完全二叉树，一共有多少种？A B 2^(h-1) C D二、证明题1. 什么样的有向无环图有唯一的拓扑有序序列，并证明。

三、计算题1 有n个结点的二叉树最大高度，最小高度分别是多少？其中g和f函数的作用是通过输入参数，进行一系列运算后返回。

相当于Ti 以a和a[i-1]为输入参数，a和b为输出。

要求使用pv原语，实现T1～Tn-1的并发互斥，尽量保证最大限度的并发。

(a[i-1]为Ti-1线程的结果,)四、进程同步问题假设当前处于非抢占调度策略，进程只有两种方式可以放弃cpu，一个是主动调用系统调度函数yield()，此时进程主动放弃cpu；另一个方式是当进程执行I/O 操作时，系统将调度下一个进程。

试分析如下三种进程对，何时会出现不符合下列原则，并说明原因：1）空闲则入 2)有限等待 3）保证互斥。

第一种：Thread1(){yield();----critical section-----g=g+b;f=g-a; //这部分确切的语句想不起来了，但不影响。

只要记得临界区不能被打断。

----critical section-----}Thread2(){----critical section-----g=g+b;f=g-a;----critical section-----}第二种：Thread1(){yield();----critical section-----g=g+b;f=g-a;----critical section----- }Thread2(){----critical section-----g=g+b;f=g-a;----critical section-----yield();}第三种：Thread1(){yield();----critical section-----g=g+b;fstring=printf(……) ; // 调用I/O;f=g-a;----critical section-----}Thread2(){yield();----critical section-----g=g+b;f=g-a;----critical section-----}五文件操作题很长，大意如下给定两种文件系统，分别采用FAT方式和索引方式组织文件结构。

清华大学2001年硕士入学计算机原理试题一、（10分）某RISC处理机各类指令使用频率和理想CPI（指令和数据访问Cache命中率为100％时的CPI）如下表所示。

而实际测得的指令访问Cache缺失率（miss rate）为5％，数据访问的Cache缺失率为10％，Cache的缺失损失（miss penalty）为40个时钟周期。

（1）该机器在无Cache缺失（理想情况）时的CPI是多少？（3分）（2）该机器在无Cache缺失（理想情况）时的速度比有Cache缺失时快多少倍？（7分）指令类型使用频率CPI idealALU操作43％1Loads21％2Stores12％2Branches24％2二、（13分）一台模型机共有7条指令，主频25MHz，各指令的使用频率与CPI如下表所示。

该模型机有8位和16位两种指令字长，采用2-4扩展操作码。

8位字长指令为寄存器（R－R）二地址类型，16位字长指令为寄存器－存储器（R－M）二地址变址寻址类型（-128<=变址范围<=127）。

指令（字长）使用频度f CPII1（8位）35%1I2（8位）25%2I3（8位）20%2I4（16位）10%2I5（16位）5%1I6（16位）3%2I7（16位）2%2（1）计算该机的MIPS速率。

（4分）（2）计算操作码的平均码长。

（3分）（3）该机允许使用多少个可编址的通用寄存器，多少变址寄存器？（3分）（4）设计该机的两种指令格式，标出各字段位数并给出操作编码。

（3分）三、（12分）假设在一个采用组织相联映像方式的Cache中，主存有B0～B7共8块组成，Cache有C0～C3共4块，组内块数为2块。

每块的大小为32个字节，采用FIFO块替换算法。

在一个程序执行过程中依次访问块地址流如下：B1，B4，B6，B3，B0，B4，B6，B2，B4，B5。

清华大学研究生入学试卷二一．一．选择题（每小题1分，共10分）。

1.定点8位字长的字，采用2的补码形式表示时，一个字所表示的整数范围是___。

A.–128—+127B.-127—+127C.-129—+128D.-128—+1282.运算器虽有许多部件组成，但核心部分是___。

A.数据总线B.算术逻辑单元C.多路开关D.通用寄存器3.某计算机字长32位，其存储容量是1MB，若按字编址，它的寻址范围是___。

A.0—1MB.0—512KBC.0—256KD.0—256KB4.二地址指令中，操作数的物理位置可安排在___。

A.栈顶和次栈顶B.两个主存单元C.一个主存单元和一个寄存器D.两个寄存器5.描述多媒体CPU的基本概念中，正确的表述是___。

A.多媒体CPU是带有MMX技术的处理器.B.MMX是一种多媒体扩展结构.C.MMX指令集是一种MIMD（多指令流多数据流）的并行处理指令.D.多媒体CPU是以超标量结构为基础的CISC的基础.6.在下面描述的RISC机器基本概念中，不正确的表述是____。

A.A.RISC机器不一定是流水CPU.B.B.RISC机器一定是流水CPU.C.C.RISC机器有复杂的指令系统.D.D.CPU配备很少的通用寄存器.7.在下面描述的PCI总线基本概念中，不正确的表述是___。

A.PCI总线是一个与处理器无关的高速外围总线.B.PCI总线的基本传输机制是猝发式传送.C.PCI设备一定是主设备.D.系统中允许只有一条PCI总线.8.CRT的分辨率为1024×1024像素，像素的颜色总数为256色，则刷新存储器每个单元字长是___。

A.256位B.16位C.8位D.7位9.在单级中断系统中，CPU一旦响应中断，则立即关闭___标志，以防止本次中断服务结束前同级的其他中断源产生另一次中断进行干扰。

A.中断允许B.中断请求C.中断屏蔽10.为了便于实现多级中断，保有现场信息最有效的方法是采用___。

[考研类试卷]计算机专业基础综合数据结构（排序）历年真题试卷汇编9一、综合题1 如果只要找出一个具有n个元素的集合的第k(1≤k≤n)个最小元素，你所学过的排序方法中哪种最适合?给出实现的思想。

【北方交通大学1998六(10分)】2 设结点个数为n，请问采用堆排序法进行排序，其时间复杂性是多少?请以大O 形式给出，并给出证明。

【上海交通大学2004四(10分)】2 已知待排序的序列为(503，87，512，6l，908，170，897，275，653，462)，试完成下列各题。

3 根据以上序列建立一个堆(画出第一步和最后堆的结果图)，希望先输出最小值。

4 输出最小值后，如何得到次小值(并画出相应结果图)。

【同济大学2001二(10分)】4 试将关键字序列(56，塾，55，67，46，58，18，88)5 调整成一个初始大顶堆，用二叉树形式说明调整过程；6 简要说明如何从初始大顶堆开始进行排序。

【华中科技大学2007四、24(10分)】7 一组记录的关键字为(50，79，8，56，32，41，85)，给出利用重建堆方法建立的初始堆(堆顶最大)，并给出堆排序的过程。

【吉林大学2007二、5(4分)】8 已知序列{503，87，512，61，908，170，897，275，653，462)将其调整为堆(大堆顶，即K i≥K2i，K i≥K2i+1)。

【中国海洋大学2006一、4(8分)】9 给定关键字序列(20，18，9，86，72，12，27，40)。

试将该序列建成小根堆。

10 判断下面的每个结点序列是否表示一个堆，如果不是堆，请把它调整成堆。

①100，90，80，60，85，75，20，25，10，70，65，50②100，70，50，20，90，75，60，25，10，85，65，80【复旦大学1997二(8分)】11 全国有10000人参加物理竞赛，只录取成绩优异的前10名，并将他们从高分到低分输出。

2001年数据结构与程序设计试题内容:一、试给出下列有关并查集(mfsets)的操作序列的运算结果：union(1,2) , union(3,4) , union(3,5) , union(1,7) , union(3,6) , union(8,9) , union(1,8) , union(3,10) , union(3,11) , union(3,12) , union(3,13) , union(14,15) , union(16,0) , u nion(14,16) , union(1,3) , union(1,14)。

（union是合并运算，在以前的书中命名为merge）要求(1) 对于union(i,j)，以i作为j的双亲；（5分）(2) 按i和j为根的树的高度实现union(i,j)，高度大者为高度小者的双亲；（5分）(3) 按i和j为根的树的结点个数实现union(i,j)，结点个数大者为结点个数小者的双亲；（5分）二、设在4地（A,B,C,D）之间架设有6座桥,如图所示:要求从某一地出发,经过每座桥恰巧一次,最后仍回到原地(1) 试就以上图形说明:此问题有解的条件是什么? (5分)(2) 设图中的顶点数为n,试用C或Pascal描述与求解此问题有关的数据结构并编写一个算法,找出满足要求的一条回路. (10分)三、针对以下情况确定非递归的归并排序的运行时间(数据比较次数与移动次数):(1) 输入的n个数据全部有序; (5分)(2) 输入的n个数据全部逆向有序; (5分)(3) 随机地输入n个数据. (5分)四、简单回答有关AVL树的问题.(1) 在有N个结点的AVL树中,为结点增加一个存放结点高度的数据成员,那么每一个结点需要增加多少个字位(bit)? (5分)(2) 若每一个结点中的高度计数器有8bit,那么这样的AVL树可以有多少层?最少有多少个关键码? (5分)五、设一个散列表包含hashSize=13个表项,.其下标从0到12,采用线性探查法解决冲突. 请按以下要求,将下列关键码散列到表中.10 100 32 45 58 126 3 29 200 400 0(1) 散列函数采用除留余数法,用%hashSize(取余运算)将各关键码映像到表中. 请指出每一个产生冲突的关键码可能产生多少次冲突. (7分)(2) 散列函数采用先将关键码各位数字折叠相加, 再用%hashSize将相加的结果映像到表中的办法. 请指出每一个产生冲突的关键码可能产生多少次冲突. (8分)六、设一棵二叉树的结点定义为struct BinTreeNode{ElemType data;BinTreeNode *leftChild, *rightChild;}现采用输入广义表表示建立二叉树. 具体规定如下:(1) 树的根结点作为由子树构成的表的表名放在表的最前面;(2) 每个结点的左子树和右子树用逗号隔开. 若仅有右子树没有左子树, 逗号不能省略.(3) 在整个广义表表示输入的结尾加上一个特殊的符号(例如”#”)表示输入结果.例如,对于如右图所示的二叉树, 其广义表表示为A(B(D,E(G,)),C(,F))A/ \B C/ \ \D E F/G此算法的基本思路是:依次从保存广义表的字符串ls中输入每个字符. 若遇到的是字母(假定以字母作为结点的值), 则表示是结点的值, 应为它建立一个新的结点, 并把该结点作为左子女(当k=1)或有子女(当k= 2)链接到其双亲结点上. 若遇到的是左括号”(“, 则表明子表的开始,将k置为1;若遇到的是右括号”)”,则表明子表结果. 若遇到的是逗号”,”, 则表示以左子女为根的子树处理完毕,应接着处理以右子女为根的子树, 将k置为2.在算法中使用了一个栈s, 在进入子表之前,将根结点指针进栈, 以便括号内的子女链接之用. 在子表处理结束时退栈. 相关的栈操作如下:MakeEmpty(s) 置空栈Push(s,p) 元素p进栈Pop(s) 进栈Top(s) 存取栈顶元素的函数下面给出了建立二叉树的算法, 其中有5个语句缺失. 请阅读此算法并把缺失的语句补上. (每空3分)Void CreateBinTree(BinTreeNode *&BT, char ls){Stack<BinTreeNode*>s; MakeEmpty(s);BT=NULL; //置二叉树BinTreeNode *p;int k;istream ins(ls); //把串ls定义为输入字符串流对象insChar ch;ins>>ch; //从ins顺序读入一个字符While(ch!=”#”){ //逐个字符处理,直到遇到'#'为止Switch(ch){case’(‘: _______(1)_______k=1;break;case’)’: pop(s);break;case’,‘: _______(2)_______break;default: p=new BinTreeNode;_______(3)_______p->leftChild=NULL;p->rightChild=NULL;if(BT==NULL)_______(4)_______else if (k==1) top(s)->leftChild=p;else top(s)->rightChild=p;}_______(5)_______}}七、下面是一个用C编写的快速排序算法. 为了避免最坏情况,取基准记录pivot采用从left,right和mi d=[(left+right)/2]中取中间值, 并交换到right位置的办法. 数组a存放待排序的一组记录, 数据类型为Type, left和right是呆排序子区间的最左端点和最右端点.Void quicksort(Type a&#;,int left,int right){Type temp;If(left<right){Type pivot=median3(a,left,right);Int I=left, j=right-1;For( ; ; ){While(i<j && a[i]<pivot) i++;While(i<j && pivot<a[j]) j--;if(i<j){temp=a[i]; a[j]=a[i]; a[i]=temp;I++; j--;}else break;}if(a[i]>pivot){temp=a[i]: a[i]=a[right]; a[right]=temp;}quicksort(a,left,i-1); //递归排序左子区间quicksort(a,i+1,right); //递归排序右子区间}}(1) 用C 或Pascal 实现三者取中子程序 median3(a,left,right); (5分)(2) 改写 quicksort 算法, 不用栈消去第二个递归调用 quicksort(a,i+1,right); (5分)(3) 继续改写 quicksort 算法, 用栈消去剩下的递归调用. (5分)编译原理及操作系统试题内容:编译原理部分1.(5%) 给出下述NFA M 的五元组表示, 并将其确定化2 (5%) 构造一个不具有ε-转移的NFA M ’ , 使得L(M ’)=L(M)3 (10%) 证明文法G[A]是LR(1)文法.G[A]: A->BA|εB->aB|b4 (5%) 证明合并不存在冲突(移进/归约、归约/归约)的LR(1)项目集的同心集不会产生新的移进/归约冲突.5.(5%) 对目标代码运行时的存储空间采用基于过程活动记录的栈式分配方案, 举例说明象PASCAL 这样的语言如何实现对非局部变量的访问.6(15%) 文法G[R]: R->R+R | R ·R | R*| (R) | a | b | ε(1)证明文法G[R] 生成字母表Σ={a, b} 上的所有正规表达式(用+代替”|”, 连接符·没有省略)(2)证明此文法是二义的(3)根据正规式的三个运算符(+,·, *) (或, 连接, 闭包) 的优先性和结合性约定重新构造一个等价的LL(1) 文法7(5%) 找出下列流图中的回边和回边组成的循环.编译中利用流图完成什么工作?操作系统部分一、名次解释（10分）多道程序、多重处理、进程、线程、虚存二、画出NT操作系统的线程状态转移图（10分）三、UNIX系统与Linux系统等中都提供pipe文件功能，简述pipe() 的工作原理。

2001年清华大学计算机原理考研试题试题内容：一、（10分）某RISC处理机各类指令使用频率和理想CPI（指令和数据访问Cache命中率为100％时的CPI）如下表所示。

而实际测得的指令访问Cache缺失率（miss rate）为5％，数据访问的Cache缺失率为10％，Cache的缺失损失（miss penalty）为40个时钟周期。

该机器在无Cache缺失（理想情况）时的CPI是多少？（3分）该机器在无Cache缺失（理想情况）时的速度比有Cache缺失时快多少倍？（7分）指令类型使用频率CPI idealALU操作43％ 1Loads 21％ 2Stores 12％ 2Branches 24％ 2二、（13分）一台模型机共有7条指令，主频25MHz，各指令的使用频率与CPI如下表所示。

该模型机有8位和16位两种指令字长，采用2-4扩展操作码。

8位字长指令为寄存器（R－R）二地址类型，16位字长指令为寄存器－存储器（R－M）二地址变址寻址类型（-128<=变址范围<=127）。

指令（字长）使用频度f CPII1（8位）35% 1I2（8位）25% 2I3（8位）20% 2I4（16位）10% 2I5（16位）5% 1I6（16位）3% 2I7（16位）2% 2计算该机的MIPS速率。

（4分）计算操作码的平均码长。

（3分）该机允许使用多少个可编址的通用寄存器，多少变址寄存器？（3分）设计该机的两种指令格式，标出各字段位数并给出操作编码。

（3分）三、（12分）假设在一个采用组织相联映像方式的Cache中，主存有B0～B7共8块组成，Cache有C0～C3共4块，组内块数为2块。

每块的大小为32个字节，采用FIFO块替换算法。

在一个程序执行过程中依次访问块地址流如下：B1，B4，B6，B3，B0，B4，B6，B2，B4，B5写出主存地址的格式，并标出各字段的长度（3分）写出Cache地址的格式，并标出各字段的长度（3分）画出主存与Cache之间各个块的映像对应关系（3分）列出程序执行过程中Cache的块地址流分布情况。

2001年10月高等教育自学考试计算机网络基本原理试题及答案2001年10月高等教育自学考试计算机网络基本原理试题及答案第一部分选择题一、单项选择题（本大题共20小题，每小题1分，共20分）在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。

1.一座大楼内的一个计算机网络系统，属于（）A、PANB、LANC、MAND、W AN2.计算机网络中可以共享的资源包括（）A、硬件、软件、数据、通信信道B、主机、外设、软件、通信信道C、硬件、程序、数据、通信信道D、主机、程序、数据、通信信道3.网络协议主要要素为（）A、数据格式、编码、信号电平B、数据格式、控制信息、速度匹配C、语法、语义、同步D、编码、控制信息、同步4.采用专用线路通信时，可以省去的通信阶段是（）A、建立通信线路B、建立数据传输链路C、传送通信控制信号和数据D、双方确认通信结束5.通信系统必须具备的三个基本要素是（）A、终端、电缆、计算机B、信号发生器、通信线路、信号接收设备C、信源、通信媒体、信宿D、终端、通信设施、接收设备6.宽带传输通常使用的速率为（）A、0 －10Mbit/sB、1 －2.5Mbit/sC、5 －10Mbit/sD、0 －400Mbit/s7.计算机网络通信系统是（）A、电信号传输系统B、文字通信系统C、信号通信系统D、数据通信系统8.网络接口卡的基本功能包括：数据转换、通信服务和（）A、数据传输B、数据缓存C、数据服务D、数据共享9.完成通信线路的设置与拆除的通信设备是（）A、线路控制器B、调制解调器C、通信控制器D、多路复用器10.在星型局域网结构中，连接文件服务器与工作站的设备是（）A、调制解调器B、交换器C、路由器D、集线器11.在OSI七层结构模型中，处于数据链路层与运输层之间的是（）A、物理层B、网络层C、会话层D、表示层12.完成路径选择功能是在OSI模型的（）A、物理层B、数据链路层C、网络层D、运输层13.下列功能中，属于表示层提供的是（）A、交互管理B、透明传输C、死锁处理D、文本压缩14.在TCP/IP协议簇的层次中，解决计算机之间通信问题是在（）A、网络接口层B、网际层C、传输层D、应用层15.对局域网来说，网络控制的核心是（）A、工作站B、网卡C、网络服务器D、网络互连设备16.在中继系统中，中继器处于（）A、物理层B、数据链路层C、网络层D、高层17.各种网络在物理层互连时要求（）A、数据传输率和链路协议都相同B、数据传输率相同，链路协议可不同C、数据传输率可不同，链路协议相同D、数据传输率和链路协议都可不同18.网络管理系统中，管理对象是指（）A、网络系统中各种具体设备B、网络系统中各种具体软件C、网络系统中各类管理人员D、网络系统中具体可以操作的数据19.Intranet技术主要由一系列的组件和技术构成，Intranet的网络协议核心是（）A、ISP/SPXB、PPPC、TCP/IPD、SLIP20.网络管理信息系统的分析设计以（）A、功能模块设计为中心B、数据分析为中心C、系统拓扑结构设计为中心D、系统规模分析为中心第二部分非选择题二、填空题（本大题共20个空，每空1分，共20分）不写解答过程，将正确的答案写在每小题的空格内。

计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编11(总分：60.00，做题时间：90分钟)一、填空题(总题数：24，分数：48.00)1.二叉树按某种顺序线索化后，任一结点均有指向前驱和后继的线索，这种说法是正确的么?__________【南京理工大学2005二、9(1分)】__________________________________________________________________________________________ 正确答案：(正确答案：说法错误。

只有空指针处才能加线索，左指针指向前驱(遍历的第一个结点无前驱)，右指针指向后继(遍历的最后一个结点无后继)。

)2.线索二元树的左线索指向其__________，右线索指向其__________。

【哈尔滨工业大学2000二、3 (2分)】__________________________________________________________________________________________ 正确答案：(正确答案：(1)前驱 (2)后继)3.将一棵树转换成二叉树后，根结点没有__________子树。

【电子科技大学2005二、2(1分)】__________________________________________________________________________________________ 正确答案：(正确答案：右)4.哈夫曼树是__________。

【北京理工大学200l七、4(2)】【长沙铁道学院1998二、3(2分)】__________________________________________________________________________________________ 正确答案：(正确答案：带权路径长度最小的二叉树，又称最优二叉树)5.若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是__________。

计算机专业基础综合数据结构（集合）历年真题试卷汇编1(总分：82.00，做题时间：90分钟)一、综合题(总题数：25，分数：72.00)1.试用关键字序列(33，10，45，20，53，43，31，15，65，40)，构造哈希(Hash)表，设哈希函数为：H(key)=key％11，其中key为关键字，％为求余运算符；用开放定址法处理冲突，用线性探测再散列法查找空位，用长度为14的数据元素组A[14]表示哈希表。

(1)画出该哈希表的存储结构图；(2)假定每个元素的查找概率相等，计算查找成功时的ASL；(3)计算查找不成功时的ASL。

【华中科技大学2007四、25(10分)】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：(2)ASL 成功 =(6*1+2*3+5+7)／10=24／10(3)ASL 失败=(4+3+2+1+2+1+1+2+1+9+8)／11=34／1 1。

计算方法参见上面58题(3)。

)解析：2.采用哈希函数H(k)=3*k mod 13并用线性探测开放地址法处理冲突，在散列地址空间[0．．12]中对关键字序列22，41，53，46，30，13，1，67，51。

(1)构造哈希表(画示意图)；(2)装填因子；等概率下(3)成功的和(4)不成功的平均查找长度。

【北京工业大学2000三(8分)】【烟台大学2007四、4(10分)】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：(2)装填因子=9／13=0．7 (3)ASL SUCC =11／9 (4)ASL UNSUCC =29／13)解析：3.设散列表长度为14i为键值中第一个字母在字母表中的序号，若键值的输入顺序为Jan，Feb，Mar，Apr，May，Jun，Jul，Aug，Sep，Oct，Nov，Dec，用拉链法处理冲突，要求：(1)构造散列表；(2)求出在等概率情况下，查找成功的平均查找长度。

《计算机操作系统》试卷（5）学号___________ 姓名_________ 成绩_______（适用教材：王万森、汪国安编著《计算机操作系统教程》）一、单项选择题（每题1分，共１0分）1、当某个作业被作业调度程序选中，进入内存开始运行时，作业的状态为Ａ、提交状态Ｂ、完成状态Ｃ、执行状态Ｄ、后备状态2、进程由就绪状态转变为执行状态是通过以下那个调度程序实现的Ａ、作业调度Ｂ、进程调度Ｃ、中级调度Ｄ、驱臂调度3、以下那个不是程序并发执行的特性：Ａ、与速度无关性Ｂ、不可再现性Ｃ、相互制约性Ｄ、通信性4、以下那个叙述正确Ａ、使用静态重定位的系统用户的作业可不要求分配连续的存储空间Ｂ、使用静态重定位的系统作业可在内存中移动Ｃ、使用静态重定位的系统有可能为用户提供一个比内存大的多的地址空间Ｄ、使用静态重定位的系统无需增加硬件地址变换机构5、以下那种存储管理不可用于多道程序系统中Ａ、固定分区存储管理Ｂ、单一连续区存储管理Ｃ、可变分区存储管理Ｄ、段式存储管理6、以下那种存储管理可使用静态重定位Ａ、固定分区存储管理Ｂ、页式存储管理Ｃ、可重定位分区存储管理Ｄ、段式存储管理7、以下那种存储管理会产生内零头Ａ、固定分区存储管理Ｂ、可变分区存储管理Ｃ、可重定位分区存储管理Ｄ、段式存储管理8、以下那个关于纯分页存储管理的叙述不正确Ａ、此种存储管理会产生内零头Ｂ、此种存储管理要求作业一次全部调入内存Ｃ、此种存储管理会产生外零头Ｄ、此种存储管理不要求作业分配连续的存储区9、在移臂调度时读写头从盘的一端开始朝另一端移动，在移动的过程中搜索每个磁道上的请求，若有则服务之，直至到达盘的另一端。

在另一端，磁头移动的方向是相反的，并继续在移动中扫描服务，则此种算法称为Ａ、先来先服务Ｂ、最短查找时间优先Ｃ、SCAN Ｄ、C-SCAN10、死锁定理用于Ａ、预防死锁Ｂ、解除死锁Ｃ、避免死锁Ｄ、检测死锁二、填空题（每题1分，共30分）1、在手工操作阶段，当程序在输入或输出时，ＣＰＵ处于空闲等待，我们称这种现象为___________________________。

时间限制: 1 Sec 内存限制: 32 MB提交: 524 解决: 154题目描述输入任意4个字符(如：abcd)，并按反序输出(如：dcba)输入题目可能包含多组用例，每组用例占一行，包含4个任意的字符。

输出对于每组输入,请输出一行反序后的字符串。

具体可见样例。

样例输入UpincvYjWJpwcXOA样例输出nipUjYvcwpJWAOXc2000年清华大学计算机研究生机试真题1059: abc时间限制: 1 Sec 内存限制: 32 MB提交: 196 解决: 160题目描述设a、b、c均是0到9之间的数字，abc、bcc是两个三位数，且有：abc+bcc=532。

求满足条件的所有a、b、c的值。

输入题目没有任何输入。

输出请输出所有满足题目条件的a、b、c的值。

a、b、c之间用空格隔开。

每个输出占一行。

样例输入样例输出2000年清华大学计算机研究生机试真题1060: 完数VS盈数时间限制: 1 Sec 内存限制: 32 MB提交: 337 解决: 101题目描述一个数如果恰好等于它的各因子(该数本身除外)子和，如：6=3+2+1。

则称其为“完数”；若因子之和大于该数，则称其为“盈数”。

求出2到60之间所有“完数”和“盈数”。

输入题目没有任何输入。

输出输出2到60之间所有“完数”和“盈数”，并以如下形式输出：E: e1 e2 e3 ......(ei为完数)G: g1 g2 g3 ......(gi为盈数)其中两个数之间要有空格，行尾不加空格。

题目描述有N个学生的数据，将学生数据按成绩高低排序，如果成绩相同则按姓名字符的字母序排序，如果姓名的字母序也相同则按照学生的年龄排序，并输出N个学生排序后的信息。

输入测试数据有多组，每组输入第一行有一个整数N（N<=1000），接下来的N行包括N个学生的数据。

每个学生的数据包括姓名（长度不超过100的字符串）、年龄（整形数）、成绩（小于等于100的正数）。

2019年软件与理论笔试数据库：一1、你觉得数据库管理系统的核心技术是什么（10）2、事务的ACID特性指什么（10）3、数据库冲突处理的原则是什么。

根据这个原则。

数据库有哪些冲突处理的方法。

（10）二、（20）数据库以B+树结构存储。

分为索引页与叶级页。

两级索引。

索引页有8000B可以用来存储索引项。

每个索引项80B第一级索引页有两个索引项。

问整个数据库的最大存储空间与最小存储空间是多少。

索引那个题还有个条件是索引页有8000B可以用来存储索引项（就不用转换KB 的1024 T）编译原理：1.画一个有穷自动机（6）2.前五个字符含有dbc字串的正则表达式（7）3.上下文无关文法，不多于五个非终结符，a*b*c*若a只有一个那么be数量相等（7）二：lr,slr（l）分析，那个更快发现错误？（30）2016年清华应用方向复试笔试回忆淸华的计算机方向分为三个，软件理论、系统和应用。

报考人数方而，今年一共进入复试60人，有30人报了应用。

可见应用竞争之激烈。

不过单纯看笔试来说，应用是最简单的，因为应用已经快十年没有换过笔试题了。

上了考场发现今年还是这些题，当时就觉得稳了。

而英它方向上，我听说系统的笔试特别难, 有的人几乎交了白卷。

（软理不太淸楚）因此大家报考的时候要考虑一下复试的难度，究竟是想面对激烈的竞争还是想而对变态的考试难度。

当然听往届的经验来说，好像笔试并不怎么重要的样子。

应用方向的笔试科目有三个，人工智能、多媒体技术和数字信号处理（三科里选两科作答）。

在此建议各位选择人工智能和多媒体技术，难度低、计算量少而且好复习，。

当然如果本科学过信号处理的话也可以选，一切还是看自己。

人工智能：1、给岀一个博弈树，进行a-卩剪枝搜索，标出何处发生剪枝、肖点的倒推值和最佳走步2、谓词归结法证明、修改证明树、提取问题的回答。

3、1）描述一个你熟悉的人工智能方法，并简述特点2）下列两个问题是否适合用人工智能方法进行解决，如果适合请简单解释，不适合请给出理由。

清华计算机考研试题《数据结构》一、选择题123 给了一序列比如6.7.4.8.9.3.散列函数是H(key)=key%11.一问成功时的平均搜索长度二问不成功的平均搜索长度4 哪种数据结构，从某一个结点到根结点的路径序列组成一个降序排列a. b.最大堆 c.最小堆 d5 还有一个题是关于关键路径的，答案选项是49/B -C \A /F\ \\D-E H\G/6 什么是数据结构？ A B C定义在一个数据集合上的属性和操作 D7 高度为h的完全二叉树，一共有多少种？A B 2^(h-1) C D二、证明题1. 什么样的有向无环图有唯一的拓扑有序序列，并证明。

三、计算题1 有n个结点的二叉树最大高度，最小高度分别是多少？其中g和f函数的作用是通过输入参数，进行一系列运算后返回。

相当于Ti 以a和a[i-1]为输入参数，a和b为输出。

要求使用pv原语，实现T1～Tn-1的并发互斥，尽量保证最大限度的并发。

(a[i-1]为Ti-1线程的结果,)四、进程同步问题假设当前处于非抢占调度策略，进程只有两种方式可以放弃cpu，一个是主动调用系统调度函数yield()，此时进程主动放弃cpu；另一个方式是当进程执行I/O 操作时，系统将调度下一个进程。

试分析如下三种进程对，何时会出现不符合下列原则，并说明原因：1）空闲则入 2)有限等待 3）保证互斥。

第一种：Thread1(){yield();----critical section-----g=g+b;f=g-a; //这部分确切的语句想不起来了，但不影响。

只要记得临界区不能被打断。

----critical section-----}Thread2(){----critical section-----g=g+b;f=g-a;----critical section-----}第二种：Thread1(){yield();----critical section-----g=g+b;f=g-a;----critical section----- }Thread2(){----critical section-----g=g+b;f=g-a;----critical section-----yield();}第三种：Thread1(){yield();----critical section-----g=g+b;fstring=printf(……) ; // 调用I/O;f=g-a;----critical section-----}Thread2(){yield();----critical section-----g=g+b;f=g-a;----critical section-----}五文件操作题很长，大意如下给定两种文件系统，分别采用FAT方式和索引方式组织文件结构。

基于ASP的在线考试系统刘勇林（计算机系，2001（2）班，01261229号）[摘要]本文论及Internet环境下，基于ASP的在线考试系统的解决方案，介绍了在线考试系统的功能、系统设计以及人机交互的实现，讨论了在线考试系统的实现策略，对系统文件及数据库的保护、系统的安全性等。

[关键词]在线考试系统Asp Access数据库1 引言随着计算机技术、网络通信技术、多媒体技术和虚拟现实技术在教育领域中应用的不断发展,教育方式正面临着一场巨大的变革。

在线考试系统是建立在互联网上的应用系统,客户端的配置较为简单, 考试可以不受地域的限制.一个完备的在线考试系统可以使用户在网上学习后及时检验自己的学习效果, 以发现自己的不足, 提高学习效率. 在线考试系统中试卷的生成、提交和批阅等都可以在网络上自动完成. 只要形成一套成熟的题库就可以实现考试的自动化. 这样, 教师所要做的只是精心设计不同类型的试题和题库的维护, 而不是组织考试, 从而大大减轻了教师的负担。

2 ASP技术概述2.1定义和特点ASP(Active Server Pages)是Microsoft 于1996年11月推出的Web应用程序开发技术是一种服务器端的脚本开发环境。

通过ASP能创建和运行动态、交互和高效的页面组成的Web服务程序。

对于程序员，所谓ASP, 简单地说，就是在HTML文件中引入了两个扩展的成对的HTML标记〈%和%〉，同时文件的扩展名改为 .asp。

同HTML文件一样ASP文件也是文本文件，包括文本、HTML标记和ASP脚本语句（用〈%和%〉界定符标记）。

它以.asp 为扩展名,区别于一般的HTML文件。

任何文本编辑器都可以制作ASP文件。

ASP是微软公司IIS3.0中的一个组件，它实际上是一个服务器端的脚本环境。

当脚本运行在服务器上（注意不是客户机）时，Web服务器完成所有的工作，包括动态生成HTML页面并传送到用户的浏览器上。