1、【
简答题】
试题一(共15分)
阅读以下说明和流程图,填补流程图中的空缺(1)~(5),将解答填入答题纸的对应栏内。
【说明】
【流程图】
[15分]
解析:
①1->S
②x/n
③T<0.00001
④S+T
⑤n++
2、【
简答题】
试题二(共15分)
阅读以下说明和C函数,将应填入 (n) 处的字句写在答题纸的对应栏内。【说明】
C语言常用整型(int)或长整型(long)来说明需要处理的整数,在一般情况下可以满足表示及运算要求,而在某些情况下,需要表示及运算的整数比较大,即使采用更长的整型(例如,long long类型,某些C系统会提供)也无法正确表示,此时可用一维数组来表示一个整数。
假设下面要处理的大整数均为正数,将其从低位到高位每4位一组进行分组(最后一组可能不足4位),每组作为1个整数存入数组。例如,大整数2543698845679015847在数组A中的表示如下(特别引入-1表示分组结束):
在上述表示机制下,函数add_large_number(A,B,C)将保存在一维整型数组A和B中的两个大整数进行相加,结果(和数)保存在一维整型数组C中。
【C函数】
void add_large_number(int A[], int B[], int C[])
{
int i, cf ; /*cf存放进位*/
int t, *p; /*t为临时变量,p为临时指针*/
cf = (1) ;
for(i = 0; A[i]>-1 && B[i]>-1; i++) {
/*将数组A、B对应分组中的两个整数进行相加*/
t = (2) ;
C[i] = t % 10000;
cf = (3) ;
}
if ( (4) ) p = B;
else p = A;
for( ; p[i]>-1; i++) { /*将分组多的其余各组整数带进位复制入数组C*/
C[i] = (p[i] + cf) %10000; cf = (p[i] + cf) /10000;
}
if ( cf > 0 ) C[i++] = cf;
(5) = -1; /*标志"和数"的分组结束*/
}
[15分]
解析:
①0
②A[i]+B[i]+cf
③t/10000
④A[i]==-1或者B[i]>-1等等
⑤C[i]
3、【
简答题】
试题三(共15分)
阅读以下说明、C函数和问题,将解答填入答题纸的对应栏内。
【说明】
二叉查找树又称为二叉排序树,它或者是一棵空树,或者是具有如下性质的二叉树:
● 若它的左子树非空,则其左子树上所有结点的键值均小于根结点的键值;
● 若它的右子树非空,则其右子树上所有结点的键值均大于根结点的键值;
● 左、右子树本身就是二叉查找树。
设二叉查找树采用二叉链表存储结构,链表结点类型定义如下:
typedef struct BiTnode{
int key_value; /*结点的键值,为非负整数*/
struct BiTnode *left,*right; /*结点的左、右子树指针*/
}*BSTree;
函数find_key(root, key)的功能是用递归方式在给定的二叉查找树(root指向根结点)中查找键值为key的结点并返回结点的指针;若找不到,则返回空指针。
【C函数】
BSTree find_key(BSTree root, int key)
{
if ( (1) )
return NULL;
else
if (key == root-> key_value)
return (2) ;
else if (key < root -> key_value)
return (3) ;
else
return (4) ;
}
【问题1】
请将函数find_key中应填入(1)~(4)处的字句写在答题纸的对应栏内。【问题2】
若某二叉查找树中有n个结点,则查找一个给定关键字时,需要比较的结点个数取决于 (5) 。
[15分]
解析:
①root==NULL
②root
③find_key(root->left,key)
④find_key(root->right,key)
⑤关键字所在的结点的层数和二叉树的高度
解析:
1.①{int k,n, sun=0;
②scanf("%d",&n);
2.①str++
②*str='a'
5、【
简答题】
试题五(共15分)
阅读以下说明和C++代码,将应填入 (n) 处的字句写在答题纸的对应栏内。【说明】
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对象与员工对象之间的关系及存储结构如图5-1所示。
【C++代码】
#include <iostream>
#include <map>
#include <string>
using namespace std ;
class employee{
(1) :
employee(string name,string phoneNumber, string address){
this->name = name;
this->phoneNumber = phoneNumber;
this->address = address;
}
string name;
string phoneNumber;
string address;
};
int main( )
{
map <int, employee*> employeeMap;
typedef pair <int, employee*> employeePair;
for (int employIndex = 1001; employIndex <= 1003; employIndex++){
char temp[10] ; //临时存储空间
_itoa(employIndex,temp,10); //将employIndex转化为字符串存储在temp中
string tmp( (2) ); //通过temp构造string对象
employeeMap. (3) ( employeePair ( employIndex,
new employee("employee-" + tmp,
"85523927-"+tmp,
"address-"+tmp)
)
); //将员工编号和员工信息插入到employeeMap对象中
}
int employeeNo = 0;
cout << "请输入员工编号:";
(4) >> employeeNo; //从标准输入获得员工编号
map<int,employee*>::const_iterator it;
it = (5) .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;
}
[15分]
解析:
①public
②temp
③insert
④cin
⑤employeeMap
6、【
简答题】
试题六(共15分)
阅读以下说明和Java代码,将应填入 (n) 处的字句写在答题纸的对应栏内。
【说明】
java.util包中提供了HashMap模板类,该模板类可以表示多个“键-值”对的集合,其中“键”的作用与普通数组中的索引相当,而“值”用作待存储和检索的数据。HashMap实现了Map接口。在Map接口中定义了put和get方法,put方法表示Map对象中加入一个“键-值”对,get方法则通过“键”来获取其对应的“值”。
下面的Java代码中使用了HashMap模板类,将编号为1001、1002、1003的员工信息插入到HashMap对象中,然后输入一个指定的员工编号,通过员工编号来获取员工的基本信息。员工编号为整型编码,而员工的基本信息定义为类employee。
HashMap对象与员工对象之间的关系及存储结构如图6-1所示。
【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;
};
ublic class javaMain {
public static void main(String[] args) {
Map<Integer, employee> employeeMap = new HashMap<Integer, employee>();
for (Integer employIndex = 1001; employIndex <= 1003; employIndex++){
String tmp = employIndex. (1) ();
employeeMap. (2) (employIndex, (3) ("employee-"+tmp,
"85523927-"+tmp,
"address-"+tmp
)
); //将员工编号和员工信息插入到employeeMap对象中
}
int employeeNo = 0;
System.out.print("请输入员工编号:");
Scanner s= new Scanner(System.in);
employeeNo = s.nextInt(); //从标准输入获得员工编号
employee result = employeeMap. (4) (employeeNo);
if ( (5) == null)
{
System.out.println("该员工编号不存在 !");
return;
}
System.out.println("你所查询的员工编号为:" + employeeNo);
System.out.println("该员工姓名:" + result.name);
System.out.println("该员工电话:" + result.phoneNumber);
System.out.println("该员工地址:" + result.address );
}
}
[15分]
解析:
①public
②temp
③insert
④cin
⑤employeeMap