阅读以下说明和代码,填补代码中的空缺,将解答填入答题纸的对应栏内。【说明】下面的程序利用快速排序中划分的思想在整数序列中找出第 k 小的元素(即 将元素从小到大排序后,取第 k 个元素)。对一个整数序列进行快速排序的方法是:在待排序的整数序列中取第一个数 作为基准值,然后根据基准值进行划分,从而将待排序的序列划分为不大于基准 值者(称为左子序列)和大于基准值者(称为右子序列),然后再对左子序列和 右子序列分别进行快速排序,最终得到非递减的有序序列。例如,整数序列“19, 12, 30, 11,7,53, 78, 25"的第 3 小元素为 12。整数序列“19, 12,7,30, 11, 11,7,53. 78, 25, 7"的第 3 小元素为 7。函数 partition(int a[], int low,int high)以 a[low]的值为基准,对 a[low]、 a[low+l]、…、a[high]进行划分,最后将该基准值放入 a[i] (low≤i≤high),并 使得 a[low]、a[low+l]、,..、A[i-1]都小于或等于 a[i],而 a[i+l]、a[i+2]、..、 a[high]都大于 a[i]。函 教 findkthElem(int a[],int startIdx,int endIdx,inr k) 在 a[startIdx] 、 a[startIdx+1]、...、a[endIdx]中找出第 k 小的元素。【代码】#include <stdio.h>#include <stdlib.h> Int partition(int a [],int low, int high){//对 a[low..high]进行划分,使得 a[low..i]中的元素都不大于 a[i+1..high]中的 元素。int pivot=a[low]; //pivot 表示基准元素 Int i=low,j=high;while(( 1) ){While(i<j&&a[ j]>pivot)--j; a[i]=a[ j] While(i<j&&a[i]>pivot)++i; a[ j]=a[i]}(2) ; //基准元素定位 return i;}Int findkthElem(int a[],int startIdx,int endIdx, int k){//整数序列存储在 a[startldx..endldx]中,查找并返回第 k 小的元素。if (startldx<0 ||endIdx<0 || startIdx>endIdx || k<1 ||k-l>endIdx||k-1<startIdx)Return-1; //参数错误 if(startIdx<endldx){int loc=partition(a, startIdx, endldx); ∥进行划分,确定基准元素的位置 if (loc==k-1) ∥找到第 k 小的元素return (3) ;if(k-l <loc)//继续在基准元素之前查找 return findkthElem(a, (4) ,k);else //继续在基准元素之后查找 return findkthElem(a, (5) ,k);}return a[startIdx]; }int main(){int i, k; int n;int a[] = {19, 12, 7, 30, 11, 11, 7, 53, 78, 25, 7}; n= sizeof(a)/sizeof(int) //计算序列中的元素个数 for (k=1;k<n+1;k++){for(i=0;i<n;i++){ printf(“%d/t”,a[i]);}printf(“\n”);printf(“elem %d=%d\n,k,findkthElem(a,0,n-1,k));//输出序列中第 k 小的元素}return 0;}
相似试题
-
问答题
第五题 阅读以下说明和Java代码,填补代码中的空缺,将解答填入答题纸的对应栏内。【说明】以下Java代码实现一个超市简单销售系统中的部分功能,顾客选择图书等物件 (Item)加入购物车(ShoppingCart),到收银台(Cashier)对每个购物车中的物品统计其价格进行结账。设计如图5-1所示类图。问题:5.1 【Java代码】interface Item{ public void accept(Visitor visitor); public double getPrice();}class Book (1){ private double price; public Book(double price){(2);} public void accept(Visitor visitor){ //访问本元素 (3); } public double getPrice() { return price; }}//其它物品类略 interface Visitor { public voi
-
问答题
阅读以下说明和Java程序,填补代码中的空缺,将解答填入答题纸的对应栏内。[说明]对部分乐器进行建模,其类图如下图所示,包括:乐器(Instrument)、管乐器(Wind)、打击乐器(Percussion)、弦乐器(Stringed)、木管乐器(Woodwind)、铜管乐器(Brass)。类图下面是实现上述设计的Java代码,其中音乐类(Music)使用各类乐器(Instrument)进行演奏和调音等操作。[Java代码] enum Note{/*枚举各种音调*/ MIDDLE_C,C_SHARP,B_FLAT; //其他略 } interfaceInstrument {/*接口,乐器*/ ______; //play方法接口 void adjust(); //adjust方法接口 } class Wind ______{ public voidplay(Note n) { System.out.println(Wind.play()+n); } public void adjust(){System.out
-
问答题
第六题 阅读下列说明和C++代码,填补代码中的空缺,将解答填入答题纸的对应栏内。【说明 】以下C++代码实现一个超市简单销售系统中的部分功能,顾客选择图书等物品(Item)加入购物车(ShoppingCart),到收银台(Cashier)对每个购物车中的物品统计其价格进行结账,设计如图6-1所示类图。using namespace std;class Book;class Visitor {public: virtual void visit(Book* book)=0; //其它物品的visit方法};class Item {public:virtual void accept(Visitor* visitor)=0; virtual double getPrice()=0;};class Book (1){private: double price;public: Book (double price){ //访问本元素 (2); } void accept(Vis
-
问答题
试题五(共 15 分)阅读以下说明和 Java 程序,填补代码中的空缺,将解答填入答题纸的对应 栏内。【说明】以下 Java 代码实现一个简单的聊天室系统(ChatRoomSystem),多个用 户(User)可以向聊天室( ChatRoom)发送消息,聊天室将消息展示给所有用户。 类图如图 5-1 所示。 【Java 代码】 class ChatRoom { public static void showMessage(User user, Strmg message) {System.out.println([ + user.getName() + ] : + message);} }classUser{private String name; public String getName() { return name;}public void setName(String name) { this.name = name;}public User(String name) { (1) =name;}public void sendMessage(String messa
-
问答题
阅读以下说明和Java代码,填充程序中的空缺,将解答填入答题纸的对应栏内。[说明]某应急交通控制系统(TraficControlSystem)在红灯时控制各类车辆(Vehicle)的通行,其类图如下图所示,在紧急状态下应急车辆在红灯时可通行,其余车辆按正常规则通行。下面的Java代码实现以上设计,请完善其中的空缺。[Java代码]abstract class Vehicle{public Vehicle(){ }abstract void run();};interface Emergency{ ______; ______;};class Car extends Vehicle{public Car(){ }void run(){ /*代码略*/ }};Class Truck extends Vehicle{public Truck(){ }void run() { /*代码略*/ }};class PoliceCar ______ {boolean isEmergency= false;public PoliceCar(){ }public PoliceCa
热门题库
- Q起重机械作业
- 理财规划师
- 物业管理师
- 公共营养师
- 中级安全工程师
- 养老护理员
- 动物检疫检验员
- 餐厅服务员
- 中级会计职称
- 煤矿主要负责人
- 二级注册建筑师
- 演出经纪人
- 审计师
- 证券分析师
- 茶艺师
- 报检员
- 教师资格
- 岩土工程师
- (高级)经济师
- 咨询工程师
- T电梯作业
- 高校教师资格证
- 健康管理师
- 焊工作业
- 安全员
- 理工类
- 二级造价工程师
- 企业人力资源管理师
- 注册测绘师
- 煤矿安全管理人员
- 钢筋工
- 砌筑工
- 主治类
- 卫生类
- 注册结构工程师
- 钳工
- 投资银行业务-保荐代表人
- 安全员(三类人员)
- 营养师
- 一级造价工程师
- 主要负责人
- 装饰美工
- 会计从业
- 医师类
- 消防工程师
- 法律职业资格(原司法考试)
- 房地产经纪协理
- 园艺工
- 注册会计师
- 健康管理师
- 成考(专升本)
- 电工
- N厂内专用机动车辆作业
- 驾考科一、科四
- 房地产经纪人
- 物流服务师
- 国家公务员
- 煤矿特种作业人员
- 注册电气工程师
- 省公务员-行测
- 研究生入学
- Y大型游乐设施
- BIM工程师
- 消防设施操作员
- 施工员
- 卫生招聘考试
- 焊工
- 期货从业资格
- 劳务员
- 烟花爆竹安全作业
- P气瓶作业
- 基金从业资格
- A特种设备安全管理
- 同等学力申硕
- 医药商品购销员
- 军队文职人员招聘
- 汽车发动机
- 工业机器人操作员
- 陕西省-社区专职工作人员招聘
- 电子商务师
- 社会工作者
- 眼镜验光员
- 设备监理师
- F安全阀校验
- 农业技术员
- 税务师
- 电工作业
- 建筑特殊工种
- 汽车修理工
- 导游资格证
- (初级)经济师
- 石油天然气安全作业
- 初级管理会计师
- 执业药师
- 三支一扶
- 资产评估师
- 工程测量员
- 报关员
- 银行招聘考试
- 制油工
- R压力容器作业
- 高处作业
- 冶金(有色)生产安全作业
- 土地登记代理人
- 公用设备工程师
- 资料员
- 农产品食品检验员
- 注册城乡规划师
- 税务考试题库
- 自考(医学)
- G锅炉作业
- 机械员
- 煤矿类从业人员
- 心理咨询师
- 成考(高起点)
- 金属非金属矿山安全作业
- 特种设备焊接作业
- 汽车驾驶员
- 中式面点师
- 统计师
- 中药学类
- 网络与信息安全管理员
- 形象设计师
- 育婴员
- 仓库管理员
- 软件水平考试
- 综合类
- 新安全生产法
- 招标师
- 架子工
- 美容师
- 缝纫工
- 保育员
- 一级建造师
- 事业单位公开招聘
- 国家电网招聘
- 教师招聘
- 家政服务员
- 注册消防工程师
- 护理类
- 监理工程师
- 二级建造师
- 煤矿班组长
- 危险化学品安全作业
- 轨道交通信号工
- 药学类
- 标准员
- 安全工程师
- 制冷与空调作业
- 检验类
- 初级会计职称
- 美发师
- 道路运输
- D压力管道作业
- (中级)银行从业资格
- 车工
- 公安政法干警
- 注册环保工程师
- 网络安全管理员
- 中式烹调师
- 质量工程师
- 证劵从业(新版)
- 一级注册建筑师
- (中级)经济师
- 安全管理人员
- 证劵从业(旧版)
- 铣床
- 无人机驾驶员
- 环境影响评价工程师
- 西式面点师
- 保卫管理员
- 投资项目管理师
- 工业机器人运维员
- 计算机及外部设备装配调试员
- 家畜饲养员
- 职业道德
- 材料员
- 植物检疫检验员
- 高级会计
- 证券投资顾问
- 会计从业资格考试
- 土木工程师(水利水电)
- 监管人员执法
- 制冷工
- 质量员
- 试验检测师(含助理)
- 园林绿化工
- 房地产估价师
- (初级)银行从业资格