数据结构复习(2012)

1、有一个带头结点的单链表，每个结点包括两个域，一个是整型域info，另一个是指向下一个结点的指针域next。

假设单链表已建立，设计算法删除单链表中所有重复出现的结点，使得info域相等的结点只保留一个。

#include <stdio.h>typedef char datatype;typedef struct node{datatype data;struct node * next;} listnode;typedef listnode* linklist;/*--------------------------------------------*//* 删除单链表中重复的结点 *//*--------------------------------------------*/linklist deletelist(linklist head){ listnode *p,*s,*q;p=head->next;while(p){s=p;q=p->next;while(q)if(q->data==p->data){s->next=q->next;free(q);q=s->next;}else{ s=q; /*找与P结点值相同的结点*/q=q->next;}p=p->next;}return head;}2、由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序所缺的语句。

#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); }3、题目中要求矩阵两行元素的平均值按递增顺序排序，由于每行元素个数相等，按平均值排列与按每行元素之和排列是一个意思。

数据结构复习提纲（12级）数据结构复习提纲（12级）第一章绪论§1.1 数据结构1.什么是数据结构？包括哪三方面的内容？2.什么是数据类型？§1.2 算法及其描述1.算法具有哪5个特性？2.算法描述有哪些方式？§1.3 算法分析1.能分析小程序段的时间复杂度（习题1.5，1.6）2.时间复杂度T(n)=O(f(n))的含义是什么？(习题1.3)3.各种不同数量级的时间复杂度的增长率比较（P14）第二章线性表§2.1 线性表及其逻辑结构1.线性表的定义2.线性表有哪些基本运算？§2.2 线性表的顺序存储结构1.清楚顺序表的类型定义：SqList2.顺序表的各种基本算法。

3.算法（例2.3，例2.4，练习题2.2）§2.3 线性表的链式存储结构1.清楚单链表的类型定义：LinkList2.单链表的各种基本算法3.算法（例2.5，例2.6，练习题2.3 ）4.清楚双链表的类型定义：DLinkList5.双链表的算法（其各种基本算法，例2.7，习题2.4）6.循环链表的算法（例2.9，例2.10，习题2.5）§2.5 有序表例2.11第三章栈和队列§3.1 栈1.什么是栈？栈的特点是什么？栈有哪些基本运算？（例3.1、例3.2）2.栈的顺序存储结构---SqStack, 其基本运算的算法。

3.栈的链式存储结构（不考）4.练习题3.1，3.2，例3.4，例3.5§3.2 队列1. 什么是队列？队列的特点是什么？队列有哪些基本运算？（例3.6）2. 队列的顺序存储结构的定义---SqQueue。

3. 循环顺序队列的判断空队列和满队列的条件各是什么？如何求队列长度？4. 循环顺序队列的基本算法。

如：入队列算法enqueue，出队列算法dequeue，等，习题3.4，3.55. 队列的链式存储（不考）第四章串§4.1 串的基本概念1. 串的定义。

1、串的逻辑结构与（ D ）的逻辑结构不相同。

A）线性表 B）栈C）队列 D）集合2、线索二叉树中某结点D，没有左孩子的条件是（ B ）。

A）D->Lchild=Null B) D->ltag=1C) D->Rchild=Null D) D->ltag=03、若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个（ D ）。

A）上三角矩阵B) 稀疏矩阵C) 对角矩阵 D) 对称矩阵4、采用链结构存储线性表时，其地址（ B ）。

A）必须是连续的 B）连续不连续都可以C）部分地址必须是连续 D）必须是不连续的5、设单链表中指针p指着结点A，若要删除A之后的结点（若存在），则需要修改指针的操作为（ A ）。

A）p->next=p->next->next B）p=p->nextC）p=p->nexe->next D）p->next=p6、在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（ C ）。

A）4 B）5C）6 D）77、串的逻辑结构与（ D ）的逻辑结构不同。

A）线性表 B）栈C）队列 D）树8、下列序列中，执行第一趟快速排序后得到的序列是（ A ）。

A）[d,a,e,d,b]f[h,g] B) [c,e,a,d]f[h,g,b]C) [g,a,e,c,b]f[d,h] D) [a,b,c,d,]f[e,g,h]9、已知栈的最大容量为4。

若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（ C ）。

A) 5，4，3，2，1，6 B) 2，3，5，6，1，4C) 3，2，5，4，1，6 D) 1，4，6，5，2，310、n个顶点的强连通图至少有（ A ）条边。

A）n B）n+1 C）n-1 D）n(n-1)11、设有一个栈，元素的进栈次序为A, B, C, D, E,下列是不可能的出栈序列是（ C ）。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

