DATA STRUCTURE 数据结构 - 重庆邮电大学计算机科学与

机密 启用前重庆邮电大学2021年攻读硕士学位研究生入学考试试题科目名称：数据结构（A）卷科目代码：802考生注意事项1、答题前，考生必须在答题纸指定位置上填写考生姓名、报考单位和考生编号。

2、所有答案必须写在答题纸上，写在其他地方无效。

3、填（书）写必须使用黑色字迹钢笔、圆珠笔或签字笔。

4、考试结束，将答题纸和试题一并装入试卷袋中交回。

5、本试题满分150分，考试时间3小时。

一、选择题（本大题共15小题，每小题2分，共30分）1设N是描述问题规模的非负整数，下列程序段的时间复杂度是（）。

static int fun(int N) {if (N == 1) return 0;return 1 + fun(N/2);}A．O(log N) B. O(N) C. (N log N) D. O(N2)2一些随机产生的数采用线性链表存储，在下面这些排序方法中，（）的时间复杂度是最小的。

A．插入排序 B. 快速排序 C. 堆排序 D. 归并排序3一个栈的输入序列为a，b，c，d，e，则下列序列中不可能是栈的输出序列的是（）。

A．b c d a e B．e d a c b C．b c a d e D．a e d c b4实现一个队列需要（）个栈。

A．1 B. 2 C. 3 D. 45下面（）是一颗满二叉树的结点个数。

A.8B.13C.14D.156若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为（）。

A.X的双亲B.X的右子树中最左的结点C.X的左子树中最右的结点D.X的左子树中最右的结点7下列序列中，哪一个是堆（）？A.75, 65, 30, 15, 25, 45, 20, 10B.75, 65, 45, 10, 30, 25, 20, 15C.75, 45, 65, 30, 15, 25, 20, 15D.75, 45, 65, 10, 25, 30, 20, 158一棵Huffman树共有203个结点，对其Huffman编码，共能得到（）个不同的码字。

2019重邮软件工程考研初试科目、参考书目、招生人数汇总本文将由新祥旭徐老师全方位的对重庆邮电大学计算机专业考研进行解析，主要有以下几个板块：学院介绍，专业情况介绍，2019录取情况分析，考研科目介绍，专业课参考书目及备考指导等几大方面。

一、学院介绍1、计算机科学与技术学院是在我校原计算机系的基础上发展形成的。

1989年，学校为适应计算机技术迅猛发展，信息产业部各企事业单位对计算机技术人才的迫切需求，在原电信工程系计算机教研室和校计算中心的基础上组建了原计算机系。

2001年学校院系调整，将原计算机系和原信息与计算科学系的数学部分合并组建了计算机科学与技术学院。

2007年下半年，学校进行学科结构调整，将数学部分划归新组建的数理学院；2010年初，应用技术学院计算机学科部分划归我院，形成了目前的计算机科学与技术学院。

我院是中国人工智能学会粗糙集与软计算专业委员会的挂靠单位，是重庆计算机学会、重庆市人工智能学会副理事长单位等。

2、重庆邮电大学科大讯飞人工智能学院（简称重邮讯飞智能学院）是以重庆邮电大学为办学主体，以重庆邮电大学和科大讯飞股份有限公司联合成立的理事会为管理主体，依托重庆邮电大学在信息通信领域的学科专业优势，深度融合科大讯飞股份有限公司在人工智能领域一流的技术、产业和专家资源，共同负责人才培养方案、课程设置和教学过程管理，以公办全日制本科及研究生学历人才培养为主实体化运营的学院。

3、软件工程学院成立于2002 年，是重庆市首家示范性软件学院，是国家卓越工程师培养单位、重庆市软件人才培养基地和服务外包软件人才培养基地;软件工程学科是全国首批软件工程一级学科硕士学位授权点和重庆市重点学科，软件工程专业是国家级特色专业。

二、计算机专业考试科目计算机学硕：①101思想政治理论②201英语一③301数学一④802 数据结构注：1.软件工程专硕考试科目为数二、英二，其余与学硕一致2.软件学院软工学硕科目设置计算机学硕一致。

重庆邮电大学2022年[数据结构]考研真题一、选择题1．对于双向循环链表，每个结点有两个指针域next和prior，分别指向前驱和后继。

在p指针所指向的结点之后插入s指针所指结点的操作应为（）。

