2012宁夏回族自治区数据结构基础考资料

1、由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序所缺的语句。

#define MAX 100typedef struct Node{char info; struct Node *llink, *rlink; }TNODE;char pred[MAX],inod[MAX];main(int argc,int **argv){ TNODE *root;if(argc<3) exit 0;strcpy(pred,argv[1]); strcpy(inod,argv[2]);root=restore(pred,inod,strlen(pred));postorder(root);}TNODE *restore(char *ppos,char *ipos,int n){ TNODE *ptr； char *rpos; int k;if(n<=0) return NULL;ptr->info=(1)_______;for((2)_______ ; rpos<ipos+n;rpos++) if(*rpos==*ppos) break;k=(3)_______;ptr->llink=restore(ppos+1, (4)_______,k );ptr->rlink=restore ((5)_______+k,rpos+1,n-1-k);return ptr;}postorder(TNODE*ptr){ if(ptr=NULL) return;postorder(ptr->llink); postorder(ptr->rlink); printf(“%c”,ptr->info); }2、设计一个尽可能的高效算法输出单链表的倒数第K个元素。

1、在Word文档中插入图形的第一步操作是____。

A、执行"插入"菜单中的"图片"命令B、将插入点置于图形预期出现的位置C、在图片对话框中选择要输入的图片文件名D、单击"确定"按钮，插入图片2、计算机所具有的存储程序和程序原理是____提出的。

A、图灵B、布尔C、冯?诺依曼D、爱因斯坦3、____特点是处理的信息数据量比较大而数值计算并不十分复杂。

A、工程计算B、数据处理C、自动控制D、实时控制4、万维网的WWW的含义是____。

A、Work wide withB、wait wait waitC、Work wind weakD、World wide web5、欲将已经删除的某一文件恢复，在回收站窗口中选中该文件后，在文件菜单中应选择的菜单项是____。

A、删除B、关闭C、还原D、清空回收站6、具有管理计算机全部硬件资源、软件资源功能的软件系统是____。

A、编译系统B、操作系统C、资源管理器D、网页浏览器7、下列软件中主要用于制作演示文稿的是____。

A、WordB、ExcelC、WindowsD、PowerPoint8、全文搜索引擎一般采用什么原理来采集信息____A、人工方式B、蜘蛛程序C、关键字检索D、检索工具9、在Windows 中，有些菜单项的右端有一个向右的箭头，则表示该菜单项____。

A、将弹出下一级菜单B、当前不能选取执行C、已被选中D、将弹出一个对话框10、下列哪一项表示一个完整的计算机系统____。

A、主机，键盘，显示器B、主机和它的外围设备C、系统软件和应用软件D、硬件系统和软件系统11、____是上档键，可以用于辅助输入。

A、ShiftB、CtrlC、AltD、Tab12、在word中，将一部分内容改为四号楷体，然后紧接这部分内容后输入新的文字，则新输入的文字字号和字体分别为____。

A、四号楷体B、五号楷体C、五号宋体D、不能确定13、下面关于Windows 中滚动条的叙述，是不正确的是____A、通过单击滚动条上的滚动箭头可以实现单步滚动B、通过拖动滚动条上的滚动块可以实现快速滚动C、滚动条有水平滚动条和垂直滚动条两种D、每个窗口上都具有滚动条14、内存储器可分为____。

