第一章 1.计算机由五部分构成：输入、运算器、存储器、控制器、输出 2.计算机三个子系统：处理器子系统、存储器子系统、输入输出子系统 3.输入输出通常被称为人机交互 4.哈佛结构将数据和程序分开存放 5。程序存储原理：程序被要求在执行前存放在存储器中，还要求程序和数据采用同样的存储格式 6.计算机系统是由计算机硬件和软件组成的 ①计算机硬件系统包括：处理器系统（主机）、存储器系统、外部设备（输入设备、输出设备） ②计算机软件系统包括：A.系统软件（操作系统、编程语言/计算机语言系统、工具软件）、 B.应用软件 7.计算机硬件史 ①第一代计算机：电子管 ②第二代计算机：晶体管 ③第三代计算机：集成电路（IC） ④第四代计算机（微型计算机、个人计算机）：大规模集成电路 8.计算机的类型 ①巨型计算机（超级计算机） ②大型计算机 ③小型计算机 ④微型计算机 9.硬件的三个子系统 计算机三个子系统：处理器子系统、存储器子系统、输入输出子系统 存储器子系统：存储数据、程序和参与运行程序 10.计算机软件 11.计算机如何运行 事实上，只要通电启动，机器就开始执行程序，直到关机为止 计算机通电后，CPU执行启动程序BIOS（基本输入/输出系统），其基本任务就是把存放在磁盘中的操作系统调入内存执行，此后将在操作系统的管理下直接操控计算机的硬件。12.信息系统 信息系统的基本功能是为需要者提供特定的信息，支持用户迅速、有效地输入、存储、处理和获取信息。 信息系统有以下6个要素： ①硬件 ②软件 ③数据/信息 ④用户 ⑤过程 ⑥通信 13.HTML:制作web的超文本置标语言 14.web浏览器为用户访问因特网提供了简单的方法，该系统基于超文本技术。 超文本（Hypertext）还包括视频、音频、动画、图片等其他数据。
模拟 2 得分一．选择题(本大题共15 题，每题 1 分，共15 分 ) 1．数据在计算机内存中的表示是指 A. 数据的存储结构 C. 数据的逻辑结构 。 B. 数据结构 D. 数据元素之间的关系 2. 对线性表，在下列情况下应当采用链表表示的是 A. 经常需要随机地存取元素 B. 经常需要进行插入和删除操作 C. 表中元素需要占据一片连续的存储空间 D. 表中的元素个数不变 。 3．与单链表相比，双链表的优点之一是 A．插入、删除操作更加简单。 。 B．可随机访问。 C．可以省略表头指针或表尾指针 D．访问前驱结点更加方便 4．如果最常用的操作是取第i 个结点及前驱，则采用 A．顺序表B．双链表 存储方式最节省时间。 C．单循环链表D．单链表 5．可以用带表头附加结点的链表表示线性表，也可以用不带表头附加结点的链表表示线性表，前者最主要的好处是。 A．可以加快对表的遍历 C．节省存储空间 6. 一个队列的入队序列是1,2,3,4, B. 使空表和非空表的处理统一 D. 可以提高存取表元素的速度则队列的输出序列是。 A. 4,3,2,1 B. 1,2,3,4 C. 1,4,3,2 D. 3,2,4,1 7．栈和队列的共同点是。 A．都是先进先出B．都是先进后出 C．属于非线性结构D．只允许在端点处插入和删除元素8．以下不是栈的基本运算的是。 A．删除栈顶元素C．判断栈是否为空B. 删除栈底元素D. 将栈置为空栈 9．一个递归的定义可以用递归过程求解，也可以用非递归过程求解，若从运行时间来看，通常__________ 。 A．非递归算法比递归算法快B．非递归算法比递归算法慢 10. C．非递归算法与递归算法时间一样D．非递归算法与递归算法时间不一定在一个非空二叉数的中序遍历序列中，根结点的右边。 A. 只有右子树上的所有结点 B.只有右子树上的部分结点 C. 只有左子树上的部分结点 D.只有左子树上的所有结点
浙江大学2007–2008学年秋季学期 《数据结构基础》课程期末考试试卷 开课学院：软件学院、计算机、竺可桢学院，考试形式：闭卷，允许带_ 无入场考试时间：_2007_年_11_月_17日, 所需时间： 120 分钟 考生姓名： ___学号：专业： ____教师：题序一二三四总分得分 评卷人 Answer Sheet Part I 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. Part II 1. c d e 2. c d 3. c d Part III 1. (a) (b) 1. (c)
2. (a) 2. (b) 3. 4. (a) 4. (b)
Part IV void Dijkstra( Table T )
NOTE: Please write your answers on the answer sheet. 注意：请将答案填写在答题纸上。 I. Please select the answer for the following problems. (20 points) (1)The time complexity of the following piece of code is (2 points) for(i=0; i
第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）。【北京邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（）【中科院计算所1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 【南京理工大学1999 一、1（2分）【武汉交通科技大学1996 一、1（4分）】4．一个算法应该是（）。【中山大学1998 二、1（2分）】 A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C. 5. 下面关于算法说法错误的是（）【南京理工大学2000 一、1（1.5分）】 A．算法最终必须由计算机程序实现 B. 为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的
6. 下面说法错误的是（）【南京理工大学2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。【武汉交通科技大学1996 一、4（2分）】 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。【北方交通大学2000 二、1（2分）】 A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？【北方交通大学2001 一、1（2分）】 A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（）【北方交通大学2001 一、2（2分）】 A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学2001 一、10（3分）】
浙江大学 – 学年_ _季学期 《 应用光学 》课程期末考试试卷 开课学院：信息学院 ，考试形式：闭卷，允许带__计算器、尺入场 考试时间： 年__ _月__ _日,所需时间：120分钟 考生姓名： _____ 学号： 专业： ________ 题序 一 二 三 四 总 分 得分 评卷人 一、选择题（每题2分共16分） 1. 当一远视眼通过带分划板的望远镜观察远处物体时，应使 a. 物镜远离分划板 b. 物镜靠近分划板 c. 目镜远离分划板 d. 目镜靠近分划板 2. 负透镜对 a. 实物只能成实像 b. 实物只能成虚像 c. 虚物只能成实像 d. 虚物只能成虚像 3. 像面的光照度正比于 a. 光源亮度、22sin β与U b.光源亮度与U 2sin c. 光源亮度与2β d. 22sin β与U 4. 200度的近视眼，应配戴的眼镜的焦距为 a. 200mm b. 500mm c. -500mm d. –200mm 5. 以下几种初级像差中，当视场很小时就要考虑的是 a. 畸变 b. 彗差 c. 像散 d. 场曲 6. 在以下的哪个平面，轴外物点的像是垂直于子午面的短线？ a. 高斯像面 b. 弧矢像面 c. 子午像面 d. 以上都不是 7. 拍摄人像艺术照，为突出主要人物，应选用 a. 焦距大，F 数与对准距离小 b. 对准距离与F 数大，焦距小 c. 对准距离与焦距大，F 数小 d. 对准距离小、焦距与F 数大 8. 在球差、彗差、像散、像面弯曲、畸变、位置色差、倍率色差中，对轴上点成像产生圆形弥散斑的有 a. 1种 b. 2种 c. 3种 d. 以上都不对 答案： 1 2 3 4 5 6 7 8 c b b c b c a b 二、填空题(每空2分，共42分)
浙大数据结构与算法离线作业
————————————————————————————————作者：————————————————————————————————日期: ?
浙江大学远程教育学院 《数据结构与算法》课程离线作业 姓名:学号: 年级：2016春学习中心： ————————————————————————————— 一、填空题：(【序号,章，节】。。。。。。） 【１，１,2】线性结构中元素之间存在一对一关系，树形结构中元素之间存在 一对多关系,图形结构中元素之间存在多对多关系。 【2，１，2】为了最快地存取数据元素，物理结构宜采用顺序存储结构。 【３，1，2】存储结构可根据数据元素在机器中的位置是否一定连续分为顺序存储结构 , 链式存储结构。 【4，１，3】度量算法效率可通过时间复杂度来进行。 【5,1,３】设n 为正整数,下面程序段中前置以记号@的语句的频度是ｎ(n＋１)/2 。 fｏｒ(i=０; i } 【7,３,2】线性表（a1,a２，…，a n)有两种存储结构: 顺序存储结构和链式存储结构，请就这两种存储结构完成下列填充:顺序存储密度较大；顺序存储利用率较高;顺序可以随机存取；链式不可以随机存取；链式插入和删除操作比较方便。 【8,3,２】从一个长度为n的顺序表中删除第ｉ个元素(1≤i≤n)时，需向前移动n－ｉ个元素。 【９,3,2】带头结点的单链表Heaｄ为空的条件是Head-＞nexｔ=NUＬＬ。 【10,3，2】在一个单链表中ｐ所指结点（p所指不是最后结点)之后插入一个由指针s所指结点,应执行s->neｘt=_p-＞next;和p->next＝ｓ的操作。 【11，3,2】在一个单链表中删除p所指结点时，应执行以下操作： ｑ= p-＞ｎext； p->data= p->next-＞daｔａ； ｐ->ｎｅxｔ＝ p->next->ｎext ； frｅe(q); 【1２，3，2】带头结点的单循环链表Head的判空条件是Head-＞nexｔ==Head；不带头结点的单循环链表的判空条件是Heａd==NUＬL。 【13，3,2】已知L是带表头结点的非空单链表, 且P结点既然不首元结点,也不是尾元结点,试从下列提供的答案中选择合适的语句序列。 a．删除P结点的直接前驱结点的语句序列是１0 12 8 １1 4 14。 b. 删除结点P的语句序列是10 １2 7 ３ 1４。 c. 删除尾元结点的语句序列是９ 1１ 3 1４。 (１）P ＝P->nexｔ; （２） P－>ｎext ＝Ｐ; （3) P－>neｘt = Ｐ->next ->next; （４）Ｐ＝P->nｅxｔ -＞neｘt; (5) whiｌe (P ！= NULL）Ｐ＝ P->ｎext; (6) ｗhile (Q－>neｘt != NＵLL）{P = Q; Q ＝Ｑ－>ｎｅｘｔ}； (7） whｉｌe (P－>ｎｅxｔ！= Q) Ｐ＝ P－>nexｔ; (8)ｗhｉle （P-＞nexｔ->nｅxｔ！＝Q）P = P->ｎｅxｔ； (9) wｈｉlｅ（P－>nexｔ->neｘｔ != ＮULL) Ｐ = Ｐ－>next; (1０) Q = Ｐ; (１1）Ｑ= P->nｅxt; （１2）P ＝Ｌ; 高职高等数学课件 (二)高职高等数学教育虽重要，但没引起足够重视。 高职教育是高等教育的重要组成部分，《高等数学课程对高职生素质培养的重要性》中阐述了高等职业教育的目标、人才规格决定了高等数学教育不容忽视的重要地位，并针对高职教育现状与高职生特点，结合高等数学特质与素质教育的功能，说明了高等数学课程的重要性，但由于客观与某些人的主观臆断，以高等数学课程为代表的公共课并没有得到足够重视。鉴于此，在此呼吁高等数学日后教育教学的改革方向是增强师资力量、提高教师素养、改革教学方法提高学生学习兴趣等。 (三)高职高等数学的教学有待改革。 虽然高职教育在整体趋势上是积极进取的，是逐渐适应这个社会发展的，但面临社会的发展与生源的紧缺、就业率有待提高的紧迫局势，高职院校仍然在教学上面临着诸多困难。郭倩茹在《浅谈高职院校中高等数学教学的现状及问题解决策略》一文中，认为高职院校中高等数学教育的教材编制不合理，与高职教育不适应;高等数学教学没高职特色，与专业脱轨;评价机制落后，考核体系陈旧。与此同时，在描述高等数学教育现状的同时，提出了诸如规范教材与专业接轨、活跃课堂气氛、构建评价、考核新体系等。最后，强调高职院校一定要以学生的特点作为教育的先决条件，因材施教。这正是教育工作者所要考虑的，也是我国高职院校培养人才的目标与宗旨，一切为了学 生，为了学生的一切。 二、高职高等数学教学中存在问题的成因 (一)高等数学不被重视。 大多数高职院校偏重于职业技能的培养和实践活动的开展，作为专业基础课的高等数学学时时多时少，只是专业教学计划里专业课的替补而已。这在综合性的职业院校不常见，但在专业系别少的管理不严格的小职业院校是家常便饭，这无形中也造成了高等数学可有可无的尴尬境地。 (二)高职教师知识更新跟不上，教学方法与教学手段单一，教学态度不积极、忽略学生的德育教育与职业生涯规划导向等。 有些高职院校是中专合并等形式转轨而成或新成立的，万事在摸索前进。大部分教师还停留在原来的教学步伐上，高职教育的先进理论知识不够，年纪大一点的教师甚至根本不关心高职教育的改革与发展，混退休的大有人在。一些教师虽然胜任课程知识的讲解，但不求创新，教学方法单一，教学手段传统，而且对学生的德育与职业生涯规划引导、管理漠不关心，认为只是班主任与学生管理人员的责任，这在某种程度上疏忽了学生课上的教育与管理，这也是教学质量不高的原因之一。 (三)学生入学的数学基础整体较差，学习动力不足，缺乏学好数学的信心。 随着高职院校的扩大招生，高职学生数学基础整体较差。中学的数学知识点繁多、灵活多变且有很大的连续性，这让中学基础差的学 浙江大学远程教育学院 《数据结构与算法》课程离线作业 一、填空题：（【序号，章，节】。。。。。。） 【1，1，2】线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 【2，1，2】为了最快地存取数据元素，物理结构宜采用序存储结构。3，1，2】数据结构的三要素是逻辑结构，物理结构，操作。 【3，1，2】存储结构可根据数据元素在机器中的位置是否一定连续分为顺序存储结构，链式存储结构。 【4，1，3】度量算法效率可通过时间复杂度和空间复杂度__来进行。 【5，1，3】设n 为正整数，下面程序段中前置以记号@的语句的频度是n(n+1)/2。 for (i=0; i @ k++; // 语句的频度是_____ n(n+1)/2________________。 } 【7，3，2】线性表(a1，a2，…，a n)有两种存储结构：顺序存储结构和链式存储结构，请就这两种存储结构完成下列填充：_顺序存储结构__ 存储密度较大；_顺序存储结构___存储利用率较高；_顺序存储结构___可以随机存取；_链式存储结构____不可以随机存取；__链式存储结构__插入和删除操作比较方便。 【8，3，2】从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动n-i个元素。 【9，3，2】带头结点的单链表Head为空的条件是____ Head->next==null_____ 【10，3，2】在一个单链表中p所指结点(p所指不是最后结点)之后插入一个由指针s所指结点，应执行s->next=__ p->next___;和p->next=___s _____的操作。 【11，3，2】在一个单链表中删除p所指结点时，应执行以下操作： q= p->next; p->data= p->next->data; p->next= p->next->next_ ; free(q); 【12，3，2】带头结点的单循环链表Head的判空条件是_ Head->next==null ____；不带头结点的单循环链表的判空条件是__ Head==null___。 【13，3，2】已知L是带表头结点的非空单链表, 且P结点既然不首元结点,也不是尾元结点,试从下列提供的答案中选择合适的语句序列。 a. 删除P结点的直接前驱结点的语句序列是_10 12 8 11 4 14______。 b. 删除结点P的语句序列是_____10 12 7 3 14___________。 c. 删除尾元结点的语句序列是______9 11 3 14___________。 (1) P = P->next; (2) P->next = P; 2 / 50 选课了，希望大家都有好课选。这是些选课的参考，有些课有点小变化吧，别的基本没变，希望对大家可 以有点帮助！！！ 仅供参考 一、课程及老师推荐 由历届学长们的血的教训总结而出 1. 语言英语：方富民王元春吴越民熊海虹徐明陈颖朱晨晨德语：陆伸日语：张宏斌 2. 计算机计算机组成：潘学增杨起帆 数据结构：王申康陈越 操作系统：李善平 网络应用：孟炳泉 c语言：高济平王何宇白洪欢吴晓华应晶 大学计算机基础：白洪欢 vb 程序：孟炳泉 3. 理工科微积分:苏得矿吴明华龚乐春陈锦辉卢兴江吴建民景荣荣金显吴彪 大学物理：陈凤至潘正权阮晓声 physics：方本民潘正权鲍世宁大学物理：阮晓声陈凤至陆文琴 大学物理学实验：周小风陈星 有机化学：吴军吴百乐 无机及分析化学：贾之慎大学化学实验：曾秀琼 概率论：谈之奕黄柏琴吴国桢 数理统计：吴国桢 复变函数：汪国昭应文隆 线性代数：谈之奕戴佳玲单鉴华李方汪国军[何勇] 电路原理：贾爱民马佐群孙辉范承志 常微分方程：卢兴江应文隆贾厚玉薛儒英姜海益吴彪 偏微分方程：薛儒英贾厚玉 数学分析：沙震(是丘班的课，一般人不可选）李松 模拟电路：祁才君沈连丰 数字电路：沈连丰 电子技术基础：王小海 有机化学：吴军 工程图学：施岳定费少梅 画法几何：施林祥 理论力学：叶敏 应用电子学：王玉芬 4. 经管现代经济学：陈君徐林危启才盛晓明凤进 微观经济学：金祥荣章华施杰 宏观经济学：徐林叶航 经济法：丁关良 财务管理：赵静 管理心理学：林良夫 5. 生物医学生物论理学：袁康培 现代遗传学概论：石春海 普通生物学：钱凯先 生物化学：史锋 现代遗传学：石春海 医学史：郭永松 6. 公选课政治经济学：戴文标舒泽虎蒋文华廖亦宏包松王建宇李敏邓论：熊卫平绕清水章鑫强吴元耕宇正香 军事理论：吕强褚良才 毛概：许建平李立志 法律基础：龚慧香吴红瑛 马克思哲学：张应杭 思想道德修养：万慧进黄步琦 7. 限选课、校选课、院选课 化学与人类文明：谢玉群毛建新胡吉明徐冬梅 物理与人类文明：叶高翔沙健 环境与人类文明：刘广深 现代管理基础：郭红东陈随军戚振江 现代经济基础：陈君 生命科学导论：唐建军史锋 工程化学：郭永胜 大学语文：许志强黄擎陶然李力金立汪超红 大学写作：金立朱首献 中国近代军事史：姚杏民褚良才 中华人民共和国史：李立志 伦理学：张应杭朱法桢 社会学：刘玉能 天文学：刘广深 军事学和国防科技：吕强 诗歌鉴赏与写作：黄杰 风景画入门：付东黎 离散数学：王维维金小刚 心理学概论：符德江 社会心理学：王小章吴明证 美学：易容 19年浙大数据结构真题整理 -----木君,群内相关讨论及资源 数据结构： 1. 选择题 1.选出算法时间最快（）（C 其中logN与N不在一个数量级） A. O(n^2) B. O(n^3) C. O(n(log N)^4) D. O(n^3/2) 2.不是链表所具有的特性（）（A） A.可以随意查找 B.插入删除的复杂度为O(1) 3.判断栈的出栈顺序，是否正确（）（王道常见题型） 4.中序和后序的结果一样的，则该树所具有的特征（）（王道常见题型） 5.78，85，120，65，61...的序列排成AVL树，其中不正确的描述（）（该题还是AVL树的平衡） A.是一棵完全二叉树 B.x是根节点 C.其中a,b是兄弟结点 6.拓扑排序(王道) 7.进行一趟快排后，形成的新的序列（王道） 8.有2333个数的最小堆，最大值不可能在下面的哪个节点上（） A. 1113 B.1556 C…（王道，非叶子结点即可） 9.给出一张图，找出最小生成树，（王道，建议使用，kruskal算法） 10.（a,b,c,d）,a，b是最小频率使用的两个结点，不可能出现的编码（） C c:10 d:0 11.给出邻接表，判断它的深度遍历顺序（）（这题不是很会处理，感觉每个选项都像对） 12.广度搜索 13.20，25，16，7，96…….。进行一趟，排序问选择哪种（） A.堆排序 B.快排 C.二路并归 (20) 2. 简答题 1.1给定一串数，将他们排列成一棵完全二叉树，并保证该树是一棵二叉搜索树。 1.2并对上述的二叉树进行前序遍历 2.给出一个图，用dijkstra算法求最短路径，要求写出查找的序列以及距离起始点的最短距离。 3．程序填空 进行最大堆进行调整，主要是if语句的调整。（往年真题出现过） （思路）主要的if()语句的判断，判断内容属于对一个节点的左右孩子的比较，选出最大的那个孩子，以便进行下一个if的判断，对当前节点和刚刚最大的孩子的比较。 3.编程题 是将单链表进行新的排序，如123456，转变为615243，时间复杂度O(n)，空间复杂度O(1), 您的本次作业分数为：100分单选题 1.设散列表长为14，散列函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测法解决冲突，则放入的位置是____________。 A 8 B 3 C 5 D 9 正确答案:D 单选题 2.下列排序算法的时间复杂度最小的是____。 A 冒泡排序 B 希尔排序 C 简单选择排序 D 归并排序 正确答案:D 单选题 3.带头结点的单链表Head为空表的判定条件是______。 A Head->next==Head B Head->next==NULL C Head!=NULL D Head==NULL 正确答案:B 4.若用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值位于中间值的前面，下次的查找区间为从原开始位置至____。 A 该中间位置 B 该中间位置－1 C 该中间位置＋1 D 该中间位置／2 正确答案:B 单选题 5.一组记录的关键字为（46,79,56,38,40,84）,则利用快速排序的方法，以第一个记录为基准元素得到的一次划分结果为。 A 38,40,46,56,79,84 B 40,38,46,79,56,84 C 40,38,46,56,79,84 D 40,38,46,84,56,79 正确答案:C 单选题 6.下面关于图的存储的叙述中，哪一个是正确的？ A 用相邻矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关 B 用相邻矩阵法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关 C 用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关 D 用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关 正确答案:A 浙江大学2009–2010学年秋学期 《数据结构基础》课程期末考试试卷(A) 课程号： 211C0020_，开课学院：_计算机科学与技术_ 考试试卷：√A卷、B卷（请在选定项上打√） 考试形式：√闭、开卷（请在选定项上打√），允许带____无___入场 考试日期： 2009 年 11 月 17 日,考试时间： 120 分钟 诚信考试，沉着应考，杜绝违纪。 考生姓名：学号：所属院系： _题序一二三四总分得分 评卷人 Answer Sheet Part I (24) 1. 2. 3. 4. 5. 6. 7. 8a. 8b. 9. 10. 11. Part II (18) 1. c______________d_________________ e_______________ f________________ 2. c_________________ d_________________ Part III (43) 1. 2. (a) The initial max-heap sequence is: (b) The sequences of the first 4 runs are: 3. (a) DFS: (b) BFS: (c) Topological order: 4. S 1 2 3 4 5 6 7 8 9 10 Union(1,2) Union(3,4) Union(1,3) Union(3,5) Union(6,7) Union(1,7) Union(7,8) Union(4,10) NOTE: Please write your answers on the answer sheet. 注意：请将答案填写在答题纸上。 I. Please select the answer for the following problems. (24 points) (1)Given as following the recurrence relations of the time complexities of two programs: P1. T(1)=1, T(N)=T(N/2)+1; and P2. T(1)=1, T(N)=2T(N/2)+1; What conclusion can be made about the time complexities of the two programs? a. both are O(logN) b. O(logN) and O(NlogN) respectively c. both are O(N) d. O(logN) and O(N) respectively (2)In a singly linked list with N nodes, which operation requires the time complexity of O(N)? a. to find the i-th node in the list （1≤i≤N） b. to insert a new node after the node pointed by p c. to arrange the nodes of the list in increasing order d. to delete a node after the node pointed by p (3)If a queue is implemented by a circular array with size m. It is given that the front element is at f and the length of the queue is s. Where is the rear element in the queue? a. f+s b. f+s-1 c. (f+s-1)%m d. (f+s)%m (4)Among the following sorting algorithms, which one has the properties that for each step at least one element can be placed to its final position and the number of comparisons is NOT related to the initial order of the list to be sorted? a. Selection sort b. sort Heap c. Quick sort d. Insertion sort (5)If quadratic probing is used, and the table size is prime, then which one of the following is true? a. A new element can always be inserted b. A new element may not be inserted c. A new element can not be inserted d. None of the above (6)To test if there is a cycle in a given digraph, which of the following method can be used besides topological sort? Breath-First-Search a. b. Depth-First-Search c. Critical Path Method d. Dijkstra Method (7)The sufficient conditions of a graph of N vertices being a tree are that the graph must be a. connected and directed b. acyclic and directed c. connected and acyclic d. containing exactly N-1 edges (8) A graph of N vertices contains at least , and at most connected components. a. 0 b. 1 c. N-1 d. N 我们身边有哪些光学仪器与系统？ ?什么是光学？--- 研究有关光的本质及其规律的科学 物 理 光 学 几 何 光 学 生 理 光 学 量 子 光 学 研究光的波动本 质 研究光线传输及成像 研究人身的光学现 象 研究光的量子性?应用光学课程包括哪些主要内容？ 几 何 光 学 像 差 理 论 典 型 光 学 系 统 光 学 系 统 设 计 ? 几何光学--- 研究光线经光学系统的传播而成像，主要目的是根据技术条件设计出符合要求的光学系统。?像差理论--- 成像并不理想，产生缺陷有误差( 如哈哈镜) ?典型光学系统---- 最常用的或以往的设计出的光学系统的特点 眼睛2) 显微镜3) 望远系统4) 摄影系统5) 放映系统没有万能的光学系统 ?设计光学系统---- 了解技术条件。使设计出的光学系统能满足这些技术条件。如观察范围。画面大小。光线波长。倍数。体积和照明条件。 ?实验很重要哦 光组成像特性光组焦距测量材料参数测量典型光学系统?您想发挥自己的智慧、展示自己的个性与才华吗？请参加光学系统CAD 要编个程序使用国际通用软 件 要与同学合作看谁干得更好答辩评分 习题：一次~ 二次/ 章 第一章几何光学的基本定律 本章要点： 1. 发光点、波面、光线、光束 2. 光的直线传播定律、光的独立传播定律、反射定律和折射定律及其矢量形式 3. 全反射及临界角 4. 光程与极端光程定律（费马原理） 5. 光轴、顶点、共轴光学系统和非共轴光学系统 6. 实物（像）点、虚物（像）点、实物（像）空间、虚物（像）空间 7. 完善成像条件 §1-1 发光点、波面、光线、光束返回本章要点 发光点---- 本身发光或被照明的物点。既无大小又无体积但能辐射能量的几何点。对于光学系统来说，把一个物体看成由许多物点组成，把这些物点都看成几何点( 发光点) 。把不论多大的物体均看作许多几何点组成。研究每一个几何点的成像。进而得到物体的成像规律。 模拟2 1．数据在计算机内存中的表示是指。 A. 数据的存储结构 B. 数据结构 C. 数据的逻辑结构 D. 数据元素之间的关系 2. 对线性表，在下列情况下应当采用链表表示的是。 A. 经常需要随机地存取元素 B. 经常需要进行插入和删除操作 C. 表中元素需要占据一片连续的存储空间 D. 表中的元素个数不变 3．与单链表相比，双链表的优点之一是。 A．插入、删除操作更加简单。 B．可随机访问。 C．可以省略表头指针或表尾指针 D．访问前驱结点更加方便 4．如果最常用的操作是取第i个结点及前驱，则采用存储方式最节省时间。 A．顺序表 B．双链表 C．单循环链表 D．单链表 5．可以用带表头附加结点的链表表示线性表，也可以用不带表头附加结点的链表表示线性表，前者最主要的好处是。 A．可以加快对表的遍历 B. 使空表和非空表的处理统一 C．节省存储空间 D. 可以提高存取表元素的速度 6. 一个队列的入队序列是1,2,3,4, 则队列的输出序列是。 A. 4,3,2,1 B. 1,2,3,4 C. 1,4,3,2 D. 3,2,4,1 7．栈和队列的共同点是。 A．都是先进先出 B．都是先进后出 C．属于非线性结构 D．只允许在端点处插入和删除元素 8．以下不是栈的基本运算的是。 A．删除栈顶元素 B. 删除栈底元素 C．判断栈是否为空 D. 将栈置为空栈 9．一个递归的定义可以用递归过程求解，也可以用非递归过程求解，若从运行时间来看，通常__________。 A．非递归算法比递归算法快B．非递归算法比递归算法慢 C．非递归算法与递归算法时间一样D．非递归算法与递归算法时间不一定 10. 在一个非空二叉数的中序遍历序列中，根结点的右边。 A. 只有右子树上的所有结点 B.只有右子树上的部分结点 C. 只有左子树上的部分结点 D.只有左子树上的所有结点 11. 有关树和二叉树的叙述错误的有。 A. 树中的最大度数没有限制，而二叉树结点的最大度数为2； B. 树的结点无左右之分，而二叉树的结点有左右之分； C. 树的每个结点的孩子数为0到多个, 而二叉树每个结点均有两个孩子； D. 树和二叉树均为树形结构。 12．深度为k的完全二叉树至少有个结点，至多有个结点。 A. (2k-1, 2k-1) B. (2k-1, 2k) C. (2k-1, 2k) D. (2k-1-1, 2k-1) 13. 具有4个顶点的无向完全图，有条边。 A. 3 B. 6 C. 12 D. 16 14．一个具有n个顶点的无向图，要确保是一个连通图，至少需要条边。 A. n-1 B. n C. n+1 D. n/2 15．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。 窗体顶端 1. 邻接表是图的一种____。 正确答案点评 A 顺序存储结构 B 链式存储结构 C 索引存储结构 D 散列存储结构 正确答案：B 答案讲解： 无【试题出处】 第6章第3节1 窗体底端 窗体顶端 2. 一组记录的关键字为（46,79,56,38,40,84）,则利用快速排序的方法，以第一个记录为基准元素得到的一次划分结果为。 正确答案点评 A 38,40,46,56,79,84 B 40,38,46,79,56,84 C 40,38,46,56,79,84 D 40,38,46,84,56,79 正确答案：C 窗体底端 窗体顶端 3. 设深度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至多为_____(注意C和D中h是指数)。 正确答案点评 A 2h-1 B 2(h-1) C 2*h-1 D 2*h 正确答案：A 窗体底端 窗体顶端 4. 一个栈的入栈序列是a,b,c,d, 则下列序列中不可能的输出序列是_______。 正确答案点评 A acbd B dcba C acdb D dbac 正确答案：D 窗体底端 窗体顶端 5. 计算机算法是指______。 正确答案点评 A 计算方法 B 排序方法 C 调度方法 D 解决问题的有限运算序列 正确答案：D 窗体底端 窗体顶端 6. 关于二叉树的三种遍历，下列说法正确的是____。 正确答案点评 A 任意两种遍历序列都不可以唯一决定该二叉树 B 任意两种遍历序列都可以唯一决定该二叉树 C 先序遍历序列和后序遍历序列可以唯一决定该二叉树 D 先序遍历序列和中序遍历序列可以唯一决定该二叉树 正确答案：D高职高等数学课件
浙大远程数据结构与算法离线答案-完整版
浙江大学课程推荐(学长学姐吐血整理)
2019年浙大数据结构真题整理
2014--浙江大学远程教育学院在线作业数据结构与算法100分
浙大数据结构期末考试2009-2010
(整理)浙大应用光学(完整版)
浙大城院数据结构期末模拟2
浙江大学 数据结构与算法课程自我测试答案
相关主题
文本预览