30.现有稀疏矩阵A如下图所示，要求画出以下几种表示法。 （1）三元组表示法
（2）带行指针向量的单链表表示法 （3）十字链表示法。
四、算法阅读题(每小题6分，共12分)
31、下列算法的功能是实S串的逆序
(串均采用顺序存储方式)，请在空白处填入适当的内容。 SeqString *invert (SegString *s) { int i; char temp
for (i=0; i
s->ch[i]=s->ch[ s->length-i+1 ]; s->ch[s->length-i+1]= temp ; }
return s ;}
32.下列算法的功能是实现链栈的进栈运算，请在空白处填入适当的内容。 链栈的类型定义如下： Typedef struct stacknode { DataType data;
Struct stacknode *next; } StackNode; Typedef struct { StackNode *top;
第 6 页 (共 9 页)
}LinkStack;
Void Push(LinkStack *s,DataType x) {
StackNode p;
*p=(StackNode *)malloc(sizeof(StackNode)); p->data= x ; p->next= s->top ; s->top= p ; }
五、算法设计题
33、假设二叉树采用链接方法存储，编写一个函数复制一棵给定的二叉树。结点结构为： Copy(BiTree *T) {
if(!T)return NULL; BiTree *S=new BiTree;
if(T->Lchild) S->Lchild=T->Lchild; Copy(T->Lchild); if(T->Rchild) S->Rchild=T->Rchild; Copy(T->Rchild); } D 卷
一、单项选择题1. B 2. A 3. C 4. B 5. B 6. A 7. A 8. D 9. A 10. D 11. C 12. A 13. D 14. C 15. A 二、填空题（每小题2分，共30分）
16. O(m*n) 17. 先移动栈顶指针，后存入元素
18. hq->front==hq->rear 19. LOC(A[0][0])+(n*i+j)*k 20. 答 1 2 2 3 3 3 4 4 4 4
23、 v1,v2,v3,v6,v5,v4 v1,v2,v5,v4,v3,v6 24、哈希表查找法 25、3 26、(n+1)/2 ((n+1)*log2(n+1))/n-1
第 7 页 (共 9 页)
三、操作题（每小题5分，共20分）
27、初始：503，87，512，61，908，170，897，275，653，462 第1趟(按个位排序)170,61,462,512,503,653,475,87,897,908 第2趟(按十位排序)503,908,512,653,61,462,170,175,87,897 第3趟(按百位排序)61,87,170,275,462,503,512,653,897,908 28、加权路径长度wpl=7×2+8×2+4×3+2×4+3×4+9×2=80 29．（1）
(2) 前序：abcejfdghki 中序：jefcgkhidba 后序：jfekihgdcba 30.
四、算法设计题（每小题 6 分，共 12 分） 参考答案
31.s-length-i+1 Temp
Return(s) 32. p->data=x; p->next=s->top; s->top=p;
五、算法设计题（共8分） 参考答案 33.
Btree *copy(btree *b) {
Btree *p; If (b!=NULL) {
P=(btree *)malloc(sizeof(btree)) p->data=b->data;
p->left=copy(b->left); p->right=copy(b->right); return(p); }
Else return(NULL); }
第 8 页 (共 9 页)
第 9 页 (共 9 页)