A.p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;B.p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;C.s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;D.s->prior=p;s->next=p->next;p->next->prior=s;p->next=s; 2．由abc,3个结点可以构造出多少种不同的二叉树？（）A.2B.3C.4D.53. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为（）。

A.BA+141B.BA+180C.BA+222D.BA+2254. 一个栈的输入序列为123，则下列序列中不可能是栈的输出序列的是（）。

A.231B.321C.312D.1235. 下述编码中哪一个不是前缀码（）。

A.（00，01，10，11）B.（0，1，00，11）C.（0，10，110，111）D.（1，01，000，001）6. 当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组A[l..n]中时，数组中第i个结点的左孩子为（）。

A.A[2i](2i=<n)B.A[2i+1](2i+1=<n)C.A[i/2]D.无法确定7. 假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是（）。

重邮2018数据结构题解重庆邮电大学（以下简称重邮）是一所以信息与通信技术为特色的综合性大学，其计算机科学与技术专业一直以来都备受瞩目。

在该专业中，数据结构是一门非常重要的课程，也是考核学生编程能力和算法思维的重要一环。

下面将为大家介绍一道重邮2018年数据结构题目的解题思路。

题目描述如下：给定一个整数数组nums，找到其中两个数使得它们的和等于一个给定的目标值target，并返回这两个数的索引。

假设每个输入只对应唯一的答案，而且不可以重复利用相同的元素。

解题思路如下：1. 首先，我们可以使用一个哈希表来存储数组中的元素及其对应的索引。

遍历数组nums，将每个元素及其索引存入哈希表中。

2. 接下来，我们再次遍历数组nums，对于每个元素nums[i]，我们可以通过计算target与nums[i]的差值diff，然后在哈希表中查找是否存在这个差值。

3. 如果存在这个差值，且这个差值的索引不等于当前元素的索引i，那么我们就找到了满足条件的两个数。

我们可以将这两个数的索引存入一个结果数组中，并返回该结果数组。

4. 如果遍历完整个数组nums后仍然没有找到满足条件的两个数，那么说明不存在这样的两个数，我们可以返回一个空数组。

下面是使用C++语言实现的代码：```cpp#include <iostream>#include <vector>#include <unordered_map>using namespace std;vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> hash;vector<int> result;for (int i = 0; i < nums.size(); i++) {hash[nums[i]] = i;}for (int i = 0; i < nums.size(); i++) {int diff = target - nums[i];if (hash.count(diff) && hash[diff] != i) {result.push_back(i);result.push_back(hash[diff]);break;}}return result;}int main() {vector<int> nums = {2, 7, 11, 15};int target = 9;vector<int> result = twoSum(nums, target);if (result.empty()) {cout << "No two sum solution" << endl;} else {cout << "The indices of the two numbers are: " << result[0] << " and " << result[1] << endl;}return 0;}```以上就是对重邮2018数据结构题目的解题思路和代码实现。

重庆邮电大学计算机科学与技术学院2005——2006学年第二学期中期教学检查汇报材料2006年是我校发展史上具有里程碑意义的一年，学校正式更名为重庆邮电大学。

为了适应大学的发展要求，适应教育现代化、信息产业化以及西部大开发战略发展要求，学校致力于建设以信息学科为特色，以工科、理科、商科为主，兼顾人文科学、社会科学、医学等学科门类，以发展本科教育为主，积极发展研究生教育，在主要学科拥有博士学位授予权的高水平教学科研型大学。

2006年同时也是计算机科学与技术学院教学工作硕果累累的一年。

在学校相关职能部门以及计算机学院党政部门的领导下，各教学部老师团结一致，以培养高质量的社会急需高级专门人才为目标，强化思想认识和责任意识，狠抓教学工作，努力提高教学质量、办学水平和学术水平，取得了良好的成效。

现根据各教学单位教学工作的开展情况，结合学校相关职能部门对我院的督导检查情况，我院2005－2006学年第二学期的中期教学情况总结如下：一、毕业设计进展顺利，师生交流和谐融洽计算机学院2006届毕业设计工作已于2005年12月启动。

按照计算机学院文件《毕业设计（论文）管理实施条例》的规定，各教学部针对计算机科学与技术专业、地理信息系统专业、信息计算科学专业和信息安全专业的培养目标和计划，共近200位指导教师设计了400多个题目。

