- 搜标题
- 搜题干
- 搜选项
问答题
试设计一个算法，判断一个有向无环图G中是否存在这样的顶点，该顶点到其他任意顶点都有一条有向路径。有向图G以邻接表的形式存储。根据设计思想，采用C、C++语言描述算法，关键之处给出注释。
答案：
正确答案：算法实现如下： 方法一：广度优先遍历（使用队列） int rbfs (ADJLIST g，int vi) in...
你可能感兴趣的试题
问答题
有一结点的关键字序列F= {129，72，180，105，147，96，45，69}，散列函数为：H (k) =k mod 11，其中k为关键字，散列地址空间为0～10。要求：画出相应的散列表。当发生冲突时，以线性探测法解决。该散列表的装填因子是多少？计算在等概率情况下，查找成功和查找不成功时的平均查找长度ASL。
答案：
{{*HTML*}}正确答案：采用线性探测法处理冲突建立的散列表如下： H(129)=129 mod 11=8 H(72...
问答题
试设计一个算法，判断一个有向无环图G中是否存在这样的顶点，该顶点到其他任意顶点都有一条有向路径。有向图G以邻接表的形式存储。给出算法的基本设计思想以及结点和邻接表的定义。
答案：
正确答案：基本设计思想：若存在这样的顶点，该顶点到其他任一结点都有一条有向路，又因为该有向图是无环路的，那么该顶点到这些...
问答题
有一结点的关键字序列F= {129，72，180，105，147，96，45，69}，散列函数为：H (k) =k mod 11，其中k为关键字，散列地址空间为0～10。要求：画出相应的散列表。当发生冲突时，以链地址法解决。计算在等概率情况下，查找成功和查找不成功时的平均查找长度ASL（只将与关键字的比较次数计算在内即可）。
答案：
{{*HTML*}}正确答案：采用链地址法处理冲突建立的散列表如下：
ASLsucc=(...
ASLsucc=(...
问答题
有以下两段C语言程序代码：int funl(unsigned short si) int fun2 (unsigned short si}return . (s1*256) ； return (( (short) s1*256) /256) ；请回答下列问题：假设计算机硬件不提供直接乘除运算功能，如何实现上述函数的功能？函数funl和fun2得到的结果各有什么特征？
答案：
正确答案：因为256=28，所以上述函数中的乘、除运算可以分别用左、右移运算来实现。可用“左移8位”代替“乘256”的操...
问答题
试设计一个算法，判断一个有向无环图G中是否存在这样的顶点，该顶点到其他任意顶点都有一条有向路径。有向图G以邻接表的形式存储。根据设计思想，采用C、C++语言描述算法，关键之处给出注释。
答案：
正确答案：算法实现如下： 方法一：广度优先遍历（使用队列） int rbfs (ADJLIST g，int vi) in...
问答题
某系统有R1、R2和R3共三种资源，在T0时刻，P1、P2、P3和P4这四个一组合作进程，执行顺序如图4—4所示。请用PV操作实现进程中的同步操作。
某系统有R1、R2和R3共三种资源，在T0时刻，P1、P2、P3和P4这四个一组合作进程，执行顺序如图4—4所示。请用PV操作实现进程中的同步操作。
答案：
正确答案：图中示出了上述并发进程之间的前驱关系，为了使上述进程同步，可设置8个信号量A，B，C，D，E，F，G，H，他们...
问答题
某操作系统的文件管理采用直接索引和多级索引混合方式，文件索引表共有10项，其中前8项是直接索引项，第9项是一次间接索引项，第10项是二次间接索引项，假定物理块的大小是2KB，每个索引项占用4个字节，试问：该文件系统中最大的文件可以达到多大？
答案：
正确答案：物理块大小为2KB，每个索引项占4B，所以一块物理块可容纳2KB/4B=512个索引项。由此可知，一次间接索引...
问答题
以下是计算两个向量点积的程序段：float dotproduct (float x L83 f float y [8] )float sum=0.0；int i；for (i=0；i＜8；1++)sum+=x [i] *y [i) ；return sum；}试回答以下问题：访问数组x和y时的时间局部性和空间局部性各如何？能否推断出命中率的高低？
答案：
正确答案：数组x和y都按存放顺序访问，不考虑映射的情况下，空间局部性都较好，但都只被访问一次，所以没有时间局部性。命中率...
问答题
有以下两段C语言程序代码：int funl(unsigned short si) int fun2 (unsigned short si}return . (s1*256) ； return (( (short) s1*256) /256) ；请回答下列问题：表中的哪些数据异常？并分析“异常”产生的原因。
答案：
正确答案：表4—6中，加粗的数据是一些异常的结果，即当si=128时，fun2返回的结果异常，当si=256时，funl...
问答题
试设计一个算法，判断一个有向无环图G中是否存在这样的顶点，该顶点到其他任意顶点都有一条有向路径。有向图G以邻接表的形式存储。说明你所设计算法的时间复杂度。
答案：
正确答案：时间复杂度分析：无论是采用深度优先遍历还是广度优先遍历，可知每个结点均访问了一次，因此时间复杂度为O(n)。
问答题
某操作系统的文件管理采用直接索引和多级索引混合方式，文件索引表共有10项，其中前8项是直接索引项，第9项是一次间接索引项，第10项是二次间接索引项，假定物理块的大小是2KB，每个索引项占用4个字节，试问：假定一个文件的实际大小是128MB，该文件实际占用磁盘空间多大（包括间接索引块，不计索引表所占空间）?
答案：
正确答案：文件的实际大小为128MB，即128MB/2KB=64K个物理块。8个直接索引项可以表示8个物理块，一个间接索...
问答题
以下是计算两个向量点积的程序段：float dotproduct (float x L83 f float y [8] )float sum=0.0；int i；for (i=0；i＜8；1++)sum+=x [i] *y [i) ；return sum；}试回答以下问题：假定该段程序运行的计算机的数据Cache采用直接映射方式，其容量为32B，每个主存块大小为16B。假定编译程序将变量sum和i分配给寄存器，数组x存放在00000040H开始的32B的连续存储区中，数组y则紧跟在x后进行存放。试计算该程序数据访问的命中率，要求说明每次访问的Cache命中情况。
答案：
正确答案：Cache共有32B/16B=2行；4个数组元素占一个主存块（float占4个字节）；数组x的8个元素（共32...
问答题
以下是计算两个向量点积的程序段：float dotproduct (float x L83 f float y [8] )float sum=0.0；int i；for (i=0；i＜8；1++)sum+=x [i] *y [i) ；return sum；}试回答以下问题：将上述(2)中的数据Cache改用2—路组相联映射方式，块大小改为8B，其他条件不变，则该程序数据访问的命中率是多少?
答案：
正确答案：若Cache改用2一路组相联，块大小改为8B，则Cache共有4行，每组两行，共两组。两个数组元素占一个主存块...
问答题
以下是计算两个向量点积的程序段：float dotproduct (float x L83 f float y [8] )float sum=0.0；int i；for (i=0；i＜8；1++)sum+=x [i] *y [i) ；return sum；}试回答以下问题：在上述(2)中条件不变的情况下，如果将数组x定义为float[12]，则数据访问的命中率又是多少？
答案：
正确答案：若(2)中条件不变，数组x定义了12个元素，则12个元素共有48B，使得y从主存第7块开始存放，即x[0]～x...
问答题
假定站点A和B在同一个10Mbit/s以太网的网段上，这两个站点之间的传播时延为225比特时间。现假定A开始发送一帧，并且在A发送结束之前B也发送一帧。如果A发送的是以太网所允许的最短的帧，试问：A在检测到和B发生碰撞之前能否把自己的数据发送完毕？如果A在发送完毕之前并没有检测到碰撞，那么能否肯定A所发送的帧不会和B发送的帧发生碰撞？（提示：在计算时应当考虑到每一个以太网帧在发送到信道上时，在MAC帧前面还要增加7个字节的前同步码和1个字节的帧定界符）
答案：
正确答案：设在t=0时，A开始发送数据，那么在t=(64+8)×8=576比特时间的时候，A应当发送完毕。另外，由题意可...
问答题
假定站点A和B在同一个10Mbit/s以太网的网段上，这两个站点之间的传播时延为225比特时间。现假定A开始发送一帧，并且在A发送结束之前B也发送一帧。如果A发送的是以太网所允许的最短的帧，试问：在(1)中的站点A和B在t=0时同时发送了数据帧。当t=225比特时间，A和B同时检测到发生了碰撞，并且在t=225+48=273比特时间完成了干扰信号的发送。A和B在CSMA/CD算法中选择不同的r值退避。假定A和B选择的随机数分别是0和1。试问：A和B各在什么时间开始重传其数据帧？A重传的数据帧在什么时间到达B?A重传的数据会不会和B重传的数据再次发送碰撞？B会不会在预定的重传时间停止发送数据？
答案：
正确答案：t=0时，A和B开始发送数据。 t=225比特时间，A和B都检测到碰撞。 t=273比特时间，A和B结束干扰信...
