2024年计算机专业基础测试卷

2024年计算机专业基础测试卷考试时间：______分钟总分：______分姓名：______一、单项选择题（本大题共15小题，每小题2分，共30分。在每小题列出的四个选项中，只有一个是符合题目要求的，请将正确选项字母填在题后的括号内。）1.在线性表顺序存储结构中，插入和删除操作的最坏时间复杂度是O(n)。2.下列数据结构中，适合用来表示稀疏矩阵的是三元组表。3.设栈S的初始状态为空，依次进行入栈操作：P,Q,R,S,T，再进行出栈操作，则出栈序列的最后一个元素是R。4.在各种查找方法中，的平均查找长度与记录个数n无关的是散列查找。5.冒泡排序在最坏情况下的时间复杂度是O(n^2)。6.对一棵具有n个结点的二叉树进行遍历，遍历的总次数是2n。7.在深度为h的二叉树中，最多有2^h-1个结点。8.在树形结构中，任何结点（除根结点外）都有且仅有一个前驱结点。9.哈夫曼树是一种带权路径长度最短的二叉树。10.计算机系统总线按传输信息的功能可分为数据总线、地址总线和控制总线。11.CPU访问存储器需要经历的周期称为机器周期。12.在计算机中，指令和数据都以二进制代码的形式存放在存储器中。13.I/O接口的主要功能之一是实现CPU与I/O设备之间的信息交换。14.操作系统的功能可以概括为进程管理、内存管理、文件管理和设备管理。15.进程的状态转换不包括阻塞状态变为就绪状态。二、多项选择题（本大题共5小题，每小题3分，共15分。在每小题列出的五个选项中，有多项符合题目要求。请将正确选项字母填在题后的括号内。多选、少选、错选均不得分。）1.下列关于线性表的说法中，正确的是（）。A.线性表是n个数据元素的有限序列B.线性表中的每个元素都有且仅有一个直接前驱和直接后继C.线性表可以是空表D.线性表可以通过地址直接访问任何一个元素E.线性表只能进行插入和删除操作2.下列排序算法中，属于不稳定排序算法的是（）。A.冒泡排序B.插入排序C.选择排序D.快速排序E.堆排序3.在树形结构中，下列说法正确的是（）。A.树的度是指树中结点的最大度数B.叶子结点是度为0的结点C.树的深度是指树中结点的最大层次D.非空二叉树只有根结点和叶子结点两种结点E.满二叉树是指除叶子结点外，每个结点都有两个孩子的二叉树4.计算机硬件系统由（）组成。A.运算器B.存储器C.输入设备D.输出设备E.操作系统5.操作系统中，进程调度算法的目标是（）。A.提高CPU的利用率B.缩短平均周转时间C.保证公平性D.最小化平均等待时间E.降低系统开销三、判断题（本大题共10小题，每小题1.5分，共15分。请判断下列叙述的正误，正确的填“√”，错误的填“×”。）1.链表是线性表的链式存储结构，链表中的元素在内存中可以连续存储。（）2.二分查找算法适用于有序的顺序表，其时间复杂度为O(logn)。（）3.图是一种不存在环的有向图称为有向树。（）4.堆排序是一种基于堆这种数据结构的排序算法，它的时间复杂度为O(nlogn)。（）5.程序计数器（PC）用于存放下一条要执行指令的地址。（）6.主存中的数据可以直接被CPU访问，而辅存中的数据不能。（）7.I/O设备是指所有输入输出设备，如键盘、鼠标、打印机、显示器等。（）8.操作系统是计算机系统中最核心的系统软件，它负责管理和控制计算机系统的所有资源。（）9.进程和程序是不同的概念，进程是动态的，而程序是静态的。（）10.死锁是指两个或两个以上进程在执行过程中，因争夺资源而造成的一种相互等待的现象，若无外力作用，这些进程都将无法向前推进。（）四、填空题（本大题共10空，每空2分，共20分。请将答案填写在答题纸的横线上。）1.数据结构是指相互关联的数据元素的集合，其核心是研究数据元素之间的______。2.在栈的操作中，插入元素的操作称为______，删除元素的操作称为______。3.在树形结构中，每个结点（除根结点外）都有且仅有一个______。4.对于n个元素的线性表，在最坏情况下，快速排序需要进行的比较次数为______。5.计算机硬件系统采用冯·诺依曼体系结构，其核心思想是______。6.CPU的主要功能是______和控制。7.存储器按在计算机系统中的地位和作用可以分为______和辅助存储器。8.在操作系统中，文件系统负责管理计算机中的______。9.进程的基本状态有就绪状态、运行状态和______。10.计算机网络按覆盖范围可以分为局域网和______。五、简答题（本大题共4小题，每小题5分，共20分。）1.简述线性表和树的区别。2.简述操作系统的主要功能。3.什么是中断？中断处理过程大致分为哪几个步骤？4.简述TCP协议与UDP协议的主要区别。六、计算题（本大题共2小题，每小题10分，共20分。）1.设有一棵二叉树的前序遍历序列为ABCD，中序遍历序列为CBAD。请画出该二叉树。2.假设有一个顺序存储的线性表，元素依次为(15,23,63,45,87,92,57)。请写出对该线性表进行快速排序的第一趟排序过程（即从线性表中选取一个元素作为枢轴，将线性表划分为两个子表，使得左子表所有元素小于枢轴，右子表所有元素大于枢轴）。试卷答案一、单项选择题1.A2.B3.D4.A5.A6.C7.A8.B9.A10.A11.A12.A13.A14.A15.D二、多项选择题1.ABC2.CD3.ABC4.ABCD5.ABCD三、判断题1.×2.√3.×4.√5.√6.√7.×8.√9.√10.√四、填空题1.结构关系2.入栈出栈3.父结点4.n(n-1)/25.程序存储6.运算7.主存储器（内存）8.文件9.阻塞（等待）10.广域网（WAN）五、简答题1.线性表是数据元素之间存在一对一的线性关系，每个元素有唯一的前驱和后继（除首尾元素外）；树是数据元素之间存在一对多的层次关系，除根结点外每个元素有唯一的前驱，但可以有零个或多个后继。线性表具有顺序存储和链式存储两种主要方式，树通常采用链式存储。2.操作系统的主要功能包括：进程管理（负责进程创建、调度、终止等，管理CPU资源）、内存管理（负责内存分配、回收、保护等，管理内存资源）、文件管理（负责文件的创建、删除、读写、目录管理等，管理磁盘等外存资源）、设备管理（负责管理各种I/O设备，实现CPU与设备之间的信息交换）以及提供用户接口（为用户和应用程序提供方便的使用方式）。3.中断是指计算机在执行程序过程中，出现某些意外事件，需要CPU暂停当前正在执行的任务，转而去处理这些事件，处理完毕后再返回原任务继续执行的过程。中断处理过程大致分为：中断请求、中断判优（如果有多个中断请求）、中断响应（CPU暂停当前工作，保存现场，并跳转到中断服务程序入口）、中断处理（执行中断服务程序，处理中断事件）、中断返回（恢复现场，继续执行被中断的程序）。4.TCP（传输控制协议）是一种面向连接的、可靠的、基于字节流的传输层协议。它提供数据传输的可靠保证（通过序列号、确认应答、重传机制等），但传输效率相对较低，开销较大。UDP（用户数据报协议）是一种无连接的、不可靠的、基于数据报的传输层协议。它传输速度快，开销小，但不对数据传输的可靠性提供保证（尽最大努力交付）。六、计算题1.解：前序遍历序列：ABCD中序遍历序列：CBAD由前序遍历可知，A是根结点。由中序遍历可知，CB在A之前，为A的左子树；D在A之后，为A的右子树。对A的左子树（CB），前序遍历为BC，中序遍历为CB，可知B是左子树的根，C是B的右孩子。对A的右子树（D），前序遍历为（无），中序遍历为D，可知D是右子树的根（且无子树）。画出二叉树如下：A/\BD/C2.解：枢轴选择第一个元素，即63。将线性表划分为左子表（小于63）和右子表（大于63）。原始线性表：15,23,63,45,87,92,57划分过程：1.从后向前找到第一个小于63的元素57，交换57和63：15,23,57,45,87,92,632.将小于63的元素移到枢轴左边，大于63的元素移到枢轴右边（使用首尾指针法）：15,23,57,45,87,92,63i=0,j=615<63,i++->i=123<63,i++->i=257<63,i++->i=345<63,i++->i=487>63,j--->j=592>