发布时间 : 星期四 文章2005数据结构更新完毕开始阅读b6f05ad97f1922791688e8e9
中南大学考试试卷
2005 -- 2005 学年 下 学期 时间110分钟
数据结构 课程 48 学时 3 学分 考试形式： 闭 卷
专业年级： 信科03级，应数03级 总分100分，占总评成绩 %
注：此页不作答题纸，请将答案写在答题纸上
一、 单选题：(每题2 分，共 14 分）
1. 带头结点的单链表H1中，要向其表头插入一个由指针p指向的结点，则执行（ ）。 A. H1＝p; p->next=H1; B. p->next=H1; H1=p;
C. p->next=H1; p=H1; D. p->next=H1->next; H1->next=p.
2. 如果有四列火车车厢(编号分别为1,2,3,4)，其进站的方式相当于栈，假设它们按1,2,3,4的序列进站(例：可以1进去后马上出来)，则它们出站的序列不可能是（ ） A. 1234 B. 4321 C. 4312 D. 3214
3. 串是任意有限个（ ）
A.符号构成的序列 B.符号构成的集合 C.字符构成的序列 D.字符构成的集合 4. 设矩阵A（aij ，l≤I,j≤ 10）的元素满足：aij≠0(i≥j, l≤I, j≤ 10)
aij=0(I A.2340 B.2336 C.2164 D.2160 5. 二分查找要求被查找的表是（ ） A.键值有序的链接表 B链接表但键值不一定有序 C.键值有序的顺序表 D.顺序表但键值不一定有序 6. 三个结点可构成（ ）个不同形态的二叉树。 A.2 B.3 C.4 D.5 7. 栈操作的原则是（ ） A.先进先出 B.后进先出 C.栈顶插入 D.栈顶删除 二、填空题 (每空3分，共 15分。) 1．如图（图三）所示的二叉树的先序遍历序列是 。 2．已知一棵度为m的树有n1个度为1的结点，n2个度为2的结点，... ，nm个度为m的结点，则树中有 个叶子结点。 3． 在一个循环顺序队列Q中，判断队空的条件为 ，判断队满的条件为 。 4． 将中缀算术表达式（2＋3）＊2.5－（7.3／5＋6）转化为后缀表达式是 。 三、应用题（共45分） 1. 已知线性表为（18，19，，21，16，15，17，20）。按数据元素在表中的次序构造一棵平衡 二叉排序树：要求画出平衡二叉排序树的构造过程。 2．已知某系统在通信联络中会出现七种字符，其概率分别为0.05, 0.10, 0.30, 0.25, 0.03, 0.11, 0.16，试设计赫夫曼编码。要求：图示每一步的生成过程。 1 3． 如图（图一）为一带权有向网 a) 简述FLOYD算法求有向图的各对顶点之间的最短路径的基本思想。 b) 写出利用FLOYD算法求图一各对顶点之间的最短路径时在执行算法过程中所得到 的最短路径长度矩阵序列和最短路径矩阵序列 4． 有一组键值49，38，65，97，76，13，27，49，采用快速排序方法由小到大进行排序，请写出每趟的结果，并标明在第一趟排序过程中键值的移动情况。 5．对下图（图二）所示的AOE网，求出各项活动的最早开始时间e(i)和最晚开始时间l(i),并回答：工程完成的最短时间是多少？哪些活动是关键活动？是否有某些活动提高速度后能导致整个工厂缩短工期？ A4=3 6 5 A8=1 2 A A1=3 8 B 13 A3=2 4 A7=2 16 5 4 A5=4 A2=2 C A6=3 3 （图一） （图二） 四、阅读程序说明程序执行的功能并写出对下图（图三）的输出结果。（6分） typedef struct BiTNode{ A int data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; B C int preprn(BiTtree T) {if((T->lchild!=NULL)&&（T->rchild!=NULL）) E F { printf(T->data); D preprn(T->lchild); preprn(T->rchild); G H } else return OK; } （图三） 五、算法和程序设计（共20分） 1. 一个单链表，其结点在元素值以非递减有序排列，编写一个函数删除该单链表中多余的元素值相同的结点，并释放该节点空间。 struct LNode { ElemType data; LNode *next; }; void Del(LNode *&HL) { } 2．用类C语言写出折半查找算法。 2