题目内容
（请给出正确答案）
阅读下列算法说明和算法，将应填入(n)处的语句写在对应栏内。
1. 【说明】
实现连通图G的深度优先遍历(从顶点v出发)的非递归过程。
【算法】
第一步：首先访问连通图G的指定起始顶点v；
第二步：从V出发，访问一个与v(1)p，再从顶点P出发，访问与p(2)顶点q，然后从q出发，重复上述过程，直到找不到存在(3)的邻接顶点为止。
第三步：回退到尚有(4)顶点，从该顶点出发，重复第二、三步，直到所有被访问过的顶点的邻接点都已被访问为止。
因此，在这个算法中应设一个栈保存被(5)的顶点，以便回溯查找被访问过顶点的未被访问过的邻接点。
简答题官方参考答案
（由简答题聘请的专业题库老师提供的解答）
更多“阅读下列算法说明和算法，将应填入（n)处的语句写在对应栏内。1.【说明】 实现连通图G的深度优先遍历（”相关的问题
阅读下列函数说明和C代码，将应填入(n)处的字句写在对应栏内。
【说明】
函数QuickSort是在一维数组A[n]上进行快速排序的递归算法。
【函数】
void QuickSort(int A[ ],int s,int t)
{ int i=s,j=t+1,temp;
int x=A[s];
do{
do i ++ ;while (1);
do j -- ;while(A[j]＞x);
if(i＜j){temp=A[i];(2);(3);}
}while(i＜j);
A[a] =A[j];A[j] =x;
if(s＜i-1) (4);
if(j+1＜t) (5);
}
●试题一
阅读下列算法说明和算法，将应填入(n)处的语句写在答题纸的对应栏内。
【说明】
为了减少直接插入排序关键字的比较次数，本算法使用了二分(折半)插入法对一个无序数组R［1..n］进行排序。排序思想是对一个待插入元素，先通过二分法(折半)找到插入位置，后移元素后将该元素插入到恰当位置(假设R［］中的元素互不相同)。
【算法】
1．变量声明
X：DataType
i，j，low，high，mid，R0..n
2．每循环一次插入一个R［i］
循环：i以1为步长，从2到n，反复执行
①准备
X＜-R［i］； (1) ；high＜-i-1；
②找插入位置
循环：当 (2) 时，反复执行
(3)
若X．key＜R［mid］．key
则high＜-mid-1
否则 (4)
③后移
循环：j以-1为步长，从 (5) ，反复执行
R［j+1］＜-R［j］
④插入
R［low］＜-X
3．算法结束
●试题四
阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
函数QuickSort是在一维数组A［n］上进行快速排序的递归算法。
【函数】
void QuickSort(int A［］，int s，int t)
{int i=s，j=t+1，temp；
int x=A［s］；
do{
do i＋＋；while (1) ；
do j--；while(A［j］＞x)；
if(i＜j){temp=A［i］； (2) ； (3) ；}
}while(i＜j)；
A［a］=A［j］；A［j］=x；
if(s＜i-1) (4) ；
if(j+1＜t) (5) ；
}
阅读下列程序说明和c代码，将应填入(n)处的字句写在对应栏内。
[说明]
下面的程序利用递归算法计算x和y的最大公约数。
[函数2.1]
main ()
{ int x,y,k,t;
scanf(" % d% d" , &x, &y);
if(x＞y) { t=x;x=y; y=t;}
(1);
while(k! =0){
y=x;
(2);
k=y%x;
}
prinff("% d" ,x); }
[函数2.2说明]
函数fun(char *str,char *substr的功能是计算子串sugbstr在串str中出现的次数。
[函数2.2]
fun(ehar * str, char * substr)
{ int x,y,z;
(3);
for(x=0;str[ x] ! = '\O';x + + )
for(y=x,z=0;sabstr[z] = =str[y];(4),y+ +)
if((5)= ='\0') {
num + +;
break;
}
return(num);
}
阅读以下说明和C语言函数，将应填入(n)处的字句写在对应栏内。
[说明]
完成以下中序线索化二叉树的算法。
[函数]
Typedef int datatype;
Typedef struct node {
Int ltag, rtag;
Datatype data;
*lchild,* rchild;
}bithptr;
bithptr pre;
void inthread (p );
{if
{inthread (p-＞lchild );
if (p-＞lchild==unll ) (1);
if (P-＞RCHILD=NULL) p-＞rtag=1;
if (2)
{if (3) pre-＞rchild=p;
if (p-＞1tag==1 )(4);
}
INTHREAD (P-＞RCHILD );
(5);
}
}
阅读下列算法说明和算法，将应填入(n)处的语句写在对应栏内。
【说明】
本程序可以将字符串s1中出现的所有s2子串替换成s3，形成一个新串，但不破坏字符串s1。
【代码】
include＜stdio.h＞
include＜stdlib.h＞
include＜string.h＞
char*replace(char *s1, char *s2,char *s3)
{ char *p, *q, *r, *s; int |2，|3, i=0;
|2=strlen(s2);
|3=strlen(s3);
p=s1;
while((p=strstr(p,s2))!=NULL)
{ i++; /* 统计s2串出现的次数*/
(1);
}
i=(2);
s=r=(char*)malloc(i); /*分配动态内存存放新字符串*/
p=s1;
while(1)
{ q=strstr(p, s2); /* s2串是否在s1中出现，q是首次出现的位置*/
if(q!=NULL)
{ i=q-p;
(3);
r+=i;
(4);
r+=|3;
p=q+|2; /*将指向s1串的指针移到s2子串出现的位置后，
为下一次循环做好准备*/
}
else /*q为空，表示剩余的s1串中已经没有s2*/
{ (5);
break; /*终止循环*/
}
}
return(s); /*返回指向所形成的新串的指针*/
}
void main()
{ char *a="sabcababde", *b="ab", *c="efg", *d;
d=replace(a, b, c); printf("result=%s\n", d); free(d);
}
阅读下列函数说明和C代码，将应填入(n) 处的字句写在对应栏内。
【说明】
函数print(BinTreeNode*t; DateType &x)的功能是在二叉树中查找值为x的结点，并打印该结点所有祖先结点。在此算法中，假设值为x的结点不多于一个。此算法采用后序的非递归遍历形式。因为退栈时需要区分右子树。函数中使用栈ST保存结点指针ptr以及标志tag，Top是栈顶指针。
【函数】
void print(BinTreeNode * t; DateType &x) {
stack ST; int i, top; top = 0;//置空栈
while(t! = NULL &&t-＞ data!= x || top!=0)
{ while(t!= NULL && t-＞ data!=x)
{
/*寻找值为x的结点*/
(1);
ST[top]. ptr = t；
ST[top]. tag = 0;
(2);
}
if(t!= Null && t -＞ data == x) { /*找到值为x的结点*/
for(i=1;(3);i ++)
printf("%d" ,ST[top]. ptr -＞data);
else {
while((4))
top--;
if(top＞0)
{
ST[top]. tag = 1;
(5);
}
}
}
●试题二
阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
函数print(BinTreeNode*t；DateType ＆x)的功能是在二叉树中查找值为x的结点，并打印该结点所有祖先结点。在此算法中，假设值为x的结点不多于一个。此算法采用后序的非递归遍历形式。因为退栈时需要区分右子树。函数中使用栈ST保存结点指针ptr以及标志tag，Top是栈顶指针。
【函数】
void print(BinTreeNode*t；DateType ＆x){
stack ST；int i，top；top=0；∥置空栈
while(t!=NULL ＆＆t-＞data!=x‖top!=0)
{while(t!=NULL ＆＆ t-＞data!=x)
{
∥寻找值为x的结点
(1) ；
ST［top］．ptr=t；
ST［top］．tag=0；
(2) ；
}
if(t!=Null ＆＆ t-＞data==x){∥找到值为x的结点
for(i=1； (3) ；i＋＋)
printf("％d"，ST［top］．ptr-＞data)；}
else{
while((4) )
top--；
if(top＞0)
{
ST［top］．tag=1；
(5) ；
}
}
}
●试题一
阅读下列算法说明和算法，将应填入(n)处的字句写在答卷的对应栏内。
【算法说明】
某英汉词典文件包含N个记录(N＞1)，每个记录有两个字段：一个是英文单词，另一个是相应的汉语解释。各个记录按英文单词的词典顺序排列，各英文单词并不重复。
本算法用于维护、更新该英汉词典文件。维护、更新的方法是：首先输入一个英文单词及其汉语解释，然后在该词典中查找输入的英文单词，若找到，则用输入的汉语解释更新原有的解释；若找不到，则需要将输入的英文单词及其汉语解释插入到该词典的适当位置，使各记录仍按英文单词的词典顺序排列。
【算法】
第一步读入英汉词典文件，并将读入的N个英文单词依次存放在字符串数组ENG中，将相应的汉语解释依次存放在字符串数组CN中。数组元素CN(i)给出了数组元素ENG(i)的解释。
第二步输入英文单词及其汉语解释，将它们分别存放在字符串变量E和C中。若E为空串或都是空格，则转向第四步。
第三步根据变量E的值，用二分法在数组ENG中查找。具体步骤如下：
1.1→L，N→H
2.INT((L+H)／2)→K
3.若E=ENG(K)，则C→CN(K)，转向第二步
若E＜ENG(K)，则K-1→ (1) ；若E＞ENG(K)，则K+1→ (2)
4.若H＜L则
对I=N，L，-1(始值，终值，增量)循环执行：
ENG(I)→ENG(I+1)
CN(I)→CN(I+1)
然后，将E和C分别存入 (3) 和 (4) ，N+1→N最后转向第二步
否则，转向 (5)
第四步将数组ENG和CN输出，形成新的英汉词典文件，算法结束。
阅读下列说明和流程图2-3，将应填入(n)的字句写在答题纸的对应栏内。
【说明】
下面的流程图描述了对8位二进制整数求补的算法。
该算法的计算过程如下：从二进制数的低位(最右位)开始，依次向高位逐位查看，直到首次遇到“1”时，停止查看。然后，对该“1”位左面的更高位(如果有的话)，逐位求反，所得的结果就是对原二进制数求补的结果。
例如：对二进制整数10101000求补的结果是01011000。
设8位二进制整数中的各位，从低位到高位，依次存放在整型数组BIT的B1T[1]～BIT[8]中。例如，二进制整数10101000存放在数组BIT后，就有BIT[1]=0，BIT[2]=0，…，BIT[7] =0，BIT[8]=1。若流程图中存在空操作，则用NOP表示。
【流程图】
注：流程图中(1)处按“循环变量名：循环初值，增量，循环终值”格式描述。
警告：系统检测到您的账号存在安全风险
为了保护您的账号安全，请在“简答题”公众号进行验证，点击“官网服务”-“账号验证”后输入验证码“”完成验证，验证成功后方可继续查看答案！
