重庆大学数据结构与程序设计2005

《数据结构与算法》复习提纲一、程序设计原理理解二、栈(1) 栈说明：栈的定义和基本操作栈是一种特殊的线性表，只能在固定一段进行插入或者删除操作。

包含栈顶，栈底。

表中无元素时，成为空栈。

操作：empty,top,push,pop(2)栈的实现：顺序栈的实现利用连续的存储单元依次存放数据元素。

确定那一端表示栈底。

一般top=-1来表示空栈。

进栈操作时，先使top加1，用以指示新的栈顶位置。

先进后出。

上溢，top>=stacksize-1.下溢，top=-1(3) 应用-桌面计算器：理解(4) 应用-括号的匹配：理解(5) 抽象数据类型及其实现：理解三、队列(1) 定义：队列的定义和基本操作队列也是一种特殊的线性表，删除操作限定在表的一段，而插入操作在表的另一端。

队尾（rear）和对首（front）。

先进先出。

append，server，retrieve，empty，clear，full，size(2)队列的实现：顺序队列的实现删除操作由front指示，插入操作由rear指示。

rear》=maxsize队满，rear=front，表示队空。

(3)C++队列的循环实现：顺序队列的实现(4)演示和测试：理解(5) 队列的应用-模拟：理解操作系统中的各种资源请求排队和各种数据缓冲区的先进先出管理，各种应用系统的时间规划、时间模拟，树类和图类问题中的一些非递归搜索算法等等。

四、链式栈和链式队列(1) 指针和链式结构：理解链表的思想是为表结构的每一个元素扩充一个指针，这个指针给出了表中下一个元素的位置。

指针被定义为一个对象，经常是变量，用于存储其他对象的位置。

动态内存分配。

动态内存分配的优点：不需要预先分配存储空间，分配的空间可以根据程序的扩大和缩小(2)链栈：链式栈的实现(3) 带保护的链栈：理解(4) 链式队列：链式队列的实现(5) 应用-多项式运算：理解(6) 抽象数据类型及其实现：栈和队列的抽象数据类型定义五、递归(1) 递归导言：递归算法的两个组成部分、非形式化描述转化为递归定义（如求阶乘等）每个递归过程包括两个部分：终止条件，循环部分1.不需用递归处理的最小的、基本的问题2.将特定的问题简化成一个或多个更小的问题的通用方法，由此向前，最终将问题一直简化成基本问题。

天津大学数据结构和程序设计考研真题-考研资料-笔记讲义许多学生在考研复习的时候，都会遇到重点不明确，不知道从何复习的情况。

为此，研途宝考研网建议，考研复习中，专业的考研复习资料，是帮助考生能够快速掌握复习重点及方法必不可少的因素，然后就是真题和讲义，可以让同学了解历年考研的出题方向和大致范围。

研途宝考研网推出了天津大学数据结构和程序设计的考研复习资料及真题解析班，以下为详细介绍:天津大学数据结构和程序设计考研真题等资料由研途宝考研网签约的天津大学计算机科学与技术学院高分考研学生历时近一月所作，该考生在考研中取得了专业课129分的好成绩并在复试中更胜一筹，该资料包含该优秀本校考生的考研经验、考研试题解题思路分析、复试流程经验介绍以及针对官方指定参考书的重难要点并根据天津大学本科授课重点整理等，从漫漫初试长路到紧张复试亮剑为各位研友提供全程考研指导攻关。

特别说明：此科目06年以前科目名称为数据结构；自06年到08年科目名称改为计算机基础（包含数据结构、程序设计、计算机原理）；自09年开始全国统考，科目名称为计算机学科专业基础综合；自20XX年开始由学校自主命题，科目名称改为901数据结构与程序设计。

第一部分由研途宝考研网提供的核心复习资料：天津大学数据结构和程序设计资料编者序言：本文的重点在于C++，数据结构的复习和复试基本情况介绍。

C++、数据结构又分别从复习规划，复习用书，重点知识点结合历年考题这四个方面来展开的。

