数据结构算法设计题.doc

一、算法设计题
1. 设二叉树bt采用二叉链表结构存储。试设计一个算法输出二叉树中所有非叶子结点，并求出非叶子结点的个数。
【答案】
int count=0;
void algo2(BTNode *bt){
if (bt){
if(bt->lchild || bt->rchild){
printf(bt->data);
count++;
}
algo2(bt->lchild);
algo2(bt->rchild);
}
}
2. 阅读下列函数arrange()
int arrange(int a[],int 1,int h,int x)
{//1和h分别为数据区的下界和上界
int i,j,t；
i=1；j=h；
while(i<j){
while(i<j && a[j]>=x)j--；
while(i<j && a[j]>=x)i++；
if(i<j)
{ t=a[j]；a[j]=a[i]；a[i]=t；}
}
if(a[i]<x) return i；
else return i－1；
}
（1）写出该函数的功能；
（2）写一个调用上述函数实现下列功能的算法：对一整型数组b[n]中的元素进行重新排列，将所有负数均调整到数组的低下标端，将所有正数均调整到数组的高下标端，若有零值，则置于两者之间，并返回数组中零元素的个
数。
【答案】
（1）该函数的功能是：调整整数数组a[]中的元素并返回分界值i，使所有＜x的元素均落在a[1..i]上，使所有≥x的元素均落在a[i＋1..h]上。
（2）int f(int b[],int n) 或 int f(int b[],int n)
{ {
int p,q； int p,q；
p=arrange(b,0,n－1,0)； p=arrange(b,0,n－1,1)；
q= arrange(b,p+1,n－1,1)； q= arrange(b,0,p,0)；
return q－p； return p－q；
} }
3. 假设线性表以带表头结点的循环单链表表示。试设计一个算法，在线性表的第k个元素前插入新元素y。假如表长小于k，则插在表尾。
【答案】
void algo1(LNode *h,int k,ElemType y){
q=h; P=h->next; j=1;
while( p!=h && j<k){
q=p; p=p->next; j++;
}
s=(LNode *)malloc(sizeof(Lnode));
s->data=y;
q->next=s;
s->next=q;
}
4. 二叉排序树的类型定义如下：
typedef struct BSTNode {∥ 二叉排序树的结点结构
int data; ∥数据域
struct BSTNode *lchild, *rchild; ∥左、右孩子指针
}BSTNode,*BSTree;
设计递归算法，统计一棵二叉排序树T中值小于a的结点个数。
【答案】
int f34(BSTree root)
{
int count;
BSTNode *p;
p=root;
if ( p && p->data<a) count++;
f34(p->lchild);
return count;
}
5. 设二叉树T采用二叉链表结构存储，试设计算法求出二叉树中离根最近的第一个叶子结点。（注：结点按从上往下，自左
至右次序编号）
【答案】
BTNode * Firstleaf(BTNode *bt)
{ InitQueue(Q); //初始化队列Q
if(bt){
EnQueue(Q,bt);;
while(!EmptyQueue(Q)){
DeQueue(Q,p);
if(!p->lchild && !p->rchild) return p;
if(p->lchild) EnQueue(Q,p->lchild);
if(p->rchild) EnQueue(Q,p->rchild);
}
}
}
6. 已知一棵具有n个结点的完全二叉树被顺序存储在一维数组中，结点为字符类型,编写算法打印出编号为k的结点的双亲和
孩子结点。
【答案】
int algo2(char bt[],int n,int k){
if (k<1||k>n) return 0;
if( k==1) printf(“ %c is a root\n”, bt[1]);
else printf(“ %c’s parent is %c\n”, bt[k], bt[k/2]);
if(2*k<=n) printf(“ %c’s lchild is %c\n”, bt[k], bt[2*k]);
else printf(“ %c is not lchild\n”, bt[k]));
if(2*k+1<=n) printf(“ %c’s rchild is %c\n”, bt[k], bt[2*k+1]);
else printf(“ %c is not rchild\n”, bt[k]));
return 1;
}
7. 编写算法，将非空单链表hb插入到单链表ha的第i(0<i≤表长)个结点前。
【答案】
int algo1(LNode *ha, LNode *hb,int i){
for(p=hb;p->next; p=p->next);
for(j=1,q=ha;j<i; j++) q=q->next;
p->next=q->next;
q->next=hb->next ；
free(hb);
}
8. 设二叉树T已按完全二叉树的形式存储在顺序表T中，试设计算法根据顺序表T建立该二叉树的二叉链表结构。顺序表T定义如下：
struct tree{
int no; /* 结点按完全二叉树的编号*/
ElEMTP data; /* 数据域 */
}T[N]; /* N为二叉树T的结点数*/
【答案】
BTNode *creat_tree(struct tree T[N])
{ BTNode *p[MAX];
t=NULL;
for(i=0;i<N;i++){
s=(BTNode *)malloc(sizeof(BTNode));
s->data=T[i].data;
s->lchild=s->rchild=NULL;
m=T[i].no; p[m]=s;
if(m==1) t=s;
else { j=m/2;
if(m%2==0) p[j]->lchild=s;
else p[j]->rchild=s;
}//slse
}//for
return t;
}// creat_tree
9. 编写算法判断带表头结点的单链表L是否是递增的。若递增返回1，否则返回0。
【答案】
int algo1 (LNode *L)
{
if(!L->next) return 1;
p=L->next;
while(p->next){
if(p->data < p->next->data) p=p->next;
else return 0;
}
return 1;
}
10. 假设一线性表由Fibonacci数列的前n（n≥3）项构成，试以带表头结点的单链表作该线性表的存储结构，设计算法建立该单链表，且将项数n存储在表头结点中。Fibonacci数列根据下式求得：
1 (n=1)
f(n)= 1 (n=2)
f(n-2)+f(n-1) (n≥3)
【答案】
LNode * Creatlist(LNode *h,int n){
h=(LNode *)malloc(sizeof(Lnode));
h->data=n;
h->next=p=(LNode *)malloc(sizeof(Lnode));
p->next=q=(LNode *)malloc(sizeof(Lnode));
p->data= q->data=1;
for(i=3;i<=n;i++){
q->next=s=(LNode *)malloc(sizeof(Lnode));
s->data=p->data+q->data; s->next=NULL;
p=q;q=s;
}
return h;
}

