题目

●试题五
阅读以下预备知识、函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。
【预备知识】
①对给定的字符集合及相应的权值，采用哈夫曼算法构造最优二叉树，并用结构数组存储最优二叉树。例如，给定字符集合{a，b，c，d}及其权值2、7、4、5，可构造如图3所示的最优二叉树和相应的结构数组Ht(数组元素Ht［0］不用)(见表5)。

图3最优二叉树
表5 结构数组Ht

结构数组Ht的类型定义如下：
define MAXLEAFNUM 20
struct node{
char ch;/当前结点表示的字符，对于非叶子结点，此域不用/
int weight;/当前结点的权值/
int parent;/当前结点的父结点的下标，为0时表示无父结点/
int lchild,rchild;
/当前结点的左、右孩子结点的下标，为0时表示无对应的孩子结点/
}Ht［2*MAXLEAFNUM］;
②用′0′或′1′标识最优二叉树中分支的规则是：从一个结点进入其左(右)孩子结点，就用′0′(′1′)标识该分支(示例如图3所示)。
③若用上述规则标识最优二叉树的每条分支后，从根结点开始到叶子结点为止，按经过分支的次序，将相应标识依次排列，可得到由′0′、′1′组成的一个序列，称此序列为该叶子结点的前缀编码。例如图3所示的叶子结点a、b、c、d的前缀编码分别是110、0、111、10。
【函数5．1说明】
函数void LeafCode(int root,int n)的功能是：采用非递归方法，遍历最优二叉树的全部叶子结点，为所有的叶子结点构造前缀编码。其中形参root为最优二叉树的根结点下标；形参n为叶子结点个数。
在构造过程中，将Ht［p］．weight域用作被遍历结点的遍历状态标志。
【函数5．1】
char**Hc；
void LeafCode(int root,int n)
{/为最优二叉树中的n个叶子结点构造前缀编码，root是树的根结点下标/
int i,p=root,cdlen=0;char code［20］;
Hc=(char)malloc((n+1)sizeof(char));/申请字符指针数组/
for(i=1;i＜=p;++i)
Ht［i］．weight=0;/遍历最优二叉树时用作被遍历结点的状态标志/
while(p){/以非递归方法遍历最优二叉树，求树中每个叶子结点的编码/
if(Ht［p］．weight==0){/向左/
Ht［p］．weight=1;
if (Ht［p］．lchild !=0) { p=Ht［p］．lchild; code［cdlen++］=′0′;}
else if (Ht［p］．rchild==0) {/若是叶子结点，则保存其前缀编码/
Hc［p］=(char)malloc((cdlen+1)sizeof(char));
(1) ;strcpy(He［p］，code);
}
}
else if (Ht［p］．weight==1){/向右/
Ht［p］．weight=2;
if(Ht［p］．rchild !=0){p=Ht［p］．rchild;code［cdlen++］=′1′;}
}
else{/Ht［p］．weight==2,回退/
Ht［p］．weight=0;
p= (2) ; (3) ;/退回父结点/
}
}/while结束/
}
【函数5．2说明】
函数void Decode(charbuff,int root)的功能是：将前缀编码序列翻译成叶子结点的字符序列并输出。其中形参root为最优二叉树的根结点下标;形参buff指向前缀编码序列。
【函数5．2】
void Decode(charbuff,int root)
{ int pre=root,p;
while(buff!=′＼0′){
p=root;
while(p!=0){/存在下标为p的结点/
pre=p;
if((4) )p=Ht［p］．lchild;/进入左子树/
else p=Ht［p］．rchild;/进入右子树/
buff++;/指向前缀编码序列的下一个字符*/
｝
(5) ;
printf(″%c″,Ht［pre］．ch);
}
}

答案

查看答案

相关试题

试题二（25分）

阅读以下关于某网络系统结构的叙述，回答问题1、问题2和问题3。

某公司的网络结构如图2-1所示，所有路由器、交换机都采用Cisco产品，路由协议采用OSPF协议，路由器各接口的IP地址参数等如表2-1所示。

为了保证各区域的地址连续性，便于实现路由汇总，各区域的地址范围如下：

Area 0 —— 10.0.0.0/13

Area 1 —— 10.8.0.0/13

Area 2 —— 10.192.0.0/13

Area 3 —— 10.224.0.0/13

[问题1]（6分）

假设路由体系中OSPF进程号的ID为1，则对于拥有三个快速以太网接口的路由器R7,如果仅希望OSPF进程和接口Fa0/0、Fa1/0相关联，而不和Fa2/0关联，也就是说只允许

接口Fa0/0、Fa1/0使用OSPF进程，请写出路由器R7上的OSPF进程配置。

[问题 2]（9分）

在Area 1中，路由器R4、R5和R6通过一台交换机构成的广播局域网络互连，各路由器ID由路由器

loopback接口地址指定，如指定R4是指派路由器（Designated Routers, DR）、R5为备份的指派路由器（Backup Designated Router, BDR），而R6不参与指派路由器的选择过程。

配置路由器R6时，为使其不参与指派路由器的选择过程，需要在其接口Fa0/0上添加配置命令_（a）。

在配置路由器R4与R5时，如果允许修改路由器的loopback接口地址，可以采用两种方式，让R4成为DR，而R5成为BDR，这两种可行的方法分别是：（b）。（c）。

[问题 3]（10 分）

OSPF协议要求所有的区域都连接到OSPF主干区域0，当一个区域和OSPF主干区域0的网络之间不存在物理连接或创建物理连接代价过高时，可以通过创建OSPF虚链路（virtual link）的方式完成断开区域和主干区域的互连。在该公司的网络中，区域3和区域0之间也需要通过虚拟链路方式进行连接，请给出路由器R3和路由器R8上的OSPF进程配置信息。

查看答案解析

试题二（共15分）

阅读以下说明，回答问题1至问题5，将解答填入答题纸对应的解答栏内。

【说明】

某公司要在 Windows 2003 Server 上搭建内部FTP服务器，服务器分配有一个静态的公网IP地址228.121.12.38。FTP服务器的创建可分为安装、配置、测试等三个过程。其中图2-1和图2-2分别为配置过程中FTP站点创建和 FTP站点属性的配置窗口。

【问题1】（2分）

在Windows 2003中安装FTP服务，需在“应用程序服务器”选项的（1）组件复选框中选择“文件传输协议(FTP)服务”进行安装。

（1）备选答案：

A. ASP.NET

B. Internet信息服务(IIS)

C. 应用程序服务器控制台

D. 启用网络服务

【问题2】（4分）

在图2-1中，在“输入此FTP站点使用的 IP地址”文本框中应填入（2），默认情况下“输入此FTP站点的TCP端口”文本框中应填入（3）。

【问题3】（2分）

在图2-2中，如果FTP资源存储在F盘，新建FTP站点的默认主目录为（4）。

（4）备选答案：

A. F:inetpubftproot

B. F:ftp

C. F:ftproot

D. F:inetpubwwwroot

【问题4】（4分）

FTP服务器配置完成后，可以在网络上另一台 PC中测试 FTP是否配置成功。测试过程为：在该计算机上命令行模式下输入命令（5），在出现 USER提示时输入 FTP服务器上计算机管理员名称和密码就可以登陆了。如果该 FTP上开启了匿名访问功能，在用户名处输入（6），密码处填写一个 Email地址也可以登录。

（6）备选答案：

A. anonymous B. user C. administrator

【问题5】（3分）

依据图2-2的配置，该FTP服务器配置完成后，用户可以上传文件吗？为什么？

查看答案解析

●试题一

阅读下列说明和流程图，将应填入(n)的语句写在答题纸的对应栏内。

【流程图】