国防科技大学数据结构和离散数学2003真题

2022年国防科技大学数据科学与大数据技术专业《计算机网络》科目期末试卷B（有答案）一、选择题1、设某段电路的传播时延是20ms，带宽为20Mbivs，则该段电路的时延带宽积为（）。

A.2×105bitB.4×105bitC.1×105bitD. 8×105bit2、计算机网络最基本的功能是（）。

I.流量控制Ⅱ.路由选择 III.分布式处理 IV.传输控制A.I、Ⅱ、IVB. I、III、ⅣC.I、IVD. Ⅲ、IV3、动态路山选择和静态路由选择的主要区别是（）。

A.动态路由选择需要维护整个网络的拓扑结构信息，而静态路由选择只需要维护有限的拓扑结构信息B.动态路由选择需要使用路由选择协议去发现和维护路由信息，而静态路由选择只需要手动配置路由信息C.动态路由选择的可扩展性要大大优于静态路由选择，因为在网络拓扑结构发生了变化时，路由选择不需要手动配置去通知路由器D.动态路由选择使用路由表，而静态路由选择不使用路由表4、IPv6的地址长度为（）位。

A.32B.64C.128D.2565、若Hub再生比特流过程中，会产生1.535us延时，信号传播速度为200m/us，不考虑以太网帧的前导码，则H3与H4之间理论上可以相距的最远距离是（）。

A.200mB.205mC.359mD.512m6、站点A、B、C通过CDMA共享链路，A、B、C的码片序列（chipping sequence）分别是（1，1，1，1）、（1，-1，1，-1）和（1，1，-1，-1）。

若C从链路上收到的序列是（2，0，2，0，0，-2，0，-2，0，2，0，2），则C收到A发送的数据是（）。

A.000B.101C.110D.1117、使用两种编码方案对比特流01100111进行编码的结果如图所示，编码1和编码2分别是（）A.NRZ 和曼彻斯特编码B.NRZ 和差分曼彻斯特编码C.NRZ-I和曼彻斯特编码D.NRZ-I和差分曼彻斯特编码8、在TCPMP模型中，传输层的主要作用是在互联网络的源主机和目的主机对等实体之间建立用于会话的（）。

A2003年研究生入学试题已知一棵度为12 的树，它的根结点的地址为root。

该树是用顺序存储方式存储的，说明如下：struct node { i nt data;// 树中结点的数据场。

int son[12]; //给出结点的第一个、第二个……第12个儿子结点//地址。

}tnode[M]; //注意：M是一个常量。

请设计一个非递归的程序，按前序遍历该树，打印每个结点的的数据场之值，注意：如用递归程序实现，作零分处理。

（本题15 分。

）二．从键盘上输入一串正整数，最后输入－1作为结束标志。

如：8,7,1,22,98,46,……,75,-1。

请设计一个非递归程序，创建一棵二叉排序树，并且该二叉排序树业必须是中序线索二叉树。

设该二叉排序树上的结点结构为：其中：data 域为结点的数据场。

ltag=0,那么left域中存放的是该结点的左儿子结点的地址。

ltag=1,那么left域中存放的是该结点的按中序周游次序的前驱结点的地址。

rtag=0,那么right域中存放的是该结点的右儿子结点的地址。

rtag=1,那么right域中存放的是该结点的按中序周游次序的后继结点地址。

（本题20 分。

）三．已知中序线索二叉树的某结点的地址为P请设计一个程序给出地址为P 的结点的按前序周游次序的后继结点的地址q。

注意：本程序要求辅助空间只能为O(1)，否则作零分处理。

另外，结点形式可参考第2 题。

（本题15 分。

）四．已知某有向图用邻接表表示。

该邻接表的结点及边表说明如下：#define TOTAL 1000struct arcnode { int adjvex; // 该边所指向的结点的下标地址。

struct arcnode *nextarc; // 给出下一条边的边结点的地址。

} arcnode ; // 边结点说明。

