2022年南京农业大学信息科学技术学院853计算机专业基础综合之数(3)

void leafchain（BiTree Abt）

{p={BiTree）malloc（sizeof（BiTNode））; If（!p）{print£（“OVERFLOW\n”;exit（1）;}

head=p; top=0;

if（bt）

{top++; stack[top]=bt; while（top）

{t=stack[top];top--;

if（it->Lchild && !t->Rchild）{ （1） ; （2） ; （3） ;} else {if（ （4） ）{top++; stack[top]= （5） ; } if（ （6） ）{top++; stack[top]= （5） ; } } }

（8） ; （9） ; } } 【答案】

p->Rchild=t:t->Lchild=p:p=t: p->Rchild=head:head->Lchild=p

5．

设单链表的结点结构为

t->Rchild!=null:t->Rchild:

t->Lchild!=null:

t->Lchild:

为指针域，已知指针px指向单链表中data为x的结

_____；点，指针py指向data为y的新结点，若将结点y插入结点x之后，贝懦要执行以下语句：

_____;

【答案】

6． 求最短路径的Dijkstra算法的时间复杂度为_____。

【答案】

7． 设T和P是两个给定的串，在T中寻找等于P的子串的过程称为_____，又称P为_____。

【答案】模式匹配；模式串

8． 实现字符串拷贝的函数strcpy为：

【答案】

9． 应用prim算法求解连通网络的最小生成树问题。

（1）针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。

〔始顶点号，终顶点号，权值）

（2）下面是Prim算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。

的值在〈limits h>中

//图的顶点数，应由用户定义

//用二维数组作为邻接矩阵表示

//生成树的边结点

//边的起点与终点

//边上的权值

//最小生成树定义

//从顶点rt出发构造图G的最小生成树T，rt成为树的根结点

//初始化最小生成树

T

//依次求MST的候选边

//遍历当前候选边集合

//选具有最小权值的候选边

//图不连通，出错处理

//修改候选边集合

【答案】（1）（0，3，1）; （3，5, 4）; （5，2，2）; （3，1, 5）; （1，4，3） （2）①T[k]; tovex=i②min=Maxint③mispos=i④exit（O）⑤T[i]; fromvex=v

【解析】Prim算法的执行类似于寻找图的最短路径的Dijkstra算法。假设N={V，E}是连通图

，是N

上最小生成树边的集合。算法从属于

为止。

ET开始，重复执行下述操作：在所有u属于

加入集合

同时将

并入

v

直到

的边（u，v）属于E

中找一条代价最小的边

10．索引顺序文件既可以顺序存取，也可以_____存取。

【答案】随机

二、选择题

11．计算机算法指的是解决问题的步骤序列，它必须具备（ ）三个特性。

A.可执行性、可移植性、可扩充性 B.可执行性、确定性、有穷性 C.确定性、有穷性、稳定性 D.易读性、稳定性、安全性 【答案】B

【解析】计算机算法是以一步接一步的方式来详细描述计算机如何将输入转化为所要求的输出的过程，或者说，算法是对计算机上执行的计算过程的具体描述，也就是解决问题的步骤序列。一个算法通常需要具备五大特性：有穷性；确定性；可执行性；输入一个算法有零个或多个输入；输出一个算法有零个或者多个输出。

12．下列选项中，导致创建新进程的操作是（ ）。

用户登录成功

设备分配

启动程序执行 A.仅和B.仅和C.仅和D.

和

【答案】C

【解析】进程创建是需要填写PCB表的，其中唯一不需要的是II。考察一个进程创建的过程是这样的：当进程被创建，可以是用户创建，例如双击相关图标；也可以由父进程创建，例如lock（ ）时，操作系统首先到PCB表区搜索空闲的表格，若无则直接拒绝创建进程，若有则填，许多操写PCB表创建进程。通常填写PCB表的过程有一段时间（主要涉及资源分配需要协调），也有的操作系统不设这个中间状态。此时操作系作系统为此设立了一个中间状态称为“初始化”

统填写进程ID号、处理机参数、进程参数（状态、特权、优先级）、分配内存（若是虚拟存储就分配虚拟地址）、映射文件等，一切就绪，将控制权交给系统进行下一步调度。设备分配可能引起进程状态的改变，但不会创建新进程，用户登录成功和启动程序执行都会创建新的进程，所以本题答案为C。

13．元素a,b,c,d,e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是（ ）。

A.3 B.4 C.5 D.6

【答案】B

【解析】d首先出栈后的状态如下图所示。

此时可有以下4种操作：

（1）e进找后出栈，出梭序列为decba。 （2）c出找，e进找后出栈，出找序列为dceba。 （3）cb出找，e进找后出栈，出找序列为dcbea。

（4）cba出找，e进找后出找，出找序列为dcbae。

14．冯.诺依曼计算机中指令和数据均以二进制形式存放在存储器中，CPU区分它们的依据是（ ）。

A.指令操作码的译码结果 B.指令和数据的寻址方式 C.指令周期的不同阶段 D.指令和数据所在的存储单元 【答案】C

【解析】在冯 诺依曼结构计算机中指令和数据均以二进制形式存放在同一个存储器中，CPU可以根据指令周期的不同阶段来区分是指令还是数据，通常在取指阶段取出的是指令，其他阶段（分析取数阶段、执行阶段）取出的是数据。所以，CPU区分指令和数据的依据是指令周期的不同阶段。

15．假定用若干个2Kx4位的芯片组成一个8Kx8位的存储器，则地址0B1FH所在芯片的最小地址是（ ）。

A.0000H B.0600H C.0700H D.0800H 【答案】D

【解析】由若干芯片构成存储器，采用字和位同时扩展方法。8片2Kx4位的芯片分成4组，