2012贵州省数据结构与算法(必备资料)

1、已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>}写出G的拓扑排序的结果。

G拓扑排序的结果是：V1、V2、V4、V3、V5、V6、V72、4、void LinkList_reverse(Linklist &L)//链表的就地逆置;为简化算法,假设表长大于2{p=L->next;q=p->next;s=q->next;p->next=NULL;while(s->next){q->next=p;p=q;q=s;s=s->next; //把L的元素逐个插入新表表头}q->next=p;s->next=q;L->next=s;}//LinkList_reverse3、我们用l代表最长平台的长度，用k指示最长平台在数组b中的起始位置（下标）。

用j 记住局部平台的起始位置，用i指示扫描b数组的下标，i从0开始，依次和后续元素比较，若局部平台长度（i-j）大于l时，则修改最长平台的长度k（l=i-j）和其在b中的起始位置（k=j），直到b数组结束，l即为所求。

void Platform (int b[ ], int N)//求具有N个元素的整型数组b中最长平台的长度。

{l=1;k=0;j=0;i=0;while(i<n-1){while(i<n-1 && b[i]==b[i+1]) i++;if(i-j+1>l) {l=i-j+1;k=j;} //局部最长平台i++; j=i; } //新平台起点printf(“最长平台长度%d，在b数组中起始下标为%d”，l，k)；}// Platform。

2012年数据结构与算法参考答案一、填空题1. 顺序存储链式存储2. BDCA3. 132454. Head【Tail【Head【Tail（LS）】】】5. 36. 1297. 08. O(n^2)二、选择题1.A2.C3.D4.D5.A6.A7.B8.B9.D 10.C三、判断题1.✕2. ✓3. ✓4.✓5.✕6.✕7. ✓8. ✕9. ✓10.✕四、应用题1. （1）数（a）的先根序列：ABCDEF数（a）的后根序列：BDEFCA（2）先序：ABCDEFGHIJK中序：BDEFCAIJKHG（3）如下图：ABGH CI JKDEF2. (1) 邻接矩阵：⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡∞58∞∞∞∞∞5∞∞722∞∞8∞∞4∞∞7∞∞74∞∞∞∞6∞2∞∞∞4∞∞∞2∞∞4∞∞8∞∞7∞∞∞∞8∞∞∞6∞88∞ 邻接表：01234567(2) 深度优先搜索树为：（答案不唯一）V0V1V5V4V6V7V2V3(3)最小生成树：3. 解：由线性探测法解决冲突时所建哈希表如下：ASL=(1*5+2*4+3)/10=1.64. (1) 冒泡排序一趟结果：10、4、3、6、12、1、9、18、8、18+(2) 快速排序一趟结果：8、9、4、3、6、1、10、12、18+、18(3) 增量分别为5、3、1结果如下：○110、1、4、3、6、12、18、9、18+、8○23、1、4、8、6、12、10、9、18+、18○31、3、4、6、8、9、10、12、18+、18(4) 初始堆：18、18+、12、10、8、4、1、9、3、6一趟排序结果：18+、10、12、9、8、4、1、6、3、18五、程序填空题1.（1）查询链表的尾结点（2）将第一个结点链接到链表的尾部，作为新的尾结点（3）返回的线性表为（a2,a3,..,,an,a1）2.（1）（2）中序遍历二叉树,按遍历序列中叶子结点数据域的值构建一个以Leafhead为头指针的逆序单链表,或按二叉树中叶子结点数据自右至左链接成一个链表六、算法设计题1.(1) void exam_1(Linklist,La,int,x){p=La→next; q=p; k=0; // p为工作指针pre=la;la →next=NULL; . // q指最小元素while(p&&p→data<x){//比x小的数递减r =p→next;p→next=La →next;La →next=p;p=r ; //置逆}q→next=p;pre=q; //重新链接while(p→data==x){ //考察等于x的情况pre=p;p=p→next;} // whilewhile(p){ // k为计数器k+ +;x=p→data; //避免重复计算} // while(p)} // exam_1(2)typedef int datatype;typedef struct node {datatype data; struct node *next;}lklist;void exam_2(lklist *&head){lklist *p,*q,*s;for(p=head;p!=0;p=p->next){for(q=p->next,s=q;q!=0;if (q->data==p->data){s->next=q->next; free(q);q=s->next;}else{s=q,q=q->next;}}}(3)template<classT>voidSingleList<T>::select_sort(){Node<T>*p,*r,*small;p=first->link;if(p)for(;p->link;p=p->link){for(small=p,r=p->link;r;r=r->link)if(small->data>r->data)small=r;if(small!=p)swap(p->data,small->data);}};2.(1)bool Parent(BiTree *root,TElemType x) //查找值为X，X数据类型为TElemType的结点的双亲值{if(root == NULL){print("二叉树是空树");return false；}if(root->data==x){printf("根结点的值为x，没有双亲");return false;}if(root->lchild->data == x || root->rchild->data == x){printf("找到x的双亲结点，双亲结点值为%d"，root->data);return true;}if(Parent(root->lchild,x)==true) return true; //递归调用Parent函数，若找到结点X的双亲，返回if(Parent(root->rchild,x)==true) return true;return false;}(2) 参考思路：类似按层遍历的方式，发现空节点之后看看其后还有没有树节点，没有，则是完全二叉树，使用队列帮助实现Status iscompletetree(BiTree T)//判断是否是完全二叉树、{LinkQueue Q; //声明一个对象BiTree p;p=T;if(!T)return 0;enqueue(Q,p); //结点P入队列while(queueempty(Q)) //判断队列是不是空的{dequeue(Q,p); //出队列if(p){enqueue(Q,p->lchild);enqueue(Q,p->rchild);}if(!p){while(queueempty(Q)){dequeue(Q,p->rchild);if(p) //空节点后还有节点{printf("不是完全二叉树");return ERROR;}}}}return OK;}（3）参考思路：二叉排序树中，可以通过中序遍历的方式实现结点数据的递增遍历和打印，在打印前，可以比较打印的数据是否相同，若相同，记录相同数据的个数，不打印重复点void printnode(BiTree p){static ccount = 0; //记录重复元素个数static BiTree p0=NULL;//记录结点p的前一个结点if (p){printnode(p->left);If(p0->data==p->data) count++;if (p0==NULL || p0->data!=p->data){If(count!=0) printf(“有%d个%d元素”,count，p0->data);printf("%d ", p->data);p0 = p;count = 0;}printnode(p->right);}}。

理论实践贵州省考研计算机综合复习指南一、绪论近年来，计算机科学与技术领域发展迅速，考研成为众多计算机专业学生进一步提升自己的重要途径。

为了帮助广大考生顺利备考，本文将提供贵州省考研计算机综合复习指南，以便考生能够理论与实践相结合，全面复习，取得优异成绩。

二、数据结构与算法1. 栈与队列栈是一种后进先出（LIFO）的数据结构，队列是一种先进先出（FIFO）的数据结构。

考生需要掌握栈和队列的基本定义、实现方式和常见应用，以及相应的操作算法。

2. 链表链表是一种常见的动态数据结构，分为单向链表和双向链表。

考生需要了解链表的特点、结构和操作，掌握链表的基本操作算法，并能解决相关问题。

3. 树与图树是一种非线性数据结构，具有层次关系；图是由节点和边组成的集合。

考生应熟悉树和图的基本概念、遍历算法和应用，能够实现树和图的基本操作。

4. 排序与查找排序是将一组数据按照某个规则进行重新排列的过程，常见的排序算法有冒泡排序、插入排序、选择排序、快速排序等；查找是在给定数据集中寻找特定元素的过程，常见的查找算法有线性查找、二分查找、哈希查找等。

考生需要熟悉各类排序与查找算法的原理、实现方式和时间复杂度。

三、操作系统1. 进程与线程进程是计算机程序在执行过程中的一个实例，线程是进程中的一个执行单元。

考生应了解进程和线程的概念、特点和调度算法，掌握进程与线程的创建、同步与通信方法。

2. 存储管理存储管理是操作系统对内存资源的管理和分配，包括内存分区、内存映射和分页等。

考生需了解存储管理的基本原理和算法，如分段、分页、虚拟内存等。

3. 文件系统文件系统是操作系统中负责管理、组织和存储文件的子系统。

考生需要了解文件系统的基本概念、文件组织方式和文件操作算法，如文件的创建、读取、写入和删除等。

四、数据库原理与应用1. 数据库概述数据库是数据的集合，是计算机进行数据管理的重要工具。

考生应了解数据库的基本概念、特点和分类，掌握常见数据库模型和数据模型的设计和实现方法。

贵州省考研计算机软件与理论复习资料编程与算法核心知识点解析一、概述计算机软件与理论是贵州省考研计算机专业的重要选修课程之一，对于考生的综合素质和能力要求较高。

本文将对该课程的编程与算法核心知识点进行深入解析，帮助考生进行复习备考。

二、数据结构1. 线性表线性表是计算机科学中最常用的数据结构之一，包括顺序表和链表两种形式。

顺序表的优势在于随机访问的效率高，而链表则适用于频繁插入和删除操作。

在复习过程中，需要掌握线性表的基本操作，如插入、删除、查找等，以及相应的时间复杂度。

2. 树结构树是一种非线性的数据结构，常用的树结构包括二叉树、二叉搜索树、平衡二叉树等。

二叉搜索树的特点是左子树的节点值小于根节点，右子树的节点值大于根节点，利用这一特性可以快速查找或插入节点。

平衡二叉树则保持左右子树的高度差不超过1，以保证树的平衡性。

复习时需要了解树结构的基本概念和遍历算法。

3. 图结构图是一种复杂的非线性数据结构，由顶点和边组成。

图分为有向图和无向图，常用的表示方法有邻接矩阵和邻接表。

图结构的复杂性在于其边的多样性，复习时需重点掌握图的遍历算法和最短路径算法。

三、算法设计与分析1. 算法基础复习算法设计与分析时，需要掌握算法的基本概念和分类，如递归算法、贪心算法、动态规划算法等。

此外，还需要了解算法的性能评估指标，如时间复杂度和空间复杂度。

2. 排序算法排序算法是计算机科学中最基本的算法之一，常见的排序算法有冒泡排序、插入排序、选择排序、快速排序等。

复习时需了解各种排序算法的原理、实现和优缺点，并能够根据具体场景选择合适的排序算法。

3. 搜索算法搜索算法广泛应用于图搜索、路径规划等问题中。

常见的搜索算法有深度优先搜索（DFS）、广度优先搜索（BFS）、回溯算法等。

在复习过程中，需要了解搜索算法的原理和应用场景，能够熟练地编写相应的代码。

四、程序设计1. 编程语言复习计算机软件与理论时，需要选择一种常用的编程语言进行学习和实践。

1、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a??11为第一个元素，其存储地址为1，每元素占1个地址空间，则a85的地址为（ B ）。

A）13 B）33 C）18 D）402、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a??11为第一个元素，其存储地址为1，每元素占1个地址空间，则a85的地址为（ B ）。

A）13 B）33 C）18 D）403、在数据结构中，从逻辑上可以把数据结构分为（ C ）。

A）动态结构和静态结构 B）紧凑结构和非紧凑结构C）线性结构和非线性结构 D）内部结构和外部结构4、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。

A) 单链表 B) 仅有头指针的单循环链表C) 双链表 D) 仅有尾指针的单循环链表5、广义表head(((a,b),(c,d)))的运算结果为（ A ）。

