1、#define maxsize 栈空间容量
void InOutS(int s[maxsize])
//s是元素为整数的栈，本算法进行入栈和退栈操作。
{int top=0; //top为栈顶指针，定义top=0时为栈空。 for(i=1; i<=n; i++) //n个整数序列作处理。 {scanf(“%d”,&x); //从键盘读入整数序列。
if(x!=-1) // 读入的整数不等于-1时入栈。 if(top==maxsize-1){printf(“栈满\\n”);exit(0);} else s[++top]=x; //x入栈。
else //读入的整数等于-1时退栈。
{if(top==0){printf(“栈空\\n”);exit(0);}
else printf(“出栈元素是%d\\n”,s[top--])；} }
}//算法结
2、矩阵中元素按行和按列都已排序，要求查找时间复杂度为O（m+n），因此不能采用常规的二层循环的查找。可以先从右上角（i=a,j=d）元素与x比较，只有三种情况：一是A[i,j]>x，这情况下向j 小的方向继续查找；二是A[i,j] void search(datatype A[ ][ ], int a,b,c,d, datatype x) //n*m矩阵A,行下标从a到b,列下标从c到d,本算法查找x是否在矩阵A中. {i=a; j=d; flag=0; //flag是成功查到x的标志 while(i<=b && j>=c) if(A[i][j]==x) {flag=1;break;} else if (A[i][j]>x) j--; else i++; if(flag) printf(“A[%d][%d]=%d”,i,j,x); //假定x为整型. else printf(“矩阵A中无%d 元素”，x)； }算法search结束。 [算法讨论]算法中查找x的路线从右上角开始，向下（当x>A[i,j]）或向左（当x 3、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。 29. ①试找出满足下列条件的二叉树 1）先序序列与后序序列相同 2）中序序列与后序序列相同 3）先序序列与中序序列相同 4）中序序列与层次遍历序列相同 4、在有向图G中，如果r到G中的每个结点都有路径可达，则称结点r为G的根结点。编写一个算法完成下列功能： （1）．建立有向图G的邻接表存储结构； （2）．判断有向图G是否有根，若有，则打印出所有根结点的值。 5、数组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(i if(a[i] 4、要求二叉树按二叉链表形式存储。15分 （1）写一个建立二叉树的算法。（2）写一个判别给定的二叉树是否是完全二叉树的算法。 BiTree Creat() //建立二叉树的二叉链表形式的存储结构 {ElemType x；BiTree bt; scanf(“%d”,&x); //本题假定结点数据域为整型 if(x==0) bt=null; else if(x>0) {bt=(BiNode *)malloc(sizeof(BiNode)); bt->data=x; bt->lchild=creat(); bt->rchild=creat(); } else error(“输入错误”)； return(bt); }//结束 BiTree int JudgeComplete(BiTree bt) //判断二叉树是否是完全二叉树,如是，返回1，否则，返回0 {int 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 && !tag) QueueIn(Q,p->rchild); //右子女入队 else if (p->rchild) return 0; else tag=1; } //while return 1; } //JudgeComplete 6、编程实现单链表的就地逆置。 23．在数组 A[1..n]中有n个数据，试建立一个带有头结点的循环链表，头指针为h，要求链中数据从小到大排列，重复的数据在链中只保存一个. 7、在有向图G中，如果r到G中的每个结点都有路径可达，则称结点r为G的根结点。编写 一个算法完成下列功能： （1）．建立有向图G的邻接表存储结构； （2）．判断有向图G是否有根，若有，则打印出所有根结点的值。 8、矩阵中元素按行和按列都已排序，要求查找时间复杂度为O（m+n），因此不能采用常规的二层循环的查找。可以先从右上角（i=a,j=d）元素与x比较，只有三种情况：一是A[i,j]>x，这情况下向j 小的方向继续查找；二是A[i,j] void search(datatype A[ ][ ], int a,b,c,d, datatype x) //n*m矩阵A,行下标从a到b,列下标从c到d,本算法查找x是否在矩阵A中. {i=a; j=d; flag=0; //flag是成功查到x的标志 while(i<=b && j>=c) if(A[i][j]==x) {flag=1;break;} else if (A[i][j]>x) j--; else i++; if(flag) printf(“A[%d][%d]=%d”,i,j,x); //假定x为整型. else printf(“矩阵A中无%d 元素”，x)； }算法search结束。 [算法讨论]算法中查找x的路线从右上角开始，向下（当x>A[i,j]）或向左（当x 9、约瑟夫环问题（Josephus问题）是指编号为1、2、?，n的n（n>0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，?，如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法，模拟此过程。 #include typedef listnode *linklist; void jose(linklist head,int s,int m) {linklist k1,pre,p; int count=1; pre=NULL; k1=head; /*k1为报数的起点*/ while (count!=s) /*找初始报数起点*/ {pre=k1; k1=k1->next; count++; } while(k1->next!=k1) /*当循环链表中的结点个数大于1时*/ { p=k1; /*从k1开始报数*/ count=1; while (count!=m) /*连续数m个结点*/ { pre=p; p=p->next; count++; } pre->next=p->next; /*输出该结点，并删除该结点*/ printf(\free(p); k1=pre->next; /*新的报数起点*/ } printf(\输出最后一个结点*/ free(k1); } main() {linklist head,p,r; int n,s,m,i; printf(\ scanf(\ printf(\ scanf(\ printf(\ scanf(\ if (n<1) printf(\ else {/*建表*/ head=(linklist)malloc(sizeof(listnode)); /*建第一个结点*/ head->data=n; r=head; for (i=n-1;i>0;i--) /*建立剩余n-1个结点*/ { p=(linklist)malloc(sizeof(listnode)); p->data=i; p->next=head; head=p; } r->next=head; /*生成循环链表*/ jose(head,s,m); /*调用函数*/ } } 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库2014河北省数据库考试含答案基础在线全文阅读。
相关推荐：