清华大学-912-2019-真题回忆版.pdf-资料库

763a07dc-71e9-4807-837a-05bc993dfb01.pdf-第1页.png

第1页 / 共10页

763a07dc-71e9-4807-837a-05bc993dfb01.pdf-第2页.png

第2页 / 共10页

763a07dc-71e9-4807-837a-05bc993dfb01.pdf-第3页.png

第3页 / 共10页

763a07dc-71e9-4807-837a-05bc993dfb01.pdf-第4页.png

第4页 / 共10页

763a07dc-71e9-4807-837a-05bc993dfb01.pdf-第5页.png

第5页 / 共10页

763a07dc-71e9-4807-837a-05bc993dfb01.pdf-第6页.png

第6页 / 共10页

763a07dc-71e9-4807-837a-05bc993dfb01.pdf-第7页.png

第7页 / 共10页

763a07dc-71e9-4807-837a-05bc993dfb01.pdf-第8页.png

第8页 / 共10页

清华大学 912 考研真题回忆版数据结构(70) 判断题 (12*2=24) (1) nlogloglogn = Ο(⌊logn⌋!) (2)交换哈夫曼树的不同深度的节点，编码长度必然改变 (3) 伸展树若不具备局部性，平摊复杂度就无法达到O(logn) 或对于不符合局部性原理的访问，splay 的分摊复杂度不是 O(logn) (4)即使不使⽤改进的next[]，kmp 依然可以达到线性的时间复杂度 (5)对于二叉树，通过先序遍历和后序遍历不能确定其层次遍历 (6) 拥有2019个节点的真二叉树的种数比2018个所能够成的合法序列要少 (7)对于叶节点数量为 2018 的⼆叉树，对其进行层次遍历时辅助队列大小最多不超过2018 (8)插⼊排序每次插⼊数据，即使不增加循环节，也不⾄减少 (9)交换两个逆序对，必然会减少总逆序对数 (10)如果基数排序底层采⽤不稳定的算法，那么得到的结果可能是不正确的 (11)函数的调⽤栈中如果有相同的函数，则他们必然紧邻 (12)如果插⼊的关键码独⽴均匀分布，堆的插⼊操作平均O(1) 简答题(8*4=32) 1.逆波兰表达式为什么相比普通表达式计算效率更高，既然转换为逆波兰式已经消耗掉了一次相当于普通计算的时间，那这样的转换价值何在？ 2.用DFS搜索图，何时标前向边，何时标后向边 3.相对于选择排序，插入排序有哪些优点？2条 4.Dijstra在处理稠密图时为何使用多叉堆替换常规的完全二叉堆，多叉堆的分叉数又如何确定？ 5.相比于开放散列，封闭散列有什么优点？2条 6.相对于一般的锦标赛树，败者树有什么优势？为什么？

