数据结构常用算法

专升本考试计算机专业《数据结构》算法专题

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->frontrear) s[top++]=q->data[++q->front]; q->front=-1;q->rear=0; while(top>0)

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