2018年江苏大学理学院851数据结构之数据结构考研基础五套测试题
● 摘要
一、单项选择题
1． 若线性表最常用的操作是存取第I 个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（ ）。
A. 单链表 B. 双向链表 C. 单循环链表 D. 顺序表 【答案】D
【解析】线性表采用顺序表，便于进行存取任一指定序号的元素。
2． 某计算机的指令流水线由4个功能段组成，指令流经各功能段的时间(忽略各功能段之间的缓存时间) 分别为90ns 、80ns 、70ns 和60ns ，则该计算机的CPU 时钟周期至少是（ ）.
A.90ns B.80ns C.70ns D.60ns 【答案】A
【解析】对于各功能段执行时间不同的指令流水线，计算机的CPU 时钟周期应当以最长的功能段执行时间为准.
3． —个栈的入栈序列为1, 2, 3, ……, n , 其出栈序列是取值的个数是（ ）
A. B. C.
D. 无法确定
【答案】C
【解析】除了3本身以外, 其他的值均可以取到, 因此可能取值的个数为n-1。 4． 假定一台计算机的显示存储器用DRAM 芯片实现, 若要求显示分辨率为1600x1200, 颜色深度 为24位, 帧频为85Hz , 显存总带宽的50%用来刷新屏幕, 则需要的显存总带宽至少约为（ ）。
A.245Mbps B.979Mbps C.1958Mbps D.7834Mbps
。若, 则, 则可能
【答案】D
【解析】显存的容量＝分辨率×色深，带宽＝分辨率×色深×帧频，考虑到
的时间用来刷
新屏幕，故显存总带宽应加倍. 所以需要的显存总带宽至少约为:1600×l200×24×85×2＝7834Mbps.
5． 若用邻接矩阵存储有向图, 矩阵中主对角线以下的元素均为零, 则关于该图拓扑序列的结论是（ ）。
A. 存在, 且唯一 B. 存在, 且不唯一不唯一 C. 存在, 可能不唯一 D. 无法确定是否存在 【答案】C 。
【解析】图的基本应用--拓扑排序, 用邻接矩阵存储有向图, 矩阵中主对角线以下的元素均为零, 说明该图为有向无环图, 所以其拓扑序列存在, 但不一定唯一,
如图的邻接矩阵为在两个拓扑序列。
6． —个多道批处理系统中仅有P1和P2两个作业, P2比P1晚5ms 到达。它们的计算和作顺序如下:P1:计算60ms
,
, 计算20ms ; P2:计算120ms
,
不考虑调度和切换时间, 则完成两个作业需要的时间最少是（ ）。
A.240ms B.260ms C.340ms D.360ms
【答案】B 。
【解析】考查处理系统的性能计算, 由于P2比P1晚5ms 到达, P1先占用CPU , 根据P1和P2的执行过程, 作业运行的甘特图如下所示, 故答案为B 。
, 则存
操
, 计算40ms 若
7． 当字符序列
A.4个 B.5个 C.3个
图 甘特图
作为图输入时，输出长度为3的且可用作C 语言标识符的序列的有（ ）。
D.6个
图
【答案】C
【解析】首先需要明白C 语言标识符的命名规则。数字不能作为标识符的开头，因此第一个字符只能为t 或者下划线。若首字符为t ，有两种结果
因此总共有3种结果。
8． 下述文件中适合于磁带存储的是（ ）。
A. 顺序文件 B. 索引文件 C. 哈希文件 D. 多关键字文件 【答案】A
【解析】磁带存储是一种顺序存储，顺序文件(sequential file)是记录按其在文件中的逻辑顺序依次进入存储介质而建立的，即顺序文件中物理记录的顺序和逻辑记录的顺序是一致的。因此顺序文件适合磁带存储。
9． 若一棵二叉树的前序遍历序列和后序遍历序列分别为1, 2, 3, 4和4, 3, 2, 1, 则该二叉树的中序遍历序列不会是（ ）。
A.1, 2, 3, 4 B.2, 3, 4, 1 C.3, 2, 4, 1 D.4, 3, 2, 1
【答案】C
【解析】题目中的二叉树的先序序列和后序序列正好相反, 这样的二叉树每层只有一个结点。该二叉树的形态如下图所示。
和
，若首字符为，
则只有一种结果
从左至右, 这8棵二叉树的中序序列分别为: (1)4, 3, 2, 1,
相关内容
相关标签