Skip to content
22考研咨询 | 码哥（jnumagekaoyan）
已知由n(n≥2)个正整数构成的集合a={ak} 0≤k<n}，将其划分为两个不相交的子集a1和a2，元素个数分别是n1和n2，a1和a2中元素之和分别为s1和s2。设计一个尽可能高效的划分算法，满足|n1-n2|最小且|s1-s2|最大。要求：
(2)根据设计思想，采用c或c++语言描述算法，关键之处给出注释。?
(3)说明你所设计算法的平均时间复杂度和空间复杂度。
题目意思就是将数据分成两堆，个数相差1或者相等，两堆之间相差最大。一看还不简单，直接个序，前n/2个数一堆，后面的一堆，此时相差最大。
1）将所有元素排序，然后将前?n/2?个元素放在a1中，其余的元素放在a2中，产生最大值。
2）选择，插入，冒泡排序，时间复杂度为o(n^2)， 空间复杂度为o(1)，当选择快速排序，归并排序，堆排序，时间复杂度为o(nlogn),空间复杂度o(logn)，o(n)，o(1)。
int buddle(int a[], int n){ //冒泡排序 for(int i = 1; i < n; i++){ for(int j = 0; j < n-1; j++){ if(a[j]>a[j+1]) { int t = a[j]; a[j] = a[j+1]; a[j+1] = t; } } } //前面一部分n int s1 = 0; for(int i = 0; i < n/2; i++){ s1 += a[i]; } //后面一部分 int s2 = 0; for(int i = n/2; i < n; i++){ s2 += a[i]; } return s2-s1;}
设计一个算法，将给定的表达式树（二叉树）转换为等价的中缀表达式（通过括号反映操作符的计算次序）并输出。例如，当下列的两棵表达式树作为算法的输入时：
输出等价的中缀表达式分别为（a+b）*（c*（-d））和（a*b）+（-（c-d））。
typedef struct node{ char data[10]; struct node *left, *right; }btree;
（2）根据设计思想，采用 c 或 c++语言描述算法，关键之处给出注释
1）表达式树的中序序列加上必要的括号即为等价的中缀表达式。可以基于二叉树的中序遍历策略得到所需的表达式。表达式树中分支结点所对应的子表达式的计算次序，由该分支结点所处的位置决定。为得到正确的中缀表达式，需要在生成遍历序列的同时，在适当位置增加必要的括号。显然，表达式的最外层(对应根结点)及操作数(对应叶结点)不需要添加括号。
void btreetoe(btree * root){ btreetoexp(root，1)；//根的高度为1 void btreetoexp(btree * root, int deep) { if( root = = null) return; else if(root->left = = null && root->right = = null) //若为叶结点 printf(“％s”，root->data)；//输出操作数 else{ if(deep>1) printf(“(”)；//若有子表达式则加1层括号 btreetoexp(root->left，deep+1)； printf(“％s”，root->data)；//输出操作符 btreetoexp(root->right，deep+1)； if(deep>1) printf(“)”)；//若有子表达式则加1层括号 } }
给定一个含 n(n≥1)个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如,数组{-5, 3, 2, 3}中未出现的最小正整数是 1；数组{1, 2, 3}中未出现的最小正整数是 4。要求：?
（2）根据设计思想，采用 c 或 c++语言描述算法，关键之处给出注释。
题目意思找出数组从未出现的正数，看起来挺简单呀，无处下手，想排序，排序找到第一个大于0的数，好像这个方法可行，搞起来，写着写着。。好像问题来了，若1234567。。。n那第一个大于0的数就有问题了，心里好焦灼。
1）桶排序，找到数组中最大的元素，以便生成多少个桶；
2）若最大的元素小于0，那最大正数m就为1，若不为0，生成m+1个桶，并置0；
4）依次遍历桶，找到第一个没有数据的桶。若桶1到m都有数据，那就返回m+1。
计数排序的缺点：生成最大的数据的数组空间，若数组数据过大，其所占空间很大。
int majority(int a[ ]，int n){ //找出最大的数 int m = a[0]; for(int i = 1; i < n; i++){ if(a[i] > m) m = a[i]; } //最大的元素小于0，那最大正数m就为1 if(m < 0) return 1 int b = malloc(sizeof(int) * (m+1)) // 申请n个桶 for(int i = 0; i < n; i++){ //置0 b[i] = 0； } for(int i = 0; i < n; i++){ b[a[i]]++; //将值为a[i]放入桶中，桶里面个数加1 } for(int i = 1; i <= m; i++){ if(b[i] == 0) return i; //找到第一个没有数据的桶 } //若桶1到m都有数据，那就返回m+1. //数组a为12345 ， 返回6 return m+1；}
设线性表 l=(a1，a2，a3，…，an-2,an-1，an)采用带头结点的单链表保存，链表中结点定义如下：?
typedef struct node { int data； struct node * next： }node；
请设计一个空间复杂度为o(1)且时间上尽可能高效的算法，重新排列l中的各结点，得到线性表 l’=(a1，an，a2，an-1，an-2，…)。?
(2)根据设计思想，采用 c 或 c++语言描述算法，关键之处给出注释。?
1）先找出链表l的中间点，为此设置了两个指针p和q，指针p每次走一步，q每次走两步，当指针q达到链尾时，指针p正好在链表的中间点;
3）从单链表前后两段中以此各取一个结点，按要求重排
void change_list(linklist h){ lnode *p,*q,*r,*s; p=q=h; /*双指针找链表的中点*/ while(q->next!=null){ p=p->next; //p走一步 q=q->next; if(q->next!=null)q=q->next; //q走两步 } /*链表的逆置*/ q=p->next; //p所指结点为中点 p->next=null; //q为后半链表的首结点 while(q!=null){ r=q->next; q->next=p->next; p->next=q; q=r; } /*后半部分的链表头插进入前半部分*/ s=h->next; q=p->next; p->next=null; while(q!=null){ r=q->next q->next=s->next;//将q所指结点插入到s所指结点之后 s->next=q; s=q->next; //将s指向前半段的下一个插入点 q=r; }}
定义三元组（a,b,c）（a,b,c 均为整数）的距离 d=|a-b|+|b-c|+|c-a|。给定3个非空整数集合 s1,s2,s3,按升序分别存储在 3 个数组中。请设计一个尽可能高效的算法，计算并输出所有可能的三元组（a,b,c）（a∈s1,b∈s2,c∈s3）?中的最小距离。例如 s1={-1,0,9},s2=｛-25，-10，10，11｝，s3=｛2，9，17，?30，41｝。则最小距离为 2，相应的三元组为（9，10，9），要求：?
（2）根据设计思想，采用 c 或 c++语言描述算法，关键之处给出注释；?
看到这题三元组，算了，不想了，直接三层暴力吧，其它方法也想不出来，浪费时间，开干。
时间复杂度o(length1 * length2 * length3 ), 空间复杂度o(1)。
void arr(int s1[ ]，int s2[], int s3[]){ int length1 = sizeof(s1)/sizeof(s1[0]); // s1数组大小 int length2 = sizeof(s2)/sizeof(s2[0]); // s2数组大小 int length3 = sizeof(s3)/sizeof(s3[0]); // s3数组大小 int a, b, c; a = b = c;//存储三元组 int d = 100000; //给出一个超大的值 for (int i = 0 ; i < length1; i++){ for (int j = 0; j < length2; j++){ for (int k = 0; k < length3; k++){ int dis = abs(s1[i] - s2[j]) + abs(s2[j]- s3[k]) + abs(s3[k] - s1[i]); if(dis < d){ d = dis; //更新最小距离以及三元组 a = s1[i]; b = s2[j]; c = s3[k]; } } } } print("%d", d); print("%d%d%d", a, b, c);}
|京ICP备18012533号-328