数据结构 试卷 第 1 页 共 7 页 2016年4月高等教育自学考试全国统一命题考试
数据结构 试卷
(课程代码02331)
注意事项：
1．本试卷分为两部分，第一部分为选择题，第二部分为非选择题。
2．应考者必须按试题顺序在答题卡(纸)指定位置上作答，答在试卷上无效。
3．涂写部分、画图部分必须使用2B铅笔书写部分必须使用黑色字迹签字笔。
第一部分 选择题
一、单项选择题（本大题共15小题，每小题2分，共30分）
1．下列选项中，属于非线性数据结构的是（ ）
A．队列 B．栈 C．二叉排序树 D．线性表
2．瑞士计算机科学家沃思教授曾指出：算法+数据结构=程序．这里的数据结构指的是（ ）
A．数据的逻辑结构和存储结构 B．数据的线性结构和非线性结构
C．数据的紧凑结构和非紧凑结构 D．数据的顺序结构和链式结构
3．线性表顺序存储时，逻辑上相邻的两个数据元素，其存储地址（ ）
A．一定相邻 B．一定不相邻 C．不一定相邻 D．可能不相邻
4．数据元素1，2，3，4，5依次入栈，则不可能得到的出栈序列是（ ）
A．4，5，3，2，1 B．1，2，3，4，5
C．4，3，5，1，2 D．5，4，3，2，1
5．设顺序表首元素A[0]的存储地址是4000，每个数据元素占5个存储单元，则元素A[20]的起始存储地址是（ ）
A．4005 B．4020 C．4100 D．4105
6．广义表 A=(a，(b，c，(e，f)))，函数 head(head(tail(A)))的运算结果是（ ）
A．a B．b C．c D．e
7．设高度为h的二叉树中，只有度为0和2的结点，则此类二叉树包含的结点数至少是（ ）
A．2h B．2h-1 C．2h+1 D．h+1
8．—棵非空二叉树T的前序遍历和后序遍历序列正好相反，则T一定满足（ ）
A．所有结点均无左孩子 B．所有结点均无右孩子
09:00-11:30
14:30-17:0009:00-11:3000147 人力资源管理(一)00018 计算机应用基础00182 公共关系学
00163 管理心理学00107 现代管理学00277 行政管理学
00292 市政学00341 公文写作与处理03350 社会研究方法
12656 毛泽东思想和中国特色社会主义理论体系概论03706 思想道德修养与法律基础
00051 管理系统中计算机应用00054 管理学原理00070 政府与事业单位会计
00053 对外经济管理概论04184 线性代数(经管类)00078 银行会计学
00058 市场营销学04183 概率论与数理统计(经管类)00067 财务管理学
00068 外国财政
00139 西方经济学
03708 中国近现代史纲要
00051 管理系统中计算机应用00054 管理学原理00078 银行会计学
00053 对外经济管理概论00061 国家税收04183 概率论与数理统计(经管类)00058 市场营销学00076 国际金融
00067 财务管理学00150 金融理论与实务
00068 外国财政04184 线性代数(经管类)
03708 中国近现代史纲要
00051 管理系统中计算机应用00045 企业经济统计学00102 世界市场行情
00097 外贸英语写作00149 国际贸易理论与实务04183 概率论与数理统计(经管类)00100 国际运输与保险04184 线性代数(经管类)07750 国际投资学
03708 中国近现代史纲要05844 国际商务英语
00042 社会经济统计学原理00054 管理学原理00153 质量管理(一)
00051 管理系统中计算机应用00061 国家税收00154 企业管理咨询
00067 财务管理学00149 国际贸易理论与实务04183 概率论与数理统计(经管类)00151 企业经营战略00150 金融理论与实务
03708 中国近现代史纲要04184 线性代数(经管类)00042 社会经济统计学原理00061 国家税收00159 高级财务会计
02325计算机系统结构
复习题参考答案
1.评价储存系统的指标包括价格、命中率、等效访问时间。
2.计算机硬件和软件在逻辑功能上是等效大，在性能价格实现上是不同滴。
3.cache块大调度算法常有堆栽法和比较发。
4.计算机系统设计方法有由上而下、由下而上、由中间开始。其中，软硬结合较好是由中间开始。
5.系列机大软件兼容可分为向上、向下、向前、向后兼容；其中之一向上兼容是软件大根本特性。
6.在通到方式i/o传输过程中，用户由管态指令来使用外设，进管后cpu要编制通道程序。Cpu在执行完通道启动指令后，通道就能并行工作。
7. i/o控制方式分为：程序控制i/o、直接储存器访问dma和i/o处理机。
8.主存有1024页，分为s组，s=1024时成为全相联映像，s=1时则为直接映像。
9.解决cache与主存内容一致的算法是写回法和写直达法。
10.并行性的途径有资源共享、时间重叠和资源重叠。
二、1.冷启动时效率从cache为空开始到cache全满装满这一时期的失效率.
2.动态再定位: 在程序执行时，通过地址加法器将逻辑地址加上基址寄存器的程序基点地址形成物理地址后进行访存的方法.
3.Huffman压缩概念:将出现概率最大的事件用最少的位来表示，而概率最小的事件用较多位表示达到平均速度缩短.
4.Mimd：它使用多个控制器来异步地控制多个处理器，从而实现空间上的并行性.
5.Lru替换算法: 即最近最少使用页面置换算法，是选择近期最少访问页作为被替换的页.
6.仿真:用微程序直接解释另一种指令系统的方法.
7.并行算法:并行计算中非常重要的问题。并法研究应该确立一个“理论－设计－实现－应用”的系统方法，形成一个完善的 “架构—算法—编程” 方法论，这样才能保证并行算法不断发展并变得更加实用
8.中断：在运行一个程序的过程中，断续地以“插入”方式执行一些完成特定处理功能的程序段
三、解答题
1 / 318 第一章
计算机系统结构的基本概念
从处理数据的角度看，并行级别有位串字串，位并字串，位片串字并，全并行。位串字串和位并字串基本上构成了SIMD。位片串字并的例子有：相联处理机STARAN，MPP。全并行的例子有：阵列处理机ILLIAC
IV。
从加工信息 2 / 318 的角度看，并行级别有存储器操作并行，处理器操作步骤并行，处理器操作并行，指令、任务、作业并行。
存储器操作并行是指可以在一个存储周期内并行读出多个CPU字的，采用单体多字、多体单字或多体多字的交叉访问主存系统，进而采用按内容访问方式，位片串字并或全并行方 3 / 318 式，在一个主存周期内实现对存储器中大量字的高速并行操作。例子有并行存储器系统，以相联存储器为核心构成的相联处理机。
处理器操作步骤并行是指在并行性概念中引入时间因素，让多个处理过程在时间上错开，轮流重复地执行使用同一套设备的各个部分，加快硬件周转来赢得速 4 / 318 度。例子有流水线处理机。
处理器操作并行是指一个指令部件同时控制多个处理单元，实现一条指令对多个数据的操作。擅长对向量、数组进行处理。例子有阵列处理机。
指令、任务、作业并行是指多个独立的处理机分别执行各自的指令、任务、作业。例子有多处理机，计算机网络， 5 / 318 分布处理系统。
并行性的开发途径有时间重叠(Time
Interleaving)，资源重复(Resource
Replication)，资源共享(Resource
Sharing)。
时间重叠是指在并行性概念中引入时间因素，让多个处理过程在时间上错开，轮流重复地执行使用同一套设备的各个部 6 / 318 分，加快硬件周转来赢得速度。例子有流水线处理机。
资源重复是指一个指令部件同时控制多个处理单元，实现一条指令对多个数据的操作。例子有阵列处理机，相联处理机。
