数据结构期末考试试卷(通信14)-A答案及评分标准.doc

Ａ卷

2015—2016学年第1学期
《数据结构与算法》试卷答案及评分标准

专业班级 通信1401-02
姓 名
学 号
开课系室 计通学院软件工程系
考试日期 2015-11-08

题 号
一
二
三
四
五
总分
得 分

阅卷人

一、填空题（每空1分，共10分）
1．尾 首
2．O(1) O(n)
3．128 208
4. abedc abcde
5．2n n+1
二、单项选择题（每题2分，共20分）
1、C 2、B 3、D 4、A 5、A
6、C 7、A 8、C 9、C 10、D
三、应用题（每小题10分，共40分）
1、已知一棵二叉树的前序遍历的结果是ABKCDFGHIJ, 中序遍历的结果是KBCDAFHIGJ, 试画出这棵二叉树，并保留中间过程。
当前序序列为ABKCDFGHIJ，中序序列为KBCDAFHIGJ时，逐步形成二叉树的过程如下图所示：

（评分说明：每个结点位置正确得1分）。

2．2．某带权有向图如下：
1）试画出它的邻接表表示法示意图。
2）根据邻接表表示法示意图试写出它的深度优先搜索序列。

B
C
E
A
G
D
F
H

A
B
C
^
B
C
D
E
F
G
H
D
E
^
F
^
C
F
G
^
E
H
^
G
^
H
^
^
（1）邻接表表示法示意图:

（评分说明：数组正确得1分，每个链表0.5分）。
(2) 深度优先搜索序列:A，B，D，C，F，E，G，H (3分)
3．假定用于通信的电文仅由8个字母c1, c2, c3, c4, c5, c6, c7, c8组成, 各字母在电文中出现的频率分别为5, 25, 3, 6, 10, 11, 36, 4。试为这8个字母设计不等长Huffman编码, 并给出该电文的总长度。

1
0
100

1
39
61

1
0
0

1
1
0
0
C2
17
22
36
25

C7
7
11
11
10

1
1
0
0
C6
C5

5
6
3
4

C4
C1
C8
C3

（评分说明：5分）
已知字母集 { c1, c2, c3, c4, c5, c6, c7, c8 }，频率 {5, 25, 3, 6, 10, 11, 36, 4 }，则Huffman编码为
c1
c2
c3
c4
c5
c6
c7
c8
0110
10
0000
0111
001
010
11
0001
（评分说明：3分）
电文总码数为 4 * 5 + 2 * 25 + 4 * 3 + 4 * 6 + 3 * 10 + 3 * 11 + 2 * 36 + 4 * 4 = 257 （评分说明：2分）
4、将以下关键字23，35，17，28，13，52，27，33，15，19，按照树形选择排序的思想进行排序，排列成非递减序列。
（1）给出初始选择树。
（2）输出前2个关键字，画出输出每一个关键字后树的结构。

初始选择树如下： 或（4分）

输出13：（3分）

输出15：（3分）

四、算法设计题（每题15分，共30分）
1、试写一算法，对单链表表示的线性表(a0,a1,...an-1)实现就地逆置。假设表长大于2。所谓"就地"指辅助空间应为O(1)，单链表定义如下：
Typedef struct LNode {
ElemType data; // 数据域
struct Lnode *next; // 指针域
} LNode, *LinkList;
函数头定义为：
void invert_linkst(LinkList *hlink)
　　// 逆转以 hlink 为头指针的单链表
分析:本算法的思想是,逐个地把L的当前元素q插入新的链表头部,p为新表表头.
void invert_linkst (Linklist & hlink)//链表的就地逆置;为简化算法,假设表长大于2
{L=hlink;//L为头节点
  p=L->next; q=p->next; （3分）
s=q->next; p->next=NULL; （3分）
  while(s->next)
  {
    q->next=p; p=q;
    q=s; s=s->next; //把L的元素逐个插入新表表头
  } （6分）
  q->next=p; L->next=q; （3分）
}//LinkList_reverse

2、请写出利用栈对二叉树进行中根遍历的非递归算法。
typedef struct BiTNode { // c语言的结点结构
TElemType data;
struct BiTNode *lchild, *rchild;
// 左右孩子指针
} BiTNode, *BiTree;

void PreOrder_Nonrecursive(Bitree T)//中序遍历二叉树的非递归算法
{
  InitStack(S);
  Push(S,T); //根指针进栈 （4分）
  while(!StackEmpty(S))
  {
    while(Gettop(S,p)&&p)
    {
            push(S,p->lchild);
    } //向左走到尽头 （3分）

    pop(S,p); （3分）
    if(!StackEmpty(S))
    {
     pop(S,p);
visit(p->data);
     push(S,p->rchild); //向右一步
    }
  }//while （5分）
}//PreOrder_Nonrecursive
评分说明：以上仅为参考评分标准，评卷老师可灵活掌握评分标准，如果给出算法思想，且思想正确、算法不正确，则给一半分。如果没有给算法思想，而算法不正确，则根据学生所写算法酌情减分。

7