天大2021年秋学期考试《数据结构》离线作业考核试题[答案]

天大2021年秋学期考试《数据结构》离线作业考核试题[答案]答案

数据结构
要求：
一、 独立完成，下面已将五组题目列出，任选一组进行作答，每人只答一组题目，多答无效，满分100分
二、答题步骤：
1. 使用A4纸打印学院指定答题纸（答题纸请详见附件）；
2. 在答题纸上使用黑色水笔按题目要求手写作答；答题纸上全部信息要求手写，包括学号、姓名等基本信息和答题内容，请写明题型、题号；
三、提交方式：请将作答完成后的整页答题纸以图片形式依次粘贴在一个Word
    文档中上传（只粘贴部分内容的图片不给分），图片请保持正向、清晰；
1. 完成的作业应另存为保存类型是“Word97-2003”提交;
2. 上传文件命名为“中心-学号-姓名-科目.doc”;
3. 文件容量大小：不得超过20MB。
提示：未按要求作答题目的作业及雷同作业，成绩以0分记！

题目如下：
第一组：
一、编程题（每小题30分，共60分）
(一)
已知某哈希表的装载因子小于1，哈希函数H(key)为关键字（标识符）的第一个字母在字母表中的序号，处理冲突的方法为线性探测开放定址法。试编写一个按第一个字母的顺序输出哈希表中所有关键字的算法。
(二)
用标准C语言实现Hanoi塔问题
二、解答题（20分）
(一)
设待排序记录的关键字序列为{46, 55, 13, 42, 94, 05, 17, 70}写出其第一趟快速排序过程。（要求写出每次交换后的序列，并且枢轴记录到位也算一次交换）

初始关键字：  46   55   13   42   94   05   17   70
1次交换后：
2次交换后：
3次交换后：
4次交换后：
5次交换后：
三、画图题（20分）
(一)
将下面的森林变换成二叉树


















第二组：
一、编程题（每小题30分，共60分）
(一)
用标准C语言实现Hanoi塔问题

(二)
1.设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表
中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。
2. 设计在链式存储结构上交换二叉树中所有结点左右子树的算法。
二、解答题（20分）
(一)
已知一棵二叉树的先序序列是ABCDEFGHIJK，中序序列是CDBGFEAHJIK，请构造出该二叉树。

三、画图题（20分）
(一)
设有序顺序表中的元素依次为017, 094, 154, 170, 275,503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行折半搜索时的判定树, 并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。








第三组：
一、编程题（每小题30分，共60分）

(一)
1.设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表
中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。
2. 设计在链式存储结构上交换二叉树中所有结点左右子树的算法。

(二)
1.设有一组初始记录关键字序列（K1，K2，„，Kn），要求设计一个算法能够在O(n)的时间
复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。
2． 设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C用链式存储结构表示。

二、解答题（20分）
(一)
若二叉树中各结点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树，但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。
(1)已知一棵二叉树的前序序列和中序序列分别为ABDGHCEFI和GDHBAECIF，请画出此二叉树。
(2)已知一棵二叉树的在序序列和后序序列分别为BDCEAFHG和DECBHGFA，请画出此二叉树。
(3)已知一棵二叉树的前序序列和后序序列分别为AB和BA，请画出这两棵不同的二叉树。


三、画图题（20分）
(一)
某子系统在通信联络中只可能出现8种字符，其出现的概率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11试设计赫夫曼编码
























第四组：
一、编程题（每小题30分，共60分）
(一)
已知某哈希表的装载因子小于1，哈希函数H(key)为关键字（标识符）的第一个字母在字母表中的序号，处理冲突的方法为线性探测开放定址法。试编写一个按第一个字母的顺序输出哈希表中所有关键字的算法。

(二) 设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。

二、解答题（20分）

(一)
写出下图所示的AOV网的可能拓扑序列，要求至少写出五个










三、画图题（20分）
(一)
设有序顺序表中的元素依次为017, 094, 154, 170, 275,503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行折半搜索时的判定树, 并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。








