《数据结构》网上教学活动文本(2004.doc
《《数据结构》网上教学活动文本(2004.doc》由会员分享,可在线阅读,更多相关《《数据结构》网上教学活动文本(2004.doc(20页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、数据结构网上教学活动文本(数据结构网上教学活动文本(2004.10.22)问:问:老师,你好!这门课太难学了?请问有什么好方法吗?上课听不懂 徐孝凯:徐孝凯:请参考实验教材中的内容学习,可能容易些。问:问:什么是抽象数据类型? 徐孝凯:徐孝凯:抽象数据类型同 C+中类的概念相似。徐孝凯:徐孝凯:如何学好这门课 1.认真听面授辅导课; 2.认真做好平时作业; 3.认真按实验教材要求做好每个实验; 4.有问题请教面授课老师和身边的同学; 5.不抠难题怪题,掌握基本概念和算法。 徐孝凯:徐孝凯:如何加强练习 1.按照该课程期末复习指导的要求,掌握教学内容; 2.做好该复习指导中的练习题; 3.做好形
2、成性作业中的每次作业; 4.做好实验教材后面附录中所给的全部综合练习题,特别是选择、填空、判断等题型。 5.参考以前考过的试卷,做会其中的考题。 问:问:殷老师,徐老师,下面题怎么解 设 L 链表中数据为 12,24,30,90,84,36,n 的初值为 0,写出 unknown(L.first,n)调用后的结果,指 出算法功能 float unknown(ListNode *f,int else n+; return unknown(f-getLink(),n)+f-getData()/n; 徐孝凯:徐孝凯:返回 6 个数的平均值。因为当最后每次递归返回时,n 的值不变,即为链表中数 据的个
3、数,每次都使一个数据除以 6,整个算法是每个数除以 6 之和。 徐孝凯:徐孝凯:数据结构课程教学如何,是太难了呢?以后会好写,因为考题难度在下降,并且 在实验教材中给出了综合练习题。 赵永虹:试题有一定难度。 问:问:请问数据结构这门课程的学习重点在哪里?它是开卷考试还是闭卷考试?题目有哪些 类型? 徐孝凯:徐孝凯: 1.为闭卷考试,时间为 150 分钟。2.题目类型有选择、填空、判断、运算、算法分析、算法设计等。 3.请参考往届考试试卷。 4.请按照实验教材后面给出的综合练习题的范围掌握教学要求和难易程度。 徐孝凯:徐孝凯:四川电大赵老师,你认为数据结构考试难度如何,应如何改进? 赵永虹:这
4、样经过几次考试,可能好一些 问:问:老师这门课程很难我们应怎样才能考好这门课呢?能否出题简单点? 徐孝凯:徐孝凯: 1.为闭卷考试,时间为 150 分钟。 2.题目类型有选择、填空、判断、运算、算法分析、算法设计等。 3.请参考往届考试试卷。 4.请按照实验教材后面给出的综合练习题的范围掌握教学要求和难易程度。 5.现在试题难道有所降低,和实验教材后的综合练习题难易相当,也许更容易写。 徐孝凯:徐孝凯:参考以前试卷:中央广播电视大学计算机科学与技术专业数据结构试题(计算机科学与技术专业数据结构试题(2 2)2003 年 8 月题 号一二三四五六总 分得 分一、单项选择题,在括号内填写所选择的标
5、号(每小题一、单项选择题,在括号内填写所选择的标号(每小题 1 1 分,共分,共 1212 分)分)1. 若需要利用形参直接访问实参,则应把形参变量说明为( )参数。A. 指针 B. 引用 C. 传值 D. 常值2. 以下说法错误的是( ) 。 A. 抽象数据类型具有封装性。 B. 抽象数据类型具有信息隐蔽性。 C. 使用抽象数据类型的用户可以自己定义对抽象数据类型中数据的各种操作。 D. 抽象数据类型的一个特点是使用与实现分离。3. 设有一个 nn 的对称矩阵 A,将其上三角部分按行存放在一个一维数组 B 中,A0 0存放于 B0中,那么第 i 行的对角元素 Aii存放于 B 中( )处。A
6、. (i+3)*i/2 B. (i+1)*i/2 C. (2n-i+1)*i/2D. (2n-i-1)*i/24. 已知单链表 A 长度为 m,单链表 B 长度为 n,若将 B 联接在 A 的末尾,其时间复杂 度应为( ) 。A. O(1) B. O(m) C. O(n) D. O(m+n)5. 假定一个链式队列的队头和队尾指针分别为 front 和 rear,则判断队空的条件为( )。A. front = rearB. front != NULLC. rear != NULL D. front = NULL6. 设有一个递归算法如下int fact(int n) /n 大于等于 0if(n,
7、,从顶点 1 出发,对 图 G 进行广度优先搜索的序列有_种。10. 每次直接或通过基准元素间接比较两个元素,若出现逆序排列就交换它们的位置, 这种排序方法叫做_排序。11. 快速排序在平均情况下的空间复杂度为_。12. 若对长度 n=10000 的线性表进行二级索引存储,每级索引表中的索引项是下一级 20 个表项的索引,则一级索引表的长度为_。三、判断题,在每小题前面打对号表示正确或打叉号表示失败(每小题三、判断题,在每小题前面打对号表示正确或打叉号表示失败(每小题 1 1 分,共分,共 1010 分)分)1. 数据的逻辑结构是指各数据元素之间的逻辑关系,是用户根据应用需要建立的。2. 顺序
8、表和一维数组一样,都可以按下标随机(或直接)访问。3. 在一个顺序存储的循环队列中, 队头指针指向队头元素的后一个位置。4. 用非递归方法实现递归算法时一定要使用递归工作栈。5. 在一棵二叉树中,假定每个结点只有左子女,没有右子女,对它分别进行中序遍历 和后序遍历,则具有相同的结果。6. 在顺序表中进行顺序搜索时,若各元素的搜索概率不等,则各元素应按照搜索概率 的降序排列存放,则可得到最小的平均搜索长度。7. 在二叉搜索树中,若各结点的搜索概率不等,使得搜索概率越小的结点离树根越近, 则得到的是最优二叉搜索树。8. 对于 AOE 网络,加速任一关键活动都能使整个工程提前完成。9. 直接选择排序
9、是一种稳定的排序方法。10. 闭散列法通常比开散列法时间效率更高。四、运算题(前四、运算题(前 2 2 小题,每小题小题,每小题 6 6 分,后分,后 3 3 小题,每小题小题,每小题 8 8 分,共分,共 3636 分)分)1. 设有一个二维数组 A1020,按行存放于一个连续的存储空间中,A00的存 储地址是 200,每个数组元素占 1 个存储字,则 A62的存储字地址是多少。A62的存储字地址:2. 已知一棵二叉树的中序和后序序列如下,求该二叉树的高度(假定空树的高度为- 1)和度为 2、度为 1 及度为 0 的结点个数。中序序列:c,b,d,e,a,g,i,h,j,f后序序列:c,e,
10、d,b,i,j,h,g,f,a高度: 度为 2 的结点数:度为 1 的结点数: 度为 0 的结点数:3. 假定一组记录为(36,75,83,54,12,67,60,40),将按次序把每个结点插入到初始为 空的一棵 AVL 树中,请回答在插入时需进行“左单旋转” 、 “右单旋转” 、 “先左后右双旋转” 、 “先右后左双旋转” , “不调整”的结点数各是多少?左单旋转结点个数: 右单旋转结点个数:先左后右双旋转结点个数: 先右后左双旋转结点个数:不调整结点个数:4. 已知一个带权图的顶点集 V 和边集 G 分别为:V=0,1,2,3,4,5,6;E=(0,1)19,(0,2)10,(0,3)14
11、,(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) (3) 五、算法分析题(每小题五、算法分析题(每小题 6 6 分,共分,共 1818 分)分)1. 指出下面算法的功能并求出其时间复杂度。void m
12、atrimult(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); else return 1+LN(t-right,X); (1) (2) (3)六、算法设计题(每小题六、算法设计题(每小题 6 6 分,共分,共 1212 分)分)1. 试编写一个函数,在一个顺序表 A 中查找出具有最大值和最小值的整数。函数的原型如下所示,原型的参数表中给出顺序表对象为 A,通过算法执行,从参数 表中的引用参数 Max
13、 中得到表中的最大整数,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 分别为指向左、右子女结点的指针域,根据下 面函数声明编写出判断
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 网上 教学 活动 流动 文本
限制150内