内蒙古大学计算机学院《893数据结构与操作系统(自命题)》历年考研真题专业课考试试题

2022年内蒙古农业大学数据科学与大数据技术专业《计算机系统结构》科目期末试卷B(有答案）一、选择题1、从计算机系统结构上讲，机器语言程序员所看到的机器属性是（）A.计算机软件所要完成的功能B.计算机硬件的全部组成C.编程要用到的硬件组织D.计算机各部件的硬件实现。

2、在操作系统机器级，一般用（）程序（）作业控制语句。

A.汇编程序，翻译B.汇编程序，解释C.机器语言，解释D.机器语言，翻译3、与流水线最大吞吐率高低有关的是( )A.各个子过程的时间B.最快子过程的时间C.最慢子过程的时间D.最后子过程的时间4、计算机系统多级层次中，从下层到上层，各级相对顺序正确的应当是（）。

A.汇编语言机器级，操作系统机器级，高级语言机器级B.微程序机器级，传统机器语言机器级，汇编语言机器级C.传统机器语言机器级，高级语言机器级，汇编语言机器级D.汇编语言机器级，应用语言机器级，高级语言机器级5、不同系列的机器之间，实现软件移植的途径不包括( )A.用统一的高级语言B.用统一的汇编语言C.模拟D.仿真6、开发并行的途径有（），资源重复和资源共享。

A.多计算机系统B.多道分时C.分布式处理系统D.时间重叠7、下列说法正确的是（）A."一次重叠"是一次解释一条指令B."一次重叠"是同时解释相邻两条指令C.流水方式是同时只能解释两条指令D."一次重叠"是同时可解释很多条指令8、不同系列的机器之间，实现软件移植的途径不包括（）。

A.用统一的高级语言B.用统一的汇编语言C.模拟D.仿真9、在尾数下溢处理方法中，平均误差最大的是（）A.截断法B.舍入法C.恒置"1"法D.ROM查表法10、下列说法中不正确的是（）A.软件设计费用比软件重复生产费用高B.硬件功能只需实现一次，而软件功能可能要多次重复实现C.硬件的生产费用比软件的生产费用高D.硬件的设计费用比软件的设计费用低二、填空题11、单体多字并行存储器的访问冲突包括取指令冲突，________，写数据冲突，________12、存储器速度可以用________、________、频宽来描述。

2022年内蒙古师范大学计算机科学与技术专业《操作系统》科目期末试卷A（有答案）一、选择题1、现代操作系统中，文件系统都有效地解决了重名（即允许不同用户的文件可以具有相同的文件名）问题。

系统是通过（）来实现这一功能的。

A.重名翻译结构B.建立索引表C.树形目录结构D.建立指针2、无结构文件的含义是（）A.变长记录的文件B.索引文件C.流式文件D.索引顺序文件3、银行家算法在解决死锁问题中用于（）。

A.预防死锁B.死锁避免C.检测死锁D.解除死锁4、若一个信号量的初值为3，经过多次P、V操作之后当前值为-1，则表示等待进入临界区的进程数为（）A.1B.2C.3D.45、采用资源剥夺法可以解除死锁，还可以采用（）方法解除死锁。

A.执行并行操作B.撤销进程C.拒绝分配新资源D.修改信号量6、（）存储管理方式提供一维地址结构。

A.分段B.分页C.分段和段页式D.以上都不对7、采用分页或分段管理后，提供给用户的物理地址空间（）。

A.分页支持史大的物理空间B.分段支持更大的物理空间C.不能确定D.一样大8、在单处理器系统中，可并行的是（）I.进程与进程II.处理器与设备III.处理器与通道IV.设备与设备A.I、II和IIIB.I、II和IVC.I、III和IVD.II、III和IV9、下列选项中，在用户态执行的是（）。

A.命令解释程序B.缺页处理程序C.进程调度程序D.时钟中断处理程序10、程序员利用系统调用打开I/O设备时，通常使用的设备标识是（），A.逻辑设备名B.物理设备名C.主设备号D.从设备号11、下列关于SPOOLing技术的叙述中，错误的是（）A.需要外存的文持B.需要多道程序设计技术的支持C.可以让多个作业共享一台独占设备D.由用户作业控制设备与输入/输出之间的数据传送12、（）是操作系统中采用的以空间换取时间的技术。

A.Spooling 技术B.虚拟存储技术C.覆盖与交换技术D.通道技术二、填空题13、采用层次式结构的操作系统通常把对一设备的管理放在__________。

2022年内蒙古科技大学计算机科学与技术专业《操作系统》科目期末试卷A（有答案）一、选择题1、驱动调度算法中，（）算法可能会随时改变移动臂的运动方向。

A.电梯调度B.最短寻道时间优先C.扫描D.单向扫描2、通常对文件系统来说，文件名及属性可以集中在（）中以使查询。

A.目录B.索引C.字典D.作业控制块3、在下述父进程和子进程的描述中，正确的是（）A.父进程创建了子进程，因而父进程执行完后，子进程才能运行B.父进程和了进程可以并发执行C.撤销了进程时，应该同时撤销父进程D.撤销父进程时，应该同时撤销子进程4、结构（Cobegin语句1：语句2 Coend）表示语句1和语句2并发执行。

代码如下：X：=0；Y：=0；CobeginBeginX：=1；Y：=Y+X；EndBeginY：=2；X：=X+3；EndCoend当这个程序执行完时，变量X和Y的值有可能为（）。

I.X=1，Y=2 II.X=1，Y=3 III.X=4，Y=6A.IB. I和IIC.II和IIID. I、II和III5、在支持多线程的系统中，进程P创建的若干个线程不能共享的是（）A.进程P的代码段B.进程P中打开的文件C.进程P的全局变量D.进程P中某线程的找指针6、（）存储管理方式能使存储碎片尽可能少，而且使内存利用率较高。

A.固定分区B.可变分区。

C.分页管理D.段页式管理7、下面有关外层页表的叙述中错误的是（）。

A.反映在磁盘上页面存放的物理位置B.外层页表是指页表的页表C.为不连续（离散）分配的页表再建立一个页表D.若有了外层页表，则需要一个外层页表寄存器就能实现地址变换8、在下列选项中，（）不属于操作系统提供给用户的可使用资源。

A.中断机制B.处理机C.存储器D.I/O设备9、下列关于批处理系统的叙述中，正确的是（）I.批处理系统允许多个用户与计算机直接交互II.批处理系统分为单道批处理系统和多道批处理系统III.中断技术使得多道批处理系统的1/O设备可与CPU并行工作A.仅II、IIIB.仅IIC.仅I、IID. 仅I、III10、（）是操作系统中采用的以空间换取时间的技术。

数据结构考研真题及其答案完整版数据结构是计算机科学与技术领域中的一门重要课程，也是计算机考研中必考的一门科目。

通过研究数据结构，可以帮助我们更好地理解和应用计算机算法，提高计算机程序的效率和性能。

为了帮助考生更好地备考数据结构，本文将分享一些数据结构考研真题及其答案，供考生参考。

一、选择题1. 下列关于栈的叙述中，错误的是（）A. 栈是一种线性数据结构，具有后进先出（LIFO）的特点B. 栈可以用数组实现，也可以用链表实现C. 栈的插入和删除操作都是在同一端进行的D. 栈的插入和删除操作的时间复杂度都是O(1)答案：C解析：栈的插入操作叫做入栈，删除操作叫做出栈。

入栈和出栈操作都是在栈顶进行的，而不是同一端。

2. 假设要对n个整数关键字进行排序，以下排序算法中，平均时间复杂度最小的是（）A. 冒泡排序B. 快速排序C. 归并排序D. 直接插入排序答案：C解析：归并排序的时间复杂度是O(nlogn)，平均时间复杂度最小。

二、填空题1. 下列关于图的遍历顺序的说法中，正确的是：深度优先搜索访问的顺序是________，广度优先搜索访问的顺序是________。

答案：前序遍历，层次遍历解析：深度优先搜索即前序遍历，广度优先搜索即层次遍历。

2. 给定一个最小堆，若删除堆顶元素后，需要对堆进行调整，所采用的操作是________。

答案：下滤解析：删除堆顶元素后，将最后一个叶子节点放到堆顶，然后进行下滤操作。

三、简答题1. 请简要说明动态规划算法的基本思想和应用场景。

答：动态规划算法的基本思想是将问题分解为多个子问题，通过求解子问题的最优解来得到原问题的最优解。

它通常适用于具有重叠子问题和最优子结构性质的问题。

动态规划算法可以大大减少问题的重复计算，提高算法的效率和性能。

它在求解最短路径、最长公共子序列、背包问题等具有广泛的应用。

2. 请简要介绍红黑树的特点和应用场景。

答：红黑树是一种自平衡的二叉查找树，它具有以下特点：1) 每个节点都有一个颜色，红色或黑色；2) 根节点是黑色的；3) 叶子节点（NIL节点）都是黑色的；4) 如果一个节点是红色的，则它的两个子节点都是黑色的；5) 从根节点到叶子节点的路径上，不同路径上黑节点的个数相同。

