2018年杭州电子科技大学通信工程学院851数据结构考研核心题库
● 摘要
一、判断题
1． 设栈采用顺序存储结构。若已有i-1个元素入栈，则将第i 个元素入栈时，入栈算法的时间复杂性为O(i)。（ ）
【答案】 ×
【解析】由于该栈采用顺序存储结构，时间复杂度应该为O(1)。
2． 算法的优劣与算法描述语言无关，但与所用计算机有关。（ ）
【答案】 ×
【解析】算法的优劣和它的时间复杂度和空间复杂度有关，与算法描述语言和所用计算机都无关。
3． 在平衡二又树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。（ ）
【答案】×
【解析】不一定，比如一个平衡因子为1的结点，这时往它的右部插入一个新结点，就不会引起平衡旋转
4． 不同的求最小生成树的方法最后得到的生成树是相同的。（ ）
【答案】×
【解析】对于一个带权连通无向图G=(V，E) , 生成树不同，每棵树的权也可能不同。若生成树T 上的所有边的权值之和最小，则T 称为G 的最小生成树。因此可以看出，最小生成树不是唯一的，最小生成树的权值之和总是唯一的。
5． 抽象数据类型与计算机内部表示和实现无关。（ ）
【答案】 √
【解析】抽象数据类型只表示数据的逻辑结构，与计算机内部表示和实现无关。
6． 无环有向图才能进行拓扑排序。（ ）
【答案】√
【解析】在图论中，由一个有向无环图的顶点组成的序列，才能进行拓扑排序。
二、单项选择题
7． 假定用若干个
是（ ）。
A.0000H
B.0600H
C.0700H
D.0800H
【答案】D 位的芯片组成一个8K ×8位的存储器, 则地址0B1FH 所在芯片的最小地址
【解析】由若干芯片构成存储器, 采用字和位同时扩展方法。8片
组2个芯片, 各组芯片的地址分配分别为:
第1组,
第3组, ; 第2组, ; 第4组, ; 。 位的芯片分成4组, 每
地址0BIFH 处于第2组内, 其芯片的最小地址为0800H 。
8． 对线性表进行折半查找时，要求线性表必须（ ）。
A. 以顺序方式存储
B. 以顺序方式存储，且数据元素有序
C. 以链接方式存储
D. 以链接方式存储，且数据元素有序
【答案】B
【解析】二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。折半查找方法适用于对以顺序方式存储的有序表的查找，查找效率较高。
9． 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
A. 顺序表
B. 双链表
C. 带头结点的双循环链表
D. 单循环链表
【答案】A
【解析】线性表采用顺序表，便于进行存取任一指定序号的元素；线性表采用链表，便于进
行插入和删除操作。但该题是在最后进行插入和删除运算，所以利用顺序表存储方式最节省时间。
10．若某文件系统索引结点(inode)中有直接地址项和间接地址项, 则下列选项中, 与单个文件长度无关的因素是（ ）
A. 索引结点的总数
B. 间接地址索引的级数
C. 地址项的个数
D. 文件块大小
【答案】A
【解析】根据文件长度与索引结构的关系可知, 只有选项A 是与单个文件长度无关的。
11．假设某系统总线在一个总线周期中并行传输4字节信息，一个总线周期占用2个时钟周期，总线时钟频率为10MHz ，则总线带宽是（ ）.
A.10MB/s
B.20MB/S
C.40MB/S
D.80MB/S
【答案】B
【解析】因为一个总线周期占用2个时钟周期，完成一个32位数据的传送. 总线时钟频率为10MHz ，时钟周期为，总线周期占用2个时钟周期，为＝一个总线周期中并行传输4字节信息，则总线带宽是＝20MB/s.
12．若用户1与用户2之间发送和接收电子邮件的过程如题40图所示, 则图中①、②、③阶段分别使用的应用层协议可以是（ ）。
图 电子邮件发送接收示意图
A.SMTP 、SMTP 、SMTP
B.POP3、SMTP 、POP3
C.POP3、SMTP 、SMTP
D.SMTP 、SMTP 、POP3
【答案】D 。
【解析】题中电子邮件的工作过程如下:
①用户1调用用户代理来编辑要发送的邮件, 用户代理用SMTP 将邮件传送给用户1的发送端邮件服务器。
②发送端邮件服务器也就是用户1的邮件服务器将邮件放入邮件缓存队列中, 等待发送。 ③运行在发送端邮件服务器的SMTP 客户进程, 发现在邮件缓存中有待发送的邮件, 就向运行在接收端邮件服务器也就是用户2的邮件服务器的SMTP 服务器进程发起TCP 连接建立。当TCP 连接建立后, SMTP 客户进程开始向远程的SMTP 服务器发送邮件。当所有的待发邮件发完了, SMTP 就关闭所建立的TCP 连接。
④运行在接收端邮件服务器中的SMTP 服务器进程收到邮件后, 将邮件放人收信人的用户邮箱中, 等待收信人在他方便时进行读取。收信人在打算收信时, 调用用户代理, 使用POP 协议将自己的邮件从接收端邮件服务器的用户邮箱中取回(如果邮箱中有来信的话) 。