struct vnode { int data; // 结点数据场，其值为整数。

arcnode * firstarc; //指向离开本结点的第一条边的边结点。

2021年国防科技大学数据科学与大数据技术专业《计算机组成原理》科目期末试卷A（有答案）一、选择题1、在对破坏性读出的存储器进行读/写操作时，为维持原存信息不变，必须辅以的操作是（）。

A.刷新B.再生C.写保护D.主存校验2、若数据在存储器中采用以低字节地址为字地址的存放方式（小端存储），则十六进制数12345678H按自己地址由小到大依次存为（）。

A.12345678B.87654321C.78563412D.341278563、下列关于各种移位的说法中正确的是（）。

I.假设机器数采用反码表示，当机器数为负时，左移时最高数位丢0，结果出错；右移时最低数位丢0，影响精度Ⅱ在算术移位的情况下，补码左移的前提条件是其原最高有效位与原符号位要相同Ⅲ.在算术移位的情况下，双符号位的移位操作中只有低符号位需要参加移位操作（）A. Ⅲ、ⅡB.只有ⅡC.只有ⅢD.全错4、当满足下列（）时，x>-1/2成立。

A.x1必须为l，x2~x4至少有一个为1B.x1必须为1，x2~x4任意C.x1必须为0，x2~x4至少有一个为1D.x1必须为0，X2~x4任意5、ALU属于（）。

A.时序电路B.控制器C.组合逻辑电路D.寄存器6、总线的半同步通信方式是（）。

A.既不采用时钟信号，也不采用握手信号B.只采用时钟信号，不采用握手信号C.不采用时钟信号，只采用握手信号D.既采用时钟信号，又采用握手信号7、某机器I/O设备采用异步串行传送方式传送字符信息，字符信息格式为1位起始位、8位数据位、1位校验位和1位停止位。

若要求每秒传送640个字符，那么该设备的有效数据传输率应为（）。

A.640b/sB.640B/sC.6400B/sD.6400b/s8、将高级语言源程序转换为机器目标代码文件的程序是（）。

A.汇编程序B.链接程序C.编译程序D.解释程序9、下列关于配备32位微处理器的计算机的说法中，正确的是（）。

该机器的通用寄存器一般为32位Ⅱ.该机器的地址总线宽度为32位Ⅲ.该机器能支持64位操作系统IV.一般来说，64位微处理器的性能比32位微处理器的高A.I、ⅡB.I、ⅢC.I、ⅣD.I、IⅡ、Ⅳ10、某计算机的指令流水线由4个功能段组成，指令流经各功能段的时间（忽略各功能段之间的缓存时间）分别为90ns，80ns、70ns和60ns，则该计算机的CPU时钟周期至少是）（）。

2022年国防科技大学数据科学与大数据技术专业《计算机组成原理》科目期末试卷A（有答案）一、选择题1、设存储器容量为32字，字长为64位。

模块数m=4，采用低位交叉方式。

存储周期T=200ns，数据总线宽度为64位，总线传输周期r=50ns。

该交叉存储器的带宽是（）。

A.32×107bit/sB.8×107bit/sC.73×107bit/sD.18×107bit/s2、容量为64块的Cache采用组相联映射方式，字块大小为128个字，每4块为一组。

如果主存为4K块，且按字编址，那么主存地址和主存标记的位数分别为（）。

A.16，6B.17，6C.18，8 D .19，83、浮点数加/减运算过程一般包括对阶、尾数运算、规格化、舍入和判断溢出等步骤。

设浮点数的阶码和尾数均采用补码表示，且位数分别为5位和7位（均含两位符号位）。

若有两个数，即x=2×29/32，y=25×5/8，则用浮点数加法计算xty的最终结果是（）。

A.001111100010B.001110100010C.010*********D.发生溢出4、下列编码中，能检测出所有长度小于或等于校验位（检测位）长度的突发错的校验码是（）。

A.循环冗余校验码B.海明码C.奇校验码D.偶校验码5、对于相同位数（设为N位，且各包含1位符号位）的二进制补码小数和十进制小数，（二进制小数所表示的数的个数）/（十进制小数所能表示的数的个数）为（）。

A.（0.2）NB. （0.2）N-1C. （0.02）ND. （0.02）N-16、某同步总线采用数据线和地址线复用方式，其中地址/数据线有32根，总线时钟频率为66MHz，每个时钟周期传送两次数据（上升沿和下降沿各传送一次数据），该总线的最大数据传输率（总线带宽）是（）。

A.132MB/sB.264MB/sC.528MB/sD.1056MB/s7、为协调计算机系统各部件的工作，需要一种器件来提供统一的时钟标准，这个器件，是（）。

国防科技大学试题：离散数学
432-离散数学试题题单号:40632
(可不抄题)
考生注意：答案必须写在统一配发的答题纸上！
一、（每小题10分，共20分）
设A = {a, b, c, d}，A 上的二元关系R1和R2定义如下：
R1 = {<a, b>, <b, c>, <c, d>, <d, a>}
R2= IA∪{<a, b>,<b, a>,<c, d>,<d, c>}
i) 试分别指出R1和R2所具有的性质（即是否具有自反性，反自反性，对称性，反对称性和传递性这五种性质）。