2024年自考-自考专业(计算机网络)-数据结构考试历年真题常考点试题带答案（图片大小可任意调节）第1卷一.单选题(共25题)1.设有一个10阶的对称矩阵A，采用行优先压缩存储方式，a11为第一个元素，其存储地址为1，每个元素占一个字节空间，则a85的地址为()。

A.13B.18C.33D.402.假设以数组A[60]存放循环队列的元素，其头指针是front=47，当前队列有50个元素，则队列的尾指针值为()。

A.3B.37C.50D.973.若栈采用链式存储结构，则下列说法中正确的是()。

A.需要判断栈满且需要判断栈空B.不需要判断栈满但需要判断栈空C.需要判断栈满但不需要判断栈空D.不需要判断栈满也不需要判断栈空4.在带头结点的双向循环链表中插入一个新结点，需要修改的指针域数量是()。

A.2个B.3个C.4个D.6个5.若一个算法的时间复杂度用T(n)表示，其中n的含义是()。

A.问题规模B.语句条数C.循环层数D.函数数量6.设栈的初始状态为空，入栈序列为1，2，3，4，5，6，若出栈序列为2，4，3，6，5，1，则操作过程中栈中元素个数最多时为()。

A.2 个B.3 个C.4 个D.6 个7.假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。

若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为()。

