天津理工大学2011年全日制工程硕士研究生入学考试大纲
一、考试科目：数据结构与C++程序设计（834）
二、考试方式：
考试采用笔试形式，考试时间为180分钟，试卷满分为150分。
三、试卷结构与分数比重：
题型包括填空题（20%）、选择题（20%）、算法或数据结构的设计与分析题（30%）、程序分析题（15%）与编程题（15%）等。
四、考查的知识范围：
《数据结构与C++程序设计》入学考试包括两部分内容：其中数据结构考试主要涉及线性结构、树、图、查找表和排序，占75分；C++程序设计考试主要涉及支持面向对象程序设计的内容，同时兼顾C++支持结构化程序设计的特征，占75分。本试卷总共150分，具体考试内容主要包括：
数据结构部分
一、绪论（5%）
1．数据结构相关基本概念
2．逻辑结构和物理结构
3．算法效率的度量（O－表示法）
二、线性表、栈和队列（25%）（以下各点要求掌握算法的程序实现）
1．顺序表的表示和基本操作的实现算法
2．线性链表、循环链表、双向链表的表示和和基本操作的实现算法
3．栈的表示和和基本操作的实现算法
4．循环队列、链队列的表示和和基本操作的实现算法
三、数组、递归（10%）
1．数组的存储方式
2．特殊矩阵的压缩存储
3．递归思想的特点
4．递归算法和递归函数
四、树和二叉树（15%）
1．树的定义和基本术语
2．二叉树的定义、性质，二叉链表存储结构
3．完全二叉树的性质
4．二叉树的深度优先（先序、中序、后序）和广度优先（层序）遍历算法和程序实现
5．树的孩子－兄弟二叉链表存储结构
6．树、森林与二叉树的转换
7．霍夫曼树的定义、性质
五、图（10%）
1．图的定义和术语
2．图的邻接矩阵、邻接表存储结构
3．图的深度优先搜索、广度优先搜索及其算法实现
4．生成树的定义
5．拓扑排序
六、查找（25%）
1．平均搜索长度（ASL）的定义
2．顺序表的查找算法、程序实现和ASL分析
3．二分查找法的算法描述、程序实现和ASL分析
4．二叉排序树的定义，插入、删除操作
5．平衡二叉树的定义，建立过程（掌握4种旋转方法），计算等概率下查找成功的ASL和查找不成功的ASL
6．索引顺序表的查找
7．B树的定义，插入、删除操作
8．散列表的概念，散列函数的构造方法
9．散列表处理冲突的方法（线性探查法、二次探查法、再散列法、链地址法），计算等概率下查找成功的ASL和查找不成功的ASL
10．散列表负载因子（装填因子）α的定义
七、排序（10%）（以下每种排序算法要求掌握排序过程和程序实现）
1．直接插入排序、希尔排序
2．冒泡排序、快速排序
3．简单选择排序、堆排序
4．归并排序
5．以上各种排序算法的时间复杂度分析，各自的特征及其比较
C++程序设计部分
一、C++基础语法（15%）
1．C++的字符集与词法规则
2．常见的数据类型
3．变量与常量
4．运算符的优先级和结合性
5．表达式的类型与计算顺序
6．语句：包括操作运算语句和流程控制语句
7．C++中的编译预处理
二、函数、指针、结构与联合（15%）
1．函数定义/说明的格式
2．函数的参数和返回值
3．函数的调用机制
4．函数的参数传递方式
5．重载函数以及函数重载的原则
6．标识符的作用域与变量的存储类别
7．指针、引用与数组的概念和应用
三、类的封装性（20%）
1．类的定义
2．构造函数与析构函数
3．隐含的this指针
4．类的静态成员
5．类的友元
6．指向类成员的指针
7．复杂对象与成分对象
8．类的常量成员
四、类的继承性（15%）
1．基类与派生类
单继承与多继承
继承方式：public protected private
2．访问特征
派生类成员函数对基类成员的访问
派生类对象对基类成员的访问
派生类的派生类对基类成员的访问
3．虚拟继承（共享继承）
多继承时的二义性
虚基类：在派生类对象中只有一份拷贝
4．构造函数和析构函数的调用顺序
Con：虚基类－非虚基类－成员对象类－派生类
Des：以构造函数相反的顺序
五、多态性（15%）
1．多态性的概念
2．多态性的分类
编译时的多态性：采用静态联编
运行时的多态性：采用动态联编
3．静态联编：概念与常见形式
4．运算符重载：“四不变”原则，另外只能重载已有的运算符，而不能创造新的运算符；即将c++已有的运算符扩展到用户自定义类的类型上。
①两种形式：成员函数与友元函数形式
②++ --的重载，分前缀和后缀两种形式
5．动态联编
虚函数的概念与应用
六、模板与I/O流类（20%）：
1．模板引入的必要性
函数模板
类模板
2．C++ I/O流类库
标准I/O
文件I/O
字符串I/O
题目： 学院： 专业班级： 学生姓名： 指导教师： 2016 年06 月2 9日
目录 一、课程设计目的 (3) 二、课程设计步骤 (3) 三、课程设计内容 (4) 四、课程设计报告 (6) 五、提交材料 (6) 六、考核方式与评分标准 (7) 七、参考文献 (8) 附录1 齐齐哈尔大学软件工程系课程设计说明书（报告）撰写规范 (9)
一、课程设计目的及要求 《数据结构与算法分析》课程设计培养计算机专业的学生的算法程序设计能力。通过上机实验，可以培养学生程序设计的方法和技巧，提高学生编制清晰、合理、可读性好的系统程序的能力，加深对数据结构课程和算法的理解。使学生更好地掌握数据结构的基本概念、基本原理、及基本算法,具有分析算法、设计算法、构造和开发较复杂算法的基本能力。 要求学生能综合运用《数据结构与算法分析》的相关知识，培养学生上机解决一些与实际应用结合紧密的、规模较大的问题的能力，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握数据结构和算法设计技术，掌握分析实际问题的能力并提高C语言编程技巧，培养良好的编程风格。 课程设计要求独立完成，题目自选（参考题目见三，也可自拟）,但需要老师确认(6月16日前定题)，一人一题，要求程序有能采用交互式工作方式的界面进行功能的选择,只能用文件存储数据和处理数据不能使用数据库。要求在教学周的第18周前完成。 二、课程设计步骤 随着计算机性能的提高，它所面临的软件开发的复杂度也日趋增加。然而，编制一个10000行的程序的难度绝不仅仅是一个5000行的程序的两倍，因此软件开发需要系统的方法。一种常用的软件开发方法，是将软件开发过程分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的课程设计的复杂度远不如(从实际问题中提出来的)一个“真正的”软件，但为了培养一个软件工作者所应具备的科学工作的方法和作风，完成课程设计的应有如下的5个步骤： 1.问题分析和任务定义 通常，课程设计题目的陈述比较简洁，或者说是有模棱两可的含义。因此，在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么，限制条件是什么。注意：本步骤强调的是做什么，而不是怎么做。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如：输入数据的类型、值的范围以及输入的形式；输出数据的类型、值的范围及输出的形式；若是会话式的输入，则结束标志是什么，是否接受非法的输入，对非法输入的回答方式是什么等等。这一步还应该为调试程序准备好测试数据，包括合法的输入数据和非法形式输入的数据。 2.数据类型和系统设计 在设计这一步骤中需分逻辑设计和详细设计两步实现。逻辑设计指的是，对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型；详细设计则为定义相应的存储结构并写出各过程和函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。作为逻辑设计的结果，应写出每个
天津大学数据结构和程序设计考研真题-考研资料- 笔记讲义 许多学生在考研复习的时候,都会遇到重点不明确,不知道从何复习的情况。为此,天津考研网建议,考研复习中,专业的考研复习资料,是帮助考生能够快速掌握复习重点及方法必不可少的因素,然后就是真题和讲义,可以让同学了解历年考研的出题方向和大致范围。天津考研网推出了天津大学数据结构和程序设计的考研复习资料及真题解析班,以下为详细介绍: 天津大学数据结构和程序设计考研真题等资料由天津考研网签约的天津大学计算机科学与技术学院高分考研学生历时近一月所作,该考生在考研中取得了专业课129分的好成绩并在复试中更胜一筹,该资料包含该优秀本校考生的考研经验、考研试题解题思路分析、复试流程经验介绍以及针对官方指定参考书的重难要点并根据天津大学本科授课重点整理等,从漫漫初试长路到紧张复试亮剑为各位研友提供全程考研指导攻关。 特别说明:此科目06年以前科目名称为数据结构;自06年到08年科目名称改为计算机基础(包含数据结构、程序设计、计算机原理);自09年开始全国统考,科目名称为计算机学科专业基础综合;自2013年开始由学校自主命题,科目名称改为901数据结构与程序设计。 第一部分由天津考研网提供的核心复习资料: 天津大学数据结构和程序设计资料编者序言:本文的重点在于C++,数据结构的复习和复试基本情况介绍。C++、数据结构又分别从复习规划,复习用书,重点知识点结合历年考题这四个方面来展开的。复习规划大家务必看一下,然后根据自己的实际情况在制定自己的复习时间,因为内容很多,大多数同学都在考试之前复习不完,在心理因素上就落了一节。重点知识点一定要看了,这些知识点几乎每年都会有题了。另外我还给了历年试题的答案供大家参考。有的答案是自己做的答案,可能会有疏忽的地方。望大家提出宝贵的意见和建议。复试的东西现在了解一下即可,等到进复试了,还是有足够的时间看的。另外我还给了些自己复习心得。考完后感慨很多,回顾了这多半年来自己的成败得失。希望大家从一开始就沿着比较高效的方向前进,减少不必要时间的浪费。本资料格式为A4纸打印版,总量达到了130页
北京航空航天大学程序设计与数据结构试题 (2001年) 一、问答题(10’) 一般情况下，线性表可以采用哪几种存储结构？请分别叙述每一种存储结构的构造原理与特点。 二、(10’) 已知AOE网为G=(V，E)，其中V={v1，v2，v3，v4，v5，v6，v7，v8，v9，v10}，E={a1， a2，a3，a4，a5，a6，a7，a8，a9，a10，a11，a12，a13，a14}，其中： a1:(v1，v2)5a2:(v1，v3)6a3:(v2，v5)3a4:(v3，v4)3 a5:(v3，v5)6a6:(v4，v5)3a7:(v4，v7)1a8:(v4，v8)4 a9:(v5，v6)4a10:(v5，v7)2a11(v6，v10)4a12:(v7，v9)5 a13:(v8，v9)2a14:(v9，v10)2 注：顶点偶对右下角的数字表示边上的权值。 请按下述过程指出所有关键路径： ee[1:10]: le[1:10]: e[1:14]: l[1:14]: 其中，ee[i]与le[i]分别表示事件v i的最早发生时间与最晚发生时间；e[i]与l[i]分别表示活动a i的最早开始时间与最晚开始时间。 三、(10’) 欲建立一文献库，其正文(文献本身)存放在一个双向循环链表的各个链接点中。 1.为便于链接点的插入、删除操作，以及按题目、发表日期、发表者名称、主题词(假设每文最多给出三个主题词)进行检索，请设计该链表的链接点结构(给出链接点每个域的名称，并说明该域内存放什么信息。注：以下各小题设计链结点结构也这样要求)。画出整个链表结构的示意图。 2.设计一个三级索引结构，其中第三级索引称为题目索引，示按文献题目构造的稠密索引，通过该级索引并根据给定题目可得到每个文献的存放地址；该级索引按文献学科类分类存放。第二级索引称为中类索引，是题目索引的索引，指出同一中类的文献题目索引的存放位置(例如农林类、气象类……，古代史类，近代史类……)。第一级索引称为大类索引，指出同一大类(如：自然科学类、历史类……)的文献的中类索引的存放位置。请设计每一级索引的结点结构，并画出该索引的整体示意图。 3.在设计一种三级索引结构，其中第三级索引仍是题目索引(与2题所述相同)，第二级索引把具有相同主题词的文献题目索引地址组织在一个单链表中。第一级索引称为主题词索引，用文献给出的主题词做关键字组成杂凑表，即该级索引为一个杂凑表，能够指出具有同一主题词的文献题目索引的索引链表的第一个链结点的存储位置。该杂凑表采用链地址法处理冲突。请设计每一级索引的结点结构，并画出该索引的整体示意图。 四、(10’) 已知非空线性链表由list 五、(5’+10’) 已知求两个正整数m与n的最大公因子的过程用自然语言可以表述为反复执行如下动作：
Programming Principles 1 1.2 THE GAME OF LIFE Exercises 1.2 Determine by hand calculation what will happen to each of the configurations shown in Figure 1.1 over the course of five generations. [Suggestion: Set up the Life configuration on a checkerboard. Use one color of checkers for living cells in the current generation and a second color to mark those that will be born or die in the next generation.] Answer (a) Figure remains stable. (b) (c) (d) Figure is stable. 1 2 Chapter 1 _ Programming Principles (e) (f) Figure repeats itself. (g) (h) (i) Figure repeats itself. (j) (k) (l) Figure repeats itself. Section 1.3 _ Programming Style 3 1.3 PROGRAMMING STYLE Exercises 1.3
E1. What classes would you define in implementing the following projects? What methods would your classes possess? (a) A program to store telephone numbers. Answer The program could use classes called Phone_book and Person. The methods for a Phone_book object would include look_up_name, add_person, remove_person. The methods for a Person object would include Look_up_number. Additional methods to initialize and print objects of both classes would also be useful. (b) A program to play Monopoly. Answer The program could use classes called Game_board, Property, Bank, Player, and Dice. In addition to initialization and printing methods for all classes, the following methods would be useful. The class Game_board needs methods next_card and operate_jail. The class Property needs methods change_owner, look_up_owner, rent, build, mortgage, and unmortgage. The class Bank needs methods pay and collect. The class Player needs methods roll_dice, move_location, buy_property and pay_rent. The class Dice needs a method roll. (c) A program to play tic-tac-toe. Answer The program could use classes called Game_board and Square. The classes need initialization and printing methods. The class Game_board would also need methods make_move and is_game_over. The class Square would need methods is_occupied, occupied_by, and occupy. (d) A program to model the build up of queues of cars waiting at a busy intersection with a traffic light. Answer The program could use classes Car, Traffic_light, and Queue. The classes would all need initialization and printing methods. The class Traffic_light would need additional methods change_status and status. The class Queue would need additional methods add_car and remove_car. E2. Rewrite the following class definition, which is supposed to model a deck of playing cards, so that it conforms to our principles of style. class a { // a deck of cards int X; thing Y1[52]; /* X is the location of the top card in the deck. Y1 lists the cards. */ public: a( ); void Shuffle( ); // Shuffle randomly arranges the cards. thing d( ); // deals the top card off the deck } ; Answer class Card_deck { Card deck[52]; int top_card; public: Card_deck( ); void Shuffle( ); Card deal( );
目录 题目1：设计一元多项式简单计算.................................. 错误!未定义书签。题目2：链表应用1 ....................................................... 错误!未定义书签。题目3：链表应用2 .......................... 错误!未定义书签。题目4：?通讯录 ............................ 错误!未定义书签。题目5：停车场管理系统....................... 错误!未定义书签。题目6：约瑟夫环............................ 错误!未定义书签。题目7：运动会分数统计....................... 错误!未定义书签。题目8：文学研究助手问题..................... 错误!未定义书签。题目9：银行业务模拟与离散事件模拟 ............ 错误!未定义书签。题目10：学生信息管理系统任务（用顺序表/链表）.. 错误!未定义书签。题目11：文章编辑功能 ....................... 错误!未定义书签。题目12：实验室管理......................... 错误!未定义书签。题目13：二叉树的基本操作（建立、求二叉树树深度、遍历）.错误!未定义 书签。 题目14：纸牌游戏任务 ....................... 错误!未定义书签。题目15：算术表达式求值...................... 错误!未定义书签。题目16：内部排序算法比较.................... 错误!未定义书签。题目17：哈夫曼树的构造和哈夫曼编码/译码 ....... 错误!未定义书签。题目18：构造可以使n个城市连接的最小生成树..... 错误!未定义书签。题目19：交通咨询系统中的最短路径............. 错误!未定义书签。题目20：集合的交、并、差运算................. 错误!未定义书签。题目21：长整数四则运算...................... 错误!未定义书签。题目22：机订票系统......................... 错误!未定义书签。题目23：图书管理系统 ....................... 错误!未定义书签。题目24：哈希表应用......................... 错误!未定义书签。题目25：模拟旅馆管理系统的一个功能——床位的分配与回收.错误!未定义 书签。 题目26：地图着色问题 ....................... 错误!未定义书签。题目27：俄罗斯套娃问题...................... 错误!未定义书签。题目28：扫雷.............................. 错误!未定义书签。题目29：用C语言设计一个日历系统............. 错误!未定义书签。
<<数据结构>> 课 程 设 计 班级:111004 姓名:董丽美 学号:111004122 指导教师:史延新 完成日期:2013 _07 _10
题目一:约瑟夫环问题 【问题描述】约瑟夫（Joseph）问题的一种描述是：编号为1,2，…,n 的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m 的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出列顺序。【基本要求】利用单向循环链表存储结构模拟此过程，按照出列的顺序打印出各人的编号。 【测试数据】m的初值为20；n=7,7个人的密码依次为：3,1,7,2，4,8,4，首先m值为6（正确的出列顺序应为：6,1,4,7,2,3,5） 一 .需求分析 1．用单循环链表存储并遍历及删除节点的方法，计算并输出约瑟夫环的问题。 2．环中总人数和节点信息由用户输入，且均为正整数。3．在窗口界面输出出列顺序的编号。 二．概要设计
1.设定链表的抽象数据类型定义： ADT List{ 数据对象：D={a(i)|a(i)∝Elemset,i=1,2,…,n,n>=0} 数据关系：R1={
湖南师范大学硕士研究生入学考试自命题考试大纲 考试科目代码：[967] 考试科目名称：C语言程序设计和数据结构 一、试卷结构 1) 试卷成绩及考试时间 本试卷满分为150分，考试时间为180分钟。 2)答题方式：闭卷、笔试 3)试卷内容结构 C语言程序设计部分 80% 数据结构部分 20% 4)题型结构 a: 单项选择题，共40分 b: 程序填空题，共30分 c: 程序阅读题，共25分 d: 编程题，共45分 e: 分析题，共10分 二、考试内容与考试要求 （一）C语言程序设计部分 考试内容 1、基本知识 （1）C语言的数据类型 （2）C语言中各种类型常量的表示法 （3）各类数值型数据间的混合运算 （4）C运算符 （5）关系表达式及运算，逻辑表达式及运算
2、顺序、选择与循环结构 （1）赋值语句，格式输入与输出 （2）if语句，switch语句 （3）goto、while、do-while、for、break、continue语句3、数组 （1）一维数组的定义和引用 （2）二维数组的定义和引用 （3）字符数组的定义和引用，字符串及其处理函数 4、函数 （1）函数定义与调用 （2）局部变量和全局变量 （3）变量的存储类型 （4）内部函数与外部函数 5、宏定义 （1）带参数的宏定义 （2）包含文件的处理 6、指针 （1）地址和指针的概念 （2）数组的指针和指向数组的指针变量 （3）字符串的指针和指向字符串的指针变量 （4）函数的指针和指向函数的指针变量 （5）指针数组和指向指针的数组 7、结构体和共同体 （1）结构体变量的定义和使用方法 （2）指向结构体类型变量的指针 （3）用指针处理链表 （4）共同体变量的定义和使用方法
数据结构课程设计题目 1.飞机订票系统（限1 人完成）（顺序或链式存储） 任务：通过此系统可以实现如下功能： 录入： 可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定） 查询： 可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）； 可以输入起飞抵达城市，查询飞机航班情况； 订票：（订票情况可以存在一个数据文件中，结构自己设定） 可以订票，如果该航班已经无票，可以提供相关可选择航班； 退票：可退票，退票后修改相关数据文件； 客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。 修改航班信息： 当航班信息改变可以修改航班数据文件 要求： 根据以上功能说明，设计航班信息，订票信息，客户信息的存储结构，设计程序完成功能； 2.宿舍管理查询软件（限1 人完成） 任务：为宿舍管理人员编写一个宿舍管理查询软件, 程序设计要求： 采用交互工作方式 建立数据文件，包括学生信息、宿舍信息、住宿信息，学生信息按关键字（姓名、学号）进行排序(排序方法自选，不能相同)； 查询: (用二分查找实现以下操作) 按姓名查询 按学号查询 (用顺序查找实现以下操作) 按房号查询 3.校园导航问题（限1 人完成） 设计要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。 要求：能增加场所 4.图书借阅管理系统（限1 人完成）（顺序或链式存储） 主要分为两大功能： 1)图书管理(增加图书、查询图书、删除图书、图书借阅、还书)； 2)会员管理(增加会员、查询会员、删除会员、借书信息)； 5.学生成绩管理（限1 人完成）（顺序或链式存储） 包括：课程信息，学生信息等；能增加课程或学生。 实现功能：输入、输出、插入、删除、查找、显示、保存、排序、退出。6.活期储蓄帐目管理（限1 人完成） 活期储蓄处理中，储户开户、销户、存入、支出活动频繁，系统设计要求： 1)能比较迅速地找到储户的帐户，以实现存款、取款记账；
《数据结构与C语言程序设计》复习大纲 《数据结构与C语言程序设计》包括“数据结构”与“C语言程序设计”两门课程的内容，各占比例50%。 《数据结构》部分 指定参考书： 《数据结构教程（第二版）》唐发根编著，北京航空航天大学出版社，2005 一、概述 1．简要了解数据的逻辑结构与存储结构的基本概念； 2．了解算法的定义、算法的五个基本性质以及算法分析最基本的概念，包括算法分析的前提、目的。 二、线性表 1．了解线性关系、线性表的定义，线性表的基本操作； 2．线性表的顺序存储结构与链式存储结构(包括单链表、循环链表和双向链表)的构造原理； 3．掌握在以上两种存储结构的基础上对线性表实施的基本操作，重点包括顺序表的插入和删除、链表的建立、插入和删除、检索等操作对应的过程和算法的设计。 三、堆栈与队列 1．了解堆栈与队列(不含循环队列)的基本概念、基本操作； 2．掌握堆栈与队列的顺序存储结构与链式存储结构的构造原理； 3．掌握在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作过程。
四、树与二叉树 1．了解树型结构的基本概念，基本特征、名词术语； 2．了解完全二叉树、满二叉树的概念；二叉树的基本性质（至少要记住结论）； 3．了解二叉树的顺序存储结构与二叉链表存储结构的构造原理及特点，重点是二叉链表存储结构； 4．掌握二叉树的前序遍历、中序遍历、后序遍历和按层次遍历算法(非递归算法)以及利用遍历解决有关二叉树的其它操作； 5．掌握二叉排序树的基本概念、建立(插入)和查找。 五、图 1．了解图结构的基本概念、基本名词术语； 2．掌握图的邻接矩阵存储方法和邻接表存储方法的基本构造原理与特点； 3．图的深度优先搜索和广度优先搜索的基本过程，遍历的基本作用； 4．最小生成树的求解过程，拓扑排序及其目的。 六、文件及查找 1．掌握顺序查找法、折半查找法的查找过程，了解折半查找方法的基本要求； 2．了解散列(Hash)文件的基本特点，散列函数和散列冲突的概念，处理散列冲突的方法。 七、内排序 了解插入排序法、选择排序法、泡排序法、快速排序法以及堆积排序(大顶堆积)法等排序方法的排序原理、规律和特点。 《C语言程序设计》部分 指定参考书： 《C程序设计》（第三版）谭浩强著，清华大学出版社, 2005.7
《数据结构》 Part1 一．选择 1. 组成数据的基本单位是（） A）数据项B）数据类型C）数据元素D）数据变量 2．算法分析的目的是（） A）找出数据结构的合理性B）研究算法的输入/输出关系 C）分析算法的效率以求改进D）分析算法的易读性 3．在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）A）O(1) B）0(n) C）O(n^2) D）O(nlog2n) 4．若线性表采用顺序存储结构，每个元素占用4个存储单元，第一个元素的存储地址为100，则第12个元素的存储地址是（） A）112 B）144 C）148 D）412 5．下面关于线性表的叙述中，错误的是（） A）顺序表使用一维数组实现的线性表B）顺序表必须占用一片连续的存储单元. C）顺序表的空间利用率高于链表D）在单链表中,每个结点只有一个链域. 6．在需要经常查找结点的前驱与后继的情况下，使用（）比较合适 A）单链表B）双链表C）顺序表D）循环链表 7．队列通常采用的两种存储结构是（） A）顺序存储结构和链式存储结构B）散列方式和索引方式 C）链表存储结构和线性存储结构D）线性存储结构和非线性存储结构 8．在一个单链表中，若删除p所指结点的后继结点，则执行（） A）p->next=p->next->next；B）p=p->next；p->nex=p->next->next； C）p->next=p->next；D）p=p->next->next； 9．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间 A）单链表B）仅有头指针的单循环链表C）双链表D）仅有尾指针的单循环链表 10．按二叉树的定义，具有三个结点的二元树共有（）种形态。 A）3 B）4 C）5 D）6 11．任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）A）发生改变B）不发生改变C）不能确定D）以上都不对12．深度为5的二叉树至多有（）个结点 A）16 B）32 C）31 D）10 13．在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，那么度为0的结点数为（）个。 A）4 B）5 C）6 D）7 14．对于一个具有n个顶点的无向图，若采用邻接表表示，则存放表头结点的数组(顶点表)的大小为（） A）n B）n+1 C）n-1 D）n/2 15．静态查找表和动态查找表二者的根本差别在于（）
814程序设计与数据结构考试大纲 085211计算机技术专业 一、考试目的 本考试是全日制计算机技术专业学位研究生的入学资格考试之专业基础课，各语种考生统一用汉语答题。各招生院校根据考生参加本考试的成绩和其他三门考试的成绩总分来选择参加第二轮，即复试的考生。 二、考试的性质与范围 本考试是测试考生计算机科学基础知识的水平考试。考试范围包括本大纲规定的C++语言程序设计和数据结构。 三、考试基本要求 1. 具备扎实的C++语言程序设计基本功。 2. 具备设计数据结构和算法求解问题的基本能力。 四、考试形式 本考试采取客观试题与主观试题相结合，单项技能测试与综合技能测试相结合的方法，强调考生设计数据结构和算法并编程实现来求解问题的能力。试题分类参见“考试内容一览表”。 五、考试内容 本考试包括两个部分：C++程序设计、数据结构。总分150分。 I. C++程序设计 1. 考试要求 该部分要求考生对C++语言基本特性、面向对象程序设计方法和Visual C++编译器相关特性有很好的了解。 2. 题型 选择题、读程序写出Visual C++下的执行结果、程序填空，共75分。 II. 数据结构 1. 考试要求 该部分要求考生掌握线性表（及其扩展：栈和FIFO队列）、树（包括基本的二叉树和堆、搜索树等特殊树结构）、图等基本数据结构及其上的操作；掌握二分搜索、Hash技术及搜索树等搜索方法；掌握选择、起泡、插入等简单排序算法，堆排序、快速排序、归并排序和谢尔（希尔）等快速排序算法，以及箱子、基数排序等非比较排序算法。具备利用上述数据结构和算法以及设计新数据结构和算法来求解问题的能力。 2. 题型 选择题、简答题、算法设计题，共75分。
目录 题目1：设计一元多项式简单计算 (1) 题目2：链表应用1 (1) 题目3：链表应用2 (1) 题目4：通讯录 (2) 题目5：停车场管理系统............................................. 错误！未定义书签。题目6：约瑟夫环 (3) 题目7：运动会分数统计 (3) 题目8：文学研究助手问题 (3) 题目9：银行业务模拟与离散事件模拟 (4) 题目10：学生信息管理系统任务（用顺序表/链表）.... 错误！未定义书签。题目11：文章编辑功能 .............................................. 错误！未定义书签。题目12：实验室管理.................................................. 错误！未定义书签。题目13：二叉树的基本操作（建立、求二叉树树深度、遍历）.. (4) 题目14：纸牌游戏任务 (5) 题目15：算术表达式求值 (5) 题目16：内部排序算法比较 (5) 题目17：哈夫曼树的构造和哈夫曼编码/译码 (6) 题目18：构造可以使n个城市连接的最小生成树 (7) 题目19：交通咨询系统中的最短路径 (7) 题目20：集合的交、并、差运算 ................................ 错误！未定义书签。题目21：长整数四则运算 (7) 题目22：机订票系统.................................................. 错误！未定义书签。题目23：图书管理系统 (8) 题目24：哈希表应用 (8) 题目25：模拟旅馆管理系统的一个功能——床位的分配与回收 (9) 题目26：地图着色问题 (9) 题目27：俄罗斯套娃问题 (10) 题目28：扫雷 (11) 题目29：用C语言设计一个日历系统 (11)
2013年“数据结构与C程序设计”(代码991)试题 一、单项选择题（本题共20分，每小题各2分） 1．对于长度为n的线性表，建立其对应的单链表的时间复杂度为( )。 A．O(1)；B．O(log2n)；．O(n)；D．O(n2)。 2．一般情况下，在一个双向链表中插入一个新的链结点，( )。 A．需要修改4个指针域内的指针；B．需要修改3个指针域内的指针； C．需要修改2个指针域内的指针；D．只需要修改1个指针域内的指针。 3．假设用单个字母表示中缀表达式中的一个运算数(或称运算对象)，并利用堆栈产生中缀表达式对应的后缀表达式。对于中缀表达式A+B*(C/D-E)，当从左至右扫描到运算数E时，堆栈中的运算符依次是( )。(注：不包含表达式的分界符) A．+*/-；B．+*(/-；C．+*-；．+*(-。 4．若某二叉排序树的前序遍历序列为50,20,40,30,80,60,70，则后序遍历序列为( )。 A．30,40,20,50,70,60,80；B．30,40,20,70,60,80,50； C．70,60,80,50,30,40,20；D．70,60,80,30,40,20,50。 5．分别以6, 3, 8, 12, 5, 7对应叶结点的权值构造的哈夫曼(Huffman) 树的深度为( )。 A．6；B．5；C．4；D．3。 6．下列关于图的叙述中，错误的是( )。 A．根据图的定义，图中至少有一个顶点； B．根据图的定义，图中至少有一个顶点和一条边(弧)； C．具有n个顶点的无向图最多有n(n-1)/2条边； D．具有n个顶点的有向图最多有n(n-1)条边(弧)。 7．若在有向图G的拓扑序列中，顶点vi在顶点vj之前，则下列4种情形中不可能出现的是( )。 A．G中有弧
上海应用技术学院课程设计报告 课程名称《数据结构课程设计》 设计题目猴子选大王；建立二叉树；各种排序；有序表的合并；成绩管理系统；院系计算机科学与信息工程专业计算机科学与技术班级 姓名学号指导教师日期 一.目的与要求 1. 巩固和加深对常见数据结构的理解和掌握 2. 掌握基于数据结构进行算法设计的基本方法 3. 掌握用高级语言实现算法的基本技能 4. 掌握书写程序设计说明文档的能力 5. 提高运用数据结构知识及高级语言解决非数值实际问题的能力 二.课程设计内容说明 1. 项目一 (1) 对设计任务内容的概述 学生成绩管理** 任务：要求实现对学生资料的录入、浏览、插入和删除等功能。 输入：设学生成绩以记录形式存储，每个学生记录包含的信息有：学号和各门课程的成绩，设学生成绩至少3门以上。存储结构：采用线性链式结构。 (2) 详细设计 LinkList *create()：输入学生成绩记录函数； void print(LinkList *head)：显示全部记录函数 LinkList *Delete(LinkList *head)：删除记录函数 LinkList *Insert(LinkList *head)：插入记录函数 void menu_select()：菜单选择 void ScoreManage()：函数界面
(3) 程序流程图 (4) 程序模块及其接口描述 该程序可以分为以下几个模块： 1、菜单选择：void menu_select(); 提供五种可以选择的操作，在main函数中通过switch语句调用菜单menu_select()函数，进入不同的功能函数中完成相关操作。
数据结构与及程序设计专题 实验报告 一．实验任务： 对于给定的源文档 SourceDoc.txt， 1) 统计其中所有字符的频度（某字符的频度等于其出现的总次数除以总字符数），字符包括字母（区分大小写）、标点符号及格式控制符（空格、回车等）。 2) 按频度统计结果构建哈夫曼编码表。 3) 基于哈夫曼编码表进行编码，生成对应的二进制码流，并输出到文件 Encode.dat，完成信源的编码过程。 4) 根据生成的哈夫曼编码表，对二进制码流文件Encode.dat 进行解码，把结果输出到文件 TargetDoc.txt，完成信源的解码过程。 5) 判断 TargetDoc.txt 与 SourceDoc.txt 内容是否 一致，以验证编解码系统的正确性。 二．实验内容: 1) 线性链表的构建以及排序; 2) 哈夫曼树的构建; 3) 基于哈夫曼码进行编码; 4) 对二进制码进行解码;
5）对生成文件与原文件进行比较；三．程序的算法描述
四．程序运行结果：
五．源程序代码： #include
{ NODE *h, *p, *s,*death; int i; h=(NODE*)malloc(sizeof(NODE));p=(NODE*)malloc(size of(NODE)); h->next=p;h->pre=NULL; p->pre=h;p->next=NULL; p->data=b[0]; p->count=1.0; for(i=1;b[i]!='\0';i++) {s=(NODE*)malloc(sizeof(NODE)); s->data=b[i]; s->count=1.0; s->next=NULL; s->pre=p; p->next=s; p=s; } return h; } void fun(NODE* h,int amount) { NODE *p,*q,*death; for(p=h->next;p;p=p->next){
程序设计部分 读程序，写结果 1.#include 4. #include
相关主题
文本预览