清华08计算机考研试题.doc

《数据构造》                 一、选择题 1 2 3 给了一序列例如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定义在一种数据集合上的属性和操作 D 7 高度为h的完全二叉树，一共有多少种？A  B 2^(h-1)  C  D 二、证明题 1. 什么样的有向无环图有唯一的拓扑有序序列，并证明三、计算题 1 有n个结点的二叉树最大高度，最小高度分别是多少？ 2 一棵有n个结点的树有m个叶节点，如果用做兄弟-右子女表达法，则有多少个结点的右指针域为空? 3 霍夫曼树中，有n个叶结点，问一共有多少个结点? 4 有n个结点的树的不同排列形式有多少种 四、给定一种文献有1,000,000个记录，每个200B，记录中核心码大小50B，页面大小为4kB，现以B+树（最大核心码复刻）方式组织该文献，尽量使每结点拥有尽量多的核心码，已知每个指针占用5B。

     问1.该B+树有多少个叶结点，共有多少层；2.该B+树共有多少个索引结点；3.每次搜索要读盘多少次？ 五、算法设计题 1.给定A[n],设计一种算法，重排数组，使得奇数都在数组前半部分，偶数都在后半部分规定期间复杂度O(n)   函数头：void exstorage(int A[], int n) 2.重新设计一种直接选择算法函数，采用递归方式对一种大小为n的数组，初始的调用方式为：selectsort(A, 0, n-1)   函数头：void selectsort(int A[],int left, int right) 《操作系统》 一、简答题 1. 磁盘I/O操作的时间构成部分，论述优化磁盘调度方略的目的 2. 什么是内碎片，外碎片3. 内核线程和顾客线程的区别？各自有什么特点 4. 什么是内核模式和顾客模式？为什么系统要设立这两种模式 5. 什么是上下文（context),请说出它的构成，系统是如何实行多种进程之间调度的，具体过程是如何的二、计算题 已知系统为32位实地址，采用48位虚拟地址，页面大小4kB，页表项大小为8个字节；每段最大为4G 1. 系统将采用多少级页表，页内偏移多少位？ 2. 假设系统采用一级页表，TLB命中率为98%，TLB访问时间10ns，内存访问时间100ns，并假设当TLB访问失败时才开始访问内存，问平均页面访问时间多少？ 3. 如果是二级页表,页面平均访问时间是多少？ 4. 每顾客最多可以有多少个段？段内采用几级页表？ 5.如果要满足访问时间<=120ns, 那么命中率需要至少多少?三、pv操作题 给定一种全局数组a[n] b[n]，然后是T1~Tn-1 共n-1个线程，线程为代码如下 Ti(){ a=g(a,a[i-1]); b=f(a); } 其中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方式和索引方式组织文献构造。

然后给出缓冲区，缓冲区大小为4个数据块，使用LRU替代算法，并假设所有操作均不波及内存或cache，只考虑缓冲区 并声明只有如下两种状态才会刷新缓冲区：a）缓冲区冲突 b)系统积极调用一种同步函数sync()，同步缓冲区然后给出目前根目录文献共有10块，分别分布在缓冲区的位置，缓冲区一种24个数据块用一种表格把它们相应起来了 然后就是一种超大的表格，给出某些列操作，例如读第几种数据块，并偏移多少字节之类的，然后让填写在fat和索引方式下读盘次数，写盘次数和目前缓冲区内容 ps：本题实在记不清了，光读题都要十分钟 file表寄存在第23块(第一列都是类似一下的语句)从偏移量100字节处读入50字节从偏移量1000字节处读入20字节从偏移量***字节处读入**字节调用sync()FAT索引方式读次数 写次数 缓存内容 读次数  写次数  缓存内容从偏移量100字节处读入50字节 《计算机原理》 一、填空题 1. 写出-1.125的IEEE754 32位原则的浮点数 2.控制器部件由哪五部分构成____  _____ _____  ______  ______； 3.五级指令流水线哪五部分构成 IF,  _____  ______  ______  ______; 二、下述指令集能否用单字指令（字长为12位）实现，涉及：a 4条三寄存器指令  b 255条单寄存器指令 c 16条0寄存器指令 三、cache和虚拟地址有关的计算题 一种标记位Tag, 一种有效位, 一种脏位(Dirty), 块号(Offset), 采用全相连方式, 为什么要采用全相连方式? 1 画图表达标记，块号，块内地址。

  2.cache的存储效率 （即除掉标记位，access位，dirty位） 四、输入输出方式均有哪几种？请简要论述各自特点 五、1在虚拟页式系统中，给了虚拟地址的位数大概48位，可用的最大主存空间位128GB，每页大小4KB 问了四个问题，大概有波及的多级页表，访存的平均时间，命中率等等 (假设没有TLB存在)2. 系统中为什么要设计TLB画图表达出虚拟地址到真实地址的转化--清华大学计算机系上机题（回忆版）一、输入：两行　　第一行：M和N　　第二行：X　　M和N是一种十进制数，M和N都在[2-36]之间，X是一种M进制数，X在[1-2*10^19]　　输出：一行　　第一行：目前规定你将M进制数X转换成N进制数输出　　输入一：　　16 10　　F　　输出一：　　15二、按照键盘输入字母的方式，筹划所耗费的时间　　如：a,b,c都在“1”键上，输入a只需要按一次，输入c需要持续按三次　　如果持续两个字符不在同一种按键上，则可直接按，如：ad需要按两下，kz需要按6下　　如果持续两字符在同一种按键上，则两个按键之间需要等一段时间，如ac，在按了a之后，需要等一会儿才干按 C　　目前假设每按一次需要耗费一种时间段，等待时间需要耗费两个时间段。

　　目前给出一串字符，需要筹划出它所需要耗费的时间　　输入一：bob　　输出一：7　　输入二：www　　输出二：7考完笔试，将试题回忆了出来但愿能有助于后人，也算是对前人予以的协助的一种回报吧此资料不得被任何人以任何形式贩卖！请卖考研资料者自律下面的是人工智能和多媒体技术的试题人工智能====一、对下图所示博弈树进行α-β剪枝，标明各结点的倒推值及何处发生剪枝见附图1数值不准，仅作参照二、对状态空间图进行搜索，标出下述算法的扩展结点序列和求得的解途径序列和解途径用字母串表达，如SABC见附图2数值不准，仅作参照1. 宽度优先搜索；2. 深度优先搜索；3. A算法其中各节点旁标记的是该节点的h值，途径上的数字表达该途径的耗散值三、请回答问题：1. α-β剪枝的原理，即为什么可以α-β剪枝2. 模拟退火算法的特点3. 简述遗传算法的过程多媒体=====一、什么是多媒体技术（定义）？其核心技术是什么？二、写出音频差分编码(DPCM)的原理列举参数编码的两个国际原则，阐明它们的编码参数和数据率三、量化措施的分类？某均匀量化器的输出为L阶，输出编码位数n位则已知L的话，n的值是多少？已知n的话，L的值为多少？四、信息的量如何度量？离散信源的无损编码的理论极限（仿。