复旦大学考研计算机961真题答案针对回忆版

复旦大学计算机科学技术学院专业硕士复试上机考试题（2013-03-27）第一篇：复旦大学计算机科学技术学院专业硕士复试上机考试题(2013-03-27)复旦大学计算机科学技术学院专业硕士复试上机考试题（2013-03-27）建议时间：120分钟。

评分方法和注意事项：1.按考场老师指示的方法和要求提交源代码文件。

按题目编号命名和上传源代码文件problem1.cpp、problem2.cpp、problem3.cpp。

提交不必要的文件、建不必要的文件夹、不必要的压缩、不按要求命名文件，而导致评测程序找不到对应文件的，将得0分。

2.第一、二题我们拟只采用黑盒测试，因此：可以不书写注释；更不必美化程序。

3.第三题我们对未通过黑盒测试的程序，将检查其程序，因此推荐写解题思路、注释，保持良好的编程风格。

解题思路以注释的形式，放在源代码文件的开始，建议采用伪代码风格。

如果您不能完成全部代码，书写正确的解题思路可能得部分分数。

4.仔细阅读题目要求，一定要确保您的输入输出严格符合要求。

如输入输出格式不严格遵循题目的要求，会导致被判断为结果错误而不得分。

没有特别说明的，输入为标准输入（键盘），输出为标准输出（屏幕）。

5.提交的源代码必须保持无编译错误，提交有编译错误的程序该题直接得-10分。

6.除题目另有要求外，程序执行时间应在1秒之内，程序中的死循环恕不等待。

7.不要编写破坏性程序，否则产生的结果对您也是破坏性的，即取消评分资格。

Problem1: 字符串匹配对于主串M和模式串P，找到P在M中出现的所有子串的第一个字符在P中的位置。

P中第一个字符所在的位置为0。

首行的数字表示有多少组字符串。

[输入及示例] 2 ababababa ababa aaa aa [输出及示例] 0 2 4 0 1(相邻位置之间用一个空格隔开)Problem2:A Famous ICPC TeamMr.B, Mr.G, Mr.M and their coach Professor S are planning their way for the ACM-ICPC World Finals.Each of the four has a square-shaped suitcase with side length Ai(1<=i<=4)respectively.They want to pack their suitcases into a large square box.The heights of the large box as well as the four suitcases are exactly the same.So they only need to consider the large box’s side length.Of course, you sho uld write a program to output the minimum side length of the large box, so that the four suitcases can be put into the box without overlapping.[Input] There are N test cases.The first line is N.Each test case contains only one line containing 4 integers Ai(1<=i<=4, 1<=Ai<=1,000,000,000)indicating the side length of each suitcase.[Output]For each test case, display a single line containing the case number and the minimum side length of the large box required.[Sample Input] 2 2 2 2 2 2 2 2 1 [Output for Sample Input] Case 1: 4 Case 2: 4 [Explanation]For the first case, all suitcases have size 2x2.So they can perfectly be packed in a 4x4 large box without wasting any space.For the second case, three suitcases have size 2x2 and the last one is 1x1.No matter how you rotate or move the suitcases, the side length of the large box must be at least 4.Problem3：A Famous Grid Mr.B has recently discovered the grid named “spiral grid”.Construct the grid like the following figure.(The grid is actually infinite.The figure is only a small part of it.) Considering traveling in it, you are free to any cell containing a composite number or 1, but traveling to any cell containing a prime number is disallowed.You can travel up, down, left or right,but not diagonally.Write a program to find the length of the shortest path between pairs of nonprime numbers, or report it's impossible.[Input]There are N test cases.The first line is N.Each test case is described by a line of input containing two nonprime integer 1 <=x, y<=10,000.[Output]For each test case, display its case number followed by the length of the shortest path or “impossible”(without quotes)in one line.[Sample Input] 3 1 4 9 32 10 12[Output for Sample Input] Case 1: 1 Case 2: 7Case 3: impossible第二篇：北京大学硕士计算机上机题上机题（占总成绩的30%）1、编写一个C++程序，计算并输出两个同符号的整数m与n的整商（其中| m | ≤ 10，1000| n | ≤ 10）。

2020复旦大学软件工程考研961真题回忆版
一、数据结构（60分）
1.设计一个算法，统计二叉树中有一棵子树非空的节点个数并给出时间复杂度（15分）
2.列举二叉排序树中在最坏情况下增删改查时间复杂度仍为O(logn)的两种树，并分析（10分）
3.代码填空：Floyd、改良的插入排序（15分共五个空，每空三分）
4.设计一个算法，找一个数列中的前k大数，要求时间复杂度O(n)，并给出时间复杂度的分析（20分）
二、软件工程（60分）
5.概念解释（30分，每题6分）
（1）CMMI连续式模型和阶段式模型的区别
（2）测试和调试的关系
（3）列举三种耦合
（4）开闭原则
（5）回归测试
6.画图（30分，每题15分）
（1）类图。

