2014--浙江大学远程教育学院在线作业数据结构与算法100分

浙江大学远程教育学院《数据结构与算法》课程离线作业姓名：陈翠学号：713009014001年级：2013秋学习中心：金华学习中心—————————————————————————————一、填空题：（【序号，章，节】。

）【1，1，2】线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。

【2，1，2】为了最快地存取数据元素，物理结构宜采用顺序存储结构。

【3，1，2】存储结构可根据数据元素在机器中的位置是否一定连续分为顺序存储结构___，链式存储结构___。

【4，1，3】度量算法效率可通过时间复杂度___来进行。

【5，1，3】设n 为正整数，下面程序段中前置以记号@的语句的频度是n(n+1)/2 。

for (i=0; i<n; i++){for (j=0; j<n; j++)if (i+j==n-1)@ a[i][j]=0;}【6，1，3】设n 为正整数，试确定下列各程序段中前置以记号@的语句的频度:(1) i=1; k=0;while (i<=n-1){i++;@ k+=10 * i; // 语句的频度是_________n-1_______________。

}(2) k=0;1for (i=1; i<=n; i++){for (j=i; j<=n; j++)@ k++; // 语句的频度是_________n(n+1)/2________________。

}【7，3，2】线性表(a1，a2，…，a n)有两种存储结构：顺序存储结构和链式存储结构，请就这两种存储结构完成下列填充：___顺序_ 存储密度较大；___顺序____存储利用率较高；___顺序____可以随机存取；__链式_____不可以随机存取；__链式____插入和删除操作比较方便。

【8，3，2】从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动n-i 个元素。

浙江大学远程教育学院试题卷B卷课程名称数据结构与算法教学站年级专业(层次) 学号姓名注意：所有试题答案均按题目编号写在答题卷上。

一.单项选择题（每项选择1.5分，共60分）1、数据结构形式地定义为（D，S），其中D是①的有限集合，S是D上的②的有限集合。

① A.算法 B.数据元素 C.逻辑结构 D.数据操作② A.结构 B.操作 C.存储 D.关系2、计算机算法是指①，它必须具备输入、输出和②等五个特性。

① A.计算方法 B.排序方法 C.调度方法 D.解决问题的有限运算序列② A.可行性、可移植性和可扩充性B.可行性、确定性和有穷性C.确定性、稳定性和有穷性D.易读性、稳定性和安全性3、线性表若采用链式存储结构时，要求内存中可用存储单元的地址①。

① A.必须是连续的 B.部分地址必须是连续的C.连续或者不连续都可以D.一定是不连续的4、线性表的逻辑顺序和存储顺序总是一致的，这种说法①。

① A. 不正确 B.正确5、一个栈的进栈序列是a,b,c,d,e,则栈的不可能的出栈序列是①。

① A. edcba B. decba C. dceab D. abcde6、判断一个循环队列Q(最多元素为MAXQSIZE)为空队列的条件是①，为满队列的条件是②。

A. Q.front == Q.rearB. Q.front != Q.rearC. Q.front == (Q.rear+1)%MAXQSIZED. Q.rear == (Q.front+1)%MAXQSIZE7、一个一维数组第一个存储单元的地址是100，每个元素的长度是4，则它的第5个元素的地址是①。

① A. 120 B. 116 C. 110 D. 1048、某语言采用低下标优先方式存放数组元素，数组下标从1开始。

设维数为（5,6,7）的数组A5x6x7的起始存储地址为Loc[1][1][1]=1000，每个数组元素占用4个字节。

则元素A[3][4][5]所在的地址Loc[3][4][5]=①。

您的本次作业分数为：100分单选题1.设散列表长为14，散列函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测法解决冲突，则放入的位置是____________。

A 8B 3C 5D 9正确答案:D单选题2.下列排序算法的时间复杂度最小的是____。

A 冒泡排序B 希尔排序C 简单选择排序D 归并排序正确答案:D单选题3.带头结点的单链表Head为空表的判定条件是______。

A Head->next==HeadB Head->next==NULLC Head!=NULLD Head==NULL正确答案:B4.若用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值位于中间值的前面，下次的查找区间为从原开始位置至____。

A 该中间位置B 该中间位置－1C 该中间位置＋1D 该中间位置／2正确答案:B单选题5.一组记录的关键字为（46,79,56,38,40,84）,则利用快速排序的方法，以第一个记录为基准元素得到的一次划分结果为。

