贵州大学硕士研究生入学考试大纲
EBR，叫做扩展MBR（Extended MBR），位于硬盘的某柱面0磁道1扇区 1.簇（cluster） 是DOS给文件系统分配磁盘空间的最小单位。由若干连续的逻辑扇区组成，不同的盘，簇的大小不同，簇是从2开始编号，见表6-1。 逻辑扇区号=（簇号-2）×扇区数/簇+数据区首扇区号 2.BOOT记录： 第一部分：0～2字节为跳转指令，转向启动码区。 第二部分：3～10字节为厂商标识字段，如MSDOS5.0。 第三部分：11～61字节为磁盘参数表（51字节）。 第四部分：62～509字节为启动程序（438字节）。 最后：55,AA字节。 51字节BPB表（BIOS Parameter Block） OB－OC：每扇区字节数(512) OD：扇区数/簇 0E－0F：保留扇区（指Boot区） 10：FAT个数 11－12：根目录最大登记项数 13－14：本分区扇区总数（小于32M的分区，大于32MB时,为0） 15：介质描述符 16－17：每个FAT扇区数 18－19：每道扇区数 1A－1B：磁头数 1C－1F：本分区前的扇区数（隐含扇区，即从0（X）柱0头1扇到0（X）柱1头1扇之间的扇区，由于不能为DOS访问，故称为隐含扇区）。 20－23：大容量盘总扇区数。 24：BIOS设备号（hex：HD=8x） 25：未使用 26：扩展引导标记（29H） 27-2A：卷序列号（随机） 2B-35：卷标，分区标识，如：WIN98 36-3D：文件系统格式（FAT16） 3.FAT（文件配置表） FAT有两个，当第一个损坏时，为人工修复提供方便，DOS不会自动用第二个去修复第一个FAT，而DOS实际上没有用尽2个FAT占用的扇区，因为可作为他用。FAT登记盘上簇的使用情况，登记项有12位、16位和32位之分，下面以16位为例说明FAT的格式。 16位FAT格式： 簇号（表项） 0000H 0001H 0002H … NNNNH 类型保留簇使用簇 含义介质标志记录文件簇号链
题目： 学院： 专业班级： 学生姓名： 指导教师： 2016 年06 月2 9日
目录 一、课程设计目的 (3) 二、课程设计步骤 (3) 三、课程设计内容 (4) 四、课程设计报告 (6) 五、提交材料 (6) 六、考核方式与评分标准 (7) 七、参考文献 (8) 附录1 齐齐哈尔大学软件工程系课程设计说明书（报告）撰写规范 (9)
一、课程设计目的及要求 《数据结构与算法分析》课程设计培养计算机专业的学生的算法程序设计能力。通过上机实验，可以培养学生程序设计的方法和技巧，提高学生编制清晰、合理、可读性好的系统程序的能力，加深对数据结构课程和算法的理解。使学生更好地掌握数据结构的基本概念、基本原理、及基本算法,具有分析算法、设计算法、构造和开发较复杂算法的基本能力。 要求学生能综合运用《数据结构与算法分析》的相关知识，培养学生上机解决一些与实际应用结合紧密的、规模较大的问题的能力，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握数据结构和算法设计技术，掌握分析实际问题的能力并提高C语言编程技巧，培养良好的编程风格。 课程设计要求独立完成，题目自选（参考题目见三，也可自拟）,但需要老师确认(6月16日前定题)，一人一题，要求程序有能采用交互式工作方式的界面进行功能的选择,只能用文件存储数据和处理数据不能使用数据库。要求在教学周的第18周前完成。 二、课程设计步骤 随着计算机性能的提高，它所面临的软件开发的复杂度也日趋增加。然而，编制一个10000行的程序的难度绝不仅仅是一个5000行的程序的两倍，因此软件开发需要系统的方法。一种常用的软件开发方法，是将软件开发过程分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的课程设计的复杂度远不如(从实际问题中提出来的)一个“真正的”软件，但为了培养一个软件工作者所应具备的科学工作的方法和作风，完成课程设计的应有如下的5个步骤： 1.问题分析和任务定义 通常，课程设计题目的陈述比较简洁，或者说是有模棱两可的含义。因此，在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么，限制条件是什么。注意：本步骤强调的是做什么，而不是怎么做。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如：输入数据的类型、值的范围以及输入的形式；输出数据的类型、值的范围及输出的形式；若是会话式的输入，则结束标志是什么，是否接受非法的输入，对非法输入的回答方式是什么等等。这一步还应该为调试程序准备好测试数据，包括合法的输入数据和非法形式输入的数据。 2.数据类型和系统设计 在设计这一步骤中需分逻辑设计和详细设计两步实现。逻辑设计指的是，对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型；详细设计则为定义相应的存储结构并写出各过程和函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。作为逻辑设计的结果，应写出每个
习题5参考答案 5.1 选择 （1）C（2）B（3）C（4）B（5）C（6）D（7）C（8）C（9）B（10）C （11）B（12）C（13）C（14）C（15）C（16）B 5.2 填空 （1）1 （2）1036；1040 （3）2i （4） 1 ； n ; n-1 ; 2 （5）2k-1；2k-1 （6）ACDBGJKIHFE （7）p->lchild==NULLL （8）Huffman树 （9）其第一个孩子; 下一个兄弟 （10）先序遍历；中序遍历 5.3 叶子结点:C、F、G、L、I、M、K； 非终端结点：A、B、D、E、J； 各结点的度： 结点： A B C D E F G L I J K M 度： 4 3 0 1 2 0 0 0 0 1 0 0 树深：4 5.4 无序树形态如下： 二叉树形态如下：
5.5 二叉链表如下: 三叉链表如下: 5.6 先序遍历序列:ABDEHICFJG
中序遍历序列:DBHEIAFJCG 后序遍历序列:DHIEBJFGCA 5.7 (1) 先序序列和中序序列相同：空树或缺左子树的单支树； (2) 后序序列和中序序列相同：空树或缺右子树的单支树； (3) 先序序列和后序序列相同：空树或只有根结点的二叉树。 5.8 这棵二叉树为: 5.9 先根遍历序列:ABFGLCDIEJMK 后根遍历序列:FGLBCIDMJKEA 层次遍历序列:ABCDEFGLIJKM 5.10 证明：设树中结点总数为n，叶子结点数为n0，则 n=n0 + n1 + …… + n m （1） 再设树中分支数目为B，则 B=n1 + 2n2 + 3n3+ …… + m n m （2） 因为除根结点外，每个结点均对应一个进入它的分支，所以有 n= B + 1 （3） 将（1）和（2）代入（3），得 n0 + n1 + …… + n m = n1 + 2n2 + 3n3+ …… + m n m + 1 从而可得叶子结点数为： n0 = n2 + 2n3+ …… + (m-1)n m + 1 5.11 由5.10结论得，n0 = (k-1)n k + 1 又由 n=n0 + n k，得n k= n-n0，代入上式，得 n0 = (k-1)（n-n0）+ 1 叶子结点数为：n0 = n (k-1) / k
天津大学数据结构和程序设计考研真题-考研资料- 笔记讲义 许多学生在考研复习的时候,都会遇到重点不明确,不知道从何复习的情况。为此,天津考研网建议,考研复习中,专业的考研复习资料,是帮助考生能够快速掌握复习重点及方法必不可少的因素,然后就是真题和讲义,可以让同学了解历年考研的出题方向和大致范围。天津考研网推出了天津大学数据结构和程序设计的考研复习资料及真题解析班,以下为详细介绍: 天津大学数据结构和程序设计考研真题等资料由天津考研网签约的天津大学计算机科学与技术学院高分考研学生历时近一月所作,该考生在考研中取得了专业课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的最大公因子的过程用自然语言可以表述为反复执行如下动作：
附录习题参考答案 习题1参考答案 1.1.选择题 (1). A. (2). A. (3). A. (4). B.,C. (5). A. (6). A. (7). C. (8). A. (9). B. (10.) A. 1.2.填空题 (1). 数据关系 (2). 逻辑结构物理结构 (3). 线性数据结构树型结构图结构 (4). 顺序存储链式存储索引存储散列表（Hash）存储 (5). 变量的取值范围操作的类别 (6). 数据元素间的逻辑关系数据元素存储方式或者数据元素的物理关系 (7). 关系网状结构树结构 (8). 空间复杂度和时间复杂度 (9). 空间时间 (10). Ο(n) 1.3 名词解释如下： 数据：数据是信息的载体，是计算机程序加工和处理的对象，包括数值数据和非数值数据。数据项：数据项指不可分割的、具有独立意义的最小数据单位，数据项有时也称为字段或域。数据元素：数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，一个数据元素可由若干个数据项组成。 数据逻辑结构：数据的逻辑结构就是指数据元素间的关系。 数据存储结构：数据的物理结构表示数据元素的存储方式或者数据元素的物理关系。 数据类型：是指变量的取值范围和所能够进行的操作的总和。 算法：是对特定问题求解步骤的一种描述，是指令的有限序列。 1.4 语句的时间复杂度为： (1) Ο(n2) (2) Ο(n2) (3) Ο(n2) (4) Ο(n-1) (5) Ο(n3) 1.5 参考程序： main() { int X,Y,Z； scanf(“%d, %d, %d”,&X,&Y,Z)； if (X>=Y) if(X>=Z) if (Y>=Z) { printf(“%d, %d, %d”,X,Y,Z);} else { printf(“%d, %d, %d”,X,Z,Y);}
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( );
<<数据结构>> 课 程 设 计 班级: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={
数据结构课程设计题目 1.飞机订票系统（限1 人完成）（顺序或链式存储） 任务：通过此系统可以实现如下功能： 录入： 可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定） 查询： 可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）； 可以输入起飞抵达城市，查询飞机航班情况； 订票：（订票情况可以存在一个数据文件中，结构自己设定） 可以订票，如果该航班已经无票，可以提供相关可选择航班； 退票：可退票，退票后修改相关数据文件； 客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。 修改航班信息： 当航班信息改变可以修改航班数据文件 要求： 根据以上功能说明，设计航班信息，订票信息，客户信息的存储结构，设计程序完成功能； 2.宿舍管理查询软件（限1 人完成） 任务：为宿舍管理人员编写一个宿舍管理查询软件, 程序设计要求： 采用交互工作方式 建立数据文件，包括学生信息、宿舍信息、住宿信息，学生信息按关键字（姓名、学号）进行排序(排序方法自选，不能相同)； 查询: (用二分查找实现以下操作) 按姓名查询 按学号查询 (用顺序查找实现以下操作) 按房号查询 3.校园导航问题（限1 人完成） 设计要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。 要求：能增加场所 4.图书借阅管理系统（限1 人完成）（顺序或链式存储） 主要分为两大功能： 1)图书管理(增加图书、查询图书、删除图书、图书借阅、还书)； 2)会员管理(增加会员、查询会员、删除会员、借书信息)； 5.学生成绩管理（限1 人完成）（顺序或链式存储） 包括：课程信息，学生信息等；能增加课程或学生。 实现功能：输入、输出、插入、删除、查找、显示、保存、排序、退出。6.活期储蓄帐目管理（限1 人完成） 活期储蓄处理中，储户开户、销户、存入、支出活动频繁，系统设计要求： 1)能比较迅速地找到储户的帐户，以实现存款、取款记账；
数据结构（C语言版）（第2版） 课后习题答案 李冬梅
目录 第1章绪论............................................. 错误!未定义书签。第2章线性表........................................... 错误!未定义书签。第3章栈和队列......................................... 错误!未定义书签。第4章串、数组和广义表................................. 错误!未定义书签。第5章树和二叉树....................................... 错误!未定义书签。第6章图................................................ 错误!未定义书签。第7章查找............................................. 错误!未定义书签。第8章排序............................................. 错误!未定义书签。
第1章绪论 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。 答案： 数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。 数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。 数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。 数据对象：是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。 逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 存储结构：数据对象在计算机中的存储表示，也称为物理结构。 抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。 2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 答案： 例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构，即线性结构。 这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录，则称为顺序存储结构；如果存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储结构。 即相同的逻辑结构，可以对应不同的存储结构。 3．简述逻辑结构的四种基本关系并画出它们的关系图。
湖南师范大学硕士研究生入学考试自命题考试大纲 考试科目代码：[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）共同体变量的定义和使用方法
数据结构C语言版第2版课后习题答案 本页仅作为文档封面，使用时可以删除 This document is for reference only-rar21year.March
数据结构（C语言版）（第2版） 课后习题答案 李冬梅
目录 第1章绪论 ............................................................................ 错误!未定义书签。第2章线性表......................................................................... 错误!未定义书签。第3章栈和队列 ..................................................................... 错误!未定义书签。第4章串、数组和广义表 ........................................................ 错误!未定义书签。第5章树和二叉树 .................................................................. 错误!未定义书签。第6章图 ................................................................................ 错误!未定义书签。第7章查找 ............................................................................ 错误!未定义书签。第8章排序 ............................................................................ 错误!未定义书签。 I
《数据结构与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
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)
不管怎样，生活还是要继续向前走去。有的时候伤害和失败不见得是一件坏事，它会让你变得更好，孤单和失落亦是如此。每件事到最后一定会变成一件好事，只要你能够走到最后。附录习题参考答案 习题1参考答案 1.1.选择题 (1). A. (2). A. (3). A. (4). B. C. (5). A. (6). A. (7). C. (8). A. (9). B. (10.) A. 1.2.填空题 (1). 数据关系 (2). 逻辑结构物理结构 (3). 线性数据结构树型结构图结构 (4). 顺序存储链式存储索引存储散列表（Hash）存储 (5). 变量的取值范围操作的类别 (6). 数据元素间的逻辑关系数据元素存储方式或者数据元素的物理关系 (7). 关系网状结构树结构 (8). 空间复杂度和时间复杂度 (9). 空间时间 (10). Ο(n) 1.3 名词解释如下： 数据：数据是信息的载体 是计算机程序加工和处理的对象 包括数值数据和非数值数据 数据项：数据项指不可分割的、具有独立意义的最小数据单位 数据项有时也称为字段或域 数据元素：数据元素是数据的基本单位 在计算机程序中通常作为一个整体进行考虑和处理 一个数据元素可由若干个数据项组成 数据逻辑结构：数据的逻辑结构就是指数据元素间的关系 数据存储结构：数据的物理结构表示数据元素的存储方式或者数据元素的物理关系 数据类型：是指变量的取值范围和所能够进行的操作的总和 算法：是对特定问题求解步骤的一种描述 是指令的有限序列 1.4 语句的时间复杂度为： (1) Ο(n2) (2) Ο(n2) (3) Ο(n2) (4) Ο(n-1)
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中有弧