第五组：
一、编程题（每小题30分，共60分）
(一)
对于二维整数数组A[m][n]，对下列三种情况，分别编写相应的函数。
1. 求数组所有边缘元素的数值和。
int sum1(int A[M][N],int m ,int n)
{
2.求从A[0][0]开始的互不相邻的所有元素的和
注：一个元素的八个方向上的第一个元素均为相邻元素。
int sum2 (int A[M][N] , int m , int n)
{
3. 假定m=n，并为偶数，请分别计算正、反两条对角线上的元素值之和。
int sum3(int A[M][N] , int n)
{

(二)
已知某哈希表的装载因子小于1，哈希函数H(key)为关键字（标识符）的第一个字母在字母表中的序号，处理冲突的方法为线性探测开放定址法。试编写一个按第一个字母的顺序输出哈希表中所有关键字的算法。

二、解答题（20分）
(一)
设待排序记录的关键字序列为{46, 55, 13, 42, 94, 05, 17, 70}写出其第一趟快速排序过程。（要求写出每次交换后的序列，并且枢轴记录到位也算一次交换）

初始关键字：  46   55   13   42   94   05   17   70
1次交换后：
2次交换后：
3次交换后：
4次交换后：
5次交换后：

三、画图题（20分）
(一)
已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。

天大2021年秋学期考试《数据结构》离线作业考核试题[答案]历年参考题目如下：

北理工《汽车网络技术》在线作业-0001

试卷总分:100    得分:0

一、 单选题 (共 15 道试题,共 30 分)

1.二进制的特点不包括（ ）

A.简单可行，容易实现

B.算术运算规则简单

C.运行不稳定

D.适合逻辑运算

 

 

2.错误检测的类型不包括（ ）

A.位错误

B.填充错误

C.操作错误

D.形式错误

 

 

3.下列不属于单片机特点的是（）

A.体积小

B.质量轻

C.灵活性好

D.抗干扰能力弱

 

 

4.下列关于ASCII码128种字符个数错误的是（ ）

A.通用控制字符34个

B.阿拉伯数字10个

C.大小写英文字母51个

D.各种标点符号和运算符号共有32个

 

 

5.下列关于SAE分类总线的类别叙述正确的是（）

A.A类是多媒体设备、高速数据流传输的高性能网络。

B.B类是面向独立控制模块间的信息共享的中速网络。

C.C类是面向传感器或执行器管理的低速网络。

D.D类是面向面向闭环实时控制的多路传输高速网络。

 

 

6.下列哪些不属于CAN被细分的层次（ ）

A.数据链路层

B.物理层

C.媒体访问控制子层

D.会话层

 

 

7.下列关于6264芯片与8031的连接方法叙述正确的是（ ）

A.8031的PO口一方面与6264的8条I/0数据线相连，同时经锁存器74LS373与6264的低8位地址线相连

B.P2.0~P2.4与6264的高5位读允许端相连

C.6264的写使能端与单片机的地址线相连

D.输出使能端与单片机的写允许端相连

 

 

8.下列关于网络系统各层的功能叙述正确的是( )

A.物理层的作用是在物理传输媒体上传输各种数据的比特流。

B.数据链路层最重要的作用就是将分组从源端机器经选定的路由送到目的端机器。

C.网络层主要功能是对源站的数据进行编码，形成适合于传输的比特流。

D.表现层的功能是通过一系列数据链路层协议，在不可靠的物理链路上实现可靠的数据传输。

 

 

9.下列不属于网络系统层交换技术的是 （ ）

A.电路交换

B.报文交换

C.分组交换

D.结构交换

 

 

10.CPU功能强弱需要指标来测量，以下指标哪项不是（ ）

A.内部总线宽度

B.指令数

C.寻址方式越多，对某一空间的寻址越灵活

D.运行速度

 

 

11.以下哪些不属于MCS-51单片机的I/O口（ ）。

A.P1

B.P2

C.P3

D.P4

 

 

12.以下不属于故障界定的是（ ）

A.错误激活

B.错误认可

C.总线关闭

D.应答错误

 

 

13.MCS-51单片机的方式不包括（ ）

A.复位方式

B.程序执行方式

C.低功耗方式

D.存储方式

 

 

14.在汽车内部网络中，各个子网根据内部数据通信的网络特征，采用不同的CAN标准，下列叙述错误的是（ ）

A.信息娱乐子网，音响、图像等媒体数据流的位速率一般都在2Mb/s以上，低于CAN的带宽范围

B.动力传动子网，该子网一般是按照ISO11898、J1939及J2284的要求组建高速CAN或TTCAN来实时采集所有传感器的输出信号，并将采集到的数据打包，再定期以广播的方式发送出去

C.车身电子子网，该子网通常是遵循ISO11519-2和J2284的要求，组建低速容差CAN来增加传输距离，改善系统抗干扰特性

D.故障诊断子网，传统故障诊断模块正打算采用高速CAN的物理层来实现，并形成了ISO/DIS15765和J24

 

 

15.下列哪项不属于MSC-51单片机的工作方式（ ）

A.复位方式

B.程序执行方式

C.高功耗方式

D.掉电保护方式

 

 

二、 多选题 (共 10 道试题,共 30 分)

1.下列属于CAN属性的是（ ）

A.报文的优先权

B.保持延迟时间

C.设置灵活

D.系统内数据的连贯性

E.多主机

 

 

2.MCS-51单片机的运算器包括（ ）

A.算术逻辑部件ALU

B.位处理器

C.累加器A

D.寄存器B

E.暂存器

 

 

3.单片微型计算机的基本组成部分有（ ）

A.中央处理器

B.存储器

C.输入接口电路

D.输出接口电路

E.定时器

 

 

4.以下哪些型号属于MCS-51系列单片微型计算机（ ）

A.8031

B.8041

C.8051

D.8651

 

 

5.以下哪些属于MCS-51单片机的I/O口（ ）

A.P0

B.P1

C.P2

D.P3

E.P4

 

 

6.以下哪些是单片机的特点（ ）

A.体积大

B.抗干扰能力强

C.对环境要求不高

D.价格低廉

 

 

7.循环程序包括（ ）

A.初始化部分

B.循环处理部分

C.循环控制部分

D.位转移部分

E.循环结束部分

 

 

8.下列属于半导体存储器的是（ ）

A.只读存储器

B.可读写存储器

C.不挥发性读写存储器

D.加密型ROM

E.双端口RAM

 

 

9.以下哪些属于汽车子系统（ ）

A.动力传动系统

B.底盘车身系统

C.C动系统

D.转向机构以

E.载通讯系统

 

 

10.MCS-51单片机开始运行时，首先是进入取指阶段，其次序是（ ）

A.程序计数器的内容送到地址寄存器

B.程序计数器的内容自动加1

C.地址寄存器的内容通过内部地址总线到存储器，通过存储器中地址译码电路，使地址为0000H的单元被选中

D.CPU使读控制线有效

E.在读命令控制下被选中存储器单元的内容送到内部数据总线上，因为取指阶段，所以该内容通过数据总线被送到指令寄存器

 

 

三、 判断题 (共 20 道试题,共 40 分)

1.引脚8在C250/251上的助记符是S。（ ）

A.错误

B.正确

 

 

2.数据可实现双向传送，但不能同时进行，实际的应用采用某种协调实现收/发开关转换成为全双工方式。

A.错误

B.正确

 

 

3.传输层的主要功能是将分组从源端极其经选定的路由送到目的端机器。

A.错误

B.正确

 

 

4.AMT既具有液力自动变速器自动变速的优点，又保留了原手动变速器齿轮传动的效率高、成本低、结构简单、易制造的长处。( )

A.错误

B.正确

 

 

5.堆栈实际上是一种数据结构，是只允许在其一端进行数据插入和数据删除操作的线性表。

A.错误

B.正确

 

 

6.当制动力小于车轮附着力时，摩擦力和滑移摩擦随制动力的增长而减小。( )

A.错误

B.正确

 

 

7.输入和输出接口电路不属于单片微型计算机的基本组成部分。

A.错误

B.正确

 

 

8.位处理器属于MCS-51单片机基本组成。

A.错误

B.正确

 

 

9.体积大是单片机的特点。

A.错误

B.正确

 

 

10.EPROM一般部的工作方式包括读方式、维持方式、编程方式、编程校核方式和编程禁止方式。

A.错误

B.正确

 

 

11.向SJA1000发送缓冲区写入数据时，一定要检查发送缓冲区是否处于锁定状态，如锁定，这时写入的数据将丢失。（ ）

A.错误

B.正确

 

 

12.如果相位误差为负，则相位缓冲段1就增长一个与重新同步跳转宽度相等的值。（ ）

A.错误

B.正确

 

 

13.使能发送中断时，中断寄存器的位IR.2 置位

A.错误

B.正确

 

 

14.多终端是一种不用改变终端电缆DC特性而能增强EMC性能的终端配置方法。（ ）

A.错误

B.正确

 

 

15.安全总线是为了增进汽车的被动安全性而被独立开发出来的，它专用于实现对安全气囊的管理。

A.错误

B.正确

 

 

16.MCS-51的时序定时单位包括时间、拍节、状态、机器周期和指令周期。

A.错误

B.正确

 

 

17.8255的工作方式2为双向数据传送方式，其功能概括为：有一个8位双向数据端口（A）和一个5位控制/状态信号端口，输入、输出均可锁存。

A.错误

B.正确

 

 

18.补码的设计目的是使加法运算转换为减法运算，进一步简化计算机中运算器的线路设计。

A.错误

B.正确

 

 

19.报文帧用校验和场作为起始，用一个同步间隔场作为结束。( )

A.错误

B.正确

 

 

20.CAN网桥主要由89C52和两路CAN控制器接口组成。( )

A.错误

B.正确