数据结构试题库答案算法设计题

算法设计题(10分)

(1)阅读下列递归算法,写出非递归方法实现相同功能的C程序。

void test(int &sum)

{ int x;

scanf(x);

if(x=0) sum=0 else

printf(sum);

}

#include (1分)

void main() (1分)

{ int x,sum=0,top=0,s[]; (1分)

scanf(“%d”,&x)

while (x0)

{ s[++top]:=a; scanf(“%d”,&x); }(3分)

while (top)

sum+=s[top--]; (3分)

printf(“%d”,sum); (1分)

}

(2)试写出把图的邻接矩阵表示转换为邻接表表示的算法。

设图的邻接矩阵为g[n][n](针对无向图),定义邻接表节点的类型为

struct edgenode

{ int adjvex;

edgenode next;

}

typedef edgenode *adjlist[n];

void matritolist (int g[][], adjlist gl, int n )

{ edgenode *p, *q;

for (int i=0 i

for (int i=0; i

for ( int j=0; j

{ if (g[i][j]!=0 )

p = ( edgenode *) malloc(sizeof (edgenode));

p->adjvex=j;

p->next=null;

if (gl[i]=null) { gl[i]==p; q=p; }

else ( q->next=p; q=p; }

}

}

(3)阅读算法并根据输入数据画出链表。

linklist createlistr1( )

{ char ch;

linklist head=(listnode*)malloc(sizeof(listnode));

listnode *p,*r;

r=head;

while((ch=getchar( ))!=‵\n′)

{ p=(listnode*)malloc(sizeof(listnode));

while (p) p=(listnode*)malloc(sizeof(listnode));

p–>data=ch; r–>next=p; r=p;

}

r–>next=NULL;

return(head);

}

输入数据为:text8

(4)阅读算法并指出下列各段程序完成的功能。

void add_poly(Lnode *pa,Lnode *pb)

{ Lnode *p,*q,*u,*pre; int x;

p=pa->next; q=pb->next; pre=pa;

while((p!=NULL) && ((q!=NULL))

{ if (p->exp exp)

{ pre=p; p=p->next; }

else if (p->exp= =q->exp)

{ x=p->coef+q->coef;

if (x!=0) { p->coef=x; pre=p;}

else { pre->next=p->next; free(p); }

p=pre->next; u=q; q=q->next;

free(u);

}

else

{ u=q->next;q->next=p;pre->next=q;

pre=q; q=u;

}

}

if (q!=NULL) pre->next=q;

free(pb);

}

两个多项式相加

(5)阅读下面的程序,说明程序的具体功能。

typedef int elementype

typedef struct node

{ elemtype data;

strunct node *next;

}linklist;

void function( linklist *head, elemtype x )

{ linklist *q, *p;

q=head;

p=q-next;

while (p !=NULL) && (p->data != x )

{ q=p; p=p->next; }

if (q==NULL) printf (“there is no this node ::\n”);

else { q ->next =p ->next ; free (p); }

}

该程序的功能是:在带头结点的单链表中,删除单链表中枝为z的数据元素。

(6)阅读下面的程序,说明程序的具体功能。

void function( )

{ initstack(s);

scanf (“%”,n);

while(n)

{ push(s,n%8); n=n/8; }

while(! Stackempty(s))

{ pop(s,e); printf(“%d”,e); }

}

该程序的功能是:10进制数转换为8进制

(7)阅读下面的程序,说明程序的具体功能。

void print(int w)

{ int i;

if ( w!=0)

{ print(w-1);

for(i=1;i

printf(“%3d,”,w);

printf(“/n”);

}

}

运行结果:

1,

2,2,

3,3,3,

(8)阅读下面的程序,分别说明程序中四个for循环和语句++cpot[col];的具体功能。

void FastTransposeSMatrix(Matrix M, Matrix &T)

{ T.mu=M.nu; T.nu=M.mu; T.tu=M.tu;

if (T.tu)

{ for (col=1;col

for (t=1;t

cpot[1]=1;

for (col=2;col

cpot[col]=cpot[col-1]+num[col-1];

for (p=1;p

{ col=M. item[p].j;

q=cpot[col];

T.item[q].i=M.data[p].j;

T.item [q].j=M. item[p].i;

T.item[q].e=M.data[p].e;

++cpot[col];

}

}

return OK;

}

第一个for循环:初始化每一列中非零元素的个数为

第二个for循环,计算每一列中非零元素的个数;

第三个for循环,计算每一列的第一个元素的首地址;

第四个for循环,转置过程;

++cpot[col]:语句的功能是当每一列进行一次转置后,其位置向后加1。

(9)已知二叉树的二叉链表存储表示,指出建立如图所示树的结构时输入的字符序列。

typedef struct BiTNode

{ char data;

struct BiTNode *lchild,*rchild;

} BiTNode;

void CreateBiTree( BiTNode *T)

{ char ch;

scanf(&ch);

if(ch= =‘ ‘) T=NULL;

else{ T=(BiTNode *)malloc(sizeof(BiTNode));

while (T==NULL)

T=(BiTNode *)malloc(sizeof(BiTNode));

T–>data=ch;

CreateBiTree(T–>lchild);

CreateBiTree(T–>rchildd);

}

}

ABVDVVCEVFGVVV8

(10)已知二叉树的二叉链表存储表示,写出中序遍历的递归算法。

typedef struct BiTNode

{ char data;

struct BiTNode *lchild,*rchild;

} BiTNode,*BiTree;

void inorder( BiTNode *p)

{ if (p!=NULL)

{ inorder(p–>lchild);

printf(“%c”,p–>data)

inorder(p–>rchild);

}

}

(11)阅读下面的程序,分别指出程序中三个for循环、整个程序以及语句scanf("%d,%d",&G.vexnum,&G.arcnum);的功能。

void funcgraph(MGraph &G)

{int i,j,k,w;char v1,v2;

printf("Input vexnum & arcnum:");

scanf("%d,%d",&G.vexnum,&G.arcnum);

printf("Input Vertices:");

for (i=0;i

scanf("%c",&G.vexs[i]);

for (i=0;i

for (j=0;j

G.arcs[i][j]=0;

for (k=0;k

{printf("Input Arcs(v1,v2 & w):\n");

scanf("%c%c,%d",&v1,&v2,&w);

i=LocateVex(G,v1);

j=LocateVex(G,v2);

G.arcs[i][j]=w; G.arcs[j][i]=w;

}

}

第一个for循环:将图中的顶点输入到数组G.vexs[i];

第二个for循环,初始化邻接矩阵;

第三个for循环,将图中边信息存入数组G.vexs[i]中;

本程序的功能是:创建图的邻接矩阵;

scanf("%d,%d",&G.vexnum,&G.arcnum);语句的功能输入定点数和图中的边数。

设哈希(Hash)表的地址范围为~17,哈希函数为:H(K)=K MOD 16。

K为关键字,用线性探测法再散列法处理冲突,输入关键字序列:

(10,24,32,17,31,30,46,47,40,63,49)

造出Hash表,试回答下列问题:

(1)画出哈希表的示意图;

(2)若查找关键字63,需要依次与哪些关键字进行比较?

(3)若查找关键字60,需要依次与哪些关键字比较?

(4)假定每个关键字的查找概率相等,求查找成功时的平均查找长度。

解:(1)画表如下:

(2) 查找63,首先要与H(63)=63%16=15号单元内容比较,即63vs31,no;

然后顺移,与46,47,32,17,63相比,一共比较了6次!

(3)查找60,首先要与H(6)=6%16=12号单元内容比较,但因为12号单元为空(应当有空标记),所以应当只比较这一次即可。

(4) 对于黑色数据元素,各比较1次;共6次;

对红色元素则各不相同,要统计移位的位数。“63”需要6次,“49”需要3次,“40”需要2次,“46”需要3次,“47”需要3次,

本文来自企鹅号 - Java程序猿媒体

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

Gym 100952J&&2015 HIAST Collegiate Programming Contest J. Polygons Intersection【计算几何求解两个凸多边形的相交面积板子题

J. Polygons Intersection time limit per test:2 seconds memory limit per test:64 ...

2797
来自专栏用户画像

5.3.1图的遍历

图的遍历是指从图中的某一顶点出发,按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次。注意到树是一种特殊的图,所以树的遍历实际上也可以看作是一种特...

901
来自专栏计算机视觉与深度学习基础

Leetcode 164 Maximum Gap 桶排序好题

Given an unsorted array, find the maximum difference between the successive ele...

2175
来自专栏青玉伏案

算法与数据结构(十四) 堆排序 (Swift 3.0版)

上篇博客主要讲了冒泡排序、插入排序、希尔排序以及选择排序。本篇博客就来讲一下堆排序(Heap Sort)。看到堆排序这个名字我们就应该知道这种排序方式的特点,就...

24910
来自专栏Golang语言社区

Go语言 -浮点数

Go提供了两种size的浮点数,float32和float64。它们的算术规范是由IEEE754国际标准定义,现代CPU都实现了这个规范。 浮点数能够表示的范...

3564
来自专栏owent

POJ PKU 2549 Sumsets 解题报告

题目链接http://acm.pku.edu.cn/JudgeOnline/problem?id=2549

901
来自专栏小詹同学

Leetcode打卡 | No.22 括号生成

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

2401
来自专栏我是业余自学C/C++的

线性表——链式描述(双向链表)

1373
来自专栏海天一树

NOIP 2013初赛普及组C/C++答案详解

试题和答案: https://wenku.baidu.com/view/aa2bc10b5022aaea988f0f77.html?re=view

1384
来自专栏null的专栏

C/C++——柔性数组

1、问题来源 在博文数据结构和算法——kd树中,在构建kd树的过程中,有如下的一段代码: #define MAX_LEN 1024 typedef struc...

3054

扫码关注云+社区

领取腾讯云代金券