大连东软数据结构编程题.docx

数据结构编程题1) 题1完成函数f的实现，参数a为int数组首地址，len为数组长度，要求函数f能够将数组元素重新排列奇数在前，偶数在后。 答案：void f(int *a, int len) int i, j;for(i=0; ilen-1; i+) int flg=1;for(j=0; jlen-1-i; j+) if(aj%2=0 & aj+1%2) int tmp=aj;aj=aj+1;aj+1=tmp;flg=0;if(flg) break;2) 题2完成函数f的实现，参数a为int数组的首地址，len为数组长度，要求函数f能够返回数组最大元素的个数。答案：int f(const int *a, int len) int i, max=0, cnt=1;/max用于保存最大元素的序号，cnt用于记录个数 for(i=1; ilen; i+)if(amaxai) max=i;cnt=1; else if(amax=ai) +cnt;return cnt;3) 题3完成函数f的实现，参数a为int数组的首地址，len为数组长度，要求函数f能够将数组元素按照个位排降序，同时要求使用的算法要保证排序稳定性。答案：解法一：（插入排序）void f(int *a, int len) int i, j, tmp;for(i=1; ia0%10) /对某数进行%10运算，即可获取其个位上的值 for(j=i-1; tmp%10aj%10; -j)aj+1=aj;aj+1=tmp; else for(j=i; j0; -j)aj=aj-1;a0=tmp;解法二：（冒泡排序）void f(int *a, int len) int i, j, flg, tmp;for(i=0; ilen-1; +i) flg=0;for(j=0; jaj%10) tmp=aj+1; aj+1=aj;aj=tmp;if(flg=0) break;4) 题4完成函数f的实现，参数a为int数组首地址，len数组长度，要求函数f返回数组中元素是否构成大根堆，是返回1，否返回0.答案：_Bool f(const int *a, int len) int i;for(i=(len-1)/2; i=0; -i) if(aia2*(i+1)-1 | aia2*(i+1) return false;return true;5) 题5完成函数f的实现，参数a为int数组首地址，len为数组长度，x为一个整数，假设数组元素已排好降序，要求函数f运用折半查找算法，查找数组中是否存在x，存在返回1，不存在返回0。答案：_Bool f(const int *a, int len, int x) int low=0, high=len-1, mid=(low+high)/2;while(lowhigh) if(amid=x) return true; else if(amidx) low=mid+1;mid=(low+high)/2;return false;6) 题6完成函数f的实现，参数s和t分别表示两个字符串首地址，要求函数f返回字符串t在字符串s中出现的次数，例如：f(“aaa”, “aa”)返回2。答案：int f(const char *s, const char *t) int len1=strlen(s), len2=strlen(t), i, num=0;for(i=0 ;itail=NULL)return false;Node *cur=lp-tail;lp-tail=cur-p;if(lp-tail=NULL)lp-head=NULL;elselp-tail-n=NULL;free(cur);return true;8) 题8代码中，结构体Node表示二叉树节点，其中left指向左孩子，right指向右孩子；完成函数f的实现，参数root表示二叉树根节点指针，要求函数f返回该树的深度，提示可用先序遍历。答案：int f(const Node *root) if(root=NULL)return 0;int l=f(root-left);int r=f(root-right);return lr?l+1:r+1;9) 题9代码中，结构体Node表示二叉树节点，其中left指向左孩子，right指向右孩子；完成函数f的实现，参数root表示二叉树根节点指针，要求函数f释放该树全部节点占用的内存（假设节点内存来自堆区），提示可用后序遍历。答案：int f(Node *root) if(root=NULL)return;f(root-left);f(root-right);free(root);10) 题10代码中，结构体Node表示单链表的节点，data是整型数据域，next是指向后继的指针；完成函数f的实现，参数head是某链表的头节点，参数x表示一个整数，要求函数f返回链表中数据域大于x的节点的个数。答案：int f(Node *head, int x) Node *p;int cnt=0;for(p=head; p!=NULL; p=p-next)if(p-datax)cnt+;return cnt;11) 题11完成函数f的实现，参数n表示正整数，参数a表示二维数组首地址，a表示的二维数组用于存储n个系欸但有向图的邻接矩阵，aij=1时表示节点i到节点j有边，函数f需要返回有向图中出度大于入度的顶点的个数。答案：int f(int n, const _Bool ann) int i, j, cnt=0;for(i=0; in; i+) int in=0, out=0;for(j=0; jin)cnt+;return cnt;12) 题12完成函数f的实现，参数n表示正整数，参数a表示一个一位数组首地址，i表示一个正整数（0=in），a表示的一维数组用于存储n个节点无向图的邻接矩阵的上三角压缩存储，函数f需要返回无向图中节点i的度。答案：int f(int n, const _Bool a, int i) int j, k=0;int m=n-i;for(j=0; ji; j+)k+=(n-);int cnt=0;for(j=k; j0)stack-;elsereturn false;if(stack=0)return true;return false;14) 题14完成函数f的实现，参数s1和s2分别表示两个字符串首地址，要求函数f实现不区分大小写字母的字符串比较，当s1比s2小时f返回负数，当s1比s2大时返回正数，字母串相等返回0。答案int f(const char *s1, const char *s2) int i;for(i=0; s1i!=0 | s2i!=0; i+)if(s1i=s2i) continue; else if(s1i=A & s1i=a & s1i=A & s2i=a & s2is2i) return 1; else return -1;return 0;15) 题15完成函数f的实现，参数a、b、c表示三个int数组的首地址，la和lb表示数组a和b的长度，假设数组a和b存在升序。要求函数f完成将数组a和b的内容归并到数组c中，即a和b的内容复制至数组c后，c也有升序，同时当a和b中存在相等元素时，需要优先向c中写入a中的等