四川大学生命科学学院 计算机基础历年考研真题汇编

一、单项选择题1-40小题，每小题2分，共80分。

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

1 【正确答案】 D【试题解析】考查限定条件的出栈序列。

A可由in，jn，jn，in，out，out，in，out，out，in，out，out得到；B可由in，in，in，out，out，in，out，out，in，out，in，out得到；C可由in，in，out，in，out，out，in，in，out，in，out，out得到；D可由in，out，in，in，in，in，in，out，out，out，out，out得到，但题意要求不允许连续三次退栈操作，故D错。

2 【正确答案】 C【试题解析】考查受限的双端队列的出队序列。

A可由左入，左入，右入，右入，右入得到；B可由左入，左入，右入，左入，右入得到；D可由左入，左入，左入，右入，左入得到。

所以不可能得到C。

3 【正确答案】 D【试题解析】考查线索二叉树的基本概念和构造。

题中所给二叉树的后序序列为dbca。

结点d无前驱和左子树，左链域空，无右子树，右链域指向其后继结点b：结点b无左子树，左链域指向其前驱结点d：结点c无左予树，左链域指向其前驱结点b，无右子树，右链域指向其后继结点a。

4 【正确答案】 C【试题解析】考查平衡二叉树的插入算法。

插入48以后，该二叉树根结点的平衡因子由一1变为一2，失去平衡，需进行两次旋转(先右旋后左旋)操作。

5 【正确答案】 B【试题解析】考查树结点数的特性。

设树中度为i(i=0，1，2，3，4)的结点数分别为Nj，树中结点总数为N，则树中各结点的度之和等于N—1，即N=1+N1+2N2+3N3+4N4=N0+N1+N2+N3+N4，根据题设中的数据，即可得到N0=82，即树T的叶结点的个数是82。

6 【正确答案】 A【试题解析】考查赫夫曼树的特性。

赫夫曼树为带权路径长度最小的二叉树，不一定是完全二又树。

一、单项选择题1-40小题，每小题2分，共80分。

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

1 【正确答案】 B【试题解析】考查栈和队列的特点及应用。

C和D直接排除，缓冲区的特点需要先进先出，若用栈，先进入缓冲区的数据则要排队到最后才能打印，不符题意，故选B。

2 【正确答案】 C【试题解析】考查栈的最大递归深度。

时刻注意栈的特点是先进后出。

出入栈的详细过程见表A-3。

栈内的最大深度为3，故栈S的容量至少是3。

3 【正确答案】 D【试题解析】考查二叉树的特殊遍历。

分析遍历后的结点序列，可以看出根结点是在中间被访问的，而右子树结点在左子树之前，得遍历的方法是RNL。

本题考查的遍历方法并不是二叉树的三种基本遍历方法，对于考生而言，重要的是要掌握遍历的思想。

4 【正确答案】 B【试题解析】考查平衡二叉树的定义。

根据平衡二叉树的定义有，任意结点的左、右子树高度差的绝对值不超过1。

而其余三个答案均可以找到不符合的结点。

5 【正确答案】 C【试题解析】考查完全二叉树的特点。

完全二叉树比满二叉树只是在最下面一层的右边缺少了部分叶结点，而最后一层之上是个满二叉树，并且只有最后两层有叶结点。

第6层有叶结点则完全二叉树的高度可能为6或7，显然树高为7时结点更多。

若第6层上有8个叶结点，则前六层为满二叉树，而第7层缺失了8×2=16个叶结点，故完全二叉树的结点个数最多为27一1-16=111个结点。

6 【正确答案】 B【试题解析】考查森林和二叉树的转换。

森林与二叉树的转换规则为“左孩子右兄弟”。

在最后生成的二叉树中，父子关系在对应森林关系中可能是兄弟关系或原本就是父子关系。

情形I：若结点v是结点u的第二个孩子结点，在转换时，结点v就变成结点u第一个孩子的右孩子，符合要求。

情形Ⅱ：结点u和v是兄弟结点的关系，但二者之中还有一个兄弟结点k，则转换后，结点v就变为结点k的右孩子，而结点k则是结点u的右孩了，符合要求。

