程序员水平考试辅导.ppt

程序员水平考试辅导 数据结构 程序设计 操作系统 程序员考试简介 名称 计算机技术与软件专业技术资格 水平 考试主办单位 是国家人力资源和社会保障部 工业和信息化部联合组织实施的国家级考试 目的 科学 公正地对全国计算机与软件专业技术人员进行职业资格和专业技术资格认定 专业技术水平测试 参加计算机软件资格考试并取得相应级别的资格证书 是各用人单位聘用计算机技术与软件专业工程师系列职务的前提 证书 由中华人民共和国工业信息化部及中华人民共和国人力资源和社会保障部用印的计算机技术与软件专业技术资格 水平 证书 考试安排 考试时间 上半年考试时间为5月底 第三个周六 周日 下半年考试时间为11月中旬 第二个周六 周日 考试形式 上午 150分钟 满分75分 单项选择 下午 150分钟 满分75分 程序填空 证书样本 程序员考试内容 上午题 基本包含所有的计算机基础 75分 计算机操作微机原理多媒体软件工程数据结构操作系统 编译原理面向对象的程序设计计算机网络数据库原理计算机英语下午题 75分 流程图 15分 C语言 30分 数据结构 15分 Java或C 15分 本课程目的 针对程序员考试 起到引导和抛砖引玉的作用 课程安排 C 数据结构C语言基本程序数组 字符串流程图链表队列 栈顺序表矩阵二叉树排序和查找图Java 上午题 操作系统程序设计软件工程数据库原理 学习方法 针对性练习 近5年的程序员考试真题总结 类似问题或知识点的归纳总结 考核方式 平时 30 期末 70 C语言基本程序 语法函数数组字符串 函数 函数的实际参数函数的形式参数函数的返回值函数的调用 数组 类型相同的数据的集合数组名是一个常量 其值是这个空间的首地址数组做函数参数时传递的是数组的起始地址数组和指针 2009年下试题三 函数1 2009年下试题二 2009年上试题二 2008年下试题二 2009年上试题二 C语言常用整型 int 或长整型 long长以的满整足型表 示例及如运 算要求 而在某些情况下 需来要说表明示需及要运处算理的的整整数数比较在大 一般即情使况采下可用一维数组来表示一个整数 假设要处理的大整数是正数 将其从低位到高位每四位一组进行分组 最后一组可能不足4位 每组作为一个整数存入数组 特别引入 1表示分组结束 voidadd large number intA intB intC inti cf intt p cf for inti 0 A i 1 标志 和数 的分组结束 2009年下 函数Smove intA intn 的功能是将数组中所有的奇数都放到所有偶数之前 其过程为 设置数组元素下标索引i 初值为0 和j 初值为n 1 从数组的两端开始检查元素的奇偶性 若A i A j 都是奇数 则从前往后找出一个偶数 再与A j 进行交换 若A i A j 都是偶数 则从后往前找出一个奇数 再与A i 进行交换 若A i 是偶数而A j 是奇数 则交换两者 直到将所有的奇数都排在所有偶数之前为止 voidSmove intA intn inttemp i 0 j n 1 if n 2 return while i j if A i 2 1 else while 2009年下 函数test f1 intm intn 对整数m n进行某种运算后返回一个整数值 inttest f1 intm intn intk k m n m n for k m 0 k n 0 k returnk 问题1 5分 1 请写出发生函数调用test f1 9 6 时 函数的返回值 2 请说明函数test f1的功能 2008年下 下面C程序代码的功能是 对于输入的一个正整数n 100 n 1000 先判断其是否是回文数 正读反读都一样的数 若不是 则将n与其反序数相加 再判断得到的和数是否为回文数 若还不是 再将该和数与其反序数相加并进行判断 依此类推 直到得到一个回文数为止 例如 278不是回文数 其反序数为872 相加后得到的1150还不是回文数 再将1150与其反序数511相加 得到的1661是回文数 函数intisPalm longm 的功能是 将正整数m的各位数字取出存入数组中 然后判断其是否为回文数 若m是回文数则返回1 否则返回0 intmain longn a t printf inputapositiveinteger scanf ld intisPalm longm 判断m是否为回文数 inti 0 k 0 charstr 32 while m 0 从个位数开始逐个取出m的各位数字并存入字符数组str str k 1 0 m m 10 for i 0 i k 2 i 判断str中的k个数字字符序列是否是回文 if str i str 2 return0 return1 字符串 字符数组存储字符串 末尾自动加 0 要会利用 0 字符串与指针字符串的主要函数 strlen strcpy strcmp strcat 2009年下试题三 函数2 2009年下试题三 函数3 2008年上试题二 2010年上试题三 2009下 设在某C系统中为每个字符分配1个字节 为每个指针分配4个字节 sizeof x 计算为x分配的字节数 函数test f2 用于测试并输出该C系统为某些数据分配的字节数 voidtest f2 charstr NewWorld char p str chari 0 void ptr malloc 50 printf d t sizeof str printf d n sizeof p printf d t sizeof i printf d n sizeof ptr 问题2 4分 请写出函数test f2 的运行结果 2009下 函数test f3 chars 的功能是 将给定字符串s中的所有空格字符删除后形成的串保存在字符数组tstr中 串s的内容不变 并返回结果串的首地址 char test f3 constchars char tstr char malloc 50 unsignedinti k 0 for i 0 i strlen s i if s i tstr k s i returntstr 问题3 6分 函数test f3 对返回值的处理有缺陷 请指出该缺陷并说明修改方法 字符串类 字符串的简单应用2003年判一个字符是否在字符串中2004 5判回文 根据分隔字符分割子串2005 5拆分整数2005 11删除前导和尾部空格 2004 118进制求补 2001 函数strcmp 是比较两个字符串s和t的大小 若st 函数返回正数 函数1 1 intstrcmp char s char t while s 2002 试题二函数strcat char s1 char s2 是将字符串s2连接在字符串s1之后 构成一个首指针为s1的字符串 voidstrcat char sl char s2 while s1 0 1 for 2 s1 s2 2005 5 函数2 2说明 函数longfun2 char str 的功能是 自左至右顺序取出非空字符串str中的数字字符形成一个十进制整数 最多8位 例如 若字符串str的值为 f3g8d5 ji2e3p12fkp 则函数返回值为3852312 longfun2 char str inti 0 longk 0 char p str while p 0 2004 5 函数palindrome chars 的功能是 判断字符串s是否为回文字符串 若是 则返回0 否则返回 1 若一个字符串顺读和倒读都一样时 称该字符串是回文字符串 例如 LEVEL 是回文字符串 而 LEVAL 不是 intpalindrome chars char pi pj pi s pj s strlen s 1 while pi pj 2004 5 函数2 2说明 函数f char str chardel 的功能是 将非空字符串str分割成若干个子字符串并输出 del表示分割时的标志字符 例如若str的值为 33123333435 del的值为 3 调用此函数后 将输出三个子字符串 分别为 12 4 和 5 voidf char str chardel inti j len len strlen str i 0 While i len While 3 i 忽略连续的标志字符 寻找从str i 开始直到标志字符出现的一个子字符串 j i 1 while str j del 2003 函数char strrchr char s charch 的功能是在字符串s中寻找字符ch若ch出现在字符串s中 则返回最后一次出现时的位置 否则返回NULL 函数2 1 char strrchr char s charch char p p 1 p指向字符串s的结束标志 while p s if 2 returnp returnNULL C语言基本程序 常见错误 变量的定义变量的初始化Scanf 指针逻辑错 近几年改错题 2010年上 2010年下 2009年上 2009年下 2008年上 2008年下 链表 链表 插入 删除 查找 逆序有序链表 单循环链表 双向循环链表 查找沿着指针顺序比较的过程插入先查找 再修改指针 删除先查找 再修改指针 逆序头插法可以实现逆序 有序表在有序表中插入建立有序表单循环链表头指针的指向双向循环链表 2007年上 函数sort NODE head 的功能是 用冒泡排序法对单链表中的元素进行非递减排序 对于两个相邻结点中的元素 若较小的元素在前面 则交换这两个结点中的元素值 其中 head指向链表的头结点 排序时 为了避免每趟都扫描到链表的尾结点 设置一个指针endptr 使其指向下趟扫描需要到达的最后一个结点 例如 对于以下的链表进行一趟冒泡排序后 得到下面的链表 endptr endptr head head 链表的结点类型定义如下 typedefstructNode intdata structNode next NODE voidsort NODE head NODE ptr preptr endptr inttempdata ptr head next while 1 查找表尾结点 ptr ptr next endptr ptr 令endptr指向表尾结点 ptr 2 while ptr endptr while 3 if ptr data ptr next data tempdata data 交换相邻结点的数据 ptr data ptr next data ptr next data tempdata preptr 4 ptr ptr next endptr 5 ptr head next 2007年上 已知包含头结点 不存储元素 的单链表的元素已经按照非递减方式排序 函数compress NODE head 的功能是去掉其中重复的元素 使得链表中的元素互不相同 处理过程中 当元素重复出现时 保留元素第一次出现所在的结点 图4 1 a b 是经函数compress 处理前后的链表结构示例图 链表的结点类型定义如下 typedefstructNode intdata structNode next NODE head head voidcompress NODE head NODE ptr q ptr 1 取得第一个元素结点的指针 while 2 endofwhile endofcompress 2004 11 函数movetoend LinkedListLa inti 的功能是 将线性表A的第i个元素移到表尾 若移动成功 则返回0 否则返回 1 线性表A采用带头结点的单链表表示 La为表A的头指针 如下图所示 链表结点的类型定义为 typedefstructnode intkey structnode next LNode LinkedList intmovetoend LinkedListLa inti LinkedListp q prep intk 1 p La next prep La while 1 查找第i个元素并使指针p指向该结点 prep p p p next k if p k i return 1 if 2 第i个元素结点已经是表尾结点 则无需移动 return0 q p while 3 q q next 查找表尾并使q指向表尾结点 4 p next p next NULL 5 return0 2006年11月 某班级有N名学生 他们可根据自己的情况选修名称和数量不尽相同的课程 设N等于6 学生信息 所选课程及成绩用链表结构存储 如图5 1所示 程序中相应的类型定义如下 defineN6structnode charcname 5 课程名 intgrade 成绩 structnode next 指针 指示某学生选修的下一门课程及成绩 structstudent charxh 5 学号 charname 20 姓名 structnode link 指针 指示出选修的课程及成绩链表 stud info N stud info 为一个全局数组 函数func charkc int num 的功能是统计选修了课程名为kc的学生的人数 并返回该课程的平均成绩 若无人选修该课程 则平均成绩为0 参数num带回选修课程kc的学生人数 doublefunc charkc int num inti count 0 sum 0 count用于记录选修课程名为kc的学生的人数 doubleavg 0 0 structnode p for i 0 inext while 4 if 5 avg double sum count 计算平均成绩 returnavg func 2000 设链表结点的类型为typedefstructelem intval structelem next intNode 函数merge intNode a intNode b 是将两个升序链表a和b合并成一个升序链表 intNode merge intNode a intNode b intNode h a p q while b for p h p 栈和队列 栈的基本操作出栈入栈栈的应用括号匹配进制转换表达式求值队列的基本操作 先进后出 先进先出 2004 5 函数MultibaseOutput longn intB 的功能是 将一个无符号十进制整数n转换成B 2 B 16 进制整数并输出 该函数先将转换过程中得到的各位数字入栈 转换结束后再把B进制数从栈中输出 有关栈操作的诸函数功能见相应函数中的注释 C代码中的符号常量及栈的类型定义如下 defineMAXSIZE32typedifstruct int elem 栈的存储区 intmax 栈的容量 即栈中最多能存放的元素个数 inttop 栈顶指针 Stack intInitStack Stack S intn 创建容量为n的空栈 S elem int malloc n sizeof int if S elem NULL return 1 S max n 1 0 return0 intPush Stack S intitem 将整数item压入栈顶 if S top S max printf Stackisfull n return 1 2 item return0 intStackEmpty Stack S return S top 1 0 判断栈是否为空 intPop Stack S 栈顶元素出栈 if S top printf Popanemptystack n return 1 return 3 voidMultibaseOutput longn intB intm StackS if InitStack 2006年5月 函数boolDel elem STACK S charpara ch 的功能是 删除栈 s中与para ch之值相等且最接近栈顶的元素 字符 若栈中不存在该元素 则函数返回FALSE 否则返回TRUE 其中 STACK是栈的类型名 函数Del lem实现上述功能的方法是利用栈的基本操作 先将栈 s中所有比parlch之值更接近栈顶的元素暂时存放在临时工作栈s bak中 使得与para ch之值相等的元素成为栈顶元素 此时执行出栈操作 即从栈中删除与para ch之值相等的元素 最后再将s bak中的元素依次存回栈 s 在函数Del elem中必须使用栈的基本操作进行栈上的运算 实现栈的基本操作的 函数原型说明如下 voidInitStack STACK S 初始化栈 voidPush STACK S chare 将一个字符压栈 栈中元素数目增1 voidPop STACK S 栈顶元素出栈 栈中元素数目减1 charTop STACKS 返回非空栈的栈顶元素值 栈中元素数目不变 boolIsEmpty STACKS 若S是空栈 则返回TRUE 否则返回FALSE bool类型定义如下 typedefenum FALSE 0 TRUE 1 bool boolDel elem STACK S charpara ch STACKs bak 定义临时工作栈s bak charCh booltag FALSE 1 初始化临时工作栈s bak 将栈 s中所有比para ch更接近栈顶的元素暂时存放在临时工作栈s bsk中 while IsEmpty s ch 2 取栈顶元素 Pop S if ch para ch tag TRUE break 3 将暂存于1临时工作栈s bak中的元素存回栈 s while 4 ch Top s bak 5 Push s ch returntag 2008年上半年 计算机在处理算术表达式时 首先将其转换为后缀表达式 例如 表达式 46 5 120 37 的后缀表达式形式为 46512037 计算后缀表达式时 从左至右扫描后缀表达式 若遇到运算对象 则压入栈中 遇到运算符 则从栈中弹出相关运算对象进行计算 并将运算结果压入栈中 重复以上过程 直到后缀表达式扫描结束 例如 后缀表达式 46512037 的计算过程为 a 依次将46 5 120 37压入栈中 b 遇到 取出37 120 计算120 37 得83 将其压入栈中 c 遇到 取出83 5 计算5 83 得415 将其压入栈中 d 遇到 取出415 46 计算46 415 得461 将其压入栈中 e 表达式结束 则计算过程完成 函数computing中所用栈的基本操作的函数原型说明如下 voidInitStack STACK s 初始化栈 voidPush STACK s inte 将一个整数压栈 栈中元素数目增1 voidPop STACK s 栈顶元素出栈 栈中元素数目减1 intTop STACKs 返回非空栈的栈顶元素值 栈中元素数目不变 intIsEmpty STACKs 若s是空栈 则返回1否则返回0 intcomputing charexpr int result STACKs inttnum a b char ptr InitStack else if isdigit ptr 当前字符是数字 则将该数字开始的数字串转换为数值 tnum 2 while ptr 0 switch ptr case Push 文件操作 文件类型 字节流或字符流文本文件二进制文件文件指针FILE fp 文件打开fp fopen 文件名 使用文件方式 文件关闭fclose 文件指针 文件读写intfgetc FILE fp 从fp所指的文件中取得下一个字符 返回所得到字符 出错返回EOF intfputc charch FILE fp 将字符ch输出到fp所指文件 成功返回该字符 否则返回非0 1 char fgets char buf intn FILE fp 从fp指向的文件读取长度为n 1的字符串 存入起始地址为buf的空间 返回地址buf 否则返回NULLintfputs char str FILE fp 将str指向的字符串输出到fp指向的文件中 成功返回0 否则返回非0 fscanf 文件指针 格式字符串 输入列表 fprintf 文件指针 格式字符串 输出列表 intfread void buffer intsize intcount FILE fbin 从二进制文件流fbin中读取count块长度为size字节的数据块到buffer指向的存储区 返回值为实际读取的数据块数 intfwrite void buffer intsize intcount FILE fbin 各参数和返回值的意义与fread相同 但对文件进行写操作 2007年下 某电信公司记录了每个用户的详细通话情况 每次通话数据记录在一行 现将某用户某月的通话数据存入一个文本文件 dial txt 其数据格式如下 拨入或拨出标记通话开始时间通话结束时间对方号码注1 数据字段以一个空格作为分隔符 注2 拨入和拨出标记均为小写字母 拨入标记为 i 表示其他用户呼叫本机 本机用户不需付费 拨出标记为 o 表示本机呼叫其他用户 此时本机用户需要付费 注3 通话开始和结束时间的格式均为 HH MM SS 其中HH表示小时 取值00 23 MM表示分钟 取值00 59 SS表示秒 取值00 59 从通话开始到结束这段时间称为通话时间 假定每次通话时间以秒为单位 最短为1秒 最长不超过24小时 注4 跨月的通话记录计入下个月的通话数据文件 例如 o23 01 1200 12 15 表示本次通话是本机呼叫其他用户 时间从23时01分12秒至次日的0时12分15秒 通话时间为71分03秒 下面程序的功能是计算并输出该用户本月电话费 单位 元 通话计费规则为 1 月通话费按每次通话费累加 2 每次的通话费按通话时间每分钟0 08元计算 不足1分钟时按1分钟计费 对于每次的拨出通话 程序中先分别计算出通话开始和结束时间相对于当日0点0分0秒的时间长度 以秒为单位 然后算出本次通话时间和通话费 例如 若输入文件dial txt的数据如下所示 则输出fee 7 44 o14 05 2314 11 2582346789i15 10 0016 01 1513890000000o10 53 1211 07 0563000123o23 01 1200 12 1513356789001 includeFILE fin intmain charstr 80 inth1 h2 m1 m2 s1 s2 longt start t end interval intc doublefee 0 fin fopen dial txt r if fin return 1 while feof fin if fgets str 80 fin break if 1 continue h1 str 2 48 10 str 3 48 m1 str 5 48 10 str 6 48 s1 str 8 48 10 str 9 48 h2 str 11 48 10 str 12 48 m2 str 14 48 10 str 15 48 s2 str 17 48 10 str 18 48 t start h1 60 60 m1 60 s1 通话开始时间 t end h2 60 60 m2 60 s2 通话结束时间 if 2 若通话开始和结束时间跨日 interval 3 t start t end elseinterval t end t start c 4 计算完整分钟数表示的通话时间 if interval 60 5 fee c 0 08 fclose fin printf fee 2lf n fee return0 流程图 2007年下半年 试题三 2008年下半年 试题一 2009年下半年 二叉树 二叉排序树建立查找插入删除遍历哈夫曼树 2003 函数BTREE SortTreeSearch BTREE tree intd 采用非递归方法 在二叉排序树 二叉查找树 中查找键值为d的结点 若找到 则返回键值所在结点的指针 否则返回NULL 二叉查找树的结点类型为 typedefstructnode intdata 结点的键值 structnode left structnode right BTREE BTREE SortTreeSearch BTREE tree intd BTREE ptr tree while ptr NULL 2005 5 一棵非空二叉树中 最左下 结点定义为 若树根的左子树为空 则树根为 最左下 结点 否则 从树根的左子树根出发 沿结点的左孩子分支向下查找 直到某个结点不存在左孩子时为止 该结点即为此二叉树的 最左下 结点 例如 下图所示的以A为根的二叉树的 最左下 结点为D 以C为根的子二叉树中的 最左下 结点为C 函数BSTreeFind Del BSTreeroot 的功能是 若root指向一棵二叉树的根结点 则找出该结点的右子树上的 最左下 结点 p 并从树中删除以 p为根的子树 函数返回被删除子树的根结点指针 若该树根的右子树上不存在 最左下 结点 则返回空指针 BSTreeFind Del BSTreeroot BSTreep pre If root returnNULL root指向的二叉树为空树 1 令p指向根结点的右子树 if p returnNULL 2 设置pre的初值 while p lch 查找 最左下 结点 pre p p 3 if 4 root root的右子树根为 最左下 结点 pre rch NULL else 5 NULL 删除以 最左下 结点为根的子树 returnp 2005 11 二叉排序树或者是一棵空树 或者是具有如下性质的二叉树 若它的左子树非空 则左子树上所有结点的值小于根结点的值 若它的右子树非空 则右子树上所有结点的值均大于根结点的值 左 右子树本身就是两棵二叉排序树 函数insert BST char dtr 的功能是 对给定的字符序列按照ASCII码值大小关系创建二叉排序树 并返回指向树根结点的指针 序列中重复出现的字符只建一个结点 并由结点中的Count域对字符的重复次数进行计数 二叉排序树的链表结点类型定义如下 typedefstructBSTNode charElem 结点的字符数据 intCount 记录当前字符在序列中重复出现的次数 structBSTNode Lch Rch 结点的左 右指针 BiTree BiTreeinsert BST char str BiTreeroot parent p char 1 变量定义及初始化 root BiTree malloc sizeof structBSTNode if root s 0 returnNULL root Lch root Rch NULL root Count 1 root Elem s for s 0 s 2 parent NULL while p p从树根结点出发查找当前字符 s所在结点 parent p if s p Elem 若树中已存在当前字符结点 则当前字符的计数值加1 p Count break else 否则根据字符 s与结点 p中字符的关系 进入 p的左子树或右子树 if s p Elem p p Rch elsep p Lch while if 3 若树中不存在字符值为 s的结点 则申请结点并插入树中 p BiTree malloc sizeof structBSTNode if p returnNULL p Lch p Rch NULL p Count 1 p Elem s 根据当前字符与其父结点字符值的大小关系 将新结点作为左子树或右子树插入 if p Elem parent Elem 4 p else 5 p for returnroot 2009年上 二叉查找树又称为二叉排序树 它或者是一棵空树 或者是具有如下性质的二叉树 若它的左子树非空 则其左子树上所有结点的键值均小于根结点的键值 若它的右子树非空 则其右子树上所有结点的键值均大于根结点的键值 左 右子树本身就是二叉查找树 设二叉查找树采用二叉链表存储结构 链表结点类型定义如下 typedefstructBiTnode intkey value 结点的键值 为非负整数 structBiTnode left right 结点的左 右子树指针 BSTree 函数find key root key 的功能是用递归方式在给定的二叉查找树 root指向根结点 中查找键值为key的结点并返回结点的指针 若找不到 则返回空指针 BSTreefind key BSTreeroot intkey if 1 returnNULL elseif key root key value return 2 elseif keykey value return 3 elsereturn 4 问题 若某二叉查找树中有n个结点 则查找一个给定关键字时 需要比较的结点个数取决于 5 2008年下 已知某二叉树的非叶子结点都有两个孩子结点 现将该二叉树存储在结构数组Ht中 结点结构及数组Ht的定义如下 defineMAXLEAFNUM30structnode charch 当前结点表示的字符 对于非叶子结点 此域不用 char pstr 当前结点的编码指针 非叶子结点不用 intparent 当前结点的父结点 为0时表示无父结点 intlchild rchild 当前结点的左 右孩子结点 为0时表示无对应的孩子结点 structnodeHt 2 MAXLEAFNUM 数组元素Ht 0 不用 二叉树示意图下标chparentlchildrchild1a5002b5003c7004d600561267547036 StatusLeafCode structnodeHt intn intpc pf inti start chartstr 31 0 for i 1 1 i 对所有叶子结点求编码 i表示叶结点在HT数组中的下标 start 29 pc i pf Ht i parent while pf 2 没有到达树根时 继续求编码if 3 lchild pc tstr start 0 elsetstr start 1 pc 4 pf Ht pf parent endofwhile Ht i pstr char malloc 31 start if Ht i pstr returnERROR strcpy Ht i pstr 5 endoffor returnOK endofLeafCode 二维数组和矩阵 存储结构 一般顺序存储基本操作 存取特殊矩阵 压缩存储稀疏矩阵 压缩存储 2006年11月 假设以二维数组G 1 m 1 n 表示一幅图像各像素的颜色 则G i j 表示区域中点 i j 处的颜色 颜色值为0到k的整数 下面的算法将指定点 i0 j0 所在的同色邻接区域的颜色置换为给定的颜色值 约定所有与点 i0 j0 同色的上 下 左 右可连通的点组成同色邻接区域 例如 一幅8 9像素的图像如图1 1所示 设用户指定点 3 5 其颜色值为0 此时其上方 2 5 下方 4 5 右方 3 6 邻接点的颜色值都为0 因此这些点属于点 3 5 所在的同色邻接区域 再从上 下 左 右四个方向进行扩展 可得出该同色邻接区域的其他点 见图1 1中的阴影部分 将上述同色区域的颜色替换为颜色值7所得的新图像如图1 2所示 算法 输入 矩阵G 点的坐标 i0 j0 新颜色值newcolor 输出 点 i0 j0 所在同色邻接区域的颜色置换为newcolor之后的矩阵G 算法步骤 为规范算法 规定该算法只在第七步后结束 第一步 若点 i0 j0 的颜色值与新颜色值newcolor相同 则 1 第二步 点 i0 j0 的颜色值 oldcolor 创建栈S 并将点坐标 i0 j0 入栈 第三步 若 2 则转第七步 第四步 栈顶元素出栈 x y 并 3 第五步 1 若点 x y 1 在图像中且G x y 1 等于oldcolor 则 x y 1 入栈S 2 若点 x y 1 在图像中且G x y 1 等于oldcolor 则 x y 1 入栈S 3 若点 x 1 y 在图像中且G x 1 y 等于oldcolor 则 x 1 y 入栈S 4 若点 x 1 y 在图像中且G x 1 y 等于oldcolor 则 x 1 y 入栈S 第六步 转 4 第七步 算法结束 2006 5 信息处理过程中经常需要将图片或汉字点阵做旋转处理 一个矩阵以顺时针方向旋转90 后可以形成另一个矩阵 如下图所示 流程图1 1描述了对n n矩阵的某种处理 流程图1 2是将矩阵A顺时针旋转90 形成矩阵B的具体算法 1 B j n i 1 2 C n i 1 n j 1 3 A n j 1 i 2006年11月 矩阵转置cpot 0 0cpot j cpot j 1 num j 1 j为列号 类型ElemType Triple和Matrix定义如下 typedefintElemType typedefstruct 三元组类型 intr c 矩阵元素的行号 列号 ElemTypee 矩阵元素的值 Triple typedefstruct 矩阵的三元组顺序表存储结构 introws cols elements 矩阵的行数 列数和非零元素数目 Tripledata MAXSIZE Matrix intTransposeMatrix MatrixM intj q t int num cpot MatrixMT MT是M的转置矩阵 num int malloc M cols sizeof int cpot int malloc M cols sizeof int if num cpot returnERROR MT rows 1 设置转置矩阵MT行数 列数和非零元数目 MT cols 2 MT elements M elements if M elements 0 for q 0 q M cols q num q 0 for t 0 t M elements t 计算矩阵M中每一列非零元素数目 num M data t c 计算矩阵M中每列第一个非零元素在其转置矩阵三元组顺序表中的位置 3 for j 1 j M cols j cpot j 4 以下代码完成转置矩阵MT三元组顺序表元素的设置 for t 0 t M elements t j 5 取矩阵M的一个非零元素的列号存入j q为该非零元素在转置矩阵MT三元组顺序表中的位置 下标 q cpot j MT data q r M data t c MT data q c M data t r MT data q e M data t e cpot j 计算M中第j列的下一个非零元素的目的位置 for if 2008年5月 下面的程序用DoleRob算法生成N阶 N为奇数 魔方阵 各行 列 对角线数字2之和相等 该算法的过程为 从1开始 按如下方法依次插入各自然数 直到N为止 a 在第一行的正中插入1 b 新位置应当处于最近插入位置的右上方 若该位置已超出方阵的上边界 则新位置取应选列的最下一个位置 若超出右边界 则新位置取应选行的最左一个位置 c 若最近插入的元素是N的整数倍 则选同列的下一行位置为新位置 例如 3阶魔方阵如下所示 816357492 defineSIZE50main introw col n value inta SIZE 1 SIZE 1 不使用下标为0的元素 printf 请输入要输出魔方阵的阶数n 奇数 n 4 elserow value 5 printf n d阶魔方阵如下所示 n n n for row 1 row n row for col 1 col n col printf a row col printf n 2005 5 假设一个剧场有N N个座位 顾客买票时可以提出任意有效的座号请求 下面用二维数组a N N 模拟剧场中的座位 a i j 等于0表示第i排第j列 0 I j N 1 的票尚未售出 函数intFind inta N intR int row int col 的功能是 在部分票已售出的情况下 找出剧场中的R R个空座位 要求这些座位的排列形成一个正方形 若找到满足要求的一个座位排列 则函数返回1 并算出该正方形左上角的行 列号 若未找到 返回0 intFind inta N intR int row int col inti j k c t intFOUND 0 for i 0 FOUND 查找和排序 排序算法冒泡排序选择排序快速排序直接插入排序归并排序堆排序其它排序查找二分查找 冒泡排序 若序列中有n个元素 通常进行n 1趟 第1趟 针对第1至n个元素进行 第2趟 针对第1至n 1个元素进行 第n 1趟 针对第1至2个元素进行 每一趟进行的过程 从第一个元素开始 比较两个相邻的元素 若相邻的元素的相对位置不正确 则进行交换 否则继续比较下面两个相邻的元素 结束条件 在任何一趟进行过程中 未出现交换 voidBubbleSort intL intn inti j flag inttemp for i 0 i n 1 i flag 0 for j 0 j n 1 i j if L j 1 L j temp L j 1 L j 1 L j L j temp flag 1 if flag 0 break 2007年5月 选择排序 第一趟扫描所有数据 选择其中最小的一个与第一个数据互换 第二趟从第二个数据开始向后扫描 选择最小的与第二个数据互换 依次进行下去 进行了 n 1 趟扫描以后就完成了整个排序过程 voidSelectSort intL intn inti j k inttemp for i 0 i n 1 i k i for j i 1 j n j if L j L k k j if k i temp L i L i L k L k temp 2004 11 某单位举办了一场知识竞赛 参加竞赛的选手为300名 依次从1 300进行编号 竞赛时间为9 00 11 00 8道竞赛题目依次从 A H 编号 选手可按任意次序答题 每完成一道题目 可立即提交答案 若答案正确 Y 则选择其他题目进行解答 否则 可继续做该题目或选择其他题目进行解答 直至竞赛结束 选手提交答案的情况及判定结果由专人即时录入 录入的数据如下表1所示 对竞赛情况进行统计和排名的结果如表2所示 统计和排名的规则如下 1 若选手X在竞赛时提交的题目P解答正确 则解答该题目所用时间如下计算 解答题目P的用时 提交题目P正确的时间 竞赛的开始时间 罚时罚时 提交题目P错误解答的次数 202 已经提交正确答案的题目再次提交时不再计算 3 竞赛结束时 选手的总用时为所有解答正确的题目用时累加所得 解答不正确的题目不计时 4 排名里 完成题目数量多者排名靠前 若完成的题目数相同 则用时少者排名靠前 若完成的题目数和所用时间均相等 则名次相同 完成题目数为0的选手不参加排名 函数voidStatistic 的功能是 读取输入数据 进行统计 排名并输出结果 defineMAXN300typedefstruct intno 选手编号 intnum 完成的题目数量 inttime 完成题目的总用时 intd 8 d i 用于记录提交第i个题目错误答案的次数 inta 8 a i 用于记录第i个题目是否已经提交正确答案 Info voidStatistic charch pass inti j k h m t time MaxIndex InfoR MAXN 1 for i 1 i MAXN i 数组R的元素置初值0 R i no 0 R i num 0 R i time 0 for j 0 j 8 j R i d j 0 R i a j 0 for MaxIndex 0 while 1 录入一句选手提交答案的信息 小时 分钟 选手编号 题目号 是否正确 scanf d d d c c while for i 1 i0 if R i num R 0 num R i time R 0 time k R 0 5 printf d 3d 4d 5d n k R i no R i num R i time if Statistic 直接插入排序 过程 第一个数为有序序列 将第2 n数插入到有序序列中1 判断要插入的数是否小于有序序列中的最后一个数 如果小于 说明需要插入 2 插入 将要插入的数放到监视哨 下标为0 中 监视哨与有序元素从尾开始进行比较 在已排序的序列中寻找自己的位置 每比较一次 后移一个数据 找到位置后退出 进行插入 寻找不到 则一直进行到哨兵为止 意味着本元素最小 应该放在r 1 voidInsertSort intL intn inti j for i 2 i n i if L i L i 1 L 0 L i for j i 1 L 0 L j j L j 1 L j L j 1 L 0 2002 函数insert sort inta intcount 是用直接插入排序法对指定数组的前count个元素从小到大排序 直接插入排序法的基本思想是 将整个数组 count个元素 看成是由有序的 a 0 a i 1 和无序的 a i a Count 1 两个部分组成 初始时i等于1 每趟排序时将无序部分中的第一个元素a i 插入到有序部分中的恰当位置 共需进行count 1趟 最终使整个数组有序 voidinsert sort inta intcount inti j t for i 1 i 0 快速排序 任取待排序列中的某个记录 例如取第一个记录 作为基准 按照该记录的关键字大小 将整个记录序列划分为左右两个子序列 左侧子序列中所有记录的关键字都小于基准记录的关键字右侧子序列中所有记录的关键字都大于或等于基准记录的关键字基准记录则排在这两个子序列中间 这也是该记录最终应安放的位置 然后分别对这两个子序列重复施行上述方法 直到所有的记录都排在相应位置上为止 一趟排序过程 intPartition intL intlow inthigh pivotkey L low 枢轴while low pivotkey high L low L high while low high voidQuickSort intL intlow inthigh 在待排序区间low high中递归地进行快速排序if low high pivotloc Partition L low high 划分QuickSort L low pivotloc 1 在左子区间递归进行快速排序QuickSort L pivotloc 1 high 在右子区间递归进行快速排序 voidmain intL 11 QuickSort L 1 10 2004 5 下面的流程图用N S盒图形式描述了数组A中的元素被划分的过程 其划分