下载文档原格式
1、对二叉树的某层上的结点进行运算，采用队列结构按层次遍历最适宜。
int LeafKlevel(BiTree bt, int k) //求二叉树bt 的第k(k>1) 层上叶子结点个数{if(bt==null || k<1) return(0);BiTree p=bt,Q[]; //Q是队列，元素是二叉树结点指针,容量足够大int front=0,rear=1,leaf=0; //front 和rear是队头和队尾指针, leaf是叶子结点数int last=1,level=1; Q[1]=p; //last是二叉树同层最右结点的指针，level 是二叉树的层数while(front<=rear){p=Q[++front];if(level==k && !p->lchild && !p->rchild) leaf++; //叶子结点if(p->lchild) Q[++rear]=p->lchild; //左子女入队if(p->rchild) Q[++rear]=p->rchild; //右子女入队if(front==last) {level++; //二叉树同层最右结点已处理,层数增1last=rear; } //last移到指向下层最右一元素if(level>k) return (leaf); //层数大于k 后退出运行}//while }//结束LeafKLevel2、请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为head。
二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。
分析你的算法的时、空复杂度。
3、本题应使用深度优先遍历，从主调函数进入dfs(v)时，开始记数，若退出dfs()前，已访问完有向图的全部顶点（设为n个），则有向图有根，v为根结点。
第二十一届全国青少年信息学奥林匹克联赛初赛普及组C++语言试题竞赛时间：2015年10月11日14:30~16:30选手注意：●试题纸共有7页，答题纸共有2页，满分100分。
请在答题纸上作答，写在试题纸上的一律无效。
●不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。
一、单项选择题（共20题，每题1.5分，共计30分；每题有且仅有一个正确选项）1.1MB等于（）。
A. 1000字节B. 1024字节C. 1000 X 1000字节D. 1024 X 1024字节2.在PC机中，PENTIUM（奔腾）、酷睿、赛扬等是指（）。
A. 生产厂家名称B. 硬盘的型号C. CPU的型号D. 显示器的型号3.操作系统的作用是（）。
A. 把源程序译成目标程序B. 便于进行数据管理C. 控制和管理系统资源D. 实现硬件之间的连接4.在计算机内部用来传送、存贮、加工处理的数据或指令都是以（）形式进行的。
A. 二进制码B. 八进制码C. 十进制码D. 智能拼音码5.下列说法正确的是（）。
A. CPU的主要任务是执行数据运算和程序控制B. 存储器具有记忆能力，其中信息任何时候都不会丢失C. 两个显示器屏幕尺寸相同，则它们的分辨率必定相同D. 个人用户只能使用Wifi的方式连接到Internet6.二进制数00100100和00010100的和是（）。
A. 00101000B. 01110011C. 01000100D. 001110007.与二进制小数0.1相等的十六进制数是（）。
A. 0.8B. 0.4C. 0.2D. 0.18.所谓的“中断”是指（）。
A. 操作系统随意停止一个程序的运行B. 当出现需要时，CPU暂时停止当前程序的执行转而执行处理新情况的过程C. 因停机而停止一个程序的运行D. 电脑死机9.计算机病毒是（）。
A. 通过计算机传播的危害人体健康的一种病毒B. 人为制造的能够侵入计算机系统并给计算机带来故障的程序或指令集合C. 一种由于计算机元器件老化而产生的对生态环境有害的物质D. 利用计算机的海量高速运算能力而研制出来的用于疾病预防的新型病毒10.FTP可以用于（）。
1、下面描述中，符合结构化程序设计风格的是(A)A. 使用顺序、选择和重复（循环）三种基本控制结构表示程序的控制逻辑B. 模块只有一个入口，可以有多个出口C. 注重提高程序的执行效率D. 不使用goto语句2、下列关于栈的叙述中正确的是(D)A. 在栈中只能插入数据B. 在栈中只能删除数据C. 栈是先进先出的线性表D. 栈是先进后出的线性表3、下列叙述中正确的是(A)A. 线性表是线性结构B. 栈与队列是非线性结构C. 线性链表是非线性结构D. 二叉树是线性结构4、在结构化方法中，软件功能分解属于下列软件开发中的阶段是(C) 注：总体设计也就是概要设计A. 详细设计B. 需求分析C. 总体设计D. 编程调试5、在结构化方法中，用数据流程图（DFD）作为描述工具的软件开发阶段是(B)A. 可行性分析B. 需求分析C. 详细设计D. 程序编码6、在关系数据库中，用来表示实体之间联系的是(D)A. 树结构B. 网结构C. 线性表D. 二维表7、下面概念中，不属于面向对象方法的是 (D)A. 对象B. 继承C. 类D. 过程调用8、在结构化方法中，软件功能分解属于下列软件开发中的阶段是(C) 注：总体设计也就是概要设计A. 详细设计B. 需求分析C. 总体设计D. 编程调试9、下面不属于软件工程的3个要素的是(D)A. 工具B. 过程C. 方法D. 环境10、以下数据结构中不属于线性数据结构的是(C)A. 队列B. 线性表C. 二叉树D. 栈。
2023年宁夏回族自治区中卫市全国计算机等级考试C语言程序设计真题(含答案)学校:________ 班级:________ 姓名:________ 考号:________一、2.填空题(10题)1. 以下程序输出的结果是#include＜stdio.h＞#include＜string.h＞main() {charw[][10]={"ABCD"，"EFGH"，"IJKL"，"MNOP"}1，k；for(k=1；k＜3；k++) printf("%s\n"，&w[k][k])；}2. 若有如下定义：int x=2,y=3,z=4;则表达式!(x=y)||x+z&&y-z的值是【】。
3. 下面程序把从终端读入的文本(用@作为文本结束标志)输出到一个名为bi．dat的新文件中，请填空。
#include "stdio．h"FILE *fp；main(){ char ch；if((fp=fopen( 【】))==NULL)exit(0)；while((ch=getchar())!='@')fputc(ch,fp)；fclose(fp)；}4. 设有以下定义和语句，则*(*(p+2)+1)的值为【】。
int a[3][2]={10,20,30,40,50,60},(*p)[2];p=a;5. 下面程序的输出是【】。
main(){int arr[10],i,k=0;for(i=0;i＜10;i++)arr[i]=i;fov(i=1;i＜4;i++)k+=arr[i]+i;printf("%d\n",k);}6. 以下程序建立一个带有头结点的单向链表，链表结点中的数据通过键盘输入，当输入数据为-1时，表示输入结束(键表头结点的data域不放数据，表空的条件是ph-＞next==NULL)，请填空。
2022年宁夏回族自治区银川市全国计算机等级考试网络技术真题(含答案) 学校:________ 班级:________ 姓名:________ 考号:________一、单选题(10题)1.以下不属于网络安全评估内容的是()。
A.数据加密B.漏洞检测C.风险评估D.安全审计2.数据链路层可分成( )。
A.数据子层和链路子层B.冲突检测子层和传输层C.逻辑链路控制子层和介质访问控制子层D.互连子层和MAC子层3.下列哪一项不是收集网络商务信息的基本要求()。
A.经济B.适度C.按时D.准确4.第40题IEEE802参考模型中不包含（）A.逻辑链路控制于层B.介质访问控制子层C.网络层D.物理层5.广域网所覆盖地理范围一般是()公里。
A.几十到几千B.几十到几万C.几到几百D.几到几千6.在计算机网络体系结构中，要采用分层结构的理由是( )。
A.可以简化计算机网络的实现B.各层功能相对独立，各层因技术进步而做的改动不会影响到其他层，从而保持体系结构的稳定性C.比模块结构好D.只允许每层和其上、下相邻层发生联系7.通信控制处理机在网络拓扑结构中被称为()。
A.网络服务器B.网络防火墙C.网络交换机D.网络结点8.网络基础服务系统不包括()。
A.网络管理和服务软件B.网络安全软件C.网络下载和上传软件D.网络管理软件9.第11题SDH的模块信号STM一4的速率是（）。
A.100MbpsB.2.5GbpsC.622.080MbpsD.1.55.520Mbps10.在计算机网络中负责信息处理的部分称为( )。
A.通信子网B.交换网C.资源子网D.工作站二、填空题(10题)11.12.第72 题从使用的传输介质类型来看，局域网可以分为使用有线介质的局域网和使用___________的局域网。
13. 在分布式计算中，一个应用程序被动地等待，而另一个应用程序通过请求启动通信的模式就是______交互模式。
14. Solaris 10操作系统获得业界支持，它的桌面已经窗口化和菜单化。
（2023年）宁夏回族自治区中卫市全国计算机等级考试数据库技术预测试题(含答案)学校:________ 班级:________ 姓名:________ 考号:________一、1.选择题(10题)1. 在关系型数据库中，实现实体之间的联系是通过表与表之间的A.公共索引B.公共存储C.公共元组D.公共属性2. 数据库管理系统中对数据库数据的删除由( )功能模块实现?A.数据库存取B.数据库存储管理C.数据库运行处理D.数据库维护3. Oracle针对Internet/Intranet的产品是______。
A.Oracle WebServerB.Oracle WebListenerC.Oracle WebAgentD.Oracle 7服务器4. 在关系代数中，自然连接的运算符号为( )。
A.∞B.×C.πD.σ5. 下列不属于数据库运行过程中可能发生的故障是( )。
A.系统故障B.事务故障C.逻辑故障D.磁盘故障6. 解决主机命名、主机域名管理、主机域名与IP地址映射等问题的是( )。
A.域名系统B.SMTP协议C.主机服务器D.TCP/IP协议7. DDL是A.操作数据语言B.定义数据的语言C.自含语言D.宿主语言8. 下列哪一种文件存储设备不支持文件的随机存取?______。
A.磁盘B.光盘C.软盘D.磁带9. 一个部门有若干名职工，则部门与职工之间具有A.一对一联系B.一对多联系C.多对多联系D.多对一联系10. 数字签名是通过______来实现的。
A.认证B.程序C.签字算法D.仲裁二、填空题(10题)11.计算机网络是由多台计算机互联而成的，为保证网络中计算机间的数据交换，要求计算机在交换数据的过程中遵守相应的网络协议。
一个网络协议由语法、【】和时序三个要素组成。
12.从被管理设备中收集数据有两种方法：轮询法和基于中断法，将两者结合起来的___________ (Trap—directed Polling)是执行网络管理最有效的方法。
1、设一棵树T中边的集合为{(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)}，要求用孩子兄弟表示法（二叉链表）表示出该树的存储结构并将该树转化成对应的二叉树。
2、设t是给定的一棵二叉树，下面的递归程序count(t)用于求得:二叉树t中具有非空的左,右两个儿子的结点个数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数NR和叶子结点个数N0。
N2、NL、NR、N0都是全局量，且在调用count(t)之前都置为0.typedef struct node{int data; struct node *lchild,*rchild;}node;int N2,NL,NR,N0;void count(node *t){if (t->lchild!=NULL) if (1)___ N2++; else NL++;else if (2)___ NR++; else (3)__ ;if(t->lchild!=NULL)(4)____; if (t->rchild!=NULL) (5)____;}26.树的先序非递归算法。
void example(b)btree *b;{ btree *stack[20], *p；int top;if (b!=null){ top=1; stack[top]=b;while (top>0){ p=stack[top]; top--;printf(“%d”,p->data);if (p->rchild!=null){(1)___; (2)___;}if (p->lchild!=null)(3)___; (4)__;}}}}3、设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。
1、已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>}写出G的拓扑排序的结果。
G拓扑排序的结果是：V1、V2、V4、V3、V5、V6、V72、约瑟夫环问题（Josephus问题）是指编号为1、2、…，n的n（n>0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，…，如此重复直到所有的人全部出列为止。
现要求采用循环链表结构设计一个算法，模拟此过程。
3、设一棵二叉树的结点结构为 (LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针，p 和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR（ROOT，p,q,r）,该算法找到p和q的最近共同祖先结点r。
4、连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边，最小生成树是边上权值之和最小的生成树。
故可按权值从大到小对边进行排序，然后从大到小将边删除。
每删除一条当前权值最大的边后，就去测试图是否仍连通，若不再连通，则将该边恢复。
若仍连通，继续向下删；直到剩n-1条边为止。
void SpnTree (AdjList g)//用“破圈法”求解带权连通无向图的一棵最小代价生成树。
{typedef struct {int i,j,w}node; //设顶点信息就是顶点编号，权是整型数node edge[];scanf( "%d%d",&e,&n) ; //输入边数和顶点数。
for (i=1;i<=e;i++) //输入e条边：顶点，权值。
scanf("%d%d%d" ,&edge[i].i ,&edge[i].j ,&edge[i].w);for (i=2;i<=e;i++) //按边上的权值大小，对边进行逆序排序。
{edge[0]=edge[i]; j=i-1;while (edge[j].w<edge[0].w) edge[j+1]=edge[j--];edge[j+1]=edge[0]; }//fork=1; eg=e;while (eg>=n) //破圈，直到边数e=n-1.{if (connect(k)) //删除第k条边若仍连通。
{edge[k].w=0; eg--; }//测试下一条边edge[k]，权值置0表示该边被删除k++; //下条边}//while}//算法结束。
connect()是测试图是否连通的函数，可用图的遍历实现，5、由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序所缺的语句。
#define MAX 100typedef struct Node{char info; struct Node *llink, *rlink; }TNODE;char pred[MAX],inod[MAX];main(int argc,int **argv){ TNODE *root;if(argc<3) exit 0;strcpy(pred,argv[1]); strcpy(inod,argv[2]);root=restore(pred,inod,strlen(pred));postorder(root);}TNODE *restore(char *ppos,char *ipos,int n){ TNODE *ptr； char *rpos; int k;if(n<=0) return NULL;ptr->info=(1)_______;for((2)_______ ; rpos<ipos+n;rpos++) if(*rpos==*ppos) break;k=(3)_______;ptr->llink=restore(ppos+1, (4)_______,k );ptr->rlink=restore ((5)_______+k,rpos+1,n-1-k);return ptr;}postorder(TNODE*ptr){ if(ptr=NULL) return;postorder(ptr->llink); postorder(ptr->rlink); printf(“%c”,ptr->info); }6、4、void LinkList_reverse(Linklist &L)//链表的就地逆置;为简化算法,假设表长大于2{p=L->next;q=p->next;s=q->next;p->next=NULL;while(s->next){q->next=p;p=q;q=s;s=s->next; //把L的元素逐个插入新表表头}q->next=p;s->next=q;L->next=s;}//LinkList_reverse7、由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序所缺的语句。
#define MAX 100typedef struct Node{char info; struct Node *llink, *rlink; }TNODE;char pred[MAX],inod[MAX];main(int argc,int **argv){ TNODE *root;if(argc<3) exit 0;strcpy(pred,argv[1]); strcpy(inod,argv[2]);root=restore(pred,inod,strlen(pred));postorder(root);}TNODE *restore(char *ppos,char *ipos,int n){ TNODE *ptr； char *rpos; int k;if(n<=0) return NULL;ptr->info=(1)_______;for((2)_______ ; rpos<ipos+n;rpos++) if(*rpos==*ppos) break;k=(3)_______;ptr->llink=restore(ppos+1, (4)_______,k );ptr->rlink=restore ((5)_______+k,rpos+1,n-1-k);return ptr;}postorder(TNODE*ptr){ if(ptr=NULL) return;postorder(ptr->llink); postorder(ptr->rlink); printf(“%c”,ptr->info); }8、根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论，为此设全局指针变量pre（初值为null）和全局变量flag，初值为true。
若非二叉排序树，则置flag为false。
#define true 1#define false 0typedef struct node{datatype data; struct node *llink,*rlink;} *BTree;void JudgeBST（BTree t,int flag）// 判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag得出结论。
{ if（t!=null && flag）{ Judgebst（t->llink,flag）；// 中序遍历左子树if（pre==null）pre=t；// 中序遍历的第一个结点不必判断else if（pre->data<t->data）pre=t；//前驱指针指向当前结点else{flag=flase；} //不是完全二叉树Judgebst （t->rlink,flag）；// 中序遍历右子树}//JudgeBST算法结束9、有一种简单的排序算法，叫做计数排序（count sorting）。
这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。
必须注意的是，表中所有待排序的关键码互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小，假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。
(1) (3分)给出适用于计数排序的数据表定义;(2) (7分)使用Pascal或C语言编写实现计数排序的算法；(3) (4分)对于有n个记录的表，关键码比较次数是多少?(4) (3分)与简单选择排序相比较，这种方法是否更好?为什么?10、二部图（bipartite graph） G=（V，E）是一个能将其结点集V分为两不相交子集V 1和V2=V-V1的无向图，使得：V1中的任何两个结点在图G中均不相邻，V2中的任何结点在图G中也均不相邻。
（1）．请各举一个结点个数为5的二部图和非二部图的例子。
（2）．请用C或PASCAL编写一个函数BIPARTITE判断一个连通无向图G是否是二部图，并分析程序的时间复杂度。
设G用二维数组A来表示，大小为n*n（n为结点个数）。
请在程序中加必要的注释。
若有必要可直接利用堆栈或队列操作。
【11、给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。
20分void Hospital(AdjMatrix w,int n)//在以邻接带权矩阵表示的n个村庄中，求医院建在何处，使离医院最远的村庄到医院的路径最短。
{for (k=1;k<=n;k++) //求任意两顶点间的最短路径for (i=1;i<=n;i++)for (j=1;j<=n;j++)if (w[i][k]+w[k][j]<w[i][j]) w[i][j]=w[i][k]+w[k][j];m=MAXINT; //设定m为机器内最大整数。