A.(rear-front-1) ％nB.(rear-front) ％ nC.(front-rear+1) ％nD.(rear-front+n) ％n8.二维数组A[10][6]采用行优先的存储方法，若每个元素占4个存储单元，已知元素A[3][4]的存储地址为1000，则元素A[4][3]的存储地址为()。

A.1020B.1024C.1036D.10369.便于进行布尔查询的文件组织方式是()。

A.顺序文件B.索引文件C.散列文件D.多关键字文件10.在一个长度为n的顺序表中插入一个元素的算法的时间复杂度为()。

2022年内蒙古大学数据科学与大数据技术专业《计算机组成原理》科目期末试卷A（有答案）一、选择题1、下述说法中正确的是（）。

I.半导体RAM信息可读可写，且断电后仍能保持记忆Ⅱ.动态RAM是易失性RAM，而静态RAM中的存储信息是不易失的Ⅲ.半导体RAM是易失性RAM，但只要电源不断电，所存信息是不丢失的IV.半导体RAM是非易失性的RAMA.I、ⅢB.只有ⅢC.Ⅱ、IVD.全错2、连续两次启动同一存储器所需的最小时间间隔称为（）。

A.存储周期B.存取时间C.存储时间D.访问周期3、在C语言程序中，以下程序段最终的f值为（）。

Float f=2.5+1e10；f=f-1e10；A.2.5B.250C.0D.3.54、下列关于定点数原码一位乘算法的描述正确的是（）。

I.符号位不参加运算，根据数值位的乘法运算结果确定结果的符号位II.在原码一位乘算法过程中，所有移位均是算术移位操作Ⅲ.假设两个n位数进行原码一位乘，部分积至少需要使用n位奇存器A.II，III C.只有IIIB.只有Ⅲ D.全错5、下列关于各种移位的说法中正确的是（）。

I.假设机器数采用反码表示，当机器数为负时，左移时最高数位丢0，结果出错；右移时最低数位丢0，影响精度Ⅱ在算术移位的情况下，补码左移的前提条件是其原最高有效位与原符号位要相同Ⅲ.在算术移位的情况下，双符号位的移位操作中只有低符号位需要参加移位操作（）A. Ⅲ、ⅡB.只有ⅡC.只有ⅢD.全错6、下列关于多总线结构的叙述中，错误的是（）。

