1、软件水平考试（中级）软件设计师上午（基础知识）试题章节练习试卷 5及答案与解析 1 进程 PA不断地向管道写数据，进程 PB从管道中读数据并加工处理，如图 3-4所示。如果采用 PV操作来实现进程 PA和进程 PB间的管道通信，并且保证这两个进程并发执行的正确性，则至少需要 _。 （ A） 1个信号量，信号量的初值为 0 （ B） 2个信号量，信号量的初值分别为 0， 1 （ C） 3个信号量，信号量的初值分别为 0， 0， 1 （ D） 4个信号量，信号量的初值分别为 0， 0， 1， 1 2 假设系统中有三类互斥资源 R1， R2和 R3，可用资源数分别为 9， 8和 5。在 T0时刻系统
2、中有 P1， P2， P3， P4和 P5五个进程，这些进程对资源的最大需求量和已分配资源数如表 3-2所示。如果进程按 _ 序列执行，那么系统状态是安全的。 （ A） P1P2P4P5P3 （ B） P2P1P4P5P3 （ C） P2P4P5P1P3 （ D） P4P2P5P1P3 3 如果主存容量为 16M字节，且按字节编址，表示该主存地址至少应需要 _ 位。 （ A） 16 （ B） 20 （ C） 24 （ D） 32 4 在计算机系统中构成虚拟存储器 _。 （ A）只需要一定的硬件资源便可实现 （ B）只需要一定的软件即可实现 （ C）既需要软件也需要硬件方可实现 （ D）既不需要
3、软件也不需要硬件 5 页式存储系统的逻辑地址是由页号和页内地址两部分组成的。假定页面的大小为4KB，地址变换过程如图 3-8所示，图中逻辑地址用十进制数表示。图中有效地址经过变换后，十进制数物理地址 a应为 _。 （ A） 33220 （ B） 8644 （ C） 4548 （ D） 2500 6 假设某计算机系统的主存大小为 256KB，在某一时刻主存的使用情况如表 3-3所示。此时，若进程顺序请求 20KB、 10KB和 55的存储空间，系统采用 _ 算法为进程依次分配主存，则分配后的主存情况如表 3-4所示。 （ A）最佳适应 （ B）最差适应 （ C）首次适应 （ D）循环首次适应 7
4、 使 Cache命中率最高的替换算法是 _。 （ A）先进先出算法 FIFO （ B）随机算法 RAND （ C）先进后出算法 FILO （ D）最近最少使用的页面替换算法 LRU 8 某软盘有 40个磁道，磁头从一个磁道移至另一个磁道需要 5ms。文件在磁盘上非连续存放，逻辑上相邻数据块的平均距离为 10个磁道，每块的旋转延迟时间及传输时间分别为 100ms和 25ms，则读取一个 100块的文件需要 _时间。 （ A） 17500ms （ B） 15000ms （ C） 5000ms （ D） 25000ms 9 文件系统中，设立打开文件 (Open)系统功能调用的基本操作是 _。 （ A
5、）把文件信息从辅存读到内存 （ B）把文件的控制管理信息从辅存读到内存 （ C）把磁盘的超级块从辅 存读到内存 （ D）把文件的 FAT表信息从辅存读到内存 10 假设在系统中一个文件有两个名字，它与一个文件保存有两个副本的区别是 _。 （ A）前者比后者所占用的存储空间更大 （ B）前者需要两个目录项，后者只需要一个目录项 （ C）前者存取文件的速度快，后者存取文件的速度慢 （ D）前者改变与某个名字相联系的文件时，与另一个名字相联系的文件也改变：后者的另一个副本不改变 11 在文件存储设备管理中，有三类常用的空闲块管理方法，即位图向量法，空闲块链表连接法和 _。 （ A）一级目 录法 （
6、B）多级自录法 （ C）分区法 （ D）索引法 12 在 UNIX操作系统中，把输入 /输出设备看做 _。 （ A）普通文件 （ B）目录文件 （ C）索引文件 （ D）特殊文件 13 在 UNIX操作系统中，若用户键入的命令参数的个数为 1时，执行 cat 1命令；若用户键入的命令参数的个数为 2时，执行 cat 2 1命令。请将下面所示的 Shell程序的空缺部分补齐。 case _ in1)cat 1;2)cat 2 1;*)echo default.esac （ A） （ B） （ C） # （ D） * 14 在 UNIX操作系统中，当用户执行如下命令 Link(“/user/inc
7、lude/myfile.sh“，“/usr/userwang/youfile.sh“)则文件名 “/usr/userwang/youfile.sh“存放在 _。 （ A） user目录文件中 （ B） include目录文件中 （ C） userwang目录文件中 （ D） youfile.sh的文件内容中 15 多媒体应用需要对庞大的数据进行压缩，常见的压缩编码方法可分为 两大类，一类是无损压缩法，另一类是有损压缩法，也称 (2)。 (3)属于无损压缩法。 （ A）熵编码 （ B）熵压缩法 （ C） MPEG压缩法 （ D） JPEG压缩法 （ A） MPEG压缩 （ B）子带编码 （ C）
8、 Huffman编码 （ D）模型编码 17 若磁盘的写电流波形如图 6-1所示。 图中 波形的记录方式是 (8)， 波形的记录方式是 (9)。 （ A）调频制 (FM) （ B）改进调频制 (MFM) （ C）调相制 (PE) （ D）不归零制 (NRZ) （ A）调频制 (FM) （ B）改进调频制 (MFM) （ C）调相制 (PE) （ D）不归零制 (NRZ) 19 声音的三要素为音调、音强和音色，其中音色是由混入基音的 (10)决定的。若对声音以 22.05kHz的采样频率、 8位采样深度进行采样，则 10分钟双声道立体声的存储量为 (11)字节。 （ A）响度 （ B）泛音 （
9、C）高音 （ D）波形声音 （ A） 26460000 （ B） 441000 （ C） 216000000 （ D） 108000000 21 MIDI是一种数字音乐的国际标准， MIDI文件存储的 (12)。它的重要特色是(13)。 （ A）不 是乐谱而是波形 （ B）不是波形而是指令序列 （ C）不是指令序列而是波形 （ D）不是指令序列而是乐谱 （ A）占用的存储空间少 （ B）乐曲的失真度少 （ C）读写速度快 （ D）修改方便 23 若每个像素具有 8位的颜色深度，则可表示 (27)种不同的颜色。若某个图像具有 640480个像素点，其未压缩的原始数据需占用 (28)字节的存储空间
10、。 （ A） 8 （ B） 128 （ C） 256 （ D） 512 （ A） 1024 （ B） 19200 （ C） 38400 （ D） 307200 25 MPEG是 一种 (40)，它能够 (41)。 （ A）静止图像的存储标准 （ B）音频、视频的压缩标准 （ C）动态图像的传输标准 （ D）图形国家传输标准 （ A）快速读写 （ B）有高达 200:1的压缩比 （ C）无失真地传输视频信号 （ D）提供大量基本模板 27 用二进制加法器对二一十进制编码的十进制数求和，当和的本位十进制数二一十进制编码小于等于 1001且向高位无进位时， (14)；当和小于等于 1001且向高位有
11、进位时， (15)；当和大于 1001时， (16)。 （ A）不需进行修正 （ B）需进行加 6修正 （ C）需进行减 6修正 （ D）进行加 6或减 6修正，需进一步判别 （ A）不需进行修正 （ B）需进行加 6修正 （ C）需进行减 6修正 （ D）进行加 6或减 6修正，需进一步判别 （ A）不需进行修正 （ B）需进行加 6修正 （ C）需进行减 6修正 （ D）进行加 6或减 6修正，需进一步判别 30 操作数所处的位置，可以决定指令的寻址方式。操作数包含在指令中，寻址方式为 (37)；操作数在寄存器中，寻址方式为 (38)；操作数的地址在寄存器中，寻址方式为 (39)。 （ A
12、）立即寻址 （ B）直接寻址 （ C）寄存 器寻址 （ D）寄存器间接寻址 （ A）立即寻址 （ B）相对寻址 （ C）寄存器寻址 （ D）寄存器间接寻址 （ A）相对寻址 （ B）直接寻址 （ C）寄存器寻址 （ D）寄存器间接寻址 33 一般来说， Cache的功能 (71)。某 32位计算机的 Cache容量为 16KB， Cache块的大小为 16B，若主存与 Cache的地址映射采用直接映射方式，则主存地址1234E8F8(十六进制数 )的单元装入的 Cache地址为 (72)。在下列 Cache替换算法中，平均命中率最高的是 (73)。 （ A）全部由软件实现 （ B）全部由硬件实
13、现 （ C）由硬件和软件相结合实现 （ D）有的由硬件实现，有的由软件实现 （ A） 00010001001101(二进制数 ) （ B） 01001000110100(二进制数 ) （ C） 10100011111000(二进制数 ) （ D） 11010011101000(二进制数 ) （ A）先进后出 (FILO)算法 （ B）随机替换 (RAND)算法 （ C）先进先出 (FIFO)算法 （ D）最近最少使用 (LRU)算法 36 假设一个有 3个盘片的硬盘，共有 4个记录面，转速为 7200rpm，盘 面有效记录区域的外直径为 30cm，内直径为 10cm，记录位密度为 250位 /
14、mm，磁道密度为8道 /mm，每磁道分 16个扇区，每扇区 512字节，则该硬盘的非格式化容量和格式化容量约为 (75)，数据传输率约为 (76)，若一个文件超出一个磁道容量，剩下的部分 (77)。 （ A） 120MB和 100MB （ B） 30MB和 25MB （ C） 60MB和 50MB （ D） 22.5MB和 25MB （ A） 2356Kb/s （ B） 3534Kb/s （ C） 7069Kb/s （ D） 1178Kb/s （ A）存于同一盘面的其他 编号的磁道上 （ B）存于其他盘面的同一编号的磁道上 （ C）存于其他盘面的其他编号的磁道上 （ D）存放位置随机 39 O
15、MT是一种对象建模技术，它定义了三种模型，它们分别是 (39)模型、 (40)模型和 (41)模型，其中， (39)模型描述了系统中对象的静态结构，以及对象之间的联系； (40)模型描述系统中与时间和操作顺序有关的系统特征，表示瞬时行为上的系统的 “控制 ”特征，通常可用 (42)来表示： (41)模型描述了与值的变换有关的系统特征，通常可用 (43)来表示。 （ A）对象 （ B）功能 （ C） ER （ D）静态 （ A）控制 （ B）时序 （ C）动态 （ D）实时 （ A）对象 （ B）功能 （ C）变换 （ D）计算 （ A）类图 （ B）状态图 （ C）对象图 （ D）数据流图 （
16、 A）类图 （ B）状态图 （ C）对象图 （ D）数据流图 一、主观题 44 阅读下列说明、图和 C代码，将应填入 (n)处的字句写在对应栏内。 【说明 5-1】 B树是一种多叉平衡查找树。一棵 m阶的 B树，或为空树，或为满足下列特性的 m叉树： 树中每个节点至多有 m棵子树； 若根节点不是叶子节点，则它至少有两棵子树 ； 除根之外的所有非叶子节点至少有 m/2棵子树； 所有的非叶子节点中包含下列数据信息 (n， A0， K1， A1， K2， A2， ， Kn， An)，其中：Ki(i=1， 2， ， n)为关键字，且 Ki Ki+1(i=1， 2， ， n-1)， Ai(i=0， 1，
17、 ， n)为指向子树根节点的指针，且指针 Ai-1所指子树中所有节点的关键字均小于 Ki，Ai+1所指子树中所有节点的关键字均大于 Ki， n为节点中关键字的数目； 所有的叶子节点都出现在同一层次上，并且不带信息 (可以看成是外部节点或查找失败的节点，实际上这些节点不存在 ，指向这些节点的指针为空 )。 例如，一棵 4阶 B树如图 5-1所示 (节点中关键字的数目省略 )。 B树的阶 M、 bool类型、关键字类型及 B树节点的定义如下： #define M 4 /*B树的阶 */ typedef enumFALSE=0,TRUE=1bool; typedef int ElemKeyType;
18、 typedef struct BTreeNode int numkeys; /*节点中关键字的数目 */ struct BTreeNode *parent; /*指向父节点的指针，树根的父节点指针为 空 */ struct BTreeNode *AM; /*指向子树节点的指针数组 */ ElemKeyType KM; /*存储关键字的数组， K0闲置不用*/ BTreeNode； 函数 SearchBtree(BTreeNode* root， ElemKeyType akey，BTreeNode *ptr)的功能是：在给定的一棵 M阶 B树中查找关键字 akey所在节点，若找到则返回 TRU
19、E，否则返回 FALSE。其中， root是指向该 M阶 B树根节点的指针，参数 ptr返回 akey所在节点的指针，若 akey不在该 B树中，则 ptr返回查找失败时空指针所在节点的指针。例如，在如图 5-1所示的 4阶 B树中查找关键字 25时， ptr返回指向节点 e的指针。 注：在节点中查找关键字 akey时采用二分法。 【函数 5-1】 bool SearchBtree(BTreeNode* root, ElemKeyType akey, BTreeNode *ptr) int lw,hi,mid; BTreeNode *p=root; *pb=NULL; while(p) lw=
20、1;hi=(1); while(lw =hi) mid=(lw+hi)/2; if(p- Kmid=akey) *Ptr=p; return TRUE; else if(2) hi=mid-1; else lw=mid+1; *ptr=p; p=(3); return FALSE; 【说明 5-2】 在 M阶 B树中插入一个关键字时，首先在最接近外部节点的某个非叶子节点中增加一个关键字，若该节点中关键字的个数不超过 M-1，则完成插入；否则，要进行节点的 “分裂 ”处理。所谓 “分裂 ”，就是把节点中处于中间位置上的关键字取出来并插入其父节点中， 然后以该关键字为分界线，把原节点分成两个节点。
21、 “分裂 ”过程可能会一直持续到树根，若树根节点也需要分裂，则整棵树的高度增 1。 例如，在如图5-1所示的 B树中插入关键字 25时，需将其插入节点 e中，由于 e中已经有 3个关键字，因此将关键字 24插入节点 e的父节点 b，并以 24为分界线将节点 e分裂为e1和 e2两个节点，结果如图 5-2所示。 函数 Isgrowing(BTreeNode* root， ElemKeyType akey)的功能是：判断在给定的 M阶 B树中插入关键字 akey后，该 B树的高度是否增加，若增加则返回 TRUE，否则返回 FALSE。其中， root是指向该 M阶 B树根节点的指针。 在函数 Is
22、growing中，首先调用函数 SearchBtree(即函数 5-1)查找关键字 akey是否在给定的 M阶 B树中，若在则返回 FALSE(表明无须插入关键字 akey，树的高度不会增加 )；否则，通过判断节点中关键字的数目考察插入关键字 akey后该 B树的高度是否增加。 【函数 5-2】 bool Isgrowing(BTreeNode* root,ElemKeyType akey) BTreeNode *t,*f; if(!SearchBtree(4) t=f; while(5) t=t- parent; if(!t) return TRUE; return FALSE; 45 阅读
23、以下函数说明、图和 C代码，将应填入 (n)处的字句写在对应栏内。 【说明】 散列文件的存储单位称为桶 (BUCKET)。假如一个桶能存放 m个记录，当桶中已有 m个同义词 (散列函数值相同 )的记录时，存放第 m+1个同义词会发生 “溢出 ”。此时需要将第 m+1个同义词存放到另一个称为 “溢出桶 ”的桶中。相对地，称存放前 m个同义词的桶为 “基桶 ”。 溢出桶和基桶大小相同，用指针链接。查找指定元素记录时，首先在基桶中查找。若找到，则成功返回，否则沿指针到溢出桶中进行查找。 例如：设散列函数为 Hash(Key)=Key mod 7，记录的关键字序列为15， 14， 21， 87， 96
24、， 293， 35， 24， 149， 19， 63， 16， 103， 77， 5， 153，145， 356， 51， 68， 705， 453，建立的散列文件内容如图 5-3所示。 为简化起见，散列文件的存储单位以内存单元表示。 函数 InsertToHashTable(int NewElemKey)的功能是 ；若新元素 NewElemKey正确插入散列文件中，则返回值1；否则返回值 0。 采用的散列函数为 Hash(NewElemKey)=NewElemKey % P，其中 P为设定的基桶数目。 函数中使用的预定义符号如下： #define NULLKEY-1 /*散列桶的空闲单元标识
25、 */ #define P 7 /*散列文件中基桶的数目 */ #define ITEMS 3 /*基桶和溢出桶的容量 */ typedef struet BucketNode /*基桶和溢出桶的类型定义 */ int KeyDataITEMS; struct BucketNode *Link; BUCKET; BUCKET BucketP; /*基桶空间定义 */【函数 5-3】 int InsertToHashTable(int NewElemKey) /*将元素NewElemKey插入散列桶中，若插入成功则返回 0，否则返回 -1*/ /*设插入第一个元素前基桶的所有 KeyData，
26、Link域已分别初始化为 NULLKEY、 NULL*/ int Index; /*基桶编号 */ int i,k BUCKET *s,*front,*t; (1); for(i=0;i ITEMS;i+) /*在基桶查找空闲单元，若找到则将元素存入 */ if(BucketIndex.KeyDatai=NULLKEY) BucketIndex.KeyDatai=NewElemKey; break; if(2)return 0; /* 若基桶已满，则在溢出桶中查找空闲单元，若找不到则申请新的溢出桶 */ (3); t=BucketIndex.Link; if(t!=NULL) /*有溢出桶 *
27、/ while(t!=NULL) for(k=0;k ITEMS;k+) if(t- KeyDatak=NULLKEY)/* 在溢出桶链表中找到空闲单元 */ t- KeyDatak=NewElemKey; break; /*if*/ front=t; if(4)t=t- Link; else break; /*while*/ /*if*/ if(5) /* 申请新溢出桶并将元素存入*/ s=(BUCKET *)malloc(sizeof(BUCKET); if(!s)retum -1; s- Link=NULL; for(k=0;k ITEMS;k+) s- KeyDatak=NULLKEY
28、; s- KeyData0=NewElemKey; (6); /*if*/ return 0; /*InsertToHashTable*/ 46 阅读下列函数说明和 C代码，将应填入 (n)处的字句写在对应栏内。【说明】 函数 int Toplogcal(LinkedWDigraph G)的功能是对图 G中的顶点进行拓扑排序，并返回关键路径的长度。其中图 G表示一个具有 n个顶点的 AOE网，图中顶点从 1 n依次编号，图 G的存储结构采用邻接表表示，其数据类型定义如下： typedef struct Gnode /*邻接表的表节点类型 */ int adjvex; /*邻接顶点编号 */ i
29、nt weieht; /*弧上的权值 */ stract Gnode *nextarc; /*指示下一个弧的节点 */ Gnode; typedef struct Adjlist /*邻接表的头节点类型 */ char vdata; /*顶点的数据信息 */ struct Gnode *Firstadj; /*指向邻接表的第一个表节点 */ Adjlist; typedef struct LinkedWDigraph /*图的类型 */ int n,e; /*图中顶点个数和边数 */ struct Adjlist *head; /*指向图中第一个顶点的邻接表的头节点 */ LinkedWDig
30、raph; 例如，某 AOE网如图 5-4所示，其邻接表存储结构如图 5-5所示。 int Toplogical(LinkedWDigraph G) Gnode *p; int j,w,top=0; int *Stack,*ve,*indegree; ve=(int*)malloc(G.n+1)*sizeof(int); indegree=(int*)malloc(G.n+1)*sizeof(int); /*存储网中各顶点的入度 */ Stack=(int*)malloe(G.n+1)*sizeof(int); /*存储入度为 0的顶点的编号 */ if(!ve|!indegree|!Stac
31、k)exit(0); for(j=1;j=G.n;j+) vej=0;indegreej=0; /*for*/ for(j=1;j =G.n;j+) /*求网中各顶点的入度 */ p=G.headj.Firstadj; while(p) (1); p=p- nextarc; /*while*/ /*for*/ for(j=1;j=G.n;j+) /*求网中入度为 0的顶点并保存其编号 */ if(!indegreej)Stack+top=j; while(top 0) w=(2); printf(“%c“,G.headw.vdata); p=G.headw.Firstadj; while(p)
32、 (3); if(!indegreep- adjvex) Stack+top=p- adjvex; if(4) vep-adjvex=vew+p- weight; p=p- nextarc; /*while*/ /*while*/ return (5); /*Toplogical*/ 47 阅读下列函数说明和 C函数，将应填入 (n)处的字句写在对应栏内。 【说明】 函数 DeleteNode(Bitree*r， inte)的功能是：在树根节点指针为 r的二叉查找 (排序 )树上删除键值为 e的节点，若删 除成功，则函数返回 0，否则函数返回 -1。二叉查找树节点的类型定义为： typedef
33、 struct Tnode int data;/*节点的键值 */ struct Tnode *Lchild,*Rchiid;/*指向左、右子树的指针 */ *Bitree; 在二叉查找树上删除一个节点时，要考虑 3种情况。 若待删除的节点 p是叶子节点，则直接删除该节点。 若待删除的节点 p只有一个子节点，则将这个子节点与待删除节点的父节点直接连接，然后删除节点。 若待删除的节点 p有两个子节点，则在其左子树上，用中序遍历寻找关键值最大的节点 s，用节点 s的值代替节点 p的值，然后删除节点 s，节点 s必属于上述 、 情况之一。 【函数 5-5】 int DeleteNode(Bitree
34、 *r,int e) Bitree p=*r,pp,s,c; while( (1) /*从树根节点出发查找键值为 e的节点 */ pp=p; if(e p- data)p=p- Lchild; else p=p- Rehild; if(!p)retrn -1;/*查找失败 */ if(p- Lchild pp=p; while( (3)pp=s;s=s- Rchild; p- data=s- data;p=s; /* 处理情况 、 */ if(4)c=p- Lchild; else c=p- Rchild; if(p= *r)*r=c; else if(5)pp- Lchild=c; else
35、 pp- Rchild=c; free(p); return 0; 48 阅读以下预备知识、函数说明和 C代码，将应填入 (n)处的字句写在对应栏内。【预备知识】 对给定的字符集合及相应的权值，采用哈夫曼算法构造最优二叉树，并用结构数组存储最优二叉树。例如，给定字符集合 a， b， c， d及其权值2、 7、 4、 5，可构造如图 5-6所示的最优二叉树和相应的结构数组 Ht(数组元素Ht0不用 )。 结构数组Ht的类型定义如下： #define MAXLEAFNUM 20 struct node char ch; /*当前节点表示的字符，对于非叶子节点，此域不用 */ int weight;
36、 /*当前节点的权值 */ int parent; /*当前节点的父节点的下标，为 0时 表示无父节点 */ int lchild,rchild; /*当前节点的左、右孩子节点的下标，为 0时表示无对应的孩子节点 */ Ht2*MAXLEAFNUM; 用 “0”或 “1”标识最优二叉树中分支的规则是：从一个节点进入其左 (右 )孩子节点，就用 “0”(“1”)标识该分支 (示例见图 5-6)。 若用上述规则标识最优二叉树的每条分支后，从根节点开始到叶子节点为止，按经过分支的次序，将相应标识依次排列，可得到由 “0”、 “1”组成的一个序列，称此序列为该叶子节点的前缀编码。例如图 5-6所示的叶
37、子节点 a、 b、 c、 d的前缀编码分别是 110、 0、 111、 10。 【函数5-6说明】 函数 void LeafCode(int root， int n)的功能是：采用非递归方法，遍历最优二叉树的全部叶子节点，为所有的叶子节点构造前缀编码。其中形参 root为最优二叉树的根节点下标，形参 n为叶子节点个数。 在构造过程中，将 HtP.weight域用做被遍历节点的遍历状态标志。 【函数 5-6】 char *Hc; void LeafCode(int root, int n) /*为最优二叉树中的 n个叶子节点构造前缀编码， root是树 的根节点下标 */ int i,p=roo
38、t,cdlen=0; char code20; Hc=(char*)maloc(n+1)*sizeof(char*); /*申请字符指针数组 */ for(i=1;i =p;+i) Hti.weight=0; /*遍历最优二叉树时用做被遍历节点的状态标志 */ while(p) /*以非递归方法遍历最优二叉树，求树中每个叶子节点的编码 */ if(Htp.weight=0)/*向左 */ Htp.weight=1; if(Htp.lchild !=0) p=Htp.lchild; codecdlen+=0; else if(Htp.rchild=0) /*若是叶子节点，则保存其前缀编码 */
39、Hcp=(char *)malloc(cdlen+1)*sizeof(char); (1); strcpy(Hcp,code); else if(Htp.weight=1)(/*向右 */ Htp.weight=2; if(Htp.rchild !=0) p=Htp.rchild; codeedlen+=1; else /*Htp.weight=2，回退 */ Htp.weight=0; p=(2); (3); /*退回父节点 */ /*while结束 */ 【函数 5-7说明】 函数 void Decode(char *buff,int root)的功能是：将前缀编码序列翻译成叶子节点的字符
40、序列，并输出。其中形参 root为最优二叉树的根节点下标，形参 buff指向前缀编码序列。 【函数 5-7】 void Decode(char *buff,int root) int pre=root,p; while(*buff !=0) p=root; while(p !=0)/* 存在下标为 p的节点 */ pre=p; if(4)p=Htp.lchild; /*进入左子树 */ else p=Htp.rchild; /*进入右子树 */ buff+; /*指向前缀编码序列的下一个字符 */ (5); printf(“%c“,Htpre.ch); 49 阅读下列程序说明和 C代码，将应填
41、入 (n)处的字句写在对应栏内。 【说明】 设 M叉树采用列表 法表示，即每棵子树对应一个列表，列表的结构为：子树根节点的值部分 (设为一个字符 )和用 “()”，括起来的各子树的列表 (如有子树的话 )，各子列表间用 “， ”分隔。例如下面的三叉树可用列表 a(b(c， d)， e， f(g， h， i)表示。 本程序输入列表，生成一棵 M叉树，并由 M叉树输出列表。假定输入无错误。 【函数 5-8】 #inelude stdio.h #include stdlib.h #define M3 typedef struct node char val; street node *subTree
42、M; NODE; char buf255, *six = buf; NODE *d = NULL; NODE *makeTree()/*由列表生成 M叉树 */ int k; NODE *s; s=(1); s- val=*six+; for(k=0; k M; k+)s- subTreek=NULL; if(*str=() k=0; do six+; s- subTreek=(2); if(*str=) six+; break; k=k+1; while(3); return s; void walkTree(NODE *t)/*由 M叉数输出列表 */ int i; if(t !=NULL
43、) (4); if(t- subTree0=NULL)return; putchar(); for(i=0;i M; i+) (5); if(i !=M-1 putchax(); void main() prinff(“Enter exp:“); scanf(“%s“, str); d = makeTree(); walkTree(d); putchaW,n); 50 阅读下列程序说明和 C代码，将应填入 (n)处的字句写在对应栏内。 【说明】 设某城市有 n个车站，并有 m条公交线路连接这些车站，设这些公交车都是单向的，这 n个车站被顺序编号为 0至 n-1。输入该城市的公交线路数、车站个数
44、，以及各公交线路上的各站编号，求得从站 0出发乘公交车至站 n-1的最少换车次数。 程序利用输入信息构建一张有向图 G(用邻接矩阵 g表示 )，有向 图的顶点是车站，若有某条公交线路经 i站能到达 j站，就在顶点 i到顶点 j之间设置一条权为 1的有向边 i,j。如是这样，从站点 x至站点 y的最少上车次数便对应图 G中从点x至点 y的最短路径长度。而程序要求的换车次数就是上车次数减 1。 【函数 5-9】 #include stdio.h #define M 20 #define N 50 int aN+1; /*用于存放一条线路上的各站编号 */ iht gNN; /*存储对应的邻接矩阵
45、*/ int distN; /*存储站 0到各站的最短路径 */ int m,n; void buildG() int i,j,k,sc,dd; printf (“输入公交线路数，公交站数 n“); scanf(“%d%d“, for(i=0; i n; i+) /*邻接矩阵清 0*/ for(j = 0; j n; j+)gij = 0; for(i=0; i m; i+) printf(“沿第 %d条公交车线路前进方向的各站编号 (O =编号 =%d,-1结束 ):n“, i+1, n-1); sc=0;/* 当前线路站计数器 */ while(1) scanf(“%d“, if(dd=-
46、1)break; if(dd =0 asc=-1; for(k=1;ak =0; k+) /* 处理第 i+1条公交线路 */ for(j=0; j k; j+) g(2)=1; int minLen() int j, k; for(j=0;j n;j+)distj=g0j; dist0=1; do for(k=-1,j=0;j n;j+) /* 找下一个最少上车次数的站 */ if(distj 0 if (k 0 | k=n-1) break; distk=-distk; /* 设置 k站已求得上车次数的标记 */ for(j=1;j n;j+) /* 调整经过 k站能到达的其余各站的上车次
47、数 */ if (3) while(1); j=distn-1; return (5); void main() int t； buildG(); if(t=minLen() 0)printf(“无解 !n“); else pdnff(“从 0号站到 %d站需换车 %d次 n”， n-1， t)； 51 阅读以下说明和 C程序，将应填 入 (n)处的字句写在对应栏内。 【说明】 假设需要将 N个任务分配给 N个工人同时去完成，每个人都能承担这 N个任务，但费用不同。下面的程序用回溯法计算总费用最小的一种工作分配方案，在该方案中，为每个人分配 1个不同的任务。 程序中， N个任务从 0开始依次编号， N个工人也从。开始依次编号，主要的变量说明如下。 . cij：将任务 i分配给工人 j的费用。 . taski：值为 0表示任务 i未分配，值为 j表示任务 i分配给工人 j。 . workerk：值为 0表示工人 k未分配 任务，值为 1表示工人 k已分配任务。 . mincost：最小总费用。 【 C程序】 #include stdio.h #define N 8 /*N 表示任务数和工人数 */ int cNN
