计算机科学系《计算机系统结构》期末考试试卷（A卷）
2、此试卷适用于计算机科学与技术本科专业。
一单选题：(10分，每题1分)
1、."启动I/O"指令是主要的输入输出指令，是属于（ B ）
A.目态指令
B.管态指令
C.目态、管态都能用的指令
D.编译程序只能用的指令
2、输入输出系统硬件的功能对(B )是透明的
A.操作系统程序员
B.应用程序员
C.系统结构设计人员
D.机器语言程序设计员
3、全相联地址映象是指（A）
A.任何虚页都可装入主存中任何实页的位置
B.一个虚页只装进固定的主存实页位置
C.组之间固定，组内任何虚页可装入任何实页位置
D.组间可任意装入，组内是固定装入
4、( C ) 属于MIMD系统结构
A.各处理单元同时受一个控制单元的管理
B.各处理单元同时受同个控制单元送来的指令
C.松耦合多处理机和多计算机系统
D.阵列处理机
5、多处理机上两个程序段之间若有先写后读的数据相关，则（B ）
A.可以并行执行
B.不可能并行
C.任何情况均可交换串行
D.必须并行执行
6、计算机使用的语言是（B）
A.专属软件范畴，与计算机体系结构无关
B.分属于计算机系统各个层次
C.属于用以建立一个用户的应用环境
D.属于符号化的机器指令
7、指令执行结果出现异常引起的中断是（C ）
A.输入/输出中断
B.机器校验中断
C.程序性中断
D.外部中断
8、块冲突概率最高的Cache地址映象方式是（A ）
A．直接 B．组相联 C．段相联 D．全相联
9、组相联映象、LRU替换的Cache存储器，不影响Cache命中率的是(B ) A．增大块的大小 B．增大主存容量 C．增大组的大小 D．增加Cache中的块数
10、流水处理机对全局性相关的处理不．包括（C）
A.猜测法
B.提前形成条件码
C.加快短循环程序的执行
D.设置相关专用通路
二填空题：（20分，每题2分）
1、数据通路宽度就是数据总线上一次并行传送的信息位数。
2、计算机仿真用微程序解释，计算机模拟用机器语言解释
3、阵列处理机按存贮器的组成方式可分为两种构形,分别为: 分布式存储器
和集中共享式。
4、按弗林的观点，计算机系统可分为 SISD 、 SIMD 、
MISD 和 MIMD 四大类
5、浮点数尾数的下溢处理方法有：截断法, 舍入法, 恒置1法, 查表舍入法。
6、流水线消除速度瓶颈的方法有瓶颈子过程_ 拆分_和瓶颈子过程_并联_ ____两种。
7、具有相同“系统结构”（如指令系统相同）的计算机可以因为速度要求等因素
的不同而采用计算机组成。
8.在非线性流水线机器中, 可能发生的数据相关有: 先读后写相关 , 写写相关
和先写后读相关。
8、互连网络的交换方法主要有线路交换、包交换、线路/包交换，SIMD互连网络
多采用线交换，多处理机常采用包交换。
9、Cache存储器写操作时，只写入Cache，仅当需要块替换时，才将其写回主存，称这种修改主存块内容的方法为__写回法____。
三简答题：（40分，每题4分）
1．计算机系统结构研究的是什么？
软、硬件之间的功能分配以及对传统机器级界面的确定。
2．计算机组成和计算机实现有什么关系？
计算机组成指的是计算机系统结构的逻辑实现。计算机实现指的是计算机组成的物理实现。计算机组成和计算机实现关系密切, 有人将它们和称为计算机实现。
3．器件的发展对系统结构的影响？
器件的发展改变了逻辑设计的传统方法。器件的发展也使系统结构的“下移”速度加快。
器件的发展还促进了算法、语言和软件的发展。
4．解决计算机主存与CPU的速度差对机器性能的影响，可采用哪些解决方法?
设置Cache, 采用并行主存系统
5.简述设计RISC结构使用的基本技术。
(1)按设计RISC的一般原则来设计 (2)逻辑实现上采用硬联和微程序相结合 (3)设置
大量工作寄存器并采用重叠寄存器窗口 (4)指令用流水和延迟转移 (5) 采用Cache (6)优化设计编译系统
6.什么是软件的可移植性?
软件不修改或只经少量修改就可由一台机器移植到另一台机器上运行
7.请解释说明常用的4种基本单级互联网络.
立方体单级网络, PM2I网络, 混洗交换单级网络, 蝶形单级网络
8.什么是中断响应次序和处理次序?
中断响应次序是在同时发生多个不同种类的中断请求时,中断响应硬件中排队器所决定的响应次序. 处理次序是各个中断请求实际被处理完毕的顺序.
9.请解释存储系统和存储体系的区别.
存储系统是将多种不同工艺的存储器组织在一起, 但从逻辑上还不能成为一个整体.
而存储体系就是从程序员角度来看, 各种不同工艺的存储器在逻辑上是一个整体.
10.请说明一次重叠中通用寄存器组相关的处理办法.
处理办法有推后读和设置相关通路
四计算题：（30分，每题6分）
1. 经统计, 某机器14条指令的使用频率分别为: 0.01, 0.15, 0.12, 0.03, 0.02,
0.04, 0.02,
0.04, 0.01, 0.13, 0.15, 0.14, 0.11, 0.03。请分别求出用等长码, 哈夫曼码, 只
有两种码长的扩展操作码的操作码平均码长。
等长码码长为４位，哈夫曼码平均码长为３.３８位，两种码长的扩展操作码的操作码平均码长为３.４位
2. 设有两个向量C和D，各有4个元素，在图中的静态双功能流水线上工作。其中，
1->2->3->5组成加法流水线，1->4->5组成乘法流水线。设每个流水线所经过的时间均为Δt，而且流水线的输出结果可以直接返回到输入或暂存于相应的缓冲寄存器中，其延迟时间和功能切换所需要的时间都可以忽略不计。求：该流水线的实际吞吐率TP和效率η。
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 时间Δt
实际吞吐率TP=7/（15Δt）
η=32%
3. 在一个5段的流水线处理机上需经9拍才能完成一个任务，其预约表如下表所
示。
(1)分别写出延迟禁止表F、初始冲突向量C；(2)画出流水线状态转移图；(3)求出
最小平均延迟、调度最佳方案。
分别写出延迟禁止表F = {1, 5, 6, 8},
初始冲突向量C = {1 0 1 1 0 0 0 1 },
流水线状态转移图
最小平均延迟: 3.5拍调度最佳方案（３，４）
4. 如果设一个系统有四个中断级，中断响应次序为1->2->3->4。现要求中断处理次序改为1->4->3->2, (1)请画出中断级屏蔽位表。(2) 如果在运行用户程序的过程中同时发生了1,2,3,4 级中断, 请画出此程序运行过程示意图。(3) 如果在运行用户程序的过程中同时发生了2,3级中断, 而在3级中断未处理完毕又发生了4级中断, 最后回到用户程序时又同时发生了1,2级中断, 请画出此程序运行过程示意图。
（１）
（２）（３）
5. 计算多级立方体互连网络。见图N=8多级立方体互连网络，求当输入端级控制信
号为S2S1S0=010时，输入端为0 1 2 3 4 5 6 7时，输出端为： 23016745 。Array计算机科学系《计算机系统结构》期末考试试卷（B卷）
年级：＿＿＿专业：＿＿＿＿＿班级：＿学号：＿＿＿姓名：＿＿＿＿＿
2、此试卷适用于计算机科学与技术本科专业。
一单选题：(10分，每题1分)
. 计算机中优化使用的操作码编码方法是（ D ）
A. 哈夫曼编码
B. ASCII码
C. BCD码
D. 扩展操作码
12、对系统程序员不透明的应当是( B )
A. Cache存储器
B. 虚拟存储器
C. 指令缓冲寄存器
D. 数据通路宽度
13、全相联地址映象是指（A）
A.任何虚页都可装入主存中任何实页的位置
B.一个虚页只装进固定的主存实页位置
C.组之间固定，组内任何虚页可装入任何实页位置
D.组间可任意装入，组内是固定装入
14、( C ) 属于MIMD系统结构
A.各处理单元同时受一个控制单元的管理
B.各处理单元同时受同个控制单元送来的指令
C.松耦合多处理机和多计算机系统
D.阵列处理机
15、多处理机上两个程序段之间若有先写后读的数据相关，则（B ）
A.可以并行执行
B.不可能并行
C.任何情况均可交换串行
D.必须并行执行
16、系列机软件必须保证（ C ）
A. 向前兼容，并向上兼容
B. 向前兼容，并向下兼容
C. 向后兼容，力争向上兼容
D. 向后兼容，力争向下兼容
17、指令执行结果出现异常引起的中断是（C ）
A.输入/输出中断
B.机器校验中断
C.程序性中断
D.外部中断
18、在Cache存储器中常用的地址映象方式是（C ）
A．全相联映象 B．页表法映象 C．组相联映象 D．段页表映象
19、组相联映象、LRU替换的Cache存储器，不影响Cache命中率的是(B ) A．增大块的大小 B．增大主存容量 C．增大组的大小 D．增加Cache中的块数
20、流水处理机对全局性相关的处理不．包括（D）
A.猜测法
B.提前形成条件码
C.加快短循环程序的执行
D.设置相关专用通路
二填空题：（20分，每题2分）
10、数据宽度就是Ｉ／Ｏ设备取得Ｉ／Ｏ总线后所传送数据的总
量。
11、计算机仿真用微程序解释，计算机模拟用机器语言解释
12、固件就是一种具有软件功能的硬
件。
13、按弗林的观点，计算机系统可分为SISD 、SIMD 、
MISD 和 MIMD 四大类
14、浮点数尾数的下溢处理方法有：截断法, 舍入法, 恒置1法, 查表舍入
法。
15、实现软件移植的基本技术有同一高级语言，采用系列机，模拟和仿真。
16、并行主存系统包括单体多字，多体单字和多体多字交叉存储器。
17、在非线性流水线机器中, 可能发生的数据相关有: 先读后写相关 , 写写相关
和先写后读相关。
18、互连网络的交换方法主要有线路交换、包交换、线路/包交换，SIMD互连网络多采用线交换，多处理机常采用包交换。
19、Cache存储器写操作时，在写入Cache的同时将其写回主存，称这种修改主存块内容的方法为__写直达法____。
三简答题：（40分，每题4分）
5．计算机系统结构研究的是什么？
软、硬件之间的功能分配以及对传统机器级界面的确定。
6．计算机组成设计要解决的问题是什么？
在所希望能达到的性能和价格比的前提下，怎样最佳、最合理地把各种设备和部件组织成为一台计算机，以实现所确定的系统结构。
7．举例说明几种指令级高度并行的超级处理机？
超标量处理机、超长指令字处理机、超流水线处理机、超标量超流水线处理机
8．解决计算机主存与CPU的速度差对机器性能的影响，可采用哪些解决方法?
设置Cache, 采用并行主存系统
11.CISC指令系统的含义?
复杂指令系统计算机，即机器指令系统变得越来越庞杂，这就是所谓的CISC指令系统。
12.什么是软件的可移植性?
软件不修改或只经少量修改就可由一台机器移植到另一台机器上运行
13.请解释说明常用的4种基本单级互联网络.
立方体单级网络, PM2I网络, 混洗交换单级网络, 蝶形单级网络
14.什么是并行性？
只要在同一时刻或是在同一时间间隔内完成两种或两种以上性质相同或不同的工作，它们在时间上能相互重叠，都体现了并行性。
15.请解释存储系统和存储体系的区别.
存储系统是将多种不同工艺的存储器组织在一起, 但从逻辑上还不能成为一个整体. 而存储体系就是从程序员角度来看, 各种不同工艺的存储器在逻辑上是一个整体.
16.请说明一次重叠中通用寄存器组相关的处理办法.
处理办法有推后读和设置相关通路
四计算题：（30分，每题6分）
1. 设一台模型机有7条指令，其使用频度为：
指令使用频度 | 指令使用频度
I1 0.03 | I4 0.05
I2 0.03 | I5 0.15
I3 0.04 | I6 0.3
| I7 0.4
2. 设有两个向量C和D，各有4个元素，在图中的静态双功能流水线上工作。其中，1->2->3->5组成加法流水线，1->4->5组成乘法流水线。设每个流水线所经过的时间均为Δt，而且流水线的输出结果可以直接返回到输入或暂存于相应的缓冲寄存器中，其延迟时间和功能切换所需要的时间都可以忽略不计。求：该流水线的实际吞吐率TP和效率η。
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 时间Δt
实际吞吐率TP=7/（15Δt）
η=32%
3. 在一个5段的流水线处理机上需经9拍才能完成一个任务，其预约表如下表所
示。
(1)分别写出延迟禁止表F、初始冲突向量C；(2)画出流水线状态转移图；(3)求出
最小平均延迟、调度最佳方案。
分别写出延迟禁止表F = {1, 5, 6, 8},
初始冲突向量C = {1 0 1 1 0 0 0 1 },
流水线状态转移图
最小平均延迟: 3.5拍调度最佳方案（３，４）
4. 若机器共有5级中断，中断响应优先次序为l→2→3→4→5，现要求其实际的中断
处理次序为l→4→5→2→3。(1) 设计各级中断处理程序的中断级屏蔽位(令“1”对应于屏蔽，“0”对应于开放)；(2) 若在运行用户程序时，同时出现第4、2级中断请求，而在处理第2级中断未完成时，又同时出现第l、3、5级中断请求，请画出此程序运行过程示意图。
5. 计算多级立方体互连网络。见图N=8多级立方体互连网络，求当输入端级控制信号为S2S1S0=010时，输入端为0 1 2 3 4 5 6 7时，输出端为： 23016745 。
实验二指令流水线相关性分析 ·实验目的 通过使用WINDLX模拟器，对程序中的三种相关现象进行观察，并对使用专用通路，增加运算部件等技术对性能的影响进行考察，加深对流水线和RISC处理器的特点的理解。 ·实验原理： 指令流水线中主要有结构相关、数据相关、控制相关。相关影响流水线性能。·实验步骤 一．使用WinDLX模拟器，对做如下分析： （1）观察程序中出现的数据/控制/结构相关。指出程序中出现上述现象的指令组合。 （2）考察增加浮点运算部件对性能的影响。 （3）考察增加forward部件对性能的影响。 （4）观察转移指令在转移成功和转移不成功时候的流水线开销。 ·实验过程 一．使用WinDLX模拟器，对做如下分析： } 浮点加、乘、除部件都设置为1，浮点数运算部件的延时都设置为4，如图1： 图1 初始设置 将和加载至WinDLX中，如图2示。
图2 加载程序 1.观察程序中出现的数据/控制/结构相关；指出程序中出现上述现象的指令组合。 1）数据相关 点击F7，使程序单步执行，当出现R-Stall时停止，运行过程中出现下图3所示，输入整数6。 图3 输入整数6 @ 打开Clock Diagram，可以清楚的看到指令执行的流水线如图4所示。 图4 指令流水线 双击第一次出现R-Stall的指令行，如图5所示。
图5 指令详细信息 对以上出现的情况分析如下： 程序发生了数据相关，R-Stall（R-暂停）表示引起暂停的原因是RAW。 lbu r3,0×0(r2) 要在WB周期写回r3中的数据；而下一条指令 & seqi r5,r3,0×a 要在intEX周期中读取r3中的数据。 上述过程发生了WR冲突，即写读相关。为了避免此类冲突， seq r5,r4,0×a的intEX指令延迟了一个周期进行。 由此，相关指令为： 2）控制相关 由图6可以看出，在第4时钟周期：第一条指令处于MEM段，第二条命令处于intEX段，第三条指令出于aborted状态，第四条命令处于IF段。 图 6 指令流水线 }
一、解答题（满分30分，每小题5分） 1. 怎样理解数据挖掘和知识发现的关系？请详细阐述之 首先从数据源中抽取感兴趣的数据，并把它组织成适合挖掘的数据组织形式；然后，调用相应的算法生成所需的知识；最后对生成的知识模式进行评估，并把有价值的知识集成到企业的智能系统中。 知识发现是一个指出数据中有效、崭新、潜在的、有价值的、一个不可忽视的流程，其最终目标是掌握数据的模式。流程步骤：先理解要应用的领域、熟悉相关知识，接着建立目标数据集，并专注所选择的数据子集；再作数据预处理，剔除错误或不一致的数据；然后进行数据简化与转换工作；再通过数据挖掘的技术程序成为模式、做回归分析或找出分类模型；最后经过解释和评价成为有用的信息。 2. 时间序列数据挖掘的方法有哪些，请详细阐述之 时间序列数据挖掘的方法有： 1）、确定性时间序列预测方法:对于平稳变化特征的时间序列来说，假设未来行为与现在的行为有关，利用属性现在的值预测将来的值是可行的。例如，要预测下周某种商品的销售额，可以用最近一段时间的实际销售量来建立预测模型。 2）、随机时间序列预测方法:通过建立随机模型，对随机时间序列进行分析，可以预测未来值。若时间序列是平稳的，可以用自回归(Auto Regressive，简称AR)模型、移动回归模型(Moving Average，简称MA)或自回归移动平均(Auto Regressive Moving Average，简称ARMA)模型进行分析预测。 3）、其他方法:可用于时间序列预测的方法很多，其中比较成功的是神经网络。由于大量的时间序列是非平稳的，因此特征参数和数据分布随着时间的推移而变化。假如通过对某段历史数据的训练，通过数学统计模型估计神经网络的各层权重参数初值，就可能建立神经网络预测模型，用于时间序列的预测。
实验二结构相关 一、实验目得: 通过本实验,加深对结构相关得理解,了解结构相关对CPU性能得影响。 二、实验内容: 1、用WinDLX模拟器运行程序structure_d、s 。 2、通过模拟,找出存在结构相关得指令对以及导致结构相关得部件。 3、记录由结构相关引起得暂停时钟周期数,计算暂停时钟周期数占总执行 周期数得百分比。 4、论述结构相关对CPU性能得影响,讨论解决结构相关得方法。 三、实验程序structure_d、s LHI R2, (A>>16)&0xFFFF 数据相关 ADDUI R2, R2, A&0xFFFF LHI R3, (B>>16)&0xFFFF ADDUI R3, R3, B&0xFFFF ADDU R4, R0, R3 loop: LD F0, 0(R2) LD F4, 0(R3) ADDD F0, F0, F4 ;浮点运算,两个周期,结构相关 ADDD F2, F0, F2 ; < A stall is found (an example of how to answer your questions) ADDI R2, R2, #8 ADDI R3, R3, #8 SUB R5, R4, R2 BNEZ R5, loop ;条件跳转 TRAP #0 ;; Exit < this is a ment !! A: 、double 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 B: 、double 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 四、实验过程 打开软件,load structure_d、s文件,进行单步运行。经过分析,此程序一 次循环中共有五次结构相关。(Rstall 数据相关Stall 结构相关) 1)第一个结构相关:addd f2,,f0,f2 由于前面得数据相关,导致上一条指令addd f0,f0,f4暂停在ID阶段,所以下一条指令addd f2,,f0,f2发生结构相关,导致相关得部件:译码部件。
2017年数据结构期末考试题及答案 一、选择题（共计50分，每题2分，共25题） 1 ?在数据结构中，从逻辑上可以把数据结构分为 C 。 A. 动态结构和静态结构B?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2?数据结构在计算机内存中的表示是指 A ° A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D .数据元 素之间的关系 3.在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A. 逻辑B?存储 C.逻辑和存储 D.物理 4 .在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C ° A.数据的处理方法B?数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5. 在决定选取何种存储结构时，一般不考虑 A ° A.各结点的值如何B?结点个数的多少 C?对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6. 以下说法正确的是D ° A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据可以有相同的逻辑结构 7. 在以下的叙述中，正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出
8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一 个结点，则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点 的双循环链表 11. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点（由p所指向）满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点
一、名词解释 1.数据仓库：是一种新的数据处理体系结构.是面向主题的、集成的、不可更新的(稳定性)、 随时间不断变化(不同时间)的数据集合.为企业决策支持系统提供所需的集成信息。 2.孤立点：指数据库中包含的一些与数据的一般行为或模型不一致的异常数据。 3.OLAP：OLAP是在OLTP的基础上发展起来的.以数据仓库为基础的数据分析处理.是共享多 维信息的快速分析.是被专门设计用于支持复杂的分析操作.侧重对分析人员和高层管理人员的决策支持。 4.粒度：指数据仓库的数据单位中保存数据细化或综合程度的级别。粒度影响存放在数据 仓库中的数据量的大小.同时影响数据仓库所能回答查询问题的细节程度。 5.数据规范化：指将数据按比例缩放(如更换大单位).使之落入一个特定的区域（如0－1） 以提高数据挖掘效率的方法。规范化的常用方法有：最大－最小规范化、零－均值规范化、小数定标规范化。 6.关联知识：是反映一个事件和其他事件之间依赖或相互关联的知识。如果两项或多项属 性之间存在关联.那么其中一项的属性值就可以依据其他属性值进行预测。 7.数据挖掘：从大量的、不完全的、有噪声的、模糊的、随机的数据中.提取隐含在其中的、 人们事先不知道的、但又是潜在有用的信息和知识的过程。 8.OLTP：OLTP为联机事务处理的缩写.OLAP是联机分析处理的缩写。前者是以数据库为基 础的.面对的是操作人员和低层管理人员.对基本数据进行查询和增、删、改等处理。 9.ROLAP：是基于关系数据库存储方式的.在这种结构中.多维数据被映像成二维关系表.通 常采用星型或雪花型架构.由一个事实表和多个维度表构成。 10.MOLAP：是基于类似于“超立方”块的OLAP存储结构.由许多经压缩的、类似于多维数组 的对象构成.并带有高度压缩的索引及指针结构.通过直接偏移计算进行存取。 11.数据归约：缩小数据的取值范围.使其更适合于数据挖掘算法的需要.并且能够得到和原 始数据相同的分析结果。 12.广义知识：通过对大量数据的归纳、概括和抽象.提炼出带有普遍性的、概括性的描述统 计的知识。 13.预测型知识：是根据时间序列型数据.由历史的和当前的数据去推测未来的数据.也可以 认为是以时间为关键属性的关联知识。 14.偏差型知识：是对差异和极端特例的描述.用于揭示事物偏离常规的异常现象.如标准类 外的特例.数据聚类外的离群值等。 15.遗传算法：是一种优化搜索算法.它首先产生一个初始可行解群体.然后对这个群体通过 模拟生物进化的选择、交叉、变异等遗传操作遗传到下一代群体.并最终达到全局最优。 16.聚类：是将物理或抽象对象的集合分组成为多个类或簇(cluster)的过程.使得在同一个 簇中的对象之间具有较高的相似度.而不同簇中的对象差别较大。 17.决策树：是用样本的属性作为结点.用属性的取值作为分支的树结构。它是分类规则挖掘 的典型方法.可用于对新样本进行分类。 18.相异度矩阵：是聚类分析中用于表示各对象之间相异度的一种矩阵.n个对象的相异度矩 阵是一个nn维的单模矩阵.其对角线元素均为0.对角线两侧元素的值相同。 19.频繁项集：指满足最小支持度的项集.是挖掘关联规则的基本条件之一。 20.支持度：规则A→B的支持度指的是所有事件中A与B同地发生的的概率.即P(A∪B).是 AB同时发生的次数与事件总次数之比。支持度是对关联规则重要性的衡量。 21.可信度：规则A→B的可信度指的是包含A项集的同时也包含B项集的条件概率P(B|A).
一、填空题 1.Web挖掘可分为、和3大类。 2.数据仓库需要统一数据源，包括统一、统一、统一和统一数据特征 4个方面。 3.数据分割通常按时间、、、以及组合方法进行。 4.噪声数据处理的方法主要有、和。 5.数值归约的常用方法有、、、和对数模型等。 6.评价关联规则的2个主要指标是和。 7.多维数据集通常采用或雪花型架构，以表为中心，连接多个表。 8.决策树是用作为结点，用作为分支的树结构。 9.关联可分为简单关联、和。 10.B P神经网络的作用函数通常为区间的。 11.数据挖掘的过程主要包括确定业务对象、、、及知识同化等几个步 骤。 12.数据挖掘技术主要涉及、和3个技术领域。 13.数据挖掘的主要功能包括、、、、趋势分析、孤立点分析和偏 差分析7个方面。 14.人工神经网络具有和等特点，其结构模型包括、和自组织网络 3种。 15.数据仓库数据的4个基本特征是、、非易失、随时间变化。 16.数据仓库的数据通常划分为、、和等几个级别。 17.数据预处理的主要内容(方法)包括、、和数据归约等。 18.平滑分箱数据的方法主要有、和。 19.数据挖掘发现知识的类型主要有广义知识、、、和偏差型知识五种。 20.O LAP的数据组织方式主要有和两种。 21.常见的OLAP多维数据分析包括、、和旋转等操作。 22.传统的决策支持系统是以和驱动，而新决策支持系统则是以、建 立在和技术之上。 23.O LAP的数据组织方式主要有和2种。 24.S QL Server2000的OLAP组件叫，OLAP操作窗口叫。 25.B P神经网络由、以及一或多个结点组成。 26.遗传算法包括、、3个基本算子。 27.聚类分析的数据通常可分为区间标度变量、、、、序数型以及混合 类型等。 28.聚类分析中最常用的距离计算公式有、、等。 29.基于划分的聚类算法有和。
第二章算法分析 1.算法分析是计算机科学的基础 2.增长函数表示问题（n）大小与我们希望最优化的值之间的关系。该函数表示了该算法的时间复杂度或空间复杂度。增长函数表示与该问题大小相对应的时间或空间的使用 3.渐进复杂度：随着n的增加时增长函数的一般性质，这一特性基于该表达式的主项，即n 增加时表达式中增长最快的那一项。 4.渐进复杂度称为算法的阶次，算法的阶次是忽略该算法的增长函数中的常量和其他次要项，只保留主项而得出来的。算法的阶次为增长函数提供了一个上界。 5.渐进复杂度：增长函数的界限，由增长函数的主项确定的。渐进复杂度类似的函数，归为相同类型的函数。 6.只有可运行的语句才会增加时间复杂度。 7. O() 或者大O记法：与问题大小无关、执行时间恒定的增长函数称为具有O（1）的复杂度。 增长函数阶次 t(n)=17 O(1) t(n)=3log n O(log n) t(n)=20n-4 O(n) t(n)=12n log n + 100n O(n log n) t(n)=3n2+ 5n - 2 O(n2) t(n)=8n3+ 3n2O(n3) t(n)=2n+ 18n2+3n O(2n) 8.所有具有相同阶次的算法，从运行效率的角度来说都是等价的。 9.如果算法的运行效率低，从长远来说，使用更快的处理器也无济于事。 10.要分析循环运行，首先要确定该循环体的阶次n，然后用该循环要运行的次数乘以它。（n 表示的是问题的大小） 11.分析嵌套循环的复杂度时，必须将内层和外层循环都考虑进来。 12.方法调用的复杂度分析： 如：public void printsum(int count){ int sum = 0 ; for (int I = 1 ; I < count ; I++) sum += I ; System.out.println(sun); } printsum方法的复杂度为O（n）,计算调用该方法的初始循环的时间复杂度，只需把printsum方法的复杂度乘以该循环运行的次数即可。所以调用上面实现的printsum方法的复 杂度为O（n2）。 13指数函数增长> 幂函数增长> 对数函数增长
单选题 1. 某超市研究销售纪录数据后发现，买啤酒的人很大概率也会购买尿布，这种属于数据挖掘的哪类问题？(A) A. 关联规则发现 B. 聚类 C. 分类 D. 自然语言处理 2. 以下两种描述分别对应哪两种对分类算法的评价标准？(A) (a)警察抓小偷，描述警察抓的人中有多少个是小偷的标准。 (b)描述有多少比例的小偷给警察抓了的标准。 A. Precision, Recall B. Recall, Precision A. Precision, ROC D. Recall, ROC 3. 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务？(C) A. 频繁模式挖掘 B. 分类和预测 C. 数据预处理 D. 数据流挖掘 4. 当不知道数据所带标签时，可以使用哪种技术促使带同类标签的数据与带其他标签的数据相分离？(B) A. 分类 B. 聚类 C. 关联分析 D. 隐马尔可夫链 5. 什么是KDD？(A) A. 数据挖掘与知识发现 B. 领域知识发现 C. 文档知识发现 D. 动态知识发现 6. 使用交互式的和可视化的技术，对数据进行探索属于数据挖掘的哪一类任务？（A） A. 探索性数据分析 B. 建模描述 C. 预测建模 D. 寻找模式和规则 7. 为数据的总体分布建模；把多维空间划分成组等问题属于数据挖掘的哪一类任务？(B) A. 探索性数据分析 B. 建模描述 C. 预测建模 D. 寻找模式和规则 8. 建立一个模型，通过这个模型根据已知的变量值来预测其他某个变量值属于数据挖掘的哪一类任务？(C) A. 根据内容检索 B. 建模描述 C. 预测建模 D. 寻找模式和规则 9. 用户有一种感兴趣的模式并且希望在数据集中找到相似的模式，属于数据挖掘哪一类任务？(A) A. 根据内容检索 B. 建模描述 C. 预测建模 D. 寻找模式和规则 11.下面哪种不属于数据预处理的方法？(D) A变量代换B离散化 C 聚集 D 估计遗漏值 12. 假设12个销售价格记录组已经排序如下：5, 10, 11, 13, 15, 35, 50, 55, 72, 92, 204, 215 使用如下每种方法将它们划分成四个箱。等频（等深）划分时，15在第几个箱子内？(B) A 第一个 B 第二个 C 第三个 D 第四个 13.上题中，等宽划分时（宽度为50），15又在哪个箱子里？(A) A 第一个 B 第二个 C 第三个 D 第四个 14.下面哪个不属于数据的属性类型：(D) A 标称 B 序数 C 区间D相异 15. 在上题中，属于定量的属性类型是：(C) A 标称 B 序数C区间 D 相异 16. 只有非零值才重要的二元属性被称作：( C )
2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（A） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B） A.（100,80,90,60,120,110,130） B.（100, 120, 110,130,80, 60,90） C.（100,60,80,90,120,110,130） D.（100,80, 60,90, 120, 130,110） 9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（B ） A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（D） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序
北京邮电大学 实验报告 课程名称计算机系统结构 计算机学院03班 王陈(11)
目录 实验一WINDLX模拟器安装及使用......................................... 错误!未定义书签。 ·实验准备................................................................................ 错误!未定义书签。 ·实验环境................................................................................ 错误!未定义书签。 ·实验步骤................................................................................ 错误!未定义书签。 ·实验内容及要求.................................................................... 错误!未定义书签。 ·实验过程............................................................................. 错误!未定义书签。 ·实验总结............................................................................. 错误!未定义书签。实验二指令流水线相关性分析 ............................................... 错误!未定义书签。 ·实验目的............................................................................. 错误!未定义书签。 ·实验环境................................................................................ 错误!未定义书签。 ·实验步骤................................................................................ 错误!未定义书签。 ·实验过程............................................................................. 错误!未定义书签。 ·实验总结............................................................................. 错误!未定义书签。实验三DLX处理器程序设计 .................................................... 错误!未定义书签。 ·实验目的............................................................................. 错误!未定义书签。 ·实验环境................................................................................ 错误!未定义书签。 ·实验步骤................................................................................ 错误!未定义书签。 ·实验过程............................................................................. 错误!未定义书签。 A.向量加法代码及性能分析 ................................................... 错误!未定义书签。 B.双精度浮点加法求和代码及结果分析 .............................. 错误!未定义书签。 ·实验总结............................................................................. 错误!未定义书签。实验四代码优化 ....................................................................... 错误!未定义书签。 ·实验目的............................................................................. 错误!未定义书签。 ·实验环境................................................................................ 错误!未定义书签。 ·实验原理................................................................................ 错误!未定义书签。 ·实验步骤................................................................................ 错误!未定义书签。 ·实验过程............................................................................. 错误!未定义书签。 ·实验总结+实习体会........................................................... 错误!未定义书签。实验五循环展开 ....................................................................... 错误!未定义书签。 ·实验目的............................................................................. 错误!未定义书签。 ·实验环境................................................................................ 错误!未定义书签。 ·实验原理................................................................................ 错误!未定义书签。 ·实验步骤................................................................................ 错误!未定义书签。 ·实验过程............................................................................. 错误!未定义书签。 矩阵乘程序代码清单及注释说明........................................... 错误!未定义书签。 相关性分析结果........................................................................... 错误!未定义书签。 增加浮点运算部件对性能的影响........................................... 错误!未定义书签。 增加forward部件对性能的影响 ............................................ 错误!未定义书签。 转移指令在转移成功和转移不成功时候的流水线开销 .. 错误!未定义书签。 ·实验总结+实习体会+课程建议......................................... 错误!未定义书签。
1.某超市研究销售纪录数据后发现，买啤酒的人很大概率也会购买尿布，这种属于数据挖掘的哪类问题？A A. 关联规则发现 B. 聚类 C. 分类 D. 自然语言处理 2.以下两种描述分别对应哪两种对分类算法的评价标准？A (a)警察抓小偷，描述警察抓的人中有多少个是小偷的标准。 (b)描述有多少比例的小偷给警察抓了的标准。 A. Precision, Recall B. Recall, Precision C. Precision, ROC D. Recall, ROC 3.将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务？C A. 频繁模式挖掘 B. 分类和预测 页脚内容1
C. 数据预处理 D. 数据流挖掘 4.当不知道数据所带标签时，可以使用哪种技术促使带同类标签的数据与带其他标签的数据相分离？B A. 分类 B. 聚类 C. 关联分析 D. 隐马尔可夫链 5. 什么是KDD？A A. 数据挖掘与知识发现 B. 领域知识发现 C. 文档知识发现 D. 动态知识发现 6.使用交互式的和可视化的技术，对数据进行探索属于数据挖掘的哪一类任务？A A. 探索性数据分析 B. 建模描述 C. 预测建模 页脚内容2
D. 寻找模式和规则 7.为数据的总体分布建模；把多维空间划分成组等问题属于数据挖掘的哪一类任务？B A. 探索性数据分析 B. 建模描述 C. 预测建模 D. 寻找模式和规则 8.建立一个模型，通过这个模型根据已知的变量值来预测其他某个变量值属于数据挖掘的哪一类任务？C A. 根据内容检索 B. 建模描述 C. 预测建模 D. 寻找模式和规则 9.用户有一种感兴趣的模式并且希望在数据集中找到相似的模式，属于数据挖掘哪一类任务？ A. 根据内容检索 B. 建模描述 C. 预测建模 D. 寻找模式和规则 页脚内容3
2017《数据结构》期末考试试题及答案 《数据结构》期末考试试题及答案 1 ................................................................. 2..试题 1 答案............................................................ 7..《数据结构》期末考试试题及答案 2 ................................................................. 9..试题 2 答案........................................................................ 1.. 4. 《数据结构》期末考试试题及答案 3 ............................................................... 1..6试题 3 答案........................................................................ 2.. 1.
数据结构》期末考试试题及答案 1 单选题（每题 2 分，共 20 分） 1. 栈和队列的共同特点是 （ ）。 A. 只允许在端点处插入和删除元素 B. 都是先进后出 C. 都是先进先出 D. 没有共同点 2. 用链接方式存储的队列，在进行插入运算时 （ ）. A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D .头、尾指针可能都要修改 3. 以下数据结构中哪一个是非线性结构？ （ ） A. 队列 B. 栈 C. 线性表 D. 二叉树 4. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644（io ）, A[2][2]存放 若有18个元素的有序表存放在一维数组 A[19]中，第一个元素放A[1]中, 现进行二分查找，则查找 A [3]的比较序列的下标依次为（ A. 1 ， 2， 3 B. 9， 5， 2， 3 C. 9， 5， 3 D. 9， 4， 2， 3 8. 对n 个记录的文件进行快速排序，所需要的辅助存储空间大致为 A. O （1） B. O （n ） C. O （ 1 og 2n ） D. O （n2） 9. 对于线性表（ 7， 34， 55， 25， 64， 46， 20， 10）进行散列存储时，若选 用 H （K ）=K %9 作为散列函数，则散列地址为 1 的元素有（ ）个， 位置在 676（10），每个元素占一个空间， 表示用 10 进制表示。 问 A[3][3] （10）存放在什么位置？脚注 （10） 5. A ．688 B ．678 C ． 692 D ． 696 树最适合用来表示 （ ）。 A.有序数据元素 B.无序数据元素 6. C.元素之间具有分支层次关系的数据 D .元素之间无联系的数据 二叉树的第 k 层的结点数最多为 （ ）. A ．2-1 B.2K+1 C.2K-1 D. 2k-1 7.
计算机系统结构实验报告 一．流水线中的相关 实验目的： 1. 熟练掌握WinDLX模拟器的操作和使用，熟悉DLX指令集结构及其特点； 2. 加深对计算机流水线基本概念的理解； 3. 进一步了解DLX基本流水线各段的功能以及基本操作； 4. 加深对数据相关、结构相关的理解，了解这两类相关对CPU性能的影响； 5. 了解解决数据相关的方法，掌握如何使用定向技术来减少数据相关带来的暂停。 实验平台： WinDLX模拟器 实验内容和步骤： 1.用WinDLX模拟器执行下列三个程序： 求阶乘程序fact.s 求最大公倍数程序gcm.s 求素数程序prim.s 分别以步进、连续、设置断点的方式运行程序，观察程序在流水线中的执行情况，观察 CPU中寄存器和存储器的内容。熟练掌握WinDLX的操作和使用。 2. 用WinDLX运行程序structure_d.s，通过模拟找出存在资源相关的指令对以及导致资源相 关的部件；记录由资源相关引起的暂停时钟周期数，计算暂停时钟周期数占总执行周期数的 百分比；论述资源相关对CPU性能的影响，讨论解决资源相关的方法。 3. 在不采用定向技术的情况下（去掉Configuration菜单中Enable Forwarding选项前的勾选符），用WinDLX运行程序data_d.s。记录数据相关引起的暂停时钟周期数以及程序执行的 总时钟周期数，计算暂停时钟周期数占总执行周期数的百分比。 在采用定向技术的情况下（勾选Enable Forwarding），用WinDLX再次运行程序data_d.s。重复上述3中的工作，并计算采用定向技术后性能提高的倍数。 1. 求阶乘程序 用WinDLX模拟器执行求阶乘程序fact.s。这个程序说明浮点指令的使用。该程序从标准 输入读入一个整数，求其阶乘，然后将结果输出。 该程序中调用了input.s中的输入子程序，这个子程序用于读入正整数。 实验结果： 在载入fact.s和input.s之后，不设置任何断点运行。 a.不采用重新定向技术，我们得到的结果
广东创新科技职业学院期末考试试题（标明A 卷、B 或C 卷） 2018 —2019 学年第二学期考试科目：《数据结构》 (闭（开）卷 90分钟) 院系____________ 班级____________ 学号___________ 姓名 __________ 一、选择题（每小题 2 分，共 40 分） 1.计算机识别、存储和加工处理的对象被统称为（）。 A ．数据 B ．数据元素 C ．数据结构 D ．数据类型 2.数据结构指的是数据之间的相互关系，即数据的组织形式。数据结构一般包括（）三方面内容。 A ．数据的逻辑结构、数据的存储结构、数据的描述 B ．数据的逻辑结构、数据的存储结构、数据的运算 C ．数据的存储结构、数据的运算、数据的描述 D ．数据的逻辑结构、数据的运算、数据的描述3．数据的逻辑结构包括（）。 A ．线性结构和非线性结构 B ．线性结构和树型结构 C ．非线性结构和集合结构
D ．线性结构和图状结构 4.（）的特征是：有且仅有一个开始结点和一个终端结点，且所有结点都最多只有一个直接前驱和一个直接后继。 A ．线性结构 B ．非线性结构 C ．树型结构 D ．图状结构 5. 评价一个算法时间性能的主要标准是（）。 A ．算法易于调试 B ．算法易于理解 C ．算法的稳定性和正确性 D ．算法的时间复杂度 6. 下述程序段①中各语句执行频度的和是（）。 s=0; ① for(i=1;i<=i;j++) s+=j; A ．n-1 B ．n C ．2n-1 D ．2n 7. 下面程序段的时间复杂度为（）。 for(i=0;i 12/13 年第2学期《数据挖掘与知识发现》期末考试试卷及答案 一、什么是数据挖掘？什么是数据仓库？并简述数据挖掘的步骤。（20分） 数据挖掘是从大量数据中提取或发现（挖掘）知识的过程。 数据仓库是面向主题的、集成的、稳定的、不同时间的数据集合，用于支持经营管理中的决策制定过程。 步骤： 1）数据清理（消除噪声或不一致数据） 2) 数据集成（多种数据源可以组合在一起） 3 ) 数据选择（从数据库中检索与分析任务相关的数据） 4 ) 数据变换（数据变换或统一成适合挖掘的形式，如通过汇总或聚集操作） 5) 数据挖掘（基本步骤，使用智能方法提取数据模式） 6) 模式评估（根据某种兴趣度度量，识别表示知识的真正有趣的模式；） 7) 知识表示（使用可视化和知识表示技术，向用户提供挖掘的知识） 二、元数据的定义是什么？元数据包括哪些内容？（20分） 元数据是关于数据的数据。在数据仓库中, 元数据是定义仓库对象的数据。 元数据包括： 数据仓库结构的描述，包括仓库模式、视图、维、分层结构、导出数据的定义, 以及数据集市的位置和内容。 操作元数据，包括数据血统（移植数据的历史和它所使用的变换序列）、数据流通（主动的、档案的或净化的)、管理信息（仓库使用统计量、错误报告和审计跟踪）。 汇总算法，包括度量和维定义算法, 数据所处粒度、划分、主题领域、聚集、汇总、预定义的查询和报告。 由操作环境到数据仓库的映射，包括源数据库和它们的内容，网间连接程序描述, 数据划分, 数据提取、清理、转换规则和缺省值, 数据刷新和净化规则, 安全 (用户授权和存取控制)。 关于系统性能的数据，刷新、更新定时和调度的规则与更新周期，改善数据存取和检索性能的索引和配置。 商务元数据，包括商务术语和定义, 数据拥有者信息和收费策略。 三、在 O L A P 中，如何使用概念分层? 请解释多维数据模型中的OLAP上卷 下钻切片切块和转轴操作。（20分） 在多维数据模型中，数据组织成多维，每维包含由概念分层定义的多个抽象层。这种组织为用户从不同角度观察数据提供了灵活性。有一些 O L A P 数据立方体操作用来物化这些不同视图，允许交互查询和分析手头数据。因此， O L A P 为交互数据分析提供了友好的环境。 上卷：上卷操作通过一个维的概念分层向上攀升或者通过维归约，在数据立方体上进行聚集。 下钻：下钻是上卷的逆操作，它由不太详细的数据到更详细的数据。下钻可以通过沿维的概念分层向下或引入新的维来实现。 切片：在给定的数据立方体的一个维上进行选择，导致一个子方。 切块：通过对两个或多个维执行选择，定义子方。 贵州大学理学院数学系信息与计算科学专业 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 一、单项选择题 1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。 (A)、正确性(B). 可行性(C). 健壮性(D). 输入性 2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（）。 for(i=n-1；i>=0；i--) for(j=0；j数据挖掘试卷及答案
数据结构期末考试试题及答案
相关主题
文本预览