1、在软件开发中，下面任务不属于设计阶段的是(D)A. 数据结构设计B. 给出系统模块结构C. 定义模块算法D. 定义需求并建立系统模型2、算法的时间复杂度是指(C)A. 执行算法程序所需要的时间B. 算法程序的长度C. 算法执行过程中所需要的基本运算次数D. 算法程序中的指令条数3、面向对象的设计方法与传统的的面向过程的方法有本质不同，它的基本原理是(C)A. 模拟现实世界中不同事物之间的联系B. 强调模拟现实世界中的算法而不强调概念C. 使用现实世界的概念抽象地思考问题从而自然地解决问题D. 鼓励开发者在软件开发的绝大部分中都用实际领域的概念去思考4、在软件开发中，下面任务不属于设计阶段的是(D)A. 数据结构设计B. 给出系统模块结构C. 定义模块算法D. 定义需求并建立系统模型5、希尔排序法属于哪一种类型的排序法(B)A.交换类排序法B.插入类排序法C.选择类排序法D.建堆排序法6、设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为(B) 注：利用公式n=n0+n1+n2、n0=n2+1和完全二叉数的特点可求出A. 349B. 350C. 255D. 3517、在深度为5的满二叉树中，叶子结点的个数为(C)A. 32B. 31C. 16D. 158、软件需求分析阶段的工作，可以分为四个方面：需求获取、需求分析、编写需求规格说明书以及(B)A. 阶段性报告B. 需求评审C. 总结D. 都不正确9、在深度为5的满二叉树中，叶子结点的个数为(C)A. 32B. 31C. 16D. 1510、在软件开发中，下面任务不属于设计阶段的是(D)A. 数据结构设计B. 给出系统模块结构C. 定义模块算法D. 定义需求并建立系统模型11、下面描述中，符合结构化程序设计风格的是(A)A. 使用顺序、选择和重复（循环）三种基本控制结构表示程序的控制逻辑B. 模块只有一个入口，可以有多个出口C. 注重提高程序的执行效率D. 不使用goto语句。

宁夏回族自治区考研计算机应用技术复习资料操作系统与数据库原理重难点梳理一、引言计算机应用技术复习过程中，操作系统与数据库原理是考生们最为关注的两个重要考点。

本文将对宁夏回族自治区考研计算机应用技术复习资料中涉及的操作系统与数据库原理的重难点进行梳理，帮助考生们更好地理解和掌握相关知识。

二、操作系统1. 进程管理• 进程的概念和特征• 进程的状态及转换• 进程的调度算法：先来先服务、短作业优先、最高优先级调度等• 死锁的概念和处理方法2. 内存管理• 内存的分段和分页管理• 页面置换算法：最佳置换算法、先进先出算法、最近最久未使用算法等• 虚拟内存的概念和工作原理• 分页与分段的比较与选择3. 文件系统• 文件的组织和存储结构• 文件的操作方式：打开、读写、关闭等• 文件的保护和共享机制• 文件系统的实现方式：索引结构、位图结构等4. 设备管理• 设备的分类和管理• 设备的分配与释放• 中断处理和设备驱动程序三、数据库原理1. 数据库基本概念• 数据库的特点和作用• 数据库模型：层次模型、网状模型、关系模型等• 数据库管理系统的结构和功能2. 数据库设计与规范化• 数据模型的设计方法：实体关系模型、E-R模型等• 关系数据库的规范化理论和方法• 数据库设计的范式：第一范式、第二范式、第三范式等3. SQL语言• SQL语言的基本语法和结构• SQL语言的查询操作和数据更新操作• SQL语言的高级操作：联合查询、嵌套查询、分组聚合查询等4. 事务与并发控制• 事务的特征和ACID属性• 并发控制的概念和目标• 并发控制方法：加锁机制、时间戳机制等四、总结通过对宁夏回族自治区考研计算机应用技术复习资料中操作系统与数据库原理的重难点梳理，我们可以看到，操作系统的重点在于进程管理、内存管理、文件系统和设备管理等方面，而数据库原理的核心在于数据库基本概念、数据库设计与规范化、SQL语言和事务与并发控制等方面。

1、下述关于数据库系统的叙述中正确的是(A)A. 数据库系统减少了数据冗余B. 数据库系统避免了一切冗余C. 数据库系统中数据的一致性是指数据类型的一致D. 数据库系统比文件系统能管理更多的数据2、数据流图用于抽象描述一个软件的逻辑模型，数据流图由一些特定的图符构成。

