山东大学计算机2018年算法导论试题。
--粗略回忆版
一、最小生成树思想。包括Kruskal、Prim
二、计算BFS，DFS
三、计算最大流二分匹配
四、判断-强连通分量课后题。
五、判断-最小生成树的割与安全边相关
六、证明-最短路径的上界，收敛性质
七、证明-有向无环图不含后向边
八、设计算法-DFS
九、设计算法-最短路径的动态规划-与所有节点对最短路径相似。
９，IP协议提供的服务是（）。 A、尽最大努力传递 B、可靠的 C、面向连接的 D、虚电路 １０，网络中，用于报告错误和测试的协议为（）。 A、NAT B、OSPF C、ICMP D、RIP 三、填空题（每题0.5分，共8分）。 1.网络可以有多种分类标准，按照覆盖范围（距离）这个标准，网络可以分为＿＿＿＿、城域网 和＿＿＿＿。 2.服务质量用来描述网络能够提供的服务能力或网络应用的要求，网络中经常使用的服务质量参 数有＿＿＿＿、＿＿＿＿、＿＿＿＿与＿＿＿＿等。 3.无线局域网对应的IEEE标准为＿＿＿＿＿＿＿＿，宽带无线网络对应的IEEE标准为＿＿＿＿ ＿＿＿＿。 4.网络中常见的调制方式有＿＿＿＿、＿＿＿＿与＿＿＿＿。 5.TCP协议中校验和校验的范围包括＿＿＿＿、＿＿＿＿和＿＿＿＿＿＿。 6.在以太网中发生冲突后，经常采用＿＿＿＿＿＿＿＿来解决冲突。 7.IP协议中有一个＿＿＿＿＿＿＿＿字段，用于限制分组在网络上的存活时间，避免分组无休止 的在网络上循环。 四、简答计算题（每题5分，共20分） 1.网络使用CRC校验。假设使用的生成式为10011，计算发送数据1101011111的校验和。 2.漏桶和令牌桶是网络中用于流量整形的主要方法。根据所学知识，回答下面问题：
五、论述题（每题8分，共32分） 1.滑动窗口协议是数据链路层的一个重要协议，提供在一条不可靠的线路上可靠的数据递交。根 据所学知识，回答下述问题： 1）发送窗口和接收窗口的含义是什么？ 2）滑动窗口是如何提供流量控制的？
山东大学 2014-2015 学年 2 学期 计算机网络（A ）课程试卷 ………… … … ……………… 第 3页 共 4 页 4. 地址解析协议（ARP ）是网络层一个重要的协议。根据所学知识，回答下面问题： 1）ARP 协议的目的是什么？ 2）依据给定内容，完成表格各项，并简述ARP 协议的工作过程。
851计算机基础综合考试大纲 计算机基础综合包括数据结构、操作系统、计算机组成原理三部分内容，每部分内容各占1/3。 I 数据结构 课程基本要求 全面系统地掌握队列、堆、栈、树、图等基本数据结构，深刻理解和熟练掌握课程中的典型算法，为计算机学科的学习打下坚实基础。 考试内容 1．链表、间接寻址和模拟指针 2．数组和矩阵 3．堆栈和队列及其应用 4．跳表和散列 5．二叉树和其他树 6．合并/搜索应用,堆和堆排序 7．左高树,霍夫曼编码和竞赛树 8．搜索树, A VL树或红黑树,直方图 9．图 10．图和贪婪算法 11．货箱装载,0/1背包,最短路径和生成树 12．分而治之算法 13．动态编程 14．回溯和分枝定界算法 参考书目
1 《数据结构，算法与应用》----C++语言描述 Data Structures,Algorithms,and Applications in C++ Sartaj Sahni 著汪诗林，孙晓东译 机械工业出版社2000年出版教材科，书店均有 2 《数据结构》殷仁昆著清华大学出版社 II 操作系统 课程基本要求 操作系统是计算机类学科的一门核心专业基础课程，具有较强的理论性和实践性。该课程的主要包括进程管理、内存管理、存储管理（包括文件系统与输入/输出系统）、保护与安全等内容的相关概念、设计原理和实现方法。要求： 1.了解操作系统在计算机系统中的作用、地位、发展和特点。 2.理解操作系统的基本概念、主要功能、主要组成部分，掌握操作系统各 个组成部分的设计方法和实现技术。 3.能够运用所学的操作系统原理、方法和技术对相关问题进行分析和解 决。 考试内容 一、导论 1.操作系统的概念 2.计算机系统的操作、存储结构、输入输出结构和计算机系统的体系结构 3.操作系统的结构组成、操作系统的操作及各部分的功能、高速缓冲存储 器CACHE 4.操作系统的分类和运行环境 二、操作系统结构 1.操作系统提供的服务类型 2.操作系统的用户接口类型
(Destnation Postion) glMatrixMode(GL_MODELVIEW) a) glTranslatef(0.0, 0.0, -d); //d>0 b) glTranslatef(0.0, 0.0, d); //d>0 第 1 页共 4 页
第 2 页 共 4 页
A B C g E D a 第 3 页共 4 页
(2)If we can vary the values in the theta array freely, what spatial region can be reached by the tip of the upper arm? 一个中心点在(0.0, 0.2, 0.0) (3)Write out the affine transformation Cube-C. 对于Cube-A:Ry(0)*T(0,0.1,0)*S(0.2,0.2,0.2) 计算得为 0.2 0 0 0.2 0 0 0 0 第 4 页共 4 页
第 4 页 共 4 页 对Cube-B:Ry(0)*T(0,0.2,0)R(z)(45)*T(0,0.5,0)*R(z)(45)*T(0,0.25,0)S(0.05,0.5,0.05) 计算得 0 -1/2 0 -(1+sqrt(2))/4 ? 0 0 sqrt(2)/4+1/5 0 0 1/(20) 0 0 0 0 1 对于Cube-C:Ry(0)*T(0,0.2,0)*R(z)(45)*T(0,0.25,0)*S(0.05,0.5,0.05) 计算得 sqrt(2)/40 -sqrt(2)/40 0 -sqrt(2)/8 sqrt(2)/40 -sqrt(2)/40 0 sqrt(2)/8+1/5 0 0 1/20 0 0 0 0 1
专科《计算机基础》试题 一、单项选择 1．完整的计算机系统由（C）组成。 A．运算器、控制器、存储器、输入设备和输出设备B．主机和外部设备 C．硬件系统和软件系统D．主机箱、显示器、键盘、鼠标、打印机2．以下软件中，（B）是系统软件。 A．Word B．Unix C．Excel D．Microsoft office 3．计算机能直接识别的语言是（ C ）。 Ａ．汇编语言Ｂ．自然语言 C 机器语言Ｄ．高级语言 4．任何程序都必须加载到（ C ）中才能被CPU执行。 A．磁盘B．硬盘C．内存D．外存 5．组成计算机的主机的部件是（C ）。 A．运算器和控制器B．控制器和寄存器C．CPU和内存D．控制器和内存6．下列关于操作系统的叙述中，正确的是（ C ） Ａ．操作系统是软件和硬件之间的接口Ｂ．操作系统是源程序和目标程序之间的接口Ｃ．操作系统是用户和计算机之间的接口Ｄ．操作系统是外设和主机之间的接口7．Windows的目录结构采用的是（A ）。 A．树形结构B．线形结构C．层次结构D．网状结构8．Windows XP操作系统是（ C ） A．多用户多任务操作系统B．多用户单任务操作系统 C．单用户多任务操作系统D．单用户单任务操作系统 9．Windows XP新增的系统维护功能是（ D ）。 A．系统数据备份B．磁盘整理C．磁盘清理D．系统还原 10．对于Windows XP的控制面板，以下说法不正确的是（B ）。 A．控制面板是一个专门用来管理计算机硬件系统的应用程序 B．从控制面板中无法删除计算机中己经安装的声卡设备 C．对于控制面板中的项目，可以在桌面上建立起它的快捷方式 D．可以通过控制面板删除一个己经安装的应用程序 11．在Word 的编辑状态下，可以同时显示水平标尺和垂直标尺的视图方式是（ B ）。 A．普通视图B．页面视图C．大纲视图D．全屏幕显示方式 12．关于Word 2003文档窗口的说法，正确的是（ C ）。 A．只能打开一个文档窗口B．可以同时打开多个文档窗口且窗口都是活动的 C．可以同时打开多个文档窗口，只有一个是活动窗口 D．可以同时打开多个文档窗口，只有一个窗口是可见文档窗口 13．Excel工作表的单元格中（ B ）。 A．只能包含数字B．可以是数字、字符公式等C．只能包含文字D．以上都不是14．如果想在Word 2003的文档中插入页眉和页脚，应当使用( D )菜单。 A．工具B．插入C．格式D．视图 15．在Excel中，若在某单元格插入函数SUM(D2:$D$4)，该函数中对单元格的引用属于（C ）。 A．相对引用B．绝对引用C．混合引用D．交叉引用
一、单选 1.第一台电子数字计算机在美国研制成功的，是于（B）。 A.1940年 B.1946年 C.1950年 D.1959年 2.计算机最基本的工作原理是（D）。 A.机电原理 B.存储程序 C.程序控制 D.存储程序与程序控制 3.计算机领域中，客观事物的属性表示为（D）。 A.模拟量 B.处理后数值 C.信息 D.数据 4.按使用范围分类，可以将电子计算机分为（A）。 A.通用计算机和专用计算机 B.电子数字计算机和电子模拟计算机 C.巨型计算机、大中型机、小型计算机和微型计算机 D.科学与过程计算计算机、工业控制计算机和数据计算机 5.（B）表示计算机辅助设计。 A.CAT B.CAD C.CAM D.CAI 6.在微机的配置中常看到“P4\2.4G”字样，其中数字“2.4G”表示（A）。 A.处理器的时钟频率是2.4GHz B.处理器的运算速度是2.4 C.处理器是Pentium4第2.4 D.处理器与内存间的数据交换速率 7.下列计算机存储器中，读写速度最快的是（B）。 A.硬盘 B.内存 C.光盘 D.U盘
8.（A）是以微型计算机为中心，配以相应的外围设备、电源和辅助电路，以及指挥微型计算机工作的系统软件而构成的。 A.微型计算机系统 B.微型计算机 C.服务器 D.微处理器 10.在下列4个数中（B）数值最大。 A.56 B.80H C.123D D.111101B 11.在计算机的存储单元中，一个ASCII码值占用的字节数为（C）。 A.4 B.2 C.1 D.8 12.组成计算机系统的由两大部分是（A）。 A.硬件系统和软件系统 B.输入设备和输出设备 C.系统软件和应用软件 D.主机和外部设备 13.计算机的指令系统能实现的运算有（B）。 A.数值运算和非数值运算 B.算术运算和逻辑运算 C.图形运算和数值运算 D.算术运算和图象运算 14.（D）是计算机指令的集合。 A.汇编语言 B.模拟语言 C.机器语言 D.程序 15.下列四个计算机存储容量的换算公式中，（D）是错误的。 A.1GB=1024MB B.1MB=1024KB C.1KB=1024B D.1KB=1024MB
山东大学软件学院 软件工程专业《人机交互技术》课程 实验指导书 山东大学 软件学院 2015年9月
《人机交互技术》课程实验教学大纲 一．实验教学的目的 通过《人机交互技术》实验课程的实践，使学生了解《人机交互技术》与计算机图形、程序设计、认知心理学以及计算机硬件的发展等领域密切相关，本课程在2013年春节课程的实验安排采用Android系统，通过开发并创建个Android应用程序，并在PC机上模拟Android 手机环境下或连接手机环境下进行开发和运行。加深学生对人机交互知识的理解，增强学生的实际运用能力和开发高可用性的交互界面的能力，了解和掌握最新的人机交互开发工具和手段，方法。 二．实验教学的任务 了解利用Android系统进行人机交互系统或界面开发的系统通过案例学习，让学生了解不同的人机交互模型设计类型，以及成功与失败案例所带来的启示。通过原型设计使学生了解原型的作用，并了解用户需求对设计一个良好人机交互界面的重要性。通过原型和界面评估，使学生掌握针对交互系统的评估方法。 三．实验教学的环境 在游戏与动漫实训中心的PC机房进行。 开发和运行环境：MS Windows XP 或Windows 7 ； Android2.1及以上版本； JA V A的IDE开发工具– Eclipse，Java开发包— Java SE Development Kit (JDK) JDK 6； Android开发包— Android SDK For Windows 四．具体实验题目名称和学时分配、适用专业及实验性质（设计性、综合性、验证性）
（2）编程实现扩展列表视图的实机界面。 3 （1）编程实现滚动视 图（ScrollView） 2 计算机科学技 术/软件工程 设计性必开 4 基于Android的二维交互 游戏：利用Android2.1以上系 统，搭建二维游戏平台，通过 键盘鼠标交互方式，实现综合 养成、解谜、休闲、角色扮演 和移动应用的3G游戏。 8 计算机科学技 术/软件工程 综合性必开
专科《计算机基础》试题 、 单项选择 1．完整的计算机系统由（ C ）组成。 A ．运算器、控制器、存储器、输入设备和输出设备 B ．主机和外部设备 C ?硬件系统和软件系统 D ?主机箱、显示器、键盘、鼠标、打印机 2．以下软件中， （ B ）是系统软件。 A ? Word B ? Unix C . Excel D . Microsoft office 3．计算机能直接识别的语言是（ C ）。 A.汇编语言 E.自然语言 C 机器语言 D.高级语言 4?任何程序都必须加载到（ C ）中才能被CPU 执行。 A ． 磁盘 B ． 硬盘 5．组成计算机的主机的部件是（ C ）。 A .运算器和控制器 B .控制器和寄存器 6．下列关于操作系统的叙述中，正确的是（ A.操作系统是软件和硬件之间的接口 C.操作系统是用户和计算机之间的接口 7． Windows 的目录结构采用的是（ A ）。 A ．树形结构 B ．线形结构 & Windows XP 操作系统是（C ） A ．多用户多任务操作系统 C .单用户多任务操作系统 9. Windows XP 新增的系统维护功能是（D A .系统数据备份 B .磁盘整理 10．对于 Windows XP 的控制面板，以下说法不正确的是（ B ）。 A .控制面板是一个专门用来管理计算机硬件系统的应用程序 B .从控制面板中无法删除计算机中己经安装的声卡设备 C .对于控制面板中的项目，可以在桌面上建立起它的快捷方式 D .可以通过控制面板删除一个己经安装的应用程序 11．在 Word 的编辑状态下，可以同时显示水平标尺和垂直标尺的视图方式是（ B ）。 A .普通视图 B .页面视图 C .大纲视图 D .全屏幕显示方式 12．关于 Word 2003文档窗口的说法，正确的是（ C ）。 A .只能打开一个文档窗口 B .可以同时打开多个文档窗口且窗口都是活动的 C .可以同时打开多个文档窗口，只有一个是活动窗口 D .可以同时打开多个文档窗口，只有一个窗口是可见文档窗口 13．Excel 工作表的单元格中（ B ）。 A .只能包含数字 B .可以是数字、字符公式等 C .只能包含文字 D .以上都不是 14．如果想在 Word 2003的文档中插入页眉和页脚，应当使用 （ D ） 菜单。 A ．工具 B ．插入 C ．格式 D ．视图 15．在 Excel 中，若在某单元格插入函数 SUM （D2:$D$4） ，该函数中对单元格的引用属于（ C ）。 A ．相对引用 B ．绝对引用 C ．混合引用 D ．交叉引用 16．Excel 2003 的工作表最多有（ C ）列 A ． 16 B ． 65536 C ． 256 D ． 1024 17．在 PowerPoint2003 中，在（ D ）视图“超链接”功能才起作用。 C ．内存 D ．外存 C . CPU 和内存 D .控制器和内存 C ） E.操作系统是源程序和目标程序之间的接口 D.操作系统是外设和主机之间的接口 C ．层次结构 D ．网状结构 B .多用户单任务操作系统 D .单用户单任务操作系统 ）。 C .磁盘清理 D .系统还原
全国计算机专业大学排名一览表 计算机系统结构前20名(总共47所高校) 1.清华大学， 2.华中科技大学， 3.西安交通大学， 4.上海交通大学， 5.浙江大学， 6.西安电子科技大学， 7.武汉大学， 8.复旦大学， 9.哈尔滨工业大学，10.东北大学，11.北京大学，12.东南大学，13.北京航空航天大学，14.中国科学技术大学，15.电子科技大学，16. 吉林大学，17.南京理工大学，18.重庆大学，19.北京科技大学，20.同济大学 计算机软件与理论前40名(总共158所高校) 1.上海交通大学， 2.南京大学， 3.北京大学， 4.北京航空航天大学， 5.吉林大学， 6.清华大学， 7.浙江大学， 8.西安交通大学， 9. 东南大学，10.电子科技大学，11.中国科学技术大学，12.哈尔滨工 业大学，13.大连理工大学，14.华中科技大学，15.武汉大学，16. 复旦大学，17.中山大学，18.西安电子科技大学，19.东北大学，20.西北工业大学，21.北京理工大学，22.北京交通大学，23.南京理工 大学，24.重庆大学，25.山东大学，26.四川大学，27.中南大学，28.云南大学，29.上海大学，30.同济大学，31.河海大学，32.北京 邮电大学，33.山东科技大学，34.中国人民大学，35.南京邮电大学，36.西北大学，37.武汉理工大学，38.贵州大学，39.陕西师范大学，40.天津大学 1.清华大学， 2.浙江大学， 3.哈尔滨工业大学， 4.北京大学， 5.东南大学， 6.东北大学， 7.西北工业大学， 8.安徽大学， 9.上海交 通大学，10.华中科技大学，11.北京航空航天大学，12.北京理工大学，13.西安电子科技大学，14.西安交通大学，15.吉林大学，16. 西南交通学，17.大连理工大学，18.电子科技大学，19.北京工业大学，20.重庆大学，21.复旦大学，22.哈尔滨工程大学，23.武汉理 工大学，24.武汉大学，25.同济大学，26.南京大学，27.中国科学 技术大学，28.华南理工大学，29.南京理工大学，30.四川大学，31.
山东大学计算机学院博士生导师简介 1．博士生导师陈宝权教授 陈宝权教授，于1999年获纽约州立大学石溪分校计算机系博士学位，现任中国计算机学会常务理事及青工委主任，SIGGRAPH ASIA 指导委员会委员，SIGGRAPH Asia 2014会议主席，IEEE 可视化会议2005 年主席及2004 年程序委员会主席，主要从事大规模城市场景三维获取及海量数据可视化研究，获2003 年美国NSF CAREER奖，2005年IEEE可视化国际会议最佳论文奖，2008 年入选中科院"百人计划"，2010 年获国家杰出青年科学基金资助。 2．博士生导师孟祥旭教授 孟祥旭教授，于1998年获中国科学院计算所博士学位。现任山东计算机学会理事长，山东省制造业信息化专家组组长，山东省软件工程重点实验室主任，中国计算机学会计算机辅助设计与图形学专委会副主任委员。获山东省有突出贡献的中青年专家称号，享受国务院政府特殊津贴，主要从事图形学与可视化、人机交互与虚拟现实和服务计算等研究，获得国家科技进步二等奖2项及省部级奖8项。 3．博士生导师张彩明教授 张彩明教授，获日本东京工业大学博士学位，美国肯塔基大学博士后；现任几何设计与计算专业委员会主任、CADDM英文杂志主编；主要从事几何设计与信息可视化研究。获省部级一等奖一次、二等奖6次；山东省有突出贡献的中青年专家，获山东大学优秀教师称号和宝钢优秀教师奖。 4. 博士生导师马军教授 马军教授，获日本九州大学博士学位。现任中国计算机学会大数据、自然语言处理、信息检索和理论专委会委员。主要从是信息检索与数据挖掘、社会网络分析、机器学习和多媒体检索等研究。
2019年4月 第一章绪论 1【多选题】关于信息社会，下列说法不正确的是（） A、计算机的发明和广泛使用是人类社会进入信息社会的唯一标志。 B、信息社会中所有的工业生产都是自动化的。 C、在信息社会，信息技术催生大批新兴产业，同时，传统产业也普遍实行技术改造。 D、信息社会中信息产业高度发展，在产业结构优势的地位日益突出。 E、在信息社会，信息、知识成为重要的生产力要素。 F、计算机的发明是第三次科技革命的重要标志，是人类文明史上继蒸汽技术革命和电力技术革命之后科技领域里的又一次重大飞跃。 正确答案： AB 2【多选题】关于信息技术（Information Technology，IT）下列说法正确的是（）A、广义而言，能充分利用与扩展人类信息器官功能的各种方法、工具与技术都可称为信息技术。 B、现代信息技术是指以微电子技术、计算机技术和通信技术为特征的技术。 C、信息技术就是计算机技术和计算机网络技术。 D、在信息社会，所有的信息处理中都用到了信息技术。 E、在信息处理的每一个环节，都必须使用信息技术。 F、信息技术无法对工业社会形成的传统设备进行技术改造，成为智能设备。 正确答案： AB 3【多选题】在人体器官中，下列说法不正确的是（） A、大脑的思维是对外部事物的直接反应。 B、大脑是一种直接感觉器官。 C、人体器官可分为直接感觉器官和间接感觉器官。 D、大脑具有记忆和思维功能。 E、大脑是一种间接感觉器官。 F、大脑是人体的思维器官。 正确答案： AB 4【多选题】二进制是由下列哪位科学家首先提出来的（） A、莱布尼兹
B、布尔 C、巴贝奇 D、图灵 E、冯?诺依曼 正确答案： A 5【多选题】对于计算思维，下列说法错误的是（） A、计算思维是计算机科学家独有的思维方式。 B、计算思维是一种借助于计算能力进行问题求解的思维和意识。 C、计算思维的产生与信息社会发展的时代背景有关，工具影响我们的思维方式。 D、计算思维的本质是抽象和自动化。 E、计算思维并不是继逻辑思维和形象思维以后的人类思维的第三种形态。 正确答案： A 6【多选题】下列内容属于信息素养（Information Literacy）的是（） A、信息意识 B、信息知识 C、信息能力 D、信息道德 E、信息素质 F、信息水平 正确答案： ABCD 7【多选题】关于思维，下列说法正确的是（） A、思维是人类的大脑对外部客观世界概括的和间接的反应。 B、思维是人类凭借知识、经验对客观事物进行的间接的应。 C、思维是在表象、概念的基础上进行分析、综合、判断、推理等认识活动的过程。 D、思维是大脑活动，与工具无关。 E、思维是人类与生俱来的，与后天的学习无关。 正确答案： ABC 8【多选题】关于推理，下列说法正确的是（） A、推理是由已知判断，根据一定的思维规则导出一个或一组新的判断的过程。 B、推理是逻辑思维的重要形式。 C、三段论是一种演绎推理形式。 D、归纳推理比演绎推理更具有说服力。
第二章算法入门 由于时间问题有些问题没有写的很仔细，而且估计这里会存在不少不恰当之处。另，思考题2-3 关于霍纳规则，有些部分没有完成，故没把解答写上去，我对其 c 问题有疑问，请有解答方法者提供个意见。 给出的代码目前也仅仅为解决问题，没有做优化，请见谅，等有时间了我再好好修改。 插入排序算法伪代码 INSERTION-SORT(A) 1 for j ← 2 to length[A] 2 do key ←A[j] 3 Insert A[j] into the sorted sequence A[1..j-1] 4 i ←j-1 5 while i > 0 and A[i] > key 6 do A[i+1]←A[i] 7 i ←i ? 1 8 A[i+1]←key C#对揑入排序算法的实现: public static void InsertionSort
Chapter21 Michelle Bodnar,Andrew Lohr April12,2016 Exercise21.1-1 EdgeP rocessed initial{a}{b}{c}{d}{e}{f}{g}{h}{i}{j}{k} (d,i){a}{b}{c}{d,i}{e}{f}{g}{h}{j}{k} (f,k){a}{b}{c}{d,i}{e}{f,k}{g}{h}{j} (g,i){a}{b}{c}{d,i,g}{e}{f,k}{h}{j} (b,g){a}{b,d,i,g}{c}{e}{f,k}{h}{j} (a,h){a,h}{b,d,i,g}{c}{e}{f,k}{j} (i,j){a,h}{b,d,i,g,j}{c}{e}{f,k} (d,k){a,h}{b,d,i,g,j,f,k}{c}{e} (b,j){a,h}{b,d,i,g,j,f,k}{c}{e} (d,f){a,h}{b,d,i,g,j,f,k}{c}{e} (g,j){a,h}{b,d,i,g,j,f,k}{c}{e} (a,e){a,h,e}{b,d,i,g,j,f,k}{c} So,the connected that we are left with are{a,h,e},{b,d,i,g,j,f,k}, and{c}. Exercise21.1-2 First suppose that two vertices are in the same connected component.Then there exists a path of edges connecting them.If two vertices are connected by a single edge,then they are put into the same set when that edge is processed. At some point during the algorithm every edge of the path will be processed,so all vertices on the path will be in the same set,including the endpoints.Now suppose two vertices u and v wind up in the same set.Since every vertex starts o?in its own set,some sequence of edges in G must have resulted in eventually combining the sets containing u and v.From among these,there must be a path of edges from u to v,implying that u and v are in the same connected component. Exercise21.1-3 Find set is called twice on line4,this is run once per edge in the graph,so, we have that?nd set is run2|E|times.Since we start with|V|sets,at the end 1
1.1微型计算机系统的三个层次 了解微型计算机系统从局部到全局划分三个层次，结构。微型处理器： 微处理器包括算术逻辑部件ALU （Arithmetic Logic Unit）,控制部件CU （Control Unit）和寄存器组R （Registers）三个基本部分和内部总线。 微型计算机 微型计算机（Microcomputer）是以微处理器为核心，加上由大规模集成电路制作的存储器M （ROM和RAM）、I/O （输入/输出）接口和系统总线组成的。微型计算机系统 微型计算机系统（Micro Computer System）是以微型计算机为核心，再配以相 应的外围设备,电源、辅助电路和控制微型计算机工作的软件而构成的完整的计算系统。 软件分为 系统软件和应用软件两大类: 系统软件是用来支持应用软件的开发与运行的，它包括操作系统、标准实用程序和各种语言处理程序等。 应用软件是用来为用户解决具体应用问题的程序及有关的文档和资料。 1.2微型计算机的硬件结构一?冯.诺依曼结构 冯?诺依曼结构的特点： 1）曲运算器、控制器、存储器、输入设备和输出设备五大部分组成； 2）数据和程序以二进制代码形式不加区别地存放在存储器小，存放位置由地址指定，地址码也为二进制形式； 3）控制器是根据存放在存储器中的指令序列即程序来工作的，并由一个程序计数器（即指令地址计数器）控制指令的执行。控制器具有判断能力，能根据计算结果选择不同的动作流程。 二.微型计算机主要组成部分的结构及功能 1.微处理器 算术逻辑单元：是运算器的核心。它是以全加器为基础，辅之以移位寄存器及相 应控制逻辑组合而成的电路，在控制信号的作用下可完成加、 减、乘、除四则运算和齐种逻辑运算。 累加器ACC、累加锁存器和暂存器 标志寄存器FR :用于寄存ALU操作结果的某些重耍状态或特征，如是否溢出、是 否为零、是否为负、是否有进位、是否有偶数个T等 寄存器组RS：是微处理器的内部RAM,因受芯片面积和集成度所限，其容量（即寄存器数目）不可能很多。寄存器组可分为专用寄存器和通用寄存器。在需耍重复使用 某些操作数或中间结
Chapter6 Michelle Bodnar,Andrew Lohr December31,2016 Exercise6.1-1 At least2h and at most2h+1?1.Can be seen because a complete binary tree of depth h?1hasΣh?1 i=02i=2h?1elements,and the number of elements in a heap of depth h is between the number for a complete binary tree of depth h?1exclusive and the number in a complete binary tree of depth h inclusive. Exercise6.1-2 Write n=2m?1+k where m is as large as possible.Then the heap consists of a complete binary tree of height m?1,along with k additional leaves along the bottom.The height of the root is the length of the longest simple path to one of these k leaves,which must have length m.It is clear from the way we de?ned m that m= lg n . Exercise6.1-3 If there largest element in the subtee were somewhere other than the root, it has a parent that is in the subtree.So,it is larger than it’s parent,so,the heap property is violated at the parent of the maximum element in the subtree Exercise6.1-4 The smallest element must be a a leaf node.Suppose that node x contains the smallest element and x is not a leaf.Let y denote a child node of x.By the max-heap property,the value of x is greater than or equal to the value of y.Since the elements of the heap are distinct,the inequality is strict.This contradicts the assumption that x contains the smallest element in the heap. Exercise6.1-5 Yes,it is.The index of a child is always greater than the index of the parent, so the heap property is satis?ed at each vertex. 1
计算机基础1 一、单项选择 1 ?最早设计计算机的目的是进行科学计算，但其主要的都是用于（ B ）。 A .科研B.军事C.商业 D .管理 2 .下列术语中，属于显示器性能指标的是（C）。 A .速度 B .可靠性C.分辨率D.精度 3 .早期的计算机体积较大、耗能高、速度也较慢，其主要原因是制约于（ D ）。 A. 工艺水平 B .元器件 C .设计水平 D .元材料 4 .能够将高级语言源程序加工为目标程序的系统软件是（C）。 A. 解释程序 B .汇编程序 C .编译程序 D .编辑程序 5. 计算机主机的组成是（ B ）。 A .运算器加控制器 B .中央处理器加主存储器 C .运算器加外设 D .运算器加存储器 6 .字长16位的计算机，它表示（A ）。 A. 数以16位二进制数表示B .数以16进制来表示 C .可处理16位字符串 D .数以两个8进制表示 7 .在计算机内部，数据加工、处理和传送的形式是（ A ）。 A .二进制码 B .八进制码C.十进制码 D .十六进制码 8. 光盘是一种已广泛使用的外存储器，英文缩写CD-ROM指的是（A）。 A. 只读型光盘 B .一次写入光盘 C .追记型光盘 D .可抹型光盘 9 .十进制数向二进制数进行转换时，十进制数91相当于二进制数（D）。 A. 1101011 B. 1101111 C. 1110001 D. 1011011 10. 在计算机中表示存储容量时，下列描述中正确的是（C）。 A .1KB=1024M B B. 1KB=1000B C. 1MB=1024KB D. 1MB=1024GB 11. 下列字符中ASCII码值最小的是（A ）。 A . a B . A C. f D. Z 12. “ 32位微型计算机”中的32指的是（D）。 A .微机型号 B .内存容量 C .运算速度 D .机器字长 13. 在计算机中，应用最普遍的字符编码是（ D ）。 A .机器码 B .汉字编码 C . BCD码 D . ASCII码 14. 构成计算机物理实体的部件被称为（B ） A. 计算机系统 B .计算机硬件C.计算机软件D .计算机程序 15. 某单位的人事管理程序属于（C ）。 A .系统程序 B .系统软件C.应用软件 D .目标软件 16. 操作系统是（A ）的接口。 A. 用户与软件 B.系统软件与应用软件 C .主机与外 D .用户与计算机 17. 在Windows资源管理器中选定了文件或文件夹后，若要将它们移动到不同驱动 器的文件夹中，操作为（B ）。 A .按下Ctrl键拖动鼠标 B .按下Shift键拖动鼠标 C.直接拖动鼠标 D .按下Alt键拖动鼠标 18. 在Windows桌面底部的任务栏中，可能出现的图标有（A ）。 A. “开始”按钮、“快速启动工具栏”、应用程序图标及“指示器” B. 资源管理器”按钮、快速启动工具栏”、应用程序图标及 指示器” C. 开始”按钮、资源管理器”快捷菜单、应用程序图标及指示器” D. “开始”按钮、“快速启动工具栏”、“指示器”及“屏幕设置”快捷菜单 19. 在Windows中快速获得硬件的有关信息可通过（C ）。 A .鼠标右键单击桌面空白区，选择属性”菜单项 B. 鼠标右键单击开始”菜单 C. 鼠标右键单击我的电脑”，选择属性”菜单项 D. 鼠标右键单击任务栏空白区，选择“属性”菜单项 20. 在Windows中，用户建立的文件默认具有的属性是（ D ）。 A .隐藏 B .只读 C .系统 D .存档
Chapter7 Michelle Bodnar,Andrew Lohr April12,2016 Exercise7.1-1 13199512874212611 13199512874212611 13199512874212611 91913512874212611 95131912874212611 95131912874212611 95819121374212611 95871213194212611 95874131912212611 95874131912212611 95874219122113611 95874261221131911 95874261121131912 Exercise7.1-2 If all elements in the array have the same value,PARTITION returns r.To make PARTITION return q= (p+r)/2 when all elements have the same value,modify line4of the algorithm to say this:if A[j]≤x and j(mod2)= (p+1)(mod2).This causes the algorithm to treat half of the instances of the same value to count as less than,and the other half to count as greater than. Exercise7.1-3 The for loop makes exactly r?p iterations,each of which takes at most constant time.The part outside the for loop takes at most constant time.Since r?p is the size of the subarray,PARTITION takes at most time proportional to the size of the subarray it is called on. Exercise7.1-4 To modify QUICKSORT to run in non-increasing order we need only modify line4of PARTITION,changing≤to≥. 1
2019山东大学计算机考研参考书目及研究方向 山东大学（Shandong University），简称山大（SDU），由中华人民共和国教育部直属，中央直管副部级建制，位列“211工程”、“985工程”、“世界一流大学和一流学科”，入选“2011计划”、“珠峰计划”、“111计划”，是一所综合性全国重点大学。 据2018年8月山大官网信息显示，山大总占地面积8000余亩（含青岛校区约3000亩），形成了一校三地（济南、威海、青岛）八个校园（济南中心校区、洪家楼校区、趵突泉校区、千佛山校区、软件园校区、兴隆山校区及威海校区、青岛校区）的办学格局；设有有55个教学院系，4所附属医院，3所非隶属附属医院，11所教学、实习医院；拥有一级学科博士学位授权点44个，一级学科硕士学位授权点55个，专业学位博士点3个，专业学位硕士点27个，本科专业117个，博士后科研流动站41个；在职教职工7493人（不含附属医院），其中教授1246人，博士生导师897人；各类全日制学生达6万人，其中，全日制本科生40789人，研究生18816人，留学生3791人。 软件工程研究方向： 01人机交互与虚拟现实 02智能图形图像处理与与信息可视化 03密码学与信息安全
04网络与系统安全 05数据与知识工程 06机器学习与数据挖掘 07高性能计算与大数据处理08软件体系结构 09软件服务工程 10媒体计算与图形学 11社会计算 12计算机网络 13智能算法 14智能计算系统 15人工智能 软件工程考研科目 学硕： ①101思想政治理论 ②201英语一
③301数学一 ④849软件工程专业基础综合专硕： ①101思想政治理论 ②204英语二 ③302数学二 ④909数据结构
第一章绪论 1. [多选题] 阿兰?麦席森?图灵（Alan Mathison Turing）对计算机科学的发展做出了巨大贡献，下列说法正确的是（） A.图灵是著名的数学家、逻辑学家、密码学家，被称为计算机科学之父。 B.图灵最早提出关于机器思维的问题，被称为人工智能之父。 C.“图灵奖”是为奖励那些对计算机科学研究与推动计算机技术发展有卓越贡献的杰出科学家而设立的。 D.图灵创立了数理逻辑学。 E.图灵发明了二进制。 F.图灵设计了第一台电子计算机。 正确答案：ABCD 2. [多选题] 在人体器官中，下列说法不正确的是（） A.大脑的思维是对外部事物的直接反应。 B.大脑是一种直接感觉器官。 C.人体器官可分为直接感觉器官和间接感觉器官。 D.大脑具有记忆和思维功能。 E.大脑是一种间接感觉器官。 F.大脑是人体的思维器官。 正确答案：AB 3. [多选题] 对于计算思维，下列说法错误的是（） A.计算思维是计算机科学家独有的思维方式。 B.计算思维是一种借助于计算能力进行问题求解的思维和意识。 C.计算思维的产生与信息社会发展的时代背景有关，工具影响我们的思维方式。 D.计算思维的本质是抽象和自动化。 E.计算思维并不是继逻辑思维和形象思维以后的人类思维的第三种形态。 正确答案：A 4. [多选题] 关于推理，下列说法正确的是（） A.推理是由已知判断，根据一定的思维规则导出一个或一组新的判断的过程。 B.推理是逻辑思维的重要形式。
C.三段论是一种演绎推理形式。 D.归纳推理比演绎推理更具有说服力。 E.所有可能的假言推理都是逻辑正确的。 正确答案：ABC 5. [多选题] 对于计算思维，下列说法正确的是（） A.计算思维是运用计算机科学的基础概念进行问题求解、系统设计、以及人类行为理解等涵盖计算机科学之广度的一系列思维活动。 B.计算思维的本质是抽象和自动化。 C.计算思维是一种这种借助于计算能力进行问题求解的思维和意识。 D.计算思维的产生于信息社会发展的时代背景有关，工具影响我们的思维方式。 E.计算思维是计算机科学家的思维。 F.计算思维是计算机相关从业人员的思维方式。 正确答案：ABCD 6. [多选题] 关于信息技术（Information Technology，IT）下列说法正确的是（）A.广义而言，能充分利用与扩展人类信息器官功能的各种方法、工具与技术都可称为信息技术。 B.现代信息技术是指以微电子技术、计算机技术和通信技术为特征的技术。 C.信息技术就是计算机技术和计算机网络技术。 D.在信息社会，所有的信息处理中都用到了信息技术。 E.在信息处理的每一个环节，都必须使用信息技术。 F.信息技术无法对工业社会形成的传统设备进行技术改造，成为智能设备。 正确答案：AB 7. [多选题] 关于思维，下列说法正确的是（） A.思维是人类的大脑对外部客观世界概括的和间接的反应。 B.思维是人类凭借知识、经验对客观事物进行的间接的应。 C.思维是在表象、概念的基础上进行分析、综合、判断、推理等认识活动的过程。 D.思维是大脑活动，与工具无关。 E.思维是人类与生俱来的，与后天的学习无关。 正确答案：ABC 8. [多选题] 下列内容属于信息素养（Information Literacy）的是（）