复习规划大家务必看一下，然后根据自己的实际情况在制定自己的复习时间，因为内容很多，大多数同学都在考试之前复习不完，在心理因素上就落了一节。

重点知识点一定要看了，这些知识点几乎每年都会有题了。

另外我还给了历年试题的答案供大家参考。

有的答案是自己做的答案，可能会有疏忽的地方。

望大家提出宝贵的意见和建议。

复试的东西现在了解一下即可，等到进复试了，还是有足够的时间看的。

另外我还给了些自己复习心得。

据重庆师范大学研究生院消息，2016年重庆师范大学考研参考书目与考试科目已发布，详情如下：101思想政治理论全国指定大纲和教材199管理类联考综合能力全国指定大纲和教材201英语一全国指定大纲和教材204英语二全国指定大纲和教材211翻译硕士英语参见有关专业学位指导委员会编制的考试大纲240自命题俄语《大学俄语简明教程》张宝钤编，高等教育出版社241自命题法语《法语》（1-3册），马晓宏编著，商务印书馆出版242自命题日语1.《中日交流标准日本语》中级（上册前10课），人民教育出版社2.《新世纪日本语教程》（自学用），清华大学外语系编，外语教学与研究出版社243自命题英语任选一套大学英语教材301数学一全国指定大纲和教材302数学二全国指定大纲和教材303数学三全国指定大纲和教材333教育综合1.《教育学基础》（第二版）全国十二所重点师范大学联合编写，教育科学出版社，2008版2.《中国教育史》孙培青主编，华东师范大学出版社，2009版3.《外国教育史》张斌贤主编，教育科学出版社，2008版4.《教育心理学》（第二版）张大均主编，人民教育出版社，2011版341农业知识综合三1.《大学计算机基础教程》（网络技术部分）张高亮编，清华大学出版社，2010年2.《Visual FoxPro程序设计》谭华山等著，清华大学出版社，2010年342农业知识综合四《管理学》（第四版），杨文士，人民大学出版社。

348文博综合1.《中国考古学通论》（修订版）张之恒著，南京大学出版社2.《中国博物馆学基础》王宏均著，上海古籍出版社354汉语基础参见有关专业学位指导委员会编制的考试大纲357英语翻译基础1.《英汉翻译教程》张培基等编，上海外语教育出版社2.《汉英翻译教程》吕瑞昌等编，陕西人民出版社445汉语国际教育基础参见有关专业学位指导委员会编制的考试大纲448汉语写作与百科知识参见有关专业学位指导委员会编制的考试大纲510素描《设计素描》（第2版）黄作林、杨悦、李育，重庆大学出版社610辩证唯物主义与历史唯物主义《辩证唯物主义与历史唯物主义》第五版，李秀林主编，中国人民大学出版社611教育学基础综合1.《教育学基础》全国十二所重点师范大学联合编写，教育科学出版社，20082.《中国教育史》孙培青，华东师范大学出版社，20093.《外国教育史》张斌贤，教育科学出版社，20084.《教育心理学》陈琦，高教出版社，20115.《教育科研方法》陈时见，高教出版社，2007612基础心理学《心理学导论》（第二版）黄希庭主编，人民教育出版社，2007年8月613高等数学Ⅱ《高等数学》（第六版）（上、下册），同济大学数学系编，高等教育出版社，2007年614教育技术学《教育技术学》何克抗、李文光编，北京师范大学出版社，2009年615文学1.《中国文学史》（四册）袁行霈主编，高等教育出版社2.《中国现代文学三十年》（修订本）钱理群、温儒敏、吴福辉，北京大学出版社616基础英语一《高级英语》（第一、二册）（第三版），张汉熙编，外语教学与研究出版社。