下列图符名标识的图符不属于数据流图合法图符的是(A)A. 控制流B. 加工C. 数据存储D. 源和潭3、在下列选项中，哪个不是一个算法一般应该具有的基本特征(C)A. 确定性B. 可行性C. 无穷性D. 拥有足够的情报4、关系表中的每一横行称为一个(A)A. 元组B. 字段C. 属性D. 码5、下列叙述中正确的是(C)A.数据库是一个独立的系统，不需要操作系统的支持B.数据库设计是指设计数据库管理系统C.数据库技术的根本目标是要解决数据共享的问题D.数据库系统中，数据的物理结构必须与逻辑结构一致6、关系数据库管理系统能实现的专门关系运算包括(B)A. 排序、索引、统计B. 选择、投影、连接C. 关联、更新、排序D. 显示、打印、制表7、程序流程图（PFD）中的箭头代表的是(B)A. 数据流B. 控制流C. 调用关系D. 组成关系8、下述关于数据库系统的叙述中正确的是(A)A. 数据库系统减少了数据冗余B. 数据库系统避免了一切冗余C. 数据库系统中数据的一致性是指数据类型的一致D. 数据库系统比文件系统能管理更多的数据9、下列关于栈的叙述中正确的是(D)A. 在栈中只能插入数据B. 在栈中只能删除数据C. 栈是先进先出的线性表D. 栈是先进后出的线性表10、下列关于队列的叙述中正确的是(C)A. 在队列中只能插入数据B. 在队列中只能删除数据C. 队列是先进先出的线性表D. 队列是先进后出的线性表11、算法的空间复杂度是指(D)A. 算法程序的长度B. 算法程序中的指令条数C. 算法程序所占的存储空间D. 算法执行过程中所需要的存储空间12、在深度为5的满二叉树中，叶子结点的个数为(C)A. 32B. 31C. 16D. 1513、在下列选项中，哪个不是一个算法一般应该具有的基本特征(C)A. 确定性B. 可行性C. 无穷性D. 拥有足够的情报14、信息隐蔽的概念与下述哪一种概念直接相关(B)A.软件结构定义B. 模块独立性C. 模块类型划分D. 模拟耦合度15、对建立良好的程序设计风格，下面描述正确的是(A)A. 程序应简单、清晰、可读性好B. 符号名的命名要符合语法C. 充分考虑程序的执行效率D. 程序的注释可有可无16、下列叙述中正确的是(C)A.数据库是一个独立的系统，不需要操作系统的支持B.数据库设计是指设计数据库管理系统C.数据库技术的根本目标是要解决数据共享的问题D.数据库系统中，数据的物理结构必须与逻辑结构一致17、数据库概念设计的过程中，视图设计一般有三种设计次序，以下各项中不对的是(D)A. 自顶向下B. 由底向上C. 由内向外D. 由整体到局部18、下列叙述中正确的是(A)A. 线性表是线性结构B. 栈与队列是非线性结构C. 线性链表是非线性结构D. 二叉树是线性结构19、数据流图用于抽象描述一个软件的逻辑模型，数据流图由一些特定的图符构成。

宁夏回族自治区考研计算机科学与技术复习重点一、数据结构与算法数据结构是计算机科学与技术领域的基础，它关注如何组织和存储数据以便高效地访问和操作。

算法则是解决问题的步骤和方法，它涉及到如何设计和分析高效的解决方案。

1. 线性表线性表是最基本的数据结构之一，它包括顺序表和链表两种形式。

顺序表使用数组存储元素，具有随机访问的特点；链表通过指针将元素连接起来，方便插入和删除操作。

2. 栈和队列栈和队列是两种特殊的线性表。

栈具有后进先出（LIFO）的特点，插入和删除操作只能在一端进行；而队列具有先进先出（FIFO）的特点，插入操作在队尾进行，删除操作在队头进行。

