主观

该贪心算法的时间复杂度为(5)。

试题出自试卷《软件水平考试（初级）程序员下午（应用技术）模拟试卷20》

参考答案

查看试卷详情

相关试题

阅读以下关于某订单管理系统的技术说明、部分UML类图及Java程序，将Java程序中(1)-(5)空缺处的语句填写完整。
  [说明]
某订单管理系统的部分UML类图如图3-21所示。

图3-21 某订单管理系统的部分分类图
在图3-21中，Product表示产品，ProductList表示所销售产品的列表，Order表示产品订单，OrdeItem表示产品订单中的一个条目，OrderList表示订单列表，SalesSystem提供订单管理系统的操作接口。各个类的部分属性和方法说明如表3-16所示。
可以使用类java.util.ArrayList＜E＞来实现对象的聚集关系，如图3-21所示OrderList与Order之间的聚集关系。
For...each循环提供了一种遍历对象集合的简单方法。在for...each循环中，可以指定需要遍历的对象集合及用来接收集合中每个元素的变量，其语法如下：
for(用来接收集合中元素的变量：需要遍历的对象集合)
如果要使用for-each循环来遍历对象集合，那么包含该对象集合的类必须实现接口java.util.Iterable＜T＞。
[Java程序7-1]和[Java程序7-2]分别给出了类OrderList和方法statistic的Java代码。
[Java程序7-1]
  import java.util.*.
  public class OrderList (1) {
    private ArrayList＜Order＞ orders;
    public OrderList() {
      this.orders = new ArrayList(Order)"();
    }
    public void addOrder(Order order) {
      this.orders, add (order);
    }
    public Iterator＜Order＞ iterator() {
      return (2);
   }
   public int getNumberOfOrders() {
     return this.orders, size();
   }
}
[Java 程序7-2]
import java.util.*;
public class SalesSystem {
private ProductList catalog;
private OrderList sales;
private static PrintWriter stdOut = new PrintWriter(System.out, true);
public void statistic() {
   for (Product product :(3) {
     int number = 0;
     for (Order order :(4) {
       for ( (5): order) {
         if＜product.ecluals(item.getProduct()))
           number += item.getQuantity() ;
       }
     }
     stdOut.println(product.getCode() + " " + product.getDescription() + " " + number + " " + number *product.getPrice());
   }
  }
  //其余的方法未列出
}
点击查看答案
阅读以下程序说明和C++程序，将程序段中(1)～(5)空缺处的语句填写完整。
  【说明】
以下【C++程序】实现一个简单的小型复数类MiniComplex，该复数类能进行输入、输出、复数的加法、减法、乘法和除法运算，还可以进行复数的相等比较。
【C++程序】
#ifndef H_MiniComplex
#define H_MiniComplex
#include ＜iostream＞
using namespace std;
class MiniComplex{
public:                    //重载流插入和提取运算符
    (1) ostream&operator＜＜(ostream &osObject,const MiniComplex&complex){
     osObject＜＜"("＜＜complex.realPart＜＜"+"＜＜complex.imagPart＜＜"i"＜＜")";
     return osObject;
   }
    (2) istream&operator＞＞(istream&isObject, MiniComplex&complex){
     char ch;
     isObject ＞＞complex.realPart＞＞ch＞＞complex.imagPart＞＞ch;
     return isObject;
   }
   MiniComplex(double real=0,double imag=0);               //构造函数
   MiniComplex operator+(const MiniComplex&otherComplex)const;      //重载运算符+
   MiniComplex operator-(const MiniComplex&otherComplex)const;      //重载运算符-
   MiniComplex operator*(const MiniComplex&otherComplex)const;      //重载运算符*
   MiniComplex operator/(const MiniComplex&otherComplex)const;      //重载运算符/
   bool perator==(const MiniComplex&otherComplex)const;         //重载运算符==
private :
   double (3);
   double imagPart;
};
#end if
#include "MiniComplex.h"
bool MiniComplex::operator==(const MiniComplex&otherComplex)const{
return(realPart==otherComplex.realPart&&imagPart==ortherComplex.imagPart);
}
MiniComplex::MiniComplex(double real,double imag){
realPart== real;    imagPart==imagPart;
}
MiniComplex MiniComplex::operator+(const MiniComplex&otherComplex)const{
MiniComplex temp;
temp.realPart = realPart+ortherComplex. realPart;
temp.imagPart = imagPart +ortherComplex. imagPart;
return temp;
}
(4)
{ MiniComplex temp;
temp.realPart= realPart-ortherComplex. realPart;
temp.imagPart = imagPart-ortherComplex. imagPart;
return temp;
}
MiniComplex MiniComplex::operator*(const MiniComplex&otherComplex)const{
MiniComplex temp;
temp.realPart = (realPart*ortherComplex. realPart)-(imagPart *ortherComplex.imagPart);
temp.imagPart = (realPart*ortherComplex. imagPart)+(imagPart *ortherComplex.realPart);
return temp;
}
MiniComplex MiniComplex::operator/(const MiniComplex&otherComplex)const{
MiniComplex temp;
float tt;
tt=1/(ortherComplex.realPart*ortherComplex.realPart+ortherComplex.imagPart *ortherComplex. imagPart);
temp.realPart=((realPart*ortherComplex,  realPart)+(imagPart  *ortherComplex. imagPart))*tt;
temp.imagPart =((imagPart  *ortherComplex.  realPart)-(realPart*ortherComplex. imagPart))*tt;
return temp;
}
#include ＜iostream＞
#include ＜MiniComplex.h＞
using namespace std;
int main(){
MiniComplex numl(23, 34),num2(56, 35);
cout＜＜"Initial Value of num1="＜＜num1＜＜"\n Initial Value of num2="＜＜num2＜＜end1;
cout＜＜num1＜＜"+"＜＜num2＜＜"="＜＜num1+num2＜＜end1;         //使用重载的加号运算符
cout＜＜num1＜＜"-"＜＜num2＜＜"="＜＜num
点击查看答案
若要在图4-16窗口内新增一个[帮助]按钮，单击该按钮就会弹出一个帮助对话框(另一名为frm002的窗体)，用户必须在其中做出响应，程序才能继续运行。请将以下该命令按钮的单击事件过程中的程序代码填写完整。
Private Sub CmdHelp_C1ick()
(10)
End Sub
点击查看答案
阅读以下应用说明及Visual Basic程序，根据要求回答问题1至问题2。
[说明]
某Visual Basic应用程序用于监测某种锅炉设备内液面高度(0～50cm)，其运行窗口界面如图4-16所示。

图4-16 某锅炉设备液面高度显示界面
在图4-16中，设计了一个高度计(矩形形状shpMeter)及其中指示当前液面高度的水银柱(矩形形状shpT)，文字标签标记了液面高度的刻度；另有一个图片框picCurve，用于动态描述检测到的液面高度曲线(用户见到的曲线与水银柱等高变化)；[开始](CmdStart)按钮用于启动液面高度检测，命令按钮“暂停”(CmdStop)用于暂停液面高度检测。
液面高度计形状控件shpMeter是固定的，其属性FillsStyle默认为透明。矩形形状shpT(水银柱)的 Visible属性初始设置为不可见，属性Filltype设置为Solid(实心)，FillColor设置为红色；图片框picCurve的属性AutoRedraw设置为True；程序设计过程中，创建了一个定时器TimT，属性Enabled初始设置为 False(不可用)，属性Interval(定时间隔)的值应设置为(1)。
为模拟锅炉设备液面高度的检测，程序中利用了(0，1)之间均匀分布的伪随机数获得[0，50]之间的随机液面高度WH。为便于在图片框picCurve中绘制曲线，程序中对该图片框建立了如下坐标系统：图片框的左上角定义为原点(0，0)，水平向右方向为X轴，垂直向上方向为Y轴，右下角坐标为(50.200)。为了便于观察记录的液面高度值，图片框中从上到下创建了7条水平虚线Ls(i)，i=0，1…6，并在程序中按等间隔排列进行位置设置。应用程序中每隔3秒算出曲线点(x, y)，其中x=O，1，2……，再用直线段连接各相邻曲线点形成液面高度曲线。
[Visual Basic程序代码]
Dim (2) AS Integer        '试题全局变量
Private Sub CmdStart_Click()
   TimT.Enabled =(3)
   ShpT.Visible = True
End Sub
Private Sub CmdStop_Click()
   TimT.Enabled = False
End Sub
Private Sub Form_Load( )
   Dim i,S As Integer
   PicCurve.Scale (0,0)-(50,200)   '设置图片框坐标系：左上角-右下角
   S = 25              'H等于图片框高度的1/8
   For i = 0 To 6          '设置7条水平线Ls(i)的位置
     Ls(i).X1 = 0         'Ls(i)起点横坐标
     Ls(i).Y1 =(4)       'Ls(i)起点纵坐标
     Ls(i).X2 = 50         'Ls(i)终点横坐标
     Ls(i).Y2 = Ls(i).Y1      'Ls(i)终点纵坐标
     Ls(i).BorderColor = &H00FCFCFC  '设置水平线颜色
    (5)
   x = 0               '设置曲线坐标初值
End Sub
Private Sub timT_Timer ( )
   Dim WH, H As Integer        'WH为实时液面高度，H为图片框中液面高度点显示高度
   WH = Int(Rnd * 51)         '随机模拟产生锅炉内液面高度(0～50 cm)
   H = ShpMeter.Height * (6)     '算出水银柱的高度
   ShpT.Top =(7)          '设置水银柱顶部位置
   ShpT.Height = H          '设置水银柱的高度
   '绘制液面高度曲线
   y =(8)             '算出曲上当前点的纵坐标
    If x ＝ 51 Then         '当超出图片框时
     PicCurve. Cls        '清框图片框内以前画的曲线
      (9)
   ElseIf x ＞ 0 Then        '除左边点外
     PicCurve. Line (x-1,Lasty)-(x,y),vbRed  '由前1点到当前点画红色线段
   End If
   x = x + 1            '准备下一点坐标
   Lasty = y            '保存当前坐标供下次使用
End Sub
请根据[说明]和图4-16所示的显示结果，将[说明]中(1)空缺处的内容和[Visual
点击查看答案
请从以下选项中选择相应的判断逻辑填写【算法4-2】中的“判断条件1”至“判断条件3”。注意，如“判断条件2”的逻辑判断结果为假，则无须对“判断条件3”进行判断。判断条件1：(8) 判断条件2：(9) 判断条件3：(10) 【供选择的答案】A．栈顶元素表示的是与当前字符匹配的左括号
B．栈顶元素表示的是与当前字符匹配的右括号
C．字符是左括号
D．字符是右括号
E．栈不空F．栈空G．字符是括号
点击查看答案
阅读以下算法说明和C程序，根据要求回答问题1和问题2。
【说明】
【算法4-1】的功能是用来检查文本文件中的圆括号是否匹配。若文件中存在圆括号而没有对应的左括号或者右括号，则给出相应的提示信息，如图1-18所示。
在【算法4-1】中，slack为一整数栈。算法中各函数的说明如表1-11所示。
【算法4-1】
将栈stack置空，置EOF为false
Ch＜-nextch()；
while(not EOF)
k←kind(ch)；
if (k ==(1)　) {
push(　(2)　)；
push(　(3)　)；}
else if( k ==(4)　)
if(not empty()){
pop()；
pop()；)
else{
显示错误信息(缺少对应左括号或右括号)：
显示行号row：显示列号col：)
End if
End if
Ch＜-nextch()；
end while
if(not empty())
显示错误信息(缺少对应左括号或右括号)：
While(not empty()){
row＜-pop()；
col＜-pop()：
显示行号row：显示列号col；)
End while
End if
为了识别更多种类的括号，对【算法4-1】加以改进后得到【算法4-2】。【算法4-2】能够识别圆括号、方括号和花括号(不同类型的括号不能互相匹配)。改进后，函数kind(charch)的参数及其对应的返回值如表1-12所示。
【算法4-2】
将栈stack置空，置EOF为false
Ch＜-nextch()；
while(not EOF){
k＜- kind(ch)；
if(k ＞ 0)
if(判断条件1){
   push( (5) )；
     push( (6) )；
     push( (7) )；}
   else if(判断条件2 and判断条件3){
       pop()；
       pop()；
       pop()；}
     else {
       显示错误信息(缺少对应左括号或右括号)；
       显示行号row；显示列号col；)
     end if
   end if
   ch ＜- nextch()；)
end while
if(not empty()){
显示错误信息(缺少对应左括号或右括号)；
While(not empty()){
   Pop()；
   row ＜- pop()：
   col ＜- pop()；
   显示行号row；显示列号col；))
end while
end if
请将【算法4-1】和【算法4-2】中，(1)～(7)空缺处的内容补充完整。
点击查看答案
该贪心算法的时间复杂度为(5)。
点击查看答案
阅读以下应用程序说明和C程序，将C程序段中(1)～(7)空缺处的语句填写完整。
  【说明】
以下【C程序】的功能是从文件text_01.ini中读入一篇英文短文，统计该短文中不同单词和它的出现次数，并按词典编辑顺序将单词及它的出现次数输出到文件word_xml.out中。
该C程序采用一棵有序二叉树存储这些单词及其出现的次数，一边读入一边建立。然后中序遍历该二叉树，将遍历经过的二叉树上节点的内容输出。
程序中的外部函数
int getword(FILE *fpt，char *word)
从与fpt所对应的文件中读取单词置入word，并返回1；若已无单词可读，即到文件尾部时，则函数返回0。
【C程序】
#include ＜stdio.h＞
#include ＜malloc.h＞
#include ＜ctype.h＞
#include ＜string.h＞
#define INF "TEXT_01.INI"
#define OUTF "WORD_XML.OUT"
typedef struct treenode {
char *word;
int count;
struct treenode *left, *right;
} BNODE;
int getword(FILE *fpt,char *word);
void binary tree(BNODE **t,char *word)
{ BNODE *ptr, *p;
int cmpres;
p = NULL;
  (1);
while (ptr) {             /*寻找插入位置*/
   cmpres = strcmp(word, (2));   /* 保存当前比较结果*/
   if (!cmpres) {
      (3)
     return;
   }
   else {
      (4);
     ptr = cmpres ＞ 0 ? ptr-＞right : ptr-＞left;
   }
}
ptr = (BNODE *)malloc(sizeof(BNODE));
ptr-＞right = ptr-＞left = NULL;
ptr-＞word = (char *)malloc(strlen(word)+1);
strcpy(ptr-＞word,word);
ptr-＞count = 1;
if (p == NULL)
    (5) ;
else
   if (cmpres ＞ 0)
     p-＞right = ptr;
   else
     p-＞left = ptr; }
}
void midorder(FILE *fpt, BNODE *t)
{ if ((6))
   return;
midorder(fpt , t-＞left);
fprintf(fpt , " %s %d\n " , t-＞word , t-＞count);
midorder(fpt , t-＞right); }
void main()
{ FILE *fpt;
char word[40];
BNODE *root = NULL;
if ((fpt = fopen(INF , "r")) == NULL) {
   printf("Can't open file %s\n",INF);
   return;
}
while (getword(fpt,word) == 1)
   binary_tree( (7) );
fclose(fpt);
    fopen(OUTF,"w");
midorder(fpt, root);
fclose(fpt);
}
点击查看答案
阅读以下技术说明和问题模型图，根据要求回答问题1和问题2。
【说明】
某大学城图书馆需要在无线阅览厅的某些位置上放置无线接入点AP(Access Poin)。假设每个无线AP覆盖范围的半径是6米，因此必须使得每台笔记本电脑上的无线网卡到某个无线AP的直线距离不超过6米。为了简化问题，假设所有无线网卡在同一直线上，并且无线AP沿该直线放置。该问题可以建模为如图1-16所示，其中直线表示无线网卡所在的直线，实心正方形表示无线网卡。现利用贪心策略实现用尽可能少的无线AP覆盖所有的无线网卡。

实现贪心算法的流程如图1-17所示。其中，①d[i](1≤i≤N)表示第i张无线网卡到通道A端的距离，N表示无线网卡的总数，无线网卡的编号按照无线网卡到通道A端的距离从小到大进行编号；②s[k]表示第k(k≥1)个无线AP到通道A端的距离。算法结束后k的值为无线AP的总数。
请填补图1-17流程图中(1)-(4)空缺处的内容。
点击查看答案
阅读以下说明和流程图，将应填入(n)处的字句写在对应栏内。
[说明]
下面的流程图实现了正整数序列{K(1),K(2),…,K(n)}的重排，得到的新序列中，比K(1)小的数都在K(1)的左侧，比K(1)大的数都在K(1)的右侧。以n=6为例，序列{12，2，9，13，21，8}的重排过程为：
            {12,2,9,13,21,8}
           →{2,12,9,13,21,8}
           →{9,2,12,13,21,8}
           →{8,9,2,12,13,21}
[流程图]
点击查看答案