A）(a,b) B）(c,d)C）空表 D）（（a,b）,(c,d)）6、设给定问题的规模为变量n，解决该问题的算法所需时间为Tn=O(f(n)),Tn表示式中记号O表示（ A ）。

A）一个数量级别 B）一个平均值C）一个最大值 D）一个均方值7、设一数列的顺序为1，2，3，4，5，6，通过栈结构不可能排成的顺序数列为（ B ）。

A）3，2，5，6，4，1 B）1，5，4，6，2，3C）2，4，3，5，1，6 D）4，5，3，6，2，18、在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行（ A ）。

A）q->next=s; s->next=p; B）s->next=p->next; p->next=s;C）p->next=s->next; s->next=p D）p->next=s; s->next=q;9、如果结点A有3个兄弟，而且B为A的双亲，则B的度为（ B ）。

1、队列的操作的原则是（ A ）。

A）先进先出 B) 后进先出C) 只能进行插入 D) 只能进行删除2、在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为（ B ）。

A) rear=rear->next; B) front=front->next;C) rear=front->next; D) front=rear->next ;3、在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行（ A ）。

A）q->next=s; s->next=p; B）s->next=p->next; p->next=s;C）p->next=s->next; s->next=p D）p->next=s; s->next=q;4、队列的操作的原则是（ A ）。