3. 树和二叉树树是一种非线性的数据结构，它由节点和边组成。

每个节点可以有多个子节点，但每个节点只有一个父节点。

二叉树是树的一种特殊形式，每个节点最多有两个子节点。

4. 图图是由节点和边组成的非线性数据结构，它用于表示不同对象之间的关系。

图可以分为有向图和无向图，根据节点之间的关系可以有多种表示方法。

5. 排序和搜索算法排序算法用于将一组元素按照特定的顺序排列，常见的排序算法有冒泡排序、选择排序、插入排序、快速排序等。

搜索算法用于在给定数据集合中查找某个特定元素，常见的搜索算法有线性查找、二分查找、哈希查找等。

二、操作系统操作系统是计算机系统中的核心软件，它管理和控制计算机硬件资源，并提供用户与计算机系统之间的接口。

1. 进程和线程进程是正在执行的程序的实例，它包括代码、数据和资源等。

线程是进程中的一个执行单元，多个线程可以共享进程的资源，提高程序的执行效率。

2. 内存管理内存管理涉及到如何分配和释放计算机的内存资源，以及如何优化内存的使用。

常见的内存管理技术有分页、分段和虚拟内存等。

3. 文件系统文件系统是操作系统中用于管理文件和目录的组织方式。

它提供了文件的访问和操作接口，包括读取、写入、复制、删除等操作。

4. 进程间通信进程间通信用于不同进程之间的信息传递和共享。

2012数据结构_习题及程序设计整理疯狂记忆力数据结构是计算机科学中非常重要的一个领域，它主要研究数据的组织、存储和管理方式。

在学习数据结构的过程中，习题和程序设计是提高理解和应用的重要手段。

下面将整理一些2012年的数据结构习题及程序设计内容，帮助读者巩固和深入理解这一领域的知识。

一、线性结构1. 线性表是数据结构中最基本的一种结构，它的特点是元素之间存在一对一的关系，先后次序唯一确定。

请写一个C语言程序，实现线性表的基本操作，包括插入、删除、查找等。

2. 栈是一种特殊的线性表，具有“先进后出”的特点。

设计一个栈，支持判断栈是否为空、入栈和出栈操作，并实现一个简单应用情境，例如操作系统任务的进出栈操作。

3. 队列也是一种特殊的线性表，具有“先进先出”的特点。

设计一个队列，支持判断队列是否为空、入队和出队操作，并实现一个简单应用情境，例如模拟排队等待的场景。

二、非线性结构1. 树是一种重要的非线性结构，它以分层的方式存储数据。

定义一个树的基本数据结构，包括节点的定义、插入节点、删除节点等操作。

2. 图是由节点和边组成的数据结构，用于表示多对多的关系。

请设计一个简单的图结构，实现图的初始化、添加节点、添加边以及遍历等基本操作。

三、查找与排序1. 二分查找是一种常见的查找算法，适用于有序数组。

请编写一个二分查找算法的Java程序，并验证其正确性。

2. 快速排序是一种常见的排序算法，通过分治法实现。

请实现一个快速排序算法的Python程序，并对随机生成的一组数据进行排序。

四、高级数据结构1. 堆是一种完全二叉树，主要用于实现高效的优先队列。

设计一个堆的数据结构，并实现堆排序算法。

2. 哈希表是一种以键值对存储数据的数据结构，通过哈希函数实现高效的数据查找。

请实现一个简单的哈希表，包括哈希函数的设计、数据的插入和查找等操作。

以上是一些2012年的数据结构习题及程序设计内容，涵盖线性结构、非线性结构、查找与排序以及高级数据结构等方面的内容。

1、Windows中的回收站，存放的是____。

A、硬盘上被删除的文件或文件夹B、软盘上被删除的文件或文件夹C、网上邻居上被删除的文件或文件夹D、所有外存储器中被删除的文件或文件夹2、树型结构体现的是____A、表格的数据结构B、文件的目录结构C、程序的控制结构D、存储空间的物理结构3、我们要支持国产软件，支持民族产业。

