湖南大学数据结构期末考试试题.doc

考试中心填写：
湖 南 大 学 课 程 考 试 试 卷

课程名称：数据结构 ；试卷编号：01 ；考试时间：120分钟
年 月 日
考 试 用

专业班级：

题 号
一
二
三
四
五
六
七
八
九
十
总 分
应得分
20
10
35
35

100
实得分

评分：
评卷人

（请将所有答案写在答题纸上）

一、填空题。（20分）
1. 已知单链表中指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入*s，则应执行（ ）语句。
2. 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。
3. 堆栈的特点是（ ）。
4. 已知完全二叉树的第5层有4个结点(根结点在第1层), 则其叶结点数是（ ）。
5. 在有n个叶结点的Huffman树中, 共有（ ）个结点。
6. 若数据表中每个元素已距其最终位置不远, 则采用（ ）算法最省时间。
7. 内部排序问题的时间复杂度的下限是（ ）。
8. 对线性表进行折半查找时性能要能达到O(logn)，要求线性表必须（ ）。
9. 如果具有n个顶点的图是一个环, 则它有（ ）棵生成树。
10. 具有n个顶点的无向图最多有（ ）条边。

二、请将下面的算法填写完整。（10分）
下面算法的功能是：用基数排序法对n个无符号整数进行排序（递增），在算法空缺处填上适当语句或表达式，使得算法完整且正确。
template <class elem,class comp>
void radix(elem a[], elem b[], int n, int k, int r, int cnt[])
{ //k为排序码的个数，r为基数
int i, j,x, m=1;
for (i=1; i<=k; i++) //分别对第i个排序码进行分配
{ for ( j=0; j<r; j++) cnt[j]=0; //初始计数器为0
for (j=0; j<n; j++)

装订线（答题不得超过此线）
学号：
姓名：

第 1 页（共3 页）

{ x=(a[j]/m)%r; //取a[j]的第i位排序码
cnt[x]++;
}
for (j=1; j<r; j++) cnt[j]=cnt[j-1]+cnt[j];
for (j=n-1; j>0; j--) b[ ]=a[j];
for(j=0; j<n; j++) //将临时数组 b 中的内容复制到a 中
;
m= ;
}
}

三、应用题。（35分）
1、将两个栈存入一个数组V[n]中，如何存放比较合理？为什么？此时栈空和栈满的条件分别是什么？

2、用序列（46，88，45，39，70，58，101，10，66，34）建立一个二叉查找树，画出该树，并求在等概率情况下查找成功的平均查找长度。

3、对于下图所示的有向图若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，试写出：
(1)从顶点①出发进行深度优先搜索所得到的深度优先生成树；
(2)从顶点②出发进行广度优先搜索所得到的广度优先生成树。

第 2页（共3 页）

4、设一个散列表包含13个表项,.其下标从0到12,采用线性探查法解决冲突（p（K，i)＝i），请按以下要求,将下列关键码按从左到右的顺序散列到表中。
　　10，100，32，45，58，126，3，29，200，400，0
　　散列函数采用除留余数法,用%SIZE（对表长取余运算）将各关键码映像到表中.，请指出每一个产生冲突的关键码可能产生多少次冲突？

5、一棵前序序列为1，2，3，4的二叉树，其中序序列可能是4，1，2，3吗，为什么？设一棵二叉树的前序序列为1，2，3，4，5，6，7，8，9，其中序序列为2，3，1，5，4，7，8，6，9，试画出该二叉树。

6、假设用于通信的电文由字符集{a,b,c,d,e,f,g}中的字母构成。它们在电文中出现的幅度分别为{0.31, 0.16, 0.10, 0.08, 0.11, 0.20, 0.04},为这7个字母统计哈夫曼编码，并计算其平均编码长度。

7、插入排序是否为稳定的排序算法？为什么？插入排序在最佳情况和最坏情况下，比较次数和移动数据次数分别为多少？（假设共有n个元素）

四、算法设计。（35分）
  1．设某带头结点的单链表L，,结点中的元素为整型数据，试编写算法，判断该单链表L中的元素，是否成等差关系，即各元素植依次为a1, a2, a3, a4,……an判断ai+1-ai=ai- ai－1是否成立，其中i满足1<=i<=n-1  

  2．设一棵二叉树，结点结构为|lchild |data |rchild其中   data域中存放一个字符，设计一个算法按前叙遍历顺序，仅打印出data域为数字的字符（即‘0’<=data<=’9’）  

  3．某百货公司仓库中电视机的价格和数量信息，按其价格从低到高存储在一个带头结点的循环链表中，链表中的结点由价格、数量和链指针三个域组成：|cost |num |next|，现新到m台价格为c的电视机需入库，试为此编写修改循环链表中存储的电视机信息的算法。 

第 3页（共3 页）