11. 设二叉树T采用二叉链表结构存储，数据元素为字符类型。设计算法将二叉链表中所有data域为小写字母的结点改为大写
字母。
【答案】
void algo2(BTNode *bt){
if (bt){
if(bt->data>=’a’&& bt->data<=’z’)
bt->data-=32;
algo2(bt->lchild);
algo2(bt->rchild);
}
}

12. 假设线性表以带表头结点的循环单链表表示。试设计一个算法，在线性表的第k个元素前插入新元素y。假如表长小于k，则插在表尾。
【答案】
void Insertlist(LNode *h,int k,ElemType y)
{
q=h; P=h->next; j=1;
while( p!=h && j<k){
q=p; p=p->next; j++;
}
s=(LNode *)malloc(sizeof(Lnode));
s->data=y;
q->next=s;
s->next=q;
}

13. 有一带表头结点的单链表，其结点的元素值以非递减有序排列，编写一个算法在该链表中插入一个元素x，使得插入后的单链表仍有序。
【答案】
void algo1 (LNode *H, ElemTp x)
{
s=(LNode *) malloc (sizeof(LNode));
s->data=x;
q=H; p=H->next;
while ( p && p->data<=x )
{
q=p; p=p->next;
}
s->next=p; q->next=s;
}
14. 二叉排序树的类型定义如下：
typedef struct BSTNode {∥ 二叉排序树的结点结构
int data; ∥数据域
struct BSTNode *lchild, *rchild; ∥左、右孩子指针
}BSTNode,*BSTree;
设计递归算法，统计一棵二叉排序树T中值小于a的结点个数。
【答案】
int f34(BSTree root)
{
int count;
BSTNode *p;
p=root;
if ( p && p->data<a) count++;
f34(p->lchild);
return count;
}
15. 有一带表头结点的单链表，其结点的data域的类型为字符型，编写一个算法删除该链表中的数字字符。
【答案】
void Del_digit (LNode *h){
for(p=h;p->next;){
q=p->next;
if(q->data>=’0’&& q->data <=’9’)
{p->next=q->next; free(q); }
else p=q;
}
}
16. 利用栈的基本运算，编写一个算法，实现将整数转换成二进制数输出。
【答案】
void returnDtoO(int num)
{
initStack(s);
while(n)
{ k=n%2;
n=n/2;
push(s,k);
}
while(EmptyStack(s))
{ pop(s,k);
printf(“%d”,k);
}
}

