得分 二、填空题（每空1分，共18分）
名 姓 。 案 写答 勿 外， 线 装订号：学 意 注 级班 徐 州 师 范 大 学 试 卷(四)（2007-2008学年度第一学期）
（考试日期 ： 年 月 日）
8.数据的基本单位是 ，最小单位 。
院系 计算机学院 专业 计算机科学与技术
9.算法的的特性有 、 、 、输入、输出 。 10. 当线性表的长度变化不大并且主要操作是查找时，用 存储结构较好。 课程名称 ： 算法与数据结构 成绩
11. 空格串是指 ，其长度等于 。
题 号 一 二 三 四 五 合分人 12.二叉树的第i层上至多有 个结点；具有n个结点的完全二叉树的深度为 。13.如图，该树的先根遍历序列为 ，后根遍历序列为 。
分 值 14 18 12 36 20 得 分 得分 一、单项选择题（每小题2分，共14分）
在下列每小题的四个备选答案中选出一个正确的答案，并将其字母标号填入题目的括号内。
1.线性链表不具有的特点是（ ）。
14．一棵有n个顶点的生成树有且仅有 条边。 A．随机访问 B．不必事先估计所需存储空间大小 15．图的遍历中，设置辅助数组是为了 。
C．插入与删除时不必移动元素 D．所需空间与线性表长度成正比 16．G是一个非连通图，共有28条边，则该图至少有 个顶点。
2.若进栈顺序为1234，则可能出现的序列是 （ ） 17．影响哈希表关键字比较次数的因素有三个： 、 、 A.3412 B.3124 C.4123 D.4321 。 3．在有n个结点的二叉链表中的空链域有（ ）个。 得分 A.n B.n+1 C.n-1 D.n+2
4．设有无向图G的顶点个数为n，则该图最多有（ ）条边。 A.n(n+1)/2 B.n(n-1) C.n(n-1)/2 D. n-1 三、判断题（每题2分，共12分） 5.若第4题的无向图G是连通图，其边的个数至少为（ ）
18．队列只允许在表的一端进行插入，而在另一端删除元素。 （ ） A.n(n+1)/2 B.n(n-1) C.n(n-1)/2 D. n-1
19．广义表的表尾可以是原子也可以是列表。 （ ） 6．含有n各结点的二叉排序树在最坏情况下查找成功时的平均查找长度为（设每个记20．二叉树的中序和后序遍历序列可以唯一确定一棵二叉树。 （ ） 录的查找概率相等）（ ）
21．分块查找比折半查找的查找效率高。 （ ）
A.n B.(n-1)/2 C.(n+1)/2 D.n-1
22．用简单选择排序方法分别对序列S1=（1，2，3，4，5，6，7）和序列S2=（7，5，3，2，7．二维数组A[10][20]采用行优先顺序存储，每个元素占1个存储单元，并且初始地址4，1，6）进行排序，两者的比较次数不相同。 （ ）
是200，则A[6][12]的地址是（ ） 23．基数排序是稳定的内部排序方法，它最适用于n值很小而关键字较大的序列。
A.365 B.326 C.360 D.332
（ ）
1
得分
四、应用题（共36分）
24.画出和下列已知序列对应的二叉树：先序访问序列为ABCDEFGHIJKL,中序访问序列为CBEFDGAJIKLH （4分）
25.画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。（6分）
26.已知某系统在通讯联络中只可能出现5种字符{a,b,c,d,e}，其概率分别为0.10，0.22，0.27，0.15，0.26，试画出赫夫曼树并设计赫夫曼编码。（6分）
27.下图为一无向带权图，（1）写出其邻接矩阵和邻接表；（2）按克鲁斯卡尔算法求其最小生成树。（10分）
28.给出一组关键字T=（12，2，16，30，8，28，4，10，20）。写出用下列算法 从小到大排序时第一趟结束时的序列（写出过程）（10分） （1）希尔排序（第一趟排序的增量为4）（3’） （2）快速排序（选第一个纪录为数轴）(5’) （3）归并排序(2’)
2
得分
五、算法设计题（共20分）
29.请根据下列数据结构定义完善简单选择排序的算法，并分析算法在待排序列按关键字正序和逆序情况下的记录的比较和移动次数。（10分） #define MAXSIZE 20
typedef int Keytype; // 定义关键字类型为整型 typedef struct {
KeyType key; // 关键字项 InfoType otherinfo; // 其他数据项 }RedType; // 记录类型 typedef struct {
RedType r[MAXSIZE+1]; // r[0]闲置或用作哨兵 int length; // 顺序表长度 }SqList; // 顺序表类型 void SelectSort(SqList &L) {//对顺序表作简单选择排序
} // SelectSort
元素的比较次数 元素的移动次数为 在逆序情况下 在正序情况下
30.我们可以借助队列对二叉树进行层次遍历，请补充下列算法。（每空2分，10分）
typedef struct BiTNode{ //二叉链表的定义 TElemType data;
Struct BiTNode *lchild,*rchild; }BiTNode, *BiTree;
typedef BiTNode* ElemType; typedef struct{ QElemType *base; int front,rear; }SqQueue;
void LevelOrderTraverse(BiTree T)
{ BiTree p; SqQueue Q; InitQueue(Q); if (T)
{ Q.base[Q.rear]=T;
; while ( ) { p=Q.base[Q.front]; printf(\"%c\
; if ( )
{ Q.base[Q.rear]=p->lchild; Q.rear=(Q.rear+1)%MAXQSIZE; }
if ( )
{ Q.base[Q.rear]=p->rchild; Q.rear=(Q.rear+1)%MAXQSIZE; } } } }
3
徐 州 师 范 大 学 试 卷(四)（2007-2008学年度第一学期）
参考答案及评分标准
院系 计算机学院 专业 计算机科学与技术 课程名称 ：算法与数据结构
一、选择题（每题2分，共14分） 1.A 2.D 3.B 4.C 5.D 6.C 7.D 二、填空题(每空1分，共18分)
8.数据元素，数据项9.有穷性，确定性，可行性10.顺序 11.有一个或多个空格组成的串，串中空格字符的个数
12.2k-1 ，|_ log2n_|+1 13.ABCEFIJGHKD，BEIJFGKHCDA14.n-1
15.避免同一顶点被访问多次 16.8 17.哈希函数、处理冲突的方法、装填因子 三、 判断题（每题2分，共12分） 18. √ 18. × 20. √ 21. × 22.× 23.× 四、 应用题（共36分）
24. 二叉树为：（4分） 25.判定树如下图（4分）
ASL=1/10（1+2*2+3*4+4*3）=2.8 (2分)
26.w={10,22,27,15,26}
赫夫曼树为（3分） 赫夫曼编码为（3分） a: 010 b: 00 c: 10 d: 011 e: 11
27.邻接矩阵为（3分）
邻接表为（3分） 最小生成树为：（4’）
0110000a 1 b 0 2 ∧ 3 4 ∧ 10011001001000c 0 3 ∧ 0110100 d 1 2 4 ∧ e 1 3 5 6 ∧0101011 0000100f 4 ∧ 0000100g a 4 ∧a 28.希尔排序：4，2，16，12，8，20，30，10，28（3分）
12 2 16 30 8 28 4 10 20 12 30 4
2 8 10
16 28 20
快速排序：10 2 4 8 12 28 30 16 20（5分） 初始 12 2 16 30 8 28 4 10 20
i j j
进行一次交换后10 2 16 30 8 28 4 20
i i j
进行二次交换后 10 2 30 8 28 4 16 20
i j j
进行三次交换后10 2 4 30 8 28 16 20
i i j
进行四次交换后10 2 4 8 28 30 16 20
i j j
4
进行五次交换后10 2 4 8 28 30 16 20
i i j
归并排序 2 12 16 30 8 28 4 10 20（2分）
12 2 16 30 8 28 4 10 20
(2 12) (16 30) (8 28 ) (4 10) (20)
五、算法填空（每题10分，共20分） 29. void SelectSort(SqList &L) {//对顺序表作简单选择排序
for(i = 1; i < L.ength; i++) {
for(k = i, j =i; k <= L.length; k++) if (L.r[k].key < L.r[j].key) j = k; if (j != i) {L.r[i] ← → L.r[j];} } //for
} // SelectSort ————5分 在逆序情况下
元素的比较次数: n(n-1)/2 元素的移动次数为：3(n-1)/2 在正序情况下
元素的比较次数: n(n-1)/2 元素的移动次数为：0
————5分
30．Q.rear=(Q.rear+1)%MAXQSIZE Q.front !=Q.rear
Q.front=(Q.front+1)%MAXQSIZE p->lchild p->rchild
每空2分
5
因篇幅问题不能全部显示，请点此查看更多更全内容