下载文档原格式
2017年计算机考试试题及答案一、选择题（每题2分，共40分）1. 计算机网络中，下列哪种协议不属于TCP/IP协议族？（）A. HTTPB. FTPC. SMTPD. ICQ答案：D2. 下列哪种编程语言不是面向对象的编程语言？（）A. JavaB. C++C. PythonD. C答案：D3. 在计算机系统中，下列哪个设备不属于输入设备？（）A. 键盘B. 鼠标C. 扫描仪D. 打印机答案：D4. 计算机操作系统中，下列哪个概念不是进程和线程的关系？（）A. 并发B. 同步C. 互斥D. 串行答案：D5. 在数据库中，下列哪种数据模型不是关系型数据库模型？（）A. 层次模型B. 网状模型C. 关系模型D. 面向对象模型答案：D6. 下列哪个软件不属于办公自动化软件？（）A. Microsoft OfficeB. WPS OfficeC. Adobe PhotoshopD. CorelDRAW答案：C7. 计算机网络中，下列哪种传输方式不是广播传输方式？（）A. 单播B. 多播C. 广播D. 组播答案：A8. 在计算机编程中，下列哪种编程范式不是函数式编程范式？（）A. 命令式编程B. 声明式编程C. 面向对象编程D. 逻辑编程答案：C9. 下列哪个操作系统不是基于Linux内核的？（）A. UbuntuB. Red HatC. WindowsD. CentOS答案：C10. 在计算机科学中，下列哪种算法不是排序算法？（）A. 冒泡排序B. 快速排序C. 暴力排序D. 插入排序答案：C二、填空题（每题2分，共20分）1. 计算机网络中，IP地址分为______类。
答案：A、B、C2. 在计算机编程中，面向对象的三个基本特性是______、______和______。
答案：封装、继承、多态3. 计算机操作系统中，进程和线程的主要区别是______。
答案：进程是系统进行资源分配和调度的基础单位，线程是进程的执行单元4. 数据库中，主键的作用是______。
昆明理工大学2017年硕士研究生招生入学考试试题(A 卷)
考试科目代码：818 考试科目名称 ：计算机学科专业基础综合
考生答题须知
1． 所有题目（包括填空、选择、图表等类型题目）答题答案必须做在考点发给的答题纸上，做在本试题册上无效。
请考生务必在答题纸上写清题号。
2． 评卷时不评阅本试题册，答题如有做在本试题册上而影响成绩的，后果由考生自己负责。
3． 答题时一律使用蓝、黑色墨水笔或圆珠笔作答（画图可用铅笔），用其它笔答题不给分。
4． 答题时不准使用涂改液等具有明显标记的涂改用品。
数据结构部分
一、填空题：（每空1分，共20分）
3.用计算机处理问题的方法称为 算法 。
评价其优劣的的办法是在其 的前提下主要是考察其 时间 和 空间 复杂度。
1.在Data Set 中，数据元素分为 行 元素和 列 元素； 元素间的关系是独立于计算机之外的称为 逻辑 关系， 分为 线性 和 非线性 关系。
实际问题
2.这里的数据关系称为 存储关系， 有 顺序 、 链式 、 索引 和 散列 存储方法。
用数据描述实际问题获得数据集 Data Set 计算机 存储器 数据存入计算机
昆明理工大学2017年硕士研究生招生入学考试试题。
桂林电子科技大学2017年硕士研究生入学考试复试试卷考试科目代码：309考试科目名称：计算机网络二、填空题（每空2分，共20分）1、面向连接服务具有建立连接、和取消连接这三个阶段。
2、是一组规则，规定了同一层上对等实体之间所交换的数据包或者报文的格式和含义。
3、一般用来划分冲突域的设备是。
3、FTP使用的传输层协议为。
4、RIP协议采用算法，OSPF协议采用算法。
5、在TCP的流量控制和拥塞控制中，发送方窗口的大小受和的限制。
6、一个理想低通信道带宽为3KHZ，其最高码元传输速率为6000Baud。
若一个码元携带2bit 信息量，则最高信息传输速率为。
7、设用户的数据为01111101111101，根据比特填充方法，输出的比特序列应该是。
三、简答题（30分，每题6分）1、请简要描述三次握手建立TCP连接的过程。
2、滑动窗口协议中，发送窗口和接收窗口的含义。
3、一个IP数据报的长度是4000字节，网络层的MTU是1500，请回答下列问题：a.该IP包在传送时是否需要分解为更小的数据包？为什么？b.如果要分，写出该IP数据报会被分成几个片？c.各个片的头部信息中，Length、Fragflag、offset字段的内容。
4、传输信息位串为1011110001，生成码为1001，求出发送端发送的码字。
并简述其校验的过程。
5、请解释为什么会发生网络拥塞，并给出典型的网络拥塞标志？四、应用题（30分，每题10分）1、有某子网的LSPs（链路状态数据包）集合如下所示，请完成以下题目：a..请根据此LSPs给出此网络的拓朴结构图(4分)；b.请根据Dijsktra’s算法计算出A点到其他各点的最小路径(6分，无中间过程不得分)。
2、假设接收窗口的大小是16KB且最大段大小是1KB，传输开始时将阈值设为10KB，当发生超时时，TCP的拥塞窗口为16KB，且接收窗口这时也是12KB。
假设后面所有的传输都成功，需要多少次（从开始算起）TCP拥塞窗口等于上一个接收窗口？请画图示意。
北京邮电大学2017年硕士研究生入学考试试题考试科目：计算机学科基础综合请考生注意：①所有答案（包括选择题和填空题）一律写在答题纸上，否则不计成绩。
②不允许使用计算器一、单项选择题（每小题2分，共80分）1.下列选项中与算法的时间复杂度有关的是A.问题规模B.计算机硬件性能C.编译程序质量D.程序设计语言2.用单链表存储两个各有n个元素的有序表，若要将其归并成一个有序表，最少的比较次数是A.n-lB.nC.2n-1D.2n3.一个队列用只带尾指针的单循环链表存储，则队列插入和删除操作的时间复杂度分别是A.O（l）、O（l）B.O（l）、O（n）C.O（n）、o（l）D.O（n）、O（n)4.已知一个三维数组A[l.15][0.9][-3.6]的每个元素占用5个存储单元，该数组总共需要的存储空间单元数为A.1500B.4050C.5600D.75005.一棵具有n（m>1）个结点的树，其高度最小和最大分别是A.1、log2nB.1、nC.2、nD.log2n、n6.在下列选项中，不能作为树的存储形式是A.孩子链表表示法B.双亲表示法C.按层次的顺序存储表示法D.孩子兄弟表示法7.一个具有n个顶点的强连通图，边数最多是A.n-1B.nC.n（n-1）/2D.n（n-l）8.下列关于图的叙述中，正确的是A.在有向图中，各顶点的入度之和等于各顶点的出度之和。
B.若图的临界矩阵是对称矩阵，则该图一定是连通的无向图。
C.连通分量是无向图中的极小连通子图。
D.用临界表存储图所用的空间大小只与图的顶点数有关。
9.查找有序表中的某一指定元素时，折半查找比顺序查找的比较次数A.一定少B.一定多C.相同D.不确定10.下列关于排序算法的叙述中，正确的是A.算法的稳定性是指在各种情况下的时间效率相差不大的特性。
B.希尔（Shell）排序的实质是多次利用直接插入排序方法。
C.所有时间复杂度为O（n2）的简单排序算法都是稳定的。
计算机考研复试题目及答案计算机考研复试作为考生进入硕士研究生阶段的重要一环，对考生的计算机专业知识以及解决问题的能力进行全面考察。
下面将给大家介绍一些常见的计算机考研复试题目及答案，希望能够对考生们的备考有所帮助。
一、综合知识与技术能力1. 请简述计算机系统结构并指出其中的关键组成部分。
计算机系统结构由四个主要组成部分构成：中央处理器（CPU）、存储器、输入设备和输出设备。
其中，中央处理器是计算机的核心，负责进行数据的计算和操作；存储器用于存储数据和程序；输入设备用于将外部信息输入计算机系统；输出设备则是将计算机处理的结果显示给用户。
2. 请说说主流操作系统的分类及其特点。
主流操作系统主要分为四类：分时操作系统、实时操作系统、网络操作系统和分布式操作系统。
分时操作系统以时间片轮转的方式实现多个用户同时使用计算机系统，具有良好的用户体验和资源管理能力；实时操作系统主要用于对时间要求严格的任务处理，能够满足实时性要求；网络操作系统则是针对网络环境下的计算机系统，强调对网络资源的管理和协同工作；分布式操作系统则是将多台计算机组成一个整体共享资源的系统，实现了资源共享和负载均衡的优点。
二、数据结构与算法1. 请简述常见的排序算法并给出它们的时间复杂度。
常见的排序算法有冒泡排序、选择排序、插入排序、快速排序和归并排序。
冒泡排序的时间复杂度为O(n^2)；选择排序的时间复杂度也为O(n^2)；插入排序的时间复杂度为O(n^2)；快速排序的时间复杂度为O(nlogn)；归并排序的时间复杂度也为O(nlogn)。
2. 请解释什么是动态规划算法，并给出一个应用实例。
动态规划算法是指通过对问题进行划分和确定状态转移方程，将问题分解为若干子问题的求解得到最优解的方法。
一个经典的动态规划应用实例是求解斐波那契数列。
斐波那契数列定义为：F(0) = 0，F(1) = 1，F(n) = F(n-1) + F(n-2)。
我们可以使用动态规划算法以时间复杂度O(n)求解斐波那契数列中的第n项。
计算机考研复试题目及答案解析前言：计算机考研的复试是考生进入研究生阶段的重要一步，复试中将进行笔试和面试环节。
笔试是考察考生的基础知识和专业素养，而面试则更加注重考生的综合能力和研究潜力。
本文将为大家介绍一些常见的计算机考研复试题目，并给出答案解析，以帮助考生更好地应对复试。
一、操作系统1. 什么是进程和线程？它们有什么区别？答案解析：进程是指正在运行的程序的实例，具有独立的内存空间和系统资源。
线程是进程中的一个执行单元，一个进程可以包含多个线程。
进程是资源分配和调度的基本单位，而线程是CPU调度和执行的基本单位。
2. 解释虚拟内存的概念。
答案解析：虚拟内存是指利用磁盘空间来扩展可寻址的内存空间，使得进程可以拥有比物理内存更大的地址空间。
虚拟内存的大小受到物理内存和硬盘空间的限制。
二、数据结构与算法1. 请解释栈和队列的概念，并分别给出它们的应用场景。
答案解析：栈是一种先进后出（FILO）的数据结构，队列是一种先进先出（FIFO）的数据结构。
栈常用于递归、表达式求值和括号匹配等场景，而队列常用于模拟队列等实际应用场景。
2. 解释二叉搜索树（BST）的特点，并给出其查找和插入操作的时间复杂度。
答案解析：二叉搜索树是一种有序的二叉树，其中左子树的节点值都小于根节点，右子树的节点值都大于根节点。
其查找操作的时间复杂度为O(log n)，插入操作的时间复杂度也是O(log n)，其中n表示树的节点数。
三、数据库1. 什么是关系数据库？举例说明其常见的特点和优势。
答案解析：关系数据库是基于关系模型的数据库，采用表的形式存储数据。
其常见特点包括数据的结构化、数据的共享性、数据的完整性和数据的独立性。
关系数据库具有良好的数据一致性和可扩展性。
2. 解释事务的概念，并说明ACID特性的含义。
答案解析：事务是指数据库操作的一个执行单元，要么全部执行成功，要么全部回滚。
ACID是指原子性（Atomicity）、一致性（Consistency）、隔离性（Isolation）和持久性（Durability），是事务应满足的特性。
北京邮电大学 97 年硕士研究生入学试题1．已知：[Y]补=Y0.Y1Y2…Y n求证：[-Y]补=Y0.Y1Y2…Y n+2-n证明：若 Y为正值则依定义有：Y=[Y]补=Y0.Y1Y2…Y n[-Y]补=2+[-Y]=2+（-Y0.Y1Y2…Y n）=2-Y0.Y1Y2…Y n=Y0.Y1Y2…Y n+2-n若 Y为负值则依定义有：Y=2-[Y]补=2-Y0.Y1Y2…Y n[-Y]补=Y=2-Y0.Y1Y2…Y n=Y0.Y1Y2…Y n+2-n所以命题成立。
2．已知：X= - 0.1011*2-010Y= + 0.1101*2-011用变形补码求 X-Y=？依题意： [M X]补 = 11.0101 [E X]补 = 11.110[M Y]补 = 00.1101 [E Y]补 = 11.101 解：（1）对阶ΔE = [E X]补- [E Y]补 = 11.110- 11.101=00.001>0[E(X-Y)]补 = [E Y]补 +ΔE = 11.110[M Y]补' = 00.01101（2）尾数相减[M(X-Y)]补 = [M X]补- [M Y]补' =11.0101 -00.01101=10.11101（3）规格化[M(X-Y)]补' =11.011101 [E(X-Y)]补' =11.111 （4）0舍1入处理[M(X-Y)]补' =11.0111（5）判别溢出[E(X-Y)]补' =11.101 无溢出所以：X-Y= - 0.1001*2-0013. 某机CPU可提供16条地址线，8条数据线，1条控制线（R/W），R/W = 1表示读，R/W = 0表示写。
现用存储器总容量为8KB。
拟采用2K*4位的RAM芯片。
（1）画出CPU与RAM之间的连接图。
（2）说明该RAM的地址范围。
该RAM的地址范围为0000H---1FFFH4. 某机主存容量为64K*16位，采用单字长，单地址指令，共有60条。
2017年计算机考研真题哎呀，一提到2017 年计算机考研真题，我这心里就跟过电影似的。
想起当年我自己准备考研的那段日子，那可真是一把辛酸泪啊！就说这 2017 年的计算机考研真题吧，它就像一个神秘的城堡，充满了各种难题和陷阱。
数据结构、操作系统、计算机组成原理、计算机网络，每一个科目都像是城堡中的一个房间，等着你去探索和征服。
数据结构那部分的真题，可真是让人头疼。
有一道题是关于二叉树的遍历，那复杂的节点关系，就像是一团乱麻，得一点一点地理清楚。
我还记得当时我做这道题的时候，草稿纸用了好几张，一会儿画这个图，一会儿写那个代码，脑袋都快炸了。
操作系统的真题也不简单。
比如有个关于进程调度的问题，要求计算各种时间参数。
这可不仅要对概念清楚，还得有很强的逻辑思维能力。
我就跟个侦探似的，在各种线索中寻找答案，稍有不慎就会出错。
计算机组成原理的真题更是“磨人精”。
什么指令系统、存储系统，各种细节都得考虑到。
有个关于 cache 命中率的计算，那数字和公式看得我眼花缭乱，感觉自己就像在一个数字迷宫里打转。
计算机网络的真题也没放过我。
IP 地址的划分、路由协议的理解，每一个知识点都像是一颗钉子，扎得我心里痒痒的。
不过，话说回来，虽然这些真题很难，但也正是通过它们，才能真正检验出我们的水平。
就像爬山一样，过程很艰辛，但当你爬到山顶，看到那美丽的风景，一切都值得了。
如今再回过头来看 2017 年的计算机考研真题，我觉得它们不仅仅是一道道题目，更是我们成长的见证。
每一道做错的题，都是一次教训；每一道做对的题，都是一次鼓励。
它们让我们明白，只有不断努力，不断积累，才能在计算机这个广阔的领域里站稳脚跟。
所以啊，准备考研的小伙伴们，别怕这些真题，勇敢地去面对它们，相信自己一定能攻克这座城堡，走向成功的彼岸！。
计算机考研复试面试题库及答案一、专业基础知识1. 计算机组成原理题目：简述冯·诺伊曼体系结构的基本原理。
答案：冯·诺伊曼体系结构是一种计算机系统的设计原则，也是现代计算机的基础。
它的基本原理包括以下几点：- 存储程序：计算机通过将指令和数据存储在同一个存储器中，实现了程序的自动执行。
- 二进制系统：计算机使用二进制表示数据和指令，简化了计算机系统的设计和实现。
- 指令流水线：计算机通过将指令的执行过程划分为多个阶段，并同时进行不同指令的执行，提高了计算机的执行效率。
- 内存层次结构：计算机通过多层次的存储器结构，包括高速缓存、内存和外部存储器，提供了不同速度和容量的存储器选择。
2. 算法与数据结构题目：什么是二叉搜索树？如何实现插入和删除操作？答案：二叉搜索树（BST）是一种特殊的二叉树，满足以下条件：- 对于树中的每个节点，其左子树的所有节点的值小于该节点的值，右子树的所有节点的值大于该节点的值。
- 对于树中的每个节点，其左子树和右子树也是二叉搜索树。
实现插入操作的步骤：- 从根节点开始，将待插入的值与当前节点的值进行比较。
- 如果待插入的值小于当前节点的值，且当前节点的左子树为空，则将待插入的值作为当前节点的左子节点。
- 如果待插入的值大于当前节点的值，且当前节点的右子树为空，则将待插入的值作为当前节点的右子节点。
- 如果待插入的值小于当前节点的值，且当前节点的左子树不为空，则将当前节点更新为其左子节点，重复上述步骤。
- 如果待插入的值大于当前节点的值，且当前节点的右子树不为空，则将当前节点更新为其右子节点，重复上述步骤。
实现删除操作的步骤：- 如果待删除的节点为叶子节点，直接删除。
- 如果待删除的节点只有一个子节点，将子节点连接至待删除节点的父节点。
- 如果待删除的节点有左右子节点，找到其右子树中的最小节点，用该节点替换待删除节点，并删除最小节点。
二、算法设计与分析1. 动态规划题目：请简述动态规划算法的基本思想，并给出一个应用动态规划算法的例子。
上午复试计算机，5道编程：1：顺序存储的n个整数，编程输出最大的前k个。
2：编函数并递归调用求1到n的和。
3：编函数swap(int a,int b)实现参数交换。
4：学生信息，姓名学号英语成绩数学成绩政治成绩。
a:写出学生结构题信息。
b:finput()输入每个学生信息。
c:求单科和总分最高的学生信息。
5：a:编函数求字符串中数字个数。
b:编函数求字符串中字符的ASCII的总和。
以上是之前学长记下的。
下面是我的个人复试感想（计算机应用这块，请注意模式识别和软件工程的笔试不是这些题目啊）报道10号，电教楼门口贴出各位老师简介，以及招生人数，报名费180，交材料给学姐看，身份证和学历复印件上交，填表选导师，是否同意调剂导师，是否同意自费，只有7成公费名额火车没睡好，我报名以后直接回酒店休息，晚上去交表格，了解情况原来想报名导师比较火我就换了位导师，如果初试成绩好，数学和英文高的话可以拼一拼，英语50以上，数学100以上的同学，统考的话也有优势，个人感觉统考应该加20分来对比非408的第二天上午九点笔试出乎意料，直接考了数据结构，初试没考的就杯具通知是说考c语言……对于学校笔试你最好主要课程都准备1 已知后序和中序求先序2 知道一向量组，构造有序单链表时间复杂度3 快速排序一趟结果4 单插入节点过程5 希尔排序取步长特点递减6 循环队列长度78前8个选择题，最后2个不记得了。
下面出的综合题，画图为主。
1 给出图的邻接矩阵，最小生成树2 冒泡排序过程3 8皇后写算法4 周游遍历代价最小5 堆调整算法6 拓扑排序题目比较基础，考过408的90分左右，应该无压力下午2点40开始面试，分了4组我这组6个老师，自己老师来考察你的情况，自我介绍3分钟，中英都可文基本没问什么，了解基本情况，如跨考的会多问了一些，比如数组指针和指针数组的差别，我自我介绍的时候有提到概率论，我导师直接问，中心极限定理和大数定理怎么理解的综合排分取前50名，包括了保送一志愿8人体检我在第三天才去，不用排队的，20分钟全搞定。
一、填空题（一空5分，共70分）1.如果每次运行环境只能执行一条语句,但是有许多语句需要执行,那么_______,构成_________2.标识符的作用域_________、_________、________、________、________3.用字符串“schedule”初始化一个字符数组的初始化语句________、_______、__________4.哪几个运算符必须重载为成员函数________、________、_________、________二、简答题（60分）1．什么是“else摇摆问题”，举例说明（10分）2．函数模板和函数重载的区别与联系（10分）3．怎样区别虚函数和纯虚函数？两者都有什么作用（20分）4．面向对象程序“接口与实现方法分离”，有什么优点（10分）5．列出所有与字符串处理有关的头文件（10分）三、编程题（20分）格式转换，从一个文件中读取日期07/21/2016，转换为以下格式July 21,2016并输出到屏幕上参考答案：（不保证正确性）填空1 用花括号{}括起来块语句（或者复合语句）2 块作用域（局部作用域）文件作用域（全局作用域）函数原型作用域函数作用域类作用域3 char s[] = “Schedual”; char s[] = {‘S’,’c’,’h’,’e’,’d’,’u’,’a’,’l’,’\0’};char s[] = {“Schedual”};4 = () [] ->简答1if (a>0)if (b>0)…else…这里的else应该与第二个if匹配而非第一个2用同一函数名定义多个函数，这些函数的参数个数和参数类型不同，这就是函数重载。
重载函数的参数个数、参数类型或参数顺序3者中必须至少有一种不同，函数返回值类型可以相同也可以不同。
函数模板实际上是建立一个通用函数，其函数类型和形参类型不具体指定，用一个虚拟的类型来代表。
2017年硕士学位研究生招生复试上机试题考试科目： C语言与数据结构算法上机测试考试时间120分钟注意事项：1、源程序都在D:\TEST文件夹下，请先将该“TEST”文件夹改名为“准考证号_姓名”，其中准考证号是初试时的15位准考证号；2、考试结束后，首先删除VC++ 6.0自动生成的debug文件夹，然后使用压缩软件将上述考生文件夹中所有内容打包（包括里面所有文件，比如工程文件等。
除上述debug文件夹外，不得删除任何考试过程中产生的文件），文件名为“准考证号_姓名.rar”，然后将该文件通过教学系统的学生端的“传文件给教师”功能上传到服务器。
注意：文件上传后，需到监考老师处确认方可离开考场。
如果未经监考老师确认，并且文件由于某种原因上传未成功，考试成绩以0分计。
3、如果已经上传，需要修改然后再上传的，在压缩包的文件名后加编号2、3、4等，形如：“考号_姓名2.rar”、“考号_姓名3.rar”。
在监考老师处确认时，请求监考老师将老文件删除。
4、所有提供的文件（包括C源文件），不得更改文件名，也不得更改其内部结构（详见题目中的红字）。
5、所有程序需要在VC++6.0环境中运行，结果正确方可。
比如，程序填空，不能仅将空填好，而是需要运行程序，进行测试，确保正确。
6、本考试共包括1道程序改错、2道程序填空、3道程序编写题，分数分别为：20、 15、 15、 15、15、20。
7、考试题文字描述见下，C程序见考生文件夹下相应文件。
(1) 给定程序modi.c中，函数fun的功能是：用下面的公式求π的近似值，直到最后一项的绝对值小于指定的数（参数num）为止(该项不包括在结果中)：例如，程序运行后，输入0.0001，则程序输出3.1414。
请改正程序中的错误，使它能得出正确结果。
注意：不要改动main函数，不得增行或删行，也不得更改程序的结构！(2) 给定程序blank1.c中，函数fun的功能是：找出100至x（x≤999）之间各位上的数字之和为15的所有整数，然后输出；符合条件的整数个数作为函数值返回。
例如，当x值为500时，各位数字之和为15的整数有：159、168、177、186、195、249、258、267、276、285、294、339、348、357、366、375、384、393、429、438、447、456、465、474、483、492。
共有26个。
所以，程序运行后，输入500，则输出 The result is: 26。
请在程序的下划线处填入正确的内容并把下划线删除，使程序得出正确的结果。
注意：不得增行或删行，也不得更改程序的结构！(3) 给定程序blank2.c中，函数fun的功能是将a和b所指的两个字符串转换成面值相同的整数，并进行相加作为函数值返回，规定字符串中只包含数字字符。
例如，主函数main中输入字符串：32486和12345，在主函数中输出的函数值为：44831。
请在程序的下划线处填入正确的内容并把下划线删除，使程序得出正确的结果。
注意：不得增行或删行，也不得更改程序的结构！(4) 有n（n很大）个范围为0~32767数字，其中有大量重复的数，在main函数中已读入到data 数组中，请编写函数fun，计算剔除重复数字之后，还剩下几个数。
fun函数的功能是：传入两个形参，一个是数组data，一个是n的值，经过计算，返回剔除重复数字后剩下的数字的个数。
比如，程序运行时输入：51 1 3 1 3则程序输出：2要求：请衡量时间复杂度和空间复杂度，尽量设计高效算法。
请在prog1.c最前面的注释部分介绍自己的算法。
注意：部分源程序存在文件prog1.c中。
请勿改动主函数main和其他函数中的任何内容，仅在函数fun的花括号中填入你编写的若干语句。
(5)计算所需要最少拦截系统的数目：某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。
但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能达到前一发的高度。
某天，雷达捕捉到敌国的导弹来袭，如果系统数量太少，将导致有可能不能拦截所有的导弹。
所以，根据雷达捕捉到的导弹高度（导弹总数目不超过1000），需要预先准备相应数量的拦截系统。
比如导弹的高度依次为：5 3 4 2 4 1则一个拦截系统的第一发炮弹必须打到高度5的地方，第二发炮弹打到高度3的地方。
但第三发炮弹打不到高度4的地方（因为每一发炮弹不能达到前一发的高度），所以要使用第二套拦截系统。
第二套拦截系统发射的炮弹高度打到4和2的高度(实际上,要拦截高度为2的炮弹,使用第一套拦截系统或者第二套都可以)。
第三套拦截系统发射的炮弹高度打到4和1的高度(实际上,要拦截高度为1的炮弹,三套拦截系统都可以)。
因此，总共需要三套拦截系统。
再比如导弹的高度依次为：5 3 4 2 3 1则一个拦截系统的第一发炮弹必须打到高度5的地方，第二发炮弹打到高度3的地方。
但第三发炮弹打不到高度4的地方（因为每一发炮弹不能达到前一发的高度），所以要使用第二套拦截系统。
第二套拦截系统发射的炮弹高度打到4的高度。
再要拦截高度为2的炮弹,使用第一套拦截系统或者第二套都可以，但考虑到后面还需要拦截炮弹，我们这里使用第一套拦截系统（为什么不能用第二套，自己想啦）。
再要拦截高度为3的炮弹,我们使用第二套拦截系统。
再拦截高度为1的炮弹，第一套和第二套系统都可以，我们使用第一套。
因此，总共仅需要两套拦截系统，第一套拦截的是5 3 2 1，第二套拦截的是4 3。
请根据给定的高度数据，帮助计算一下最少需要多少套拦截系统。
在main函数中，首先输入n，表示共有n个导弹，然后读入导弹的高度到数组a中。
fun函数接受a数组和n两个参数，计算需要的拦截系统的数目，并返回该结果。
请完成fun 函数。
比如，程序运行时输入：65 3 4 2 3 1则程序输出：“The number is: 2”注意：部分源程序存贮在文件prog2.c中。
请勿改动主函数main和其它函数中的任何内容，仅在函数fun的花括号中填入你编写的若干语句。
（6）从数据结构中树的定义可知，除根结点外，树中的每个结点都有唯一的一个双亲结点。
根据这一特性，可用一组连续的存储空间（一维数组）存储树中的各结点。
树中的结点除保存结点本身的信息之外，还要保存其双亲结点在数组中的位置（即在数组中的下标。
双亲的信息为-1则表示该结点为根结点），树的这种表示法称为双亲表示法。
树的每个结点的数据类型定义如下：struct PTNode{char data; //结点数据域int parent; //结点双亲在数组中的位置};树的数据类型定义如下：#define MAX_TREE_SIZE 100struct PTree{struct PTNode nodes[MAX_TREE_SIZE]; //存储树中所有结点int n; //树中共有n个结点，n不超过100};则下图1所示的树，按照双亲表示法存储结构，存储为图2所示形式（n为10）。
序号 data parent图1 树的示意图图2 双亲表示法存储已知一棵树已存储为以上形式，请编写函数GetNearestCommonGrand，查找给定的两个（不相同的）结点最近的共同祖先。
GetNearestCommonGrand的函数原型为：char GetNearestCommonGrand(struct PTree T, char nodeData1, char nodeData2) 函数形参：T：保存了树中结点数目及图2所示的结点数组nodeData1,nodeData2：给定的两个结点的数据（输入时保证这两个结点存在）。
函数返回值：两个结点最近的共同祖先。
比如，nodeData1为’G’,nodeData2为’H’,则函数返回’A’。
说明：输入保证nodeData1和nodeData2在树中能找到。
部分代码在prog3.c中，请仅在GetNearestCommonGrand函数中填入内容，完成程序。
要求：尽量优化算法的时间复杂度与空间复杂度，并在GetNearestCommonGrand函数前的注释部分简要介绍自己的算法，同时指出该算法具有什么样的时间复杂度与空间复杂度。
请勿改动主函数main和其它已有函数中的任何内容，可以在函数GetNearestCommonGrand的花括号中填入你编写的若干语句，允许增加自定义函数。
prog3.c中，struct PTree CreateTree()函数用于从键盘输入树的双亲表示法的信息，创建一棵树。
输入的第一个数n表示树中结点数，此后有n行输入，每行表示一个结点的信息，其中第一个信息为结点的数据，第二个信息为结点的双亲结点在数组中的位置。
在main函数中还需要输入两个结点的字符数据，查询这两个结点的最近共同祖先。
如输入（第一行为n，表示共有10个结点，后面10行，为10个结点的信息，最后一行为g和h，表示查询结点g和结点h的最近共同祖先）：10a -1b 0c 0d 0e 1f 1g 1h 2i 3j 3g h则将创建图b所对应的树。
输出结果为’a’如输入：8a -1b 0e 1h 6c 0d 0f 5g 5g h输出结果为’d’。