7.红黑树对AVL树所不具有的优势？为什么？ 8.KMP算法对蛮力算法的优势，在什么条件足够明显？为什么？算法题(7+3+4=14) 第K大节点 struct BinNode{ int size; //当前节点和孩⼦总数 BinNode *lchild,*rchild; }; BinNode *rank(BinNode* t,int k){ //有效代码⾏数不超过 12 ⾏ //求出后序遍历的第k大的结点 //不可直接模拟后续遍历，性能不能满足，会直接判0分 //时间复杂度和空间复杂度不超过O(depth(x))(x为第k大的节点) } 1.实现，填写代码已完成上述功能（不超过12行） 2.原理，解释说明代码思想 200字，可附一图 3.证明时间、空间复杂度 120字

计算机组成原理(30) 判断题(5*1=5) 1. MIPS五级流水线设计中，使用充分设置功能单元的方法可以改善结构冲突 2. 假设x类型是C语言中的int，若x>0，则x*x>0 3. 冯诺依曼结构体系中把程序也当做数据放在内存中 4. 对于传统机械硬盘，读100MB数据，顺序读取时间小于随机读取时间 5. CPI减少，执行相同程序的时间也减少选择题(5*2=10) 1. 下列哪一项没有容错能力 A. RAID0 B. RAID1 C. RAID5 D. RAID6 2. 下列关于静态存储器和动态存储器的描述正确的是 A.静态存储器使用触发器，需要定期刷新 B.静态存储器使用电容，不需要定期刷新 C.动态存储器使用触发器，不需要定期刷新 D.动态存储器使用电容，需要定期刷新 3. 下列哪个是对的 A．虚拟内存空间比实际的地址空间大 B．虚拟内存空间比实际的地址空间小 C．虚拟内存空间连续存放，实际内存一定连续存放 D．虚拟内存空间不连续存放，实际内存有可能连续存放 4. 下面总线说法哪个正确（） A.并行总线速度大于串行 B.异步总线速度大于同步 C.单总线速度大于双总线 D.以上说法均错误 5. MIPS五级流水中，有哪个数据冲突（） A.RAR B.RAW C.WAR D.WAW

填空题(2+2+3+3=10) 1.十进制整数+1234的32位的补码是：_______（16进制，小端机表示） 2.十进制单精度浮点数-27.625在IEEE754浮点标准下表示：_______ （16进制） 3. 缓存缺失的类型包括，写3个 4. MIPS五级流水线中，解决数据冲突的方法，给出3个. 计算题(5) MIPS处理器内存延迟10ns ALU延迟6ns 寄存器3ns 输入延迟1ns 流水线寄存器以及多周期锁存器输出延迟为2ns 要有计算过程以下是指令(可能有个别字母不对) 1.addn vd rs rt 2.subu rd rs rt 3.ori rt rs rimm 4.lw rt rs imm 5.sw rt rs imm 6.beg rs rt imm 7. j target 1.按照单周期设计，指令内存与数据内存分开，计算指令延迟？ 2.按照多周期设计，指令内存和数据内存在同一个内存模块，最长和最短的指令延迟分别是指哪条指令，分别计算对应的延迟 3.按照五级流水线设计，指令内存和数据内存在同一个内存模块，处理器频率最高能到多少

操作系统(30) 1. stride调度(这个完全没多少印象了，下面是研友回忆版) Stride调度算法中，如果⽤⼋位⽆符号数表⽰进程的stride，对于 AB两个进程，如果A的步长 [1]，可以采⽤⼀些⽅法即使溢出依然能得到正确结果。。。后面好像还有几个空 2.x86 cpu ？向时的特权级检查总判别条件 CPL<=DPL[门]&CPL>=DPL[段] 3.信号量pv操作，四个填空伪代码补全 class Semaphore { int sem; WaitQueue q; } Semaphore::P() { [9] ; if ( [10] ) { Add this thread t to q; block(t); } } Semaphore::V() { [11] ; if ( [12] ) { Remove a thread t from q; wakeup(t); } } 4.ucore操作系统 do_exit(),do_wait()，若子进程执行在ucore内核中 do_exit()函数时,父进程已经退出，则ucore会唤醒initproc进程，完成进程块释放操作这时的子进程称为______进程，若子进程执行 do_exit()函数时，父进程不处于等待状态，则无法完成资源回收，这时的子进程称为_____

5.x86-32CPU的硬件组成，cr3寄存器用于存储页目录表起始____ 6.文件p在创建时的inode引用计数器初始值为1，然后给文件F创建一个符号链接A，再给文件P创建一个硬链接B，再给B创建一个硬链接 C，则此时B和C的inode引用计数器值分别是___和_____ 判断题 1. X86-32虚拟存储系统中，4KB页面大小为4KB，采用二级页表，一级页表可以不在内存中 2. 每个中断源在中断向量表中占一项，中断向量表示按中断号排序的，中断向量表中保存了CPU在响应中断时需要的选线和入口地址等信息 3. Ucore时钟中断设为10ms出发一次，所以Ucore不能实现小于10ms 的周期定时间隔 4. 只有一个main函数的程序没有线程 5. 关于银行家算法中不安全状态与死锁的关系，不安全状态即死锁状态 ucore进程切换相关源码尝试说明页表切换代码的位置、堆栈切换代码的位置、switch_to函数中读取2个函数参数的代码部分并注释以下部分为代码 globl switch_to switch_to: # switch_to(from, to) # save from's registers movl 4(%esp), %eax # eax points to from(考卷上故意把这一个注释删了) popl 0(%eax) # save eip !popl movl %esp, 4(%eax) movl %ebx, 8(%eax) movl %ecx, 12(%eax) movl %edx, 16(%eax) movl %esi, 20(%eax)

movl %edi, 24(%eax) movl %ebp, 28(%eax) # restore to's registers movl 4(%esp), %eax # not 8(%esp): popped return address already # eax now points to to：(考卷上故意把这一个注释也删了) movl 28(%eax), %ebp movl 24(%eax), %edi movl 20(%eax), %esi movl 16(%eax), %edx movl 12(%eax), %ecx movl 8(%eax), %ebx movl 4(%eax), %esp pushl 0(%eax) # push eip ret struct proc_struct { enum proc_state state; // Process state int pid; // Process ID int runs; // the running times of Proces uintptr_t kstack; // Process kernel stack volatile bool need_resched; // bool value: need to be rescheduled to release CPU? struct proc_struct *parent; // the parent process struct mm_struct *mm; // Process's memory management field struct context context; // Switch here to run process struct trapframe *tf; // Trap frame for current interrupt uintptr_t cr3; // CR3 register: the base addr of Page Directroy Table(PDT)

uint32_t flags; // Process flag char name[PROC_NAME_LEN + 1]; // Process name list_entry_t list_link; // Process link list list_entry_t hash_link; // Process hash list }; void proc_run(struct proc_struct *proc) { if (proc != current) { bool intr_flag; struct proc_struct *prev = current, *next = proc; local_intr_save(intr_flag); { current = proc; load_esp0(next->kstack + KSTACKSIZE); lcr3(next->cr3); switch_to(&(prev->context), &(next->context)); } local_intr_restore(intr_flag); } } Ucore代码大题代码三四页那么多，暂时没找那部分代码，这块我确实不熟虚拟页式存储的计算机系统，分别在进程A和B中描述逻辑地址0x64 和0x14地址转换过程，要求描述并给出计算过程，给出对应一级页表项，二级页表项和访存单元的物理地址和对应的存储内容

资料库

清华大学-912-2019-真题回忆版.pdf

相关推荐

考试认证

热门标签

最新资料