2. 计算机
  3. 阅读以下说明和c代码，将应填入(n)处的字句写在答题纸对应栏内。 【说明】 下面程序用来将打乱的单词还原为原来的次序，比如将rty还原为try。单词的原来次序存储于wordlist．txt文件中，原则上可用穷举法(ny对应的穷举为：rty、ryt、try、

阅读以下说明和c代码，将应填入(n)处的字句写在答题纸对应栏内。 【说明】 下面程序用来将打乱的单词还原为原来的次序，比如将rty还原为try。单词的原来次序存储于wordlist．txt文件中，原则上可用穷举法(ny对应的穷举为：rty、ryt、try、

admin2014-10-11  25
问题 阅读以下说明和c代码，将应填入(n)处的字句写在答题纸对应栏内。
【说明】
下面程序用来将打乱的单词还原为原来的次序，比如将rty还原为try。单词的原来次序存储于wordlist．txt文件中，原则上可用穷举法(ny对应的穷举为：rty、ryt、try、tyr、ytr、yrt)，但考虑到破译速度，采用如下方法：注意到单词列表中不存在组成字符完全相同的单词(如Hackl2与Hack21包含完全相同的字符)，因此将单词中的字符进行重组再进行比较，例如，try单词重组为rty(按AscII码顺序)，这样不管打乱的单词是什么顺序，只要是由r、t、y三个字母组成的均破译为try，大大提高破译速度。程序中借助二叉排序树以进一步提高查找效率，二叉排序树左子树(如果有)上的节点对应的值均小于根节点的值，右子树(如果有)上的节点对应的值均大于根节点的值。函数中使用的符号定义如下：
#define Numberofwords    1275／／单词总数
#de fine MaxLength    10／／最长单词所含字符数
char wordList[Numberofwords][MaxLength]；／／存储单词列表
intcmp(Node*q，Node*p)；／／q与p比较。p小，返回负值；p大返回正值；相等，返回O
typedef struct N0de(／／二叉树节点
char*eleLetters;／／重组后的字符串
int index；／／对应单词表中的下标
struct Node*1child，  *rchild；／／左右子节点
}Node；
【C代码】
void reCompose(Node  *p，  char  &temp)
／／重组，亦即将temp字符串中的字符升序排序，存储于p节点中
／／采用直接插入排序法
{
char c：
strcpy(p一>eleLetters，  temp)；／／
intlen=strlen(temp)；
int i，  j，  k；
for(i=0；  i<  len一1；  i++){
k=i：
for(j  =i+1；  jif(p一>eleLetters[j]  eleLetters[k])k=j；
}
if( (1)){
c=p一>eleLet七ers；
p一>eleLetters  =p一>eleLetters[k]；
p一>eleLetters[k]=c；
}／／if
}／／for
}；
int  find(N0de&root，  char*temp)
／／在二叉排序树root中查找与temp匹配的单词。
／／若匹配返回相应单词在wordList中下标；若查找失败，返回一1
  Node*p，  *q；
int flag;
p=(2);／／临时存储
    recompose(p，  temp)；／／将temp重组
    q=＆root；
    while((flag=  (3)  )  ＆＆q  !=NULL){
    if(flag<0)(／／搜索左子树
    q=q一>lChild;
    )else(／／搜索右子树
    q=q一>rChild；
    }
    }／／while
    if(flag==0)(／／找到匹配的，保存下标
    return (4)；
    }
    if((5))(／／查找失败
    printf(”cant unscramble the following word  ：  ％s”，  temp)；；
    return一1：
    }
  }：
选项
答案(1)k!=i (2)(Node*)maIloc(sizeofp) (3)q一>cmp(p) (4)q一>index (5)q==NULL
解析 该题涉及二叉排序树的应用、直接插入排序算法等。空(1)所在函数是直接插入排序的一个实现，理解了商接插入排序算法很容易得出答案，条件(1)成立时，需要进行交换，故空(1)应填“k!=i”。空(2)比较简单，p声明为指针，在引用reCompse(P，temp)之前需要申请空间，故空(2)应填“(Node*)malloc(sizeofp)”。接下来在二叉排序上进行查找。while循环体内只有两个分支，一个是flag＜0时继续往左子树搜索，另一个就是往右子树搜索，此时应该对应的是flag＞0。据此可判知，flag存储的是查找节点P与当前节点q之间的大小关系，显然是调用类Node的cmp方法，故空(3)应填“cmp(q，p)”。注意，不能填成“cmp(p，q)”，那样将不可能找到匹配的，因为该二叉排序树是左子树小于根节点，而cmp(q，p)当p比q小时返回负值，搜索应往左子树继续。空(4)是找到匹配时返回，根据函数注释，函数nnd的返回值是匹配单词在WordList数组中的下标，结构Node的index域正好存储的是下标。故空(4)应填“q一>index”。空(5)是查找失败的情况，对应条件为“q==NuLL”。故空(5)应填“q==NULL”。
转载请注明原文地址:https://kaotiyun.com/show/GaDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

软件设计师下午应用技术考试

软考中级

相关试题推荐
随机试题
最新回复(0)