17. 设二叉树T采用二叉链表结构存储，数据元素为int型，试设计一个算法，若结点左孩子的data域的值大于右孩子的data域的值，则交换其左、右子树。
【答案】
void algo2(bitreptr bt){
bitreptr x;
if (bt){
if ((bt->lchild && bt->rchild) && (bt->lchild ->data> bt->rchild->data) ) {
x= bt->lchild ;
bt->lchild= bt->rchild;
bt->rchild=x;
}
algo2(bt->lchild);
algo2(bt->rchild);
}
}
18. 设二叉树T采用二叉链表结构存储，试设计算法求出二叉树的深度。
【答案】
int Deep(BTNode *bt){
if (bt==NULL) return 0;
left=Deep(bt->lchild);
right=Deep(bt->rchild);
return (left>right?left:right)+1;
}
19. 设给定的哈希表存储空间为H（0～M-1），哈希函数的构造方法为“除留余数法”，处理冲突的方法为“线性探测法”，设计算法将元素e填入到哈希表中。
【答案】
void hash-insert(hashTable h[],int m,ElemType e){
j=e%p;
if(h[j]!=NULL) h[j]=e;
else{
do
{ j=(j+1) %m;
}while(h[j]!=NULL );
h[j]=e;
}
}
20. 对于给定的十进制正整数,打印出对应的八进制正整数。（利用栈）
【答案】
void DecToOct(int num)
{
initStack(s); //初始化栈
while(n)
{ k=n%8;
n=n/8;
push(s,k);
}
while(EmptyStack(s)) //判断栈是否为空
{ pop(s,k);
printf(“%d”,k);
}
}
21. 一个正读和反读都相同的字符序列称为“回文”。例如“abcba”和“1221”是回文，而“abcde”不是回文。试写一个算法，要求利用栈的基本运算识别一个以@为结束符的字符序列是否是回文。
【答案】
int Pair(char *str ) {
InitStack(s)；
p=str
for ( ; *p!=’@’; p++ )
Push(s,*p);
while(StackEmpty(s)) {
Pop(s,y);
if(y!=*str++ ) return 0;
}
return 1;
}
22. 有一带表头结点的单链表，其结点的元素值以非递减有序排列，编写一个算法删除该链表中多余的元素值相同的结点(值相同的结点只保留一个)。
【答案】
void Delsame (LNode *h){
if(h->next) {
for(p=h->next;p->next;){
q=p->next;
if(p->data==q->data){
p->next=q->next;
free(q);
}
else p=q;
}
}
23. 编写一个算法，判断带表头结点的单链表是否递增有序。
【答案】
int fun(LNode *h )
{ p=h->next;
while(p->next)
{ q=p->next ;
if(q->data>p->data) return 0;
p=q;
}
return 1;
}
24. 假设有两个带表头结点的单链表HA和HB，设计算法将单链表HB插入到单链表HA的第i(0<i≤表长)个结点前。
【答案】
void fun(LNode *ha, LNode *hb,int i)
{ for(p=hb;p->next; p=p->next);
for(j=1,q=ha;j<i; j++)
q=q->next; ;
p->next=q->next;
q->next= hb->next ；
free(hb);
}
25. 假设以带头结点的单链表表示有序表，单链表的类型定义如下：
typedef struct node{
DataType data;
struct node *next
}LinkNode, *LinkList;
编写算法，从有序表A中删除所有和有序表B中元素相同的结点。
【答案】(空)
26. 设二叉树T采用二叉链表结构存储，数据元素为字符类型。设计算法分别求出二叉链表中data域为英文字母和数字字符的
结点个数。
【答案】
int letter=0，digit=0； /*全局变量*/
void algo2(BTNode *bt){
if (bt){
if(bt->data>=’A’&& bt->data<=’Z’|| bt->data>=’a’&& bt->data<=’z’) letter ++;
if(bt->data>=’0’&& bt->data<=’9’) digit ++;
algo2(bt->lchild);
algo2(bt->rchild);
}
}
27. 假设以单链表表示线性表,单链表的类型定义如下:
typedef struct node {
DataType data;
struct node *next;
} LinkNode, *LinkList;
编写算法,将一个头指针为head且不带头结点的单链表改造为一个含头结点且头指针仍为head的单向循环链表,并分析算法的时间复杂度。
【答案】
LinkList f34(LinkList head)
{
LinkList p,s;
p=head;
while (p->next) p=p->next;
s=(LinkList)malloc(sizeof(LinkNode));
s->next=head;
p->next=s;
head=s;
return head;
}
时间复杂度为:O(n)
28. 假设有向图以邻接表方式存储，编写一个算法判别顶点vi到顶点vj是否存在弧。
【答案】
int IsArcs(ALgraph G,int i,int j) {
/* 判断有向图G中顶点i到顶点j是否有弧,是则返回1,否则返回0*/
p=G[i].firstarc;
while (p!=NULL) {
if(p->adjvex ==j)
return 1;
p=p->nextarc;
}
return 0;
}
29. 设二叉树T采用二叉链表结构存储，数据元素为字符类型。设计算法求出二叉链表中data域为大写字母的结点个数。
【答案】
int count=0；/* count为全局变量*/
void algo2(BTNode *bt){
if (bt){
if(bt->data>=’A’&& bt->data<=’Z’)
count++;
algo2(bt->lchild);
algo2(bt->rchild);
}
}
30. 假设带表头结点的双向循环链表定义如下：
typedef struct dunode{
char data;
struct dunode *prior, *next;
}DuNode;
现用该链表存放字符串，编写一个算法，判断该字符串是否中心对称关系。例如字符串“xyzzyx”和“xyzyx” 都是中心对称的。
【答案】
int fun(DuNode *h )
{ p=h->next;q=h->prior;
while(p!=q && p->prior!=q)
{
if(q->data==p->data)
{ p=p->next;q=q->prior;}
else return 0;
}
return 1;
}
31. 假设以带头结点的单链表表示线性表，单链表的类型定义如下：
typedef int DataType;
typedef struct node {
DataType data;
struct node * next;
} LinkNode, * LinkList;
编写算法，删除线性表中最大元素(假设最大值唯一存在)。函数原型为：
void f34(LinkList head) ;
【答案】
void f34(LinkList head)
{
int e;
LinkList p,q,s,spre; //s指向最大值的那个结点
spre=head; s=head->next;
q=s; p=s->next;
while (p)
{
if(s->data<p->data)
{ s=p; spre=q; }
q=p;
p=p->next;
}
e=s->data;
spre->next=s->next;
free(s);
}