1 专升本考试计算机专业数据结构算法专题1设计一个算法，计算单链表中数据域值为x 的结点个数。逐个查找单链表中的结点x，并计数。int number(lnode *h,int x) int n=0；while(h) if(h-data=x) n+；h=h-next ； return s； 2设计一个用前插法建立带表头结点的单链表的算法。前插法建立带表头结点的单链表算法中的tag 为输人数据结束标志。Lnode *createhh(int tag) int x；Lnode *p ，*h=(Lnode *)malloc(sizeof(Lnode)；h-next=NULL ；printf(input x:)；scanf(%d,&x); while(x!=tag) p=(Lnode*)malloc(sizeof(Lnode); p-data=x; p-next=h-next; h-next=p; scanf(%d,&x); return h; 3解本题的基本思想是：先将顺序队列q 中所有元素出队，并依次进入顺序栈s 中，然后出栈，再依次入队。设队列中的元素为a1,a2,an，出队并进栈的序列为a1，a2，, ， an，出栈并入队的序列为an，an-1 ，, ， a1，可见顺序队列q 中所有元素已逆置了。顺序队列的类型定义为： #define MAX 100 typedef struct int dataMAX；int front,rear； Squeue；算法描述如下：void invert(Squeue *q) int sMAX,top=0; while(q-frontrear) stop+=q-data+q-front; q-front=-1;q-rear=0; while(top0) q-dataq-rear+=s-top; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 11 页 - - - - - - - - - 2 4利用栈实现将十进制数x 转换成二进制数并输出结果。Void BNumber （ int x）算法设计题：1. 设计算法将一个带头结点的单循环链表A 分解为两个具有相同结构的链表B、C，其中： B 表中的结点为A 表中元素的顺序号为奇数的结点，而C 表中的结点为A 表中元素的顺序号为偶数的结点。（要求利用原表结点。 ）2. 已知S 为顺序栈。写出S 的存储结构类型描述。试编写算法实现将元素x 插入栈S 的入栈操作Push(S,x) 和删除栈顶元素的出栈操作Pop(S)。3. 已知队列Q 以循环队列存储。写出Q 的存储结构类型描述，并试编写算法实现将元素x 插入队列Q 的入队操作EnQueue(Q,x) 和从队列Q 中获取队首元素的函数GetTop(Q) 。4. 假设线性表L=(a1,a2, ,an) 用带头结点的单链表存储表示，试编写算法对其实现就地逆置，即利用原链表中每一个结点存储空间，使得元素的逻辑次序改变为(an, a2,a1)。5.设有两个按升序排列的单链表X 和 Y，其头指针分别为p,q 结点结构说明如下：typedef struct nodel int data; struct nodel *next node; 试设计一个算法void concat(node *p,*q) 将它们合并成一个以p 为头指针的单链表Z，使其仍然有序。6.设有序表r 长度为 n，欲在表中查找键值为Kn 的某元素。若查找成功，则返回该元素在有序表r 中的位置，若不成功，则返回0 值。用二分查找法，编写一算法完成上述操作，并给出该算法的平均查找长度。该有序表存储结构定义如下Typedef struct keytype key; Elemtype data; rec; Typedef struct rec itemmaxsize+1; int n; sqtable; 7、利用表达式的逆波兰式计算表达式的值。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 11 页 - - - - - - - - - 3 提示：设栈S，顺序读表达式的逆波兰式，读一个操作数则入栈，读一个操作符则弹栈2 次，并计算此操作，将结果重新入栈。数据结构算法2003 年真题设计求二叉树深度的算法。int BTreeDepth(btree *b) int leftdep,rightdep; if(t=NULL) return 0; else leftdep=BTreeDepth(b-left); rightdep=BTreeDepth(b-right); if(leftdeprightdep) return leftdep+1; else return rightdep+1; 2005 年真题1、二叉树采用连接存储结构，试设计一个算法计算一棵给定二叉树的单孩子结点数。（只写算法函数） （11 分）int onechild(btree *b) btree *t=b; if(t=NULL) return 0; else if(t-lchild=NULL & t-rchild!=NULL | t-lchild!=NULL & t-rchild=NULL) return onechild(t-lchild)+onechild(t-rchild)+1; else return onechild(t-lchild)+onechild(t-rchild); 2、已知线性表中的元素以值递增有序排列，并以单链表作为存储结构，试编写一高效的算法，删除表中所有值相同的多余元素（使得操作后的线性表中所有元素的值均不相同），同时释放被删除结点空间，并分析你的算法的时间复杂度（10 分）void Delete_Equal(LNode *head) /时间复杂度O(n2) int x; LNode *q,*t,*p; p=head-next; while(p!=NULL) x=p-data; q=p; while(q-next!=NULL) if(x=q-next-data) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 11 页 - - - - - - - - - 4 t=q-next; q-next=t-next; free(t); else q=q-next; p=p-next; void delinfo(LNode *h) /时间复杂度O(n) struct LNode *t,*p,*q; p=h-next; /删除重复元素t=p; while(t-next !=NULL ) if(t-data=t-next-data) q=t-next; t-next=q-next; free(q); else t=t-next; void delinfo2( LNode *h)/ 时间复杂度O(n) LNode *p,*q; p=h-next; if(p=NULL) return; while(p-next !=NULL ) if(p-data=p-next-data) q=p-next; p-next=p-next-next; free(q); else 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 11 页 - - - - - - - - - 5 p=p-next; void fun( LNode *h)/ 时间复杂度O(n) LNode *p,*q; p=h-next; while(p!=NULL & p-next !=NULL ) q=p-next; if(p-data!=q-data) p=p-next; else p-next=q-next; free(q); 2007 年真题试编写一个在带头结点的双向循环链表中值为x 的结点之前， 插入值为y 的结点的算法。（要求： 用 C 语言描述，结点类型定义为DlinkList ）Status InsertPrior-L(DlinkList *L,int x,int y) /x之前插入 y 结点 DNode *s,*p; p=L-next; while(p!=L & p-data!=x) p=p-next; if(p!=L) s=(DNode *)malloc(sizeof(DNode); s-data=y; s-next=p; s-prior=p-prior; p-prior-next=s; p-prior=s; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 11 页 - - - - - - - - - 6 2009 年真题程序填空题：单链表中，无序单链表转化为有序单链表（10 分）void sort3(LNode *L)/无序链表排序，利用单链表就地逆置的思想 LNode *p,*q,*s;/s保存新摘结点，p 保存原有链表，q 在新链表中找位置if(L-next=NULL) return; p=L-next-next; /从第二个结点开始L-next-next=NULL; while(p!=NULL) s=p; p=p-next; /p 保存原有链表q=L; while(q-next!=NULL & s-dataq-next-data) /查找插入位置q=q-next; s-next=q-next; /插入结点q-next=s; void sort4(LNode *L)/无序链表排序，利用直接选择排序思想 LNode *p,*q,*s;/p控制外层循环，q 保存最小结点，s 找位置int x; if(L-next=NULL) return; p=L-next; /第一个结点while(p!=NULL) q=p;/ 假设当前结点值是最小的s=p-next; /从第二个结点开始while(s!=NULL) /循环找最小的结点，由q 指向 if(s-datadata) q=s; s=s-next; x=p-data; /交换两个结点的数据域p-data=q-data; q-data=x; p=p-next; /下一个结点 /直接选择排序是每次从n-i+1 个结点中选择码值最小者，与第i 个结点的码值进行交换，设p 指向第 i 个结点，/min 指向无序表中码值最小的结点，算法描述如下：void selesort1(Lnode *h) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 11 页 - - - - - - - - - 7 Lnode *p,*q,*min; int x; p=h-next; while(p) min=p; q=p-next; while(q) if(q-keykey) m=q; q=q-next; if(min!=p) x=p-key; p-key=min-key; min-key=x; p=p-next; 模拟二设 n 个整数存于数组x 中，写一算法将所有偶数移到奇数之前，要求时间复杂度为O(n) 。void change(int a,int n) int i=1,j=n; while(i=j) if(i%2=0) i+; else if(j%2!=0) j-; else a0=ai;ai=aj;aj=a0; i+;j-; 模拟三1冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。void BubbleSort2(int a,int n) /相邻两趟向相反方向起泡的冒泡排序算法 int i,t,change,low,high; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 11 页 - - - - - - - - - 8 change=1;/有交换low=0;high=n; / 冒泡的上下界while(lowhigh & change) change=0; / 设不发生交换for(i=low;iai+1) t=ai; ai=ai+1;ai+1=t;change=1; / 有交换，修改标志change high-; / 修改上界for(i=high;ilow;i-) /从下向上起泡if(aiai-1) t=ai; ai=ai-1;ai-1=t;change=1; low+; / 修改下界/while /BubbleSort2 模拟四1. 设 n 个元素的线性表顺序存储在一维数组st1.maxlen的前 n 个位置上 , 试将新元素e 插入表中第i-1个和第i 个元素之间 , 写出算法。void insert(ElemType st,ElemType e,int i,int n)/插入表元素 int j; if(n=maxlen) printf(数组已满 , 不能进行插入操作!n); return ; if(in+1) printf(位置参数不正确, 不能进行插入操作!n); return ; n+; for(j=n;ji;j-) /* 结点向后移动，腾出一个位置*/ stj=stj-1; stj=e; 2. 设 Head 为带表头结点的单链表的头指针, 试写出算法 : 若为非空表 , 则输出首结点和尾结点的值(data 值) ； 否则输出: ”Empty list！”。Void disp(LNode *Head) LNode *p=Head; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 11 页 - - - - - - - - - 9 If(p-next =NULL) Printf(“Empty list!” ); Else Printf(“%c ”,p-next -data); While(p-next!=NULL) P=p-next; Printf(“%c ”,p -data); 模拟五1. 已知 S 为顺序栈。 写出 S 的存储结构类型描述。试编写算法实现将元素 x 插入栈 S 的入栈操作 Push(S,x) 和删除栈顶元素的出栈操作 Pop(S) 。#define Max 50 typedef char ElemType; typedef struct Stack ElemType stackMax; int top; SqStack; void initStack(SqStack *s) s-top=-1; void push(SqStack *s,ElemType x) if(s-top=Max-1) printf(栈上溢！ ); exit(0); s-top+; s-stacks-top=x; void pop(SqStack *s) if(s-top=-1) printf(空栈！ n); return; s-top-; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 11 页 - - - - - - - - - 10 2. 假设线性表L=(a1,a2,an) 用带头结点的单链表存储表示，试编写算法对其实现就地逆置，即利用原链表中每一个结点存储空间，使得元素的逻辑次序改变为(an, a2,a1)。struct lNode int data; struct lNode* next; ; void lreserve1( struct lNode *head) struct lNode *p,*newhead=NULL, *s; p=head-next; while (p!=NULL) /* 辅助空间为 2个*/ s=p; p=p-next; s-next=newhead; newhead=s; head-next=newhead; void lreserve2( struct lNode *head) struct lNode *p,*newhead=NULL; p=head-next; while (p!=NULL) /辅助空间为 1个 head-next=p-next; p-next=newhead; newhead=p; p=head-next; head-next=newhead; 模拟六设一个由字母组成的字符串，编写算法对它们的字母顺序进行调整，使输出时所有大写字母都在小写字母之前，并且同类字母之间的相对位置不变。（11 分）例如，原有字符串为：AbcDEfghiJKlmn 输出序列为：ADEJKbcfghilmn #include void change(char ch) int i,j; char t; i=0; while(chi!=0) if(chi=97 ) /小写，不移动i+；else /大写 t=chi; /大写字母暂存名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 11 页 - - - - - - - - - 11 j=i-1; while(j=0 & chj=97) /蒋大写字符前的小写字符后移 chj+1=chj; j-; chj+1=t; /找到大写字母的位置i+; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 11 页 - - - - - - - - -