设计题目涉及范围宽广。

学院鼓励学生自报题目，教师和学生之间指导和被指导的关系由教师和学生采用双向选择方式自愿确定。

在双方无法自愿达成指导和被指导关系时，由学院指定指导关系。

在管理毕业设计工作的各个环节上，做到了以下几个方面：①要求教师在上报题目时还必须包含研究或设计目标，主要内容、计划进度安排和成果要求。

②指导教师必须熟悉自己所指导的课题内容，掌握有关资料，提前做好准备工作。

③指导教师应指导学生定出自己的毕业设计(论文)的进度计划，严格要求学生按时独立完成任务。

④毕业设计(论文)阶段正值学生走向工作岗位的前夕，学生的思想比较活跃，指导教师应充分利用这一时机，在对学生进行业务指导的同时，对学生加强思想道德品质的培养，做到既教书又育人。

实用标准文档文案大全第1章数据结构基础结构之美无处不在：说到结构，任何一件事物都有自己的结构，就如可以看得见且触摸得到的课桌、椅子，还有看不见却也存在的化学中的分子、原子。

可见，一件事物只要存在，就一定会有自己的结构。

一幅画的生成，作家在挥毫泼墨之前，首先要在数尺素绢之上做结构上的统筹规划、谋篇布局。

一件衣服的制作，如果在制作之前没有对衣服的袖、领、肩、襟、身等各个部位周密筹划，形成一个合理的结构系统，便无法缝制出合体的衣服。

还有教育管理系统的结构、通用技术的学科结构和课堂教学结构等。

试想一下，管理大量数据是否也需要用到数据结构呢？本章知识要点：数据结构的基本概念数据类型和抽象数据类型算法和算法分析1.1 数据结构的基本概念计算机科学是一门研究数据表示和数据处理的科学。

数据是计算机化的信息，它是计算机可以直接处理的最基本和最重要的对象。

无论是进行科学计算，还是数据处理、过程控制、对文件的存储和检索以及数据库技术等计算机应用，都是对数据进行加工处理的过程。

因此，要设计出一个结构良好而且效率较高的程序，必须研究数据的特性、数据间的相互关系及其对应的存储表示，并利用这些特性和关系设计出相应的算法和程序。

计算机在发展的初期，其应用范围是数值计算，所处理的数据都是整型、实型和布尔型等简单数据，以此为加工、处理对象的程序设计称为数值型程序设计。

随着计算技术的发展，计算机逐渐进入到商业、制造业等其他领域，广泛地应用于数据处理和过程控制中。

与此相对应，计算机所处理的数据也不再是简单的数值，而是字符串、图形、图像、语音和视频等复杂的数据。

这些复杂的数据不仅量大，而且具有一定的结构。

例如，一幅图像是一个由简单数值组成的矩阵，一个图形中的几何坐标可以组成表。

此外，语言编译过程中所使用的栈、符号表和语法树，操作系统中用到的队列、磁盘目录树等，都是有结构的数据。

数据结构所研究的就是这些有结构的数据，因此，数据结构知识无论是对研制系统软件还是对开发应用软件来说，都非常重要，是学习软件知识和提高软件设计水平的重要基础。

《程序设计、算法与数据结构（一）》教学大纲课程编号：0812000217课程名称：程序设计、算法与数据结构（一）英文名称：Programming,Algorithm and Data Structure I学分：3 课程性质：必修总学时：48 其中，讲授48学时，实验0学时，上机0学时，实训0学时适用专业：网络工程建议开设学期： 1先修课程：无开课单位：计算机与通信工程学院一、课程简介《程序设计、算法与数据结构（一）》是计算机科学与技术、软件工程、网络工程、通信工程专业基础课程，是课程群的启蒙课，也是学生进入大学后的第一门程序设计类课程，其目的是以C语言程序设计为基础，使学生熟悉C程序设计的基本语法，通过大量的编程练习，引导学生进入程序设计的殿堂，培养学生基本的数据结构和算法分析能力，为后续课程的学习打下基础。

二、课程目标与毕业要求依据2017培养方案中的毕业要求，考虑本课程与专业毕业要求的支撑关系，制定本课程学习目标。

课程目标1：通过程序三种基本控制结构，函数等知识点的学习，要求学生掌握结构化程序设计的基本思想，深入领会自顶向下、逐步求精的设计方法，识别网络工程项目的设计与开发过程中功能模块划分的问题。