用类图把下面的类的关系表达出来。

计算机、台式机、笔记本电脑、鼠标、硬盘、显示器、有线鼠标、蓝牙鼠标、机械鼠标等等
（2）状态机图。

空调开启后进入系统自检，自检成功后进入模式选择，制冷，制热，吹风，三种模式自由切换；制冷时室温大于制冷温度则进入制冷，否则吹风；制热时室温小于制热温度则进入制热，否则吹风；制冷制热时系统可以进入温控模式，吹风时一直吹风。

三、深入理解计算机系统（30分）
7.RISC、CISC、RISC与Amdahl定律的关系（30分）。

文档来源为 :从网络收集整理 .word 版本可编辑 .欢迎下载支持2015年全国硕士研究生入学统一考试计算机学科专业基础综合试题一、单项选择题： 140 小题，每小题 2 分，共 80 分。

下列每题给出的四个选项中，只 有一个选项符合题目要求。

请在答题卡上将所选项的字母涂黑。

1．已知程序如下： int s(int n) {return (n<=0) ? 0 : s(n-1) +n;}void main() { cout<< s(1); }程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息一次对应的是 A ． main()->S(1)->S(0) B ． S(0)->S(1)->main() C ． main()->S(0)->S(1)D ． S(1)->S(0)->main()2． 先序序列为 a,b,c,d 的不同二叉树的个数是 A ． 13B ．14C ．15D ．163．下列选项给出的是从根分别到达两个叶节点路径上的权值序列，能属于同一棵哈夫 曼树的是序序列。

下列关于该平衡二叉树的叙述中，正确的是5. 设有向图 G=(V,E)，顶点集 V={V o ,V i ,V 2,V 3}，边集 E={<v 0,v i >,<v 0,v 2>,<v o ,v 3>,<v i ,v 3>}, 若从顶点 V 0 开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是A. 2 B . 3C . 4D . 56.求下面带权图的最小(代价)生成树时，可能是克鲁斯卡(kruskal )算法第二次选 中但不是普里姆( Prim )算法(从 V 4开始)第 2 次选中的边是A. (V1,V3)B . (V1,V4)C . (V2,V3)D . (V3,V4)A ． 24， 10， 5 和 24，10，7 C ．24，10，10 和 24， 14，114．现在有一颗无重复关键字的平衡二叉树B ．24，10，5 和 24， 12，7 D ．24，10，5 和 24，14，6( AVL 树) ,对其进行中序遍历可得到一个降A .根节点的度一定为 2 C .最后插入的元素一定是叶节点B .树中最小元素一定是叶节点 D .树中最大元素一定是无左子树文档来源为:从网络收集整理.word 版本可编辑.欢迎下载支持7. 下列选项中，不能构成折半查找中关键字比较序列的是A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，450&已知字符串S为“ abaabaabacacaabaabcc模式串t为“ abaabc '采用KMP算法进行匹配，第一次出现“失配”(s[i] != t[i]) 时，i=j=5, 则下次开始匹配时，i 和j 的值分别是A．i=1，j=0 B．i=5，j=0 C．i=5 ，j=2 D．i=6，j=29．下列排序算法中元素的移动次数和关键字的初始排列次序无关的是A .直接插入排序B .起泡排序C .基数排序D .快速排序10．已知小根堆为8，15，10，21，34，16，12，删除关键字8之后需重建堆，在此过程中，关键字之间的比较数是A. 1B. 2C. 3D. 411.希尔排序的组内排序采用的是()A .直接插入排序B .折半插入排序C .快速排序D .归并排序12.计算机硬件能够直接执行的是()I.机器语言程序n.汇编语言程序川.硬件描述语言程序A. 仅I B .仅I n C .仅I 川D. In出13.由 3 个“ 1 ”和5 个“ 0”组成的8位二进制补码, 能表示的最小整数是()A.-126 B . -125C. -32D. -314.下列有关浮点数加减运算的叙述中, 正确的是()I.对阶操作不会引起阶码上溢或下溢n.右规和尾数舍入都可能引起阶码上溢川.左规时可能引起阶码下溢I V 尾数溢出时结果不一定溢出A.仅n 川 B .仅inv C .仅I川V D. In川V15.假定主存地址为32 位，按字节编址，主存和Cache 之间采用直接映射方式，主存块大小为4 个字，每字32位，采用回写( Write Back )方式，则能存放4K 字数据的Cache 的总容量的位数至少是()A. 146kB. 147KC. 148KD. 158K16.假定编译器将赋值语句“x=x+3;转换为指令” add xaddt, 3,其'中xaddt是x对应的存储单元地址，若执行该指令的计算机采用页式虚拟存储管理方式，并配有相应的TLB ，文档来源为:从网络收集整理.word 版本可编辑.欢迎下载支持且Cache使用直写(Write Through )方式，则完成该指令功能需要访问主存的次数至少是()文档来源为 :从网络收集整理 .word 版本可编辑 .欢迎下载支持A ． 0B ．1C ．2D ．317．下列存储器中，在工作期间需要周期性刷新的是() A ． SRAMB ．SDRAMC ．ROMD ．FLASH18．某计算机使用 4 体交叉存储器，假定在存储器总线上出现的主存地址(十进制)序 列为 8005， 8006，8007， 8008，8001，8002，8003，8004，8000，则可能发生发生缓存冲 突的地址对是()B ．8002、8007C ．8001、 8008D ．8000、8004 19．下列有关总线定时的叙述中，错误的是()A •异步通信方式中，全互锁协议最慢 B. 异步通信方式中，非互锁协议的可靠性最差 C. 同步通信方式中，同步时钟信号可由多设备提供 D. 半同步通信方式中，握手信号的采样由同步时钟控制20. 若磁盘转速为 7200转/分，平均寻道时间为 8ms,每个磁道包含1000个扇区，则访 问一个扇区的平均存取时间大约是 ( )A. 8.1ms B . 12.2msC . 16.3msD . 20.5ms21. 在采用中断I/O 方式控制打印输出的情况下，CPU 和打印控制接口中的I/O 端口之 间交换的信息不可能是 ( )A .打印字符B .主存地址C .设备状态D .控制命令22. 内部异常(内中断)可分为故障(fault)、陷阱(trap)和终止(abort)三类。

