2017年北京物资学院计算机应用技术911计算机学科专业基础综合之数据结构考研导师圈点必考题汇编
● 摘要
一、填空题
1． 遍历图的过程实质上是_____，广度优先遍历图的时间复杂度_____; 深度优先遍历图的时间复杂度_____, 两者不同之处在于_____, 反映在数据结构上的差别是_____。
【答案】查找顶点的邻接点的过程；0（n+e）; 0（n+e）; 访问顶点的顺序不同；队列和栈 【解析】广度优先遍历图使用队列这种数据结构，深度优先遍历图使用栈这种数据结构。
2． 下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。
【答案】
【解析】快速排序（quicksort ）的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
3． 线性表
【答案】（n －1）/2
用数组表示，假定删除表中任一元素的概率相同，则删除一个元素
平均需要移动元素的个数是_____。
【解析】删除第一个元素需要移动n －i 次，以此类推，删除最后一个元素需要移动0次。平 均次数为
4． 实现字符串拷贝的函数strcpy 为：
【答案】
，）则
的地址为_____。
若
5． 设有一个10阶对称矩阵A 采用压缩存储方式（以行为主序存储：
【答案】33
【解析】设存储的元素的行标为i ，列标为j 。若则
则
的地址为
的地址为将代入得33。
6． 在进行入栈运算时应先判别栈是否_____:在进行出栈运算时应先判别栈是否_____:当栈中元素为n 个，进行入栈运算时发生上溢，则说明该栈的最大容量为_____。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_____分别设在内存空间的两端，这样只有当_____时才产生溢出。
【答案】满；空；n ; 栈底；两栈顶指针相邻（即值之差的绝对值为1）
7． 检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按_____检索。也可以按_____检索；按_____检索又可以有_____检索和_____检索。
【答案】关键字；记录号；记录号；顺序；直接
8． 高度为h 的堆中，最多有_____元素，最少有_____个元素。
【答案】
当最后一层只有
【解析】当这个堆构成的是满二叉树时，元素的个数最多，
元素个数为 一个元素时，此时堆的元素个数最少，元素个数为
9． 文件可按其记录的类型不同而分成两类，即_____和_____文件。
【答案】操作系统文件；数据库
10．数据结构中评价算法的两个重要指标是_____。
【答案】算法的时间复杂度和空间复杂度
二、选择题
11．程序员利用系统调用打开I/O设备时，通常使用的设备标识是（ ）。
A. 逻辑设备名 B. 物理设备名 C. 主设备号 D. 从设备号 【答案】A
【解析】设备管理具有设备独立性的特点，操作系统以系统调用方式提供给应用程序使用逻辑设备名来请求使用某类设备时，调用中使用的是逻辑设备名，例如LPT1或COM1等。而操作系统内部管理设备使用的是设备编号。
12．设有向图G= （V ，E ），顶点集能得到的不同遍历序列个数是（ ）。
A.2 B.3 C.4 D.5
【答案】D
【解析】根据题意知有向图的结构如图所示。深度优先遍历的特点是尽可能先对纵深方向进行搜索，所以可 能得到的不同遍历序列分别是：
13．对于一个线性表既要求能够进行较快速地的插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用（ ）。
A. 顺序存储方式 B. 链式存储方式 C. 散列存储方式 D. 以上均可以 【答案】B
14．以太网交换机进行转发决策时使用的PDU 地址是（ ）。
A. 目的物理地址 B. 目的IP 地址 C. 源物理地址
V={V0, VI ，V2, V3}，边
集
若从顶点V0开始对图进行深度优先遍历，则可
相关内容
相关标签