824数据结构与算法设计答案A

西安科技大学

2013年硕士研究生入学考试试题答案A

─────────────────────────────────

科目编号：824 科目名称：数据结构与算法设计

答案A： 一、 二、

单选题（2×15=30分） BDDAC BBCDC ABABC 填空题（2×10=20分）

（1） 运算/操作 （2） 4 （3） 90 （4） h （5） 2m-1 （6）top=p （7）队尾 （8）5 （9）n-1 （10）直接插入排序

三、

简答题（任选5道题，每小题8分，共40分）（只要答出要点即可） 顺序表：空间利用率高，插入、删除运算效率低；

链表：插入、删除运算效率高，不必事先估计“容量”， 空间利用率低。 （2）“假溢出”现象是

处理方式有 判断队满和队空

（3）二叉树的顺序存储方式是一维数组存储二叉树，且能反映各节点之间的逻辑关系； 优点是可方便实现二叉树的基本操作，缺点是，除非是完全二叉树，否则空间浪费很大。

（4）邻接矩阵：

邻接表、逆邻接表：不方便判断某两个顶点是否有边； 两种方式各有利弊。 （5）顺序查找，（n+1）/2;

二分查找，(（n+1）/n/)log2(n+1)-1，要求是有序表，且存储结构式顺序结构； 分块查找，（n/s+s）/2+1,要求索引有序，块间通常用二分查找，块内通常用顺序查找。

（6）什么样的图其最小生成树是唯一的？用Prim和Kruskal算法求最小生成树的时间

复杂度各为多少？他们分别适合于哪种类型的图？

答：（a）具有n的结点，n-1条边的连通图其生成树是唯一的。 （b）n的结点，e条边的无向连通图求最小生成树的时间分别为 Prim: O(n2)； Kruskal:O(e*log2e)。 （c）Prim适应于稠密图（点少边多）；

共3 页 第1页

（1）线性表：每个元素有一个直接前驱和一个直接后继（除表头和表尾外）；

（d）Kruskal 适应于稀疏图（点多边少）。

四、

应用题（10×4=40分）

（1）（a）{96,63,78,25,57,11,44} （也可画出堆形式的图） （5分，错一个位置扣2分）

（b）{63,57,44,25,11,78,96} （也可画出堆形式的图） （5分，错一个位置扣2分） （2）（a）

0 1 56 2 23 3 79 4 5 38 6 7 62 8 41 9 18 10 （5分，错一个位置扣2分）

（b）ASL=11/7。 （5分）

（3）（a）（5分，错一个位置扣2分） （b）（5分，错一个位置扣2分）

（4）答：(1) (2)V1,V2,V4,V6,V3,V5 1 2 36 25 1 2 4 29 6 10 30 3 3 5 18 38 4 5

42

(3) 顶点集合V(G)={V1,V2,V3,V4,V5,V6}

边的集合 E(G)={(V1,V2),(V2,V3),(V1,V4),(V4,V5),(V5,V6)}

(4) V1到V3最短路径为67: (V1—V4—V3) 五、算法设计题（10×2=20分） （1）void exchange(NODE *t )

{

NODE *P； if (t!=NULL) { P=t->lchild; t->lchild=t->rchild; t->rchild=P; exchange(t->lchild); exchange(t->rchild); }

共3 页 第2页

6

}

(2) 以二叉链表为存储结构，编写按层次顺序（同一层自左至右）遍历二叉树的算法。 【分析】根据层次遍历的定义，同层结点A和B，若结点A先于结点B访问，则其子结点也先于B的子结点访问，符合先进先出的处理规律。在二叉树中，在访问某个结点的时候，可以得到其指向子结点的指针，所以由上面层次访问的特点，利用队列，在访问某个结点的时候，让指向其子结点的指针入队列，随后的访问结点可从队列得到。 答

typedef struct Node { DataType data; struct Node *LChild; struct Node *Rchild; }BiTNode, *BiTree;

void LayerOrder(BiTree T) { InitQueue(Q);

EnQueue(Q,T);

while(!QueueEmpty(Q)) { DeQueue(Q,p); visit(p);

if(p->LChild) EnQueue(Q,p->LChild); if(p->RChild) EnQueue(Q,p->RChild); }

（3）解答

① search=0 ②qc=qc->next ④ pa=fa->next ⑤fa->next=qc

共3 页 ③fa=pa ⑥ pc->next=pa

第3页

本文来源：https://www.bwwdw.com/article/tr5o.html