数据结构习题课（2012）复习重点1.数据结构的概念，逻辑结构、物理结构的概念及各⾃包含的内容2.算法的特性、设计要求，如何度量算法的时间效率。

3.线性表的顺序/链式存储结构的特点，插⼊、删除算法。

4.栈和队列的逻辑特性，顺序栈的⼊栈/出栈、循环队列的⼊队/出队算法。

5.以三元组顺序表存放的稀疏矩阵的转置算法。

6.⼆叉树的性质及其四种遍历算法。

7.森林与⼆叉树的相互转换。

8.WPL、前缀编码的概念，哈夫曼树的构造算法。

9.图的相关概念，邻接矩阵及邻接表的存储结构。

10.图的深度优先/⼴度优先遍历算法。

11.最⼩⽣成树的两种算法。

12.拓扑排序的意义和算法。

13.最短路径算法。

14.顺序表、有序表的查找算法。

15.⼆叉排序树的性质、插⼊/删除算法、平衡⼆叉树的性质、插⼊算法。

16.哈希表的相关概念，常⽤的冲突处理⽅法。

17.直接插⼊排序、希尔排序、快速排序、堆排序、归并排序的算法。

注意：1.上述每个知识点可能会以任何题型出现，复习的时候别把它们当做“简答题”来复习。

2.红⾊（下划线）标识的知识点或算法，只要求对给出的初始数据，能画出结果则可。

其他的算法则可能会出现在“算法题”中。

⾃测题第1章绪论⼀、判断1.顺序存储⽅式只能⽤于存储线性结构。

（错）2.顺序查找法适⽤于存储结构为顺序或链式存储的线性表。

（对）⼆、选择1.计算机算法必须具备输⼊、输出、（ B ）等5个特性。

A.可⾏性、可移植性和可扩展性B.可⾏性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、安全性和稳定性2.算法在发⽣⾮法操作时可以作出处理的特性称为（C ）。

A.正确性B.易读性C.健壮性D.可靠性3.数据结构是⼀门研究⾮数值计算的程序设计问题中计算机的（A ）以及它们之间的（ B ）和运算的学科。

A.操作对象B.计算⽅法C.逻辑存储D.数据映像A.结构B.关系C.运算D.算法4.在数据结构中，逻辑上数据结构可分为：（B ）A.动态结构和静态结构B.线性结构和⾮线性结构C.紧凑结构和⾮紧凑结构D.内部结构和外部结构5.数据结构主要研究数据的（D ）A.逻辑结构B.存储结构C.逻辑结构和存储结构D.逻辑结构和存储结构及其运算的实现6.为了描述n个⼈之间的同学关系，可⽤（C ）结构表⽰A.线性表B.树C.图D.队列7.下⾯的程序段违反了算法的（A ）原则void sam(){ int n=2;while (!odd(n)) n+=2;printf(n);}A.有穷性B.确定性C.可⾏性D.健壮性三、问答1.什么是逻辑结构和物理结构？各⾃包含哪⼏种？2.线性结构和树型结构的特点分别是什么？3.简述顺序存储结构与链式存储结构在表⽰数据元素之间关系上的只要区别。

2012上《数据结构》复习提纲第1章绪论数据结构的研究目的和研究内容；有关术语；算法、算法复杂度的分析和计算方法例题：1．下面算法的时间复杂度为O( n )。

int f( unsigned int n ){if ( n = = 0 || n = = 1 ) return 1;else returen n *f ( n – 1 ); }2．一个算法应具备的5个特性为有穷性、确定性、可行性、输入、输出3．同类问题见第一次作业第2-3章线性表，栈和队列线性表的概念、存储结构、插入与删除操作；栈和队列的概念，理解栈顶指针、队首、队尾指针的意义和作用，特别是循环队列的头、尾指针的设置。

为什么要这样设置。

它们基本操作的实现。

判空和判满？了解有关应用。

例题：1．已知指针p所指结点不是尾结点，若在*p之后插入结点*S，则应执行和操作是s- >link =p->link; p->link =s;2．同类问题：在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行的语句？（答：q->next=s; s->next=p）；注意在某个已知结点前插需要执行的语句？3．注意循环（链）队列的判空和判满的条件？（看书理解！）4．在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是s->prior=p; s->next=p->next;p->next->prior=s; p->next=s;5．设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为p->next=p->next->next。

6.在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是O(n)。

7.向一个栈顶指针为hs的链栈中插入一个s结点时，应执行s->next=hs; hs=s;。

第二章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]);}答案：此算法功能是通过一个数组将一个栈中的所有元素逆置存放。