《2021年山东省数据理论加强.docx》由会员分享，可在线阅读，更多相关《2021年山东省数据理论加强.docx（3页珍藏版）》请在三一文库上搜索。
1、2021年山东省数据理论加强1、数组A和B的元素分别有序，欲将两数组合并到C数组，使C仍有序，应将A和B拷贝到C，只要注意A和B数组指针的使用，以及正确处理一数组读完数据后将另一数组余下元素复制到C中即可。void union(int A,B,C,m,n)/整型数组A和B各有m和n个元素，前者递增有序，后者递减有序，本算法将A和B归并为递增有序的数组C。i=0; j=n-1; k=0;/ i，j，k分别是数组A,B和C的下标，因用C描述，下标从0开始while(iif(aiwhile(iwhile(j=0) ck+=bj-;算法结束4、要求二叉树按二叉链表形式存储。15分（1）写一个建立二叉树
2、的算法。（2）写一个判别给定的二叉树是否是完全二叉树的算法。BiTree Creat() /建立二叉树的二叉链表形式的存储结构ElemType x；BiTree bt;scanf(“%d”,&x); /本题假定结点数据域为整型if(x=0) bt=null;else if(x0)bt=(BiNode *)malloc(sizeof(BiNode);bt-data=x; bt-lchild=creat(); bt-rchild=creat();else error(“输入错误”)；return(bt);/结束 BiTreeint JudgeComplete(BiTree bt) /判断二叉树是否
3、是完全二叉树,如是，返回1，否则，返回0int tag=0; BiTree p=bt, Q; / Q是队列，元素是二叉树结点指针，容量足够大if(p=null) return (1);QueueInit(Q); QueueIn(Q,p); /初始化队列，根结点指针入队while (!QueueEmpty(Q)p=QueueOut(Q); /出队if (p-lchild & !tag) QueueIn(Q,p-lchild); /左子女入队else if (p-lchild) return 0; /前边已有结点为空，本结点不空else tag=1; /首次出现结点为空if (p-rchild &
4、 !tag) QueueIn(Q,p-rchild); /右子女入队else if (p-rchild) return 0; else tag=1; /whilereturn 1; /JudgeComplete2、给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。（20分）3、设有一个数组中存放了一个无序的关键序列K1、K2、Kn。现要求将Kn放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n。51. 借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组rl.h中。若查找成功，则输出该记录在r数组中的位置及其值，否则显示“not find”信息。请编写出算法并简要说明算法思想。