二、填空题
(1)在长度为n的顺序存储的线性表中删除一个元素,最坏情况下需要移动表中的元素个数为n-1____。
(2)设循环队列的存储空间为Q(1:30),初始状态为front=rear=30。现经过一系列入队与退队运算后,front=16,rear=15,则循环队列中有___29___个元素。
(3)数据库管理系统提供的数据语言中,负责数据的增、删、改和查洵的是___数据库操纵语言___。
(4)在将E-R图转换到关系模式时,实体和联系都可以表示成。__关系____。
(5)常见的软件工程方法有结构化方法和面向对象方法,类、继承以及多态性等概念属于__面向对象法____。
(6)Access的查询分为5种类型,分别是选择查询、参数查询、操作查洵、SQL查询和_交叉表查询_____查询。
(7)如果要求用户输入的值是一个3位的整数,那么其有效性规则表达式可以设置为______。
(8)在工资表中有姓名和工资等字段,若要求查询结果按照工资降序排列,可使用的SQL语句是:SELECT姓名,工资FROM工资表ORDER BY工资_DESC_____。
(9)在宏中引用窗体控件的命令格式是______。
(10)已知:Dim rs As new ADODB RecordSet,在程序中为了得到记录集的下一条记录,应该使用的方法是rs.______。
(11)在VBA中,没有显式声明或使用符号来定义的变量,其数据类型默认是______。
(12)下列程序的功能是:输入10个整数,逆序后输出。请在程序空白处填入适当语句使程序完成指定的功能。
Pnvafe Sub Command2_Click()
Dim i, j, k, temlp, arr(11)As Integer
Dim result As Scring
For k=1 T0 10
arr (k)=Val(InputBox("请输入第" &k&"个数:","数据输入窗口"))
Nexc k
i=1
i=10
Do
temp=arr(i)
arr(i)=arr(i)
arr(j)=temp
i=i+1
j= (12)
Loop While (13)
rpsult""
For k=1 TO 10
result=result & arr(k) & Chr(13)
Next k
MsgBox result
End Sub
下面程序的功能是把316表示为两个加数的和,使两个加数分别能被13和11整除,请选择填空。 #include<stdio.h> main() { int i=0,j,k; do{i++;k=316-13*i}while(______); j=k/11; printf("316=13*%d+11,%d”,i,j); }
A.k/11
B.k%11
C.k/11==0
D.k%11==0
0-1背包问题可以描述为:有n个物品,对i=1,2,…,n,第i个物品价值为vi ,重量为wi(vi,和wi为非负数),背包容量为W(W为非负数),选择其中一些物品装入背包,使装入背包物品的总价值最大,,且总重量不超过背包容量,即,其中,xi∈{0,1},xi=0表示第i个物品不放入背包,xi=1表示第i个物品 放入背包。
【问题1】(8分)
用回溯法求解此0-1背包问题,请填充下面伪代码中(1)~(4)处空缺。
回溯法是一种系统的搜索方法。在确定解空间后,回溯法从根结点开始,按照深度优先策略遍历解空间树,搜索满足约束条件的解。对每一个当前结点,若扩展该结点己经不满足约束条件,则不再继续扩展。为了进一步提高算法的搜索效率,往往需要设计一个限界函数,判断并剪枝那些即使扩展了也不能得到最优解的结点。现在假设已经设计了BOUND(v,w,k,W)函数,其中v, w, k和W分别表示当前已经获得的价值、当前背包的重量、己经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个结点,该函数值表示确定了部分物品是否选择之后,对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值,若该价值小于等于当前已经得到的最优解,则该结点无需再扩展。
下面给出0-1背包问题的回溯算法伪代码。
函数参数说明如下:
W:背包容量;n:物品个数;w:重量数组;v:价值数组;fw:获得最大价值时背包的重量;fp:背包获得的最大价值;X:问题的最优解。
变量说明如下:
cw:当前的背包重量;cp:当前获得的价值;k:当前考虑的物品编号;Y:当前已获得的部分解。
BKNAP(W,n,w,v,fw,fp,X)
1 cw ← cp ← 0
2 (1)
3 fp ← -1
4 while true
5 while k≤n and cw+w[k]≤W do
6 (2)
7 cp ← cp+v[k]
8 Y[k]← 1
9 k ← k+1
10 if k>n then
11 if fp<cp then
12 fp ← cp
13 fw ← ew
14 k ← n
15 X ← Y
16 else Y(k)← 0
17 while BOUND(cp,cw,k,W) ≤fp do
18 while k≠0 and Y(k)≠1 do
19 (3)
20 if k=0 then return
21 Y[k]←0
22 cw ← cw ← w[k]
23 cp ← cp ← v[k]
24 (4)
A.scanf("%2d%2d%2d",&i,&j,&k);
B.scanf("%d %d %d",&i,&j,&k);
C.scanf("%d,%d,%d",&i,&j,&k);
D.scanf("i=%d,j=%d,k=%d",&i,&j,&k);
A.scanf(“%2d%2d%2d”,&i,&j,&k);
B.scanf(“%d %d %d”,&i,&j,&k);
C.scanf(“%d,%d,%d”,&i,&j,&k);
D.scanf(“i=%d, j=%d,k=%d”,&i,&j,&k);
阅读下列程序说明和C代码,把应填入其中n处的字句写在答卷的对应栏内。
【说明】
程序利用选择排序算法对数组a中的N个整数按照从小到大的顺序排列,并将排序结果显示出来。
【程序】
define N 10
main()
{
void (1);
int i,a[N];
for(i=0;i<10,i++) /*输入*/
scanf(“%d”,&a[i]);
(2);
for(i=0;i<N,i++) /*输出*/
printf(“%3d”,a[i]);
}
void selectSon(int x[],int n)
{
int i,j,k,t;
for(int i=0; (3);i++)
{
k=i;
for(j=i+1;j<n;j++)
if (4) k=j;
if (5)
{t=x[i];x[i]=x[k];x[k] =t;}
}
}
阅读以下说明和C++ 程序,将应填入(n)处的字句写在对应栏内。
[说明]
试从含有n个int 型数的数组中删去若干个成分,使剩下的全部成分构成一个不减的子序列。设计算法和编写程序求出数组的不减子序列的长。
[C++ 程序]
include<stdio.h>
define N 100
int b[]={9,8,5,4,3,2,7,6,8,7,5,3,4,5,9,1};
int a [N];
define n sizeofb/sizeofb[0]
void main ()
{
kit k,i,j;
(1)
(2)
for (i=1;i<n; i++ )
{
for (j=k;(3); j--);
(4); /*长为 j+1 的子序列的终元素存储在 a[j+1]*/
if ((5)k++; /*最长不减子序列长 k 增1*/
}
printf ("K = %d\n ",k );
}
阅读以下说明和C语言程序,将应填入(n)处的字句写在对应栏内。
【说明】
设有3n+2个球互连,将自然数1~3n+2分别为这些球编号,使相连的两球编号之差的绝对值正好是数列1,2,…,3n+1中的各数,如下图所示:
其中填自然数的思想如下;
(1)先自左向右,第1列中间1个填数,然后第2列上、下2个填数,每次2列;但若n为偶数,最后1次只排第1列中间一个数。
(2)自右向左,先右第1列中间填数;若n是奇数,再右第2列中间填数。然后依次右第1列上、下2个填数,再右第2列中间1个填数,直到左第2列为止。
【程序】
include <stdio.h>
define size 10
int a[3][size];
void main()
{
int i,k,m,n;
printf("imput the n:");
scanf("%d",&n);
k=1;
for(i=0; i<=n/2; i++)
{
a[1][2*i]=k; k++;
if((i==n/2)&& (1) ||(i<n/2))
{
a[0][2*i+1]=k;
k++;
(2)
k++;
}
}
if(n%2==1)
{
(3)
k++;
m=n;
}
else
(4)
for(i=0; i<n/2; i++)
{
a[1][m-2*i]=k; k++;
(5)
k++;
a[2][m-2*i-1]=k; k++;
}
a[1][1]=k;
printf("\n");
printf(" ");
for(i=1; i<=n; i++)
printf("%6d",a[0][i]);
printf("\n\n");
for(i=0; i<=n+1; i++)
printf("%6d",a[1][i]);
printf("\n\n");
printf(" ");
for(i=1; i<=n; i++)
printf("%6d",a[2][i]);
printf("\n");
}
阅读以下说明及Visual Basic程序代码,将应填入(n)处的字句写在对应栏内。
[说明]
某银行新近开通外汇定期存款业务。为方便用户查询不同存款方式下的日利率、计算本利,特开发了日利率查询及本利计算程序,其运行窗口如下图所示。用户只要在界面上选择相应的存款方式(包括外汇币种、存期等),便可单击按钮一查询存款日利率。若输入一定数量的本金。程序还会根据所选择的存期计算并输出本利和。
在开发过程中,选择币种和存期的组合框(ComboBox)名分别为Combo1和Combo2,单旋钮 (CommandButton)“个人单位”和“金融机构”分别名为Option1和Option2,用于输入本金的文本框 (TextBox)名为Price,“输出日利率”和“计算本利和”按钮(CommandButton)分别名为Command1和 Command2。且已知,第i类币种、第j类存期之下,个人单位与金融机构的存款日利率分别存放于数组元素interestRate(i,j,0)和interestRate(i,j,1)中,其中i,j从0开始计数。
[Visual Basic代码]
Dim interestBate(50,10,2) As Single ’通用声明
Private Sub Form_Load()
…… ’为数组interestRate赋初值
End Sub
’根据所选择的币种、存期等信息确定日利率
Function getInterestRate()
Dim strCurrency, strTime As String, i, j, k, intDays As Integer
strCurrency = Combo1.Text
strTime = Combo2.Text
For i = 0 To Combol. ListCount - 1
If Combol.List(i) = strCurrency Then (1)
Next
For j = 0 To Combo2.ListCount - 1
IfCombo2.List(j) = strTime Then (1)
Next
If (2)=True Then
k=0
Else: k=1
End If
(3)= interestRate(i, j, k)
End Function
’输出日利率
Private Sub Commund1_Click()
MsgBox "日利率为" & getInterestRate()
End Sub
’输出本利和
Private Sub Command2_Click()
Dim strTime As String, intDays As Integer, sngCorpus, sngResult As Single
strTime = Combo2. Text
sngCorpus = CSng(Text1.Text)
(4) ’计算存款天数(以每月30天计)
Case "一个月" :intDays = 30
Case "三个月" :intDays = 90
Case "六个月" :intDays = 120
End Select
’计算并输出本利和
sngResult = sngCorpus +(5)
MsgBox "本利之和为:" & sngResult
End Sub
下列给定程序中,函数fun()的功能是:给一维数组a输入任意4个整数,并按如下的规律输出。例如输入1,2,3,4,程序运行后输出以下方阵:
4 1 2 3
3 4 1 2
2 3 4 1
1 2 3 4
请改正程序中的错误,使它能得出正确的结果。
注意;不要改动main 函数,不得增行或删行,也不得更改程序的结构。
试题程序;
include <stdio.h>
define M 4
/*******************************/
void fun(int a)
{int i,j,k,m;
printf("Enter 4 number: ");
for (i=0; i<M; i++) scanf ("%d", &a [i] );
printf ("\n\n The result : \n\n ");
for (i=M; i>0; i--)
{ k=a [M-1];
for (j=M-1; j>0; j--)
/**********************************/
a[j]=a[j+1];
a[0]=k;
for (m=0 ;m<M; m++ ) printf ("%d ", a [m]);
printf ("\n ");
}
}
main ()
{int a [M];
fun(a); printf("\n\n ");
}