2024年研究生考试考研计算机学科专业基础(408)自测试卷(答案在后面)一、单项选择题（本大题有40小题，每小题2分，共80分）1、在计算机网络中，TCP协议工作在哪一层？A. 物理层B. 数据链路层C. 网络层D. 传输层2、假设有一个采用补码表示的8位寄存器，如果该寄存器的内容是10000000，则其对应的十进制数值是多少？A. -127B. -128C. 0D. 1283、以下哪项不是数据库事务应满足的ACID特性之一？A. 原子性B. 一致性C. 隔离性D. 持久性E. 可用性4、在计算机系统中，以下哪种存储器属于随机存取存储器（RAM）？A、只读存储器（ROM）B、光盘存储器C、硬盘存储器D、动态随机存取存储器（DRAM）5、下列哪个选项描述了编译器的功能？A、将汇编语言翻译成机器语言B、将高级语言翻译成机器语言C、将机器语言翻译成高级语言D、将二进制代码转换成源代码6、在数据结构中，以下哪种数据结构可以实现高效的查找操作？A、链表B、数组C、栈D、哈希表7、在下列寻址方式中，哪种寻址方式需要两次访问内存？A. 直接寻址B. 立即数寻址C. 寄存器间接寻址D. 基址变址寻址8、设有3个作业J1、J2、J3，它们的到达时间和运行时间如下表所示。

若采用短作业优先(SJF)调度算法，则这3个作业的平均等待时间是多少？作业到达时间运行时间J106J224J342A. 6B. 8C. 10D. 129、下面关于虚拟存储器的说法，哪个是正确的？A. 虚拟存储器允许程序访问比主存更大的地址空间。

B. 虚拟存储器可以完全避免碎片问题。

C. 虚拟存储器的实现不需要硬件支持。

D. 虚拟存储器中所有页面都在内存中。

10、计算机网络的OSI七层模型中，负责处理数据传输的层次是：A. 应用层B. 表示层C. 会话层D. 传输层13、在某计算机系统中，若一个文件的物理结构采用链接结构存储，则下列说法正确的是：A. 适合于随机存取B. 存储空间利用率高，但不支持随机访问C. 不利于文件长度动态增长D. 文件的逻辑记录不必连续存放16、在计算机科学中，下列哪个术语描述了一个由有限个状态组成的模型，用于描述有限个输入的序列，并产生输出？A. 有限自动机B. 状态机C. 数据结构D. 程序19、关于操作系统中的进程状态转换，以下哪个选项是正确的？A. 进程从就绪状态直接转换为阻塞状态B. 进程从运行状态直接转换为就绪状态C. 进程从阻塞状态直接转换为运行状态D. 进程从创建状态直接转换为运行状态22、在计算机科学中，以下哪种排序算法的平均时间复杂度是O(nlogn)？A. 冒泡排序B. 快速排序C. 插入排序D. 选择排序25、在计算机系统中，以下哪个设备通常用于存储大量数据？A. 硬盘驱动器（HDD）B. 光驱C. 显卡D. CPU28、以下关于C++中虚函数和纯虚函数的说法，正确的是（）A. 虚函数一定有函数体，纯虚函数必须有函数体B. 纯虚函数可以出现在类中，但不能被实例化C. 虚函数只能在派生类中重写，纯虚函数只能在基类中重写D. 虚函数和纯虚函数都是成员函数，都可以在类定义中给出函数体31、在计算机网络中，以下哪个协议是用于传输电子邮件的？A. HTTPB. FTPC. SMTPD. TCP34、以下关于数据结构中二叉搜索树的描述，错误的是：A. 二叉搜索树是一种特殊的二叉树，其中每个节点都有一个关键字。

一、单项选择题1-40小题，每小题2分，共80分。

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

1 设n是描述问题规模的非负整数，下面程序片段的时间复杂度是____。

x：2：while(x<n／2)x=2*x：（A）O(log2n)（B）O(n)（C）O(nlog2n)（D）O(n2)2 元素a，b，c，d，e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是____。

（A）3（B）4（C）5（D）63 已知循环队列存储在一维数组A[0…n一1]中，且队列非空时front和rear分别指向队头元素和队尾元素。

若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是____。

（A）0，0（B）0，n一1（C）n—1，0（D）n一1，n—14 若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（A）257（B）258（C）384（D）3855 若一棵二叉树的前序遍历序列和后序遍历序列分别为1，2，3，4和4，3，2，1，则该二又树的中序遍历序列不会是____。

（A）1，2，3，4（B）2，3，4，1（C）3，2，4，1（D）4，3，2，16 已知一棵有2011个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点个数是____。

（A）115（B）116（C）1895（D）18967 对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是____。