一、单项选择题： 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] 。

某年1.根据给出的文法写描述相应的语言，判断是否为二义S->aSbs|bSaS|ε；是二义，例：abab2.计算条件概率(全概率公式,做火车飞机轮船。

分别×××，迟到概率×××，已知迟到了，求坐火车来的概率）3.计算一定数量的指令通过给出的一条流水线的时间，计算吞吐量和最大吞吐量（已知流水线4ns一段，共5段，先16条指令通过，完毕后再26条通过）4.用差分法推导一个多项式的递归计算方法，说明这种算法的优点f(t)=(at^3+bt^2+ct+d) ti=i/n(i=1,2,3,....n)5.一个1024*16K的存储器，用DDR和EPROM两种芯片构成，前者占四分之三，两种芯片的大小各为128*8位，128*16位，计算两种芯片各要多少片，EPROM 的首地址是多少？6.考欧拉图给一张图，最少添几条线成为欧拉图。

有几种画法？(找奇数顶点）7.证明一个代数系统是群，判断正规子群G={(x,y)|x不为0, x,y都属于R},定义运算(x,y)●(z,w)=(xz,xw+y)证明[G;●]是群。

H={(1,y)|y属于R},是不是G的正规子群？8，9.软件测试有关的问题，软件结构设计的问题（选择）10.文件系统中冗余的概念和关系数据库中冗余的概念（具体是问：文件系统中不可消除的数据冗余；关系数据库中应该避免的数据冗余）11.分布式数据库中的三层透明性是什么（写出名词即可）12.两个NP语言L1,L2的并和差是否属于NP，证明或举反例~~是~~不是13.移动窗口协议端对端延迟1.25s,已知带宽*Mbps,每个帧的容量1KB,若要充分利用，应该为帧安排几位的序号字段？14.描述一个X86系统中的中断处理过程，主要是根据中断向量N和中断向量表来查中断处理子程序的入口USEINT.（写出过程，实模式or保护模式任选）1.G={(a,b)|a<>0} H={(1,x)} 在G中定义运算(x,y)*(w,z)=(xw,xz+y)求证H为G的正规子群2. 原理：一个32位浮点数分S, M, E三段，其值为(-1)^S * 1.M* 2^(E-128) ;问最大、小正负数分别是多少，且给出二进制表示。

计算机重点真题答案及解析近年来，计算机专业已成为一门越来越受欢迎的学科。

相应地，计算机考试的难度和重要性也日益增加，因此备考者更需要关注真题的解析和答案。

本文将为大家介绍一些计算机重点真题的解析和答案，帮助大家更好地备考。

1. 数据库设计数据库设计是计算机专业非常重要的一部分，也是很多考试中的必考内容。

一道常见的数据库设计题如下：问题：请根据以下需求设计一个简单的图书管理系统的数据库。

需求：- 记录图书的基本信息，包括书名、作者、出版社、价格等；- 记录借阅者的信息，包括姓名、性别、年龄、借阅书籍等；- 系统管理员能够添加、删除、修改图书信息；- 借阅者能够查询图书信息、借阅图书、还书等。

解析：根据以上需求，我们可以设计以下几个表：1) Book（图书表）：- 书籍ID（Primary Key）- 书名- 作者- 出版社- 价格2) Borrower（借阅者表）：- 借阅者ID（Primary Key）- 姓名- 性别- 年龄3) Borrowing（借阅记录表）：- 借阅记录ID（Primary Key）- 图书ID（Foreign Key）- 借阅者ID（Foreign Key）- 借阅日期- 还书日期4) Administrator（管理员表）：- 管理员ID（Primary Key）- 姓名- 职位通过以上表的设计，我们能够满足图书管理系统的各项需求。