ii) 试求出R12，R22，R1?R2，R1+ 和R2+。

二、（15分）
设函数? : X→Y 且g : X→Y ，若令
A = {a∈X | g (?(a))=a} 且
B = {b∈Y |?(g (b))=b}
则?[A]= B。

三、（20分）
设A 为有限集且?:A→A , 证明：
a) 若有自然数n≥1使? n =IA ，则?为双射；
b) 若?为双射，则有自然数n≥1使? n =IA 。

四、（15分）
求合式公式（P∨Q）∧（P→R）∧（Q→R）<==>R 的主合取范式和主析取范式。

五、（15分）
第 1 页共 2 页。

中国科技大学数据结构期终考试试题（2003.1）学号：__________ 姓名: _________ 成绩：________.一、填空题(24分，每空1.5分)1．假设一循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front(指向队头元素)和rear(指向队尾元素的下一个)，则当前队列中元素的个数是。

2．栈和队列均是运算受限的线性表，栈的特点是，队列的特点是。

3．若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3,…,pn,若p1=n，则pi(1<i<n+1)为。

4．高度为h（h>=1）的二叉哈夫曼树中，至少有个结点，至多有_____________个结点。

5．具有5个结点的不同形态的二叉树有_________棵，具有5个结点的不同形态的树有__________棵。

6．在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A。

并已知插入前，A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则应做________型调整以使其平衡。

7．高度为5的完全二叉树中至少有_____个2度结点，至多有__ 个结点有左孩子。

8．具有8个顶点的无向图至少应有__ 条边才能确保它是一个连通图，至多有__ 条边才能保证它仍是一个非连通图。

9．判断一个有向图是否存在回路除了可以用拓扑排序方法外，还可以用_____________________________方法。

10．广义表(((a), ()), ((a, b) , a), b)的表头是__________ ，表尾是_____________________。

二、解答题(41分)1．试推导含n个结点的完全k叉树的深度H。

（5分）2．某二叉树的先序遍历结点访问顺序是abdgcefh ，中序遍历的结点访问顺序是dgbaechf ，试写出其后序遍历的结点访问顺序，并画出该二叉树。

(8分)3．画出右图所示无向图中的最小生成树和深度优先生成树(从A 出发)。

