专升本考试计算机专业《数据结构》算法专题
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(\； scanf(\while(x!=tag)
{p=(Lnode*)malloc(sizeof(Lnode)); p->data=x;
p->next=h->next; h->next=p;
scanf(\ }
return h; }
3．解本题的基本思想是：先将顺序队列q中所有元素出队，并依次进入顺序栈s中，然后出栈，再依次入队。设队列中的元素为a1,a2,?,an，出队并进栈的序列为a1，a2，?，an，出栈并入队的序列为an，an-1，?，a1，可见顺序队列q中所有元素已逆置了。顺序队列的类型定义为：
#define MAX 100 typedef struct
{int data[MAX]；
int front,rear； }Squeue；
算法描述如下：
void invert(Squeue *q) {int s[MAX],top=0;
while(q->front
q->data[q->rear++]=s[--top]; }
1
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 item［maxsize+1］; int n; }sqtable;
7、利用表达式的逆波兰式计算表达式的值。
2
提示：设栈S，顺序读表达式的逆波兰式，读一个操作数则入栈，读一个操作符则弹栈2次，并计算此操作，将结果重新入栈。
数据结构算法
2003年真题
设计求二叉树深度的算法。 int BTreeDepth(btree *b) {
int leftdep,rightdep; if(t==NULL) return 0; else { } }
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);
leftdep=BTreeDepth(b->left);
rightdep=BTreeDepth(b->right); if(leftdep>rightdep) return leftdep+1; else
return rightdep+1;
}
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
{ 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