2. 算法分析算法分析是计算机专业中的一项关键内容，往往与复杂度相关。

下面是一个与排序算法相关的问题：问题：请对以下排序算法进行复杂度分析：冒泡排序、插入排序和快速排序。

解析：先来看冒泡排序，冒泡排序通过反复交换相邻的两个元素，使得每一次遍历都能将最大或最小的元素冒泡到最后。

它的平均时间复杂度为O(n^2)。

接下来是插入排序，插入排序将数组划分为已排序和未排序两部分，每次将未排序的元素插入到已排序的合适位置。

它的平均时间复杂度也是O(n^2)。

这个961改革后只有3年，之前和计算机考一样，群里只有两年的，没有2017年的，因为那年就5个人考上，要不是有我同学在也回忆不出来，所以还是比较宝贵的，天行也花了很多时间。

2017年数据结构：向量相对于数组有什么优缺点？二叉树计算叶子节点算法，时间复杂度。

（可使用任一程序设计语言或伪代码，建议先用自然语言描述算法）。

几乎逆序的数组排序用什么排序算法？写出算法，时间复杂度。

二叉排序树的2种优化方法，并且介绍这两种方法是怎样优化二叉排序树的。

流水线是怎样提高性能的，会遇到什么问题，解决方法是什么。

软件优化至关重要，软件优化一般有哪些方法？高速缓存性能分析定律存储结构是怎样提高性能的，它和局部性的关系是什么。

虚拟内存的作用，通过什么方式提高虚拟内存的性能。

软件工程：瀑布过程的特点开闭原则敏捷宣言是什么一个场景（学生毕业申请系统），画出UML图、画出流程图0、画出流程图1 结合传感器说明简述软件测试的作用。

是不是用例越多越好？为什么说明原因。

白盒测试和黑盒测试在用例设计上的区别。

2018年加一个数据结构遗漏的：数据结构向量相对于数组的区别和有什么优缺点？栈的链表实现数组和链表性能比较希尔排序是否稳定？哈弗曼树遍历输出叶子节点编码和压缩效率csapp优化程序性能的方法局部性定义虚拟内存和memony cache比较流水线处理器amdlhal定律解释软工学生系统用例图数据流图图书馆管理系统类图软工工程选择依赖转制和接口隔离加一个数据结构遗漏的：向量相对于数组的区别和有什么优缺点？2019年一，数据结构1，为什么队列的单链表表示只能选择尾部插入头部插入，以及采用什么措施可以使得尾插入和头删除的时间复杂度达到o(n).15mark2，DIJKSTRA算法的单元点最短路径给出了一段完整的伪代码要你填满四个空缺的语句。

10mark3，构造堆的算法，分析时间复度分析。

15mark4设计一个算法得出二叉树的存在两颗非空子树的节点数量。

复旦大学计算机一级考试基础题试卷 A一、单项选择题1. 目前应用愈来愈广泛的优盘(U盘)存储属于________存储技术。

A. 刻录B. 移动C. 网络D. 直接连接答案： B2. 为了保证计算机通信质量，相关通信设备的比特差错率________。

A. 与数据传输质量无关B. 可为任意值C. 低于某个值即可D. 必须为0答案： C (差错率通信过程中发生错误的概率)3. 模拟信道带宽的基本单位是_______。

A. bpmB. bpsC. HzD. ppm 答案： C*模拟信号中带宽又称为频宽，以赫兹（Hz）为单位；数字信号中带宽是指单位时间内链路能够通过的数据量,单位为bps4. 十进制数153转换成二进制数是_______。

A. 10110110B. 10100001C. 10000110D. 10011001 答案：学会用计算器计算5. 计算机中能直接被CPU存取的信息是存放在_______ 中。

A. 软盘B. 硬盘C. 光盘D. 内存答案： D6. 属于有线传输媒体的是_______。

A. 双绞线B. 微波线路C. 卫星线路D. 红外传输答案：A (其他为无线传输媒体)7. 计算机系统识别出一个移动硬盘的过程属于操作系统基本功能中的________范畴。

A. 处理器管理B. 存储器管理C. 输入输出设备管理D. 信息管理答案： C（I/O）8. 一个数据通信的系统模型由数据源、数据通信网和__________三部分组成。

A. 发送设备B. 传输信道C. 接受设备D. 数据宿答案： D9. 在打印Word文档时，__________不能在“打印”对话框中设置。

A. 打印页范围B. 打印机选择C. 页码位置D. 打印份数答案： C10. Windows XP中的MediaPlayer媒体播放器不支持_________格式的多媒体文件。

