2025计算机科学与技术专升本专项训练试卷（含答案）

2025计算机科学与技术专升本专项训练试卷（含答案）考试时间：______分钟总分：______分姓名：______一、选择题（每题2分，共20分。请将正确选项的字母填在题后的括号内）1.下列关于数据结构的叙述中，正确的是（）。a)线性表是线性结构，栈和队列不是线性结构b)树是一种非线性结构，其中每个结点都有且只有一个前件c)图是一种非线性结构，其中每个结点可以有多个前件和多个后件d)队列和栈都是非线性结构，且遵循不同的操作原则2.在长度为n的顺序表中插入一个新元素，最坏情况下需要移动的元素个数是（）。a)n/2b)n-1c)nd)13.下列排序算法中，不稳定排序算法是（）。a)插入排序b)选择排序c)希尔排序d)冒泡排序4.在一棵二叉树中，若结点x是结点y的双亲结点，则称x是y的（）。a)子结点b)父结点c)兄弟结点d)根结点5.访问一个结点，并遍历该结点的所有子结点，然后分别遍历其子结点的子结点，这种遍历方式是（）。a)先序遍历b)中序遍历c)后序遍历d)层次遍历6.在数据压缩技术中，属于无损压缩的是（）。a)游程编码b)哈夫曼编码c)子带编码d)超失真编码7.计算机硬件能够直接识别和执行的指令代码是（）。a)汇编语言指令b)高级语言源程序c)机器语言指令d)BASIC语言源程序8.CPU主要是由（）组成的。a)运算器和控制器b)控制器和存储器c)运算器和存储器d)输入设备和输出设备9.在操作系统中，进程的基本状态转换是（）。a)运行态、就绪态、阻塞态b)创建态、运行态、终止态c)就绪态、运行态、阻塞态、终止态d)就绪态、阻塞态、运行态10.在TCP/IP协议簇中，负责网络层数据包传输的协议是（）。a)HTTPb)FTPc)TCPd)IP二、填空题（每空2分，共20分。请将答案填在横线上）1.数据结构的基本操作包括插入、删除、__________和__________。2.在树形结构中，树根结点没有前件，其他每个结点有且只有一个前件，这种关系称为__________关系。3.冒泡排序的基本思想是：将待排序序列看作是__________，从前往后依次比较相邻的两个元素，若发现逆序则交换，直到序列按顺序排列。4.一个逻辑地址空间中包含的内存单元个数称为__________。5.CPU根据存储器地址寻找并读取数据或指令的操作称为__________。6.在指令系统中，操作数可以出现在操作码后面，也可以出现在寄存器中，还可以通过地址指定符指定在__________中。7.操作系统通过__________机制，将用户程序转换为CPU可直接执行的机器指令序列。8.计算机网络按照覆盖范围可分为__________网、城域网和广域网。9.在TCP/IP协议簇中，UDP协议提供的是无连接的、__________的传输服务。10.衡量计算机性能的两个主要指标是__________和__________。三、判断题（每题2分，共10分。请在题后括号内填“√”表示正确，“×”表示错误）1.递归算法必须使用栈来存储中间状态。（）2.在栈中，插入和删除操作都在栈顶进行。（）3.快速排序是一种稳定的排序算法。（）4.在树形结构中，任何一个结点都有且仅有一个双亲结点。（）5.缓存（Cache）是计算机系统中位于CPU和主存之间的高速存储器。（）四、简答题（每题5分，共15分）1.简述栈和队列的主要区别。2.简述“时间片轮转”调度算法的基本思想。3.简述IP协议在计算机网络中的主要功能。五、编程题（10分）编写一个C语言函数，实现单链表的单向反转。函数接收一个指向单链表头结点的指针作为参数，返回指向反转后链表头结点的指针。链表结点定义如下：```cstructListNode{intdata;structListNode*next;};```六、综合应用题（15分）设有一个包含10个元素的顺序表，元素初始顺序为：[12,2,8,16,5,20,15,10,7,3]。请分别写出使用冒泡排序算法对该顺序表进行从小到大排序的每一趟排序后的结果。试卷答案一、选择题1.c2.c3.c4.b5.d6.b7.c8.a9.a10.d二、填空题1.查找，修改2.父3.有序序列4.内存容量5.访问（或读/访）6.存储器（或内存）7.翻译（或编译）8.局域9.无连接的、不可靠10.运算速度（或主频），可靠性三、判断题1.√2.√3.×4.√5.√四、简答题1.解析思路：栈是后进先出（LIFO）结构，只允许在栈顶进行插入和删除操作；队列是先进先出（FIFO）结构，允许在队尾插入元素，在队头删除元素。这是两者最根本的区别。2.解析思路：时间片轮转是一种抢占式调度算法，它将所有就绪进程按FCFS原则排成一个队列，CPU按时间片轮转方式依次为每个进程服务。当一个时间片用完时，若进程尚未执行完毕，则该进程被移至就绪队列末尾，CPU切换到下一个就绪进程执行。3.解析思路：IP协议的主要功能包括：负责将数据包从源主机传输到目标主机（路由选择）；实现网络互连（作为互联网协议）；提供无连接的数据报服务；处理IP数据报分片与重组等。五、编程题```cstructListNode*reverseList(structListNode*head){structListNode*prev=NULL;//前驱指针初始化为NULLstructListNode*current=head;//当前指针指向头结点structListNode*nextTemp=NULL;//临时指针，用于保存下一个结点while(current!=NULL){nextTemp=current->next;//保存当前结点的下一个结点current->next=prev;//将当前结点的指针指向前驱结点prev=current;//前驱指针向前移动current=nextTemp;//当前指针向前移动}returnprev;//当current为NULL时，prev指向新的头结点}```解析思路：单链表反转通过迭代实现。使用三个指针：prev（初始为NULL，最终指向反转后的头结点）、current（初始指向头结点，用于遍历）、nextTemp（用于临时保存当前结点的下一个结点）。遍历链表，在遍历过程中，逐个调整当前结点的next指针指向前一个结点（prev），实现反转。每一步都需要保存下一个结点，否则链表会被断开。遍历结束后，prev指向新的头结点。六、综合应用题第一趟：[2,8,16,5,20,15,10,7,3,12]第二趟：[2,8,5,16,15,10,7,3,12,20]第三趟：[2,5,8,15,10,7,3,12,16,20]第四趟：[2,5,8,7,10,3,12,15,16,20]第五趟：[2,5,7,8,3,10,12,15,16,20]第六趟：[2,5,7,3,8,10,12,15,16,20]第七趟：[2,5,3,7,8,10,12,15,16,20]第八趟：[2,3,5,7,8,10,12,15,16,20]第九趟：[2,