下载文档原格式
清华计算机考研试题《数据结构》一、选择题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方式和索引方式组织文件结构。
2019年全国硕士研究生招生考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：1~40小题，每小题2分，共80分。
下列每题给出的四个选项中，只有一个选项符合试题要求。
1.设n是描述问题规模的非负整数，下列程序段的时间复杂度是x=0；while(n>=(x+l)*(x+l))x=x+l；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. 56B. 57C. 58D. 604.在任意一棵非空平衡二又树(AVL树)T1中，删除某结点v之后形成平衡二又树T2，再将w插入T2形成平衡二又树T3。
下列关于T1与T3的叙述中，正确的是I.若v是T1的叶结点，则T1与T3可能不相同Ⅱ.若v不是T1的叶结点，则T1与T3一定不相同Ⅲ.若v不是T1的叶结点，则T1与T3一定相同A. 仅IB. 仅IIC. 仅I、ⅡD. 仅I、Ⅲ5.下图所示的AOE网表示一项包含8个活动的工程。
活动d的最早开始时间和最迟开始时间分别是A. 3和7B. 12和12C. 12和14D. 15和156.用有向无环图描述表达式(x+y)*((x+y)/x)，需要的顶点个数至少是A. 5B. 6C. 8D. 97.选择一个排序算法时，除算法的时空效率外，下列因素中，还需要考虑的是I.数据的规模Ⅱ.数据的存储方式Ⅲ.算法的稳定性V.数据的初始状态A. 仅ⅢB. 仅I、ⅡC. 仅Ⅱ、Ⅲ、IVD. I、Ⅱ、Ⅲ、Ⅳ8.现有长度为11且初始为空的散列表HT，散列函数是H(key)=key%7，采用线性探查(线性探测再散列)法解决冲突将关键字序列87，40，30，6，11，22，98，20依次插入到HT后，HT查找失败的平均查找长度是A. 4B. 5.25C. 6D. 6.299.设主串T=“abaabaabcabaabc”，模式串S=“abaab c”，采用KMP算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是A. 9B. 10C. 12D. 1510. 排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。
清华大学研究生入学试卷二一．一．选择题（每小题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.为了便于实现多级中断，保有现场信息最有效的方法是采用___。
2019年全国硕士研究生招生考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：1~40小题，每小题2分，共80分。
下列每题给出的四个选项中，只有一个选项符合试题要求。
1.设n是描述问题规模的非负整数，下列程序段的时间复杂度是x=0；while(n>=(x+l)*(x+l))x=x+l；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. 56B. 57C. 58D. 604.在任意一棵非空平衡二又树(AVL树)T1中，删除某结点v之后形成平衡二又树T2，再将w插入T2形成平衡二又树T3。
下列关于T1与T3的叙述中，正确的是I.若v是T1的叶结点，则T1与T3可能不相同Ⅱ.若v不是T1的叶结点，则T1与T3一定不相同Ⅲ.若v不是T1的叶结点，则T1与T3一定相同A. 仅IB. 仅IIC. 仅I、ⅡD. 仅I、Ⅲ5.下图所示的AOE网表示一项包含8个活动的工程。
活动d的最早开始时间和最迟开始时间分别是A. 3和7B. 12和12C. 12和14D. 15和156.用有向无环图描述表达式(x+y)*((x+y)/x)，需要的顶点个数至少是A. 5B. 6C. 8D. 97.选择一个排序算法时，除算法的时空效率外，下列因素中，还需要考虑的是I.数据的规模Ⅱ.数据的存储方式Ⅲ.算法的稳定性V.数据的初始状态A. 仅ⅢB. 仅I、ⅡC. 仅Ⅱ、Ⅲ、IVD. I、Ⅱ、Ⅲ、Ⅳ8.现有长度为11且初始为空的散列表HT，散列函数是H(key)=key%7，采用线性探查(线性探测再散列)法解决冲突将关键字序列87，40，30，6，11，22，98，20依次插入到HT后，HT查找失败的平均查找长度是A. 4B. 5.25C. 6D. 6.299.设主串T=“abaabaabcabaabc”，模式串S=“abaabc”，采用KMP算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是A. 9B. 10C. 12D. 1510. 排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。
中国科学院大学攻读硕士学位研究生入学统一考试试题科目名称：计算机专业综合考生须知：1．本试卷满分为150分，全部考试时间总计180分钟。
2．所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。
3．试卷共16道大题，每题15分，共240分，考生可以任意选择其中10道大题回答，并在答题纸的该题答案前标明“选做本题”。
4．如果选做的题目多于10道，则判卷将按照所选做试题的题号顺序选择前10道大题计分，后续所做视为无效考试内容。
第一部分：《数据结构》第一题，简答题，共15分（1）请给出下列程序的时间复杂度（n>0）。
（2分）void func(int n) {int i,j;for(i=1,j=0; j<=n; j=j+i) i++;}（2）现有一个线性表的应用，线性表的元素总数不确定，其主要的操作是插入元素、删除表尾元素、查找表尾结点和查找指定结点的前驱结点，那么请问用怎样的数据结构比较好？请给出理由和该数据结构的C语言定义。
（3分）（3）若循环队列存储在数组A[0..m]，头指针Front指向当前队头元素，尾指针Rear指向当前队尾元素的下一个位置，那么当前实际存储有多少队列元素？现有元素x需要入队，请写出元素入队的语句。
（3分）科目名称：计算机专业综合第1页共6页（4）用如下数据结构存储广义表：typedef enum {ATOM, LIST} ElemTag;typedef struct GLNode {ElemTag tag;union {AtomType atom;struct {struct GLNode *hp, *tp;} ptr;}} *Glist;那么，对于广义表X=(A,((),(B,C)),(D,E))，给出其存储结构图，并利用Head、Tail 操作分离出元素E。
（3分）（5）现在需要从5000个元素组成的序列中，用最快的速度挑出前10个最大的元素。
请在插入排序、快速排序、堆排序、归并排序、基数排序中选择一个最合适的排序方法，并说明理由。
一、单项选择题：1-40题，每题20分共80分。
在每个小题给出的四个选项中选正确答案。
1、若元素a、b、c、d、e、f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈工作，则不可能得到的出栈序列是（）A、dcebfaB、cbdaefC、bcaefdD afedcb2、某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的顺顺序是（）A、bacdeB、dbaceC、dbcaeD ecbad3、下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是（）4、在下列所示的平衡二叉树中插入关键字48后得到一棵新平衡二叉树，在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是（）A、13，48B、24，48C、24，53D 24，905、在一棵度数为4的树T中，若有20个度为4的结点，10个度为3的结点，1 个度为2的结点，10个度为1的结点，则树T的叶结点个数是（）A、41B、82C、113D 122 6对n （n>=2）个权值均不相同的字符构成哈弗曼树，关于该树的叙述中，错误的是（）A、该树一定是一棵完全二交叉B、树中一定没有度为1的结点C、树中两个权值最小的结点一定是兄弟结点D树中任一非叶结点的权值一定不小于下一层任一结点的权值7、若无向图G=（ V.E）中含7个顶点，则保证图G在任何情况下都是连通的，则需要的边数最少是（）A 6B、15C、16D 218、对下图进行拓扑排序，可以得到不同的拓扑序列的个数是（）A 4B、3C、2D 19、已知一个长度为16的顺序表L,其元素按关键字有序排列，若采用折半查找法查找一个不存在的元素，则比较次数最多的是（）A 4B、5C、610.采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是（）A、递归次数于初始数据的排列次数无关B、每次划分后，先处理较长的分区可以减少递归次数（勤思考研）C、每次划分后，先处理较短的分区可以减少递归次数D递归次数与每次划分后得到的分区处理顺序无关11.对一组数据（2，12，16, 88, 5，10）进行排序，若前三趟排序结果如下：（）第一趟：2，12，16，5，10，88第二趟：2，12，5，10，16，88第三趟：2，5，10，12，16，88则采用的排序方法可能是A.冒泡排序法B.希尔排序法C.归并排序法D.基数排序法12.下列选项中，能缩短程序执行时间的措施是（）1.提高CPU时钟频率2.优化通过数据结构3.优化通过程序A.仅1和2B.仅1和3C.仅2和3D.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 r414.假定变量i ,f,d数据类型分别为int, float, double（i nt用补码表示，float 和double用IEEE754单精度和双精度浮点数据格式表示），已知i=785 ,f=1.5678e3 , d=1.5e100,若在32位机器中执行下列关系表达式，则结果为真的是()(I)i==(i nt)(float)l(II)f==(float)(i nt)f(III)f==(float)(double)f(IV)(d+f)-d==fA.仅I和llB.仅l和lllC.仅ll 和lllD.仅Ill 和IV15.假定用若干个2K x 4位芯片组成一个8K x 8为存储器，则0B1FH所在芯片的最小地址是()A.0000HB.0600HC.0700HD.0800H16.下列有关RAM和ROM得叙述中正确的是()I RAM是易失性存储器，ROM是非易失性存储器II RAM和ROM都是采用随机存取方式进行信息访问III RAM 和ROIW可用做CacheIV RAM和RON都需要进行刷新A.仅I和IIB.仅II 和IllC.仅I ,11，IllD.仅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、SCS k RAM MIPSD.ISA、EISA、PCI、PCI-Express21.单级中断系统中，中断服务程序执行顺序是（）I保护现场II开中断III关中断IV保存断点V中断事件处理VI恢复现场VII中断返回A l->V->VI->ll->VIIB、III->I->V->VIIC、III->IV->V->VI->VIID IV->I->V->VI->VII22、假定一台计算机的显示存储器用DRAM芯片实现，若要求显示分辨率为1600*1200,颜色深度为24位，帧频为85HZ现实总带宽的50卿来刷新屏幕, 则需要的显存总带宽至少约为（）A、245MbpsB、979MbpsC、1958MbpsD 7834Mbps23、下列选项中，操作S提供的给应程序的接口是（）A、系统调用B、中断C、库函数D原语24、下列选项中，导制创进新进程的操作是（）I用户登陆成功II设备分配III启动程序执行A、仅I和IIB、仅II 和IIIC、仅I和IIID I 、II 、III25、设与某资源相关联的信号量初值为3,当前值为1,若M表示该资源的可用个数，N表示等待该资源的进程数，则M N分别是()A 0，1B、1，0C、1，2D 2，026、下列选项中，降低进程优先权级的合理时机是()A、进程的时间片用完B、进程刚完成I/O ,进入就绪列队C、进程长期处于就绪列队D进程从就绪状态转为运行状态27、进行PO和P1的共享变量定义及其初值为()booleam flag[2] 。
计算机考研测试题及答案计算机考研是众多计算机专业学生晋升硕士研究生的通道之一，也是对学生计算机知识体系的全面考察。
在备考过程中，掌握并解答各类测试题是非常重要的。
本文将为大家提供一些常见的计算机考研测试题及答案，帮助大家更好地备考。
一、数据库1. 数据库中的ACID是指什么？请分别解释。
ACID是数据库事务处理的四个基本属性的缩写，包括原子性（Atomicity）、一致性（Consistency）、隔离性（Isolation）和持久性（Durability）。
具体解释如下：- 原子性：事务中的所有操作要么全部执行成功，要么全部失败回滚，不存在部分执行的情况。
- 一致性：事务的执行使数据库从一个一致性状态转换到另一个一致性状态，数据库在事务开始前后都必须满足一致性约束。
- 隔离性：事务的执行是相互隔离的，一个事务的中间结果不会被其他事务看到。
- 持久性：事务一旦提交，其结果就应该是永久性的。
2. 什么是数据库的三范式？数据库的三范式是指对数据的组织进行规范化的方式，包括第一范式、第二范式和第三范式。
- 第一范式：表中的字段都是单一属性的，不可再分。
- 第二范式：满足第一范式的基础上，非主键字段必须完全依赖于主键。
- 第三范式：满足第二范式的基础上，非主键字段之间不能存在传递依赖关系。
二、操作系统1. 什么是进程和线程？它们之间的区别是什么？- 进程：是指计算机中正在运行的程序，它具有独立的执行流、独立的资源和独立的地址空间。
- 线程：是进程中的一个实体，可以被操作系统调度执行，它与同一进程中的其他线程共享资源和地址空间。
两者的区别主要有以下几点：- 资源开销：进程之间切换的开销较大，线程之间切换的开销较小。
- 执行效率：线程的创建、撤销和切换比进程快。
- 数据共享：同一进程中的线程共享地址空间和资源，进程之间的数据共享需要进行特殊的处理。
2. 什么是死锁？如何避免死锁？死锁是指两个或多个进程在执行过程中因争夺资源而造成的一种僵局，彼此等待对方释放资源而无法继续执行。
一、单选题（每题 2 分，共20分）1. 1.对一个算法的评价，不包括如下（B ）方面的内容。
A．健壮性和可读性B．并行性C．正确性D．时空复杂度2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。
A. p->next=HL->next; HL->next=p;B. p->next=HL; HL=p;C. p->next=HL; p=HL;D. HL=p; p->next=HL;3. 3.对线性表，在下列哪种情况下应当采用链表表示？( )A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C )A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 35. 5.AOV网是一种（）。
A．有向图B．无向图C．无向无环图D．有向无环图6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。
A．低于链接法处理冲突 B. 高于链接法处理冲突C．与链接法处理冲突相同D．高于二分查找7.7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。
A．值B．函数C．指针D．引用8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。
A．行号B．列号C．元素值D．非零元素个数9.9.快速排序在最坏情况下的时间复杂度为（）。
A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2)10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。
A. O(n)B. O(1)C. O(log2n)D. O(n2)二、二、运算题（每题 6 分，共24分）1. 1.数据结构是指数据及其相互之间的______________。
当结点之间存在M对N（M：N）的联系时，称这种结构为_____________________。
时间限制: 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的正数）。
研究生入学试卷四一．选择题（每小题1分，共10分）1.冯.诺依曼机工作方式的基本特点是___。
A．多指令流单数据流 B.按地址访问并顺序执行指令C．堆栈操作 D.存储器按内容选择地址2.下列数中最大的数为___。
A．（10010101）2 B.（227）8 C.（96）16 D.（143）53.若浮点数用补码表示，则判断运算结果是否为规格代数的方法是___。
A．阶符与数符相同为规格代数 B.阶符与数符相异为规格代数C．数符与尾数小数点后第一位数字相异为规格代数D．数符与尾数小数点后第一位数字相同为规格代数4.某计算机字长处32 位，其存储容量为4MB，若按字编址，寻址范围是___。
A．0~~1M B.0~~4MB C.0~~4M D.0~~1MB5.双端口存储器在___情况下会发生读/写冲突。
A．左端口与右端口的地址码不同 B.左端口与右端口的地址码相同C．左端口与右端口的数据码相同 D.左端口与右端口的数据码不同6.从以下有关RISC的描述中选择正确答案___。
A．A．采用RISC技术后，计算机的体系结构又恢复到早期的比较简单的情况B．B．RISC是从原来CISC系统的指令系统中挑选一部分实现的C．C．RISC的主要目标是减少指令数D．D．RISC没有乘、除法指令和浮点运算指令7.在某CPU中设立了一条等待（WAIT）信号线，CPU在存贮器读周期T的时钟的下降沿采样W AIT线，请在下面的叙述中选出两个正确描述的句子___。
A.如WAIT为高电平，则在T2周期后不进入T3周期，而插入一个T W周期B.T W周期结束后，不管W AIT线状态如何一定转入T3周期C.T W周期结束后，只要W AIT线为低则连续插入一个T W周期直到W AIT线变高，才转入T3周期D.有了W AIT线，就可使CPU与任何速度的存储器相连接，保证了CPU与存储器连接时的时序配合8.以下描述中基本概念不正确的句子是___。
2019清华⼤学⾃主命题计算机专业基础综合（912）回忆⼀、数据结构（70分）1. 判断题（12*2=24）(1) n logloglogn = Ο(⌊logn⌋!) (2)交换哈夫曼树的不同深度的节点，编码长度必然改变(3)即使不使⽤改进的 next 表，kmp 依然可以达到线性的时间复杂度(4)对于不符合局部性原理的访问，splay 的分摊复杂度不是 logn(5)对于⼆叉树，通过先序遍历和后序遍历不能确定其层次遍历(6)对于叶节点为 2019 的真⼆叉树，其数量⼩于 2018 对括号所组成的合法表⽰式数量(7)对于叶节点数量为 2018 的⼆叉树，层次遍历队列容量必然⼩于 2018(8)插⼊排序每次插⼊数据，即使不增加循环节，也不⾄减少(9)交换两个逆序对，必然会减少总逆序对数(10)如果基数排序底层采⽤不稳定的算法，那么得到的结果可能是不正确的(11)函数的调⽤栈中如果有相同的函数，则他们必然紧邻(12)如果插⼊的关键码独⽴均匀分布，堆的插⼊操作平均O(1)2. 简答题，每题回答不超过80字（8*4=32）(1)逆波兰表达式的优点？既然中缀转换为逆波兰就需要可以计算出表达式值，那逆波兰意义何在？(2)DFS中何时标记前向边？何时标记后向边？(3)相⽐锦标赛排序，败者树的优势是？(4)试举出红⿊树优于 AVL 树的场景，红⿊树相⽐ AVL 树的优势(5)相⽐开散列，闭散列的优势，试举例说明两点。
(6)相⽐选择排序，插⼊排序的优势，试举例说明两点。
(7)对于稠密图，迪杰斯特拉应该使⽤多叉堆替换⼆叉堆，为什么？多叉堆分叉数m怎么确定？(8)在何种情形下,KMP优于蛮⼒算法，为什么？3. 算法题 (7+3+4 = 14)返回后序遍历的第 K 个节点，时间复杂度不超过 x 的深度，Ο(depth(x)) struct BinNode{int size; //当前节点和孩⼦总数BinNode *lchild,*rchild;};BinNode *rank(BinNode* t,int k){//有效代码⾏数不超过 12 ⾏//不要尝试模拟后序遍历，时间复杂度会超时。
清华计算机考研试题《数据结构》一、选择题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方式和索引方式组织文件结构。
计算机专业考研试题及答案一、概述计算机专业考研是许多计算机领域学生进一步深造的重要方式。
为了帮助考生更好地准备考试，本文整理了一些常见的计算机专业考研试题及答案，希望对考生起到一定的帮助。
二、数据结构1. 什么是数据结构？答案：数据结构是指将数据元素之间的关系组织起来的一种方式。
它包括了数据的存储结构和数据的操作。
2. 数据结构有哪些基本分类？答案：常见的基本数据结构分类包括线性结构（如数组、链表、栈、队列等）、树结构（如二叉树、二叉搜索树、平衡二叉树等）和图结构。
3. 请写出快速排序算法的代码。
答案：以下是一种常见的快速排序算法的代码实现：```javapublic static void quickSort(int[] arr, int low, int high) {if (low < high) {int pivot = partition(arr, low, high);quickSort(arr, low, pivot - 1);quickSort(arr, pivot + 1, high);}}public static int partition(int[] arr, int low, int high) { int pivot = arr[low];while (low < high) {while (low < high && arr[high] >= pivot) {high--;}arr[low] = arr[high];while (low < high && arr[low] <= pivot) {low++;}arr[high] = arr[low];}arr[low] = pivot;return low;}```三、操作系统1. 操作系统的主要功能是什么？答案：操作系统是计算机系统的核心软件，主要负责管理和控制计算机硬件资源，提供用户和计算机应用程序之间的接口。
2019年软件与理论笔试数据库：一1、你觉得数据库管理系统的核心技术是什么（10）2、事务的ACID特性指什么（10）3、数据库冲突处理的原则是什么。
根据这个原则。
数据库有哪些冲突处理的方法。
（10）二、（20）数据库以B+树结构存储。
分为索引页与叶级页。
两级索引。
索引页有8000B可以用来存储索引项。
每个索引项80B第一级索引页有两个索引项。
问整个数据库的最大存储空间与最小存储空间是多少。
索引那个题还有个条件是索引页有8000B可以用来存储索引项（就不用转换KB 的1024了）编译原理：1.画一个有穷自动机（6）2.前五个字符含有abc字串的正则表达式（7）3.上下文无关文法，不多于五个非终结符，a*b*c*若a只有一个那么b c数量相等（7）二：lr,slr(1)分析，那个更快发现错误？（30）2016年清华应用方向复试笔试回忆清华的计算机方向分为三个，软件理论、系统和应用。
报考人数方面，今年一共进入复试60人，有30人报了应用。
可见应用竞争之激烈。
不过单纯看笔试来说，应用是最简单的，因为应用已经快十年没有换过笔试题了。
上了考场发现今年还是这些题，当时就觉得稳了。
而其它方向上，我听说系统的笔试特别难，有的人几乎交了白卷。
（软理不太清楚）因此大家报考的时候要考虑一下复试的难度，究竟是想面对激烈的竞争还是想面对变态的考试难度。
当然听往届的经验来说，好像笔试并不怎么重要的样子。
应用方向的笔试科目有三个，人工智能、多媒体技术和数字信号处理（三科里选两科作答）。
在此建议各位选择人工智能和多媒体技术，难度低、计算量少而且好复习，。
当然如果本科学过信号处理的话也可以选，一切还是看自己。
人工智能：1、给出一个博弈树，进行α-β剪枝搜索，标出何处发生剪枝、节点的倒推值和最佳走步2、谓词归结法证明、修改证明树、提取问题的回答。
3、1）描述一个你熟悉的人工智能方法，并简述特点2）下列两个问题是否适合用人工智能方法进行解决，如果适合请简单解释，不适合请给出理由。
（人类是否灭亡和大气污染程度）多媒体技术（顺序记不清了）：1、JPEG压缩的原理、信号损失发生在哪个环节，DCT变换的作用2、多媒体技术的定义、举出5个以上你所知道的多媒体技术。
3、求信号的哈夫曼编码、平均码长和信源的熵。
4、查全率和准确率的区别，求两个图像的颜色直方图并求相似度5、DPCM原理，一个L阶均匀量化器的输出位数n是多少（这道题有点记不清了，大概是这样）复习教材方面，人工智能选用林尧瑞、马少平的《人工智能导论》，多媒体技术选用钟玉琢的《多媒体计算机技术基础及应用（第3版）》2015年3月软理方向复试笔试数据库（共5道简答题，每题10分）：1关系数据库系统的核心技术是什么2简述事务的ACID特性3请描述一下数据库的故障恢复过程4数据库为什么要进行查询优化5数据库中为什么要进行并发控制？都有哪些技术可以来完成并发控制？编译原理（共3道大题，第一道15分，第二道24分，第三道8分，总分应该50分）一（2道小题，第一道5分，第二道10分）1写一个NFA，{a,b}其中不得出现连续2个b，NFA状态不多于6个。
2见下图（编译原理第一大题，基本类似），写每个语言的二义文法和无二义文法各一个，总共2个语言。
二（6道小题，都是基于LR分析的）其中有SLR(1)填表和项目集，然后有关于LR(1)和LALR(1)的内容，最后是发现错误LALR （1）和SLR（1）谁更早，举例说明。
具体可以参照《编译原理》张素琴那本书第7章练习题中第6、14、15题。
三（4道小题，关于代码优化部分）第一个是填表，第二个第三个是关于ud链和du链的，第四个应该是填空。
图形见下图（编译原理第三大题，类似）。
今年编译原理没有考DFA和NFA的转换，也没有考LL分析，所以编译原理的复习一定要全，看往年的贴子你就会发现每年题都不一样，考试的重点也不一样，所以经验贴意义不大。
清华CS 2014应用方向笔试试题回忆人工智能1. 谓词归结法证明，修改证明树，提取问题回答。
2. α-β剪枝。
3. A*算法求解8数码问题。
4. 介绍一种机器学习算法。
多媒体1. 多媒体技术定义，特征，关键技术。
2. L阶均匀量化器的输出位数n; DPCM原理。
3. huffman编码，平均码长，信源的熵。
4. JPEG压缩编码原理，信息损失发生在哪一步，DCT变换的作用。
5. 查全率和准确率，利用颜色直方图进行图像检索的原理，求两幅图像的颜色直方图，并求相似度。
清华CS 2013应用方向笔试题回忆多媒体1 多媒体的概念，特征，及关键技术2 DPCM的原理，量化已知L，求n3 求信源的Huffman编码，计算信源的熵以及编码的平均码长。
4 JPEG压缩编码原理及实现过程，信息的损失发生在哪一步？离散余弦变换的作用。
5 查全率和准确率的区别，给两幅2值图像求其颜色直方图，说明直方图的相似度。
人工智能1 α-β剪枝2 A搜索3 h（n）单调，是否一定满足A*4 简介一种机器学习方法清华CS复试2013笔试编译原理回忆一.给定一个文法S -> S$S | a | b | c问：（1）将该文法转化为非二义性的上下文无关文法（2）给出文法表示语言的正则表示（3）给出文法对应的有限自动机（第二题和第三题用的是同一个文法，具体题目的顺序记不清了，请后来的同学补充）二.给定一个文法S -> AS -> εA -> aA -> (S)S并附文法LR（0）图一张（这个可以自己动手画一画）问：（1）求出各产生式右部符号的FIRST集以及产生式左部符号的FOLLOW集（2）使用一问的结果填写递归下降分析表（一个LL（1）表）（3）证明该文法是一个LL（1）文法（4）看图指出图中哪些状态存在冲突，指出冲突的类型以此证明该文法不是LR（0）文法（5）证明该文法是SLR（0）文法（6）填写该文法的LR分析表（7）'(a))'不是该文法的句子，请问使用LR分析时在哪个状态出错？四.第四题是真的记不清了，这道题是关于DISPLAY表的，一共5分。
题目大概是这样的：给定一个类似PASCAL的程序（程序中允许嵌套定义函数）然后给出一个DISPLAY表，问题是求DISPLAY表中第18、19、22、23行各应该填什么这几行对应RA（返回地址）、SL（似乎叫静态链）、DL（动态链），然后把它们的内容补充完整就行了。
（DISPLAY表我不太熟悉，考试的时候几乎是蒙的，考题实际上很简单，明年考编译的同学可以多花点时间做点DISPLAY表方面的题）2012清华软件理论方向笔试试题回忆版每部分50分，共100分数据库部分一、数据库管理系统（DBMS）的核心技术是什么？（15分）二、数据库中可以定义视图，为什么不能在视图上对数据库进行插入，修改，删除操作？（20分）（表述可能有出入，大致意思如此）三、什么是主索引？主索引可以是顺序存储，可以是B+树，为什么不能是hash存储？（15分）编译原理部分一、画一个DFA，不超过5个状态，表示语言L(G)={w|w上含有且仅含有奇数个ab字串}，字母表{a,b}（6分）二、写正规式，表示语言L(G)={w||w|>=2且w中至少含有两个位置不同的字符}，字母表{a,b}（表述可能不准确，欢迎指正）（6分）三、写一个上下文无关文法，表示字母表{a,b}上的其中不含ab串的字符串，非终结符不超过4个。
（6分）四、给一个LR（1）的DFA，有三问：第一问让补充完整DFA；第二问问项目规范集中存在什么冲突；第三问让写完整的LR（1）分析表（18分）五、语义处理题，描述很长，让你按照描述写（1）E->E(与非)E （2）repeat S until E的语义规则，题目很麻烦，教材上也没有相似类型的题目，我是照葫芦画瓢仿写的，也不知道对不对。
（14分）另外推荐下参考书目，都是清华自己出的教材：数据库用冯建华，郝晓龙，周立柱编著的《数据库系统设计与原理（第二版）》，清华大学出版社编译原理用张素琴，吕映芝，蒋维度，戴桂兰编著的《编译原理（第二版）》，清华大学出版社2012清华大学复试应用方向笔试试题回忆应用方向一般都选择人工智能和多媒体技术两个学科，每年题目变化很小，基本同往年一样，这里要说明下人工智能是指人工智能导论的内容，网上下载的清华大学网络课堂关于人工智能的有三个，分别是《人工智能导论》和《人工智能原理》以及《人工智能（研究生）》。
考试主要内容都是人工智能导论里的。
人工智能：1、一个博弈树的α-β剪枝：给定一幅博弈树的图按从左到右的顺序进行α-β剪枝搜索，试标明各生成节点的到推值，何处发生剪枝，及应选择的走步。
2、A算法求解从初始节点S到目标节点T的路径3、谓词结法证明，并修改证明树，提取问题的回答。
4、介绍一种你熟悉的机器学习方法，并分析其特点。
多媒体技术：1、多媒体技术的定义2、写出音频差分编码(DPCM)的原理。
量化方法的分类。
某均匀量化器的输出为L阶，输出编码位数n位。
则已知L的话，n的值是多少？3、求信源的Huffman编码，计算信源的熵以及编码的平均码长。
4、JPEG压缩编码原理及实现过程，信息的损失发生在哪一步？离散余弦变换的作用。
5、查全率和准确率的区别，给两幅2值图像求其颜色直方图，说明直方图的相似度。
2012年系统复试笔试参考系统结构：小题可以参考09年的，大题的话我也不知道，是我第一次碰见的，有个好像叫你画加法减法的ALU连接图软件工程：主要参考09年面向对象建模的那道大题，其他可把清华大学软件工程课件作为参考书吧系统结构最后一道题目：1.写出全加器中s和c的逻辑表达式。
2.根据以上的加法器和给出的与门、或门、非门，设计出能够完成与（op=00）、或（op=01）、加法（op=10）的ALU。
3.根据以上ALU，设计出能够完成减法（op=11）的ALU。
系统结构一道填空：具体数据记不清了硬盘5400转/分，数据传输速率5MB/s，平均寻道时间12ms，启动时间2ms，求问传输512B 数据要____和传输4KB数据需要____？（求时间）系统结构一道填空，往年考过的：64KB的Cache，每块4B，地址是32位，问Cache包含的位数是____软工第一道题：需求分析的，给一个关于银行ATM的具体需求，让你看看那地方不对。
最后一道题为黑盒测试，建议好好复习。
系统结构还有连线题，不过和09年的那些完全不同了，建议多了解些，以后估计还会出。
2011复试笔试各科题目数据库：（一共两大题。
第一大题30分。
第二大题20分）一1、你觉得数据库管理系统的核心技术是什么2、事务的ACID特性指什么3、数据库冲突处理的原则是什么。