（A）95，22，91，24，94，71（B）92，20，91，34，88，35（C）2l，89，77，29，36，38（D）12，25，71，68，33，348 下列关于图的叙述中，正确的是____。

I．回路是简单路径Ⅱ．存储稀疏图，用邻接矩阵比邻接表更省空间Ⅲ．若有向图中存在拓扑序列，则该图不存在回路（A）仅Ⅱ（B）仅I、Ⅱ（C）仅Ⅲ（D）仅I、Ⅲ9 为提高散列(Hash)表的查找效率，可以采取的正确措施是____。

四川大学大学计算机基础期末考试试卷07-08一、单项选择题（共40小题，每题1分，共40分）1) 下列关于世界上第一台电子计算机ENIAC的叙述中，错误的是A) 它是1946年在美国诞生的B) 它主要采用电子管和继电器C) 它是首次采用存储程序控制使计算机自动工作D) 它主要用于弹道计算2) 1946年首台电子数字计算机ENIAC问世后，冯·诺依曼(V on Neumann)在研制EDV AC计算机时，提出两个重要的改进，它们是A) 引入CPU和内存储器的概念B) 采用二进制和存储程控制的概念C) 采用机器语言和十六进制D) 采用ASCII编码系统3) 第三代计算机采用的电子元件是A) 晶体管B) 中、小规模集成电路C) 大规模集成电路D) 电子管4) 下列不属于计算机特点的是A) 存储程序控制，工作自动化B) 具有逻辑推理和判断能力C) 处理速度快、存储量大D) 不可靠、故障率高5) 电子计算机的最早的应用领域是A) 数据处理B) 数值计算C) 工业控制D) 文字处理6) 机器人是计算机在哪方面的应用？A) 自动控制B) 计算机辅助设计C) 数据处理D) 人工智能7) 计算机技术中，下列的英文缩写和中文名字的对照中，正确的是A) CAD——计算机辅助制造B) CAM——计算机辅助教育C) OS——操作系统D) CAI——计算机辅助设计8) 下面关于“计算机系统”的叙述中，最完整的是A) “计算机系统”就是指计算机的硬件系统B) “计算机系统”是指计算机配置的操作系统C) “计算机系统”由硬件系统和安装在其上的操作系统组成D) “计算机系统”由硬件系统和软件系统组成9) 冯·诺依曼(V on Neumann)型体系结构的计算机硬件系统的五大部件是A) 输入设备、运算器、控制器、存储器、输出设备B) 键盘和显示器、运算器、控制器、存储器和电源设备C) 输入设备、中央处理器、硬盘、存储器和输出设备D) 键盘、主机、显示器、硬盘和打印机10) 下列叙述中，错误的是A) 计算机硬件主要包括：主机、键盘、显示器、鼠标器和打印机五大部件B) 计算机软件分系统软件和应用软件两大类C) CPU主要由运算器和控制器组成D) 内存储器中存储当前正在执行的程序和处理的数据11) 通常所说的微机的主机是指A) CPU和内存B) CPU和硬盘C) CPU、内存和硬盘D) CPU、内存与CD-ROM12) 用来控制、指挥和协调计算机各部件工作的是A) 运算器B) 鼠标器C) 控制器D) 存储器13) 下列关于CPU的叙述中，正确的是A) CPU能直接读取硬盘上的数据B) CPU能直接与内存储器交换数据C) CPU主要组成部分是存储器和控制器D) CPU主要用来执行算术运算14) CPU主要技术性能指标有A) 字长、运算速度和时钟主频B) 可靠性和精度C) 耗电量和效率D) 冷却效率15) 在现代的CPU芯片中又集成了高速缓冲存储器(Cache)，其作用是A) 扩大内存储器的容量B) 解决CPU与RAM之间的速度不匹配问题C) 解决CPU与打印机的速度不匹配问题D) 保存当前的状态信息16) 随机存储器中，有一种存储器需要周期性的补充电荷以保证所存储信息的正确，它称为A) 静态RAM[SRAM] B) 动态RAM[DRAM]C) RAM D) Cache17) 下列说法中，正确的是A) 硬盘的容量远大于内存的容量B) 硬盘的盘片是可以随时更换的C) 优盘的容量远大于硬盘的容量D) 硬盘安装在机箱内，它是主机的组成部分18) 当前流行的移动硬盘或优盘进行读/写利用的计算机接口是A) 串行接口B) 并行接口C) USB D) UBS19) 目前市售的USB FLASH DISK(俗称优盘)是一种A) 输出设备B) 输入设备C) 存储设备D) 显示设备20) 下列关于CD-R光盘的描述中，错误的是A) 只能写入一次，可以反复读出的一次性写入光盘B) 可多次擦除型光盘C) 以用来存储大量用户数据的，一次性写入的光盘D) CD-R是Compact Disc Recordable的缩写21) 下列关于磁道的说法中，正确的是A) 盘面上的磁道是一组同心圆B) 由于每一磁道的周长不同，所以每一磁道的存储容量也不同C) 盘面上的磁道是一条阿基米德螺线D) 磁道的编号是最内圈为0，并依次由内向外逐渐增大，最外圈的编号最大22) 磁盘的存取单位是A) 柱面B) 磁道C) 扇区D) 字节23) 1GB的准确值是A) 1024×1024Bytes B) 1024KBC) 1024MB D) 1000×1000 KB24) 下列关于软件的叙述中，错误的是A) 计算机软件系统由程序和相应的文档资料组成B) Windows操作系统是最常有的系统软件之一C) Word 2003就是应用软件之一D) 软件具有知识产权，不可以随便复制使用的25) 下列叙述中，错误的是A) 把数据从内存传输到硬盘的操作称为写盘B) WPS Office 2003属于系统软件C) 把源程序转换为等价的机器语言目标程序的过程叫编译D) 计算机内部对数据的传输、存储和处理都使用二进制26) 字长是CPU的主要性能指标之一，它表示A) CPU一次能处理二进制数据的位数B) 最长的十进制整数的位数C) 最大的有效数字位数D) 计算结果的有效数字长度27) 已知三个字符为：a、Z和8，按它们的ASCII码值升序排序，结果是A) 8，a，Z B) a，8，ZC) a，Z，8 D) 8，Z，a28) 在标准ASCII码表中，已知英文字母D的ASCII码是0100 0100，英文字母B的ASCII码是A) 0100 0001 B) 0100 0010C) 0100 0011 D) 0100 000029) 汉字输入码可分为有重码和无重码两类，下列属于无重码类的是A) 全拼码B) 自然码C) 区位码D) 简拼码30) 已知“装”字的拼音输入码是“zhuang”，而“大”字的拼音输入是“da”，它们的国际码的长度的字节数分别是A) 6，2 B) 3，1C) 2，2 D) 4，231) 下面关于操作系统的叙述中，正确的是A) 操作系统是计算机软件系统的核心软件B) 操作系统属于应用软件C) Windows是PC机惟一的操作系统D) 操作系统的五大功能是：启动、打印、显示、文件存取和关机32) 下列各指标中，数据通信系统的主要技术指标之一的是A) 误码率B) 重码率C) 分辨率D) 频率33) 一台微型计算机要与局域网连接，必需安装的硬件是A) 集线器B) 网关C) 网卡D) 路由器34) 在因特网上，一台计算机可以作为另一台主机的远程终端，使用该主机的资源，该项服务称为A) Telnet B) BBS C) FTP D) WWW35) 在E-R图中，用来表示实体之间联系的图形是A) 矩形B) 椭圆形C) 菱形D) 平行四边形36) 在现实世界中，每个人都有自己的出生地，实体“人”与实体“出生地”之间的联系是A) 一对一联系B) 一对多联系C) 多对多联系D) 无联系37) 软件调试的目的是A) 发现错误B) 改正错误C) 改善软件的性能D) 验证软件的正确性38) 算法具有五个特性，以下选项中不属于算法特性的是A) 有穷性B) 简洁性C) 可行性D) 确定性39) 下列描述中，错误的是A) 多媒体技术具有集成性和交互性等特点B) 所有计算机的字长都是固定不变的，是32位C) 通常计算机的存储容量越大，性能就越好D) 各种高级语言的翻译程序都属于系统软件40) 以下关于防火墙技术的描述中，错误的是A) 可以对进出内部网络的分组进行过滤B) 可以布置在企业内部网和因特网之间C) 可以查、杀各种病毒D) 可以对用户使用的服务进行控制二、填空题（共30小题，每空1分，共30分）1) 在计算机内部用来传送、存储、加工处理的数据或指令所采用的形式是【1】。