A）先进先出 B) 后进先出C) 只能进行插入 D) 只能进行删除5、n个顶点的图的最小生成树必定（ D ），是不正确的描述。

A）不唯一 B）权的总和唯一C）不含回路 D）有n条边6、n个顶点的图的最小生成树必定（ D ），是不正确的描述。

A）不唯一 B）权的总和唯一C）不含回路 D）有n条边7、有一个有序表{1，4，6，10，18，35，42，53，67，71，78，84，92，99}。

当用二分查找法查找键值为84的结点时，经（ B ）比较后查找成功。

A) 4 B)3 C)2 D)128、设有一个栈，元素的进栈次序为A, B, C, D, E,下列是不可能的出栈序列是（ C ）。

A） A, B, C, D, EB） B, C, D, E, AC） E, A, B, C, DD） E, D, C, B, A9、若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个（ D ）。

A）上三角矩阵 B) 稀疏矩阵C) 对角矩阵 D) 对称矩阵10、在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为（ C ）。

数据结构与算法题库（含参考答案）一、单选题（共100题，每题1分，共100分）1、在一次校园活动中拍摄了很多数码照片，现需将这些照片整理到一个PowerPoint 演示文稿中，快速制作的最优操作方法是：A、创建一个 PowerPoint 相册文件。

