数据结构基础知识整理 *名词解释1、数据：是信息的载体，能够被计算机识别、存储和加工处理。 *2、数据元素：是数据的基本单位，也称为元素、结点、顶点、记录。一个数据元素可 以由若干个数据项组成，数据项是具有独立含义的最小标识单位。 *3、数据结构：指的是数据及数据之间的相互关系，即数据的组织形式，它包括数据的 逻辑结构、数据的存储结构和数据的运算三个方面的内容。 *4、数据的逻辑结构：指数据元素之间的逻辑关系，即从逻辑关系上描述数据，它与数 据的存储无关，是独立于计算机的。 *5、数据的存储结构：指数据元素及其关系在计算机存储器内的表示。是数据的逻辑结 构用计算机语言的实现，是依赖于计算机语言的。 *6、线性结构：其逻辑特征为，若结构是非空集，则有且仅有一个开始结点和一个终端 结点，并且其余每个结点只有一个直接前趋和一个直接后继。 *7、非线性结构：其逻辑特征为一个结点可能有多个直接前趋和直接后继。 *8、算法：是任意一个良定义的计算过程，它以一个或多个值作为输入，并产生一个或 多个值作为输出；即一个算法是一系列将输入转换为输出的计算步骤。 *9、算法的时间复杂度T(n)：是该算法的时间耗费，它是该算法所求解问题规模n趋向无穷大时，我们把时间复杂度T(n)的数量级（阶）称为算法的渐近时间复杂度。 *10、最坏和平均时间复杂度：由于算法中语句的频度不仅与问题规模n有关，还与输入实例等因素有关；这时可用最坏情况下时间复杂度作为算法的时间复杂度。而平均时间复杂度是指所有的输入实例均以等概率出现的情况下，算法的期望运行时间。 *11、数据的运算：指对数据施加的操作。数据的运算是定义在数据的逻辑结构上的，而 实现是要在存储结构上进行。 *12、线性表：由n(n≥0)个结点组成的有限序列。其逻辑特征反映了结点间一对一的关 系（一个结点对应一个直接后继，除终端结点外；或一个结点对应一个直接前趋，除开始结点外），这是一种线性结构。 *13、顺序表：顺序存储的线性表，它是一种随机存取结构。通过将相邻结点存放在相邻 物理位置上来反映结点间逻辑关系。 *14、单链表：每个结点有两个域：一个值域data；另一个指针域next，用来指向该结
2数据结构复习题（线性表） 一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳） （×）（1）线性表的链式存储结构优于顺序存储。 （×）（2）链表的每个结点都恰好包含一个指针域。 （√）（3）在线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。 （×）（4）顺序存储方式的优点是存储密度大，插入、删除效率高。 （×）（5）线性链表的删除算法简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。 （×）（6）顺序表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 （√）（7）线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。 （√）（8）线性表采用顺序存储，必须占用一片连续的存储单元。 （×）（9）顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 （ㄨ）（10）插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。 二．填空题 （1）顺序表中逻辑上相邻的元素在物理位置上必须相连。 （2）线性表中结点的集合是有限的，结点间的关系是一对一关系。 （3）顺序表相对于链表的优点是：节省存储和随机存取。 （4）链表相对于顺序表的优点是：插入、删除方便。 （5）采用顺序存储结构的线性表叫顺序表。 （6） （7）链表相对于顺序表的优点是插入、删除方便；缺点是存储密度 （8）在双链表中要删除已知结点*P （9）在单链表中要在已知结点*P之前插入一个新结点，需找到*P的直接前趋结点的地址，其查找的时间复杂度为 O(n) 。 （10）单链表中需知道头指针才能遍历整个链表。 （11）性表中第一个结点没有直接前趋，称为开始结点。 （12）在一个长度为n的顺序表中删除第i个元素，要移动n-i 个元素。 （13）在一个长度为n的顺序表中，如果要在第i个元素前插入一个元素，要后移n- i +1 个元素。（14）在无头结点的单链表中，第一个结点的地址存放在头指针中，而其它结点的存储地址存放在前趋结点的指针域中。 （15）当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快速度存取线性表中的元素时，应采用顺序存储结构。 （16）在线性表的链式存储中，元素之间的逻辑关系是通过指针决定的。 （17）在双向链表中，每个结点都有两个指针域，它们一个指向其前趋结点，另一个指向其后继结点。 （18）对一个需要经常进行插入和删除操作的线性表，采用链式存储结构为宜。 （19）双链表中，设p是指向其中待删除的结点，则需要执行的操作为：p->prior->next=p->next 。（20）在如图所示的链表中，若在指针P所在的结点之后插入数据域值为a和b的两个结点，则可用下列两个语句： S->next->next=P->next; 和P->next=S;来实现该操作。
广州大学2017—2018 学年第一学期考试卷 课程软件工程导论考试形式（闭卷，考试） 一、单选题（每小题1分，共25分，答案写在下表中） 1.软件工程方法的提出起源于软件危机，而其目的应该是最终解决软件的（D）问题 A.产生危机 B.质量保证 C.开发效率 D.生产工程化 2.瀑布模型将软件生命周期归纳为3个时期，即计划期、开发期和运行期。下列（D ）不属于开发期内的工作。 A.总体设计 B.详细设计 C.程序设计
D.维护 3.结构化方法将软件生命周期分为计划、开发和运行3个时期，下列任务中（B）属于计划时期的任务。 A.需求分析 B.问题定义 C.总体设计 D.编码 4.可行性研究要进行一次（C）需求分析。 A.详细的 B.全面的 C.简化的、压缩的 D.彻底的 5.经济可行性研究的范围包括（C）。 A.资源有效性 B.管理制度 C.效益分析 D.开发风险 6.可行性分析是在系统开发的早期所做的一项重要的论证工作，它是决定该系统是否开发的决策依据，因必须给出（B）的回答。 A.确定 B.行或不行 C.正确 D.无二义 7.产生软件维护的副作用，是指（C ）。 A.开发时的错误 B.隐含的错误 C.因修改软件而造成的错误 D.运行时错误操作 8.软件需求分析阶段的工作，可以分为4个方面：需求获取、需求分析、编写需求规格说明书以及（B）。 A.用户 B.需求评审 C.总结 D.都不对
9.软件开发的结构化分析方法，常用的描述软件工程需求的工具是（C） A.业务流程图、处理说明 B.软件流程图、模块说明 C.数据流程图、数据字典 D.系统流程图、程序编码 10.数据流图用于抽象描述一个软件的逻辑模型，数据流图由以写特定的图符构成。下列图符名标识的图符不属于数据流图合法图符的是（A） A.控制流 B.加工 C.数据存储 D.数据流 11.软件开发的结构生命周期法的基本假定是认为软件需求能做到（C） A.严格定义 B.初步定义 C.早期冻结 D.动态改变 软件需求经过分析阶段后，通过软件需求说明书表示出来，后面的开发工作以此为基础进行，即假定软件需求确定后一般不再改变，即“早期冻结”。 12.在结构化方法中，软件功能分解属于软件开发中的（C）阶段 A.详细设计 B.需求分析 C.总体设计 D.编程调试 13.概要设计的结果是提供一份（A） A.模块说明书 B.框图 C.程序 D.数据流图 14.耦合是软件各个模块间连接的一种度量。一组模块都访问同一数据结构应属于（B）方式 A.内容耦合 B.公共耦合 C.控制耦合 D.数据耦合 解释：耦合分为以下几种，按照耦合度由高到低排列是：
数据结构试卷(一) 一、单选题(每题 2 分，共 20 分) 1. 栈和队列的共同特点是 ( )。 A. 只允许在端点处插入和删除元素 B. 都是先进后出 C. 都是先进先出 D. 没有共同点 2. 用链接方式存储的队列，在进行插入运算时 ( ). 4. 设有一个二维数组 A[m][n] ，假设 A[0][0] 存放位置在 644(10)， A[2][2] 存放位置在 676(10)，每个元素占一个空间， 问 A[3][3](10) 存放在什么位置？脚注 (10)表示用 10 进制表示。 7. 若有 18个元素的有序表存放在一维数组 A[19] 中，第一个元素 放 A[1] 中，现进行二分查找，则查找 A [ 3]的比较序列的下 标依次为 ( ) B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 8. 对 n 个记录的文件进行快速排序，所需要的辅助存储空间大致 为 A. O (1) B. O (n ) C. O (1og 2n ) D. O (n2) 9. 对于线性表( 7，34，55，25，64，46，20，10)进行 散列存储 时，若选用 H ( K ) =K %9作为散列函数，则散列地址为 1 的元 素有( )个， A ．1 B ．2 C ．3 D ．4 10. 设有6个结点的无向图，该图至少应有 A. 仅修改头指针 B. C. 仅修改尾指针 D. 改 3. 以下数据结构中哪一个是非线性结构？ A. 队列 B. 栈 叉树 头、尾指针都要修改 头、尾指针可能都要修 ( ) C. 线 性表 D. A ．688 B ．678 C ．692 D ．696 5. 树最适合用来表示 ( )。 A .有序数据元素 C .元素之间具有分支层次关系的数据 系的数据 6. 二叉树的第 k 层的结点数最多为 ( ). k A ．2k -1 B.2K+1 C.2K-1 B.无序数据元素 D.元素之间无联 D. 2 k-1 A. 1， 2，3
考研心得 考研是一个枯燥而又艰辛的过程，既然决定考研就应该做好长期作战的准备保持一颗平静的心，坚持到考研结束的那一刻，考研是否成功，实力是一方面更重要的就是选择了。实力加上正确的选择，一定会事半功倍。 1. 2017“广大土木”研究生入学考试专业课(结构力学)真题分析 整体来说学硕较前几年难度相当，专硕较前几年难度提升了，学硕没有大的变化，专硕题型的变化主要体现在以下几个方面①计算量加大，以往的q、Fp用真真切切的数字代替;②图形稍有变化。这就导致很多包括我在内的考生不适应，后面我再一个一个题分析详说。从2013年开始，广大土木研究生入学考试专业课(结构力学)题量定为专硕9道计算题，学硕11道计算题，学硕较专硕多了矩阵位移法和画影响线2道题，没有特别说明题型及题量应该还不会变。由于专硕变化较大，下面以下分析详说以专硕考题为主，学硕考题为辅(学硕考题有变动的地方会在每题后面说明，如无说明即表示和往年差不多，其他都是专硕题目的比较)。 第一题(分析体系的几何组成):图形较前几年稍复杂，需要花点时间分析。 第二题(画结构弯矩图):图形较往年有变化，2017年是画连续梁的弯矩图，前几年考的是刚架。单看这道题是简单，但是对于前期研究了几个月广大结构力学真题的考生来说，图形的突然变化会感到短暂的缺氧[可能你会觉得夸张，但是在考场上就是这个感觉。所以这个时候需要你有扎实的基础和强大的抗压能力，最重要的是扎实的基础，有了扎实的基础，抗压能力自然而然就提升了。 第三题(画结构内力图<弯矩图、剪力图、轴力图>):特别注意两根竖杆长度不一样，可能在看题的时候注意到了，在计算的时候很可能会忘记。我当时就忽略了，后面检查发现错了，超级紧张，因为当时只剩下半个小时了，后面题目还没检查。 第四题(求指定杆件轴力):这道题就是求简单的析架结构中杆件的轴力，较往年不同就是Fp用数值代替。方法不外乎就是截面法和节点法。 第五题(求杆件位移):专硕这道题较往年变化不大，学硕这道题2017年由前几年求刚架结构中某点的位移变成求析架中杆件的位移，所以学弟学妹们复习时不能忽略这个知识点，特别注意求析架中某根杆的转角位移。 第六题(力法画弯矩图):图形稍有变化，力的大小全用数值代替。这道题是由基本部分和附属部分组成，只有基本部分有一个多余约束，
数据结构试卷（一） 一、单选题（每题 2 分，共20分） 1.栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)， A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。 A．688 B．678 C．692 D．696 5.树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联 系的数据 6.二叉树的第k层的结点数最多为( ). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 7.若有18个元素的有序表存放在一维数组A[19]中，第一个元素 放A[1]中，现进行二分查找，则查找A［3］的比较序列的下 标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 8.对n个记录的文件进行快速排序，所需要的辅助存储空间大致 为 A. O（1） B. O（n） C. O（1og2n） D. O（n2） 9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储 时，若选用H（K）=K %9作为散列函数，则散列地址为1的元 素有（）个， A．1 B．2 C．3 D．4
数据结构复习题 一、单选题(每小题2分，共12分) 1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。 A． HL＝ps p一>next＝HL B． p一>next＝HL；HL＝p3 C． p一>next＝Hl；p＝HL； D． p一>next＝HL一>next;HL一>next＝p； 2．n个顶点的强连通图中至少含有( )。 A.n—l条有向边 B.n条有向边 C.n(n—1)／2条有向边 D.n(n一1)条有向边 3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A.O(1) B.O(n) C.O(1Ogzn) D.O(n2) 4．由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。 A．24 B．48 C． 72 D． 53 5．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。 A.整形 B.引用型 C.指针型 D.常值引用型· 6．向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )。 A．O(n) B．O(1) C．O(n2) D．O(10g2n) 二、填空题(每空1分，共28分) 1．数据的存储结构被分为——、——、——和——四种。 2．在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为——域和——域。 3．——中缀表达式 3十x*(2.4／5—6)所对应的后缀表达式为————。 4．在一棵高度为h的3叉树中，最多含有——结点。 5．假定一棵二叉树的结点数为18，则它的最小深度为——，最大深度为——· 6．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定——该结点的值，右子树上所有结点的值一定——该结点的值。 7．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层——调整，直到被调整到——位置为止。 8．表示图的三种存储结构为——、——和———。 9．对用邻接矩阵表示的具有n个顶点和e条边的图进行任一种遍历时，其时间复杂度为——，对用邻接表表示的图进行任一种遍历时，其时间复杂度为——。 10．从有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素时，其查找长度分别为——和——· 11．假定对长度n＝144的线性表进行索引顺序查找，并假定每个子表的长度均为，则进行索引顺序查找的平均查找长度为——，时间复杂度为——· 12．一棵B—树中的所有叶子结点均处在——上。 13．每次从无序表中顺序取出一个元素，把这插入到有序表中的适当位置，此种排序方法叫做——排序； 每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做——排序。 14．快速排序在乎均情况下的时间复杂度为——，最坏情况下的时间复杂度为——。 三、运算题(每小题6分，共24分) 1．假定一棵二叉树广义表表示为a(b(c，d)，c(((，8)))，分别写出对它进行先序、中序、后序和后序遍历的结果。 先序： 中序； 后序： 2．已知一个带权图的顶点集V和边集G分别为： V＝{0，1，2，3，4，5}；
最新广州大学考研笔记汇总 ——广大本科笔记与考研真题哪里下载 考研笔记是往届考研的高分学长学姐们复习时对于考点的把握和理解的体现，往往内容详细条理清晰，手握一份广大学长学姐们的考研笔记，就感觉已经一脚踏进了大学的门槛，考研笔记就是这么神奇的存在，不过由于笔记数量过于稀缺，有需求的考生又很多，总有许多考生抱怨根本买不到。 针对考研笔记的稀缺性，鸿知广大考研网官方教学研发团队联合广大各专业排名前三的学长学姐们针对广州大学各专业考点，共同编写了一系列《考研复习全析》，发售五年来好评率超过98%！《考研复习全析》结合往年广大考研真题答案，帮助报考广州大学考研的同学通过广大教材章节框架分解、配套的课后习题讲解及相关名校考研真题与解答，帮助考生梳理指定教材的各章节内容，深入理解核心重难点知识，把握考试要求与考题命题特征。 最新广州大学考研笔记汇总全文完整内容请打开链接查看： https://www.doczj.com/doc/b52380408.html,/search/?keywords=%u5168%u6790 [ 鸿知广大考研网] 2019广大考研333教育综合复习全析（含真题答案，共三册） [ 鸿知广大考研网] 2019广大考研398法硕联考专业基础复习全析（含真题答案，共三册）[ 鸿知广大考研网] 2019广大考研498法硕联考综合复习全析（含历年真题，共四册） [ 鸿知广大考研网] 2019广州大学868经济学考研复习全析（共两册） [ 鸿知广大考研网] 2019广大考研812分析化学复习全析（含真题，共两册） [ 鸿知广大考研网] 2019广大853概率论与数理统计考研复习全析（含真题，共三册） [ 鸿知广大考研网] 2019广州大学考研817环境学复习全析（含历年真题，共两册） [ 鸿知广大考研网] 2019广州大学考研632历史学基础复习全析（含历年真题，共11册）
院、系领导 A 卷 审批并签名 ` 广州大学2014—2015 学年第一学期考试卷课程软件工程导论考试形式（闭卷，考试）学院计算机科学与教育软件班级学号姓名 题次一二三四五六七八九十总分评卷人分数10 16 25 49 100 评分 一、单选题（每小题1分，共10分，答案写在下表中） 1 2 3 4 5 6 7 8 9 10 B A C D C C A B A D 1.研究开发所需要的成本和资源是属于可行性研究中的( )研究的一方 面。 A.技术可行性 B.经济可行性 C.社会可行性 D.法律可行性 2．结构化分析方法是在软件开发过程中常用的方法。这个方法采用的基本手段是（）。 A.分解与抽象 B.分解与综合 C.归纳与推导 D.试探与回溯 3.若有一个计算类型的程序，它的输入量只有一个X，其范围是［-1.0，1.0］， 现从输入的角度考虑一组测试用例：-1.001，-1.0，1.0，1.001。设计这组测试用例的方法是( ) A.条件覆盖法 B.等价分类法 C.边界值分析法 D.错误推测法
4.快速原型模型的主要特点之一是( ) A.开发完毕才见到产品 B.及早提供全部完整的软件产品 C.开发完毕后才见到工作软件 D.及早提供工作软件 5.软件可维护性的特性中相互矛盾的是（） A.可修改性和可理解性 B.可测试性和可理解性 C.效率和可修改性 D.可理解性和可读性 6.软件维护产生的副作用，是指（） A.开发时的错误 B.隐含的错误 C.因修改软件而造成的错误 D.运行时误操作 7.软件开发时，一个错误发现得越晚，为改正它所付出的代价就（）。 A.越大 B.越小 C.越不可捉摸 D.越接近平均水平 8.软件测试的目的是（）。 A.评价软件的质量 B.发现软件的错误 C.找出软件中的所有错误 D.证明软件是正确的 9.面向对象系统的多态是（）。 A．不同的对象收到相同的消息时产生不同的动作 B．不同的对象收到相同的消息时产生相同的动作 C．相同的对象收到相同的消息时产生不同的动作 D．相同的对象收到相同的消息时产生相同的动作 10.软件测试方法中的（）属于静态测试方法。 A.黑盒法 B.路径覆盖 C.错误推测 D.人工检测 二、填空题（每空1分，共16分） 1、用户关注软件质量的外部属性，如软件的正确性、可靠性、有效性、完整性、可用性、可维护性、可移植性、可复用性等。(顺序可互换)
2014年肇庆学院本科插班生考试大纲 （数据结构） Ⅰ考试性质 普通高等学校本科插班生（又称专插本）招生考试是由专科毕业生参加的选拔性考试。高等学校根据考生的成绩，按照已确定的招生计划，德、智、体全面衡量，择优录取。因此，本科插班生考试应有较高信度、效度、必要的区分度和适当的难度。 Ⅱ考试内容及要求 一、考试基本要求 主要测试考生对数据结构各项内容的掌握程度。要求考生熟悉计算机处理数据的基本方法，掌握计算机加工的数据结构的特性，熟悉为实际应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并掌握算法的时间分析和空间分析技术。考试中相关算法要求用类C语言描述。 二、考试知识点 1．数据结构的基本概念 数据数据元素数据结构数据类型算法 算法的描述和算法分析 算法描述方法 算法效率的判断标准 算法的时间复杂度、空间复杂度计算 2．线性表 线性表、单链表、循环链表和双向链表的概念； 线性表的存储结构实现及应用。 3．堆栈和队列 堆栈和队列的基本概念； 堆栈和队列的存储实现； 堆栈和队列的基本运算的实现； 堆栈和队列的基本应用。 4．串 串的基本概念及其存储结构实现。 5．数组 数组、特殊矩阵和稀疏矩阵的概念； 三元组表。 6．树和二叉树 树、森林和二叉树的概念； 二叉树的存储结构； 树或森林与二叉树的相互转化； 树和二叉树的遍历算法； 哈夫曼树的构造和应用。 7．图 图的概念及存储实现； 图的遍历：深度优先搜索与广度优先搜索； 最小生成树的构造；最短路径。 8．排序 插入（直接和希尔）、选择（直接和堆）、交换（冒泡和快速）、归并、基数等排序算法的基本思想；
各排序算法的实现、时间复杂度和稳定性。 9．查找 查找的基本概念；静态查找表；动态查找表；哈希表； 各种查找算法的实现。 Ⅲ考试形式及试卷结构 一、考试形式： 闭卷，笔试，考试时间为120分钟，试卷满分为100分。考生使用答题卡答题。 二、试题题型及赋分： 1、选择题………………………………约占30% 2、判断题………………………………约占15% 3、填空题………………………………约占15% 4、概念与术语解释题…………………约占10% 5、分析简答及应用题…………………约占20% 6、算法设计与分析题…………………约占10% Ⅳ题型示例 一、单项选择题 1. 从逻辑上可以把数据结构分为（）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 2. 线性表是（）。 A．一个有限序列，可以为空 B．一个有限序列，不能为空 C．一个无限序列，可以为空 D．一个无限序列，不能为空 二、判断题（正确的在括号内填√，错识的填×） （）1. 算法必须有输出，但可以没有输入。 （）2．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。 三、填空题 1．已知指针p指向单链表L中的某结点，则删除其后继结点的语句序列是： ；；。 四、概念与术语解释 1. 算法的时间复杂度 2. 查找表 五、分析简答及应用题 1. 请分别写出线性表的链式存储结构、二叉树的二叉链表存储结构的类C语言描述。 六、算法设计与分析题（请加适当的注释） 单链表L是一个递减有序表，试编写高效算法，删除表中值大于min且小于max的结点，同时释放被删结点的空间，这里min和max是两个给定的参数。请分析你的算法的时间复杂度。 Ⅴ参考书目 《数据结构与算法》（第二版），张晓莉、王苗等编著，北京，机械工业出版社，2008年。
6数据结构复习题（广义表） 一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳） （√）（1）n维的多维数组可以视为n-1维数组元素组成的线性结构。 （√）（2）稀疏矩阵中非零元素的个数远小于矩阵元素的总数。 （ㄨ）（3）上三角矩阵主对角线以上（不包括主对角线中的元素），均为常数C。 （√）（4）数组元素可以由若干个数据项组成。 （√）（5）数组的三元组表存储是对稀疏矩阵的压缩存储。 （ㄨ）（6）任何矩阵都可以进行压缩存储。 （ㄨ）（7）广义表是线性表的推广，所以广义表也是线性表。 （ㄨ）（8）广义表LS=（a0,a1,……a n-1），则a n-1是其表尾。 （√）（9）广义表((a,b),a,b)的表头和表尾是相等的。 （√）（10）一个广义表的表尾总是一个广义表。 二．填空题 （1）多维数组的顺序存储方式有按行优先顺序存储和按列优先顺序存储两种。 （2）在多维数组中，数据元素的存放地址可以直接通过地址计算公式算出，所以多维数组是一种随机存取结构。 （3）在n维数组中的每一个元素最多可以有 n 个直接前驱。 （4）输出二维数组A[n][m]中所有元素值的时间复杂度为O(n*m) 。（5）数组元素a[0..2][0..3]的实际地址上2000，元素长度是4，则LOC[1,2]= 2024 。LOC[1,2]=2000+（1*4+2）*4 （6）稀疏矩阵的三元组有 3 列。 （7）稀疏矩阵的三元组中第1列存储的是数组中非零元素所在的行数。（8）n阶对称矩阵，如果只存储下三角元素，只需要 n（n-1）/2 个存储单元。（9）稀疏矩阵A如下图所示，其非零元素存于三元组表中，三元组（4，1，5）按列优先顺序存储在三元组表的第 4 项。 A= 稀疏矩阵A
2015届广州大学土木工程考研结构力学真题、复习题库、考前重点、考研经验 我是广州大学2013届建筑与土木（专硕）2班在读的研究生，本科也在广州大学读，尽管是本校学生，但是考研的时候专业课也遇到不少的问题，有时候感觉很困惑，当时想假如有考研成功的师兄给下意见就好了，更别说跨校考广州大学的师弟师妹了，因此，对于报考广州大学研究生的师弟师妹们，我还是有些经验可以和大家分享的： 政治：当年我复习政治用的时间太多，做了很多无用功，其实政治不用花太多的时间，基本大家都过线的，而且分数都差不多，不过假如你要拿很高的分数那另说，但要拿很高的分数要花费很多时间是不值得的，还是要将时间用在数学和专业课上，做一下选择题，尽量提高正确率，大题其实看一下真题，整理一下答题思路就可以了，那年我还做了任汝芬，肖秀荣最后四套题，最后发现考试的时候很多都与四套题里面的大题相似，所以做好最后四套题，大题写满，就差不多了。 英语：我方法是每天都背一下单词，将真题认真的做，将真题不懂的词语句子认真搞懂，作文最好是练一下，但是假如没时间的话，可以整理一下作文的格式，大部分人都是整理一下作文的格式，按照格式套进去写的。 数学：数学是毫无疑问的重点，分数的差距就在于数学，我
数学不太好，经验就不介绍了，不过花时间在数学上是一定的，专业课：广州大学土木工程的专业课很简单的，结构力学基本上都是130,140的，因为题目很简单，而且每年的题目变化不大，结构力学满分真的没什么，但是只有120分那就会被别人拉开差距了，因此要认真地将真题都做一遍，看自己哪里错，其实认真研究真题的就会发现历年题目类似，只要将真题弄懂，将复习资料都搞懂了，不需要看太多复杂的东西，所以有些同学说看了两个星期就能考140了，但这要建立在有一定力学基础、良好的学习方法、有完备的复习资料的基础上，但是尽量不要这样，提前两三个月看，每天都做一下题目，题目是简单，但是要拿满分还是要下些功夫的。 所以我建了一个2015届广州大学土木工程学院的考研交流的企鹅群：2015广大土木工程考研（ 98967687）。 考研群主要是让有意向报考2015届广州大学土木工程学院的师弟师妹有机会交流，有关于广州大学、考研的问题都可以问我，我可以提供本校的复习题库、资料、历年的结构力学真题及答案（因为历年真题是没有答案和解题过程的，我当年复习时候和同学对答案做的，但没有官方答案，总感觉不知道做的对不对，所以我和同学整理了答案，便于大家复习，答案是自己和同学做的，结构力学我考得还不错，考了149，应该可以给大家提供一些帮助。）除了历年的真题，我还有每一章节的复习资料，每年的考研题目基本上都是从那复习资料里变一下或者直接用原题，
“数据结构”期末考试试题 一、单选题(每小题2分，共12分) 1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。 A． HL＝ps p一>next＝HL B． p一>next＝HL；HL＝p3 C． p一>next＝Hl；p＝HL； D． p一>next＝HL一>next;HL一>next＝p； 2．n个顶点的强连通图中至少含有( )。 A.n—l条有向边 B.n条有向边 C.n(n—1)／2条有向边 D.n(n一1)条有向边 3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A.O(1) B.O(n) C.O(1Ogzn) D.O(n2) 4．由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。 A．24 B．48 C． 72 D． 53 5．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。 A.整形 B.引用型 C.指针型 D.常值引用型· 6．向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )。 A．O(n) B．O(1) C．O(n2) D．O(10g2n) 二、填空题(每空1分，共28分) 1．数据的存储结构被分为——、——、——和——四种。 2．在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为——域和——域。 3．——中缀表达式 3十x*(2.4／5—6)所对应的后缀表达式为————。 4．在一棵高度为h的3叉树中，最多含有——结点。 5．假定一棵二叉树的结点数为18，则它的最小深度为——，最大深度为——· 6．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定——该结点的值，右子树上所有结点的值一定——该结点的值。 7．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层——调整，直到被调整到——位置为止。 8．表示图的三种存储结构为——、——和———。 9．对用邻接矩阵表示的具有n个顶点和e条边的图进行任一种遍历时，其时间复杂度为——，对用邻接表表示的图进行任一种遍历时，其时间复杂度为——。 10．从有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素时，其查找长度分别为——和——· 11．假定对长度n＝144的线性表进行索引顺序查找，并假定每个子表的长度均为，则进行索引顺序查找的平均查找长度为——，时间复杂度为——· 12．一棵B—树中的所有叶子结点均处在——上。 13．每次从无序表中顺序取出一个元素，把这插入到有序表中的适当位置，此种排序方法叫做——排序；每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做——排序。 14．快速排序在乎均情况下的时间复杂度为——，最坏情况下的时间复杂度为——。 三、运算题(每小题6分，共24分) 1．假定一棵二叉树广义表表示为a(b(c，d)，c(((，8)))，分别写出对它进行先序、中序、后序和后序遍历的结果。 先序： 中序； 后序： 2．已知一个带权图的顶点集V和边集G分别为： V＝{0，1，2，3，4，5}； E={(0，1)8，(0，2)5，(0，3)2，(1，5)6，(2，3)25，(2，4)13，(3，5)9，(4，5)10}， 则求出该图的最小生成树的权。 最小生成树的权； 3．假定一组记录的排序码为(46，79，56，38，40，84，50，42)，则利用堆排序方法建立的初始堆为——。 4．有7个带权结点，其权值分别为3，7，8，2，6，10，14，试以它们为叶子结点生成一棵哈夫曼树，求出该树的带权路径长度、高度、双分支结点数。 带权路径长度：——高度：——双分支结点数：——。 四、阅读算法，回答问题(每小题8分，共16分) 1．VOldAC(List&L) { InitList(L)； InsertRear(L;25)；
《软件工程导论》课程教学大纲 一、教学大纲说明 1）课程的地位、作用和任务 《软件工程导论》是计算机软件专业的必修课程。该学科涉及到为高效率地构建满足客户需求的软件系统所需的理论、知识和实践的应用。软件工程适用于各类软件系统的开发，它包含需求分析和规约、设计、构建、测试、运行和维护等软件系统生存周期的所有阶段。 本课程是计算机及相关专业的核心课程之一，是指导软件开发、研究的系统的科学的工程方法学科。掌握必要的、丰富的软件工程知识、原理、方法、工具和管理知识等是开发出优秀软件产品基础条件。 2）课程教学的目的和要求 本课程让学生理解如何以工程技术的概念、原理和方法来开发和维护软件系统。软件工程使用工程化方法、技术和度量，学生应该了解使用管理软件开发的工具、软件制品的分析和建模工具、质量评估与控制工具、确保有条不紊且有控制地实施软件演化和复用的工具，掌握选择最适合开发环境的工具、方法和途径以控制软件系统生产的质量、进度、成本等。 通过本课程的学习，使学生既掌握软件工程的基本原理和方法，又掌握软件开发过程及过程中使用的各种方法、工具，熟悉开发大型软件系统所需的各种知识，重点掌握面向对象的软件开发理论及方法，了解软件项目管理和测试知识，培养设计、实现、管理软件项目的能力。 3）课程教学方法与手段 本课程以多媒体教案为教学手段。《软件工程导论》是一门技术和管理交叉型的学科，旨在培养高级软件开发人才，而学生的基础差距很大，致使教学难度很大。在教学中拟采用课堂讲授与实习研讨并重的方式以提高学生的学习兴趣和效果。教学管理和考核拟以学习
小组为基本单元（而不是个人）从而强化团队作业精神和协作能力。除课上可参考的power point课件外，还会推荐给学生一些经典资料，供学生在课外参考。 4）课程与其它课程的联系 计算机原理、数据结构、C++程序设计语言、操作系统、计算机网络、数据库原理是《软件工程导论》课程的先行课程，该课程是这些先行课程在实际开发中的运用。 5）教材与教学参考书 教材：《软件工程》（第3版），齐治昌等著2012年05月出版 参考书：《软件工程》郑人杰等著，人民邮电出版社2009-11版，2012年第3次印刷。 《实用软件工程》赵池龙，杨林，孙伟，电子工业出版社，2006年7月2版。 《软件工程导论》张海藩编著，清华大学出版社，2008年第5版。 《软件工程》邓良松等编著，西安电子科技大学出版社，2000年。 二、课程的教学内容、重点和难点 第1章软件与软件工程 1.1软件的概念 1.2软件工程的概念 1.3软件过程模型 1.4敏捷软件开发原则和应用 1.5软件工程人的因素 1.6软件工具及软件开发环境 1.7基于计算机的系统 第2章UML与RUP统一过程 2.1案例说明 2.2面向对象的软件开发方法 2.3ＵＭＬ概述 2.4ＲＵＰ统一过程 第3章需求工程概论 3.1软件需求的概念 3.2需求工程的预备知识 3.3需求工程的过程模型 第4章需求获取 4.1软件需求的初始表示 4.2需求获取的过程模型
师弟师妹们： 你们好！过完一个快乐的春节，新的任务又来了！在这里，首先是恭喜大家顺利通过初试，获得了复试的资格，进复试了也可以说几乎接近梦想成真了！剩下的大家只要鼓最后一把劲，按部就班的复习，一般就不会出很大意外了，但是大家千万不要掉以轻心，否则功亏一篑。下面大致跟大家说下复试相关方面的问题： 广大复试主要分为几部分：（以下任何一门不得低于60分） 1、专业课笔试（具体科目招生目录就有） 2、专业课面试（到时候分专业进行，我们为大家准备了一些历年常见问题） 3、专业英语笔试（考试形式不是很稳定，但是应该是作文+翻译的两种题型，具体翻译考一段话翻译还是多个单句翻译说不好） 4、英语面试（一般是进去之后与老师对几句话，除了聊聊基本信息还可能问你一些常见的问题，我们也已经做了总结；然后看一份英文论文的一段口头翻译，老师现场打分） 还有一些温馨提示： 1、及时关注学校出的任何通知，过来带好要求带的一切证件。 2、来复试尽量提前一两天来，定好房间安顿下来，复试一般需要一个周左右时间，住的地方除了学校推荐的学校的招待所外（相对较贵），还可以住在北亭村中（百余家旅社，离学校很近）。 3、交通路线：（建议坐地铁，当然熟悉的话公交也很方便的） 广州火车站下车的同学路线：出站往左走100m找地铁口，5号线到车陂南转4号线到大学城北下车，A出口往回走50m，坐经过广大公交车。广州东站下车的同学的路线：3号线北延段至体育西路转3号线至珠江新城转5号线至车陂南转4号线至大学城北，A出口，再往回走50m，坐经过广大的公交车。广州南站（高铁站）的同学直接做“番52路”公交车直达广大，55分钟，票价4元。 其他汽车站的同学大家自己查询！当然，具体路线大家还可以百度地图哦！
10数据结构复习题（排序） 一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳） （ㄨ）（1）如果某种排序算法不稳定，则该排序方法就没有实用价值。 （√）（2）希尔排序是不稳定的排序。 （ㄨ）（3）冒泡排序是不稳定的排序。 （√）（4）对n个记录的进行快速排序，所需要的平均时间是O(nlog2n)。 （ㄨ）（5）堆排序所需的时间与待排序的记录个数无关。 （√）（6）当待排序的元素个数很多时，为了交换元素的位置要占用较多的时间，这是影响时间复杂度的主要因素。 （ㄨ）（7）快速排序在任何情况下都比其它排序方法速度快。 （√）（8）对快速排序来说，初始序列为正序或反序都是最坏情况。 （√）（9）采用归并排序可以实现外排序。 （√）（10）采用希尔方法排序时，若关键字的排列杂乱无序，则效率最高。 （√）（11）快速排序算法在每一趟排序中都能找到一个元素放在其最终位置上。 （√）（12）冒泡排序的时间复杂度是O（n2）。 二．填空题 （1）大多数排序算法都有两个基本的操作：比较和移动。 （2）评价排序算法优劣的主要标准是时间复杂度和算法所需的附加空间。 （3）根据被处理的数据在计算机中使用不同的存储设备，排序可分为：内排序和外排序。（4）外排序是指在排序过程中，数据的主要部分存放在计算机的外存中。 （5）对n个关键字进行冒泡排序，其可能的最小比较次数为： n-1 次。 （6）在最坏情况下，在第i趟直接插入排序中，要进行 i-1 次关键字的比较。 （7）对n个关键字进行冒泡排序，时间复杂度为 O(n2) 。 （8）快速排序在最坏情况下的时间复杂度是 O(n2) 。 （9）对于n个记录的集合进行归并排序，所需要的平均时间为： O(log2n) 。 （10）对于n个记录的集合进行归并排序，所需要的附加空间是 O(n) 。 （11）若原始数据接近无序，则选用快速排序最好。 （12）在排序前，关键字值相等的不同记录，排序后相对位置保持不变的排序方法，称为稳定排序方法。 （13）在插入排序和选择排序中，若初始数据基本正序，则选用插入排序较好。 （14）当增量为1时，该趟希尔排序与直接插入排序基本一致。 （15）第一趟排序后，序列中键值最大的记录交换到最后的排序算法是冒泡排序。（16）依次将每个记录插入到一个有序的子文件中的排序方法称为直接插入排序。（17）在插入排序、选择排序和归并排序中，排序是不稳定的为：选择排序。
数据结构试卷（一) 一、单选题(每题2分,共20分） 1.栈和队列的共同特点是()。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D．没有共同点 2.用链接方式存储的队列，在进行插入运算时（）. Ａ. 仅修改头指针B．头、尾指针都要 修改 C．仅修改尾指针 D.头、尾指针可能 都要修改 3.以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈C．线性表 D. 二叉树 4.设有一个二维数组Ａ［m］[n]，假设A［0][0］存放位置在64 ４(１0),Ａ[2][2]存放位置在67６(１0),每个元素占一个空间,问 Ａ［３］[3］(10)存放在什么位置？脚注(10)表示用1０进制表 示。 A.6８８B．678 Ｃ．692 D.6９6 5.树最适合用来表示( ）。 A．有序数据元素 B.无序数 据元素 C．元素之间具有分支层次关系的数据Ｄ.元素之间无联系的数据 6.二叉树的第k层的结点数最多为（). A．２ｋ-1 B.2Ｋ+１Ｃ.２K-1 D．2k-１ 7.若有18个元素的有序表存放在一维数组A[19］中,第一个元素 放A[１］中，现进行二分查找，则查找Ａ［3］的比较序列的 下标依次为(） A．1，2，3 ??? B.9,５，２，3 C.９,5,3?????D．9,4，２，3 8.对n个记录的文件进行快速排序，所需要的辅助存储空间大致 为 A. Ｏ（1） B. O（n） C. O(１og2n）
Ｄ. Ｏ（n2） 9.对于线性表(７，34,55,25，64，４６,20,１0）进行散列存储 时,若选用H（K)=K %９作为散列函数,则散列地址为1的元素 有（）个， A．1 B.2 C．3 D．4 10.设有6个结点的无向图，该图至少应有 ( )条边才能确保是一个连通图。 A．５ B.6 C.7 D．８ 二、填空题(每空１分,共２6分） 1.通常从四个方面评价算法的质量:______＿_＿、_________、__＿ ＿_＿___和＿_＿＿_＿___。 2.一个算法的时间复杂度为（n３＋ｎ2ｌog2n+１4n)/n2，其数量级 表示为__＿_____。 3.假定一棵树的广义表表示为A(Ｃ，D(Ｅ,Ｆ，Ｇ），H(I，J))，则树 中所含的结点数为_＿_____＿__个,树的深度为__＿___＿＿___，树的度为____＿＿_＿_。 4.后缀算式9 2 ３+- １0 2 / -的值为＿_____＿___。中缀算式（3+ ４X)-2Y/3对应的后缀算式为__＿_＿＿______＿___＿＿＿_________＿＿_。 5.若用链表存储一棵二叉树时，每个结点除数据域外,还有指向左孩 子和右孩子的两个指针。在这种存储结构中,n个结点的二叉树共有＿__＿_＿＿_个指针域，其中有_____＿__个指针域是存放了地址,有_＿__＿＿＿_＿＿＿＿____个指针是空指针。 6.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的 邻接表中,所含边结点分别有_____＿_个和＿_______个。 7.AOV网是一种＿__＿_＿＿_＿＿_＿_＿_____的图。 8.在一个具有n个顶点的无向完全图中，包含有____＿__＿条边,在 一个具有n个顶点的有向完全图中，包含有_＿_＿＿＿__条边。 9.假定一个线性表为(12,23,74,55，６3,4０)，若按Keｙ% 4条件进 行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为__＿＿＿＿_＿___________＿________、__________＿＿___＿___、＿＿________＿_＿__________和____＿___________＿____＿＿_＿＿。 10.向一棵B_树插入元素的过程中,若最终引起树根结点的分裂,则新 树比原树的高度___＿___＿_＿＿。 11.在堆排序的过程中,对任一分支结点进行筛运算的时间复杂度为 ________,整个堆排序过程的时间复杂度为＿_______。 12.在快速排序、堆排序、归并排序中,________＿排序是稳定的。