数据结构复习题集(上).ppt

《数据结构复习题集(上).ppt》由会员分享，可在线阅读，更多相关《数据结构复习题集(上).ppt（43页珍藏版）》请在优知文库上搜索。

1、数据结构习题集第一二章重要概念：数据结构相关定义：数据结构=数据+结构 记作 Data_Structure=(D,S)其中, Data_Structure是数据结构的名称。D是数据元素的有限集合(一般为一个数据对象)S是D上关系的有限集.几个相关名词：存储结构 逻辑结构 现实中任何一个问题都可以定义为一个数据类型-称为抽象数据类型抽象数据类型Abstract Data Type ADT一个数学模型及定义在这个模型上的一组操作(或运算)的总称.抽象数据类型定义 抽象数据类型=数学模型+操作=数据结构+操作描述如下：ADT 抽象数据类型的名称 数据对象 数据关系 基本操作ADT抽象数据类型名时间复

2、杂度(空间复杂度雷同)通常选择对特定问题的最基本操作作为原操作，以原操作执行次数即语句频度作为算法的时间度量T(n)。算法分析一般步骤：1.计算出算法的各个语句的频度2.统计出算法的语句频度和T(n)3.给出T(n)的大O表示称为算法的时间复杂度T(n)=O(f(n)常见的时间复杂度，按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n2)、立方阶O(n3)、k次方阶O(nk)、指数阶O(2n)。第一二章习题1数据结构在计算机中的表示称为数据的（存储结构）。2数据结构是相互之间存在一种或多种特定关系的数据元素的集合.3数据结

3、构在计算机中存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为（顺序存储结构）。4. 定义一个整数序列的ADT 需要记住此整数序列需要支持元素的位置概念。Integers数据对象：D = ci|ci DO DO = INT i = 1，2, n n=0 数据关系：R NN = | ci-1 , ci D0 i = 2，3, ，n 基本操作：void clear(); void insert(int); void remove(int); void sizeof(); bool isEmpty(); bool isInSet(int); 5. 写出下列代码段的平均时间复杂度。假定其中的所

4、有变量都是整型。 (a) a = b + c; d = a + e; (b) sum = 0; for (i=0; i3; i+) for (j=0; jn; j+) sum+; (c) sum=0; for (i=0; in*n; i+) sum+; (d) for (i=0; i n-1; i+) for (j=i+1; j n; j+) tmp = Aij; Aij = Aji; Aji = tmp; (e) sum = 0; for (i=1; i=n; i+) for (j=1; j=n; j*=2) sum+; (f) sum = 0; for (i=1; i=n; i*=2) f

