2014年计算机统考真题及解析

2014年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一单选第～0小每题2共0列题出四选项，只有个项符试要求。1．列序的间度是 。count=0;for(k=1;k<=n;k*=2)for(j=1;j<=n;j++)count++;AOog2n) BOn) COnog2n) DOn2)2设初为缀表式a+cdeg转换等的缀达的过中，当扫到f时栈的素依是 。A+(*- B+(-* C．/+(*-* D．/+-*3循队放一组A0M1中end1指队头素nd2指队元素后一个置假队两均可行队出操，队中多容纳1个元。始时为。列断空队满条中的 。A队：en1=nd； 队满end1=en21odMB队：en1=ed2； 队满end2=en11od1)C队：en2=ed1od；队满end1=en21odMD队：en1=ed+od；队满end2=en11od1)4对下二树中序索则点x的线指的点别 。ab cd xeA．、c B．、a C．、c Db、a5．森林F转换对二树，F中叶结的数等 。AT叶点个数 BT度为1结个数CT左子针空结点数 DT右子针空结点数6．5个符如下4码方，缀码是 。A01,000,001,01,1 B．1,00,01,00,1C．00,01,00,01,10 D0,10,0,101007．如所的向行拓排，到拓序列能 。A3,1,24,5,6 B．31,2,,6,5C．31,4,,5,6 D3,1,42,6,58哈（散法理冲（撞时能现堆（集现列选中，会受积象接响是 。A存效率 B散函数 C装填载子 D平查长度9．一具有15关字的4阶B中含字的点数多 。A5 B．6 C．0 D1510．用希尔排序方法对一个数据序列进行排序时，若第1趟排序结果为9,1,4,3,7,820,3,1，趟排采的量间）可是 。A2 B．3 C．4 D51下选中不是快排第2趟序果的 。A2,3,54,6,,9 B．27,5,,4,39C．32,5,,7,69 D4,2,35,7,,912序P在器M上执行是20秒译化后P行指数少到来的70，而PI增到来的12，则P在M的执时是 。A8.4秒 B1.7秒 C．4秒 D16.8秒13．若=13，=25，则下列表达式采用8位定点补码运算实现时，会发生溢出的是 。Ax+y B．x+y C．xy D．xy14oat数据用EEE54精浮格示假两个oat型量x和y分别存在2寄器1和2，若1C9000，2=BC0000则x和y之间的关系。Ax<y且符相同 B．<y且符号同C．>y且符号同 Dx>y且符不同15．容为25MB储器若干8位的DAM片成，该AM芯片的地址脚数引总是 。A19 B．2 C．0 D3616．用令Cace据Cche分的要是 。A降低Cahe缺失 B提高Cace命率C降低PU平访间 D减指流线冲突17计机有16通寄存用32位长令字操码（寻方式）为8，oe令源作数目操数别用寄器接址基寻址式若基址存可用一用寄器且移用码表则oe指中移量取范围是 。A．32768~+3767 B．32767~+3768C．65536~+6535 D．65535~+653618．计机用程控制，有32条令公共取令程包含2条指令指对的程平由4微令成采用定（地字法定条微指令址则指中址字的数少是。A5 B．6C．8D919同总采数线和址复方中地址数线有32根总线钟频率为6H个钟期传两数据上沿下降各送次据该总的大数据输率总带宽是 。A132Bs B．64Bs C．28Bs D1056MBs20一总事务设备需出个地设就从首址始的干连续单读或入个据。种线务式为。A并传输 B串传输 C突传输 D同传输21．列关O口叙述，是 。A状端和制可以用一寄器B．O口中PU可的寄器为OC采独编方时O端口地和存址能相同D采统编方，PU不用存令问O端口22．某备断求响应处时为100n每40ns发一中求，断响应允的长迟间为50n，在设续工过中PU该设的O时间个PU时的分比少。A12.5% B．5% C．7.5% D50%23．列度法，可能致饿象是 。A时片转 B静优数C非占短业先 D抢式作优先24系有n台斥用的类备三并进程别要45设备可确保系锁设数n小 。A9 B．0 C1 D1225．列令，用户执的 。A．ap指令 B跳指令 C压指令 D关断令26．个程读盘作完后操系针该进必的 。A修进状为态 B降进优级C给程配户存间 D增进时片小27．有个为1B的磁分，盘以簇Cuse单进配，的大为4B，采位法管该区空空，即一位b标识簇是被配，则存该图需的数为 。A80 B．20 C．0K D320K28．列施，加虚实址换是 。．增大快表TB)容量 ．让页表驻存 ．增大交区sap)A仅I B仅I C仅、I D仅、29．一文被户程首打的程，作系需的 。A将件容到中B将件制读内中C修文控块的写权限D将件数缓首指返给户程30．页虚存管系统，用些面换算，出现Beady异常现，即进程的缺页次数会随着分配给该进程的页框个数的增加而增加。下列算法中，可能出现Beady异常现的是。．RU算法 ．O算法 ．OPTA仅I B仅、I C仅、I D仅、31．列于道Ppe信的述，是 。A一管可现数据输B管的量受盘量大限制C进对道行操和写作可被塞D一管只有读进或个进对操作32．列项，于级页优的 。A加地变速度 B减缺中次数C减页项占节数 D减页所的内存间33在SI参考型直接会层供务是 。A应层 B表层 C传层 D网层34．某以太网拓扑及交换机当前转发表如下图所示，主机00e1d50023a1向主机00e1d50023c1发送1个数据帧，主机00e1d50023c1收到该帧后，向主机00e1d50023a1发送1个确帧交机这个帧转端分是（ A．3和{1} B．{23和{1} C．{23和{,2} D．1,2,3和{1}35．列素，会响信数传速的 。A信比 B频宽带 C调速率 D信传速度36机与机之用后退N帧议N)输数的送口为100，数据为100节道带为00Mp乙收到个据立利一个帧其传延迟进确认甲乙间单传延是50s则可达最大均据传输率为 。A10Mbps B．0Mbps C．0Mbps D100Mps37．点A、C通过DA享路、C码序列chpngsuence分别是1,,1,1、1,1,1,1)和1,1,1,1。若C链收到序是2,,2,00,2,0,2,0,2,0,2)，则C收到A发的据 。A000 B．01 C10 D138．机和机已立了P连，始以MS1B大的送数，并一直数发；每到一数段会出个接窗为0B的认段若在t时刻生时拥窗为8B，从t时起不再生时情下经过10个T后，的送口。A10B B．2B C．4B D15B39．列于P协叙述，是 。．提供无接务．提供复用用务．通过差校，可靠据输A仅I B仅、I C仅、I D．、、40．用览访某学b站页，使到协是 。APPP BP CP DSMP二、合用：1—7小题共041.13分二树带径长度P)是二叉所有结的权径度之给定一二树T采叉链存，点构：et eght ght其中结点的eht域存该点非权。设oot为指向T根点针，请设求T的PL的，要：1）出法基设想；2）用C或+语给出叉结的据型定；3）据计想采用C或+言述法，键之给注。42.10分网中路器行PF路由议题42表路器1的主链路状信息S，题42是根题2及1口名造来网拓。题42表1所维护的SIR1的SIR2的SIR3的SIR4的SI备注RouterID101..1101..2101..5101..6标识路由器的P地址in1ID101..2101..1101..6101..5所连路由器的RouterIDIP101..1101..2101..5101..6in1的本地P地址Mtric3366in1的费用in2ID101..5101..6101..1101..2所连路由器的RouterIDIP101..9101..3101..0101..4in2的本地P地址Mtric2424in2的费用Nt1Prix19.110/419.160/419.150/419.170/4直连网络Nt1的网络前缀Mtric1111到达直连网络Nt1的费用请回下问。

