[数据结构与算法]Day43~Day49

Day43

数据结构

1.某二叉树的先根遍历序列和后根遍历序列正好相反，则该二叉树具有的特征是______ （中国科学院大学-2018）

A.高度等于其结点数

B.任一结点无左孩子

C.任一结点无右孩子

D.空或只有一个结点

• 答案：A
• 先序遍历顺序是：M-L-R;后序遍历顺序是：L-R-M;可以看到，只有中间的结点（M）顺序变化了，左右结点相对位置是不变的。那可以推断出，要满足题意的话“二叉树的先序序列与后序序列正好相反”，说明整个二叉树左子树或者右子树有一个没有（遍历就成了，先：M-L ；后：L-M 或者 先：M-R ；后：R-M ）也就是必然是一条链。所以只有A对了。

计算机网络

2. 以下哪种数字数据编码方式属于自含时钟编码?（华东理工大学 2006年）

A．二进制编码

B．非归零码

C．曼彻斯特编码

D．脉冲编码

• 答案: C
• 解析: 曼彻斯特编码将每个码元分成两个相等的间隔。前面一个间隔为高电平而后一个间隔为低电平表示码元1，码元0正好相反。位中间的跳变既作时钟信号，又作数据信号，因此选C。

计算机操作系统

3. 优先级是在创建进程时确定的，确定之后在整个进程运行期间不再改变（中国科学院大学 2015年）

A. 动态

B. 先来先服务

C. 短作业

D. 静态

• 答案: D
• 解析: 静态优先级是在创建进程时确定的，确定之后在整个进程运行期间不再改变。

计算机组成原理

4. 使用海明码作为一条消息的纠错码，对消息进行编码，并发送给接收者，编码后的消息到达接受者时有第______ 位发生了错误，导致接收到的消息变为111000111011111。（中国科学院大学 2017年）

A. 11

B. 13

C. 12

D. 14

• 答案: B
• 解析: 海明码用于纠正单比特错误。

Day44

数据结构

1. 若一个栈以向量V[1…n]存储，初始栈顶指针top为n+1，则下面x入栈的正确操作是 ______ （中国科学院大学 2015年）

A. top=top+1; V[top]=x

B. V[top]=x; top=top+1

C. top=top-1; V[top]=x

D. V[top]=x; top=top-1

• 答案：C
• 解析：考察栈的基础知识。

栈中设置两个指针，一个是不动端，叫bottom，另一个是可以变化的指针，是top，在进栈和出栈的过程中，top 的值不断的进行变化。
根据top 和bottom 的初始化的值的不同，栈可以用四种不同的形式：假设为顺序战分配了n 个空间，也就是V[0,1…(n-1)]
（1）bottom = top = -1
因为-1 不是一个有效的下标，进栈时，需要先让top++,然后是放入元素，代码是：top ++，V[top] = e，也可以简写为：V[++top] = e 出栈时是先出元素，再让top- - 代码是：e = V[top], top = top – 1 也可以简写为：e= V[top–] 此时top 指向栈顶元素；
（2）bottom = top = 0
因为0 是一个有效的下标，进栈时，需要先放入元素，然后是让top++，代码是：V[top] = e，top ++，
也可以简写为：V[top++] = e 出栈时是先让top- -，再出元素，代码是：top = top–1，e = V[top],也可以简写为：e= V[–top] 此时top 指向栈顶元素的上一个空位置；
（3）bottom = top = n-1
因为n-1 是一个有效的下标，进栈时，需要先放入元素，然后是让top- -，代码是：V[top] = e，top - - ，也可以简写为：V[top–] = e 出栈时是先出元素，再让top++ 代码是：top ++，e = V[top],也可以简写为：e= V[++top] 此时top 指向栈顶元素。

计算机网络

2. 有关曼彻斯特编码的正确叙述是 ______ （重庆邮电大学 2007年）

A．每个信号起始边界作为时钟信号有利于同步

B．将时钟与数据取值都包含在信号中

C．这种模拟信号的编码机制特别适合于传输声音

D．每位的中间不跳变表示信号的取值为0

• 答案：B
• 解析：曼彻斯特编码将每个码元分成两个相等的间隔。前面一个间隔为高电平而后一个间隔为低电平表示码元1，码元0正好相反，因此D错。位中间的跳变既作时钟信号，又作数据信号，因此B正确。曼彻斯特编码是将时钟和数据包含在数据流中，在传输代码信息的同时，也将时钟同步信号一起传输到对方，因此A错。每个码元都被调成两个电平，所以数据传输速率只有调制速率的1/2，不利于传声音，因此C错。