A. MP3B. MOVC. AVID. MPEG 答案： B* MOV是QuickTime影片格式，由Apple公司开发的一种音频、视频文件格式11. 在Word编辑状态下，对段落的缩进方式、左右边界调整等操作，最直观、快速的方法是利用__________。

一、单项选择题：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. 什么是计算机硬件和软件？它们之间的关系是什么？2. 解释一下计算机的数据表示方式，包括二进制、十进制和十六进制。

3. 请简要介绍一下计算机网络的基本概念和原理。

4. 什么是操作系统？请列举一些常见的操作系统。

5. 请解释一下计算机中的控制单元和运算单元的功能和作用。

这些题目既涉及了计算机的基本概念，又涉及了一些实际应用，能够帮助读者对计算机的整体结构和功能有一个清晰的认识。

接下来，我们将对这些题目进行详细的答案解析。

首先是第一题，关于计算机硬件和软件的定义和关系。

计算机硬件是指计算机内部的物理部件，如中央处理器（CPU）、内存、硬盘等等。

而计算机软件则是指可以运行在计算机硬件上的程序或应用。

简单来说，计算机硬件是计算机的身体，而计算机软件则是计算机的灵魂。

二者相互依赖，缺一不可。

对于第二题，我们需要了解不同进制的表示方式。

十进制是我们日常生活中最常用的数字系统，使用0-9这10个数码。

二进制是计算机内部使用的数字系统，使用0和1，常用于表示开关状态。

而十六进制则是二进制的简化表示法，使用0-9和A-F这16个数码。

十六进制常用于表示内存地址和颜色代码等。

掌握不同进制的转换方法对于理解计算机操作和编程语言是非常重要的。

接下来是关于计算机网络的基本概念和原理。

计算机网络是将多台计算机连接在一起，实现信息传输和资源共享。

它包括了局域网、城域网和广域网等不同的网络类型。

计算机网络的核心原理是数据包的传输和路由选择。

二、选择题1．世界上第一台电子计算机ENIAC中使用的基本元器件是（）。

A．机械装置C．晶体管D．集成电路2．现代计算机中使用的基本元器件是（）。

A．电子管B．晶体管C．SSI和MSI3．按照1989年IEEE科学巨型机委员会提出的运算速度分类法，计算机种类中不包括（）。

A．巨型机B．小型机D．微型机4．运算器中一般应包含（）。

B．ALU和IRC．ALU和DR D．ALU和AR5．冯·诺依曼计算机工作方式的基本特点是（）。

A．多指令流单数据流B．多指令流多数据流C．堆栈操作二、选择题1．在机器数中，（）的零的表示形式是唯一的。

A．原码C．反码D．原码和反码2．计算机系统中采用补码表示及运算的原因是（）。

A．与手工运算方式保持一致B．提高运算速度D．提高运算的精度3．设某机器采用8位补码定点数表示，其中符号位1位，数值位7位，则二进制10000000表示的十进制数为（）。

A．127 B．128 C．-1274．某机器字长32位，采用定点整数表示，符号位为1位，尾数为31位，则可表示的最大正整数和最小负整数分别为（）。

A．+（231-1）和-（1-2-32）B．+（230-1）和-（1-2-32）D．+（230-1）和-（2-31-1）5．在定点二进制运算器中，减法运算一般是通过（）来实现的。

A．原码运算的二进制减法器B．补码运算的二进制减法器C．补码运算的十进制加法器6．在浮点加减运算的对阶中，遵循小阶对大阶的原因是（）。

B．损失的位数少C．不容易产生溢出D．都不是7．若x=103,y=-25,则下列表达式采用8位定点补码运算实现时，会发生溢出的是( ) (2014年全国硕士研究生入学统一考试计算机学科专业基础综合试题)A．x+y B．-x+y D．-x-y8．float型整数据常用IEEE754单精度浮点格式表示，假设两个float型变量x 和y分别在32为寄存器f1和f2中，若（f1）=CC900000H, （f2）=B0C00000H,则x和y之间的关系为( ) (2014年全国硕士研究生入学统一考试计算机学科专业基础综合试题)B．x<y且符号不同C．x>y且符号相同D．x>y且符号不同9．某字长为8位的计算机中，已知整型变量x、y 的机器数分别为[x]补=11110100，[y]补=10110000。

计算机考研测试题及答案计算机考研是众多计算机专业学生晋升硕士研究生的通道之一，也是对学生计算机知识体系的全面考察。

在备考过程中，掌握并解答各类测试题是非常重要的。

本文将为大家提供一些常见的计算机考研测试题及答案，帮助大家更好地备考。

一、数据库1. 数据库中的ACID是指什么？请分别解释。

ACID是数据库事务处理的四个基本属性的缩写，包括原子性（Atomicity）、一致性（Consistency）、隔离性（Isolation）和持久性（Durability）。