5、or (j=1; j=n; j+) sum+; T(n) =O( f(2) = O(1);常数阶时间复杂度 T(n) =O( f(n-1)*(n)/2) = O(n2); T(n) =O( f(3n) = O(n); 1阶时间复杂度T(n) =O( f(n*log2n) = O(n*logn);T(n) =O( f(log2n*n) = O(logn*n);T(n) =O( f(n2) = O(n2); 2阶时间复杂度 (g)Assume that array A contains values, Random takes constant time, and sort takes steps

6、. for (i=0; in; i+) for (j=0; jn; j+) Aj = Random(n); sort(A, n); (h)Assume array A contains random permutation of the values from 0 to n-1 sum = 0; for (i=0; in; i+) for (j=0; Aj!=i; j+) sum+; (i) sum = 0; if (EVEN(n) /EVEN(n)判断元素是否为偶数 for (i=0; i 1) if (ODD(n) n = 3 * n + 1; else n = n / 2; T(n) =

7、O( f(n*(n-1)/2) = O(n2);T(n) =O( f(n*n*log2n) = O(n2logn);T(n) =O( f(n+1)/2) = O(n);下限是(log n)，没有上限。(只有当n=2x时，此段代码执行次数最少，执行的次数为log2n)7.(代码题)输入三个数x,y,z 按照从小到大顺序输出将输入的三个数作为数组元素进行冒泡排序void main() int num=3; printf(Input three number:n); int anum,temp,i,j; for(i=0;inum;i+) scanf(%d,&ai); for(i=0;inum-1;i

8、+) for(j=i+1;jaj) temp=ai; ai=aj;aj=temp; for(i=0;i=0)个数据元素的有限序列。一般表示为L=(a1,a2,ai,an)注意：线性表是一种逻辑结构，表示元素之间一对一的相邻关系，下面说的两种实现方式是指他们的存储结构。线性表的两种实现方式：顺序表 ：顺序存储的线性表又称为顺序表，是使用一组地址连续的存储单元，依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理地址上也相邻。链表：通过一组任意的存储单元来存储线性表中的数据元素，每一个链表结点，除了存放元素自身信息还需要存放指向其后继的指针。第三章习题1在下列序列中，不是线性表的是(a,

9、true,c)。2线性链表中各链结点之间的地址（连续与否无所谓）。3如某链表中最常用的操作是在最后一个结点后插入一个结点和删除最后一个结点，（带头结点的双循环链表）存储方式最节省运行时间。4线性表的顺序存储结构特点是（ 可直接随机访问任一元素）。 1. 设A是一个线性表（al，a2，,an），采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为多少？ 分析：假设 pi 是在第i个元素之前插入元素的概率，则在长度为n的线性表中插入一个元素所需移动元素次数的平均次数为：2线性表可用顺序表或链表存储。试问：(1) 两种存储表示各有哪些主要优缺点?(2) 如果有n个表同时并存，

10、并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？(3) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？Answer:(1) 顺序表需要提前估计线性表的大小并且插入删除效率低需要移动大量结点，优点在于表中节点没有浪费存储空间，并且可以按位置随机访问；链表优点在于插入删除效率高， 无需提前估计表的大小，表中元素个数没有限制，缺点在于访问结点需要从表头遍历查找并且每个节点除了储存元素还需要附加空间存储指针。(2) 链表 表的大小不固定(3) 顺序表，表大小固定，插入删除操作少，按

11、位置随机存取速度快2)2)1(110)1(11E)1(pE11nnnnnnninniii3针对带表头结点的单链表，试编写下列函数。(1) 定位函数Locate：在单链表中寻找第i个结点。若找到，则函数返回第i个结点的地址；若找不到，则函数返回NULL。(2) 求最大值函数max：通过一趟遍历在单链表中确定值最大的结点。(1)Node *LinkLocate(int i) if ( i next; int j=0; while(p & j!=i) p=p-next; j+; if(p = null) return -1; else return p; (2)template E LinkMax(

12、) Node * p; p=head-next; E j=p-data; while(p -next & p-data next-data) p=p-next; j=p-next-data; return j; (3) 统计函数number：统计单链表中具有给定值x的所有元素。(4) 建立函数create：根据一维数组an建立一个单链表，使单链表中各元素的次序与an中各元素的次序相同，要求该程序的时间复杂性为O(n)。(3)template int LinkCount(E a) Node * p; p=head-next; int count=0; while(p) if(p-data=a)

13、count+; p=p-next; return count; (4)template void LinkCreate(E a,int n) Node * p; p=head-next;/尾指针 尾插法 for(int i=0;inext=temp; temp-data=ai; p=temp-next; 5) 整理函数tidyup：在非递减有序的单链表中删除值相同的多余结点。template void LinkSort() Node *p=head-next,*temp; while(p!=null&p-next!=null) if (p-data = p-next-data ) temp =

14、 p-next; p-next=temp-next; delete temp; else p = p-link; 第四章1栈应用的典型事例是（）。A）排队 B）查找 C）归并 D）用“算符优先法”进行表达式求值2若用单链表来表示队列，则应该选用（）。A）带尾指针的非循环链表B）带尾指针的循环链表C）带头指针的非循环链表D）带头指针的循环链表 3在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，这样主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。该缓冲区应该是一个（）结构。A）堆栈B）队列C）数组D）线性表 4设一个栈的入栈序列是ABCD，则借助于一

15、个栈所得到的出栈序列不可能是（）。A）ABCDB）DCBAC）ACDBD）DABC5一般情况下，将递归算法转换成等价的非递归算法应该设置（）。A）栈B）队列C）堆栈或队列D）数组6设栈的输入序列是1，2，n，若输出序列的第一个元素是n，则第i个输出元素是（）。 A）n-i+1B）i C）n-iD）前面都不正确DBDBAA1有 5个元素，其入栈次序为：A、B、C、D、E，在各种可能的出栈次序中，以元素C第一个出栈，D第二个出栈的次序有哪几个？ 分析：栈特点：先进后出； 元素C元素D为前两个出栈元素，说明AB已入栈，并且CD入栈后又出栈。可能的情况有 三种。 E元素未入栈时，BA依次出栈 即为CD

16、BAE； B元素出栈后E元素入栈然后EA再入栈 即为CDBEA； E元素入栈后，EBA依次出栈 即为CDEBA2已知一个栈S的输入序列为abcd，下面两个序列能否通过栈的Push和Pop操作输出；如果能，请写出操作序列；如果不能，说明原因。 (1)dbca (2)cbda 分析：栈特点：先进后出；(1)dbca 不可能 若d第一个出栈，则只有dcba这种可能(2可能 操作序列为：Push(a) Push(b) Push(c) Pop(c) Pop(b) Push(d) Pop(d) Pop(a)3. 给一个链表增加一个成员函数，此函数用来将链表中的元素逆置。算法时间复杂度尽可能的小。Node* Reverse(Node* head) Node *p, *q; if(head = NULL) return NULL; p = NULL;/* 逆序后头指针的next为NULL */ while(head-next) q = head-next;/* 保存指针的下一个 */ head-next = p;/* next指针反转 */ p = head;/* 指针后移 */ head = q;/