825数据结构答案14

河南科技大学

2014年硕士研究生入学考试试题答案及评分标准

考试科目代码： 825 考试科目名称： 数据结构

一、判断题（每题1分，共5分）；

1、╳ 2、√ 3、╳ 4、╳ 5、√ 二、填空题（每空1分，共5分）：

h-1h

1、顺序 2、2、 2-1 3、事件、 活动 三、单项选择题（每题1分，共5分）：

1、C 2、B 3、B 4、C 5、B 四、简答题（每题5分，共15分）：

1、 在顺序表中逻辑上相邻的数据元素在物理位置上也相邻；在单链表中逻辑上相邻的数据元素在物理存储

位置上不一定相邻。

2、 采用链式存储结构，它根据实际需要申请内存空间，而当不需要时又可将不用的结点空间返还给系统。

在链式存储结构中插入和删除操作不需要移动元素。

10

3、根据二叉树的性质二，最多有2-1=1023个结点。

4、导致遍历序列不一致的因素有：开始遍历的顶点不同；存储结构不同；在邻接表情况下，邻接点的顺序不同。

5、若对查找表只查询某个特定的元素是否存在，或检索某个特定的元素的各种属性，此类查找表为静态查找表。如折半查找。若在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素，则此类表为动态查找表。如二叉排序树的查找。

2

6、是快速排序。因为当序列已有序时，快速排序已蜕化为冒泡排序，时间复杂度为O（n）。 五、简述算法的功能（每题5分，共10分）

1、利用数组将栈S中的元素逆置 2、利用栈将栈队列中的元素逆置

六、应用题（共60分）：

1、 C、A、T、E、D的权重分别是：3、9、4、4、1,每个字母的哈夫曼编码是：（10分） C 0000 A 1 T 001 E 01 D 0001

电文的编码长度为：45 （2分） 2、二叉树是：（8分）

3、哈希表是：（9分）

A B C E D G F I H 第1页（共4页）

0 1 2 3 4 5 6 7 8 9 10

11 22 ASL=5/3 （2分）

4、g最早和最晚发生时间为：15和16 （2分）

关键路径是：a, b, e, h, k （10分）

5、邻接矩阵是：（3分）

0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 逆邻接表：（3分）

47 92 16 3 7 29 8

0 1 2 3 4 4 5 A B C D E E F ∧ 4 0 1 0 ∧ 4 ∧∧ 5 4 ∧ ∧ 3 2 3 2 ∧ ∧

6、快速排序的每次结果如下：

(14 49 36) 52 (80 58 61) （2分）

14 (49 36) 52 (58 61) 80 （2分） 14 36 49 52 58 61 80 （2分）

7、对应的树是：（5分）

A B

C E D G F H I 七、算法设计题（第1、3题各10分，第2题15分，共35分）：

1、 typedef struct LNODE{

ElemType data； 第2页（共4页）

struct LNODE *next；

}LNODE，*LinkList；

Status creatlist（LinkList &L, int n）{ L=(LinkList)malloc(sizeof(LNode))；

L→next=NULL; for(i=n;i>0;--i)){

p=(LinkList)malloc(sizeof(LNode)); scanf(&p→data);

p→next =L→next； L→next=p； } return OK；

}// creatlist 2、typedef struct QLNODE{

QelemType data； struct QLNODE next；

}QLNODE， *Queue；

status InitQueue（Queue &Q）{ //队列初始化

Q=（Queue）malloc(sizeof（QLNODE）)； if(!Q) exit(OVERFLOW); Q->next=Q； retutn OK；

}// InitQueue

status EnQueue(Queue &Q, QelemType x){ //插入元素x为Q的新的队尾元素

p=（Queue）malloc(sizeof（QLNODE）)； if(!p) exit(OVERFLOW)；

p->data=x； p->next=p； Q=p； return OK；

}// EnQueue

status DeQueue（Queue &Q, QelemType &x）{

//若队列不空，则删除Q的队头元素，用x返回其值 if（Q==Q->next） retutn INFEASIBLE； p=Q->next->next； x=p->data； Q->next->nexp=p->next； free（p）； return OK；

}// DeQueue

3、typedef struct BiTNode{

TelemType data； struct BiTNode next；

} BiTNode，*BiTree；

status Ins（BiTree &t， BiTree p， TElemType x）{

//将数据信息为x的结点插入到二叉树t 中，作为结点p的左孩子结点 if（t==NULL） return ERROR；

else { q=（BiTree ）malloc（sizeof（BiTNode））；

q->data=x； q->lchild=NULL； q->rchild=NULL；

第3页（共4页）

if（p->lchild！=NULL） q->rchild=p->lchild； p->lchild=q； } return OK；

}//Ins

第4页（共4页）