数据结构程序设计数据结构程序设计学院：信息工程学院专业：计算机科学与技术班级: 12级本科四班学号：姓名：姚宝龙指导教师：米文丽成绩：数据结构程序设计目录实验题目：通讯录管理系统一、问题与需求二、概要设计三、模块设计四、详细设计五、测试分析六、用户手册实验题目: 表达式求值一、实验目的二、实验要求三、设计思想(本程序中的用到的所有数据类型的定义，主程序的流程图及各程序模块之间的调用关系）实验题目：药店的药品销售统计一、实验目的和要求二、需求分析三、概要设计四、详细设计五、调试分析六、使用说明实验题目：通讯录管理系统一、问题与需求1．问题描述纸质的通讯录系统已经不能满足大家的要求，容易丢失、查找困难等问题是纸质通讯录所不能克服的缺点。

“学生通讯管理系统”是为了帮助老师、同学，或者其他一些需要使用通讯录的人员进行管理和分析的一种应用程序.2．需求分析(1) 输入数据建立通讯录（2）查询通讯录系统中满足要求的信息(3) 插入新的通讯录信息(4）删除不需要的通讯录信息(5) 查看所有通讯录信息二、概要设计为了实现需求分析的功能，可以从三个方面着手设计。

1．主界面设计为了实现学生通讯录管理系统各功能的管理，设计一个含有多个菜单项的主控菜单子程序以链接系统的各项子功能,方便用户使用本系统。

本系统主控菜单运行界面如图2—3所示。

2．存储结构设计本系统主要采用链表结构类型来表示存储在“学生通讯录管理系统”中的信息。

其中，链表结点由四个分构成通讯录成员学号、通讯录成员姓名、通讯录成员电话号码、指向该结构体的指针。

此外，本系统还设置了一个全局变量seat，表示通讯录中成员的序号。

3．系统功能设计本系统设置了5个子功能菜单,5个子功能的设计描述如下。

（1）建立通讯录系统.可以一次输入多个成员通讯录的信息,建立通讯录。

该功能由creatIncreLink （）函数实现。

（2）插入通讯记录。

每次可以插入一个成员通讯录的信息。

计算机专业基础综合数据结构（串）历年真题试卷汇编3(总分：60.00，做题时间：90分钟)一、单项选择题(总题数：13，分数：26.00)1.已知字符串S为“abaabaabacacaabaabcc”，模式串t为”abaabc”，采用KMP算法进行匹配，第一次出现“失配”(s[i]!=t[i])时，i=j=5，则下次开始匹配时，i和j的值分别是( )。

【2015年全国试题8(2)分】（分数：2.00）A.i=1，j=0B.i=5，j=0C.i=5，j=2 √D.i=6，j=2解析：解析：本题f串的存储下标从0开始，其next函数值是：一100112。

2.下面关于串的叙述中，哪一个是不正确的?( )【北方交通大学2001一、5(2分)】【江苏大学2005一、6(2分)】（分数：2.00）A.串是字符的有限序列B.空串是由空格构成的串√C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储解析：3.若串S1=ABCDEFG’，=‘9898’，‘S3=‘###’，S4=‘012345’，执行concat(replace(S1，substr(S1，lengthCS2)，length(S3))，S3)，substr(S4，index(S2，‘8’)，lengthCS2)))，其结果为( )。

【北方交通大学1 999一、5(25／7分)】（分数：2.00）A.ABC###G0123B.ABCD###2345C.ABC###4G2345D.ABC###2345E.AB###G1234 √解析：4.设有两个串S1和S2，求S2在S1中首次出现的位置的运算称作( )。

【中南大学2005一、3(2分)】（分数：2.00）A.求子串B.判断是否相等C.模型匹配√D.连接解析：5.已知串S=‘aaab’，其Next数组值为( )。

【西安电子科技大学1996一、7(2分)】（分数：2.00）A.0123 √B.1 123C.1231D.1211解析：6.串‘ababaaababaa’的next数组为( )。

东莞理工学院（本科）试卷（A 卷）2006 -2007 学年第二学期开课单位：软件学院，考试形式：闭卷，允许带入场科目：数据结构与算法分析班级：姓名：学号：一、填空题（每小题2分，共18分）1、对于给定的n个元素,可以构造出的逻辑结构有集合, ，和四种。

2、数据结构中评价算法的两个重要指标是和。

3、数据类型指的是和定义在的总称。

4、顺序存储结构是通过表示数据元素之间的(逻辑)关系；链式存储结构是通过表示数据元素之间的(逻辑)关系。

5、栈是的线性表，其操作数据的基本原则是。

6、设有一个二维数组A[0…9][0…9]，若每个元素占3个基本存储单元，A[0][0]的地址是600，若按行优先（以行为主）顺序存储，则A[6][8]的存储地址是。

7、树的先序遍历实质上与将树转换成二叉树后对二叉树的相同；而树的后序遍历实质上与将树转换成二叉树后对二叉树的相同。

8、若采用邻接矩阵存储一个图所需要的存储单元取决于图的；无向图的邻接矩阵一定是。

9、对于一个有n个顶点的完全无向图，具有条边；而对于一个有n个顶点的完全有向图，具有条弧。

二、单项选择题（请将答案写在题目后的括号中。

每题2分，共18分）1、有算法sum(n)，其时间复杂度是（ A ）。

sum( int n ){ int sum=0, m, t ;for (m=1; m<=n; m++){ p=1 ;for (t=1; t<=m; t++) p*=t ;sum+=p ;}return (sum) ;}（A）O(n2) （B）O(m2) （C）O(m+n) （D）O(n×m)2、设p是非空单链表中结点q的直接前驱结点，删除q的正确操作是（ B ）。

（A）p->next=q->next；free(p) ; （B）p->next= q->next；free(q) ;（C）q->next=p->next；free(p) ; （D）q->next=p->next；free(q) ;3、设有一个栈顶指针为top的顺序栈S，top为0时表示栈空，则从S中取出一个元素保存在P中执行的操作是（ D ）。

计算机专业基础综合数据结构（概论）历年真题试卷汇编2(总分：88.00，做题时间：90分钟)一、单项选择题(总题数：11，分数：22.00)1.数据元素之间的关系称为( )。

【北京理工大学2006九、2(1分)】（分数：2.00）A.操作B.结构√C.数据对象D.数据集合解析：2.(多选)一个算法具有( )等特点。

【华中科技大学2007二、17(2分)】（分数：2.00）A.有0个或多个输入量B.健壮性√C.正确性D.可行性解析：3.下面程序的时间复杂性为( )。

【南京理工大学2004一、4(1分)】for(int i=0；i（分数：2.00）A.O(n 2 )B.O(m*n) √C.O(m 2 )D.O(m+n)解析：4.在下列算法中，“x=x*2”的执行次数是( )。

【华中科技大学2006一、16(2分)】int suanfa]．(int n){int i，j，x=1;for(i=0；i（分数：2.00）A.m(n+1)／2 √B.Nlog 2 nC.n 2D.n(n一1)／2解析：5.执行下列算法suanfa2(1000)，输出结果是( )。

【华中科技大学2006一、17(2分)】void suanfa2(int n){int i=i;while(i<=n)i*=2；printf(“％d”，i);}（分数：2.00）A.2000B.512C.1024 √D.2 1000解析：6.当n足够大时下述函数中渐近时间最小的是( )。

【哈尔滨工业大学2005二、4(1分)】（分数：2.00）A.T(n)=nlog 2 n=1000log 2 nB.T(n)=nlog 2 3=1 000log 2 n √C.T(n)=n 2 =1000log 2 nD.T(n)=2nlog 2 n=1 000log 2 n解析：7.下面算法时间复杂度是( )。

【华中科技大学2006一、18(2分)】int suanfa3(int n){int i=i，s=l；while(s（分数：2.00）A.O(n) √B.O(2 2 )C.O(log 2 n)解析：8.下列函数中渐进时间复杂度最小的是( )。

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、在下述结论中，正确的有（）。