一、单项选择题1-40小题，每小题2分，共80分。

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

1 【正确答案】 C2 【正确答案】 B3 【正确答案】 A4 【正确答案】 D5 【正确答案】 C6 【正确答案】 D7 【正确答案】 D8 【正确答案】 D9 【正确答案】 D10 【正确答案】 B11 【正确答案】 C12 【正确答案】 D13 【正确答案】 C14 【正确答案】 A15 【正确答案】 A16 【正确答案】 D17 【正确答案】 A18 【正确答案】 C19 【正确答案】 C20 【正确答案】 C21 【正确答案】 D22 【正确答案】 B23 【正确答案】 A24 【正确答案】 B25 【正确答案】 D26 【正确答案】 A27 【正确答案】 A28 【正确答案】 C29 【正确答案】 B30 【正确答案】 A31 【正确答案】 C32 【正确答案】 D33 【正确答案】 C34 【正确答案】 B35 【正确答案】 D36 【正确答案】 C37 【正确答案】 B38 【正确答案】 A39 【正确答案】 B40 【正确答案】 D二、综合应用题41-47小题，共70分。

41 【正确答案】算法的基本设计思想：①基于先序递归遍历的算法思想是用一个static变量记录wpl，把每个结点的深度作为递归函数的一个参数传递，算法步骤如下：若该结点是叶子结点，那么变量wpl加上该结点的深度与权值之积；若该结点非叶子结点，那么若左子树不为空，对左子树调用递归算法，若右子树不为空，对右子树调用递归算法，深度参数均为本结点的深度参数加1；最后返回计算出的wpl即可。