（支持毕业要求 2.1能运用数学、自然科学及网络工程的基本原理，识别和判断网络工程问题的关键环节。

）课程目标2：在程序设计C语言后阶段学习过程中，针对成绩管理信息系统大作业的要求，将同学分组了解系统功能与应用背景，对具体的开发任务进行分工联调并编程实现。

通过系统实现强化个体的角色意识和团队意识。

（支撑毕业要求9.1：能够理解多学科背景下的团队中每个角色的定位与责任，具有团队合作意识，能够胜任个体、团队成员的角色任务。

）课程目标3：通过学习标准的C语言程序设计语法，运用函数、线性表、字符串、链表等基本知识，通过学习算法的描述方法，使学生能将实际问题转换成计算机描述的算法问题，培养学生运用程序算法的描述方法进行交流的能力。

计算机科学专业英语词汇(整理版)1. 算法 (Algorithm)算法是指一系列解决问题的明确步骤或规则。

它在计算机科学中起到非常关键的作用，用于解决各种计算问题。

2. 编程 (Programming)编程是指使用计算机语言来创建计算机程序的过程。

它涉及到编写代码、调试程序以及优化程序等步骤。

3. 数据结构 (Data Structure)数据结构是指在计算机中组织和存储数据的方式。

常见的数据结构包括数组、链表、栈和队列等。

4. 网络 (Network)网络是指将多台计算机连接在一起，使它们可以相互通信和共享资源的系统。

常见的网络类型包括局域网(LAN)、广域网(WAN) 和互联网 (Internet)。

5. 数据库 (Database)数据库是指用于存储和管理数据的系统。

它提供了方便的数据访问和数据管理功能，常用于各种应用程序中。

6. 操作系统 (Operating System)操作系统是计算机系统中的核心软件，它负责管理和控制计算机的硬件和软件资源。

常见的操作系统有Windows、Mac OS和Linux等。

编译器是将高级编程语言代码转换为机器语言代码的工具。

它将程序员编写的源代码转化为计算机可以执行的指令集。

8. 虚拟现实 (Virtual Reality)虚拟现实是一种通过计算机生成的仿真环境，使用户可以与虚拟世界进行互动。

常见的虚拟现实技术包括头戴式显示器和手柄控制器等。

9. 人工智能 (Artificial Intelligence)人工智能是计算机科学的一个分支，研究如何使计算机能够模拟和执行智能行为。

它涉及到机器研究、自然语言处理和专家系统等领域。

10. 加密 (Encryption)加密是一种将信息转化为密文的过程，以保护数据的安全性和隐私。

常见的加密算法有AES、RSA和SHA等。

云计算是一种通过互联网提供计算资源和服务的方式。

它可以实现按需访问、灵活扩展和资源共享等功能。

2022年重庆工商大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、用有向无环图描述表达式(A+B)*((A+B)／/A)，至少需要顶点的数目为（）。

A.5B.6C.8D.92、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。

A.13B.33C.18D.403、算法的计算量的大小称为计算的（）。

A.效率B.复杂性C.现实性D.难度4、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（）。

A.h->next=sB.s->next=hC.s->next=h;h->next=sD.s->next=h-next;h->next=s5、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（）。

A.（rear+1）MOD n=frontB.rear=frontC.rear+1=frontD.（rear-1）MOD n=front6、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b， c，d，e，a，则根结点的孩子结点（）。

A．只有e B．有e、b C．有e、c D．无法确定7、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。

下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。

Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ8、一个具有1025个结点的二叉树的高h为（）。

A.11B.10C.11至1025之间D.10至1024之间9、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。

A.其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子C.其中只有一个叶结点D.其中度为2的结点最多为一个10、对序列{15，9，7，8，20，-1，4}用希尔排序方法排序，经一趟后序列变为{15，-1，4，8，20，9，7}则该次采用的增量是（）。