B、创建一个 PowerPoint 演示文稿，然后批量插入图片。

C、创建一个 PowerPoint 演示文稿，然后在每页幻灯片中插入图片。

D、在文件夹中选中所有照片，然后单击鼠标右键直接发送到PowerPoint 演示文稿中。

正确答案：A2、下面对“对象”概念描述错误的是A、对象不具有封装性B、对象是属性和方法的封装体C、对象间的通信是靠消息传递D、一个对象是其对应类的实例正确答案：A3、设栈与队列初始状态为空。

首先A,B,C,D,E依次入栈，再F,G,H,I,J 依次入队；然后依次出队至队空，再依次出栈至栈空。

则输出序列为A、F,G,H,I,J,E,D,C,B,AB、E,D,C,B,A,J,I,H,G,FC、F,G,H,I,J,A,B,C,D,E,D、E,D,C,B,A,F,G,H,I,J正确答案：A4、设表的长度为 20。

则在最坏情况下，冒泡排序的比较次数为A、20B、19C、90D、190正确答案：D5、设二叉树的前序序列为 ABDEGHCFIJ，中序序列为 DBGEHACIFJ。

则后序序列为A、DGHEBIJFCAB、JIHGFEDCBAC、GHIJDEFBCAD、ABCDEFGHIJ正确答案：A6、Excel工作表B列保存了11位手机号码信息，为了保护个人隐私，需将手机号码的后 4 位均用“*”表示，以 B2 单元格为例，最优的操作方法是：A、=REPLACE(B2,7,4,"****")B、=REPLACE(B2,8,4,"****")C、=MID(B2,7,4,"****")D、=MID(B2,8,4,"****")第 10 组正确答案：B7、小金从网站上查到了最近一次全国人口普查的数据表格，他准备将这份表格中的数据引用到 Excel 中以便进一步分析，最优的操作方法是：A、通过 Excel 中的“自网站获取外部数据”功能，直接将网页上的表格导入到 Excel 工作表中。