A.靠近CPU的总线速度较快B.存储器总线可支持突发传送方式C.总线之间需通过桥接器相连D.PCI-Expressx16采用并行传输方式7、某总线共有88根信号线，其中数据总线为32根，地址总线为20根，控制总线36根，总线工作频率为66MHz、则总线宽度为（），传输速率为（）A.32bit 264MB/sB.20bit 254MB/sC.20bit 264MB/sD.32bit 254MB/s8、下列关于计算机操作的单位时间的关系中，正确的是（）。

内蒙古自治区考研计算机科学复习资料数据结构重要题型归纳数据结构是计算机科学与技术领域中的基础课程之一，对于考研学生来说，熟练掌握数据结构的各种题型是必不可少的。

本文将从内蒙古自治区考研的角度出发，对数据结构中的重要题型进行归纳总结，供考生参考。

1. 数组和链表数组和链表是数据结构中最基本的两种数据类型，也是考研中经常出现的重要题型。

在解题过程中，考生需要理解数组和链表的基本概念和特点，并掌握它们的插入、删除、查找等操作。

2. 栈和队列栈和队列是常用的线性数据结构，同样也是考研中的热门考点。

考生需要了解栈和队列的特点，掌握它们的基本操作，如入栈、出栈、入队、出队等，并能够根据题目要求选择合适的数据结构进行解题。

3. 串串是由零个或多个字符组成的有限序列，字符串处理在计算机科学中有着广泛的应用。

考生需要了解串的基本操作，如串的比较、复制、连接等，并能够灵活运用相关算法解决与串相关的问题。

4. 树树是一种重要的非线性数据结构，常用于组织和存储具有层次关系的数据。

在考研中，二叉树及其派生结构是重点考点之一。

考生需要熟悉树的基本概念，掌握二叉树的各种遍历方式，如前序遍历、中序遍历、后序遍历等，并能够应用相关算法解决与树相关的问题。

5. 图图是由顶点和边组成的一种复杂数据结构，广泛应用于网络、社交等领域。

在考研中，图的基本概念和算法也是重要的考点。

考生需要了解图的表示方法，掌握图的遍历算法，如深度优先搜索（DFS）和广度优先搜索（BFS），并能够根据题目要求选择合适的算法解决与图相关的问题。

6. 排序和查找排序和查找是数据结构中非常重要的两个方面。

常见的排序算法有冒泡排序、插入排序、选择排序、快速排序、归并排序等，考生需要理解各种排序算法的原理和特点，并能够根据题目要求选择合适的排序算法解决问题。

查找算法包括线性查找、二分查找、哈希查找等，考生需要了解各种查找算法的原理和适用场景，并能够根据题目要求选择合适的查找算法解决问题。

[考研类试卷]计算机专业基础综合数据结构（集合）历年真题试卷汇编5.doc[考研类试卷]计算机专业基础综合数据结构（集合）历年真题试卷汇编5一、填空题1 对于具有144个记录的文件，若采用分块查找法，且每块长度为8，则平均查找长度为__________。

【北方交通大学2001二、8】2 有一个2000项的表，欲采用等分区间顺序查找方法进行查找，则每块的理想长度是 (1)，分成 (2) 块最为理想，平均查找长度是 (3) 。

【中国矿业大学2000一、6(3分)】3 分块检索中，若索引表和各块内均用顺序查找，则有900个元素的线性表分成__________块最好；若分成25块，其平均查找长度为__________。

【北京工业大学1999一、5(2分)】4 执行顺序查找时，储存方式可以是(1)，二分法查找时，要求线性表(2)，分块查找时要求线性表(3)，而散列表的查找，要求线性表的存储方式是(4)。

【山东大学1998一、1(3分)】5 查找是非数值程序设计的一个重要技术问题，基本上分成(1)查找，(2)查找和(3)查找。

处理哈希冲突的方法有(4)、(5)、(6)和(7)。

【华北计算机系统工程研究所1999一(5分)】6 如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为__________。

