2008-2009学年第一学期期末试卷（A）答案
课程名称 数据结构 拟题人 何汉阳
一、选择题（每小题2分，共40分）
1～5、CDCDA 6～10、DCDCD 11～15、DBADD 16～20、DBCBD
二、判断题（每小题1分，共15分）
1～5、√××√× 6～10、××√√√ 11～15、×××√×
三、解：（15分） 从顶点0出发 U={0}, V-U={1, 2, 3, 4, 5, 6} Adjvex / 0 0 0 0 0 0 k=5 Lowcost 0 28 ∞ ∞ ∞ 10 ∞ (0, 5) 0??028???10U={0, 5}, V-U={1, 2, 3, 4, 6} 128016??Adjvex / 0 0 0 5 0 0 k=4 2???3??16012??Lowcost 0 28 ∞ ∞ 25 0 ∞ (5, 4) ???12022?U={0, 5, 4}, V-U={1, 2, 3, 6} 4????22025Adjvex / 0 0 4 5 0 4 k=3 5??10???250Lowcost 0 28 ∞ 22 0 0 24 (4, 3) 6???14?1824?U={0, 5, 4, 3}, V-U={1, 2, 6} Adjvex / 0 3 4 5 0 3 k=2 Lowcost 0 28 12 0 0 0 18 (3, 2) U={0, 5, 4, 3, 2}, V-U={1, 6} Adjvex / 2 3 4 5 0 3 k=1 Lowcost 0 16 0 0 0 0 18 (2, 1) U={0, 5, 4, 3, 2, 1}, V-U={ 6} Adjvex / 2 3 4 5 0 1 k=6 Lowcost 0 0 0 0 0 0 14 (1, 6) U={0, 5, 4, 3, 2, 1, 6}, V-U={ } 四、解：（10分）
void DelSameNode(LinkList *L) //L是递增有序的单链表 { LinkList *p, *pre, *q;
pre = L; //pre是p所指向的前驱结点的指针
p = pre->next; //p是工作指针。设链表中至少有一个结点 while(p != NULL)
if(p->data == pre->data) //处理相同元素值的结点 { q=p; p=p->next; free(q); } //释放相同元素值的结点 else
{ pre=p; p=p->next; } //处理前驱，后继元素值不同 pre->next=p； //置链表尾 }
??????18??24????0??- 6 -
14五、解：（10分）
SPMatrix *TransM2(SPMatrix *A) { SPMatrix *B; int i,j,k;
int num[n+1],cpot[n+1];
B=malloc(sizeof(SPMatrix)); /*申请存储空间*/
B->mu=A->nu; B->nu=A->mu; B->tu=A->tu; /*行、列、元素个数*/ if(B->tu>0) /*有非零元素则转换*/
{ for (i=1;i<=A->nu;i++) num[i]=0;
for (i=1;i<=A->tu;i++) /*求矩阵A中每一列非零元素的个数*/ { j= A->data[i].j; num[j]++; }
cpot[1]=1; /*求矩阵A中每一列第一个非零元素在B.data中的位置*/ for (i=2;i<=A->nu;i++)
cpot[i]= cpot[i-1]+num[i-1];
for (i=1; i<= (A->tu); i++) /*扫描三元组表*/ { j = A->data[i].j; /*当前三元组的列号*/
k = cpot[j]; /*当前三元组在B.data中的位置*/ B->data[k].i = A->data[i].j; B->data[k].j = A->data[i].i; B->data[k].v = A->data[i].v; cpot[j]++; } /*for i */ } /*if (B->tu>0)*/
return B; /*返回的是转置矩阵的指针*/ }
六、解：（10分）
#include
scanf(\{ SSELEMENT r[MAXSIZE]; for(i=0; i printf(\int seq_search(int k, SSTABLE st) scanf(\{ int j=0; i=seq_search(k, st); st.r[st.len].key=k; printf(\ while(st.r[j].key!=k) j++; } if(j return j+1; else return 0; } - 7 -