具体解释如下：- 原子性：事务中的所有操作要么全部执行成功，要么全部失败回滚，不存在部分执行的情况。

- 一致性：事务的执行使数据库从一个一致性状态转换到另一个一致性状态，数据库在事务开始前后都必须满足一致性约束。

- 隔离性：事务的执行是相互隔离的，一个事务的中间结果不会被其他事务看到。

- 持久性：事务一旦提交，其结果就应该是永久性的。

2. 什么是数据库的三范式？数据库的三范式是指对数据的组织进行规范化的方式，包括第一范式、第二范式和第三范式。

- 第一范式：表中的字段都是单一属性的，不可再分。

- 第二范式：满足第一范式的基础上，非主键字段必须完全依赖于主键。

- 第三范式：满足第二范式的基础上，非主键字段之间不能存在传递依赖关系。

二、操作系统1. 什么是进程和线程？它们之间的区别是什么？- 进程：是指计算机中正在运行的程序，它具有独立的执行流、独立的资源和独立的地址空间。

- 线程：是进程中的一个实体，可以被操作系统调度执行，它与同一进程中的其他线程共享资源和地址空间。

两者的区别主要有以下几点：- 资源开销：进程之间切换的开销较大，线程之间切换的开销较小。

- 执行效率：线程的创建、撤销和切换比进程快。

- 数据共享：同一进程中的线程共享地址空间和资源，进程之间的数据共享需要进行特殊的处理。

2. 什么是死锁？如何避免死锁？死锁是指两个或多个进程在执行过程中因争夺资源而造成的一种僵局，彼此等待对方释放资源而无法继续执行。

2008年北京航空航天大学961计算机专业综合考研试题一、简答题（4’×5）1、写出影响算法执行的时间效率的主要因素，并指出哪些因素与算法的时间效率直接相关。

2、已知元素的入栈顺序为A,B,C,D,E，在所有可能的出栈顺序中，写出第一个出栈的元素为C且第二个出栈的元素为D的所有组合。

3、根据单词（Nov, Jul, Sept, Feb, Oct, Mar, May, Jun, Jan, Dec, Aug, Apr）的第一个字母在字母表中的顺序建立二叉排序树，当每个元素的查找概率相等时，求查找成功时的平均查找长度ASL。

4、证明：具有n个顶点的无向图最多有n(n-1)/2条边。

5、有人说，折半查找的时间效率一定比顺序查找的时间效率高，你怎么看待这种说法？为什么？二、算法设计题（10’）已知一非空完全二叉树存放于数组BT[0..n-1]中，请写出中序遍历该二叉树的非递归算法。

三、算法设计题（10’）写出不带头结点的双向链表的插入排序算法。

四、简答题（4’×5）1、数据传输控制方式有哪些？2、引入线程的目的是什么？3、P, V操作是如何实现互斥的的？4、什么是死锁？产生死锁的原因是什么？5、什么是文件系统？五、判断题（1’×10）略。

（基本上来自于历年真题）六、解答题（10’）某机器字长为16位，采用段页式存储管理算法，页内偏移为12位，段表和页表内容如下，给出4个虚拟地址（二进制形式），问哪个地址产生缺段中断，哪个地址产生缺页中断，哪些地址可以转换为物理地址，并求转换后的物理地址。

（地址格式中段号占1位，段内页号占3位，页内偏移为12位，另外，在给出的页表中，物理块号占6位，最后又问该机器的最大物理内存是多少（答案：256 KB）。

）七、简答题（4’×4）1、利用等值演算的方法，写出求命题逻辑公式的主范式的方法。

2、谓词逻辑中的永假式、可满足式、重言式、永真式之间的关系是什么？3、之间的真值关系是什么？4、如何判断公式中某个变元是约束变元还是自由变元？举例说明一个变元可以既是约束的又是自由的。

2015年全国硕士研究生入学统一考试计算机学科专业基础综合试题一、单项选择题：140小题，每小题2分，共80分。

下列每题给出的四个选项中，只有一个选项符合题目要求。

请在答题卡上将所选项的字母涂黑。

1．已知程序如下：int s(int n){ return (n<=0) ? 0 : s(n-1) +n; }void main(){ cout<< s(1); }程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息一次对应的是A．main()->S(1)->S(0) B．S(0)->S(1)->main()C．m ain()->S(0)->S(1) D．S(1)->S(0)->main()2．先序序列为a,b,c,d的不同二叉树的个数是A．13 B．14 C．15 D．163．下列选项给出的是从根分别到达两个叶节点路径上的权值序列，能属于同一棵哈夫曼树的是A．24，10，5和24，10，7 B．24，10，5和24，12，7C．24，10，10和24，14，11 D．24，10，5和24，14，64．现在有一颗无重复关键字的平衡二叉树（A VL树）,对其进行中序遍历可得到一个降序序列。

