信计091数据结构机考题目.doc
- 格式：doc
- 大小：75.50 KB
- 文档页数：12
1. 试写一程序，实现单链表的就地逆置。
#include<stdio.h>#include<stdlib.h>typedef struct node{int num;struct node *next;}*linklist;void initlist(linklist &head,int n){linklist p;int i;head=(linklist)malloc(sizeof(linklist));scanf("%d",&head->num);p=head;for(i=1;i<n;i++){p->next=(linklist)malloc(sizeof(linklist));scanf("%d",&p->next->num);p=p->next;}p->next=NULL;}//创建线性链表，n为线性表的长度linklist reverse(linklist &head){linklist p,q;p=head->next;head->next=NULL;while(p){q=p;p=p->next;q->next=head;head=q;}return(head);}void print(linklist head){linklist p;p=head;if(p==NULL) return;do{printf("%d ", p->num);p=p->next;}while(p != NULL);printf("\n");}void main(){int n;linklist head;printf("请输入线性表的长度:\n");scanf("%d",&n);printf("请输入数据:\n");initlist(head,n);printf("输出结果:\n");print(reverse(head));}2. 试写一程序，实现数制转换运算。
例如，十进制转化为八进制，（10）10=（17）8。
# include <stdio.h># include <stack>using namespace std;void conversion (int n,int M){stack <int> s;while (n){s.push(n%M);n=n/M;}while(!s.empty()){printf("%d",s.top());s.pop();}printf("\n");}void main(){int n,m;printf("输入要转化的数值:\n");scanf("%d",&n);printf("需转化为几进制:\n");scanf("%d",&m);printf("输出结果:\n");conversion (n,m);}3.试写一程序，实现稀疏矩阵的快速转置运算。
# include<stdio.h># define maxsize 12500typedef struct{int i,j;int e;}triple;typedef struct{triple data[maxsize+1];int mu,nu,tu;}tsmatrix;void fasttranspose(tsmatrix m,tsmatrix &t) {t.mu=m.mu;t.nu=m.nu;t.tu=m.tu;int col,p,q,t1;int copt[12500],num[12500];if(t.tu){for(col=1;col<=m.nu;col++)num[col]=0;for(t1=1;t1<=m.tu;t1++)++num[m.data[t1].j];copt[1]=1;for(col=2;col<=m.nu;++col)copt[col]=copt[col-1]+num[col-1];for(p=1;p<=m.tu;++p){col=m.data[p].j;q=copt[col];t.data[q].i=m.data[p].j;t.data[q].j=m.data[p].i;t.data[q].e=m.data[p].e;++copt[col];}}}void main(){tsmatrix m,n;int k;printf("please input M's rows,cols and NonT otal:\n");scanf("%d,%d,%d",&m.mu,&m.nu,&m.tu);printf("please input data:\n");for(k=0;k<m.tu;k++){scanf("%d,%d,%d",&m.data[k+1].i,&m.data[k+1].j,&m.data[k+1].e);printf("\n");}m.data[0].i=m.mu;m.data[0].j=m.nu;m.data[0].e=m.tu;fasttranspose(m,n);printf("please output results:\n");for(k=1;k<=n.tu;k++)printf("%d,%d,%d\n",n.data[k].i,n.data[k].j,n.data[k].e);}4. 试写一程序，在一个串中找子串，要求使用堆分配存储串。
# include <stdio.h># include <stdlib.h># include <string.h>typedef struct {char *ch;int length;}Hstring;int substring(Hstring &sub,Hstring s,int pos,int len){int i,j;if(pos<1||pos>s.length|| len<0||len>s.length -pos+1)return 0;if(!len){sub.ch=NULL;sub.length =0;}else{sub.ch=(char*)malloc(len*sizeof(char));for(j=0,i=pos-1;i<len+pos-1;i++,j++)sub.ch[j]=s.ch[i];sub.ch[j]='\0';sub.length =len;}return 1;}void main(){Hstring s,sub;char c, t[30];printf("输入pos的值和len的值\n");int i=0,pos ,len;scanf("%d,%d",&pos,&len);getchar();printf("输入字符串\n");s.ch=(char*)malloc(len*sizeof(char));while((c=getchar())!='\n'){t[i]=c;i++;}strcpy(s.ch ,t);s.length=strlen(t);substring(sub,s,pos,len);printf("%s\n",sub.ch);}5. 试写一程序，实现两个串的连接操作，要求使用堆分配存储串。
#include <stdio.h>#include <stdlib.h>#include <string.h>typedef struct{char *ch;int length;}Hstring;void concat(Hstring&t, Hstring s1,Hstring s2){int i,j;t.length=s1.length+s2.length ;t.ch=(char*)malloc(t.length*sizeof(char));for(i=1;i<=s1.length; i++)t.ch[i-1]=s1.ch[i-1];for(j=1;j<=s2.length; i++,j++)t.ch[i-1]=s2.ch[j-1];}void main(){Hstring s1, s2, t;char chars1[100];char chars2[100];printf("输入子串1:\n");gets(chars1);printf("输入子串2:\n");gets(chars2);s1.length=strlen(chars1);s2.length=strlen(chars2);s1.ch=(char*)malloc(s1.length*sizeof(char));s2.ch=(char*)malloc(s2.length*sizeof(char));strcpy(s1.ch,chars1);strcpy(s2.ch,chars2);concat(t,s1,s2);printf("输出结果:\n");printf("%s\n",t.ch);}6. 试写一程序，实现中序非递归遍历二叉树。
#include <stdio.h>#include<stdlib.h>typedef struct bitnode{char data;struct bitnode *lchild, *rchild;}bitnode,*bitree;void createtree(bitree &t){char ch;scanf("%c",&ch);if(ch==' ') t=NULL;else{if(!(t=(bitnode*)malloc(sizeof(bitnode)))) exit(-1);t->data =ch;createtree(t->lchild );createtree(t->rchild );}}void inordertr(bitree t){bitree stack[50];int top=0;stack[top]=t;do{while(t!=NULL){top++;stack[top]=t->lchild ;t=t->lchild ;}t=stack[top];top--;if(top>=0){t=stack[top];top--;printf("%c",t->data);top++;stack[top]=t->rchild;t=t->rchild ;}}while(top>=0||t!=NULL);}void main(){bitree t;printf("按先序序列输入树中的元素：\n");createtree(t);printf("请输出树的中序序列：\n");inordertr(t);printf("\n");}7. 试写一程序，利用有序表实现折半查找算法。