A 38,40,46,56,79,84B 40,38,46,79,56,84C 40,38,46,56,79,84D 40,38,46,84,56,79正确答案:C单选题6.下面关于图的存储的叙述中，哪一个是正确的？A 用相邻矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关B 用相邻矩阵法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关C 用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关D 用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关正确答案:A7.具有5个顶点的有向完全图有____条弧。

A 10B 16C 20D 25正确答案:C单选题8.数据结构课程主要研究以下三方面的内容，它们是______。

A 数据、数据元素、数据类型B 数据元素、数据类型、算法实现C 数据元素、数据的逻辑结构、数据的存储结构D 数据的逻辑结构、数据的存储结构、数据的运算正确答案:D单选题9.设二叉树根结点的层次为1，所有含有15个结点的二叉树中，最小高度是_____。

数据结构与算法离线作业答案浙江大学远程教育学院《数据结构与算法》课程离线作业姓名：陈翠学号：713009014001年级：2013秋学习中心：金华学习中心—————————————————————————————一、填空题：（【序号，章，节】。

）【1，1，2】线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。

【2，1，2】为了最快地存取数据元素，物理结构宜采用顺序存储结构。

【3，1，2】存储结构可根据数据元素在机器中的位置是否一定连续分为顺序存储结构___，链式存储结构___。

【4，1，3】度量算法效率可通过时间复杂度___来进行。

【5，1，3】设n 为正整数，下面程序段中前置以记号@的语句的频度是n(n+1)/2 。

for (i=0; i<n; i++){for (j=0; j<n; j++)if (i+j==n-1)@ a[i][j]=0;}【6，1，3】设n 为正整数，试确定下列各程序段中前置以记号@的语句的频度:收集于网络，如有侵权请联系管理员删除(1) i=1; k=0;while (i<=n-1){i++;@ k+=10 * i; // 语句的频度是_________n-1_______________。

}(2) k=0;for (i=1; i<=n; i++){for (j=i; j<=n; j++)@ k++; // 语句的频度是_________n(n+1)/2________________。

}【7，3，2】线性表(a1，a2，…，a n)有两种存储结构：顺序存储结构和链式存储结构，请就这两种存储结构完成下列填充： ___顺序_ 存储密度较大；___顺序____存储利用率较高；___顺序____可以随机存取；__链式_____不可以随机存取；__链式____插入和删除操作比较方便。

【8，3，2】从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动n-i 个元素。

窗体顶端您的本次作业分数为：100分单选题1•根据SQL标准，要查询表student中所有年龄age小于所有学生的平均年龄的记录，下面哪条语句适用？A select * from stude nt where age < avg(age)B select * from stude nt havi ng age < avg(age)C select * from stude nt a where a.age < (select avg(b.age) from stude nt b)D select * from stude nt a where (select avg(b.age) from stude nt b ) >= a.age正确答案:C单选题2•在数据库的三级模式结构中，描述数据库用户能够看到和使用的局部数据的逻辑结构和特征描述的是指（）。

CA模式'B内模式"C外模式'D逻辑模式正确答案:C单选题3•下列数据模型中，数据独立性最高的是（）。

'A网状数据模型” B关系数据模型'C层次数据模型'D非关系模型正确答案:B单选题4.SQL中，下列涉及空值的操作，不正确的是（）。

CA AGE IS NULLCB AGE IS NOT NULLC AGE = NULLD NOT (AGE IS NULL)i*正确答案:C单选题5.DBMS中实现事务隔离性的子系统是（）。

'A安全性管理子系统'B完整性管理子系统* C并发控制子系统'D恢复管理子系统正确答案:C单选题6•如果一个关系中的属性或属性组并非该关系的码，但它是另外一个关系的主码，则称其为该关系的（）。

r A码荷B外码r C元组r D主键正确答案:B单选题7•如果事务T1封锁了数据R1，T2封锁了数据R2,然后T1又请求封锁R2。

接着T2又申请封锁R1。

