1、数据结构网上教学活动文本（2004.10.22）问：老师，你好！这门课太难学了？请问有什么好方法吗？上课听不懂 徐孝凯：请参考实验教材中的内容学习，可能容易些。问：什么是抽象数据类型？ 徐孝凯：抽象数据类型同 C+中类的概念相似。徐孝凯：如何学好这门课 1.认真听面授辅导课；2.认真做好平时作业；3.认真按实验教材要求做好每个实验；4.有问题请教面授课老师和身边的同学；5.不抠难题怪题，掌握基本概念和算法。 徐孝凯：如何加强练习 1.按照该课程期末复习指导的要求，掌握教学内容；2.做好该复习指导中的练习题；3.做好形成性作业中的每次作业；4.做好实验教材后面附录中所给的全部综合练习题，特别是选
2、择、填空、判断等题型。5.参考以前考过的试卷，做会其中的考题。 问：殷老师，徐老师，下面题怎么解 设 L 链表中数据为 12,24,30,90,84,36,n 的初值为 0,写出 unknown(L.first,n)调用后的结果,指出算法功能float unknown(ListNode *f,intelse n+;return unknown(f-getLink(),n)+f-getData()/n;徐孝凯：返回 6 个数的平均值。因为当最后每次递归返回时，n 的值不变，即为链表中数据的个数，每次都使一个数据除以 6，整个算法是每个数除以 6 之和。 徐孝凯：数据结构课程教学如何，是太难了呢？
3、以后会好写，因为考题难度在下降，并且在实验教材中给出了综合练习题。 赵永虹：试题有一定难度。 问：请问数据结构这门课程的学习重点在哪里？它是开卷考试还是闭卷考试？题目有哪些类型？ 徐孝凯：1.为闭卷考试，时间为 150 分钟。2.题目类型有选择、填空、判断、运算、算法分析、算法设计等。3.请参考往届考试试卷。4.请按照实验教材后面给出的综合练习题的范围掌握教学要求和难易程度。 徐孝凯：四川电大赵老师，你认为数据结构考试难度如何，应如何改进？ 赵永虹：这样经过几次考试,可能好一些 问：老师这门课程很难我们应怎样才能考好这门课呢？能否出题简单点？ 徐孝凯：1.为闭卷考试，时间为 150 分钟。2.
4、题目类型有选择、填空、判断、运算、算法分析、算法设计等。3.请参考往届考试试卷。4.请按照实验教材后面给出的综合练习题的范围掌握教学要求和难易程度。5.现在试题难道有所降低，和实验教材后的综合练习题难易相当，也许更容易写。 徐孝凯：参考以前试卷：中央广播电视大学计算机科学与技术专业数据结构试题（2）2003 年 8 月题 号 一 二 三 四 五 六 总 分得 分一、单项选择题，在括号内填写所选择的标号（每小题 1 分，共 12 分）1. 若需要利用形参直接访问实参，则应把形参变量说明为( )参数。A. 指针 B. 引用 C. 传值 D. 常值2. 以下说法错误的是（ ） 。A. 抽象数据类型具
5、有封装性。B. 抽象数据类型具有信息隐蔽性。C. 使用抽象数据类型的用户可以自己定义对抽象数据类型中数据的各种操作。D. 抽象数据类型的一个特点是使用与实现分离。3. 设有一个 nn 的对称矩阵 A，将其上三角部分按行存放在一个一维数组 B 中，A00存放于 B0中，那么第 i 行的对角元素 Aii存放于 B 中（ ）处。A. (i+3)*i/2 B. (i+1)*i/2 C. (2n-i+1)*i/2 D. (2n-i-1)*i/24. 已知单链表 A 长度为 m，单链表 B 长度为 n，若将 B 联接在 A 的末尾，其时间复杂度应为（ ） 。A. O(1) B. O(m) C. O(n)
6、D. O(m+n)5. 假定一个链式队列的队头和队尾指针分别为 front 和 rear，则判断队空的条件为( )。A. front = rear B. front != NULLC. rear != NULL D. front = NULL6. 设有一个递归算法如下int fact(int n) /n 大于等于 0if(n,，从顶点 1 出发，对图 G 进行广度优先搜索的序列有_种。10. 每次直接或通过基准元素间接比较两个元素，若出现逆序排列就交换它们的位置，这种排序方法叫做_排序。11. 快速排序在平均情况下的空间复杂度为_。12. 若对长度 n=10000 的线性表进行二级索引存储，每
7、级索引表中的索引项是下一级20 个表项的索引，则一级索引表的长度为_。三、判断题，在每小题前面打对号表示正确或打叉号表示失败（每小题 1 分，共 10 分）1. 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。2. 顺序表和一维数组一样，都可以按下标随机（或直接）访问。3. 在一个顺序存储的循环队列中, 队头指针指向队头元素的后一个位置。4. 用非递归方法实现递归算法时一定要使用递归工作栈。5. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。6. 在顺序表中进行顺序搜索时，若各元素的搜索概率不等，则各元素应按照搜索概
8、率的降序排列存放，则可得到最小的平均搜索长度。7. 在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越小的结点离树根越近，则得到的是最优二叉搜索树。8. 对于 AOE 网络，加速任一关键活动都能使整个工程提前完成。9. 直接选择排序是一种稳定的排序方法。10. 闭散列法通常比开散列法时间效率更高。四、运算题（前 2 小题，每小题 6 分，后 3 小题，每小题 8 分，共 36 分）1. 设有一个二维数组 A1020，按行存放于一个连续的存储空间中，A00的存储地址是 200，每个数组元素占 1 个存储字，则 A62的存储字地址是多少。A62的存储字地址：2. 已知一棵二叉树的中序和后序序列
9、如下，求该二叉树的高度（假定空树的高度为-1）和度为 2、度为 1 及度为 0 的结点个数。中序序列：c,b,d,e,a,g,i,h,j,f后序序列：c,e,d,b,i,j,h,g,f,a高度： 度为 2 的结点数：度为 1 的结点数： 度为 0 的结点数：3. 假定一组记录为(36,75,83,54,12,67,60,40)，将按次序把每个结点插入到初始为空的一棵 AVL 树中，请回答在插入时需进行“左单旋转” 、 “右单旋转” 、 “先左后右双旋转” 、“先右后左双旋转” ， “不调整”的结点数各是多少？左单旋转结点个数： 右单旋转结点个数：先左后右双旋转结点个数： 先右后左双旋转结点个数
10、：不调整结点个数：4. 已知一个带权图的顶点集 V 和边集 G 分别为：V=0,1,2,3,4,5,6;E=(0,1)19,(0,2)10,(0,3)14,(1,2)6,(1,5)5,(2,3)26,(2,4)15,(3,4)18,(4,5)6,(4,6)6,(5,6)12;试根据迪克斯特拉(Dijkstra)算法求出从顶点 0 到其余各顶点的最短路径，在下面填写对应的路径长度。顶点： 0 1 2 3 4 5 60路径长度：5. 已知一个数据表为36,25,25*,62,40,53，请写出在进行快速排序的过程中每次划分后数据表的变化。(0) 36 25 25* 62 40 53(1) (2)
11、(3) 五、算法分析题（每小题 6 分，共 18 分）1. 指出下面算法的功能并求出其时间复杂度。void matrimult(int aMN, int bNL, int cML) /M、N、L 均为全局整型量int i, j, k;for(i=0; idata=X) return 1;else if(t-dataX) return 1+LN(t-left,X);elsereturn 1+LN(t-right,X);(1) (2) (3)六、算法设计题（每小题 6 分，共 12 分）1. 试编写一个函数，在一个顺序表 A 中查找出具有最大值和最小值的整数。函数的原型如下所示，原型的参数表中给出
12、顺序表对象为 A，通过算法执行，从参数表中的引用参数 Max 中得到表中的最大整数，Min 中得到表中的最小整数。注意，函数中可使用顺序表的如下两个公有函数：int Length( ); 求表的长度；int getData(int k); 提取第 k 个元素的值。#include “SeqList.h”template void FindMaxMin(SeqList2. 已知二叉树中的结点类型 BinTreeNode 定义为:struct BinTreeNode char data; BinTreeNode *left, *right;其中 data 为结点值域，left 和 right 分别
13、为指向左、右子女结点的指针域，根据下面函数声明编写出判断两棵二叉树是否相等的算法，若相等则返回 1 否则返回 0。算法中参数 T1 和 T2 为分别指向这两棵二叉树根结点的指针。当两棵树的结构完全相同并且对应结点的值也相同时才被认为相等。int BTreeEqual(BinTreeNode* T1,BinTreeNode* T2);中央广播电视大学计算机科学与技术专业数据结构试题（2）参考解答及评分标准2003 年 8 月一、单项选择题，在括号内填写所选择的标号（每小题 1 分，共 12 分）1. B 2. C 3. C 4. C 5. D 6. B7. D 8. C 9. B 10. C 1
14、1. D 12. D二、填空题，在横线处填写合适内容（每小题 1 分，共 12 分）1. 链接 2. 动态 3. 删除 4. 后出先进5. 递归 6. 3 7. 右 8. 左子树 9. 2 10. 交换 11. O (log2n) 12. 500三、判断题，在每小题前面打对号或打叉号（每小题 1 分，共 10 分）1. 对 2. 对 3. 错 4. 错 5. 对6. 对 7. 错 8. 错 9. 错 10. 错.四、运算题（前 2 小题，每小题 6 分，后 3 小题，每小题 8 分，共 36 分）1. A62的存储字地址：322 /6 分答案说明：按行存储时，计算 Aij地址的公式为LOC(i
15、,j)=LOC(0,0)+(i*n+j)*d 其中首地址 LOC(0,0)=200, 每个数组元素的存储占用数 d=1, 二维数组的列数 n=20，根据题意，元素 A62的存储地址为LOC(6,2)=200+(6*20+2)*1=3222. 高度：4 /2 分 度为 2 的结点数：3 /2 分度为 1 的结点数：3 /1 分度为 0 的结点数：4 /1 分3.左单旋转结点个数：1 /2 分右单旋转结点个数：0 /2 分先左后右双旋转结点个数：1 /2 分先右后左双旋转结点个数：0 /1 分不调整结点个数：6 /1 分4. 错 1 个数值扣 2 分，最多扣全部 8 分。顶点： 0 1 2 3 4
16、 5 6路径长度： 5.(0) 36 25 25* 62 40 53(1) 25* 25 36 62 40 53 /3 分(2) 25* 25 36 53 40 62 /3 分(3) 25* 25 36 40 53 62 /2 分五、算法分析题（每小题 6 分，共 18 分）1. 功能为： 矩阵相乘，即 aMNbNLcML。/3 分时间复杂性为：O(MNL)。 /3 分2.12 /2 分13 /2 分23 /2 分3. (1) 2 /2 分(2) 4 /2 分(3) 3 /2 分六、算法设计题（每小题 6，共 12 分）1. 请根据完整程度酌情给分#include “SeqList.h”tem
17、plate void FindMaxMin(SeqListfor(int i=1; iMax) Max=A.getData(i);else if(A.getData(i)Min) Min=A.geyData(i);2. 渐进给分，如注释。int BTreeEqual(BinTreeNode* T1,BinTreeNode* T2)/若两棵树均为空则返回 1 表示相等if(T1=NULL /1 分/若一棵为空一棵不为空则返回 0 表示不等else if(T1=NULL | T2=NULL) return 0; /2 分/若根结点值相等并且左、右子树对应相等则两棵树相等0 16 10 14 25 21 31
