1、计算机专业（基础综合）模拟试卷 19 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 若线性表最常用的运算是查找第 i 个元素及其前驱的值，则下列存储方式最节省时间的是 ( ) 。（A）单链表（B）双链表（C）单循环链表（D）顺序表2 在非空双循环链表中 q 所指的结点前插入一个由 p 所指结点的过程依次为：p-next=q；p-prior=q-prior；q-prior=p；下一条语句是( )。（A）q-next=p；（B） q 一prior-next=p；（C） p-prior-next=p；（D）p-n
2、ext-priox=p ；3 在一个长度为 n 的顺序存储线性表中，删除第 i 个元素(1in+1)时，需要从前向后依次前移的元素个数是( )。（A）n-i（B） n-i+1（C） n-i-1（D）i4 将两个长度为 n 的递增有序表归并成一个长度为 2n 的递增有序表，最少需要进行关键字比较次数是( )。（A）1（B） n-1（C） n（D）2n5 已知一算术表达式的中缀形式为 A+B*C-DE，后缀形式为 ABC*+DE一，其前缀形式为( ) 。（A）一 A+B*CDE（B）一 A+B*CDE（C）一 +*ABCDE（D）一+A*BCDE6 一个循环队列 Q 最多可存储 m 个元素，已知其
3、头尾指针分别是：front 和 rear，则判定该循环队列为满的条件是( )。（A）Qrear Qfront=m（B） Qrear!=Qfront（C） Qfront=(Q rear+1)m（D）Qfront=Qrearm+17 某二叉树的先序和后序序列正好相反，则该二叉树一定是( )。（A）空或只有一个结点（B）高度等于其结点数（C）任一结点无左孩子（D）任一结点无右孩子8 对二叉树的结点从 1 开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，为实现编号可采用的遍历是 ( )。（A）先序（B）中序（C）后序（D）从根开始按层
4、次遍历9 一棵哈夫曼树共有 9 个结点，则其叶子结点的个数为( )。（A）4（B） 5（C） 6（D）710 下列有关散列查找的叙述正确的是( )。（A）散列存储法只能存储数据元素的值，不能存储数据元素之间的关系（B）散列冲突是指同一个关键字对应多个不同的散列地址（C）用线性探测法解决冲突的散列表中，散列函数值相同的关键字总是存放在一片连续的存储单元中（D）若散列表的装填因子 1，则可避免冲突的产生11 以下排序方法中，不需要进行关键字的比较的是( )。（A）快速排序（B）归并排序（C）基数排序（D）堆排序12 “容量为 640KB 的存储器”是指( )。（A）64010 3 字节的存储器（B
5、） 640103 位的存储器（C） 640210 位的存储器（D）6402 10 字节的存储器13 在微程序控制的计算机中，若要修改指令系统，只要( )。（A）改变时序控制方式（B）改变微指令格式（C）增加微命令个数（D）改变控制存储器的内容14 生成多项式为 x3+x+1，则数据信息 10101 的 CRC 编码是( )。（A）10010111（B） 10000111（C） 10101101（D）1110100115 判断加减法溢出时，可采用判断进位的方式，如果符号位的进位为 C0，最高数值位为 C1，产生溢出的条件是( )。IC0 生进位； C1 产生进位；C0 、C1 都产生进位； C0
6、、C1 都不产生进位；VC0 产生进位，C1 不产生进位； C0 不产生进位， C1 产生进位（A）I 和（B） （C） （D）V 和16 内存按字节编址，地址从 90000H 到 CFFFFH，若用存储容量为 1 6K8bit 芯片构成该内存，至少需要的芯片数是( )。（A）2（B） 4（C） 8（D）1 617 某计算机指令字长为 16 位，指令有双操作数、单操作数和无操作数 3 种格式，每个操作数字段均有 6 位二进制表示，该指令系统共有 m 条(mnext=q； p 一prior=q 一prior； q 一prior=p； p 一prior 一next=p ； 显然，题目中需要补充的语
7、句为第条语句，答案为 C。3 【正确答案】 A【试题解析】 顺序表的删除运算的时间主要消耗在了移动表中元素上，删除第 i个元素时，其后面的元素 ai+1a n 都要向上移动一个位置，共移动了 n 一 i 个元素。4 【正确答案】 C【试题解析】 假设有两个有序表 A 和 B 都递增有序，当有序表 A 所有元素均小于 B 的元素时，只需将 A 的所有元素与 B 的第一个元素比较即可，其比较 n 次。5 【正确答案】 D【试题解析】 将算术表达式的中缀形式作为一棵二叉树的中序遍历序列，将后缀形式 作为这棵二叉树的后序遍历序列，再由二叉树的中序遍历序列和后序遍历序列唯一的确定 这棵二叉树，在对其进行
8、先序遍历，就可得出算术表达式的前缀形式。6 【正确答案】 C【试题解析】 少用一个元素空间，每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满，这种情况下队满的条件是：(Qrear+1)MAXSIZE=Qfront ，能和空队区别开。7 【正确答案】 B【试题解析】 由于先序遍历是“根左子树右子树”，而后序遍历是“左子树 右子树根”，若某二叉树的先序和后序序列正好相反，则该二叉树每层左、右子树只 能有 1 个，即则该二叉树一定是高度等于其结点数。8 【正确答案】 C【试题解析】 根据题意和先序、中序、后序遍历规则，可简单地判断出正确答案。9 【正确答案】 B【试题解析】 哈夫曼树
9、中没有度为 1 的结点，用 n 个权值(对应 n 个叶子结点)构造哈夫曼树，共需要 n 一 1 次合并，即哈夫曼树中非叶子结点的总数为 n 一 1，总结点个数为 2n 一 1。10 【正确答案】 A【试题解析】 在散列表中，每个元素的存储位置通过散列函数和解决冲突的方法得到，散列存储法只存储数据元素的值，不能存储数据元素之间的关系，所以选项A 正确；散列 冲突是指多个不同关键字对应相同的散列地址，选项 B 错误；用线性探测法解决冲突的散 列表中，散列函数值相同的关键字不一定总是存放在一片连续的存储单元中，选项 C 错误；装填因子 越小，发生冲突的概率越小，但仍有可能发生冲突。11 【正确答案】
10、 C【试题解析】 基数排序是采用分配和收集实现的，不需要进行关键字的比较，而其 他几种排序方法都是通过关键字的比较实现的。12 【正确答案】 D【试题解析】 通常，以字节数来表示存储容量，这样的计算机称为字节编址的计算 机。“容量 640KB”是指 6401KB，即 640210B。13 【正确答案】 D【试题解析】 在微程序控制的计算机中，若要修改指令系统，只需修改相应指令的微程序即可。这些微程序都存放在控制存储器中，所以只需改变控制存储器的内容。14 【正确答案】 C【试题解析】 CRc 编码由数据信息和校验位共同组成，前 5 位为数据位，后 3 位为检验位。101010001011，余数
11、为 101，将余数 101(检验位)拼接在数据位的后面，就得到 CRC 码。15 【正确答案】 D【试题解析】 采用进位位来判断溢出时，当最高有效位和符号位的值不相同时才会产生溢出。16 【正确答案】 D【试题解析】 CFFFF 一 90000+1=40000，即 256KB，若用存储容量为 16K8bit芯片则需芯片数=(256K8)(16K8)=16(片)。17 【正确答案】 B【试题解析】 双操作数指令操作码字段占 4 位，单操作数指令操作码字段占 10 位，无操作数指令操作码字段占 16 位。现指令系统中有 m 条双操作数指令，则给单操作数和无操作数指令留下了(2 4 一 m)个扩展窗
12、口。因为存在着无操作数指令，所以单操作数指令必须要给无操作数指令留下一个扩展窗口，最终最多可以设计出单操作数指令的数目为(2 4 一 m)26 一 1。18 【正确答案】 B【试题解析】 在第 18 题图中，第 3 个流水段的执行时间没有给出，显然这是一个瓶颈段，设它的执行时间为 X。通过列方程(3+X) t+49Xt=153t，可以求得X=3。19 【正确答案】 B【试题解析】 程序计数器 PC 又称指令计数器，用来存放正在执行的指令地址或接着要执行的下一条指令地址，不能用于临时存储算术逻辑运算结果。20 【正确答案】 B【试题解析】 地址总线的位数与存储单元个数有关，地址总线的位数越长，可
13、访问的存储单元个数就越多。21 【正确答案】 D【试题解析】 格式化容量计算中根据扇区数和扇区容量计算出每条磁道上的信息量，然后再乘以总磁道数。而总磁道数计算时，首先求出每面磁道数(柱面数)，再乘以记录面数。22 【正确答案】 B【试题解析】 在 4 个选项中，唯有选项 B 为正确答案，因为并非每条指令执行完毕都会产生中断请求。23 【正确答案】 A【试题解析】 本题考查操作系统的接口。操作系统的接口有命令输入和系统调用。编写程序所使用的是系统调用，例如 read()。系统调用会给用户提供一个简单的使用计算机的接口，而将复杂的对硬件(例如磁盘)，和文件操作(例如查找和访问)的细节屏蔽起来，为用
14、户提供一种高效使用计算机的途径。24 【正确答案】 A【试题解析】 本题考查进程间的通信，进程间的通信主要有管道，命名管道，消息传递，共享内存，文件映射和套接字等。数据库不能用于进程间的通信。25 【正确答案】 A【试题解析】 本题考查进程的时间片轮转调度算法。时间片轮转的主要目的是使得多个交互的用户能够及时得到响应，使得用户以为“独占”计算机在使用。因此它并没有偏好，也不会对特殊进程特殊服务。时间片轮转增加了系统开销，所以不会使得系统高效运转，吞吐量和周转时间均不如批处理优。但是其较快速的响应时间使得用户能够与计算机进行交互，改善了人机环境，满足用户需求。26 【正确答案】 B【试题解析】
15、发生死锁的四个必要条件如下：互斥条件、占有并请求资源、非剥夺条件和循环等待条件。一次分配所有资源的方法是当进程需要资源时，一次性提出所有的请求，若请求的所有资源均满足则分配，只要有一项不满足，那么不分配任何资源，该进程阻塞，直到所有的资源空闲后，满足了进程的所有需求时再分配。这种分配方法不会部分占有资源，所以就打破了死锁的四个必要条件之一，实现了对死锁的预防。但是，这种分配方式需要凑齐所有资源，所以，当一个进程所需的资源比较多时，资源的利用率会比较低，甚至会造成进程的饥饿。正确答案为 B。27 【正确答案】 B【试题解析】 本题考查多级存储层次下的平均访问时间的计算。根据题意，处理机执行指令的
16、时间与存储器的平均存取周期成正比，因此只要计算出存储器的平均存取周期，即可比较出两者的优劣。对于处理机 P1，存储器的平均存取周期为：4007+(1000+40)(1 一 07)=340ns对于处理机 P2，存储器的平均存取周期为：5007+(900+50)(1 一 07)=320ns因此可以看出，处理机 P1 需要更多的处理机时间，处理机 P1 比处理机 P2 更慢。28 【正确答案】 C【试题解析】 本题考查页式存储管理的基本概念。页式存储管理的基本点是解决程序在内存中离散存放的问题，其寻址方式是借鉴于动态重定位的技术，在动态重定位技术中，通过设置基址寄存器，将程序的逻辑地址通过基址寄存器
17、和地址加法器，动态地实现了地址转换(即每一条都是自动转换的)，操作系统在装载程序时可以不用像静态重定位那样计算程序代码的地址定位，使得地址转换快捷又简单。页式存储管理将动态重定位中的基址寄存器用一组页表来替代，当访问不同的页面时，在基址寄存器中只要存放该页面的页框号便可以快速地实现地址转换。所以说，页表项实际上是实现了动态重定位。29 【正确答案】 D【试题解析】 文件的逻辑结构和物理结构是从两个不同观点组织文件的结构而形成的概念。用户根据自己的需要确定文件的逻辑结构，而文件物理结构则是系统设计者根据文件存储器的特性和用户对文件的使用情况来确定的，一旦确定，就由操作系统管理。故正确答案为 D。
18、30 【正确答案】 D【试题解析】 FCB 的存放是不能分开的，所以 1KB 大小的盘块能存放的 FCB 数为：102464=16 ，要注意单位的统一，约定俗成的 KB 一般指 1024B，kB 指1000B。31 【正确答案】 B【试题解析】 本题考查文件路径名的概念。文件的路径名是从根目录到目标文件所经历的路径上各符号名的集合。路径名有二种形式，第一种是绝对路径名，它由根目录出发，沿着目录的路径直到文件，绝对路径名总是从根目录出发，并且是唯一的。第二种是相对路径名，它与工作目录(也称当前目录)一起使用，用户一般预先指定一个目录为当前目录，这时，所有的路径名均从当前目录出发，这样的路径名，只
19、要不是从根目录出发的，都称为相对路径名。32 【正确答案】 C【试题解析】 本题考查对通道和 DMA 的理解。对于 CPu 干预的 IO 操作，程序查询和中断技术都是必要的，而可以解放 CPU 且能控制数据交换的 10 操作只能是通道技术和 DMA 方式。经过分析这两种方式，我们发现，DMA 方式需要将 IO设备的数据口地址映射到内存中，通道是不需要的，所以采用通道控制方式来作此传送是最佳的。33 【正确答案】 C【试题解析】 协议是控制两个对等层实体之间通信的规则的集合，网络协议的三要素是语法、语义和同步，其中语法和语义规定了对等层实体之间所交换的信息的格式和含义，但第 N 层协议要为第 N
20、+1 层提供服务，因此选项 C 的论述是错误的，答案是 C。34 【正确答案】 A【试题解析】 本题考查奈奎斯特定理的直接应用，注意这里采用 8 种不同的状态，因此离散个数为 8，由 C=2Hlog2N=26log28=36Mbps，因此答案为 A。35 【正确答案】 B【试题解析】 本题考查局域网的体系结构，局域网的数据链路层分为逻辑链路控制即 LLC 和媒体接入控制，即 MAC，因此 MAC 子层还是属于链路层，数据传输单元就是 MAC 帧，答案为 B。36 【正确答案】 A【试题解析】 本题考查 CSMACD 协议的基本原理，这里 a 代表单程端到端的传播延时，因此 2a=2100021
21、08=10 微秒。在 1Gbps 速率下，每位的时间为 1纳秒，所以最小帧长为 1010 -3=10000 位=1250 字节，因此答案为 A。37 【正确答案】 B【试题解析】 本题考查信道复用的几种方式，题意指明这种复用是通过划分时间片，因此是时分多路复用，答案为 B。38 【正确答案】 B【试题解析】 本题考查 TCP 流量控制，TCP 采用滑动窗口机制来实现流量控制，并通过接收端来控制发送端的窗口大小，因此这是一种大小可变的滑动窗口协议，因此答案是 B。39 【正确答案】 B【试题解析】 本题考查网络设备中路由器的作用结构和工作原理，路由器是网络互连的关键设备，其任务是转发分组。每个路
22、由器都维护着一个路由表以决定分组的传输路径。当目的主机与源主机不在同一个网络中，则应将数据报发送给源主机所在网络上的某个路由器，由该路由器按照转发表(由路由表构造的)指出的路由将数据报转发给下一个路由器，这种交付方式称为间接交付。I：为了提高路由器的查询效率和减少路由表的内容，路由表只保留到达目的主机的下一个路由器的地址，而不是保留通向目的主机的传输路径上的所有路由信息，故 I 错误。：路由表并不一定包含子网掩码，一般只在划分了子网的网络中，路由器的路由表才使用子网掩码，如果不使用就根本不能得到网络号。而没有划分子网的网络，使用默认的就可以，不需要在路由表上显示，故错误。：路由器的路由表的表项
23、通常包含目的网络和到达该目的网络的下一个路由器的 IP 地址，因为路由器是工作在网络层，网络层使用的是 IP 地址，故正确，：路由器是工作在网络层的设备，对数据链路层是透明的，故 IV 错误。综上，只有正确，因此答案是 B40 【正确答案】 B【试题解析】 本题考查 FTP 的基本原理，FTP 客户与服务器之间一般要建立两个连接，一个是控制连接，一个是数据连接，控制连接在整个会话期间一直保持打开，FTP 客户发出的传送请求通过控制连接发送给服务器端的控制进程，但控制连接不用来传送文件。实际用于传输文件的是“数据连接”。服务器端的控制进程在接收到 FTP 客户发送来的文件传输请求后就创建“数据传
24、送进程”和“数据连接”，用来连接客户端和服务器端的数据传送进程。数据传送进程实际完成文件的传送，在传送完毕后关闭“数据传送连接“并结束运行。因此答案是 B。二、综合应用题41-47 小题，共 70 分。41 【正确答案】 (1)不一定能得到一棵树。 反例(给出任何一个正确的反例即可)： 反例 1：对于先根遍历序列1，2，3，4)，后根遍历序列 1，3，2，4)这种情况，就无法得到一棵树。 反例 2：对于先根遍历序列(1，2，3，4)，后根遍历序列(4，2， 3，1)这种情况，也不能得到一棵树。 理由(题目并不要求说明理由，如果说清了理由而没有给出反例，也可以得分)： 理由一：若一棵树的先根遍历
25、序列为1，2， 3，4)，则 1 必为树根，该树的后根遍历序列中 “1”一定在最后，故根据最后数字不为“1“的后根序列与先根序列1，2，3，4)就无法得到一棵树。 理由二：一棵树可以转换成一棵没有右子树的-y树，反之亦然。所以，对于 n 个结-点的树，可以等价地考虑相应的除去根结点(即 1)以外的(n 一 1)个结点的二叉树问题。在这里，2，3，n 就是相应的二叉树的先序遍历序列，p 1，p 2，p n-1 就是相应-y树的中序遍历序列。对于 n 个结点的树，可以等价地考虑相应的 n-1 个结点的二叉树问题。该问题转换为： 指定 2，3，n 这 n-1 个数为一棵二叉树先序遍历序列；同时 p1
26、，p 2，p n-1(其中 p 1，p 2，p n-1 为 2，3，n这 n-1 个数值的一个排列)为这棵树的二叉树中序遍历序列。是否都可以得到一棵二叉树? 可以证明：对于一棵先序遍历序列为 1，2，n 的二叉树，在中序遍历时其被涉及到的顺序也就是进入运行栈的顺序就是 1，2，n，其中中序遍历顺序，则是一种可能的出栈顺序。有可能从初始输入序列 1，2，n，利用一个栈得到输出序列 p1，p 2pn(p1，p 2，p n 是 1，2，n 的一种排列)的充分必要条件是：不存在这样的 i，j，k，满足 ijki。 因此，先根序列1，2，n 和后根序列 p1，p 2，p n-1，1 能够得到一棵树的充分
27、必要条件是不存在下标 i，j，k，满足 ijki。 (2) 如(1)所述，不一定能得到一棵树。但是如果所给出的序列合法，就能够得到一棵树，而且得到的树是唯一的。 所谓合法序列是指：先根遍历序列为 1，2，n，后根遍历序列为 p1，p 2，p n，那么只有当 pn=1 时，而且在 p1，p 2，p n-1 中不存在这样的 i，j，k，满足 ijki。(不要求考生说明什么是合法的)理由一：一棵树可以转换成一棵没有右子树的二叉树，反之亦然。所以，对于 n 个结点的树，可以等价地考虑相应的除去根结点(即 1)以外的(n1)个结点的二叉树问题。 在这里 2，3，n 就是相应二叉树的先序遍历序列，p 1，
28、p 2，p n-1 就是相应二叉树的中序遍历序列二叉树先序序列为DLR，二叉树中序序列为 LDR，因此可以定位二叉树的根，然后定位出二叉树的左右子树并对左右子树做类似的递归处理，故所的二叉树是唯一的。因此相应的树也是唯一的。 理由二：对于合法的序列：先根序列为 1，2，n，后根序列为p1，p 2，p n-1，1，首先可以确定树根为 1。其子树形成的森林的先根序列为2，n，后根序列为 p1，p 2，p n-1，这些森林被分成 m(m0)个不相交的集合T1，T 2，T m，而且这些集合的每一个又都是树，在先根序列中按照T1，T 2，T m 的结点顺序出现，在后根序列中也按照 T1，T 2，T m
29、的结点顺序出现(但是对应的每个集 Ti 中，结点出现的顺序不同)。因此可以找到每棵子树的结点集合，然后进行递归处理，最终只能得到一棵确定的树。【试题解析】 本题主要考查树的遍历，以及树的遍历与所对应的二叉树的遍历的关系。42 【正确答案】 算法如下：int LocateNode(DuLinkListh，ElemType x)DuLinkList p=h 一next，q；while(p!=NULL&p-data!=x)p=p-next； /找 data 域值为 x 的结点*pif(p=NULL) /未找到这样的结点return 0：else /找到这样的结点*pp-freq+； /频度增 1q=
30、q-prior； /*q 为*p 前驱结点if(q!=h) /若*p 为第一个数据结点，则不移动while(q!=h&q-freqfreq) /找到*q 结点，使 q-freq=p-freqq=q-prior；p-prior-next=p-next； /先删除*p 结点if(p-next!=NULLp-next-prior=p-prior；p-next=q-next； /将*P 结点插入到*q 结点之后if(q-next!=NULL)q-next 一prior=P；q-next=P；p-prior=q； return i；【试题解析】 在 DuLinkList 类型的定义中添加 freq 域(
31、int 类型) ，给该域初始化为 0。在每次查找到一个结点*p 时，使其 freq 域增 1，再在*p 结点的前面找到一个结点*q，它或是头结点或是满足 q 一freq=p 一freq，然后删除*p 结点，使其插入到*q 结点之后。43 【正确答案】 (1)EPROM 芯片数 (分为 2 组)，RAM 芯片数(分为 3 组)。 (2)EPROM 芯片容量为 4K2，具有地址线 12 根，数据线 2 根，连入低 12 位地址线 A11A 0；RAM 芯片容量为 2K4，具有地址线 11根，数据线 4 根，连入低 11 位地址线 A10A 0。 (3)ROM 区有 2 个片选信号，RAM 区有 3
32、 个片选信号，共需 5 个片选信号，根据地址分配的要求，各片选信号的逻辑式如下： 【试题解析】 假设存储器以字节编址，已知 3000 H4FFFH 为 ROM 区，故ROM 的容量为 8KB(4FFF 一 3000+1=2000 H)；又已知 5000H67FFH 为 RAM区，故 RAM 的容量为 6KB(67FF 一 5000+1=1800H)。44 【正确答案】 (1)补充完整的指令流程图如下图所示。 (2)当源操作数为间接寻址时的指令流程图如下图所示。 【试题解析】 指令分为取指阶段和执行阶段两部分，需要两次访问主存，第一次取指令，第二次取数据。若源操作数为间接寻址时，则需要三次访问主
33、存，第一次取指令，第二次取源操作数地址，第三次取数据。45 【正确答案】 (1)系统中各进程尚需资源数如下表 (2)此时安全，因为存在一个安全序列P0，P3，P4，P1，P2)，故该状态是安全的。 (3)当进程 P1 提出请求 (0，4，20)时，可以判断该请求是合理的，因为 P1 尚可以申请的最大请求为(1，7，5，0)，而且，剩余资源(1，6，2，2)也是可以满足其要求的。但是，一旦分配以后，修改请求资源表如下 剩余资源Available(1， 2，0，2)已不能满足上述任何进程的需要。进入不安全状态，所以 P1请求(0 ，4，2，0) 不能分配。【试题解析】 本题是典型的银行家算法的题目
34、。银行家算法的题目相对比较固定，复杂度也不高，只要思路正确，一般不会有太大困难。46 【正确答案】 采用旧办法时检索一个目录项需要访问磁盘 325 次。采用新办法时检索一个目录项需要访问磁盘 55 次。【试题解析】 本题是接近实际的计算题。根据已知，目录文件共有 254 个文件控制块(即目录项)，每个盘块为 512B，目录项(文件控制块) 占 128B。采用旧办法时，1 个盘块可存放：512B128B=4 个目录项，则 254 个目录项要占：INT254464 块。平均查找一个目录项需访问磁盘：(1+64)2=325 次。采用新方法后，将目录项分解成两部分，第一部分占 16B，第二部分占 12
35、2B。一个盘块可存放的用于检索的文件名和内部号部分为 512B16B=32 个目录项，这样 254 个目录项要占：INT254328 个盘块。平均查找一个目录项需要访问磁盘：(1+8)2=45 次。而为得到目录项的其它信息还应访问一次磁盘，故需访盘：45+1=5 5 次。因此，采用新办法可以有效地降低访问磁盘的次数。47 【正确答案】 本题利用 Dijkstra 算法求出最短路径树，从而得到结点 A 路由表。计算过程如下： 【试题解析】 Dijkstra 算法是一种求单源最短路径树的算法，是 OSPF 路由协议的核心算法，该算法基本原理是：每次新扩展一个距离最短的点，更新与其相邻的点的距离。当
36、所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。在以下算法中，s 为源，wu，v为点 u 和 v 之间的边的长度，结果保存在 dist(1)初始化：源的距离 dists设为 0，其他的点距离设为无穷大，同时把所有的点的状态设为没有扩展过。(2)循环 n 一 1 次：在没有扩展过的点中取一距离最小的点 u，并将其状态设为已扩展。对于每个与 u 相邻的点 v，执行 Relax(u，v)，也就是说，如果 distu+wu，vdistv，那么把 distv更新成更短的距离 distu+wu，v。此时到点 v 的最短路径上，前一个节点即为 u。(3)结束。此时对于任意的 u，distu就是 s 到 u 的距离。
