上海交通大学硕士研究生入学考试试题计算机基础2000年试题答案
- 格式:doc
- 大小:52.50 KB
- 文档页数:3
计算机基础知识基本操作及试题答案想要报考计算机考试的考生注意!小编特整理出了关于计算机基础知识的基本操作及试题答案,感兴趣的来了解一下吧!下面是整理的“计算机基础知识基本操作及试题答案”,此文本仅供参考,欢迎阅读。
计算机基础知识和基本操作一、认识自己的计算机计算机分为两个部分,硬件(hardware)、软件(software)。
硬件:物理的机械设备,比如CPU、鼠标、内存、硬盘、显示器。
软件:程序比如 windows、QQ、王者荣耀。
1、CPU (可以在计算机属性面板查看型号)中央处理器,一个CPU仅有一片奥利奥饼干那么大、那么厚。
负责计算机的所有计算操作。
CPU的主要产商:Intel(因特尔)、AMD。
(不同的价格决定不同的性能)Intel 公司的CPU主要系列是赛扬、奔腾、酷睿系列。
酷睿系列又分为 i3、i5、i7 、i9子系列,后面有小型号比如4700MQ,表示是第4代平台的处理器。
M表示移动平台,Q表示四核。
CPU 型号后面有一个主频的数字:2.4-GHz,表示GPU每秒钟能够执行24亿条指令。
CPU的原理就是二极管,有一种金属叫做硅,有一个特性,就是单向导电。
CPU使用二进制,1表示开,0表示关,科学家就研发出了CPU,具有非常强的计算能力。
2、内存条——程序工作的时候的临时存储空间内存条用来在程序运行的时候提供临时的运行空间的,特点就是:1)存储能力不是特别强,一般来说就是1G、2G、4G、8G、16G。
2)关机之后,里面的内容就丢失了。
3)存储速度非常快,可以和CPU进行完美的配合。
CPU负责计算,内存条负责临时的存储数据。
内存条的存储大小,决定了你同时能够打开软件的数量,不决定计算速度目前内存条比较出名的是金士顿。
3、硬盘——存储文件机械硬盘靠磁盘来存储,比较便宜。
现在比较好的硬盘叫做固态硬盘(SSD),存储数据非常快,不怕摔。
字节:计算机最小的存储单位就是 0 和 1 ,每 8 位 0 或者 1 我们叫做 1 个字节。
上海交通大学考试试题(模拟考)课程名称: 计算机文化基础 2004年10月8日姓名学号班级得分一、选择题(每小题1分,共55分)下列各题A) 、B)、C)、D)四个选项中,只有一个选项是正确的,请将正确选项填写在空格处。
(1) 微机硬件系统中最核心的部件是。
A) 内存储器B) 输入输出设备C) CPU D) 硬盘(2) 用MIPS来衡量的计算机性能指标是。
A) 传输速率B) 存储容量C) 字长D) 运算速度(3) 在计算机中,既可作为输入设备又可作为输出设备的是。
A) 显示器B) 磁盘驱动器C) 键盘D) 图形扫描仪(4) 微型计算机中,ROM的中文名字是。
A) 随机存储器B) 只读存储器C) 高速缓冲存储器D) 可编程只读存储器(5) 要存放10个24×24点阵的汉字字模,需要存储空间。
A) 74B B) 320B C) 720B D) 72KB(6) 把硬盘上的数据传送到计算机的内存中去,称为。
A) 打印B) 写盘C) 输出D) 读盘(7) 目前常用的3.5英寸软盘片角上有一带黑滑块的小方口,当小方口被关闭时,其作用是。
A) 只能读不能写B) 能读又能写C) 禁止读也禁止写D) 能写但不能读(8) 计算机网络的目标是实现。
A) 数据处理B) 文献检索C) 资源共享和信息传输D) 信息传输(9) 计算机内部采用的数制是。
A) 十进制B) 二进制C) 八进制D) 十六进制(10)下列四项中,不属于计算机病毒特征的是。
A) 潜伏性B) 传染性C) 激发性D) 免疫性(11)计算机病毒是可以造成计算机故障的。
A) 一种微生物B) 一种特殊的程序C) 一块特殊芯片D) 一个程序逻辑错误(12)下列存储器中,存取速度最快的是。
A) CD-ROM B) 内存储器C) 软盘D) 硬盘(13)CPU主要由运算器和组成。
A) 控制器B) 存储器C) 寄存器D) 编辑器(14)计算机软件系统包括。
A) 系统软件和应用软件B) 编辑软件和应用软件C) 数据库软件和工具软件D) 程序和数据(15)计算机能直接识别的语言是。
计算机专业基础综合计算机组成原理(计算机系统概述)历年真题试卷汇编1(总分:70.00,做题时间:90分钟)一、单项选择题(总题数:29,分数:58.00)1.电了计算机问世至今,新型机器不断推陈出新,但不管怎么更新,依然具有“存储程序”的特点,最早提出这种概念的是____。
【上海交通大学1999年】A.巴贝奇B.冯.诺依曼√C.帕斯卡D.贝尔考查计算机发展历程。
2.对有关数据加以分类、统计、分析,这属于计算机在——方面的应用。
A.数值计算B.辅助设计C.数据处理√D.实时控制考查计算机的发展及应用。
3.冯.诺依曼型计算机的最根本特征是____。
【中科院计算所2001年】A.以运算器为中心B.采用存储程序原理√C.存储器按地址访问D.数据以二进制编码,并采用二进制运算考查冯.诺依曼型计算机基本概念。
冯.诺依曼型计算机的最根本特征是采用存储程序原理,基本工作方式是控制流驱动方式,工作方式的基本特点是按地址访问并顺序执行指令。
4.冯.诺依曼型计算机的基本工作方式是____。
【中科院计算所1998年】A.控制流驱动方式√B.多指令流多数据流方式C.微程序控制方式D.数据流驱动方式考查冯.诺依曼型计算机基本概念。
解析同上。
5.计算机系统采用层次化结构组成系统,从最上层的最终用户到最底层的计算机硬件,其层次化构成为____。
A.高级语言机器一操作系统机器一汇编语言机器一机器语言机器一微指令系统B.高级语言机器一汇编语言机器一机器语言机器一操作系统机器一微指令系统C.高级语言机器一汇编语言机器一操作系统机器一机器语言机器一微指令系统√D.高级语言机器一汇编语言机器一操作系统机器一微指令系统一机器语言机器考查计算机系统层次化结构。
6.计算机系统是由____组成的。
【武汉大学2007年】A.CPU和存储器B.CPU和接口C.运算器和控制器D.硬件系统和软件系统√考查计算机系统概念。
完整的计算机系统包括硬件系统和软件系统。
计算机应用基础(二)第一次作业计算机基础知识成绩92。
50/满分100.00题目1正确获得1.00分中的1。
00分0qaid=16403532&题干3计算机软件一般分为系统软件和应用软件两大类,不属于系统软件的是____。
选择一项:a。
数据库管理系统b。
语言处理程序c。
操作系统d. 客户管理系统反馈正确答案是:客户管理系统题目2正确获得1.00分中的1。
00分0qaid=16403541&题干332位微机中的32是指该微机______.选择一项:a. 能同时处理32位二进制数b. 运算精度可达小数点后32位c。
具有32根地址总线d. 能同时处理32位十进制数反馈正确答案是:能同时处理32位二进制数题目3正确获得1.00分中的1。
00分0qaid=16403524&题干3目前计算机的基本工作原理是______。
选择一项:a。
存储程序控制b. 自动存储c. 程序设计与存储程序d. 程序设计反馈正确答案是:存储程序控制题目4正确获得1。
00分中的1.00分0qaid=16403522&题干3在计算机领域中,ASCII码用一个字节即8位二进制数来表示一个字符,这个字节的变化范围是______。
选择一项:a。
从00000000到01111111b。
从00000000到11111111c。
从00000000到10000000d. 从00000001到11111111反馈正确答案是:从00000000到01111111题目5正确获得1.00分中的1.00分0qaid=16403543&题干3输出设备的任务是将信息传送到计算机之外的______。
选择一项:a. 电缆b. 光盘c. 介质d。
文档反馈正确答案是:介质题目6正确获得1.00分中的1.00分0qaid=16403520&题干3目前广泛使用计算机进行人事档案管理、财务管理,这种应用属于计算机领域中的______。
文档来源为 :从网络收集整理 .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)三类。
上海交通大学1995年硕士研究生入学测试试题计算机原理和系统结构A. 计算机原理部分一、选择题:(每小题1.5分,总共12分)1.用n+1位字上(其中1位后号位)表示定点整数时,所能表示的数位范围是________;用n +1位字长(其中1位符号位)表示定点小数时,所能表示的数值范围是___________。
A、0≤│N│≤2n-1;B、0≤│N│≤2n-1-1;C、1≤│N│≤2n-1-1;D、1≤│N│≤2n-1;E、0≤│N│≤1-2-nF、0≤│N│≤1-2-(n+1).2.堆栈寻址方式中,设A为累加的;SP为堆栈指示器,Msp为sp指向的栈顶单元,如果过棋操作的动作是:(A)→Msp,(sp)-1→sp,那么出栈,操作的动作应为______。
A、(Msp)→A,(sp)÷1→spjB、(sp) +1→sp; (Msp) →AC、(sp)-1→sp,(Msp) →AD、(Msp) →A, (sp)-1→sp3.位操作频指令的功能是______。
A、对cpu内部通用序宰存或主存某一单元任一位进行状态检测(0或1);B、对cpu内部通用宰存或主存某一单元任一位进行状态强置(0或1);C、对cpu内部通用宰存或主存某一单元任一位进行状态检测式强置;D、进行移位操作。
4、微指令执行的顺序控制问题,实际上是如何确定下一条微指令的地址问题,通常,用的一种方法是断定方式,其基本思想是_______。
A、用程序计设加pc来产生后很微指令地址;B、用微程序计数加Mpc来产生后很微指令地址;C、通过微指令顺序控制字段由设计者指定或者由设计者指定的判断别字,段控制产生后很微指令地址;D、通过指令中指定一个专门字段来控制产生后很微指令地址。
5、磁盘存储加的记录方式一般采用_________。
A、归察制;B、不归察制;C、调频制;D、调相制6、同步通讯之所以比异步通讯具有较高的传输连享是因为_______。
计算机专业基础综合计算机组成原理(计算机系统概述)历年真题试卷汇编1(总分:70.00,做题时间:90分钟)一、单项选择题(总题数:29,分数:58.00)1.电了计算机问世至今,新型机器不断推陈出新,但不管怎么更新,依然具有“存储程序”的特点,最早提出这种概念的是____。
【上海交通大学1999年】(分数:2.00)A.巴贝奇B.冯.诺依曼√C.帕斯卡D.贝尔解析:解析:考查计算机发展历程。
2.对有关数据加以分类、统计、分析,这属于计算机在——方面的应用。
(分数:2.00)A.数值计算B.辅助设计C.数据处理√D.实时控制解析:解析:考查计算机的发展及应用。
3.冯.诺依曼型计算机的最根本特征是____。
【中科院计算所2001年】(分数:2.00)A.以运算器为中心B.采用存储程序原理√C.存储器按地址访问D.数据以二进制编码,并采用二进制运算解析:解析:考查冯.诺依曼型计算机基本概念。
冯.诺依曼型计算机的最根本特征是采用存储程序原理,基本工作方式是控制流驱动方式,工作方式的基本特点是按地址访问并顺序执行指令。
4.冯.诺依曼型计算机的基本工作方式是____。
【中科院计算所1998年】(分数:2.00)A.控制流驱动方式√B.多指令流多数据流方式C.微程序控制方式D.数据流驱动方式解析:解析:考查冯.诺依曼型计算机基本概念。
解析同上。
5.计算机系统采用层次化结构组成系统,从最上层的最终用户到最底层的计算机硬件,其层次化构成为____。
(分数:2.00)A.高级语言机器一操作系统机器一汇编语言机器一机器语言机器一微指令系统B.高级语言机器一汇编语言机器一机器语言机器一操作系统机器一微指令系统C.高级语言机器一汇编语言机器一操作系统机器一机器语言机器一微指令系统√D.高级语言机器一汇编语言机器一操作系统机器一微指令系统一机器语言机器解析:解析:考查计算机系统层次化结构。
6.计算机系统是由____组成的。
大学计算机基础课后题答案第1章计算机基础知识一、选择题1.B2.B3.B4.B5.B6.B7.C8.D 9.B 10.D 11.C 12.A 13.B 14.D二、填空题1、1946 美国ENIAC2、4 电子管晶体管集成电路超大规模集成电路3、超导计算机量子计算机光子计算机生物计算机神经计算机4、专用计算机通用计算机5、信息基础技术信息系统技术信息应用技术6、运算器控制器存储器输入设备输出设备7、7445 682 3755 30088、0292 1717 A2FC B1B1 B7D9 E4AE9、500010、72 128三、问答题1、运算速度快计算精度高具有记忆和逻辑判断能力具有自动运行能力可靠性高2、巨型机大型机小型机微型机服务器工作站3、数据计算信息处理实时控制计算机辅助设计人工智能办公自动化通信与网络电子商务家庭生活娱乐4、计算机的工作过程就是执行程序的过程,而执行程序又归结为逐条执行指令:(1)取出指令:从存储器中取出要执行的指令送到CPU内部的指令寄存器暂存;(2)分析指令:把保存在指令寄存器中的指令送到指令译码器,译出该指令对应的操作;(3)执行指令:根据指令译码器向各个部件发出相应控制信号,完成指令规定的操作;(4)一条指令执行完成后,程序计数器加1或将转移地址码送入程序计数器,然后回到(1)。
为执行下一条指令做好准备,即形成下一条指令地址。
5、计算机自身电器的特性,电子元件一般有两个稳定状态,且二进制规则简单,运算方便。
四、操作题1、(111011)2=(59)10=(73)8=(3B)16(11001011)2=(203)10=(313)8=(CB)16(11010.1101)2=(26.8125)10=(32.64)16=(1A.D)162、(176)8=(1111110)2(51.32)8=(101001.011010)2(0.23)8=(0.010011)23、(85E)16=(100001011110)2(387.15)16=(001110000111.00010101)24、(79)=(01001111)原码=(01001111)反码=(01001111)补码(-43)=(10101011)原码=(11010100)反码=(11010101)补码第2章计算机硬件及软件系统一、选择题1.A2.D3.D4.C5.B6.C7.C8.A9.D 10.B 11.D 12.C 13.C 14.B 15.D 16.A 17.C 18.D 19.D 20.D二、填空题1、系统应用2、运算控制单元存储器输出/输入设备3、数据库管理系统4、1000赫兹5、ROM RAM Cache6.、RAM 数据丢失7、U盘的文件管理系统中密码8、同一部件内部连接同一台计算机各个部件主机与外设9、数据总线地址总线控制总线10、32 6411、图形加速接口12、CPU与内存内存13、控制器运算器14、CPU与内存15、指令数据16、CPU与内存及显存间数据的交换第3章操作系统基础一、选择题1.C2.B3.A4.D5.A6.D7.B8.B 9.B 10.A 11.B 12.B 13.A 14.B二、填充题1、文件管理2、并发性3、EXIT4、Am*.wav5、开始6、Alt+PrintScreen7、PrintScreen8、Ctrl+Z9、全选10、添加/删除程序11、输入法三、问答题1、管理和协调计算机各部件之间的资源分配与运行,它是计算机所有硬件的大管家,是用户与计算机的接口。
B1 上海交通大学硕士生入学考试试题(选编)上海交通大学1999年微机原理与应用考研题1、计算(10101.01)2+(10101.01)BCD+(15.4)16=10解上式=(16+5+0.25)+(15.4)+(21.25)=57.9102、已知[X]补=00110101B,则[一2X]补= 2[-X]补=[-X]补+[-X]补=11001011B+11001011B=10010110B按习题集上的做法,先求2X的补码,然后再对其求反加1.3、一个4位的十进制数,当用规格化浮点数表示时,(阶码和尾数均用补码表示)最少需要多少位的二进制数?(IEEE:32/64/80) 20位4、用与非门构成一个半加器电路,并写出其真值表和逻辑表达式.请参考组成原理教材5、如图所示的逻辑电路的功能是什么?请参考数字电路教材6、8086/8088CPU在结构上由那两个独立的处理单元组成,这样的结构其主要的优点是什么?解: 8086/8088CPU在结构上由总线接口部件BIU和执行部件EU这两部分组成,这样的结构的优点是,使取指令和执行指令的工作可以同时进行,成倍的提高了CPU的运行速度.7、用指令SUB对两个8位的二进制数据进行减法运算后,得到结果为0FAH,以及标志位OF=1,SF=1,和CF=1,这个结果表示的十进制数值是多少?解: 结果是一个十六进制数,它的十进制数有两种可能:(1)FAH=15X16+10=250D 无符号数(2)[FAH]补=00000110B=6D 有符号数现在的关键是确定这是两个有符号数的运算还是无符号数的运算,如果为无符号数,因为OF=1,运算结果是不正确的,对于无符号数,则不管CF是否为1,在这个八位数的范围内结果是正确的.(当然如果要考虑它的高8位的话,要有一个进位或借位1)所以应取250D8、已知 ORG 0100H,ARY DW 3,$+4,4,6CNT EQR $-ARYDB 7,8,CNT,9则执行者 MOV AX,ARY+2和MOV BX,ARY+10后,AX=0106H ,BX= 0908H .解这一题:要先画出内存存储图[0100H] 03 00 06 01 04 00 06 00 07 00 08 08 09然后再做会比较安全一点.9、今要在变量名为STRING的数据区中顺次存放数据‘A’、‘B’、‘C’、‘D’、‘E’、‘F’、‘G’,‘H‘请写出分别用DB、DW、DD实现的语句。
计算机应用基础(二)第一次作业计算机基础知识成绩92.50/满分100.00题目1正确获得1.00分中的1.00分0qaid=16403532&题干3计算机软件一般分为系统软件和应用软件两大类,不属于系统软件的是____。
选择一项:a. 数据库管理系统b. 语言处理程序c. 操作系统d. 客户管理系统反馈正确答案是:客户管理系统题目2正确获得1.00分中的1.00分0qaid=16403541&题干332位微机中的32是指该微机______。
选择一项:a. 能同时处理32位二进制数b. 运算精度可达小数点后32位c. 具有32根地址总线d. 能同时处理32位十进制数反馈正确答案是:能同时处理32位二进制数题目3正确获得1.00分中的1.00分0qaid=16403524&题干3目前计算机的基本工作原理是______。
选择一项:a. 存储程序控制b. 自动存储c. 程序设计与存储程序d. 程序设计反馈正确答案是:存储程序控制题目4正确获得1.00分中的1.00分0qaid=16403522&题干3在计算机领域中,ASCII码用一个字节即8位二进制数来表示一个字符,这个字节的变化范围是______。
选择一项:a. 从00000000到01111111b. 从00000000到11111111c. 从00000000到10000000d. 从00000001到11111111反馈正确答案是:从00000000到01111111题目5正确获得1.00分中的1.00分0qaid=16403543&题干3输出设备的任务是将信息传送到计算机之外的______。
选择一项:a. 电缆b. 光盘c. 介质d. 文档反馈正确答案是:介质题目6正确获得1.00分中的1.00分0qaid=16403520&题干3目前广泛使用计算机进行人事档案管理、财务管理,这种应用属于计算机领域中的______。
2000年试题答案:
1.
O (m+n)
next: 0 1 1 1 2 2 1 2 3 2 1
nextval: 0 1 1 0 2 2 0 1 3 2 0
2.
1/(1- ) 推导参见严蔚敏《数据结构》(C语言版)p.261 3.
A
B C D
E I
F
G H
4.
Log [m/2] (N+1)/2 + 1
推导参见严蔚敏《数据结构》(C语言版)p.241
6.
O (n log n)
证明参见严蔚敏《数据结构》(C语言版)p.292
7.
成功:((n+1)log2(n+1)/n )-1
证明参见严蔚敏《数据结构》(C语言版)p.221
不成功:[log2n]+1
8
O (n log2n)
9.
1)平均情况下:2m
说明参见严蔚敏《数据结构》(C语言版)p.304
2)最长:n
最短:1
10.
BiThrNode * postorder_succ (BiThrTree r, BiThrNode *p)
{if (p= = r) return (NULL);
else {q= parent(p);
if ( p= = q->rchild) return (q);
if ((p= =q->lchild)&&(q->rtag= =1)) return (q);
if ((p= =q->lchild)&&(q->rtag= =0))
{q=q->rchild;
while (q->ltag= =0|| q->rtag= =0)
{ while(q->ltag= =0) q=q->lchild;
if (q->rtag= =0) q=q->rchild;
}
return (q);
}
}
}
BiThrNode * parent ( BiThrNode *p)
{ q=p;
while(q->ltag= =0) q=q->lchild;
q=q->lchild;
if (q->rchild= =p) return(q);
else { q=q->rchild;
while(q->lchild!=p) q=q->lchild;
return(q);
}
}
11.
void DeleteBST(BiTree &T,Keytype x)
{ f->lchild=T; p=T;
while (!p)
if (p->data<=x)
{ f->lchild=p->rchild;
q=p;
p=p->rchild;
delete(q及q的左子树) ;// 要用非递归的遍历具体实现
}
else { f=p;
p=p->lchild;
}
}
12.
int sini (BiTree p, BiTree q)
{ if (p&&q) return (1);
else if ((p&&!q)||(!p&&q)) return (0);
else return (sini (p->lchild,q->lchild)&& sini (p->rchild,q->rchild)); }。