计算机科学与技术基础专业

计算机科学与技术基础专业考试时间：______分钟总分：______分姓名：______一、选择题（每题2分，共20分。请将正确选项的代表字母填写在答题纸上对应位置。）1.下列哪项不属于计算机硬件系统的基本组成部分？A.运算器B.存储器C.输入设备D.操作系统2.计算机内部用于表示信息的标准单位是？A.位（bit）B.字节（Byte）C.字（Word）D.千字节（KB）3.在计算机中，字符'A'的ASCII码值（用十进制表示）与字符'D'的ASCII码值之间相差？A.1B.2C.3D.44.下面关于数据的逻辑结构的叙述中，哪项是正确的？A.数组是线性结构B.队列是非线性结构C.树是线性结构D.图不是结构5.在栈结构中，插入和删除操作都只能在栈的？A.栈顶进行B.栈底进行C.任意位置进行D.中间位置进行6.对于线性表（a1,a2,...,an），进行删除操作时，若要删除第i个元素（1≤i≤n），则需要先移动多少个元素？A.i-1B.iC.n-iD.n-i+17.下面关于算法的叙述中，错误的是？A.算法具有有穷性B.算法必须能输出结果C.算法可以无限循环不终止D.算法至少有一种输入8.若一个算法的时间复杂度为O(n^2)，则当输入规模n增加一倍时，算法执行时间大约增加？A.一倍B.两倍C.四倍D.八倍9.操作系统通过什么机制来管理计算机的内存资源？A.进程调度B.内存分配C.设备驱动D.文件系统10.TCP/IP协议栈中，负责提供可靠数据传输的协议是？A.TCPB.UDPC.IPD.ICMP二、填空题（每题2分，共20分。请将答案填写在答题纸上对应位置。）1.计算机硬件系统的五大基本组成部分是：运算器、______、存储器、输入设备和输出设备。2.一个字节的二进制位数是______。3.在二叉树中，一个结点拥有两个孩子，这种结构称为______二叉树。4.在队列结构中，插入操作称为______，删除操作称为______。5.算法的时间复杂度和空间复杂度分别描述了算法的______和______。6.操作系统提供了______管理、内存管理和文件管理等服务。7.计算机网络中，将不同网络互联在一起的设备称为______。8.数据库系统中，关系的特点之一是元组具有______。9.C语言中，用于输出整数n的绝对值的函数是______。10.计算机网络分层模型中，处于最高层的是______层。三、判断题（每题1分，共10分。请将“正确”或“错误”填写在答题纸上对应位置。）1.程序就是算法。（）2.任何数据结构都可以用于实现栈和队列。（）3.线性表可以是空表。（）4.算法的复杂度只与时间有关，与空间无关。（）5.操作系统是计算机系统中的系统软件。（）6.TCP协议提供面向无连接的、不可靠的数据传输服务。（）7.万维网（WWW）是在TCP/IP协议栈的网络层运行的。（）8.关系数据库中的“关系”就是数学上的集合。（）9.在C语言中，变量必须先定义后使用。（）10.计算机指令由操作码和地址码组成。（）四、简答题（每题5分，共25分。请将答案填写在答题纸上对应位置。）1.简述“冯·诺依曼体系结构”计算机的基本思想。2.什么是数据结构？它包含哪些基本操作？3.简述操作系统在个人计算机中管理硬件资源的主要方式。4.解释TCP/IP协议栈中网络接口层（或链路层）的主要功能。5.什么是数据库？它与文件系统有何主要区别？五、计算题（每题10分，共20分。请将答案填写在答题纸上对应位置。）1.假设有一个栈S，初始时为空。现依次进行以下操作：push(1),push(2),push(3),pop(),push(4),pop(),pop(),push(5)。请画出栈S在每次操作后的状态（即栈中元素及其顺序）。2.计算以下算法的执行时间复杂度（用大O表示法）：```intsum=0;for(inti=0;i<n;i++){sum+=i;}```其中，n是输入的整数。六、综合应用题（共15分。请将答案填写在答题纸上对应位置。）已知一个线性表L存储在数组A[1...10]中，初始时L为（a1,a2,a3,a4,a5,0,0,0,0,0），其中元素ai存储在A[i]中，其余位置为空。现采用顺序存储结构实现队列，并假设队头指针为front，队尾指针为rear，初始时front=1，rear=6。请回答以下问题（假设所有操作均在队列非空且未满的情况下进行）：1.写出初始时队列中存储的元素及其在数组中的位置。2.执行一次入队操作（入队元素为x），写出执行后队列中存储的元素及其在数组中的位置，以及front和rear的值。3.执行两次出队操作，写出执行后队列中存储的元素及其在数组中的位置，以及front和rear的值。试卷答案一、选择题1.D2.B3.C4.A5.A6.C7.C8.C9.B10.A二、填空题1.控制2.83.完全4.入队，出队5.效率，空间6.进程7.路由器8.无序性9.abs()10.应用三、判断题1.正确2.正确3.正确4.错误5.正确6.错误7.错误8.正确9.正确10.正确四、简答题1.答：冯·诺依曼体系结构的基本思想是计算机由运算器、控制器、存储器、输入设备和输出设备五部分组成，采用二进制表示数据和指令，程序存储执行，指令由操作码和地址码组成。2.答：数据结构是相互关联的数据元素的集合。它包含的基本操作有：插入、删除、查找、更新等。3.答：操作系统通过进程管理来调度CPU使用，通过内存管理来分配和回收内存空间，通过设备管理来控制输入输出设备的使用。4.答：网络接口层（或链路层）的主要功能是提供节点到节点的数据传输，负责物理地址（MAC地址）的寻址，数据帧的封装与解封装，以及局域网内的数据传输。5.答：数据库是长期存储在计算机内、有组织的、可共享的大量数据的集合。与文件系统相比，数据库管理系统提供了数据独立性、完整性约束、并发控制、恢复等高级管理功能。五、计算题1.答：*push(1):[1]*push(2):[1,2]*push(3):[1,2,3]*pop():[1,2]*push(4):[1,2,4]*pop():[1,2]*pop():[1]*push(5):[1,5]状态顺序：[1],[1,2],[1,2,3],[1,2],[1,2,4],[1,2],[1],[1,5]2.答：该算法包含一个循环，循环变量i从0变化到n-1，共执行n次循环体内的语句。每次循环体执行常数时间的操作（赋值和加法）。因此，执行时间与n成正比，时间复杂度为O(n)。六、综合应用题1.答：初始队列元素为(a1,a2,a3,a4,a5)，存储在A[1]到A[5]；A[6]到A[10]为空。front=1，rear=6。2.答：入队元素x后，