99-16年初试真题及答案2013

1、2013 年数据结构部分1、（1）#define MaxVertexNum 100;#defineVertexType;#define char EdgeType; Typedef structVertexType vexMaxVertexNum;EdgeType edgeMaxVertexNum MaxVertexNum;um;MGraph;（2）算法：设有两个顶点集合 S 和T，S 中存放图中已找到最短路径的顶点， T 存放图中剩余顶点。初始时，S 中只包含 Vo，然后不断从 T 中选取到 Vo 路径长度最短的顶点 Vu 并入到 S 中，S 每并入一个新的顶点，Vu 都要修改顶点 Vo到

2、T 中顶点的最短路径长度值。不断重复此过程，直到 T 中顶点全部并入到 S中为止。时间复杂度是（O2）。2、(1) 2、由 =n/N 得 N=n/，由于 N 是整数，即 N=15，从而 P=13因此散列函数为 H(key)=key/13，构造的散列表为：（2）关键字 68 的查找过程：先求散列地址 H(68)%13=3,L3不空且 L3!=68,则找下一地址 H1=(68+1)%13=4,L4不空且 L4=68,查找成功，返回的序号 4.3、算法：采用递归算法，若树为空，结点个数为 0，否则结点个数为第一在表中树结点数和兄树结点数之和再加 1.0123456789101112131426254

3、11251count(CSTree bt) n1,n2;if(bt=NULL) return 0;else/递归求以孩子兄弟链表表示的树的结点数n1=count(bt-child);/第一树结点个数n2=count(bt-nextsibling);/兄树结点个数return n1+n2+1;/总结点个数4、算法：递归主体：f(L,item)=f(L-next,item); 其他情况终止条件：f(L,item)=不做任何事；L 为空表或者只有一个结点f(L,item)=删除*L 结点；L-data=item void Del(LinkList &L,Elemtype item)LNode *p;

4、 if(L=NULL)return ;/p 指向待删除结点if(L-data=item) p=L;L=L-next; free(p);Del(L,item);/删除值为item 的结点elseDel(L-next,item);5.算法：首先递归求出其各位数字的值，然后对值求和，得到一个新的数。然后对新数进行处理，判断其是否为 0，如若不是对其进行继续处理，得到一个新的数，继续下去，直至 sum 为 0，跳出递归。统计所得到的新值得数目，返回。void fun(n,char *s,sum)/递归求整数的各位数字，并求其和if(n=0)*s=0;return;elsefun(n/10,s+1);*

5、s=n%10;sum+;dis(n)/判断并统计新得到的数字的数目fun(n);count=1;if(sum!=0)count+;elsefun(sum);return count;操作系统部分6（1）寻道时间：活动头磁盘在读写信息前，将磁头移动到特定磁道所需要的时间。（2）动态装入：装入程序在把装入模块装入内存后，并不立即把装入模块的相对地址换为绝对地址，而是把这种地址转换推程序要真正执行时才进行。因此装入内存后的全部地址均为相对地址，这种方式需要一个重定位寄存器的支持。（3）用户态线程：在用户态线程中，有关线程管理的所有工作都由应用程序完成，内核意识不到线程的存在。（4）内碎片：已经分配给

6、某进程，却不能被利用的内存空间。（5）临界区：7.临界资源的那段代码，又称为临界段。（1）正确，死锁是由若干多个进程竞争系统资源而造成的一种僵局，进程数必须大于 1 个且不应超过系统中的最大进程数。（2）错误，当TLB 未能命中时，需两次内存。错误，编程空间的大小取决于硬件的访存能力，一般由地址总线宽度决定。正确，系统中文件很多时，文件目录可能要占用大量的盘块，所以文件目录通常放在磁盘上。（5）错误，当进程等待的时间到来时，进程从等待到就绪，并不影响处理机对当前进程的执行过程。8.在分配的过程中，该系统显然在分页方面花费了大量的时间，频繁的进行页面换入换出。不能，CPU 速度提高不能降低进程的

7、缺页率。能，把撤销进程的页面分配给系统中的其他进程，使其他进程的页面数增多，缺页率下降。（3）能，分给系统内进程的页面数增多，缺页中断次数减少，磁盘 I/O 频率降低。不能，磁盘是外存，增加磁盘容量也不能降低进程的缺页率。能，页面换入换出速度加快，缩短磁盘I/O 时间，提高系统利用率9.（1）TLB 命中时，只需一次内存平均时间t=100+10=110ns（2）TLB 未能命中时，需两次内存平均时间t=100*2+10=210ns（3）平均10时间t=98%*(100+10)+(1-98%)*(100*2+10)+200=312ns目录是一种数据结构，用于标识系统中的文件及其物理地址，供检索时使