目录一、重庆邮电大学关于制订本科专业培养方案的指导性意见 (1)二、通信与信息工程学院培养方案通信与信息大类培养方案 (19)1.通信工程专业培养方案 (23)2.电子信息工程专业培养方案 (28)3.信息工程专业培养方案 (33)4.广播电视工程专业培养方案 (39)通信工程专业卓越工程师培养方案 (47)重庆邮电大学IT精英培养方案 (59)三、计算机科学与技术学院培养方案计算机与智能科学大类培养方案 (69)1.计算机科学与技术专业培养方案 (73)2.信息安全专业培养方案 (78)3.地理信息科学专业培养方案 (84)4.网络工程专业培养方案 (90)5.智能科学与技术专业培养方案 (96)计算机科学与技术专业卓越工程师培养方案 (102)四、自动化学院培养方案自动化与电气工程类专业培养方案 (109)1.自动化专业培养方案 (113)2.电气工程及其自动化专业培养方案 (119)3.物联网工程专业培养方案 (125)4.智能电网信息工程专业培养方案 (131)测控技术与仪器专业培养方案 (137)机械设计制造及其自动化专业培养方案 (147)自动化专业卓越工程师培养方案 (156)五、光电工程学院/重庆国际半导体学院培养方案电子工程大类专业培养方案 (167)1.光电信息科学与工程专业培养方案 (169)2.电子科学与技术专业培养方案 (174)3.电磁场与无线技术专业培养方案 (179)集成电路工程大类专业培养方案 (185)1.微电子科学与工程专业培养方案 (188)2.电子信息科学与技术专业培养方案 (193)电子工程大类实验班培养方案 (197)微电子科学与工程专业实验班培养方案 (202)六、生物信息学院培养方案生物医学工程专业培养方案 (208)生物技术与制药大类培养方案 (214)1.生物技术专业培养方案 (217)2.制药工程专业培养方案 (221)3.生物信息学专业培养方案 (225)生物技术与制药大类创新实验班培养方案 (230)七、数理学院培养方案数理科学与信息技术大类专业培养方案 (236)1.数学与应用数学专业培养方案 (241)2.信息与计算科学专业培养方案 (245)3.应用物理学专业培养方案 (249)数理科学与信息技术基础班培养方案（2012级） (253)信息与计算科学专业实验班培养方案 (257)八、经济管理学院培养方案信息管理与信息系统专业培养方案 (263)电子商务专业培养方案 (272)工商管理大类专业培养方案 (281)1.工商管理专业培养方案 (284)2.市场营销专业培养方案 (289)3.会计学专业培养方案 (294)工程管理专业培养方案 (299)经济学专业培养方案 (308)物流管理专业培养方案 (316)市场营销专业实验班培养方案 (325)九、法学院培养方案法学大类培养方案 (332)1.法学专业培养方案 (335)2.知识产权专业培养方案 (344)十、传媒艺术学院培养方案广播电视编导专业（含实验班）培养方案 (352)动画专业培养方案 (361)艺术设计大类专业培养方案 (370)1.环境设计专业培养方案 (372)2.视觉传达设计专业培养方案 (379)3.产品设计专业培养方案 (386)十一、外国语学院/国际学院培养方案英语大类培养方案 (393)1.英语专业培养方案 (397)2.翻译专业培养方案 (404)中加合作人才培养项目培养方案（2013） (411)十二、体育学院培养方案社会体育指导与管理专业培养方案 (417)十三、软件学院培养方案软件工程专业培养方案 (431)软件工程专业培养方案（“英语+软件”） (438)软件工程专业培养方案（“日语+软件”） (443)重庆邮电大学关于制订本科专业培养方案的指导性意见各学院、各相关单位：培养方案是学校实现人才培养目标、开展人才培养工作的总体设计和实施方案，是保证学校教育教学质量和人才培养规格与特色的重要指导性文件，是组织教学过程、安排教学任务、确定教学资源及有关工作的基本依据。

2022年重庆大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、下列说法不正确的是（）。

A.图的遍历是从给定的源点出发每个顶点仅被访问一次B.遍历的基本方法有两种：深度遍历和广度遍历C.图的深度遍历不适用于有向图D.图的深度遍历是一个递归过程2、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。

A.60B.66C.18000D.333、以下数据结构中，（）是非线性数据结构。

A.树B.字符串C.队D.栈4、在下列表述中，正确的是（）A.含有一个或多个空格字符的串称为空格串B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l5、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（）。

A.h->next=sB.s->next=hC.s->next=h;h->next=sD.s->next=h-next;h->next=s6、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。

下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。

Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ7、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。

假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。

初始时为空，下列判断队空和队满的条件中，正确的是（）。