题42图1构造的网络拓扑1）题的络抽数据构的种辑构？2）对题2中内，设合的式储构，保题42表的路状信息S要求给链储结的据型义并画对题2的存储构意图示图可以D识结点。3）照杰特拉Dksa算法策，次给出R1到达题42图子网92.1.xx的最路及用。439）根题42描述网，续答列问。1）设由结如所示请出题42中R1路表要包达题42图中网92.1x.x的，且由中路项可能。目的络 下一条 接口2主机192..1.10机1921.7.1发一个=64的P组1过哪个接口该P组主机192.1..21到的P组TTL是多？3）若R1加条Mc为10链连接nene，则题42表中R1的SI需要加哪些息？44.12）程中如下环段p：”onti=0;i<N;+)u+;”。假设编时量sum和i别分在器1和R2中。量N寄器R6中，组A的首地在器3序段P始址为804800应汇代和器代如下表所。编号地址机器代码汇编代码注释108410H00200Hlop:sll4,2,2(R2)2R4208414H00800HddR4,R4,3(R4)(R3)308418H8C8000Hlod5,0(4)((R4)0)408410CH00580HddR1,R1,5(R1)(R5)50840H20201HddR,R2(R2)160844H146FHbneR,R6lopi(R2)!(R6)otoop执行述码计机M采用2定指字中分令bne采如格式：1 625 10 1615 0P Rs Rd OSETP为作码Rs和d为寄器号OSET为偏量用码示请回下列问题并明由。1）M的储编单位什么？2）知sl指实左功能组A每个占多位？3）题44中ne令的OSET字的值多？知bne指采相寻址，当前PC容为bne指地址通分题44表指令址和bne令，推出bne指令转目地计公式。4若M采如“发射按完的5指令水：（取值D（译码及取X（行E访W（寄存且件采何转措，分支令执均起3个时周的塞则P中哪指的行由数据关发生流水阻？哪指的执行发控制险为什么令1的行不因为与令5的数相而生塞？45设于44题的算机M和序P的器码M用式拟管理P开始行1=R2R6=100机代已调主但在Cace中组A未调入所有组素在一并存在盘同个请答列问并理由。1P执结时R2内容多？2M指令Cahe据Cche分离若令ahe有16行Cache和存交的块大为2节则据区容是少若考虑段P的行指令Cace的命中为少？3P执过中哪指令执可发溢异常哪指的行能产缺页异？于组A问，要磁和TB至少各少？46.件F由200记组录从1始户开件欲内存的一条记插到件F中作为第0记。答下问，说理。1）文系采连配方每磁块一条，件F存储域前均有足的闲盘则完上插操最需要问少磁块F的文件控制块内容发哪改？2）若件系采用接配方式每磁盘存一条记和个链指，则成上述入作要问少次盘？每存块大为1B其中4字节放指针则文系支的文最长是少？47.统有个产进程多消者程共享个存放1000产品环形缓冲（始空当冲区满产进可以入生的件品则待；当缓区空费进程以缓区走件产否等一个费进程从缓区续出0品他费进可以产请用量PVa，sgna操作实现进程间的互斥与同步，要求写出整的过程，并说明所用号量的含义和初值。2014年计算机学科专业基础综合试题参考答案一、项择题（一单题1．C2．B3．A4．D5．C6．D7．D8．D9．D1．B1．C1．D1．C1．A1．A1．D．A1．C1．C0．C2．D2．B2．A2．B5．D6．A．A2．C2．B3．A3．C3．D3．C3．B3．D3．C．B3．A3．B4．D（二单题案析1．层环件=n外层环变无，次环j自增1每内循环执行n次外循条为k=n增定为k=2，可知环数为2=n即k=og2。所以层环时复度是On外循的间复是Oogn嵌套环根据乘规可，段序的间度T(n=T1)T2n=OnOog2n=Oog2n。2．中表式换缀表式算思如：从左右始描缀达式；遇到字，入缀达式；遇到算时：a.为(，入栈；b.为)则依次把的的算加后表式到现(从栈删除('；c.为括号的他算符，当优级于除(以外的顶算时接入。否则栈开次出比前理运符先级和先相的算符直一个比它先低或遇了一左号止。当扫的缀达结时，中所运符次出加后表式。待处理序列栈后缀表达式当前扫描元素动作/b(cd-ef)/gaa加入后缀表达式/b(cd-ef)/ga//入栈b(cd-ef)/g/abb加入后缀表达式(cd-ef)/g/+优先级低于栈顶的/，弹出/(cd-ef)/gb/+入栈(cd-ef)/g+b/((入栈cd-ef)/gb/cc加入后缀表达式d-ef)/gb/c*栈顶为(，入栈d-e)/g(*b/cdd加入后缀表达式-ef)/g(*b/cd--优先级低于栈顶的，弹出*-ef)/gb/cd*-栈顶为(，-入栈ef)/g(-b/cd*ee加入后缀表达式f)/g(-b/cde*优先级高于栈顶的-，入栈)/g(-*b/cdeff加入后缀表达式)/g(-*b/cdef)把栈中(之前的符号加入表达式/g+b/cdef-//优先级高于栈顶的，/入栈gb/cdef-gg加入后缀表达式b/cdef-g扫描完毕运算符依次退栈加入表达式b/cdef-/+完成由此知当到f时候栈的素次，选B。在此再出缀达转换前或缀达的一手做上给出中缀表达为：第一：照算的先级所的算位括号。式子成：ab+cd)e)g)第二：换前或缀表式。前缀把算号动对应括前，变了+ab(cd)eg)把括去+ab-cdefg前式出。后缀把算号动对应括后，变了：abcdef))g)+把括去：abcdefg+后式出。当题要直求缀后缀达时这方会比一快得。3．end1指队元那么知队操是从Aen1数然后en1再加1。end2向尾素后个位，么知队作是存到And2，后end2再加1。把A0存一元素当列始，队操是把据到A0]，后en2自增即知ed2初为0而nd1指的队元素队元的组A的标为0以知en1值为0可队条为en1=end后虑列时为列最多纳1元假设列储下为0到下为2的1区域队为A0队为AM2，时队满考在种况下ed1和ed2状，end1指队头元，知nd=0ed2向尾素后位置知en2=M2+M1，所以可知队的为end=ed2+1odM选A。注意考这具问时一特情判往往直思问能快的到答案，可画简的图以便题。4．线二叉的线实上指向是应遍序特定结的驱结和继结，所以写二树中遍历edxac中历在x边右的符就它在中序索的、线，即、，选D。5．将林转为二树相当于孩兄弟示表示森。变化程，原林某结的一孩结作为的子的弟作它右树那森林的结点由于有子点那转化二树，结就没左点以F中叶结的数就于T中孩指空的点数选C。此题可通一特来除BD项。6．前编码定义在个字符中任何个符的编都是另个符编的前缀D中码10是码00前，反缀编的则以D是前编。7．照扑序算每次选入为0点从中去此中开始有结点3入度为0删掉3结点，有点1入度为；掉点1，只结点4的入度为；删掉4结，结点2结点6入都为0此选删同的点会得出不的扑列分处理毕可可的扑序为1425和3145，选。8生积现产了冲对储率散列数装因均会有响，而平查长会为积现而大选D。9．关字数不变要结点数最，那即个结点含键字数最少根据4阶B的义根点最含1关字根结中少421=1个关字所以每结中关字量最为1，每结点有2个支类与排二，而15个点好以一个4的4阶B得叶结全第合B树义，因选。10首第个素为整序中最素所可该尔为从到大排然考增题若量为第+2个素4显第1个素9A排除若为第6元都有序=1,2,3合尔序定增量为第1个素9第+4元素7C排增为第1元素9第15个素8大D排选。1快的段排果的点第i完时，有i个上数现在最终将要现位它的数比小它边都比大题问二序的果，即要不在2这数的项A项中2、、6、9符合以A排B选项中2、9均合所以B排；D选中5、9符合所以D项除最后看C选项，有9一数合所以C可是速第二的果。12不设来令为么原PI就为0x过译化条数少到原的0即令数为07而PI增原的1.2即4x么在P在M上的行间为令数CP=0.7x24x=240.7=16.8选。13．8位点码示数据围为12~12，运算果出个围会溢A选项+=10325=7，合范A除B选项x+=10325=128，符围B除；D项x=103+25=78符合围D排除C项x=103+5=28超了12选C。该题可照进写两个进运观运的进信得结不这种法更为烦耗，实考试并推。14．1)和)对应的二进制分别是1010100…2和110010……2，根据EEE74点数准知1的为1阶为10000，数为1.01而2)的符为1为010001尾为1.1则知数为负号同BD排除1的绝对为1.0226，2的绝值为1.230，则1)的对比2的对大，符为负，值小反即1的真比2真小即<，选A。此题有为便算，1与2前4位为00与0,以出均为数，而阶用码示两的阶头位为100和01可知1阶于2)的码，又因是EE754规的数尾部均为1.x则码的值对值然，可知1值绝值2真值绝值因为负，则1<2即<。15．48的片线应为8，址应为og24M22根而AM采用址复用术地线原的，地信分列两传。址数为2221所以址脚数引的总为1819选A。此题要意是DAM是采传次址策的，以址为常一半这是很考容忽的方。16令Cahe据Cache分后取和分别不的Cace找么指令水中指分取数分可很的免冲，减了令水线冲。17．用32位长令，其操码为8位个地码共用328=4位而oe指令源作和的操数别用存直接址基寻器中有6个通用存则址寄存要og21=4位源操数的存直寻址掉4位，而目的作采用址址也要定个寄器同样掉4，留给移址的数为2444=16，偏址补码示16位码示范为3276~3277选。18．算共有32指，各指对的程平均为4，指对的微令为324=128条而共指令有2条整系中微令条一为8+=10所以要g2138能寻到30微令答选。19．据有32根就一次以送32b8=B的数，6Mz意有66M个时钟周期，而每个时钟周期传送两次数据，可知总线每秒传送的最大数据量为662=52M，总线最数传为528Bs，选C。20猝发突发输在个总周以多个储址续数一次传输个址一地连续数并传是传输有个据同在设之进行的行输指据的进代在条理信上位单按间顺逐输的式同传是传输程统的钟制选。21用一址U存问O端口的是样指以存指可以访问O口D项误，他个项为确陈选。22每40ns发一断请，响和理间为100n，中许迟为扰信息因为在50ns，论怎延，每40ns是要花费100ns理的，以设备的O间整个PU时间百为10ns40ns=25选。23采静优先调时当统是出优级高任优级的任总是得到理而生饿现短业先度不是占或非占的当统总是出新的任时长任会是不处机产饥现，此BCD都错误选。24三并进分要5台统只有31+41+51=9台设时，第一进配2二个程配3台第个进配4种况下三进程均无继执下，生死。系中增加1台备也是共10台设时这最后1台备配任一个程可顺执完此证统发死锁最设备为1。25ap指令跳指压栈令可在户执行中ap令由用态转换为核。关断指为权令必在核态能行选。26进申读盘的时因要待O操作把身时程就变了塞当O作成进得了想的会塞态换就绪态（是操系统行为。而低进优先、配用内存间和加程的间片大小都一会生选。27簇总为1B4B=2.5用位识簇否被整磁共要2.5M位，要2.5M=30B，则要320B4B=0个，选。28实址换指辑地和理址转增快容能更的表装入快表加虚地转换平速页常驻存以去些在内中页表从磁上入过能加虚地变大交区虚地变速度影因此、I正确，选C。29一文被户首次开被了pen操，把件的CB入内，而不把件容到存中只进希获文件容时才读文件容、D显误选B。30．有O算法致Bedy异常，选A。31管实上是种定大的冲道于管两的程言就是文件它是通文件它不于种件统而是立户单构一种件统，并且存于存类似通中双信的进通机个道可实双向的数传而同个刻只最有个向传能个方同进道容量大通为存的页它大并不受盘容大的制当道满进写管会阻，当道空，程管会阻塞因选C。32多页不仅会快地的换度还为增更的表程会使变换速减；不减缺页断次，而果访过中级页都不内，会大增缺的数也并会少表所的字数细析考段多页表能减页所的续内空即当表大页再分以把张表控制在页内减页所占连内空，此选D。补充页管中个表项大的限何定？页表的用找该在内的置以32位辑地空，节编单位一页4B为例地空一共有23B4B=1M则要og21=20位能保表范围能纳有为以节为址即页项大小⌈0⌉=以这个条件，了证表能够向有面那页表的小该于，当，可以选更的表大以至让个面够好容整个表以便存例取成4，么页好装下1K个表，增加些他息。33．接会层供务的会层下层是传层选C。34．机00e1d50023a1向00e1d50023c1发送数帧，换转表中有00e1d50023c1这项所以除1接外所接口播即23口会发帧，同时因为转发表中并没有0e1d50023a1这项，所以转发表会把(目的地址00e1d50023a1端口1这项入发而当00e1d50023c1向00e1d50023a1发送确帧于发经有0e1d50023a1这项以换只向1转发选。35由农理可噪比频带都以制信的限输率所以噪比和频带对道数传输率有响的AB误道传速实际就信号的送率而制度也直限数的输速C错误信的播速是号在信上播速，信道发速无选D。36．虑约的据输速的素首，道带能接约据传输，传输率定小等信道宽；次主甲乙间用退N帧议，么为甲乙机间用退N帧协传数，考发送个据接到的确之，最多发多数的最传速受两条件约以的大传速是这两个值小那一。的发送口尺为100，即收第个数的认之前最多能送100数帧就是送0001000=1B内从送个帧接到它的认时是个返时，是5+5=10s=0.1s，在10s中，最能输1MB的据此时最大输为1B0.1=10Bs=0Mbp道宽为00bp，所以为n{80bps,00Mbp=80bps选C。37把到序分每4个字为2,0,00,2,0,20,2,,2因为目求是A送数此把三数与A码片列1,,1,1做积算结分别是2,0,201,11,14,2,0,21,1,1,14=10,,0,21,11,14以C接收的A发送数是01选B。38当t刻生时，把heh为8半，为4且塞设为1B。然后历10个T拥塞口大依为、4、、、78、、1、、1，发送窗取时拥窗和接窗的小接收口为10B以此的送窗为10B选。实际该接窗一为10B可不何，发窗一小于10B，选项中有A选满足，可接选。39P供是连的服，I正确；时P也供复用分服，I正确；P然差校机但是P差校只检查据传的程有没出，出错数直丢，没有传机，能证可传，用UP议时可传输必由用实，I错误答选B。40接网时能会到PPP议A能到而当算不道主的AC地址用P址询应的C址会到AP议B可用而当问eb网站若NS缓没存储应的P址用域查相的P地时要用NS协议而S基于P协议的以C可用到SMP有用邮客端发邮，或是件务向的件服器送件才用纯访问eb页不能。二、合用题4．答：考查叉的权径度二树带路长为每叶结的度权值积的总，以用序历或次历决题。1）法基设思：①基先递遍的法思是一个sac变量记录p把个的深作为递归数一参传，算步如：若该点叶结，么量pl加该点深度权之；若该点叶结若左树为左调用归法若子为空，对右树用归法深度数为结的度参加；最后回算的pl可。②基层遍的法想是用列行次历，记当的数，当遍到子点，计p；当遍到叶结时该结的该点子加入列；当某点该的后个结时层增1；队列时历束回pl2二树点数类定义下：tpdefstrutBiNod{intiht;strutBiNodelchild,rhild;}BiNod,Bir;3算代如：①基先遍的法：intP(Bireroot){rturnplPrOdr(roo,0;}intplPrOrdr(Bireroot,intdp){stticintpl=0; //定义一个sttic变量存储pli(root-lchild=NLL&root-lchild=N) //若为叶子结点，累积plpl=dproot-iht;i(root-lchild=NU) //若左子树不空，对左子树递归遍历pl_PrOrdr(oot-lcild,d1);i(root-rhild=NL) //若右子树不空，对右子树递归遍历pl_PrOrdr(oot-rhld,d1);rturnpl;}②基层遍的法：#dineMSize100 //设置队列的最大容量intpl_lOrdr(Bireroot){Bireeq[MSiz]; //声明队列，n1为头指针，n2为尾指针intd,n2; //队列最多容纳MSize-1个素nd1=n2=0; //头指针指向队头元素，尾指针指向队尾的后一个元素intpl=,dp=0; //初始化pl和深度BireelatNod; //latNode用来记录当前层的后一个结点BireenlastNod; //nlatNode用来记录下一层的最后一个结点latNode=rot; //latNode初始化为根节点nlatNode=NU; //nlatNode初始化为空[n2]=ot; //根节点入队hil(nd1=nd2){ //层次遍历，若队列不空则循环Bireet=[n1]; //拿出队列中的头一个元素i(t-lchild=NLL&t-lchild=NU){pl=dpt->iht;} //若为叶子结点，统计pli(t-lchild=NU){ //若非叶子结点把左结点入队[n2]=t-lchil;nlatNode=t-lchild;} //并设下一层的最后一个结点为该结点的左结点i(t-rhild=NUL){//处理叶节点[n2]=t-rhild;nlatNode=t-rhild;}i(t=latNod){ //若该结点为本层最后一个结点，更新latNodelatNode=nlatNod;dp=1; //层数加1}}rturnpl; //返回pl}【评说】①若生出够足目要的他法且确，同给。②考答无用C者+言只正确样给。③若算的本计想和要据构述十分在法现能够晰反映算思且确参照的准分。④若生出二树点的据型义算实现使的除型外的他数值可同用型型。⑤若生出答中法主设思或法部分确可情分。注述个算一为递的序历一为非归层遍者应取自己擅的写式直观去先遍代行数用用他具写更容易，望者掌。在先遍的法，sac是一静变，首次用数声明pl并赋为0，后递调并使得pl为0具用请参相资的sac关键说，也可在数外先置一全变初化过虑历真算法案常都直接仅一函构以考案用sac对sac不悉同可以用下形式递：intplPrOrdr(Bireroot,intdp){intlpl,rpl; //用于存储左子树和右子树的产生的pllpl=rpl=0;i(root-lchild=NLL&root-lchild=N) //若为叶子结点计算当前叶子结点的plrturndproot-iht;i(root-lchild=NU) //若左子树不空，对左子树递归遍历lpl=pl_PrOrdr(rot-lchl,dp1);i(root-rhild=NL) //若右子树不空，对右子树递归遍历rpl=pl_PrOrdr(rot-rhid,dp1);rturnlpl+rpl;}C+语基好同可以用简的下式：intplPrOrdr(Bireroot,intdp){i(root-lchild=NLL&root-lchild=N) //若为叶子结点，累积plrturndproot-iht;rturn(oot-lcild=NULL?wplPrOdr(root-lhil,dp):0)+(root-rhid=NLL?pl_PrOrdr(root-rhid,dp1):);}这个式是面法简化质是样这形代码在时有限的情下具势能写层遍的生约多时以者当保证码确的情况量一较的算其题赢更多时是对基础扎的考生是议用对握更的法否可会得偿如上的代中考生容易记元式?z两端的号若加号则答就是误。在层遍的法者要解aode和nesNode的别aNode指的当前遍层最一结，而eaNode指下一的后个点是动变的，直到历本的后个结能认层正的后个点哪结点而数中入队作没判队考时到读好加队条里列的满件为end==ed+1的是014年题择第三的列生可以尝试用录层第个结来行次历算法这不给代码请考自练习。4．答：考察给具模时数据构应。题多考乍之以是络的，其实本并有及多的络识是用了络模际考察还数据结构内。1图1分)题中出是个单网络扑，以象无向。【评说】只要生答中出图含相的述例“网结非性构同样给。2链式储构如所示Flag=1NextIDIPFlag=1NextIDIPMetricFlag=2NextPrefixMaskMetric其数类定如：3分)tpdefstrut{

表头结点结构示意

RouterIDLN_linkNextunsindintID,P;}inNod; //ink的结构tpdefstrut{unsindintPri,Ms;}NtNod; //Nt的结构tpdefstrutNod{intla; //Fla1为in;Fla2为Ntunon{inNodenod;NtNodeNnde}inORt;unsindintMtri;strutNodent;}rcNod; //弧结点tpdefstrutHod{unsindintoterI;rcNodeN_lin;trutHodenet;}HOE; //表头结点对题42表链存构示图下。2分)Flag=110.1.1.510.1.1.92Flag=2Flag=110.1.1.510.1.1.92Flag=2192.1.1.0255.255.255.01Flag=110.1.1.210.1.1.13Flag=110.1.1.610.1.1.134Flag=2Flag=110.1.1.610.1.1.134Flag=2192.1.6.0255.255.255.01Flag=110.1.1.110.1.1.23Flag=110.1.1.110.1.1.102Flag=2Flag=110.1.1.110.1.1.102Flag=2192.1.5.0255.255.255.01Flag=110.1.1.610.1.1.56Flag=110.1.1.210.1.1.144Flag=2Flag=110.1.1.210.1.1.144Flag=2192.1.7.0255.255.255.01Flag=110.1.1.510.1.1.66【评说】①若考生给出的答案是将链表中的表头结点保存在一个一维数组中(即采用邻接表形式，样分。②若生出答中弧结没用unon义是用种同结构别表示nk和Ne同在头结中义两指，分指由两类的结构的两个表同给。③考所答的结中，以单定的中保各连络P地的前长度，可与络址存在一域。④数类定要用了行链存结并保了目所的SI信息，例如网抽为类点，出含8表结的链存结，可照~的准给分。⑤若生出答中图示分与数类定义分致图只能够现链式存结题42图网络接系可不出结内节息，给分。⑥若答完正，情给。3计算果下所。4分)目的网络路径代价（费用）步骤119.110/4直接到达1步骤219.150/4R1R39.150/43步骤319.160/4R1R29.160/44步骤419.170/4R1R2R4121..0248【评说】①若生出各最路径结部正，酌情分。②若生出从R1到子网92.1x.x的短及代正不全代价不减的序可情分。4．答：1)因为题目要求路由表中的的路由项尽可能少，所以这里可以把子网1921.6.024和192.1..024聚为网12.1.6.03其网络，可到由如：6分)目的网络下一条接口19.110/4-E019.160/3101..219.150/4101..0【评说】①每确答个由，给2分共6分。②路项答完正，或由于3，酌情分。2通过路表知R1通过0接口转发该P组。1分为分要过3个路由器1R、R4，主机92.17.21到的P分的TL是643=61。1分)3R1的SI需要增一特殊直网络缀Pex”0.00.00”,ec为10。1分)【评说】考生要答增缀Pex为”00.0.00，Mc为1，样分。4．答：该题计机成理目的合型涉到令系、储理及PU三部分内，生注各节内之的系才更好把当考的势。1已知机M用2位定指一指占4观表各令地址知，每条令地为4地址位即4个址位表4，个址就代了B，所以计机按节址的。2分)2在二制某左位相于乘该件可组的据隔为4个地址单，计机字编址所组A中元占4。2分)3由表知bne指机器码为1446AH根据目出指格，后B的内为OSET段以该的OSET为AH用补表示值为61分)当系统执行到ne指令时，PC自动加4，PC的内容就为084818H，而跳转的目标是080480H两相差了8，即24单的间隔所偏址一即是实转地址的246=4位。1分可知bne指的移地址算式为PC++SET4。分)4由于据关发塞的令第6条因第46指令与各自一指发数相关。3分)第6指会生制险。1分)当前环第条令下次环第条令然有据关但于第6条令后有3时周的塞因而除该据关。1分)【评说】对于第1问若生：因指令1和2、2和、3和4、5和6生相关因而发阻的令为第、3、、6