②基于层次遍历的算法思想是使用队列进行层次遍历，并记录当前的层数，当遍历到叶子结点时，累计wpl；当遍历到非叶子结点时对该结点的把该结点的子树加入队列；当某结点为该层的最后一个结点时，层数自增1；队列空时遍历结束，返回wpl。

42 【正确答案】二叉树结点的数据类型定义如下：typedef struct BiTNode{int weight；struct BiTNode *lchild，*rchild；}BiTNode，*BiTree。

2018年攻读硕士学位研究生入学考试试题考试科目:计算机科学专业基础综合科目代码:874（试题共8页）（答案必须写在答题纸上，写在试题上不给分）数据结构与算法（65分）一、单项选择题（每小题2分，共17小题，共34分1.下面关于“算法”的描述，错误的是（）A.算法必须是正确的B.算法必须要能够结束C.一个问题可以有多种算法解决D.算法的某些步骤可以有二义性2.下面函数的时间复杂度是（）void func(int n){int sum＝0,i, j;for(i＝1; i<n; i++)for(j＝1; j<n; j*＝2)sum++;A.O(log2n)B.O(n2)C.(n log2n)D.O(n)3.下面关于线性表的叙述中，错误的是（）A.线性表采用顺序存储，必须占用一片连续的存储单元B.执行查找操作时，链式存储比顺序存储的查找效率更高。

C.线性表采用链式存储，不必占用一片连续的存储单元。

D.线性表采用链式存储，便于插入和删除操作。

4.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（）最节省时间A.单链表B.带头指针的单循环链表C.带尾指针的单循环链表D带头结点的双循环链表5.一个栈的输入序列为1，2，3，....，n，若输出序列的第一个元素是n，则输出的第i (1<=i<=n)个元素是（）A.不确定B.n-i+1C.iD.n-i6.若一棵完全二叉树有666个结点，则该二叉树中叶子结点的个数是（）A.156B.155C.333D.3347.对于下列关键字序列，不可能构成某二叉查找树中一条查找路径的序列是（）A.99，28，86，36，94，65B.97，18，89，34，76，42C.16，91，68，29，33，50D.21，27，80，76，29，398.下述二叉树中，哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序（）A.二叉查找树B.哈夫曼树C.AVL树D.堆9.在右图的AVL树中插入关键字18后得到一棵新AVL树，在新AVL树中，关键字11所在结点的左、右孩子结点中保存的关键字分别是（）A.7，16 C.9，26B.9，18 D.7，1810.将一棵树T1转化为对应的二叉树T2，则T1后序遍历序列是T2的（）序列A.前序遍历B.中序遍历C.后序追历D.层次遍历11.当各边上的权值（）时，BFS算法可用来解决单源最短路径问题A.均相等B.均互不相等C.较小D.以上都不对12.已知有向图G=(V,E)，其中V={V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>}，则G的一个拓扑序列（）A.V1，V3，V2，V6，V4，V5，V7B.V1，V3，V4，V6，V2，V5，V7C.V1，V3，V4，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V713.采用Kruskal算法求右图的最小生成树时，依次选择的边是（）A.(a,b)(b,c)(c,d)(d,f)(a,e)B.(d,f)(c,d)(b,c)(a,b)(a,e)C.(a,b)(b,c)(d,f)(c,d)(a,d)D.(a,b)(d,f)(b,c)(c,d)(a,e)14.设哈希表长为13，哈希函数是H（key）=key％13，表中已有关键字18，39，75，93共四个，现要将关键字为70的结点加到表中，用伪随机探测再散列法解决冲突，使用的伪随机序列为5，8，3，9，7，1，6，4，2，11，13，21则放入的位置是（A.8B.11C.7D.515.一棵高度为3的3阶B树，至少含有（）个关键字A.12B.10C.7D.都不是16.在下列排序算法中，哪一个算法的时间复杂度与数据的初始排列无关（）A.直接插入排序B.希尔排序C.快速排序D.基数排序17.数据表中有10000个元素，如果仅要求求出最大的3个元素，则采用（）算法最节省时间A.堆排序B.希尔排序C.快速排序D.直接选择排序二、综合应用题（18-20题，共31分18.（10分）对于一个字符集中具有不同权值的字符进行Huffman编码时，如果已知某个字符的Huffman 编码为0101，对于其他无字符的Huffman编码，请分析说明:（1）具有哪些特征的编码是不可能的（2）具有哪些特征的编码是一定会有的19.（10分）设有向图用邻接表表示，图有n个顶点，表示为0至n-1，试写一个算法求顶点k的入度（0＜＝k＜n）20.（11分）二叉树结点的平衡因子（bf）定义为该结点的左子树高度与右子树高度之差。

一、单项选择题1-40小题，每小题2分，共80分。

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

1 【正确答案】 A2 【正确答案】 B3 【正确答案】 D4 【正确答案】 D5 【正确答案】 D6 【正确答案】 C7 【正确答案】 A8 【正确答案】 C9 【正确答案】 C10 【正确答案】 C11 【正确答案】 A12 【正确答案】 A13 【正确答案】 B14 【正确答案】 D15 【正确答案】 C16 【正确答案】 B17 【正确答案】 B18 【正确答案】 D19 【正确答案】 C20 【正确答案】 B21 【正确答案】 B22 【正确答案】 D23 【正确答案】 B24 【正确答案】 C25 【正确答案】 D26 【正确答案】 B27 【正确答案】 A28 【正确答案】 A29 【正确答案】 B30 【正确答案】 C31 【正确答案】 C32 【正确答案】 C33 【正确答案】 D34 【正确答案】 A35 【正确答案】 B36 【正确答案】 B37 【正确答案】 A38 【正确答案】 C39 【正确答案】 A40 【正确答案】 C二、综合应用题41-47小题，共70分。

41 【正确答案】算法的基本设计思想算法的核心思想是用空间换时间。

使用辅助数组记录链表中已出现的数值，从而只需对链表进行一趟扫描。

因为｜data｜≤n，故辅助数组q的大小为n+1，各元素的初值均为0。

依次扫描链表中的各结点，同时检查q[｜data｜]的值，如果为0，则保留该结点，并令q[｜data｜]=1；否则，将该结点从链表中删除。

42 【正确答案】使用C语言描述的单链表结点的数据类型定义typedef struct node{int data；struct node*link；}NODE；Typedef NODE *PNODE。

43 【正确答案】算法实现void func (PNODE h，int n){PNODE p=h，r，int *q，m；q=(int *)malloc(sizeof(int)*(n十1))；／／申请n+1个位置的辅助空间for(int i=0，i＜n+1，i++)／／数组元素初值置0*(q+i)=0；while(p-＞link!=NULL){m=p-＞link-＞data＞0?p-＞link-＞data：-p-＞link-＞data；if(*(q+m)==0)／／判断该结点的data是否己出现过{*(q+m)=1，／／首次出现p=p-＞link；／／保留}else／／重复出现{r=p-＞link；／／删除P-＞link=r-＞finkfree(r)；}44 【正确答案】算法的时间复杂度为O(m)，空间复杂度为O(n)。

一、单项选择题1-40小题，每小题2分，共80分。

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

1 【正确答案】 B【试题解析】时间复杂度是由语句频度分析得来，递归算法中重复执行的语句主要是调用。

所以递归算法的时间复杂度分析主要是分析递归函数的调用次数，并给出调用次数的函数f(n)。

从图中可以总结出该函数被调用了n+1次。

2 【正确答案】 A【试题解析】根据题目要求，栈中只存储操作符“+”，“-”，“*”，“／”，“(”和“)”，并不存储字母，这一点一定要看清楚。

根据中缀表达式a+h—a*((c+d)／e—f)+g，可以利用栈将其转换为后缀表达式ab+acd+e／f一*一g+，在转换过程中，栈中的操作符最多有5个。

这种情况出现在第二个“+”号人栈后，栈中的操作符分别为：“一”，“*”，“(”，“(”，“+”。

3 【正确答案】 A【试题解析】根据题中给出的二叉树的前序遍历a、e、b、d、c和后序遍历b、c、d、e、a可以确定的是a为二叉树的根结点。

那么根据前序遍历的访问次序为根结点、左子树、右子树，可以确定e为左子树或右子树的根结点，即根结点的孩子结点。

假设e为左孩子结点，那么根据后序遍历的结果可知，b、e、d一定在左子树上，不可能为a的孩子结点。

若e为右子树的根结点，根据前序遍历结果可知，此二叉树没有左子树。

4 【正确答案】 B【试题解析】所有非叶结点的平衡因子均为1，说明这棵平衡二叉树的非叶子结点左子树都比右子树多一层。

因此，可以得到下一页的一个图，即次平衡二叉树上的结点总数为20。

5 【正确答案】 C【试题解析】邻接表存储的有向图进行广度优先遍历的时间复杂度与图中的顶点个数以及边数都相关，因此答案选C。

6 【正确答案】 C【试题解析】邻接矩阵存储有向图且主对角线以下的元素均为零，说明在此有向图中，l为起点，n为终点。

任何一个顶点都不能到达比其号码小的顶点。

在这种有向图中拓扑序列是存在的，但是可能唯一，也可能不唯一。

2024考研计算机科学真题及答案一、选择题（每题2分，共20分）1. 数据结构中的栈是一种（）类型的数据结构。

A. 线性结构B. 树状结构C. 图形结构D. 非线性结构答案：A2. 在计算机科学中，（）是一种基本的数据结构。

A. 数组B. 链表C. 树D. 图答案：A3. 深度优先搜索（DFS）和广度优先搜索（BFS）是两种常用的（）算法。

A. 排序算法B. 查找算法C. 图算法D. 树算法答案：C4. 在计算机网络中，IP地址用于（）。

A. 数据压缩B. 数据加密C. 数据传输D. 标识网络中的设备答案：D5. 计算机操作系统的主要功能包括（）。

A. 资源管理B. 提供用户接口C. 文件管理D. 以上都是答案：D二、填空题（每题2分，共20分）1. 在数据结构中，一个存储结构如果能够随机地访问任一元素，则称之为________。

答案：随机存取存储结构2. 哈希表是通过一个________函数将关键字映射到表的一个位置来访问记录。

答案：哈希3. 在深度优先搜索中，从根节点开始，沿着树的________方向进行搜索。

答案：深度4. OSI模型中的________层负责在网络中转发数据包。

答案：网络5. ________是一种常用的进程同步机制，用于解决多个进程访问共享资源的问题。

答案：互斥锁三、简答题（每题10分，共30分）1. 简述深度优先搜索和广度优先搜索的区别。

答案：深度优先搜索（DFS）和广度优先搜索（BFS）都是图搜索算法。

DFS从起始节点开始，一直搜索到不能再深入为止，然后回溯至上一个分叉节点继续搜索。

而BFS则是从起始节点开始，逐层搜索所有邻接节点，直到找到目标节点或遍历完所有节点。

DFS通常使用递归实现，而BFS通常使用队列实现。

2. 简述操作系统的进程管理的主要功能。

答案：操作系统的进程管理主要功能包括进程的创建、进程的调度、进程同步与互斥、进程通信以及进程的终止。

进程创建涉及创建进程、初始化进程数据结构等；进程调度则是根据某种策略决定哪个进程获得CPU时间；进程同步与互斥用于解决多个进程访问共享资源的问题；进程通信提供进程间数据交换的机制；进程终止则涉及清理进程资源、释放内存等。

2007年攻读硕士学位研究生入学考试试题一、判断并改正。

1．主存中出现零头的主要原因是没有打破程序物理连续性的限制。

2．分时系统中，当一个进程用完一个时间片，它的状态由运行变为阻塞。

错误，状态由运行变为就绪。

就绪→进程调度→执行执行→时间片完→就绪执行→I/O请求→阻塞阻塞→I/O完成→就绪3．按优先数调度算法，处于运行状态的进程一定是所有进程优先级最高的进程。

正确。

4．系统采用虚拟设备能有效的提高I/O速度。

正确。

补充知识：虚拟设备是指通过某种虚拟技术将一台物理设备变换成若干逻辑设备，从而实现多个用户对该物理设备的同时共享。

由于多台逻辑设备实际上并不存在，而只是给用户的一种感觉，因此被称作虚拟设备。

SPOOLing技术，在联机情况下同时实现外围操作的技术，或称为假脱机技术。

SPOOLing系统的特点：（1）提高I/O的速度（2）将独占设备改为共享设备（3）实现了虚拟设备功能。

5．在虚拟存储系统中，只要外存磁盘空间足够大，虚拟存储器就可以设计任意大的编址空间。

错误，其逻辑容量由逻辑地址以及内存和外存容量之和决定。

6．文件的存取方式与文件的物理组织结构无关。

错误。

补充知识：文件的物理结构，又称文件的存储结构，是指文件在外存上的存储组织形式。

这不仅与存储介质的存储性能有关，而且与所采用的外存分配方式有关。

7．设备驱动程序是I/O进程与设备控制器之间的通信程序。

正确。

补充知识：设备处理程序通常又称为设备驱动程序，它是I/O设备与设备控制器之间的通信程序，又由于它常以进程的形式存在，故以后就简称之为设备驱动进程。

二、简答。

1．操作系统支持进程之间通信的机制有哪些？请至少举出三种进程通信方式，并简要说明其通信原理。

答：操作系统支持进程之间通信的机制有有三大类：共享存储系统、消息传递系统和管道通信。

2．银行家算法可以预防死锁吗？为什么？答：不能，但可以避免死锁3．在请求分页存储管理系统中，为什么要专门设置缺页中断机构，而不是直接用CPU的中断机制识别缺页中断？答：在请求分页系统中，每当所要访问的页面不在内存时，便产生一缺页中断，请求OS将所缺之页调入内存。

2024年研究生考试考研计算机学科专业基础(408)复习试题及解答一、单项选择题（本大题有40小题，每小题2分，共80分）1、在计算机网络中，路由器的主要作用是（）。

A. 资源共享B. 数据转发C. 分布式处理D. 负载均衡答案：B解析：路由器是连接两个或多个网络的硬件设备，在网络间起网关的作用。

路由器的主要功能就是进行路由选择和数据包的转发，即选择最佳的路径，将数据包从一个网络转发到另一个网络。

因此，选项B“数据转发”是路由器的主要作用。

选项A“资源共享”是计算机网络的主要功能之一，但不是路由器的主要作用；选项C“分布式处理”是计算机网络中分布式系统的一个特点，与路由器的主要功能不符；选项D“负载均衡”是路由器可能具备的一种功能，但不是其主要作用。

2、在关系数据库中，若关系R和S具有相同的属性个数，且对应的属性取自同一个域，则R与S的并集是由属于R或属于S的元组组成的集合，其结果关系（）。

A. 仍属于RB. 仍属于SC. 既属于R又属于SD. 既不属于R也不属于S答案：D解析：在关系数据库中，若两个关系R和S具有相同的属性个数，且对应的属性取自同一个域，则它们可以进行并集操作。

R与S的并集是由属于R或属于S（或两者都属于）的元组组成的集合。

然而，这个并集的结果关系并不直接属于R或S，因为并集操作会生成一个新的关系，它可能包含R和S中所有的元组，也可能只包含部分元组（如果R和S有共同的元组，则这些元组在并集中只会出现一次）。

因此，选项D“既不属于R也不属于S”是正确的。

3、在C语言中，若有以下定义和语句：int a[10]={1,2,3,4},p=a;p++;则p的值是（）。

A. 1B. 2C. 3D. 4答案：B解析：在C语言中，数组名代表数组首元素的地址。

因此，int a[10]={1,2,3,4},p=a; 这行代码定义了一个整型数组a，并初始化了前四个元素为1、2、3、4，然后定义了一个整型指针p，并将它初始化为指向数组a的首元素。