830.数据结构
- 格式:doc
- 大小:57.50 KB
- 文档页数:4
830数据结构考研参考书目
830数据结构考研的参考书目有:
1. 《数据结构(C语言版)》——严蔚敏、吴伟民编著,清华大学出版社。
这本书是国内最经典的数据结构教材之一,被广大考生认为是必备的参考书之一。
它涵盖了所有考研数据结构的知识点,并且讲解深入浅出,易于理解。
2. 《数据结构题集(C语言版)》——严蔚敏、吴伟民编著,清华大学出版社。
这本书是上述教材的配套题集,包含了大量的练习题和真题,对于考研生来说非常有价值。
通过练习这些题目,可以加深对数据结构的理解和掌握。
以上内容仅供参考,请以目标院校官方网站上公布的信息为准选择最合适的参考书目。
目 录第一部分 历年考研真题汇编2006年南京工业大学计算机科学与技术学院828数据结构与操作系统考研真题第二部分 兄弟院校真题汇编2014年山东科技大学信息科学与工程学院830数据结构与操作系统考研真题2012年山东科技大学信息科学与工程学院838数据结构与操作系统考研真题2011年山东科技大学信息科学与工程学院827数据结构与操作系统考研真题2010年山东科技大学信息科学与工程学院827数据结构与操作系统考研真题第一部分 历年考研真题汇编2006年南京工业大学计算机科学与技术学院828数据结构与操作系统考研真题南京工业大学耍堕年硕士研究生入学考试试卷(A)〈本试题150分、3小时)考试科目:数据埃构与操作系统诸应学科、专业:计算机应用技术(注意:所有答题内容均余写在答鬼地上,在试卷上答题-独无效!)第-部分,数据结构(共90分)一、选择题(每小题2分,共20分)1>数据的存储结构有廉序、健式、族引和四种疆条形式.丸线性 B.树形C,散列D一图监2、计算机体法必^具备输入、输出和尊5个特性。
A,易读性、稳定性和安全性B可行性、可移植性和可扩充性C,牖定性、有穷性和秘定性可行性、确定性和有穷性3、指出下列时间要杂度最耶的级别是________.A.对数阶Ofhfcn)B.线性阶&n)C,指数阶。
(2")D,平方阶0(『)4、己知模式串P='ABAABC',其next函数值是*A.011213B.012223C0LH22D,0112215、数组A中,行下标i义卜列下总j从1-10.每个元素的长度为3个字节,从首地址SA开始连续存糖.慢数组核列存放时,元素A”的起始地址为=A.SA+141B.SA+1S0C SA+222 D.SA+226、设无向图的顼点个数为n,聊谖无向图最多有________条辿.A.n;B.tt(n+l)/2C n(n-L)/2D n-17、将序列(50.72.43.85,73.20,35,45.65.30)构造为二叉排序树,杏找元素35重进行________次元素间的比较.A.10B.7C.5D.4一』、除度《设根的层次为L)的完全二又树至少有一^结点.七X尹C i*-T一 D.2W—-—----------------———9、下述几种排序方法中,能完成对突数数绍进行榆定捧序的是_______•,A、归弁样序 B.堆排序 C.快速排虏 D.痿数择序I。
河海838考研大纲
河海大学计算机自命题考试大纲(科目代码:838,科目名称:数据结构及程序设计)的考试内容主要包括以下部分:
1. 线性表:线性表的定义、逻辑结构、存储结构;线性表的顺序表示、链式表示;顺序表和链表的插入和删除等操作。
2. 栈和队列:栈的定义、栈的顺序表示和链式表示、顺序栈、链栈的入栈和出栈操作;队列的定义、队列的顺序表示和链式表示、顺序队列、链队列的入队和出队操作;循环队列的队空和队满的判断。
3. 串:串类型的定义、串的表示和实现、串的模式匹配算法、模式匹配的一种改进算法(KMP 方法)。
4. 数组和广义表:数组的定义、数组的顺序表示和实现;广义表的定义、存储结构。
5. 树和二叉树:树的定义和基本术语;二叉树的定义、性质、存储结构;遍历二叉树、线索二叉树;树的存储结构、森林与二叉树的转换、树和森林的遍历;最优二叉树(赫夫曼树)、赫夫曼编码。
以上信息仅供参考,具体考试内容请以河海大学发布的官方信息为准。
2023 年招收攻读硕士学位研究生入学考试试题A 卷******************************************************************************************** 招生专业与代码:网络空间安全考试科目名称及代码:数据结构 830考生注意:所有答案必须写在答题纸(卷)上,写在本试题上一律不给分。
一、单项选择题(每题 2 分,共 20 分)1.以下数据结构中, ( )是非线性数据结构A.字符串B.树C.队列D.栈2.请选择下面程序段的时间复杂度( )i = 1;while (i <= n)i = i * 3;A.O(n)B. O(log3 n)C. O(n2)D. O(i * n)3.顺序表中第一个元素的存储地址为120,每个元素的长度为5,则第4 个元素的地址为 ( )A. 135B. 140C. 130D. 1454.在单链表中,要将L所指节点插入到M所指节点之后,其语句应为( )A.L->next = M+1; M->next = L;B.(*M).next = L; (*L).next = (*M).next;C.L->next = M->next; M->next = L->next;D.L->next = M->next; M->next = L;5.若让元素1,2,3,4,7 依次进栈,则出栈顺序不可能为( )A. 7, 4, 3, 2, 1B. 4, 3, 1, 2, 7C. 2, 1, 7, 4, 3D. 2, 3, 7, 4, 16.假设栈 S 与队列 Q 的初始状态为空,元素 e1、e2、e3、e4、e5 和 e6 依次进入栈 S,一个元素出栈后即进入 Q,若 6 个元素出队的序列是 e2、e4、e3、e6、e5 和e1,则栈S 的容量至少为( )A.2 B. 4 C. 3. D.67.假设以行序列为主序存储二维数组 A = array[1..100,1..100],设每个数据元素占 2 个存储单元,基地址为 10,则 LOC[5, 5] = ( )A.808 B.1010 C.818 D.10208.由3个不同结点可计算出多少种不同的二叉树?( )A. 3B. 4C. 5D. 69.广度优先遍历类似于二叉树的( )A.先序遍历B. 中序遍历C. 层次遍历D.后序遍历10.设哈希表长为14,哈希函数是H(key)=key%11,表中已有数据的关键字为15,38,61,84 共四个,现要将关键字为49 的元素加到表中,用二次探测法解决冲突,则放入的位置是( )A.8 B.3 C.5 D.9考试科目:数据结构共 3 页,第 1 页。
计算机考研专硕院校信息汇总1.中山大学(985)广东省广州软件工程:867专业基础(数据结构)620)软件学院院系:100 本专:100 推免:60 专业:40621)(1)101思想政治理论(2)204英语二(3)302数学二(4)867专业基础(数据结构)复试专业课:F62 01计算机综合考试①《离散数学》,耿素云、屈婉玲,高等教育出版社,1998。
②《C程序设计》第二版,谭浩强编,清华大学出版社,1999。
计算机技术:(408)综合350)信息科学与技术学院院系:287 专硕:143 推免:100 一般:43 (470)中山大学-卡内基梅隆大学联合工程学院(922)数据结构与计算机原理本专:40分数线:300;270;2702.华南理工大学(985)广东省广州计算机技术:(831)计算机专业综合(数据结构、操作系统)008)计算机科学与工程学院院系:133 专业招生人数:55① 101思想政治理论② 204英语1③302数学1④831计算机专业综合(数据结构、操作系统) 复试笔试科目:902上机能力测试:数据库复试科目参考书:《数据库系统概论》(第三版)王能斌著,,电子工业出版社;《数据库系统概念》(第四版)中文版,杨冬青、唐世渭等编译,机械工业出版社;《数据库系统教程》王能斌著,电子工业出版社软件工程:(408)综合(023)软件学院院系:74推免:373.暨南大学(211)广东省软件工程和计算机技术:(830)数据结构(010)信息科学技术学院院系:110 推免:20 软件工程专业:10①101思想政治理论②204英语二③302数学二④830数据结构830数据结构1.严蔚敏、吴伟民, 数据结构(C语言版),清华大学出版社出版2.严蔚敏, 吴伟民,《数据结构习题解析》,清华大学出版社出版复试科目:C语言程序设计加试科目:①离散数学②计算机基础!!华南师范大学广东省软件工程:(918)计算机综合考试(操作系统、程序设计)(019)计算机学院院系:62 推免:164.华东师范大学(985)上海市085211 数据结构(含c语言)计算机技术1.上机考试:主要考查学生运用计算机编程解决问题的能力,上机语言为C或C++。
暨南大学硕士研究生入学考试自命题科目830《数据结构》考试大纲Ⅰ考试形式一、试卷满分及考试时间本试卷满分为150分,考试时间为180分钟二、答题方式答题方式为闭卷、笔试Ⅱ考查目标1.理解数据结构的基本概念;掌握数据结构的逻辑结构、存储结构及其差异,以及各种基本操作的实现。
2.掌握基本的数据处理原理和方法的基础上,能够对算法进行设计与分析。
3.能够选择合适的数据结构和方法进行问题求解。
一、基本概念和术语(一)数据元素、数据结构、抽象数据类型等概念(二)算法设计的基本要求(三)语句的频度和估算时间复杂度二、线性表(一)线性表的定义和基本操作(二)线性表的实现1.顺序存储结构2.链式存储结构3.线性表的应用三、栈、队列和数组(一)栈和队列的基本概念(二)栈和队列的顺序存储结构(三)栈和队列的链式存储结构(四)栈和队列的应用(五)特殊矩阵的压缩存储四、树与二叉树栈(一)树的概念(二)二叉树1.二叉树的定义及其主要特征2.二叉树的顺序存储结构和链式存储结构3.二叉树的遍历4.线索二叉树的基本概念和构造5.二叉排序树6.平衡二叉树(三)树、森林1.树的存储结构2.森林与二叉树的转换3.树和森林的遍历(四)树的应用1.特价类问题2.哈夫曼(Huffman)树和哈夫曼编码五、图(一)图的概念(二)图的存储结构及基本操作1. 邻接矩阵2.邻接表(三)图的遍历1.深度优先搜索2.广度优先搜索(四)图的基本应用1.最小(代价)生成树2.拓扑排序3.关键路径4.最短路径六、查找(一)查找的基本概念(二)顺序查找法(三)折半查找法(四)B-树(五)散列(Hash)表及其查找(六)查找算法的分析及应用七、内部排序(一)排序的基本概念(二)插入排序1.直接插入排序2.折半插入排序(三)气泡排序(bubble sort)(四)简单选择排序(五)希尔排序(shell sort)(六)快速排序(七)堆排序(八)二路归并排序(merge sort)(九)基数排序(十)各种内部排序算法的比较(十一)内部排序算法的应用Ⅲ特别推荐1.严蔚敏、吴伟民, 数据结构(C语言版),清华大学出版社出版2.严蔚敏, 吴伟民,《数据结构习题解析》,清华大学出版社出版。
在东北师范大学计算机科学与技术学院,计算机科学专业的学生需要学习一门名为“830算法与程序设计”的课程。
这门课程是计算机科学与技术专业的基础课程,主要包括算法分析与设计、数据结构、程序设计等内容。
以下是该课程的大纲。
一、课程简介1.1 课程名称:830算法与程序设计1.2 课程性质:必修课1.3 学时安排:理论课3学时/周,实验课2学时/周1.4 学分:3学分二、课程内容2.1 算法分析与设计2.1.1 时间复杂度分析2.1.2 空间复杂度分析2.1.3 基本算法:排序、查找、递归等2.1.4 动态规划2.1.5 贪心算法2.2 数据结构2.2.1 线性表2.2.2 树结构2.2.3 图结构2.2.4 堆栈与队列2.2.5 散列2.3 程序设计2.3.1 C语言基础2.3.2 算法实现2.3.3 数据结构实现2.3.4 实际项目开发三、教学目标3.1 掌握算法分析与设计的基本方法和技巧3.2 理解各种数据结构的原理和应用场景3.3 能够熟练运用C语言进行程序设计3.4 具备解决实际问题的能力四、教学方式4.1 以理论课为主,注重基础知识的传授4.2 实验课注重动手实践,培养学生的编程能力和解决问题的能力4.3 结合实际案例,引导学生运用所学知识解决实际问题五、考核方式5.1 平时成绩:包括课堂表现、作业完成情况、实验报告等5.2 期中考试:主要考察对算法分析与设计的理解和掌握情况5.3 期末考试:主要考察对数据结构和程序设计的掌握情况六、教材及参考书目6.1 主教材:《算法导论》6.2 辅助教材:《数据结构与算法分析》、《C语言程序设计》通过以上大纲,可以看出东北师范大学计算机科学与技术学院的“830算法与程序设计”课程注重理论与实践相结合,旨在培养学生的编程能力和解决实际问题的能力。
这门课程不仅是计算机科学专业的基础课程,也为学生们将来的学习和工作奠定了扎实的基础。
Course outline for 830 algorithm and program design at Northeast Normal UniversityIn the School of Computer Science and Technology of Northeast Normal University, students majoring inputer science need to study a course called "830 Algorithm and Program Design". This course is a foundational course for theputer science and technology major, m本人nly including algorithm analysis and design, data structure, program design and so on. Here is the outline of the course.I. Course introduction1.1 Course name: 830 Algorithm and Program Design1.2 Course nature:pulsory course1.3 Class arrangement: 3 hours/week for theoretical classes, 2hours/week for practical classes1.4 Credits: 3 creditsII. Course content2.1 Algorithm analysis and design2.1.1 Timeplexity analysis2.1.2 Spaceplexity analysis2.1.3 Basic algorithms: sorting, searching, recursion, etc.2.1.4 Dynamic programming2.1.5 Greedy algorithm2.2 Data structure2.2.1 Linear table2.2.2 Tree structure2.2.3 Graph structure2.2.4 Stack and queue2.2.5 Hashing2.3 Program design2.3.1 Basics of C language2.3.2 Algorithm implementation2.3.3 Data structure implementation2.3.4 Actual project developmentIII. Teaching objectives3.1 Master the basic methods and techniques of algorithm analysis and design3.2 Understand the principles and application scenarios of various data structures3.3 Able to proficiently use C language for program design3.4 Possess the ability to solve practical problemsIV. Teaching methods4.1 M本人nly theoretical classes, focusing on the impartation of basic knowledge4.2 Practical classes focus on hands-on practice to cultivate students' programming and problem-solving abilities4.3 Combine practical cases to guide students in applying the knowledge they have learned to solve practical problemsV. Assessment methods5.1 Regular performance: including classroom performance,pletion of assignments, experimental reports, etc.5.2 Mid-term exam: m本人nly assess the understanding and mastery of algorithm analysis and design5.3 Final exam: m本人nly assess the mastery of data structures and program designVI. Textbooks and references6.1 M本人n textbook: "Introduction to Algorithms"6.2 Auxiliary textbooks: "Data Structures and Algorithm Analysis", "C Language Program Design"Through the above outline, it can be seen that the course "830 Algorithm and Program Design" in the School of Computer Science and Technology of Northeast Normal University focuses on thebination of theory and practice, 本人ming to cultivate students' programming and problem-solving abilities. This course is not only a foundational course for theputer science major but also lays a solid foundation for students' future study and work.。
考试科目: 数据结构 共5页,第1 页2018年全国硕士研究生统一入学考试自命题试题( A 卷)********************************************************************************************学科、专业名称:计算机科学与技术、软件工程研究方向:计算机系统结构 081201,计算机软件与理论 081202,计算机应用技术 081203, 软件工程083500,计算机技术(专业学位)085211 考试科目名称及代码:数据结构830考生注意:所有答案必须写在答题纸(卷)上,写在本试题上一律不给分。
单项选择题(每题2分,共30分)7. 在一棵非空m 阶的B-树上,除根之外的所有非终端结点A.至少有I m/2驛子树 B.至多有 尿/2」棵子树C.至少有m/21棵子树D.至多有(m/2[棵子树8. 若用单链表来表示队列,最适合队列操作的是(A.带尾指针的非循环队列B.带尾指针的循环链表C.带头指针的非循环链表D.带头指针的循环链表9. 下面的序列中,()是堆。
A. 12, 36, 27, 65, 40, 34, 98, 81,73, 55, 49B. 12, 36, 27, 65, 40, 14, 98, 81,73, 55, 49C. 12, 36, 27, 20, 40, 34, 98, 81,73, 55, 49D. 12, 36, 35, 65, 40, 34, 98, 81,73, 55, 49 10. 设有一个10阶的对称矩阵A,采用压缩存储方式,元素,其首存储地址为1,每个元素占1个地址空间,则a 85的地址为(J1NAN UNIVERSITY1.任何一棵二叉树 T,如果度为1的结点数为2,度为0结点数为11,其分支数为(A. 23B. 22 2. 深度为k 的二叉树至多有( A. 2kB. 2k "13. 已知一棵二叉树结点的中序序列为列为(C. 24个结点(k>=1);kC. 2 +1D. 21D.2k -1后序序列为DECBHGFA,则结点的先序序A. ABCDEFGHB. DGBFHCA4. 在有向图的逆邻接表存储结构中,顶点A.顶点V 的度 C.顶点V 的入度5. 顺序栈s 的GetTop (s, e )操作是用e 返回 A. e=*(s.to p ) B. e=*(s.to p-1)6. 若线性表最常用的操作是存取第A.单链表B.双链表C. v 在表结点中出现的次数是( B. 顶点V 的出度D.依附于顶点V 的边数 s 的栈顶元素,则下列(C. e=*(--s.t op )DECBGFAHD. CAFHGDB)。
2一、 选择题1 1 1 .B 2.A 3.C 4.A 5.D 6.A 7.B 8.A 9.C 10.C1.B 12.C 13.A 14.C 15.B 16.D 17.D 18.D 19.A 20.A5 解释:线索二叉树中某结点是否有左孩子,不能通过左指针域是否为空来判 断,而要判断左标志是否为 1。
二、 填空题1 2 3 .归并排序。
. 能否将关键字均匀影射到哈希空间上.一端 先进后出有无好的解决冲突的方法4 5 6 7 8 9 . 顺序存储或链式存储 (1+n )/2.从任意节点出发都能访问到整个链表.时间 空间.n-1 n(n-1)/2.2n-1.n n三、 判断题 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 .F.F 非空才成立.F 有向的非强连通图,不成立.T.F 表头没有前驱,表尾没有后序.T.F 先序跟后序不行,中序才行.T.F 不可能0.T1.F2.T3.F4.F5.F四、 应用题1 .逻辑结构是从操作对象抽象出来的数学模型,结构定义中的“关系”描述的 是数据元素之间的逻辑关系;物理结构是数据结构在计算机中的表示(又称 映像),又称存储结构。
物理结构是指数据具体存放在哪个位置,逻辑结构是2 3.由 AOV 网构造拓扑序列的拓扑排序算法主要是循环执行以下两步,直到不存 在入度为 0的顶点为止。
(1) 选择一个入度为 0的顶点并输出之;(2) 从网 中删除此顶点及所有出边。
拓扑序列 1:abcdef 拓扑序列 2:adbcef.二叉树图如下:4 5 .略。
已经不纳入考纲.哈夫曼编码问题编码: 3: 000020: 10 10: 0001 22: 11 18: 001 37: 016.二叉排序树问题比根节点小的往左子树插,大的往右子树插。
图如下:删除50有两种做法:《数据结构》中的解析这里我用第二种做法:五.算法设计题1 & .算法填空(L.elem[i-1]) L.length-1 ++p *p L.length-1;2. 设计算法: 输入 n 个元素的值 创建带头结点的单链线性表 L 。
834计算机专业基础(数据结构、操作系统) 1 数据结构1.1 什么是数据结构数据结构是计算机科学的基础知识之一,是指组织和存储数据的方式。
数据结构的目的是为了使程序能够高效地处理和检索数据。
数据结构包括数组、链表、栈、队列、树、图等多种类型,不同的数据结构适合不同的场景和应用。
例如,数组适合存储线性数据,链表适合用于频繁的插入和删除操作,栈和队列适合用于处理数据结构中的先进先出和后进先出的规则,树和图适合表示复杂的关系型数据。
1.2 常用数据结构1.2.1 数组数组是一种线性数据结构,它可以存储同类型的数据。
数组中每个元素都有一个唯一的下标,通过下标可以访问数组中的元素。
数组的优点是可以快速的访问任意位置上的元素,但是插入和删除操作比较麻烦。
1.2.2 链表链表也是一种线性数据结构,不同于数组,链表中的元素不一定是连续的。
每个节点都包含一块内存和一个指向下一个节点的指针。
链表的优点是可以快速的插入和删除节点,但访问数据需要遍历整个链表。
1.2.3 栈栈也是一种线性数据结构,它采用后进先出的原则。
栈顶是最后一个入栈的元素,栈底是最先入栈的元素。
栈的优点是操作简单,但是只能访问栈顶元素。
1.2.4 队列队列也是一种线性数据结构,它采用先进先出的原则。
队列的队首是最先入队的元素,队尾是最后一个入队的元素。
队列的优点是可以快速地处理队首和队尾元素,但是不能在任意位置插入和删除元素。
1.2.5 树树结构是一种非线性数据结构。
它由若干个节点组成,并且每个节点最多有一个父节点和若干个子节点。
树的优点是可以快速地查找对应节点和插入删除节点。
1.2.6 图图是一种非线性的数据结构,它由若干个节点和若干条连接节点的边构成。
图的优点是可以快速地处理节点之间复杂的关系。
2 操作系统2.1 什么是操作系统操作系统是计算机必不可少的软件之一,它负责管理计算机的软硬件资源,并提供一个用户和应用程序可以使用的环境。
操作系统的核心部分包括内核和文件系统。
自考数据结构重点(每章节整理)第一章概论1.数据是信息的载体。
2.数据元素是数据的基本单位。
3.一个数据元素可以由若干个数据项组成。
4.数据结构指的是数据之间的相互关系,即数据的组织形式。
5.数据结构一般包括以下三方面内容:数据的逻辑结构、数据的存储结构、数据的运算①数据元素之间的逻辑关系,也称数据的逻辑结构,数据的逻辑结构是从逻辑关系上描述数据,与数据的存储无关,是独立于计算机的。
②数据元素及其关系在计算机存储器内的表示,称为数据的存储结构。
数据的存储结构是逻辑结构用计算机语言的实现,它依赖于计算机语言。
③数据的运算,即对数据施加的操作。
最常用的检索、插入、删除、更新、排序等。
6.数据的逻辑结构分类:线性结构和非线性结构①线性结构:若结构是非空集,则有且仅有一个开始结点和一个终端结点,并且所有结点都最多只有一个直接前趋和一个直接后继。
线性表是一个典型的线性结构。
栈、队列、串等都是线性结构。
②非线性结构:一个结点可能有多个直接前趋和直接后继。
数组、广义表、树和图等数据结构都是非线性结构。
7.数据的四种基本存储方法:顺序存储方法、链接存储方法、索引存储方法、散列存储方法(1)顺序存储方法:该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里,结点间的逻辑关系由存储单元的邻接关系来体现。
通常借助程序语言的数组描述。
(2)链接存储方法:该方法不要求逻辑上相邻的结点在物理位置上亦相邻,结点间的逻辑关系由附加的指针字段表示。
通常借助于程序语言的指针类型描述。
(3)索引存储方法:该方法通常在储存结点信息的同时,还建立附加的索引表。
索引表由若干索引项组成。
若每个结点在索引表中都有一个索引项,则该索引表称之为稠密索引,稠密索引中索引项的地址指示结点所在的存储位置。
若一组结点在索引表中只对应一个索引项,则该索引表称为稀疏索引稀疏索引中索引项的地址指示一组结点的起始存储位置。
索引项的一般形式是:(关键字、地址) 关键字是能唯一标识一个结点的那些数据项。
数据结构与算法一、任务背景在计算机科学中,数据结构是指一组数据的组织方式和管理方式。
数据结构是计算机程序中用于存储和组织数据的方法,同时也是算法设计和分析的基础。
数据结构与算法是计算机科学的核心内容之一,对于计算机科学专业的学生来说,掌握数据结构与算法是非常重要的。
二、数据结构的定义数据结构是指一组数据元素的集合,以及定义在此集合上的一些操作。
数据结构可以分为线性结构和非线性结构。
•线性结构:线性结构是指数据元素之间存在一对一的关系,其中包括线性表、栈、队列和串等。
•非线性结构:非线性结构是指数据元素之间存在一对多或多对多的关系,其中包括树、图和集合等。
三、数据结构的分类根据数据的存储方式,数据结构可以分为两类:顺序存储结构和链式存储结构。
•顺序存储结构:顺序存储结构是指将数据元素存放在连续的存储单元中,数据元素之间的关系由存储位置来表示。
顺序存储结构适合于元素个数固定且不经常变动的情况。
•链式存储结构:链式存储结构是指将数据元素存放在任意的存储单元中,数据元素之间的关系由指针来表示。
链式存储结构适合于元素个数不固定或经常变动的情况。
四、常见的数据结构1. 数组数组是一种线性结构,它由连续的存储单元组成,用于存储相同类型的数据。
数组的特点是可以通过下标访问元素,时间复杂度为O(1)。
2. 链表链表是一种线性结构,它由一系列节点组成,每个节点包含数据和指向下一个节点的指针。
链表的特点是插入和删除操作的时间复杂度为O(1),但是访问元素的时间复杂度为O(n)。
3. 栈栈是一种特殊的线性结构,它的特点是先进后出。
栈的操作包括入栈和出栈,入栈操作将元素压入栈顶,出栈操作将栈顶元素弹出。
4. 队列队列是一种特殊的线性结构,它的特点是先进先出。
队列的操作包括入队和出队,入队操作将元素插入队尾,出队操作将队头元素删除。
5. 树树是一种非线性结构,它由一系列节点组成,每个节点可以有零个或多个子节点。
树的特点是可以用来表示层次关系。
837数据结构大纲摘要:一、数据结构概述1.数据结构定义2.数据结构的重要性3.数据结构的应用领域二、数据结构的分类1.逻辑结构a.集合结构b.线性结构c.树形结构d.图形结构2.物理结构a.顺序存储结构b.链式存储结构三、线性表1.线性表的定义2.线性表的运算3.线性表的应用四、栈和队列1.栈的定义和运算2.队列的定义和运算3.栈和队列的应用五、树1.树的定义和分类2.二叉树的性质和运算3.二叉树的应用六、图1.图的定义和分类2.图的运算3.图的应用七、排序算法1.排序算法的分类2.常见排序算法及其实现3.排序算法的应用和性能分析八、查找算法1.查找算法的分类2.常见查找算法及其实现3.查找算法的应用和性能分析正文:数据结构是计算机科学与技术领域中的重要基础课程,它主要研究数据的逻辑组织、存储、管理和运算。
数据结构在计算机程序设计、系统分析和计算机应用等方面具有广泛的应用。
本大纲将介绍数据结构的概述、分类、线性表、栈和队列、树、图、排序算法和查找算法等内容。
首先,数据结构从逻辑结构和物理结构两个方面进行分类。
逻辑结构主要包括集合结构、线性结构、树形结构和图形结构,而物理结构主要包括顺序存储结构和链式存储结构。
线性表是一种最基本的线性数据结构,具有唯一的头结点和若干个尾结点。
线性表的运算主要包括插入、删除、查找等操作。
线性表在实际应用中有着广泛的应用,例如在数据库、文件系统和编译器等领域都有线性表的身影。
栈和队列是线性表的特殊形式,分别支持后进先出(LIFO)和先进先出(FIFO)的运算。
栈和队列在算法设计、操作系统和网络编程等领域具有重要的应用价值。
树是一种层次化的数据结构,具有一个根节点和多个子节点。
树分为二叉树、二叉搜索树、AVL树等不同类型。
二叉树在计算机科学中具有广泛的应用,例如在编译器、数据库和网络路由等领域都有涉及。
图是一种更复杂的数据结构,由顶点和边组成。
图分为有向图、无向图和混合图等不同类型。
河南工业大学
xxxx年硕士研究生入学考试试题
考试科目:数据结构共 4 页(第1 页)
注意:1、本试题纸上不答题,所有答案均写在答题纸上
2、本试题纸必须连同答题纸一起上交。
一、选择题(本题30分,每小题2分)
1. 导致栈上溢的操作是()。
A) 栈满时执行出栈B) 栈满时执行入栈
C) 栈空时执行入栈D) 栈空时执行出栈
2. 设有数组A[i,j],数组的每个元素长度为3字节,i的值为1 到8,j的值为1 到10,数组从内存首地址10000开始顺序存放,当用以列为主存放时,元素A[5, 8]的存储首地址为( )。
A. 10000+141
B. 10000+180
C. 10000+183
D. 10000+225
3. 广义表运算式Tail(((a,b),(c,d)))的操作结果是()。
A. (c,d)
B. c,d
C. ((c,d))
D. ((a,b),(c,d))
4. 由3 个结点可以构造出多少种不同的二叉树?()
A. 2
B. 3
C. 4
D. 5
5. 栈和队列的共同点是()
A. 都是先进先出
B. 都是先进后出
C. 只允许在端点处插入和删除元素
D. 没有共同点
6.一棵具有n个结点的完全二叉树的树高度(深度)是()
A.⎣log2n⎦+1 B.log2n+1 C.⎣log2n⎦D.log2n-1
7. n个结点的线索二叉树上含有的线索数为()
A. 2n
B. n-l
C. n+l
D. n
8. 在下面的程序段中,对x的赋值语句的频度为()
for(i=1;i<n;i++)
for(j=1;j<n;j++)
x=x+1;
A.O(2*n) B.O(n) C.O(n2) D.O(log2n)
9. 执行完下列语句段后,i值为:()
int f(int x)
{ return ((x>0) ? x* f(x-1):2);}
int i ;
i =f(f(1));
A.2 B. 4 C. 8 D. 无限递归
10.下面关于串的的叙述中,哪一个是不正确的?()
A.串是字符的有限序列 B.空串是由空格构成的串
C.模式匹配是串的一种重要运算 D.串既可以采用顺序存储,也可以采用链式存储11.对稀疏矩阵进行压缩存储目的是()。
A.便于进行矩阵运算 B.便于输入和输出 C.节省存储空间 D.降低运算的时间复杂度
12.设S为一个长度为n的字符串,其中的字符各不相同,则S中的互异的非平凡子串(非
共 4 页(第 2 页)
空且不同于S本身)的个数为()。
A.2*n-1 B.n2 C.(n2/2)+(n/2) D.(n2/2)+(n/2)-1 E. (n2/2)-(n/2)-1
13.有关二叉树下列说法正确的是()
A.二叉树的度为2 B.一棵二叉树的度可以小于2 C.二叉树中至少有一个结点的度为2 D.二叉树中任何一个结点的度都为2
14.设无向图的顶点个数为n,则该图最多有()条边。
A.n-1 B.n(n-1)/2 C. n(n+1)/2 D.0 E.n2
15.下列排序算法中,其中()是稳定的。
A. 堆排序,冒泡排序
B. 快速排序,堆排序
C. 直接选择排序,归并排序
D. 归并排序,冒泡排序
二、是非题(本题20分,每小题2分)
1.数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
数据元素相互之间的关系称为结构。
根据数据元素之间关系的不同特性,通常有下列四种基本结构:集合、线性结构、树形结构、图状结构(网状结构)。
2.对任何数据结构链式存储结构一定优于顺序存储结构。
3. 两个栈共用静态存储空间,对头使用也存在空间溢出问题。
4.设模式串的长度为m,目标串的长度为n,当n≈m且处理只匹配一次的模式时,朴素的匹配(即子串定位函数)算法所花的时间代价可能会更为节省。
5.稀疏矩阵压缩存储后,必会失去随机存取功能。
6. 完全二叉树一定存在度为1的结点。
7. 在n个结点的无向图中,若边数大于n-1,则该图必是连通图。
8. 排序算法中的比较次数与初始元素序列的排列无关。
9. 排序的稳定性是指排序算法中的比较次数保持不变,且算法能够终止。
10.散列函数越复杂越好,因为这样随机性好,冲突概率小.
三、填空题(本题20分,每小题2分)
1.当线性表的元素总数基本稳定,且很少进行插入和删除操作,但要求以最快的速度存取线性表中的元素时,应采用存储结构。
2. 循环队列的引入,目的是为了克服。
3.空格串是指,其长度等于。
4. 二叉树由,,三个基本单元组成。
5.分别采用堆排序,快速排序,冒泡排序和归并排序,对初态为有序的表,则最省时间的是
算法,最费时间的是算法。
6.顺序查找n个元素的顺序表,若查找成功,则比较关键字的次数最多为次;当使用监视哨时,若查找失败,则比较关键字的次数为。
7. 在数据表有序时,快速排序算法的时间复杂度是。
8.深度为k的完全二叉树至少有个结点,至多有个结点。
9.数据结构中评价算法的两个重要指标是、。
10.直接插入排序用监视哨的作用是。
四、简答题(本题 40 分)
1. (5分)若一棵二叉树的中序遍历结果为DBEAFGC,前序遍历结果 ABDECFG,请画出该二叉树。
共 4 页(第 3 页)
2. (5分)用克鲁斯卡尔(KRUSKAL)方法求下面网的最小生成树,要求画出中间步骤。
(5分)
3. (10分)假设用于通信的电文由字符集{a, b, c, d, e, f, g}中的字母构成。
它们在电文中出现的频度分别为{0.31, 0.16, 0.10, 0.08, 0.11, 0.20, 0.04},为这7个字母设计哈夫曼编码。
(要求画出哈夫曼树和写出编码结果,其中左子树权值小于右子树权值。
编码时左边0,右边1)
4. (10分)设哈希函数H(k)=k %7, 哈希表的地址空间是0~6,对关键字序列(19, 01, 23, 14, 55, 68, 11, 36),画出按链地址法解决冲突产生的哈希表。
5. (5分)求下图的关键路径。
(要求只画出关键路径部分,并计算关键路径长度)。
6. (5分)设待排序关键字序列{16,14,24,11,8,12,15},请画出其堆排序的初始建堆(小顶堆)的过程。
共 4 页(第 4 页)五、算法分析(本题40分,每题20分)
1. (20分)双向链表的存储结构描述如下:
Typedef struct DuLNode{
ElemType data;
Struct DuLNode *prior;
Struct DuLNode *next;
}
请写出在带头节点的双向链表L中的第i位置之前插入元素e的算法。
其中已经定义
Struct DuLNode *GetElemp_DuL(DuLinkList &L,int i,); 表示在L中确定第i个元素的位置指针。
Status ListInsert_DuL(DuLinkList &L,int i, ElemType e)
{ Struct DuLNode *p,*s;
2.(20分)请写出先序遍历二叉树(链式存储结构)算法。
其中类型定义和Visit 函数已经如下定义。
Typedef struct BiTnode{
TElemType data;
Struct BiTnode *lchidl,*rchild; //左右孩子指针
}BiTnode,*BoTree;
Status Visit(TElemType e);//输出元素e的值
Status PreOrderTraverse(BiTree T,status (*visit)(TElemType e))
{
}。