西电21秋数据结构模拟测试一答案
一 填空题（每空1分，合计20分）
1. 数据的逻辑结构，数据的存储结构
2. 若干个
3. n+1，n，n(n+1)/2，n(n-1)/2
4. s->next=p->next，p->next=s
5. SXSSXSXX
6. 9392，1228
7. 空树
8. (p->lchid==NULL && p->rchild==NULL)
9. 4
10. 先序
11. 6,261
12. n-1
13. O(n+e)
二 选择（每题2分，合计30分）
1.C 2.D 3.B 4.D 5.A 6.C 7.D 8.A 9.D 10.B
11.C 12.D 13.A 14.C 15.C
三 应用题（每题6分 合计36分）
1．由3种遍历序列的特点可知，先序遍历—每棵子树的根结点总在该子树中其他结点前被遍历；中序遍历—左子树结点在前，根结点次之，右子树结点最后；后序遍历—每棵子树的根结点总在该子树中其他结点后被遍历。由此可推断得先序序列空格中依次填ADKJ,中序序列中依次填BHG，后序序列中依次填DIEC
2. 顺序表的优点是可以随机访问数据元素而且不需要额外的空间存储元素间逻辑关系，缺点是表大小固定，增减结点需要移动大量元素。链表的优点是增减元素非常方便，只需要修改指针内容，缺点是只能进行顺序访问，另外每个结点上增加指针域造成存储空间增大。
3. 图G如图1所示。
（1）由图11.21可见，图G中有环存在，因此对图G进行拓扑排序并不能输出所有顶点，即有顶点不在拓扑序列中。
（2）n个顶点的完全有向图有n(n-1)条边。图G有4个顶点，5条边，若成为完全有向图还需要4*(4-1)-5=7条边。
4. 因为n=8， =n/m，依题意，要求新插入数据的平均查找次数不多于2.5次，即查找不成功的查找长度小于等于2.5，对于线性探测法，不成功的ASL=(1+1/(1- )2)/2，即：(1+1/(1- )2)/2≤2.5，可求得m≥2n，一般m取素数，所以取m=17,p=17。
H(key)=key%17
H(1)=1%17=1
H(9)=9%17=9
H(25)=25%17=8
H(11)=11%17=11
H(12)=12%17=12
H(35)=35%17=1 冲突 H(35)=(1+1)%17=2
H(17)=17%17=0
H(29)=29%13=3
构造散列表如图1所示。
下标 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
k 17 1 35 29 25 9 11 12
探查次数 1 1 2 1 1 1 1 1
图1 线性探测再散列法构造的散列表
ASL成功=(1*7+2*1)/8=1.125
ASL不成功=(5+4+3+2+1+1+1+1+3+2+1+3+2+1+1+1+1)/17≈1.94
5.采用冒泡排序方法排序的各趟结果如下：（加框为每次冒出元素）
初始序列： 25，18，60，40，7，21，32，73，68
第一趟： 7，25，18，60，40，21，32，68，73
第二趟： 7，18，25，21，60，40，32，68，73
第三趟： 7，18，21，25，32，60，40，68，73
第四趟： 7，18，21，25，32，40，60，68，73
第五趟： 7，18，21，25，32，40，60，68，73
第五趟无元素交换，排序结束。
6．依题意，本题对应的哈夫曼树如图所示。按照“左0右1，从根到叶”的编码规则，各字符对应的哈夫曼编码如下： a:011 b:10 c:00 d:010 e:11
四 编程题（每题7分 合计14分）
1. 算法如下：
int onechild(bitree *t)
{
int ml,mr,m=0;
if(t==NULL)
return 0;
if((t->lchild==NULL && t->rchild!=NULL)
||( t->lchild!=NULL && t->rchild==NULL))
m=1;
ml=onechild(t->lchild);
mr=onechild(t->rchild);
return ml+mr+m;
}
2. 以顺序表实现算法如下：
void del(sqlist *A,datatype x,datatype y)
{
int i=0,j=0;
while(i<=A->last)
{
if(A->data>=x && A->data<=y)
j++;
else if(A->data>y)
A->data=a->data;
i++;
}
A->last=A->last-j;
}
算法对顺序表进行了一次扫描，前移了部分元素，所以时间复杂度为O(1)。
页:
[1]