清华08计算机考研试题

数据结构》、选择题3给了一序列比如6.7.4.8.9.3. 散列函数是H(key)=key%11. 一问成功时的平均搜索长度二问不成功的平均搜索长度哪种数据结构，从某一个结点到根结点的路径序列组成一个降序排列a. b. 最大堆c. 最小堆d还有一个题是关于关键路径的，答案选项是49/B -C \/F\ \\D-E H\G/什么是数据结构？A B C定义在一个数据集合上的属性和操作D 高度为h的完全二叉树，一共有多少种？ A B 2A(h-1)、证明题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, —个是主动调用系统调度函数yieldO ，此时进程主动放弃cpu；另一个方式是当进程执行I/O 操作时，系统将调度下一个进程。

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

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

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

-- critical sectionThread2(){-- critical sectiong=g+b;f=g-a;-- critical section第二种：Thread1(){yield();-- critical sectiong=g+b;f=g-a;-- critical sectionThread2(){-- critical sectiong=g+b;f=g-a;-- critical sectionyield();第三种：Thread1(){yield();-- critical sectiong=g+b;f=g-a;-- critical sectionThread2(){yield();-- critical sectiong=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 在虚拟页式系统中，给了虚拟地址的位数大概间位128GB每页大小4KB。

问了四个问题，大概有涉及的多级页表，访存的平均时间，命中率等等。

48 位，可用的最大主存空（假设没有TLB存在）2. 系统中为什么要设计TLB 画图表示出虚拟地址到真实地址的转化2008年清华大学计算机系上机题(回忆版)一、输入：两行第一行：M 和N 第二行： XM 和N 是一个十进制数，M 和N 都在[2-36]之间，X 是一个M 进制数，X 在[1-2*10X9]输出：一行第一行：现在要求你将M 进制数X 转换成N 进制数输出输入一：16 10F 输出一：15二、按照手机键盘输入字母的方式，计划所花费的时间女口： a,b,c 都在“1”键上，输入a 只需要按一次，输入c 需要连续按三次。

如果连续两个字符不在同一个按键上，则可直接按，如： ad 需要按两下， kz 需要按 6 下如果连续两字符在同一个按键上，则两个按键之间需要等一段时间，如ac ，在按了 a 之后，需要等一会儿才能按 C 。

现在假设每按一次需要花费一个时间段，等待时间需要花费两个时间段。

现在给出一串字符，需要计划出它所需要花费的时间。

输入一： 输出一： 输入二： 输出二： 考完笔试， 将试题回忆了出来。

希望能有利于后人， 也算是对前人给予的帮助的 一种回报吧。

此资料不得被任何人以任何形式贩卖！请卖考研资料者自律。

)面的是人工智能和多媒体技术的试题。

====人工智能 ===」、对下图所示博弈树进行a - P 剪枝，标明各结点的倒推值及何处发生剪枝。

见附图 1。

数值不准，仅作参考。

)二、对状态空间图进行搜索， 标出下述算法的扩展结点序列和求得的解路径。

序列和解路径用字母串表示，如 SABC （见附图2。

数值不准，仅作参考。

）1. 宽度优先搜索；bob7www72.深度优先搜索；3.A 算法。

其中各节点旁标记的是该节点的h 值，路径上的数字表示该路径的耗散值。

、请回答下列问题：1.a - P剪枝的原理，即为什么可以a - P剪枝。

2.模拟退火算法的特点。

3.简述遗传算法的过程。

=====多媒体、什么是多媒体技术（定义）？其关键技术是什么？二、写出音频差分编码（DPCM的原理。

列举参数编码的两个国际标准，说明它们的编码参数和数据率。

三、量化方法的分类？某均匀量化器的输出为L阶，输出编码位数n位。

则已知L的话，n的值是多少？已知n的话，L的值为多少？四、信息的量如何度量？离散信源的无损编码的理论极限（好像是这么写的）是什么？已知某信源的四个符号的概率分别为：a1 - 0.5 ，a2 - 0.2412 ，a3 - 0.1702 ，a4 - 0.0886 （数值记得不太准），求信源的Huffman 编码，计算信源的熵以及编码的平均码长。

五、基于内容检索的多媒体数据库由哪些部分组成？请描述基于内容检索的工作过程。

另外，这里对考应用方向的学弟学妹们有些建议：1.笔试四选二里选人智和多媒体。

据我所知应用方向的大多数人都选的是这两科。

其他的两科比较难。

如果你四科都一样是没学过的话，AI和M^还是比较容易看懂的。

2.去网上找到“计算机系网络课堂”这套课件，里面有人智和多媒体，还有信号处理原理的课件。

仔细地做做期末试题中跟历年复试题相近的题。

大多数真题是从这里改编的。

在本版的精华区里可以找到05 至07年历年的应用方向笔试题目，这些试题具有很大的参考价值。

为了节省大家的时间，这里附上历年试题回忆的原帖。

排版有些混乱，需要的人自己整理吧。

祝后来的学弟学妹们考试顺利。

首先要非常感谢knightma ，是knightma 去年的辛勤劳动-- 复试题目回忆，为大家今年的复试准备做出了巨大的帮助。

为了回报一下之前的牛人和回报新水木，我也回忆一下题目吧。

我考的人智和多媒体。

题目基本上跟去年一样，多媒体多了个量化处理的原理和计算。

其他的都没变。

人工智能有一点变化。

题目总共才三道题，第一道是给出了8数码问题的一个h 函数，求证单调，然后再用A*求出最优解，画图很麻烦。

第二题是谓词的归结题，较繁，不仅要反演证明，还要用修改证明树求出一个结果。

第三题是名词解释四选二：遗传算法，模拟退火，神经网络，专家系统。