A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod MB．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1）C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod MD．队空：end1＝＝（end2＋1）mod M；队满：end2＝＝（end1＋1） mod （M－1）8、在下述结论中，正确的有（）。

2022年重庆邮电大学数据科学与大数据技术专业《数据库系统原理》科目期末试卷A（有答案）一、填空题1、完整性约束条件作用的对象有属性、______和______三种。

2、有两种基本类型的锁，它们是______和______。

3、SQL Server中数据完整性包括______、______和______。

4、在SQL语言中，为了数据库的安全性，设置了对数据的存取进行控制的语句，对用户授权使用____________语句，收回所授的权限使用____________语句。

5、在数据库系统封锁协议中，一级协议：“事务在修改数据A前必须先对其加X锁，直到事务结束才释放X锁”，该协议可以防止______；二级协议是在一级协议的基础上加上“事务T在读数据R之前必须先对其加S锁，读完后即可释放S锁”，该协议可以防止______；三级协议是在一级协议的基础上加上“事务T在读数据R之前必须先对其加S锁，直到事务结束后才释放S 锁”，该协议可以防止______。

6、从外部视图到子模式的数据结构的转换是由______________实现；模式与子模式之间的映象是由______________实现；存储模式与数据物理组织之间的映象是由______________实现。

7、采用关系模型的逻辑结构设计的任务是将E-R图转换成一组______，并进行______处理。

8、数据库系统是利用存储在外存上其他地方的______来重建被破坏的数据库。

方法主要有两种：______和______。

9、关系代数运算中，基本的运算是______________、______________、______________、______________和______________。

10、在SQL Server 2000中，新建了一个SQL Server身份验证模式的登录账户LOG，现希望LOG在数据库服务器上具有全部的操作权限，下述语句是为LOG授权的语句，请补全该语句。

《数据结构》教学大纲课程编号：13140203英文名称：Data Structure学分：5学时：96(其中理论学时64，实践学时32)课程类别：专业平台课程授课对象：计算机科学与技术、信息管理与信息系统专业学生教学单位：工学院计算机科学技术学科修读学期：第2学期一、教学任务基本的算法理论，分析问题的方法，数据的逻辑结构，数据的存储结构以及基于这些结构上的算法，数据组织和处理技术，基于数据结构的分析和解决问题的方法、算法实现和程序设计技能的训练。

本课程是计算机类专业的核心课，是重要的专业理论与技术基础课，是面向对象程序设计、操作系统、数据库原理、软件工程等专业课程的先修课程；通过该课程的学习，使学生具备较扎实的软件技术知识和技能，初步具备从现实问题抽象到信息范畴再到计算机中数据组织和处理的转换，实现解决问题的较综合的能力；为学生的专业素质和分析及解决问题的能力奠定基础。

二、教学目标1．明确本课程对用计算机解决实际问题的作用；明确把现实问题通过计算机来解决的过程和方法；掌握对计算机加工的数据对象特性的分析方法，掌握线性结构、树结构、图结构等结构的特性；掌握基本的查找和排序方法。

2．能根据实际问题能选择合适的数据逻辑结构和存储结构，并在此基础上掌握对这些数据对象的操作技术。

具备相应结构的组织数据的方法，基本具备在这些结构上编写结构清晰，正确易读，效率较高算法的能力，初步具备编制较综合性程序和解决问题的能力；初步具备算法评价的能力。

3．初步具备通过对现实世界中问题的分析、能把处理对象的数据和关系抽象到信息世界里的结构模型、然后把结构模型组织到计算机里，从而在这基础上编制算法实现问题求解的较综合的能力。

三、教学内容（一）基本概念1．明确本课程研究的对象、内容和过程，明确本课程在专业人才培养中的地位、任务和作用。

2．明确数据、数据对象、数据的逻辑结构、存储结构的联系与区别、抽象数据类型、算法的概念。

3．明确算法与数据结构的关系、描述算法的方法，基本掌握基本的算法分析方法。

数据结构（Datastructure）：⽤链表实现多项式的表⽰和运算（C语⾔）0.简介（在以下环境下运⾏通过）：运⾏环境：Linux(ubuntu12.10); 编译器：gcc; 语⾔：C语⾔； 作者：Catcher24。

1.问题描述： 使⽤链表实现多项式的表⽰和运算（加法、减法、乘法）。