2022年国防科技大学数据科学与大数据技术专业《计算机系统结构》科目期末试卷A(有答案）一、选择题1、对机器语言程序员透明的是（）A.中断字B.主存地址寄存器C.通用寄存器D.条件码2、除了分布处理、MPP和机群系统外，并行处理计算机按其基本结构特征可分为流水线计算机，阵列处理机，多处理机和（）四种不同的结构。

A.计算机网络B.控制流计算机C.机群系统D.数据流计算机3、浮点数尾数下溢处理时，最大误差最大，但下溢处理不需要时间，平均误差又趋于0的方法是( )。

A.截断法B.舍入法C.ROM查表法D.恒置"1"法4、下列说法中不正确的是( )A.软件设计费用比软件重复生产费用高B.硬件功能只需实现一次，而软件功能可能要多次重复实现C.硬件的生产费用比软件的生产费用高D.硬件的设计费用比软件的设计费用低5、费林按指令流和数据流的多倍性把计算机系统分类，这里的多倍性指（）。

A.系统瓶颈部件上处于同一执行阶段的指令流是数据流的多少倍。

B.系统瓶颈部件上处于同一执行阶段的数据流是指令流的多少倍。

C.系统瓶颈部件上处于同一执行阶段的指令或数据的最大可能个数。

D.A和B6、“启动I/O”指令是主要的输入输出指令，是属于（）。

A.目态指令B.管态指令C.目态、管态都能用的指令D.编译程序只能用的指令7、若输入流水线的指令既无局部性相关，也不存在全局性相关，则（）。

A.可获得高的吞吐率和效率B.流水线的效率和吞吐率恶化C.出现瓶颈D.可靠性提高8、下列关于虚拟存贮器的说法，比较正确的应当是( )A.访主存命中率随页面大小增大而提高B.访主存命中率随主存容量增加而提高C.更换替换算法能提高命中率D.在主存命中率低时，改用堆栈型替换算法，并增大主存容量，可提高命中率9、CRAY-I的流水线是( )A.多条单功能流水线B.一条单功能流水线C.多条多功能流水线D.一条多功能流水线10、微指令由（）直接执行。

2021年国防科技大学数据科学与大数据技术专业《计算机组成原理》科目期末试卷B（有答案）一、选择题1、主存与Cache间采用全相联映射方式，Cache容量4MB，分为4块，每块lMB，主存容量256MB。

若主存读/写时间为30ms，Cache的读/写时间为3ns，平均读/写时间为3.27ms，则Cache的命中率为（）。

A.90%B.95%C.97%D.99%2、主存储器主要性能指标有（）。

1.存储周期Ⅱ.存储容量Ⅲ.存取时间Ⅳ.存储器带宽A.I、IⅡB.I、IⅡ、IVC. I、Ⅲ、lVD.全部都是3、假设在网络中传送采用偶校验码，当收到的数据位为10101010时，则可以得出结论（）A.传送过程中未出错B.出现偶数位错C.出现奇数位错D.未出错或出现偶数位错4、假定有4个整数用8位补码分别表示：rl=FEH，r2=F2H，r3=90H，r4=F8H，若将运算结果存放在一个8位寄存器中，则下列运算会发生溢出的是（）。

A.rlxr4B.r2xr3C.rlxr4D.r2xr45、某机字长8位，含一位数符，采用原码表示，则定点小数所能表示的非零最小正数为（）A.2-9B.2-8C.2-7D.2-66、中断判优逻辑和总线仲裁方式相类似，下列说法中，正确的是（）。

I.在总线仲裁方式中，独立请求方式响应时间最快，是以增加处理器开销和增加控制线数为代价的II.在总线仲裁方式中计数器查询方式，若每次计数都从“0”开始，则所有设备使用总线的优先级相等III.总线仲裁方式一般是指I/O设备争用总线的判优方式，而中断判优方式一般是指I/O设备争用CPU的判优方式IV.中断判优逻辑既可以通过硬件实现，也可以通过软件实现，A. I，IIB. I，III，IVC. I，II，IVD.I，IV7、下列关于总线设计的叙述中，错误的是（）。

A.并行总线传输比串行总线传输速度快B.采用信号线复用技术可减少信号线数量C.采用突发传输方式可提高总线数据传输率D.采用分离事务通信方式可提高总线利用率8、计算机（）负责指令译码。