2018年常州大学信息学院、数理学院858数据结构考研仿真模拟五套题
● 摘要
一、单项选择题
1． 静态链表中指针表示的是（ ）。
A. 下一元素的地址
B. 内存储器的地址
C. 下一元素在数组中的位置
D. 左链或右链指向的元素的地址
【答案】C
【解析】静态链表的一般结构为:struct static_list{ElemType data；int next；}
这种结构是预先分配一个较大的空间，类似于一次申请一个较大的数组，但是元素的增删操作都不会移动元素，只需要移动next 成员就行。因此，静态链表中的指针实际上表示的就是下一个元素在数组中的位置。
2． 可以用（ ）定义一个完整的数据结构。
A. 数据元素
B. 数据对象
C. 数据关系
D 抽象数据类型
【答案】D
【解析】抽象数据类型可以定义一个完整的数据结构。包括数据元素，数据元素之间的关系，以及可以进行的操作。
3． 若一个用户进程通过read 系统调用读取一个磁盘文件中的数据, 则下列关于此过程的叙述中, 正确的是（ ）。
Ⅰ. 若该文件的数据不在内存, 则该进程进入睡眠等待状态;
Ⅱ. 请求read 系统调用会导致CPU 从用户态切换到核心态;
Ⅲ.read 系统调用的参数应包含文件的名称
A. 仅Ⅰ、Ⅱ
B. 仅Ⅰ、Ⅲ
C. 仅Ⅱ、Ⅲ
D. Ⅰ、Ⅱ和Ⅲ
【答案】A
【解析】对于Ⅰ, 当所读文件的数据不再内存时, 产生中断(缺页中断、缺段中断) , 原进程进入睡眠等待状态(阻塞状态) , 直到所需数据从外村调入内存后, 将该进程唤醒, 使其变为就绪状态。对于Ⅱ, read 系统调用cpu 将从用户态切换到核心态, 从而获取操作系统提供的服务。对于Ⅲ, 在操作
Open 系统调用的参数需要包含文件的系统中, 要读一个文件首先要open 系统调用将该文件打开。
路径名与文件名, 而read 系统调用只需使用open 返回的文件描述符, 并不使用文件名作为参数。Read 系统调用要求用户提供三个输入参数:
①文件描述符; ②buf 缓冲区首址; ③传送的字节数n 。
read 系统调用的功能是试图从fd 所指示的文件中读入n 个字节的数据, 并将它们送至由指针buf 所指示的缓冲区中。
4． 图中有关路径的定义正确的是（ ）。
A. 由顶点和相邻顶点构成的边所形成的序列
B. 由不同顶点所形成的序列
C. 由不同边所形成的序列
D. 上述定义都不是
【答案】A
【解析】顶点到顶点之间的一条路径是指顶点序列。路径上边的数目称为路径的长度。
5． 在虚拟存储管理中, 地址变换机构将逻辑地址变换为物理地址, 形成该逻辑地址的阶段是（ ）。
A. 编辑
B. 编译
C. 链接
D. 装载
【答案】B
【解析】程序的编辑阶段一般都是程序员能够识别的高级语言或低级语言的文本, 不涉及到任何与计算机运行相关的事; 编译是由编译程序将用户源代码编译成若干个目标模块, 源地址编译成目标程序时, 会形成逻辑地址; 链接是由链接程序将编译后形成的一组目标模块, 以及所需库函数链接, 形成完整的装入模块; 装入是由装入程序将装入模块装入内存。
6． 图G 是n 个顶点的无向完全图，则下列说法不正确的是（ ）
A.G 的邻接多重表需要n(n－1) 个边结点和n 个顶点结点
B.G 的连通分量个数最少
C.G 为连通图
D.G 所有顶点的度的总和为n(n—1)
【答案】A
A 项中G 的邻接多重表中需要【解析】个边结点和n 个顶点结点。此时连通分量最少
为1。无向完全图中任意两个顶点之间都存在路径，则G 必为连通图。每个顶点的度为n －1，则n 个结点的度的总和为n(n－1) 。
7． 下列关于管道(Pipe)通信的叙述中, 正确的是（ ）
A. —个管道可实现双向数据传输
B. 管道的容量仅受磁盘容量大小限制
C. 进程对管道进行读操作和写操作都可以被阻塞
D. —个管道只能有一个读写进程或一个写进程对其操作
【答案】C
【解析】只有写进程才能对管道写入数据, 读进程对管道进行读取数据, 只能半双工通信, 即某一时刻只能单向传输。管道为空, 则读操作被堵塞, 而如果有写操作对管道进行写的话那就要堵塞了。那么C 正确
8． 对于下列关键字序列, 不可能构成某二叉排序树中一条查找路径的序列是（ ）。
A.95, 22, 91, 24, 94, 71
B.92, 20, 91, 34, 88, 35
C.21, 89, 77, 29, 36, 38
D.12, 25, 71, 68, 33, 34
【答案】A
【解析】各选项对应的查找过程如下图所示, 从中看到选项B 、C 、D 对应的查找树都是二叉排序树, 只有选项A 对应的查找树不是一棵二叉排序树, 因为在以91为根的左子树中出现了比91大的结点94。
9． 已知一算术表达式的中缀表达式为a ﹣(b＋c/d)*e，其后缀形式为（ ）。 A.
B.
C.