软考初级程序员下午题（10）_初级程序员下午试题

试题四

阅读以下说明和C语言函数，将应填入______处的语句填写完整。
[说明]
本程序利用非递归算法实现二叉树后序遍历。

 [函数]
    #include ＜stdio.h＞
    #include ＜stdlib.h＞
    typedef struct node { //二叉树的结点数据结构类型
    char data;
    struct node *left;
    struct node *right;
    } BTREE;
    void SortTreelnsert(BTREE **tree, BTREE *s)
    {
    if(*tree==NULL) *tree=s;
    else
    if(s-＞data ＜ (*tree)-＞data)
    SortTreelnsert(______, s);
    else if(s-＞data ＞= (*tree)-＞data)
    SortTreelnsert(______, s);
    }
    void TraversalTree(BTREE *tree)
    {
    BTREE *stack[1000], *p;
    int tag[1000], top=0;
    p=tree;
    do {
    while (p!=NULL)
    {
    stack[++top]=p;
    ______;
    tag[top]=0;   //标记栈顶结点的左子树已进行过后序遍历
    }
    while (top ＞ 0 && ______)  //栈顶结点的右子树是否被后序遍历过
    {
    p=stack[top--];
    putchar(p-＞data);
    }
    if (top ＞ 0)//对栈顶结点的右子树进行后序遍历
    {
    ______;
    tag[top]=1;
    }
    } while (top ＞ 0);
    }
    void PrintSortTree(BTREE *tree)
    {
    if(tree!=NULL)
    {
    PrintSortTree(tree-＞left);
    putchar(tree-＞data);
    PrintSortTree(tree-＞right);
    }
    }
    main()
    {
    BTREE*root=NULL,*node;
    char ch;
    ch=getchar();
    while(ch!='#')
    {
    node=(BTREE*)malloc(sizeof(BTREE.);
    node-＞data=ch;
    node-＞left=node-＞right=NULL;
    SortTreelnsert(&root,node);
    ch=getchar();
    }
    PrintSortTree(root);
    putchar('\n');
    TraversalTree(root);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

试题五

阅读以下说明和C++代码，将应填入______处的字句填写完整。
[说明]
C++标准模板库中提供了map模板类，该模板类可以表示多个“键一值”对的集合，其中键的作用与普通数组中的索引相当，而值用作待存储和检索的数据。此外，C++模板库还提供了pair模板类，该类可以表示一个“键-值”对。pair对象包含两个属性：first和second，其中first表示“键-值”中的“键”，而second表示“键一值”中的“值”。
map类提供了insert方法和find方法，用于插入和查找信息。应用时，将一个pair对象插入(insert)到map对象后，根据“键”在map对象中进行查找(find)，即可获得一个指向pair对象的迭代器。
下面的C++代码中使用了map和pair模板类，将编号为1001、1002、1003的员工信息插入到map对象中，然后输入一个指定的员工编号，通过员工编号来获取员工的基本信息。员工编号为整型编码，员工的基本信息定义为类employee。
map对象与员工对象之间的关系及存储结构如下图所示。

[C++代码]
#include ＜iostream＞
#include ＜map＞
#include ＜string＞
using namespace std;
class employee{
______:
employee(string name,string phoneNumber,string address){
this-＞name = name;
this-＞phoneNumber = phoneNumber;
this-＞address = address;
}
stdng name;
string phoneNumber;
string address;
};
int main()
{
map ＜int, employee*＞ employeeMap;
typedef pair ＜int, employee*＞ employeePair;
for (int employlndex = 1001; employlndex ＜= 1003; employlndex++){
char temp[10];             //临时存储空间
_itoa(employlndex,temp,10);    //将employlndex转化为字符串存储在temp中
string tmp(______);       //通过temp构造string对象
employeeMap. ______(employeePair (employlndex,
new employee("employee-"+tmp,
"85523927-"+tmp,
"address-"+tmp)
)
); //将员工编号和员工信息插入到employeeMap对象中
}
int employeeNo = 0;
cout ＜＜ "请输入员工编号:";
______＞＞employeeNo;        //从标准输入获得员工编号
map＜int,employee*＞::const_iterator it;
it=______find(employeeNo);        //根据员工编号查找员工信息
if(it==employeeMap.end()){
cout＜＜"该员工编号不存在!"＜＜endl;
return-1;
}
cout＜＜"你所查询的员工编号为："＜＜it-＞first＜＜endl;
cout＜＜"该员工姓名："＜＜it-＞second-＞name＜＜endl;
cout＜＜"该员工电话："＜＜it-＞second-＞phoneNumber＜＜endl;
cout＜＜"该员工地址："＜＜it-＞second-＞address＜＜endl;
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

试题六

阅读以下说明和Java代码，将应填入______处的字句填写完整。
[说明]
java.util包中提供了HashMap模板类，该模板类可以表示多个“键-值”对的集合，其中“键”的作用与普通数组中的索引相当，而“值”用作待存储和检索的数据。HashMap实现了Map接口。在Map接口中定义了put和get方法，put方法表示Map对象中加入一个“键-值”对，get方法则通过“键”来获取其对应的“值”。
下面的Java代码中使用了HashMap模板类，将编号为1001、1002、1003的员工信息插入到HashMap对象中，然后输入一个指定的员工编号，通过员工编号来获取员工的基本信息。员工编号为整型编码，而员工的基本信息定义为类employee。
HashMap对象与员工对象之间的关系及存储结构如下图所示。

  [Java代码]
    import java.util.*;
    class employee{
    employee(String name,String phoneNumber,String address){
    this.name=name;
    this.phoneNumber=phoneNumber;
    this.address=address;
    }
    String name;
    String phoneNumber:
    String address;
    };
    public class javaMain {
    public static void main(Stdng[] args) {
    Map＜Integer, employee＞ employeeMap = new HashMap＜tnteger, employee＞();
    for (Integer emptoylndex = 1001; employlndex ＜= 1003; employlndex++){
    String tmp = employlndex.______();
    employeeMap.______(employlndex, ______("employee-"+tmp,
    "85523927-"+tmp,
    "address-"+tmp)
    );//将员工编号和员工信息插入到employeeMap对象中
    }
    int employeeNo = 0;
    System.out print("请输入员工编号:");
    Scanner s= new Scanner(System.in);
    employeeNo = s.nextlnt0;          //从标准输入获得员工编号
            employee result = employeeMap.______(employeeNo);
    if(______== null)
    {
    System.out.println("该员工编号不存在!");
    return;
    }
    System.out.println("你所查询的员工编号为: "+ employeeNo);
    System.out.println("该员工姓名: "+ result.name);
    System.out println("该员工电话: "+ resultphoneNumber);
    System.out.printtn("该员工地址: "+ resultaddress);
    }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

试题四

(1)&(*tree)-＞left
(2)&(*tree)-＞right
(3)p=p-＞left
(4)tag[top]==1
(5)p=stack[top]-＞right

[解析] 本题考查二叉树后序遍历的非递归实现。
二叉树后序遍历的特点是首先按后序遍历根结点的左子树，然后按后序遍历根结点的右子树，再访问根结点。后序遍历得到的序列根结点总在最后，我们可以用栈结构来实现后序遍历。下面来具体分析程序。
第1空很明显是函数SortTreeInsert()的第一个参数，此函数的功能是建立一棵排序二叉树，此空在条件判断语句下面，如果条件成立，说明待插入结点的值小于当前结点的值，根据排序二叉树的生成原理，应该把待插入结点插入到当前结点的左子树中，因此，此空的参数是指向当前结点左子树的地址。这里需要注意的是，这个参数是一个二重指针，需要在一重指针前加一个取地址操作符“&”。所以，此空答案为“&(*tree)-＞left”。
第2空也是函数SortTreeInsert()的第一个参数，但调用这个函数的条件与上面不一样，此空是在待插入结点的值大于等于当前结点的值的时候调用函数，根据排序二叉树的生成原理，此时应该把待插入结点插入到当前结点的右子树中，因此，此空答案为“&(*tree)-＞right”。
第3空在函数TraversalTree()中，此函数用来对树进行后序遍历，此空在一个循环体中，从程序中可以看出这个循环体的功能是将排序二叉树的所有左子树结点入栈，因此，在当前结点入栈后，接下来是它的孩子结点入栈，所以，此空答案为“p=p-＞left”。
第4空是循环的判断条件，其作用在注释中已经给出，是判断栈顶结点的右子树是否被后序遍历过。从上面程序tag[top]=0表示栈顶结点的左子树已进行过后序遍历可以推断出，tag[top]的值是用来标记栈顶结点的左右子树已进行过后序遍历，因此，此空答案为“tag[top]==1”。
第5空在条件判断语句下面，而条件判断语句为真表明要对栈顶结点的右子树进行后序遍历，那么就应该让当前需处理结点的指针指向栈顶结点的右孩子，而指向当前需要处理结点的指针变量是p，因此，此空答案为“p=stack[top]-＞right”。

试题五

(1)public
(2)temp
(3)insert
(4)cin
(5)employeeMap

[解析] 本题主要考查C++程序设计语言中类库的使用。
题干中已经给出了Map类和Pair类的使用方式，Map类主要用于存储一组员工的信息，而Pair类则主要用于建立员工号和员工信息的对应关系，员工信息主要使用类employee的对象来存储。C++语言的类生成对象时，需要调用类的构造方法，因此，employee的构造方法应该为公有构造方法，空缺1处的答案应该为public；空缺2处的代码主要是根据字符数组temp[10]来构造一个string对象，参数应为temp；空缺3处的代码是构造员工对象，并将员工对象和员工编号放入一个Pair对象中，再将Pair对象插入到employeeMap中，根据题干说明，Map类中insert方法完成插入对象的功能，因此，空缺3处应该填入insert；空缺4处的自的是从标准输入中获得员工编号，标准类库中已经定义了标准输入为cin；空缺5处是根据用户输入的员工编号，查取员工信息，Map类中的find方法可完成该功能，而当前员工的编号和员工信息都存储在Map类的实例employeeMap中。

试题六

(1)toString
(2)put
(3)new employee
(4)get
(5)result

[解析] 本题主要考查Java程序设计语言中类库的使用。空缺1处需要将employlndex转化为字符串，因此可以使用整型数的toString方法；空缺2和3处的代码是希望构造出employee对象，并把新构造出的对象及其对应的编号加入到HashMap类的实例employeeMap中，而HashMap的put方法可完成插入编号和员工对象的功能，因此空缺2处需要填写put方法，空缺3处需要使用new构造一个新的employee对象；空缺4处主要是使用employeeMap对象根据员工号码查找员工信息，可使用HashMap中的get方法，该方法查询到员工信息后将放入result引用中，若没有查到，result将为空。