一、选择题(每题2分，共20分) 1 B 2 C 3 C 4 A 5 D 6 B 7 D 8 A 9 A 10 C 二、填空题(每空2分，共30分) 1 集合 2 指针 3 s->next =p->next 4 0 5 6 7 6 9 n*(n-1)
三、问答题(共30分)
1. (每小问1分) （1）a （2）b,d,f,h,i,j,k （3）a,c,g （4）i
（5）4 2.(1) （2分）
6 8 p->next=s 串中包含的空格数 35 n+1 线性结构 树形结构 图状结构 10 有序 第 6 页 共 8 页
ABDEIH
CF(2)DHEBIFCA（3分） 3. （3分）
EIJGBKCFAD 4. （5分）度为k的分支结点和度为0的叶子结点分别为x和y个，根据树的性质，有如下等式
k*x+1=n (1) x+y=n (2)
综合两式y=n-(n-1)/k
5. （8分）
（1） (2分) (2) (2分) a的度=2
b的度=2 c的度=2 d的度=3
e的度=3
cde（3）(4分)
ab
深度优先遍历为：abdce
第 7 页 共 8 页
广度优先遍历为：abedc 6. （4分）
( 顶点1 ， 顶点2 ， 权值 ) (漏写、错写、多写每行扣1分) ①( 1 , 3 , 1 ) ②( 3 , 6 , 4 ) ③( 6 , 4 , 2 ) ④( 3 , 2 , 5 ) ⑤( 2 , 5 , 3 )
四、算法填空题(每空2分，共10分) p->next!=s 1 (或pre->next->next!=s) 2 4 p=p->next InitStack(S) 3 s(或p->next) 5 Pop(S,a) 五、算法设计题（共10分）
void Del(Linklist &L,ElemType x)(1分) {
p=L; (1分) q=p->next; (1分)
while(q!=NULL) (2分) {
if (q->data==x) (1分)
{p->next=q->next; free(q);} (2分) else p=q; (1分) q=p->next; (1分) }
}
算法描述中无变量定义，不扣分；用其他程序设计语言正确描述算法，不扣分；用流程图正确描述算法，不扣分；用文字正确描述算法，扣2分。
第 8 页 共 8 页