【山东大学1999二、1(4分)】7 在含有n个结点的二叉排序树中查找一个关键字，进行关键字比较次数的最大值是__________。

【北京交通大学2004一、15(2分)】8 在二叉排序树上成功地找到一个结点，在平均情况下的时间复杂性是：__________，在最坏情况下的时间复杂性是__________。

【上海交通大学2004五、1(15／4分)】9 AVL树__________是完全二叉树；完全二叉树__________是AVL 树。

【电子科技大学2005二、5(1分)】10 一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有__________个结点。

大学计算机《数据结构》试卷及答案第一部分 选择题(30分)一、项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后括号内。

1．算法指的是（ ）A ．计算机程序B ．解决问题的计算方法C ．排序算法D ．解决问题的有限运算序列 2．线性表采用链式存储时，结点的存储地址（ ） A ．必须是不连续的B ．连续与否均可C ．必须是连续的D ．和头结点的存储地址相连续3．将长度为n 的单链表链接在长度为m 的单链表之后的算法的时间复杂度为（） A ．O （1） B ．O （n ） C ．O （m ） D ．O （m+n ） 4．由两个栈共享一个向量空间的好处是：（ ） A ．减少存取时间，降低下溢发生的机率 B ．节省存储空间，降低上溢发生的机率 C ．减少存取时间，降低上溢发生的机率 D ．节省存储空间，降低下溢发生的机率5．设数组data[m]作为循环队列SQ 的存储空间，front 为队头指针，rear 为队尾指针，则执行出队操作后其头指针front 值为（ ）A ．front=front+1B ．front=(front+1)%(m-1)C ．front=(front-1)%mD ．front=(front+1)%m 6．如下陈述中正确的是（ ）A ．串是一种特殊的线性表B ．串的长度必须大于零C ．串中元素只能是字母D ．空串就是空白串7．若目标串的长度为n ，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是（ ）A ．O （）B ．O （n ）C ．O （n 2）D ．O （n 3） 8．一个非空广义表的表头（ ）A ．不可能是子表B ．只能是子表C ．只能是原子D ．可以是子表或原子9对应的稀疏矩阵是（ ）n 3080650400000--⎡⎣⎢⎢⎤⎦⎥⎥.08067000504000000300--⎡⎣⎢⎢⎢⎢⎢⎢⎤⎦⎥⎥⎥⎥⎥⎥10．在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为( )A ．4B ．5C ．6D ．711．在含n 个顶点和e 条边的无向图的邻接矩阵中,零元素的个数为( ) A ．e B ．2e C ．n 2－e D ．n 2－2e12．假设一个有n 个顶点和e 条弧的有向图用邻接表表示,则删除与某个顶点v i相关的所有弧的时间复杂度是( )A ．O(n)B ．O(e)C ．O(n+e)D ．O(n*e)13．用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84则所采用的排序方法是（ ）A ．选择排序B ．希尔排序C ．归并排序D ．快速排序 14．适于对动态查找表进行高效率查找的组织结构是（ ）A ．有序表B ．分块有序表C ．三叉排序树D ．线性链表 15．不定长文件是指（ ）A ．文件的长度不固定B ．记录的长度不固定C ．字段的长度不固定D ．关键字项的长度不固定第二部分 非选择题（共70分）二、填空题（本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分）不写解答过程，将正确的答案写在每小题的空格内。

2022年内蒙古工业大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、下列说法不正确的是（）。

A.图的遍历是从给定的源点出发每个顶点仅被访问一次B.遍历的基本方法有两种：深度遍历和广度遍历C.图的深度遍历不适用于有向图D.图的深度遍历是一个递归过程2、无向图G=(V，E)，其中：V={a，b，c，d，e，f}，E={(a，b)，(a， e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。

A.a，b，e，c，d，fB.a，c，f,e，b，dC.a，e，b，c，f, dD.a，e，d，f，c，b3、线性表的顺序存储结构是一种（）。

A.随机存取的存储结构B.顺序存取的存储结构C.索引存取的存储结构D.Hash存取的存储结构4、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）。

A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都可能要修改D.队头、队尾指针都要修改5、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（）。

A.h->next=sB.s->next=hC.s->next=h;h->next=sD.s->next=h-next;h->next=s6、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。

A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝27、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。

下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。

Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ8、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。