、单选题（共1. 若给定的关键字集合为A. 10B. 10C. 10D. 152.A.B.C.D.3.A. O(logB. O(n)C. O(1)D. O(nlog4.A.B.C.D. 图状结构满分：4 分得分：45. 一组记录的排序码为(46,79,56,38,40,84),则利用堆排序的方法建立的初始堆为（）。

A. 79,46,56,38,40,80B. 84,79,46,38,40,56C. 84,79,56,46,40,38D. 84,56,79,40,46,38满分：4 分得分：46. 在一个顺序队列中，队首指针指向队首元素的（）位置。

A. 后一个B. 前一个C. 当前D. 不确定满分：4 分得分：47. 计算机的算法必须具备输入，输出和（）五个特性。

A. 可行性，可移植性和可扩充性B. 可行性，确定性和有穷性C. 确定性，有穷性和稳定性D. 易读性，稳定性和安全性满分：4 分得分：48. 下列关于栈的叙述正确的是（）。

A. 栈是非线性结构B. 栈是一种树状结构C. 栈具有先进先出的特征D. 栈具有后进先出的特征满分：4 分得分：49. 在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为()。

A. eB. 2eC. n的平方－eD. n的平方－2e满分：4 分得分：410. 以下二叉树说法错误的是A. 完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达B. 在三叉链表上，二叉树的求双亲运算很容易实现C. 在二叉链表上，求根，求左、右孩子等很容易实现D. 在二叉链表上，求双亲运算的时间性能很好满分：4 分得分：411. 在一棵二叉树中，第4层上的结点数最多为（）。

A. 8B. 15C. 16D. 31满分：4 分得分：412. 非空的循环单链表head的尾节点（由p所指向）满足（）。

A. p->next=NULLB. p=NULLC. p->next=headD. p=head满分：4 分得分：413. 强连通分量是（）极大连通子图。

2022年浙江大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、将线性表的数据元素进行扩充，允许带结构的线性表是（）。

A.串B.树C.广义表D.栈2、哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数是一对一的关系，则选择好的（）方法是哈希文件的关键。

A.哈希函数B.除余法中的质数C.冲突处理D.哈希函数和冲突处理3、静态链表中指针表示的是（）。

A.下一元素的地址B.内存储器的地址C.下一元素在数组中的位置D.左链或右链指向的元素的地址4、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是（）。

A.（rear-front+m）%mB.rear-front+1C.rear-front-1D.rear-front5、在下列表述中，正确的是（）A.含有一个或多个空格字符的串称为空格串B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l6、下列选项中，不能构成折半查找中关键字比较序列的是（）。

A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，4507、已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（）。

A．3，5，12，8，28，20，15，22，19B．3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D．3，12，5，8，28，20，15，22，198、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（）。

A.二叉排序树B.哈夫曼树C.AVL树D.堆9、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。

浙江大学远程教育学院《数据库技术》课程作业姓名：谢晋学号：715007032001年级：15春季学习中心：温州学习中心—————————————————————————————填空题：注：空白下划线处为需要填充的部分。

带下划线部分为考试时可能出题的部分，需要重点注意。

1.数据是信息的符号表示。

数据处理从某些已知的数据出发，推导加工出新的信息。

数据管理及其技术发展的阶段包括：人工管理阶段、文件系统阶段、数据库系统阶段、高级数据库系统阶段。

2.人工管理阶段在20世纪50年代中期以前，其特点是：数据不保存在计算机中；没有软件系统对数据进行统一管理；基本没有文件的概念；一组数据对应一个程序，数据是面向程序的；程序和程序之间存在着大量的重复数据。

3.文件系统阶段在20世纪50年代后期至20世纪60年代中期，其特点是：数据长期保留在外存上，可经常对文件进行查询、修改、插入、删除等操作；有软件（文件系统）对数据进行管理，程序和数据有了一定的独立性；文件的形式多样化，有顺序文件、索引文件和散列文件等；数据的存取基本上以记录为单位。

4.数据库系统阶段在20世纪60年代后期开始，其特点是：面向全组织的数据结构化；数据的共享性高、、易扩充；数据独立性高。

5.数据库是长期储存在计算机存储设备上、相互关联的、可以被用户共享的数据集合。

6.数据独立性是指数据的组织和存储方法与应用程序互不依赖、彼此独立的特性。

7.数据库管理系统——DataBase Management System，简称DBMS ，DBMS运行在操作系统之上对数据库进行统一的管理和控制，并且使数据库能为多个用户共享，同时还能保证数据的安全性、可靠性、完整性、一致性，还要保证数据的高度独立性等。

数据库管理系统具备如下功能：数据库中数据的组织功能；数据库中数据的操纵功能；数据库中数据的维护功能；数据库中数据的查询功能；数据库控制功能；数据库通讯功能；数据库的数据服务功能。

数据结构与算法离线作业题目及标准答案————————————————————————————————作者：————————————————————————————————日期：2浙江大学远程教育学院《数据结构与算法》课程离线作业姓名：陈翠学号：713009014001年级：2013秋学习中心：金华学习中心—————————————————————————————一、填空题：（【序号，章，节】。

）【1，1，2】线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。

【2，1，2】为了最快地存取数据元素，物理结构宜采用顺序存储结构。

【3，1，2】存储结构可根据数据元素在机器中的位置是否一定连续分为顺序存储结构___，链式存储结构___。

【4，1，3】度量算法效率可通过时间复杂度___来进行。

【5，1，3】设n 为正整数，下面程序段中前置以记号@的语句的频度是n(n+1)/2 。

for (i=0; i<n; i++){for (j=0; j<n; j++)if (i+j==n-1)@ a[i][j]=0;}【6，1，3】设n 为正整数，试确定下列各程序段中前置以记号@的语句的频度:(1) i=1; k=0;while (i<=n-1){i++;@ k+=10 * i; // 语句的频度是_________n-1_______________。

}(2) k=0;for (i=1; i<=n; i++){3for (j=i; j<=n; j++)@ k++; // 语句的频度是_________n(n+1)/2________________。

}【7，3，2】线性表(a1，a2，…，a n)有两种存储结构：顺序存储结构和链式存储结构，请就这两种存储结构完成下列填充：___顺序_ 存储密度较大；___顺序____存储利用率较高；___顺序____可以随机存取；__链式_____不可以随机存取；__链式____插入和删除操作比较方便。

《数据结构与算法》模拟卷答案一、判断题（共10小题，每小题1分，共10分，正确的打“√”，错误的打“×”。

答案填写在答题表格中。

）×1、数据元素的逻辑结构相同时物理结构也应该相同。

√2、设n为正整数，则下列算法的时间复杂性是O(log2n)。

sum = 0; do sum += n; while(n=n/2);√3、在n个元素的顺序表中的第i个元素之前插入一个元素，需要移动n-i+1个元素。

×4、线性表的特点是每个元素都有一个前驱和一个后继。

×5、循环队列不存在空间溢出问题。

√6、n(n>0)个结点的树有n-1条边。

√7、满二叉树一定是完全二叉树，反之不然。

√8、树可以看成是连通的图。

×9、5个顶点的无向图最多可能有20条边。

×10、二叉排序树主要用于对数据的排序。

二、单项选择题（共20小题，每小题2分，共40分。

答案填写在答题表格中。

）1、数据结构是研究数据的（ D ）以及它们之间的相互关系。

A. 理想结构，物理结构B. 理想结构，抽象结构C. 物理结构，逻辑结构D. 抽象结构，逻辑结构2、计算机算法是指（ D ）。

A.计算方法B.排序方法C.调度方法D.解决问题的有限运算序列3、顺序表的特点是（ B ）。

A. 逻辑上相邻的结点其物理位置不相邻B. 逻辑上相邻的结点其物理位置亦相邻C. 顺序表不是随机存储结构D. 在顺序表中插入和删除操作比在链表上方便4、线性表按链式方式存储时，每个结点的存储包括（ B ）两部分。

A.数据值与符号B.数据与指针C.数据与表名D.数据项与符号5、带头结点的单循环链表Head为空表的判定条件是( A ) 。

A. Head->next == HeadB. Head->next == NULLC. Head != NULLD. Head == NULL6、若某堆栈的输入序列为1，2，3，…，n-1，n，输出序列的第1个元素为n，则第i个输出元素为（ A ）。

西交14秋《数据结构》在线作业西交《数据结构》在线作业试卷总分：100 测试时间：-- 试卷得分：100单选题判断题包括本科在内的各科复习资料及详细解析，可以联系屏幕右上的“文档贡献者”一、单选题（共30 道试题，共60 分。

）得分：60V 1. 对于一些特殊矩阵，采用压缩存储的目的是（）。

A. 使表达变得更简单B. 对矩阵元素的存取变得简单C. 去掉矩阵中的多于元素D. 减少不必要的存储空间满分：2 分得分：22. 任何一个非空二叉树中的叶子结点，在前序遍历、中序遍历和后序遍历中的相对位置（）。

A. 都会发生改变B. 不会发生改变C. 有可能发生改变D. 部分会发生改变满分：2 分得分：23. 图的深度优先遍历算法类似于二叉树的（）。

A. 前序遍历B. 中序遍历C. 后序遍历D. 按层次遍历满分：2 分得分：24. 判断一个图中是否存在回路可以利用（）方法。

A. 求最小生成树B. 求最短路径C. 拓扑排序D. 图的遍历满分：2 分得分：25. 在一个无向图中，所有顶点的度数之和等于边数的（）A. 1倍B. 2倍C. 3倍D. 4倍满分：2 分得分：26. 空串与空格字符组成的串的区别是（）。

A. 没有区别；B. 两串的长度不等；C. 两串的长度相等；D. 两串包含的字符不相同。

满分：2 分得分：27. 对一棵二叉排序树进行（）遍历，可以得到该二叉树的多有结点按值从小到大排列的序列。

A. 前序B. 中序C. 后序D. 按层次满分：2 分得分：28. 如果要求频繁的对线性表进行插入和删除操作，则线性表应该采用（）存储结构。

A. 散列B. 顺序C. 链式D. 任意满分：2 分得分：29. 下列各个排序算法中，要求辅助空间最大的是（）。

A. 希尔排序法B. 快速排序法C. 堆排序法D. 二路归并排序法满分：2 分得分：210. 深度为h的满二叉树，第i层有（）个结点。

A. 2i-1B. 2i-1C. 2h-1D. 2h-1满分：2 分得分：211. 在初始为空的栈中依次插入元素f，e，d，c，b，a以后，连续进行了3次删除操作，此时栈顶的元素是（）。

浙江大学远程教育学院《数据挖掘》课程作业姓名：学号：年级：学习中心：—————————————————————————————第一章引言一、填空题（1）数据库中的知识挖掘(KDD)包括以下七个步骤：数据清理、数据集成、数据选择、数据变换、数据挖掘、模式评估和知识表示（2）数据挖掘的性能问题主要包括：算法的效率、可扩展性和并行处理（3）当前的数据挖掘研究中，最主要的三个研究方向是：统计学、数据库技术和机器学习（4）孤立点是指：一些与数据的一般行为或模型不一致的孤立数据二、简答题（1）什么是数据挖掘？答：数据挖掘指的是从大量的数据中挖掘出那些令人感兴趣的、有用的、隐含的、先前未知的和可能有用的模式或知识。

（2）一个典型的数据挖掘系统应该包括哪些组成部分？答：一个典型的数据挖掘系统应该包括以下部分：数据库、数据仓库或其他信息库数据库或数据仓库服务器知识库数据挖掘引擎模式评估模块图形用户界面（3）Web挖掘包括哪些步骤？答：数据清理: (这个可能要占全过程60％的工作量)数据集成将数据存入数据仓库建立数据立方体选择用来进行数据挖掘的数据数据挖掘（选择适当的算法来找到感兴趣的模式）展现挖掘结果将模式或者知识应用或者存入知识库（4）请列举数据挖掘应用常见的数据源。

（或者说，我们都在什么样的数据上进行数据挖掘）答：常见的数据源包括关系数据库、数据仓库、事务数据库和高级数据库系统和信息库。

其中高级数据库系统和信息库包括：空间数据库、时间数据库和时间序列数据库、流数据、多媒体数据库、面向对象数据库和对象-关系数据库、异种数据库和遗产(legacy)数据库、文本数据库和万维网(WWW)等。

第二章认识数据一、填空题（1）两个文档向量d1和d2的值为：d1= (1, 0, 3, 0, 2)，d2 = (3, 2, 0, 0, 1)，则它们的余弦相似度为：5/13（2）数据离散度的常用度量包括极差、分位数、四分位数、百分位数四分位数极差和标准差（3）一种常用的确定离群点的简单方法是：出落在至少高于第三个四分位数或低于第一个四分位数1.5×IQR处的值。

1、链式存储的存储结构所占存储空间（ A ）。

A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B）只有一部分，存放结点值C）只有一部分，存储表示结点间关系的指针D）分两部分，一部分存放结点值，另一部分存放结点所占单元数2、栈进行插入和删除操作的特点是（ A ）。

A）LIFO B）FIFOC）FCFS D）HPF3、在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行（ A ）。

A）q->next=s; s->next=p; B）s->next=p->next; p->next=s;C）p->next=s->next; s->next=p D）p->next=s; s->next=q;4、数据结构研究的内容是（ D ）。

A）数据的逻辑结构 B）数据的存储结构C）建立在相应逻辑结构和存储结构上的算法 D）包括以上三个方面5、在一个链队列中，假定front和rear分别为队首和队尾指针，则插入一个结点的操作为（ B ）。

A）front=front->next; B） rear=rear->next;C） rear=front->next; D） front=rear->next ;6、串的逻辑结构与（ D ）的逻辑结构不相同。

A）线性表 B）栈C）队列 D）集合7、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。

A) 单链表 B) 仅有头指针的单循环链表C) 双链表 D) 仅有尾指针的单循环链表8、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a??11为第一个元素，其存储地址为1，每元素占1个地址空间，则a85的地址为（ B ）。

A）13 B）33 C）18 D）409、在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（ C ）。