那么以下是中国人自主开发的软件____A、FlashB、WPSC、PhotoshopD、Word4、内存储器存储信息时的特点是____A、存储的信息永不丢失，但存储容量相对较小B、存储信息的速度极快，但存储容量相对较小C、关机后存储的信息将完全丢失，但存储信息的速度不如软盘D、存储的容量很大，没有任何限制5、在Word中，下面不属于格式工具栏的按钮是____。

A、样式B、字体C、剪切D、粗体6、通常多媒体电脑中的光盘驱动器又称CD-ROM，它的特点是____A、对光盘既能读又能写B、对光盘只能写不能读C、对光盘只能读不能写D、既能读光盘，又能读软盘7、计算机的指令主要存放在____中。

A、CPUB、微处理器C、主存储器D、键盘8、下列带有通配符的文件名，能表示文件ABC、TXT的是____。

A、*BC、?B、A?.*C、?BC、*D、?.?9、选择某一段文字后，把鼠标指针置于选中文本的任一位置，按鼠标左键拖到另一位置上放开鼠标。

那么，该用户刚才的操作是____。

A、移动文本B、复制文本C、替换文本D、删除文本10、因特网采用的核心技术是____。

A、TCP/IP协议B、局域网技术C、远程通信技术D、光纤技术11、比较典型的压缩文件类型有____。

A、RAMB、ZIPC、WAVD、HTML12、在Word中，所有的字符格式排版，都可以通过执行菜单命令______来实现。

A、"格式→字体"B、"文件→打开"C、"格式→段落"D、"工具→选项"13、计算机网络是一个____系统。

第二章1、首尾顺序逆置2、找出顺序表中最大值和最小值及位置3、头插法算法4、尾插法：5、带头结点的单链表，向表头插入一个结点：6、单链表中查找第i个结点：8、单链表删除操作：9、重要习题，头结点与尾结点互换：10、重要习题，一个单链表拆为两个奇偶单链表：试写一个算法，将一个头结点为a的带头结点的单链表A分解成两个单链表A和B，其中头结点指针分别为a和b，使得A链表中含有原链表A中序号为奇数的元素，而B链表中含有原链表中序号为偶数的元素，并保持原来的相对顺序。

11、循环链表插入结点后仍然保持有序：12、重要习题(删除表中所有数值相同的多余元素)：13、双向链表的删除操作：14、双向链表的插入操作：在带头结点的双向循环链表中插入一个新结点，需要修改的指针数量是4个。

包括新插入的新结点的指针，还有插入结点的前面结点的next域，和后面结点的prior域。

第二章课后习题14、设计两个顺序表A和B，且都递增有序，试写一算法，从A中删除与B中相同的元素（也就是计算A-B）。

15、已知head P指向结点与其后继结点位置交换。

（q为p的后继结点，s r16、已知两个单链表A和B分别表示两个集合，其元素值递增有序，试写一算法，求A和B的交集C，要求C同样以元素递增的单链表形式存储。

r=head; 查找p的前趋结点y的结点。

第三章一、队列算法f31的功能是清空带头结点的链队列Q，请填空。

Type struct node{ DataType data;Struct node *next;}QueueNode;{QueueNode *front; //队头指针二、填空题15、如果编号为1，2，3的3辆列车进入一个栈式结构的站台，那么可能得到的3辆车出站序列有哪些？不可能出现的序列是什么？16、简述下列程序算法的功能（假设元素为整数类型）（1） void ex31(SeqStack *S){int A[80],i,n;n=0;while(!empty(S)){ A[n]=pop[S];n++;}for(i=0;i<n;i++)push(S,A[i]);}答案：此算法功能是通过一个数组将一个栈中的所有元素逆置存放。