下列关于该平衡二叉树的叙述中，正确的是A．根节点的度一定为2 B．树中最小元素一定是叶节点C．最后插入的元素一定是叶节点D．树中最大元素一定是无左子树5．设有向图G=(V,E)，顶点集V={V0,V1,V2,V3}，边集E={<v0,v1>,<v0,v2>,<v0,v3>，<v1,v3>},若从顶点V0 开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是A．2 B．3 C．4 D．56．求下面带权图的最小（代价）生成树时，可能是克鲁斯卡（kruskal）算法第二次选中但不是普里姆（Prim）算法（从V4开始）第2次选中的边是A．(V1,V3) B．(V1,V4) C．(V2,V3) D．(V3,V4)7．下列选项中，不能构成折半查找中关键字比较序列的是A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，4508．已知字符串S为“abaabaabacacaabaabcc”. 模式串t为“abaabc”, 采用KMP算法进行匹配，第一次出现“失配”(s[i] != t[i]) 时，i=j=5,则下次开始匹配时，i和j的值分别是A．i=1，j=0 B．i=5，j=0 C．i=5，j=2 D．i=6，j=29．下列排序算法中元素的移动次数和关键字的初始排列次序无关的是A．直接插入排序B．起泡排序C．基数排序D．快速排序10．已知小根堆为8，15，10，21，34，16，12，删除关键字8之后需重建堆，在此过程中，关键字之间的比较数是A．1 B．2 C．3 D．411．希尔排序的组内排序采用的是（）A．直接插入排序B．折半插入排序 C．快速排序D．归并排序12．计算机硬件能够直接执行的是（）Ⅰ．机器语言程序Ⅱ．汇编语言程序Ⅲ．硬件描述语言程序A．仅ⅠB．仅ⅠⅡC．仅ⅠⅢD．ⅠⅡⅢ13．由3个“1”和5个“0”组成的8位二进制补码，能表示的最小整数是（）A．-126 B．-125 C．-32 D．-314．下列有关浮点数加减运算的叙述中，正确的是（）Ⅰ. 对阶操作不会引起阶码上溢或下溢Ⅱ. 右规和尾数舍入都可能引起阶码上溢Ⅲ. 左规时可能引起阶码下溢Ⅳ. 尾数溢出时结果不一定溢出A．仅ⅡⅢB．仅ⅠⅡⅣC．仅ⅠⅢⅣD．ⅠⅡⅢⅣ15．假定主存地址为32位，按字节编址，主存和Cache之间采用直接映射方式，主存块大小为4个字，每字32位，采用回写（Write Back）方式，则能存放4K字数据的Cache 的总容量的位数至少是（）A．146k B．147K C．148K D．158K16．假定编译器将赋值语句“x=x+3;”转换为指令”add xaddt, 3”，其中xaddt是x 对应的存储单元地址，若执行该指令的计算机采用页式虚拟存储管理方式，并配有相应的TLB，且Cache使用直写（Write Through）方式，则完成该指令功能需要访问主存的次数至少是（）A．0 B．1 C．2 D．317．下列存储器中，在工作期间需要周期性刷新的是（）A．SRAM B．SDRAM C．ROM D．FLASH18．某计算机使用4体交叉存储器，假定在存储器总线上出现的主存地址（十进制）序列为8005，8006，8007，8008，8001，8002，8003，8004，8000，则可能发生发生缓存冲突的地址对是（）A．8004、8008 B．8002、8007 C．8001、8008 D．8000、800419．下列有关总线定时的叙述中，错误的是（）A．异步通信方式中，全互锁协议最慢B．异步通信方式中，非互锁协议的可靠性最差C．同步通信方式中，同步时钟信号可由多设备提供D．半同步通信方式中，握手信号的采样由同步时钟控制20．若磁盘转速为7200转/分，平均寻道时间为8ms,每个磁道包含1000个扇区，则访问一个扇区的平均存取时间大约是( )A．B．C．D．21．在采用中断I/O方式控制打印输出的情况下，CPU和打印控制接口中的I/O端口之间交换的信息不可能是( )A．打印字符B．主存地址C．设备状态D．控制命令22．内部异常(内中断)可分为故障(fault)、陷阱(trap)和终止(abort)三类。

2009年统考计算机考研真题一．单项选择题，每小题2分。

33.在OSI参考模型中，自下而上第一个提供端到端服务的层次是 BA．数据链路层 B.传输层 C.会话层 D.应用层解析：在OSI参考模型中，自下而上第一个提供端到端服务的层次是（传输层）。

自下而上方法的一般从检查物理层开始。

自下而上分别称为：物理层、数据链路层、网络层、传输层、会话层、表示层和应用层。

传输层是两台计算机经过网络进行数据通信时,第一个端到端的层次，具有缓冲作用。

