数据结构习题 - 部分答案 - 全真模拟(3)

}MGraph;//邻接矩阵结构描述

typedef struct node {

int adjvex;//邻接点域

int weight;//边的权值

struct node *next;//链指针域

} EdgeNode;//边表结点结构描述

typedef struct {

char vertex;//顶点域

EdgeNode * firstedge;//边表头指针

} VertexNode ;//顶点表结点结构描述

typedef struct {

VertexNode adjlist[MaxNum];//邻接表

int n,e;//图中当前的顶点数和边数

} ALGraph;//邻接表结构描述

下列算法是根据一个带权图的邻接矩阵存储结构G1建立该图的邻接表存储结构G2，请填入合适的内容，使其成为一个完整的算法。

void convertM(MGraph *G1,ALGraph *G2) {

int i,j;

EdgeNode * p;

G2->n=G1->n;

G2->e=G1->e;

for(i=0;in;i++)

{

G2->adjlist[i].vertex=G1->vexs[i];

G2->adjlist[i].firstedge= (1) ; }

for (i=0;in;i++)

for (j=0;jn;j++)

if(G1->edges[i][j]

{

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

p->weight= (2) ;

p->adjvex=j;

p->next=G2->adjlist[i].firstedge;

(3) ;

} }

(1) NULL

(2) G1->edges[i][j]

(3) G2->adjlist[i].firstedge=p

11.阅读下列算法，并回答下列问题：

(1)该算法采用何种策略进行排序? 插入排序

(2)算法中R[n+1]的作用是什么? 监视哨

Typedef struct {

KeyType key;

infoType otherinfo;

} nodeType;

typedef nodeType SqList［MAXLEN］;

void sort(SqList R,int n) {

//n小于MAXLEN-1

int k;i;

for(k=n-1;k>=1;k--)

if(R[k].key>R[k+1].key)

{

R[n+1]=R[k];

for(i=k+1;R[i].key

R[i-1]=R[i];

R[i-1]=R[n+1];

} }

12．设某二叉树以二叉链表为存储结构，请写出求其高度的递归算法。 答：void BTdepth (BinTree BT,int h) {

int hr, h1;

if(BT==null) h=0; (1分) else {

BTdepth (BT→lchild,h1); 2分 BTdepth (BT→rchild,hr);

if(h1>=hr)h=h1+1; 2分 else h=hr+1

} }

四、算法填空和分析

1、ListInsert_L(LinkList L, int pos, ElemType e)

//在带头结点的单链表L中第pos个数据元素之前插入数据元素e Status ListInsert_L(LinkList L, int pos, ElemType e) {

p = L; j = 0;

while (p && j < pos-1)

{ p = p->next; ++j; } // 寻找第pos-1个结点 if (!p || j > pos-1)

return ERROR; // pos小于1或者大于表长

s = (LinkList) malloc ( sizeof (LNode)); // 生成新结点 s->data = e; s->next = p->next; // 插入L中 p->next = s; return OK; }

2、void Merge (Elem SR[], Elem TR[], int i, int m, int n) {

// 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] for (j=m+1, k=i; i<=m && j<=n; ++k) { // 将SR中记录由小到大地并入TR

if (SR[i].key<=SR[j].key) TR[k] = SR[i++]; else TR[k] = SR[j++]; }

if (i<=m) TR[k..n] = SR[i..m]; // 将剩余的SR[i..m]复制到TR if (j<=n) TR[k..n] = SR[j..n]; // 将剩余的SR[j..n]复制到TR } // Merge 3、

int Partition (Elem R[], int low, int high)

{// 交换记录子序列R[low..high]中的记录，使枢轴记录到位，并返回//其所在位

置，此时，在它之前（后）的记录均不大（小）于它 R[0] = R[low];// 用子表的第一个记录作枢轴记录 pivotkey = R[low].key; // 枢轴记录关键字 while (low

// 从表的两端交替地向中间扫描

while(low=pivotkey)

--high;

R[low] = R[high];// 将比枢轴记录小的记录移到低端 while (low

}

R[low] = R[0]; // 枢轴记录到位 return low; // 返回枢轴位置 } // Partition

4、折半查找算法：

int binsrch(JD r[],int n,int k) { int low,high,mid,found; low=1; high=n; found=0;

while((low<=high)&&(found==0)) { mid=(low+high)/2;

if(k>r[mid].key) low=mid+1; else if(k==r[mid].key) found=1; else high=mid-1; }

if(found==1) return(mid); else

return(0); }

5、设有一个表头为head的单链表。通过遍历一趟链表，将链表中所有结点按逆序链接。

Typedef struct node {int data;

struct node *next; }pointer;

Void invert(pointer head) {p=NULL;

while (head!=NULL) {u=head;

head=head->next; u->next= p ; p=u; }

had=p; }

五、编写算法：