2.数据结构描述与设计：　2.1　使⽤链表的原因： 有两个多项式： P1 = 6x^4+4x^2-x; P2 = -7x^5+x^2; 如果要对两个多项式进⾏操作（多项式相加、除法等等......），可以采⽤数组的存储⽅式。

设多项式P(n) = a1x n+a2x n-1+...a n;如果采⽤数组A[n]来存储P(n)的系数，当P(n)中有的a i为0时，数组储存在空间上会带来很⼤的浪费。

⽽采⽤链表存储，每个节点存储系数和指数信息。

⽤链表来表⽰多项式，节点信息如下图：图：链表节点信息　2.2　多项式的链表实现： 下⾯给出polynomial.h⽂件，⾥⾯包含了节点的定义和函数定义；1 #include <stdlib.h>2 #include <stdio.h>34 #ifndef _List_H5 typedef int bool;6 typedef int exp_type;7 typedef float coe_type;8#define true 19#define false 010 typedef struct node {11 coe_type coefficient;12 exp_type exponent;13struct node* next;14 }node;15 typedef struct node* polynomial;1617 node* init(node* l);18 node* make_empty(node* l);19bool is_empty(node* l);20bool is_last(node* p,node* l);21 node* find(coe_type x,node* l);22 node* find_previous(coe_type x,node *l);23void delete_node(coe_type x, node* l);24void insert(coe_type x,exp_type y,node* l);25void delete_list(node* l);26 node* header(node* l);27 node* first(node* l);28void print_list(node* l);2930 polynomial create(polynomial poly,coe_type coe[],exp_type exp[],int n);32 polynomial sub_poly(const polynomial poly1,const polynomial poly2,polynomial polyprod);33 polynomial mult_poly(const polynomial poly1,const polynomial poly2,polynomial polyprod);34void print_poly(const polynomial poly);3536#endif 其中通过create()函数创建⼀个新的多项式，⽤⼀个float类型的数组来表⽰多项式的系数，⽤int型的数组来表⽰多项式的指数。

计算机大类专业培养方案计算机科学与技术（080605）、信息安全（071205W）一、培养目标计算机大类专业培养在思想道德、业务、文化、身心素质等方面全面发展，适应信息社会和知识经济时代需要，具有扎实基础、宽广知识、与时俱进、开拓创新的社会主义事业的建设者和接班人。

培养的学生能系统掌握计算机硬件与软件、计算机应用、计算机网络等的基本理论、基本知识和基本技能与方法；基本掌握通信网的组成和工作原理；较全面地了解计算机科学与技术的基本理论和基本方法；能在政府部门和企事业单位从事计算机科学与技术的教学、科研和应用开发，以及计算机网络工程设计、运营管理和维护。

二、培养规格及要求计算机大类专业学制四年，前两年为基础学习阶段，后两年为专业学习阶段。

基础学习阶段按大类培养，采用同一培养方案，使学生具有较宽的专业基础知识。

在专业学习阶段，根据学生所选专业，分别按计算机科学与技术、信息安全专业进行培养，使学生具有一定的特长。

本大类专业学生主要学习计算机科学与技术、计算机通信方面的基础理论和基本知识，接受从事科学研究及计算机应用系统开发的基本训练。

在此基础上，通过选修计算机科学与技术或信息安全等专业的选修课，使学生达到所选专业方向的知识结构要求。

再通过必修的人文类、经济管理类等课程的学习，使学生素质达到专业培养目标的要求。

为使学生达到所选专业的培养目标，教学计划中在注重基础课程教学的同时，还安排了系列综合实践技能训练和课外科技活动等环节，以培养和提高学生的求实、创新精神。

三、毕业生应获得以下几方面的知识和能力：1、掌握计算机科学与技术的基本理论和基本知识；2、掌握计算机软件和硬件基本的分析、设计和开发方法；3、掌握计算机系统的基本的分析和设计方法，具有研究和开发计算机软、硬件的基本能力；4、掌握计算机通信网与电信管理网的分析、设计、系统集成和软件开发、运营管理与维护的方法；具有分析、设计、维护和管理计算机网和电信网的基本能力；5、了解计算机学科的发展动态，具有不断更新知识的能力；6、具有资料查询、文献检索、获取信息、归纳分析资料的能力；7、基本掌握一门外语，初步具有应用外语获取知识和进行交流的能力。