34．在无噪声情况下，若某通信链路的带宽为3kHz，采用4个相位，每个相位具有4种振幅的QAM调制技术，则该通信链路的最大数据传输速率是 BA．12kbps B.24 kbps C.48 kbps D.96 kbps解析：1924年奈奎斯特(Nyquist)就推导出在理想低通信道的最高大码元传输速率的公式:理想低通信道的最高大码元传输速率C=2W.log2 N (其中W是想低通信道的带宽,N是电平强度)信道带宽与数据传输速率的关系可以奈奎斯特(Nyquist)准则与香农(Shanon)定律描述。

奈奎斯特定理描述了有限带宽、无噪声信道的最大数据传输速率与信道带宽的关系。

香农定理则描述了有限带宽、有随机热噪声信道的最大传输速率与信道带宽、信噪比之间的关系。

奈奎斯特准则指出：对于二进制数据信号的最大数据传输速率Rmax与通信信道带宽B（B=f,单位Hz)的关系可以写为：Rmax＝2*B(bps)香农定理指出：在有随机热噪声的信道上传输数据信号时，数据传输速率Rmax与信道带宽B、信噪比S/N 的关系为：Rmax＝B*log2(1+S/N)) [以2为底,1+S/N的对数]式中，Rmax单位为bps,带宽B单位为Hz，信噪比S/N通常以dB（分贝）数表示。

若S/N=30(dB),那么信噪比根据公式：S/N(dB)=10*lg(S/N) 则S/N=1000。

若带宽B=3000Hz，则Rmax≈30kbps。

2009年计算机网络考研试题1、（09-33）在OSI参考模型中，自下而上第一个提供端到端服务的层次是（B）A．数据链路层 B.传输层 C.会话层 D.应用层解析：自下而上方法的一般从检查物理层开始。

自下而上分别称为：物理层、数据链路层、网络层、传输层、会话层、表示层和应用层。

传输层是两台计算机经过网络进行数据通信时,第一个端到端的层次，具有缓冲作用。

2、（09-34）在无噪声情况下，若某通信链路的带宽为3kHz，采用4个相位，每个相位具有4种振幅的QAM调制技术，则该通信链路的最大数据传输速率是( B )A．12kbps B.24 kbps C.48 kbps D.96 kbps解析：（1）对于带宽为6MHz的信道，若用4种不同的状态来表示数据，在不考虑热噪声的情况下，该信道的最大数据传输速率是多少？答：由无热噪声的奈奎斯特公式: C=2Hlog2N=2*6M*log24=24Mbps，即该信道的最大数据传输速率是24Mbps（2）在无噪声情况下，若某通信链路的带宽为3KHz,采用4个相位，每个相位具有4种振幅的QAM调制技术，则该通信链路的最大数据传输速率是(24kbps)C=2Hlog2N=2*3k*log216=24kbps.3、（09-35）数据链路层采用了后退N帧（GBN）协议，发送方已经发送了编号为0~7的帧。

当计时器超时时，若发送方只收到0、2、3号帧的确认，则发送方需要重发的帧数是（C）A．2 B. 3 C. 4 D. 54、（09-36）以太网交换机进行转发决策时使用的PDU地址是（A）A．目的物理地址 B.目的IP地址 C.源物理地址 D.源IP地址ARP协议是“Address Resolution Protocol”（地址解析协议）的缩写。

在局域网中，网络中实际传输的是“帧”，帧里面是有目标主机的MAC地址的。

在以太网中，一个主机要和另一个主机进行直接通信，必须要知道目标主机的MAC地址。

精选文档2019 年全国硕士研究生招生考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：1~40 小题，每题 2 分，共 80 分。

以下每题给出的四个选项中，只有一个选项切合试题要求。

1.设 n 是描绘问题规模的非负整数，以下程序段的时间复杂度是x=0 ；while ( n>= ( x+l ) * ( x+l ))x=x+l ；B. O( n1/2 )C. O( n)D. O( n2)A. O( log n)2. 若将一棵树 T 转变为对应的二又树BT ，则以下对 BT 的遍历中，其遍历序列与T 的后根遍历序列同样的是A. 先序遍历B. 中序遍历C. 后序遍历D. 按层遍历3. 对 n 个互不同样的符号进行哈夫曼编码。

若生成的哈夫曼树共有115 个结点，则 n 的值是4. A. 56 B. 57( AVLC. 58D. 60T ，再将 w 插入 T 形成在随意一棵非空均衡二又树树 ) T 中，删除某结点v 以后形成均衡二又树1 2 2均衡二又树 T 3。

以下对于 T 1与 T3的表达中，正确的选项是I. 若 v 是 T 1的叶结点，则 T1与 T3可能不同样Ⅱ .若 v 不是 T1 的叶结点，则T1 与 T 3 必定不同样Ⅲ .若 v 不是 T1 的叶结点，则T1 与 T 3 必定同样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. 排序过程中，对还没有确立最后地点的全部元素进行一遍办理称为一“趟”。