计算机操作系统

3. 在分时操作系统中，进程调度经常采用______ 算法（中国科学院大学 2015年）

A. 时间片轮转

B. 最高优先级

C. 先来先服务

D. 随机

• 答案：A
• 解析：在分时操作系统中，进程调度经常采用(时间片轮转)算法。

计算机组成原理

4. 设某机器内部寄存器内容为11111111,若它等于-0，则该机器采用（1）表示；若它等于-1,则该机器采用（2）表示.正确的答案是 （中国科学院大学2017年）

A. (1)补码；(2)反码

B. (1)补码；(2)原码

C. (1)反码；(2)补码

D. (1)移码；(2)补码

• 答案：C
• 解析：考察补码原码反码的定义，考察0在不同码型中的不同表示。在原码和反码中，0均有正负之分，在补码中没有，因此补码可以多表示一个绝对值最大的负数。

Day45

数据结构

1. A[N,N]是对称矩阵，将下三角（包括对角线）以行序存储到一维数组T[N(N+1)/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是______ （中国科学院大学 2015年）

A. i(i-1)/2+j

B. j(j-1)/2+i

C. i(j-i)/2+1

D. j(i-1)/2+1

• 答案：B
• 解析：根据书上对称矩阵的存储方式可知答案为B，带入下面的公式直接计算。特殊矩阵（数组）的压缩存储，特殊矩阵一共有四种：
  1. 对称矩阵压缩存储：
  2. 上三角矩阵或者下三角矩阵：
  3. 稀疏矩阵：一个三元组(i, j, aij)唯一确定稀疏矩阵的一个非零元素。第一维是表示行， 第二维表示列，第三维表示数值。

计算机网络

2. 电话系统的典型参数是信道带宽为3000Hz，信噪比为30dB，则该系统的最大数据传输速率为______ （山东大学 2007年）

A．3kbit/s

B．6kbit/s

C．30kbit/s

D．64kbit/s

• 答案：C
• 解析：S/N为信噪比，信噪比常用分贝（dB）表示，在数值上=10log10(S/N)（dB）。因此依题意有30=10log10(S/N)，可解出S/N=1000，根据香农定理，最大数据传输率=3000log2(1+S/N)kbit/s ≈30kbit/s。

计算机操作系统

3. 文件系统采用多级目录结构的目的是______ （上海交通大学 2005年）

A.减少系统开销

B.节约存储空间

C.解决命名冲突

D.缩短传送时间

• 答案：C
• 解析：多级目录会增加存储开销，增加访问时间，因此A、B都是错误；文件的传送时间与文件系统采用何种结构无关，因此D也是错误的；只有C才是正确的选项。

计算机组成原理

4. CPU中，暂存指令的寄存器是______ （中国科学院大学2017年）

A. 数据寄存器

B. 程序计数器

C. 状态条件寄存器

D. 指令寄存器

• 答案：D
• 解析：考察CPU中寄存器的功能。数据寄存器是指一些通用寄存器，一般用作存储操作数；程序计数器用于存储下一条指令的地址；状态条件寄存器用于存储标志位：指令寄存器用于存储指令。

Day46

数据结构

1. 下列数据结构中，______ 是非线性数据结构（中国科学院大学 2015年）

A．栈

B.队列

C.二叉树

D.堆

• 答案：C
• 解析：本题中二叉树是树形结构数据结构包括三个方面，（1）逻辑结构：包括线性结构（一对一），树形结构（一对多），图形结构（多对多），集合结构（同属于一个集合），（2）物理结构：顺序结构，链式结构，索引结构，散列结构（3）操作：CURD 等其结构关系如图所示：

计算机网络

2. 下列哪一项不是虚电路的特点？（重庆邮电大学 2007年）

A．分组按同一路由

B．顺序到达

C．分组开销少

D．支持广播

• 答案：D
• 解析：在虚电路服务中，属于同一条虚电路的分组按照同一路由转发，A正确。保证分组的有序到达，B正确。目的地址仅在建立连接阶段使用，之后每个分组使用长度较短的虚电路号，C正确。

计算机操作系统

3. 关于微内核操作系统的描述，不正确的是 ______ （中国科学院大学 2017年）

A. 微内核可以增强操作系统的可靠性

B. 微内核可以提高操作系统的执行效率

C. 微内核可以提高操作系统的可移植性

D. 微内核可以提高操作系统的可扩展性

• 答案：B
• 解析：微内核将内核中最基本道德功能（如进程管理等）保留在内核，而将那些不需要在核心态执行的功能移到用户态执行。微内核结构有效地分离了内核与服务、服务与服务，使得它们之间的接口更加清晰，维护的代价大大降低，从而保证了操作系统的可靠性。同时提高了操作系统的可移植性和可扩展性。B错误。

计算机组成原理

4. 假定用若干个8K*4位芯片组成一个基地址为0的地址连续的64K*8位存储器，则主存地址3020H所在芯片的最小地址是______ （中国科学院大学2017年）

A. 3000H

B. 2000H

C. 3FFFH

D. 0000H

• 答案：B
• 解析：用3020H除以8K,得到的余数就是所在芯片，再看所在芯片的起始地址即可，答案：B。

Day47

数据结构

1．在非空双向循环链表中q所指的结点后插入一个由p所指的链结点的过程依次为：rlink§<-rlink(q); rlink(q)<-p; llink§<-q;______ （中国科学院大学 2015年）

A. rlink(q)<-p

B. rlink(llink§)<-p

C. llink(rlink§)<-p

D. rlink(rlink§)<-p

• 答案：C
• 解析：在单链表中插入一个新的结点的过程，在单链表中无论是插入结点还是删除结点，都需要找到该结点的直接前驱才可以。同时在结点后插入结点的过程是先处理右指针，也就是说先左后右。这类题目，在做的过程中先画个示意图，再进行指针的修改。

(1) p->next=q->next;
(2) q->next->prior=p;
(3) q->next=p;
(4) p->prior=q;
本题中写法可以有很多种，但是（1）（2）可以调换，（3）和（4）可以调换，但是（1）（2）最少一个需要在前，Note：如果在q 结点前，插入一个结点p，该如何去写，提示：从左往右。

计算机网络

2.下列传输介质中，不受电磁干扰和噪声影响的是______ （中南大学 2006年）

A．同轴电缆

B．光纤

C．微波

D．双绞线

• 答案：B
• 解析：光纤即光导纤维，可以传递光脉冲，具有频带宽、速率高、体积小、重量轻、衰减少、抗雷电和电磁干扰性好、误码率低、保密性好等诸多优点，因此选B。

计算机操作系统

3.操作系统中系统调用的主要作用是______ （中国科学院大学 2017年）

A.处理输入输出

B.应对软件异常

C.管理系统资源

D.为应用程序提供服务接口

• 答案：D
• 解析：程序接口由一组系统调用命令如成.用户通过在程序中使用这些系统调用命令来请求操作系统为其提供服务。

计算机组成原理

4. 冯·诺依曼计算机工作方式的基本特点是______ （中国科学院大学 2016年）

A. 多指令流单数据流

B. 按地址访问并通常顺序执行指令

C. 堆栈操作

D. 机器以控制器为中心

• 答案：B
• 解析：考察冯诺依曼计算机结果的特点，包括：
  (1) 计算机硬件系统由运算器、存储器、控制器、输入设备和输出设备五大部件组成；
  (2) 指令和数据以同等地位存放在存储器内，并按地址访问；
  (3) 指令和数据均用二进制表示；
  (4) 指令由操作码和地址码组成。操作码表示操作的性质，地址码表示操作数在存储器中的位置；
  (5) 指令在存储器中按顺序存放。通常，指令是顺序执行的。在特殊情况下，可根据运算结果或指定的条件来改变运算顺序；
  (6) 机器以运算器为中心。运算器完成数据的算术运算和逻辑运算。输入输出设备和存储器之间的数据传送通过运算器和存储器完成。

Day48

数据结构

1、若6行5列的数组以行序为主序顺序存储，基地址为1000，每个元素占2个存储单元，则第3行第4列的元素（假定无第0行第0列）的地址是 ______ （中国科学院大学 2015年）

A. 1040

B. 1042

C. 1026

D. 以上答案都不对

• 答案：C
• 解析：由二维数组地址计算公式得到C，考察数组的存储的特点：
  设有二维数组A=(aij)m*n，若每个元素占用的存储单元数为L(个)，LOC[a11] 表示元素a11的首地址，即数组的首地址。以“行优先顺序”存储
  (1) 第1 行中的每个元素对应的(首)地址是：LOC[a1j]=LOC[a11]+(j-1)*L j=1,2, …,n
  (2) 第2 行中的每个元素对应的(首)地址是：LOC[a2j]=LOC[a11]+n*l +(j-1)*L j=1,2, …,n
  (3) 第m 行中的每个元素对应的(首)地址是：LOC[amj]=LOC[a11]+(m-1)*n*l +(j-1)*L j=1,2, …,n
  由此可知，二维数组中任一元素aij的(首)地址是：
  LOC[aij]=LOC[a11]+[(i-1)*n+(j-1)]*L i=1,2, …,m j=1,2,…,n. 对于三维数组A=(aijk)m n p，若每个元素占用的存储单为l(个)，LOC[a111]表示元素a111 的首地址，即数组的首地址。以“行优先顺序”存储在内存中。三维数组中任一元素aijk 的(首)地址是：LOC(aijk)=LOC[a111]+[(i-1)*n*p+(j-1)*p+(k-1)] *L 带入计算。

计算机网络

2．某网络物理层规定：信号的电平用+5～+15V表示二进制0，用-15～-5V表示二进制1，电缆长度限于15m内，这体现了物理层接口的______ （江西财经大学 2005年）

A．机械特性

B．电气特性

C．功能特性

D．规程特性

• 答案：B
• 解析：物理层的电气特性规定传输二进制位时，线路上信号的电压高低、阻抗匹配、传输速率和距离限制等。因此选B。

计算机操作系统

3.进入内存的作业状态为______ （福州大学 2005年）

A．就绪状态

B．执行状态

C．阻塞状态

D．后备状态

• 答案：A
• 解析：进程分配到除CPU之外所有资源则进入就绪状态，作业进入内存为就绪状态，之后可能转入执行或阻塞状态。外存中的作业处于后备状态。

计算机组成原理

4. 浮点表示法本质上是一种二进制的指数计数法。在浮点表示中，对______ 采用了隐含约定技术。（哈尔滨工程大学 2004年）

A．数符

B．数位

C．指数

D．基数

• 答案：D
• 解析：在浮点机中，基数采用隐含约定，通常可约定为2、4、8等。

Day49

数据结构

1. 一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是 ______ （中国科学院大学 2015年）

A. CABDEFG

B.GFEABCD

C. DACEFBG

D. ADCFEGB

• 答案：D
• 解析：求中序序列，就看能不能和先序构成一棵二叉树。D与题目给出的先序能够构成_棵二叉树。考察二叉树的四种遍历方式，前序遍历，中序遍历，后续遍历，层次遍历。其中中序+前序，中序+后序，中序+层次三种都可以唯一确定一棵二叉树。以中序和后序为例，确定一个二叉树。首先从后序中找到根结点，然后在中序遍历中确定出左右子树，然后再利用左右子树的后序遍历，确定左右子树的根结点，依次类推，从而确定一个二叉树。当仅仅给定前序遍历，中序遍历，后续遍历或者层次遍历时，无法确定唯一的确定一个树。

计算机网络

2．当描述一个物理层接口引脚在处于高电平时的含义时，该描述属于 ______ （重庆大学 2005年）

A．机械特性

B．电气特性

C．功能特性

D．规程特性

• 答案：C
• 解析：物理层的功能特性指明某条线上出现的某一电平的电压表示何种意义，因此选C。

计算机操作系统

3. 与内核态线程相比，用户态线程的优点不包括______ （中国科学院大学 2017年）

A. 线程切换不需要转换到内核空间

B. 可以采用定制的调度算法

C. 可以避免系统调用引起进程阻害

D. 实现与操作系统平台无关

• 答案：C
• 解析：对一个进程而言，其所有线程的管理数据结构均在该进程的用户空间中，管理线程切换的线程庠也在用户地址空间运行，因此进瘟不必切模到内核方式来做线程管理，A正确：在不干扰OS调度的情况下，不同的进程可以根据自身需要选择不同的调度算法，对自己的线程进行管理和调度，B正确；用户级线程的实现与OS平台无关，因为对于线程管理的代码是属于用户程序的一部分，所有的应用程序辱可以对之进行关享。用户级线程甚至可以在不支持线程机制的操作平台上实现，D正确。

计算机组成原理

4. 某存储系统中，主存容量是Cache容量的4096倍，Cache被分为64个块，当主存地址与Cache地址采用直接地址变换时，地址变换表的大小应为 ______ （假设地址变换表每行仅存储主存字块标记）（西安电子科技大学 2007年）

A．6×12bit

B．6×4096bit

C．64×12bit

D．64×4096bit

• 答案：C
• 解析：Cache被分为64个块，故地址变换表为64行，每行存储主存字块标记为12位（212=4096）。