数据结构练习题.doc

第一章绪论应掌握的类题型一、数据结构的基本概念 1、在数据结构中，从逻辑上可以把数据结构分成 和 。 2、线性结构中元素之间存在 关系，树形结构中元素之间存 在 关系，图形结构中元素之间存在 关系。 3、数据元素是数据的最小单位(对/错)(北京邮电大学1998年)二、算法和时间复杂度分析 1、将下列函数，按它们在n-时的无穷大阶数，从小到大排序（中科院计算所1995年） n,n-n3+7n5,nlog2n,2n/2,n3, log2n,n1/2+log2n,(3/2)n,n!,n2+log2n答：log2n, n1/2+log2n, n, nlog2n, n2+log2n, n3, n-n3+7n5, 2n/2,(3/2)n, n! c log2n n nlog2n n2 n3 2n 3n n!2、void prime(int n) int i=2; while(n%2)!=0&i*1.0sqrt(n) printf(“%d is a prime number!”); else printf(“%d is not a prime number!”); 答：prime嵌套最深层语句是：i+，频度由(n%2)!=0&i*1.00 )If ( x100 ) x-=10;y - -; Else x+;n （2001） 有一计算矩阵相乘的程序，它的时间复杂度为O(n3 )，当上机运行两个1010矩阵相乘时，执行时间为5ms，试计算两个3030的矩阵相乘所需的时间。 n （2003） 1. 数据类型是一个值集合和定义在这个值集合上的一组_ 总称。 2. 若上机运行两个1010矩阵相乘，执行时间为5 ms ，该矩阵相乘算法的时间复杂度T(n)= O( n3 )，其中n为矩阵的规模，则利用该算法计算两个2020的矩阵相乘时，执行时间为_。 3. 单链表中，逻辑上相邻的元素的物理位置_紧邻。 4. 数据元素在计算机中有两种不同的存储结构即_。 5. 程序段for( i = 1; i = n; i + ) for( j = i; j = n; j+ ) k+ 中k+执行的频度是_。n （2004）设问题规模为n，算法1和算法2的基本语句执行的频度分别为f(n)、g(n)，用户从n=1测试到n=103 ，发现f (n) g (n) 总成立，请问：算法1的时间复杂度小于算法2的时间复杂度吗？说明理由。 n （2004）一个算法的基本语句执行的频度如下： ，其中n是问题的规模，试计算该算法的时间复杂度。 n （2007）设n为3的倍数，试分析程序段中带“”语句的执行频度 for ( i=1; i=n; i+ ) if (3*i = n)-n for ( j=3*i; j=n; j+ )- x+; y=3*x+2; n （2007）试分析下面程序段中带“”语句的语句执行频度 for ( i = 1; i = i+1; j- )- if ( a j-1 a j ) t = aj-1; aj-1 = aj; aj = t; n 任何一个算法的设计都取决于选定的A A.数据逻辑结构B.数据的物理结构 C.数据存储结构 D.数据的数据类型n 算法的健壮性的含义是Dn A. 程序对于几组输入数据能够得出满足规格说明要求的结果 B.程序对于带有刁难性的输入数据能够得出满足规格说明要求的结果 C.程序不含语法错误 D 当输入数据非法时，算法也能适当地作出反应或进行处理，不会产生莫名其妙的输出结果 3.数据元素是D A.数据不可分割的最小单位 B.性质相同的数据集合 C.数据的逻辑关系D.数据的基本单位，通常作为一个整体处理4. 算法效率是根据该算法编制的程序在计算机上运行所消耗的时间而度量的，程序所消耗的时间D A.取决于算法选用的策略和问题的规模，与书写程序的语言无关 B.取决于问题规模和书写程序的语言，与算法选用的策略无关 C.只与编译程序所产生的机器代码的质量和机器执行指令的速度有关 D. 与算法选用的策略、问题规模、书写程序的语言、编译程序产生的机器代码的质量和机器执行指令的速度都相关。 第二章的试题类型应掌握的知识点类型题一、顺序及链式存储结构的概念及特点。1 顺序存储方式只能用于存储线性结构。(错）2 线性表是具有n个 的有限序列。(数据元素)3 向长度为n的线性表中的第i个元素（1in之前，插入一个元素时，需向后移动 个元素，删除第i个元素时，需向前移动 个元素。(n-i+1,n-i)4 表长为n的顺序存储的线性表，当在任何位置插入和删除一个元素概率相等时，插入一个元素所需移动元素的平均个数为 ，删除一个元素需移动元素的平均个数为 。(n/2,n-1/2)5 顺序查找法适用于存储结构为顺序或链式存储的线性表。（对）7 线性表采用链表存储时结点和结点内部的存储空间可以不连续。(正确/错误)8 若频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构？为什么？二、算法性能分析2.1 若长度为n的线性表采用顺序存储结构，在其第i （1in+1）个位置插入一个新元素的算法的时间复杂度为 。 三、单链表及双向链表的基本算法（插入、删除、判空）3.1 将s所指结点加到p所指结点后，语句是 。 四、单链表逆置（原地、可构造新表、递归）4.1写一算法，在原链表上实现逆置。算法思想：依靠下标变换来实现void reverse1(Sqlist &A)int temp,i,j; for(i=0,j=A.length-1;inext; pb=b-next; pc-next=NULL; while (pa&pb) if (pa-datadata)/pa所指结点链到pc,pa指针后移 pan=pa-next; pa-next=pc-next; pc-next=pa; pa=pan; else /pb所指结点链到pc,pb指针后移 pbn=pb-next; pb-next=pc-next; pc-next=pb; pb=pbn; /while while (pa) pan=pa-next; pa-next=pc-next; pc-next=pa; pa=pan; while (pb) pbn=pb-next; pb-next=pc-next; pc-next=pb;pb=pbn; free(pb); return pc;/MergeList八 算法与C的转换define list_init_size 100#define listincrement 10Typedefine struct elemtype *elem; int kength; int listsize; sqlist;Status initlist_sq( sqlist &l) l.elem=(elemtype *) malloc(list_init_size * sizeof(elemtpye); if (!l.elem)exit(overflow); l.lenth=0;l.listsize=list_init_size;Return OK;Status listinsert_sq(sqlist &l, int i, elemtype e) if(il.length+1) return error; if(l.length=l.listsize) newbase=(elemtype *) realloc(l.elem, (l.listsize+listincrement)*sizeof(elemtype); if (!newbase) exit(overflow); l.elem=newbase; l.listsize+=listincrement; q=&( l.elemI-1); for (p=&(l.eleml.lengrh-1); p=q; -p) *(p+1)=*p; *p=e; +l.length; return OK;C程序#include#include #define list_init_size 10#define listincrement 5Typedef int elemtype;Typedef int status;Typedefine struct elemtype *elem; int length; int listsize; sqlist;Status initlist_sq( sqlist *l) l-elem=(elemtype *) malloc(list_init_size * sizeof(elemtpye); if (! L-elem) printf(“overflow”); exit(-1); l-lenth=0; l-listsize=list_init_size; Return OK; (去掉)Status listinsert_sq(sqlist *l, int i, elemtype e) int *p, * q;if(il-length+1) printf(“插入位置错误”）; exit(-1); if(l-length=l-listsize) newbase=(elemtype*)realloc(l.elem,(l-listsize +listincrement)*sizeof(elemtype); if (!newbase) printf(“空间不够”); exit(-1); l-elem=newbase; l-listsize+=listincrement; q=&( l-elemI-1); for (p=&(l-eleml-lengrh-1); p=q; -p) *(p+1)=*p; *p=e; +l-length; return OK;(去掉) Main() elemtype e; int k, i,j; sqlist l; initlist_sq(l); for(k=1; e!=0; k+) scanf(“%d %d”,&i, &e); listinsert_sq(&l,i,e ); for(j=1;jk;j+)printf(l.elemj); 第三章 栈和队列习题应掌握的类型题一、入栈和队列的序列，栈和队列判空满。 二、栈和队列的应用一、出入队列的序列，队列判空满。1 循环队列用数组A0.m-1存放其元素值，已知其头尾指针分别是front、rear，则当前队列中元素个数为 。2 用一个大小为6的数组实现循环队列，当前rear=0, front=3，当从队列中删除一个元素，再入队两个元素时，rear= ，front= 。 3用向量表示的循环队列容量为MAXSIZE，队首和队尾位置分别为1和max_size，队列为空的条件 ，队列为满的条件 。 4 设栈S和队列Q的初始状态为空，元素a、b、c、d、e、f依次通过S，一个元素出栈后即进入队列Q，若这6个元素队列的顺序是b、d、c、f、e、a，则S的容量至少是 。 5(中国科技大学1998)用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是 和 ，若只设尾指针，则出队和入队的时间复杂度分别是 和 。 二、队列应用 2.1在解决计算机主机与打印机之间速度不匹配问题时常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印，该缓冲区是一个 。A 堆 B 队列 C 数组 D 线性表 2.2已知Q是非空队列，S是一空栈，使用C语言编写一个算法，仅用队列和栈的基本操作和少量工作变量将队列Q的元素逆置。 void Reverse_Queue(SqQueue Q,SqStack s) while(!QueueEmpty(Q) data=DeQueue(Q); push(S,data); /while while(!StackEmpty(S) data=pop(S); EnQueue(Q,data); /while/Reverse_Queue郑州大学研究生入学试题选n 对循环队列，仅凭Q.front=Q.rear无法判断循环队列是空还是满，为了能判别，可使用多种处理方法，试写出其中的两种方法。（设置一布尔变量来区分队列满和空、队列中少用一个单元、设置一个记数器） n 设栈S和队列Q的初始状态为空，元素a,b,c,d,e,f依次进栈S，一个元素出栈后即进入队列Q，若这6个元素出队列的顺序是bdcfea，问栈的容量至少应为多少？ （3）n 由于栈在使用过程中所需最大空间的大小很难估计，合理的做法是为栈分配尽可能大的容量，因为一旦栈满，就没有办法使用栈了。 （对错）n 将下列递归函数改写为非递归函数：Void test ( int &sum ) int x ;scanf ( x ) ;if ( x=0 ) sum=0; else test ( sum); sum+=x; printf( sum ); 答案Void test ( int &sum ) int x ; stack s; initstack(&s); scanf ( x ) ;while ( x ) push(s,x); scanf(x);sum=0; printf( sum ); while (pop(s,x) sum=sum+x; printf(sum);n 设大小为m个空间的数组S ( 即s1sm )供一个栈和一个队列使用，且栈与队列实际占用的空间事先不知道，但要求在任何时刻它们存放的数据量都不超过m， （1）如何安排栈和队列才能充分利用空间，并写出栈底bottom、栈顶top，队列头front、队列尾rear的初始值。 （2）编写插入算法，满足当参数i =1时，将x插入到栈中；当参数i =2时，将x插入到队列中。解：(1) 初始条件： bottom=top=0 rear=front=m+1 注：满的条件：top+(front-rear)=m , void overflow-false() for (i=front-1, irear 或top=rear+1void overflow-false() for (i=front; irear; ; i-) sm-front+i =si; rear=rear+m-front; front=m;void insert(arraytype s; int i; elementype x)if (top=rear+1) overflow-false(); if (i=1) stop=x; top=top+1; else if (i=2)srear=x; rear=rear-1;n 判定一个循环队列Q（最多m个元素）满的条件是 。 n 循环队列用数组A0.m-1存放其元素，已知其头、尾指针分别为front、rear，则当前队列中元素的个数是 。 n 内存中有一连续的存储空间（设1到m单元），现将该空间分配给两个栈S1和S2，为了提高空间的利用率，减少S1和S2栈的上溢的可能性，（1）应如何分配两个栈的空间？（2）用高级语言描述出栈的定义。（3）写出栈满的条件。 解：（1）两个栈共享1至m，且两栈底分别设在空间的两端，两栈顶都向中间延伸。 （2）TypeDef struct Elemtp elemm;int top; s1,s2; (3) s2.top=s1.top+1 n 字符序列r, o, f 按顺序进栈，则出栈序列中能作为C语言变量的有_种。 n 利用两个栈s1、s2模拟一个队列，写出入队和出队算法（可以使用栈的基本操作，并假设栈s1、s2的容量足够大）。 1 /入队列在S1中，在S2中出队列enqueue(stack &s1,stack &s2 ,elemtype k) elemtype e;while(!stackempty(s2) pop(s2,e); push(s1,e);push(s1,k); dequeue(stack &s1,stack &s2 ) elemtype e;while(!stackempty(s1) pop(s1,e); push(s2,e);pop(s2,e);return(e);n 假设以带头结点的循环单链表表示队列，并只设一个指针rear指向队尾结点，但不设头指针，请写出相应的入队算法和出队算法，要求算法中含有单链表结点结构的描述。 typedef struct slink elemtype data;slink *next;slink; /*enqueue(slink &rear, elemtype x) slink *s; s=(slink*)malloc(sizeof(slink); if (!s) printf(“overflow”); exit(0);s-data=x;s-next=rear-next ;rear-next=s;rear=s;dequeue(slink &rear, elemtype &x) slink *p; if (rear-next=rear) return 0; /*p=rear-next-next;if (p=rear)rear=rear-next; rear-next=rear; / * else rear-next-next=p-next;x=p-datafree(p);return 1;第四章串习题应掌握的类型一、串的基本概念。二、串的基本操作和应用。一、串的基本概念1 空串与空格串的区别 。2 两个字符串相等的充分必要条件是 。3 是C语言中abcd321ABCD的子串。A abcd B 321ab C abcABC D 21AB 4 若串S=software，其非空子串数目为 。 5 设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身）的个数为 。二、串的基本操作和应用1 已知3个字符串分别为s=ababcaabcbcaa，s=caab，s=bcb，试用所学字符串基本运算的函数得到结果串s=caabcbcaacaai1=index(s,s,1) i2=index(s,s,1)+3; s1=substring(s,i1,strlength(s)-i1+1) s2=substring(s,i2,strlength(s)-i2+1) s=concat(s1,s2)2等值子串:若字符串的一个子串(长度1)的各字符相同.设计一个算法，输入串S，以“!”为结束。若S中不存在等值子串，则输出 “无等值子串”，否则求长度最大的等值子串。void equivalentsubstring(char Sn)for(k=0;k+) scanf(%c,&Sk); if(Sk=!) break;for(int i=0,j=1,head=0,max=1;Si!=!&Sj!=!;i=j,j+)count=1;while(Si=Sj)j+; count+; /统计当前等值子串长度if(countmax)/发现最长等值子串更新head和maxhead=i; max=count;/forif(max1)for(k=head;kn=n1+2n0-1度为1的结点最多有1个，共248个2.高为h的满二叉树叶子结点数为2h-1，而总结点数是n=2h-1，叶子结点数为2h-1=（n+1）/2结点数最少的情况是除根结点之外，每层只有两个结点，最少共2*（h-1）个一、二叉树的性质习题6 在结点个数为n(n1)的各棵树中，高度最小的树的高度是多少？它有多少叶结点？多少分支结点？高度最大的树的高度是多少？它有多少叶结点？多少分支结点？【答】结点个数为n时, 高度最小的树的高度为2；有n-1个叶结点，1个分支结点；高度最大的树的高度为n；它有1个叶结点,n-1个分支结点 四、哈夫曼树及应用1、已知下列字符A，B，C，D，E，F，G的权值分别是3、12、7、4、2、8、11，画出哈夫曼树，写出其存储结构的初态和终态,求出带权路径长度。字符编码A0110B11C00D010E0111F101G00 WPL=(3+2) *4+(7+4+8)*3+(12+11)*2 =123 GBDAECF0000111114720515900127 四、哈夫曼树及应用(续)2、假定用于通信的电文由 8 个字母 c1, c2, c3, c4, c5, c6, c7, c8 组成, 各字母在电文中出现的频率分别为 5, 25, 3, 6, 10, 11, 36, 4。试设计不等长 Huffman 编码, 并给出该电文的总码数。答案 电文总码数=4*5+2*25+4*3+4*6+ 3*10+3*11+2*36+4*4= 257第七章图的习题n 一、图的定义和术语题1 对于给定n个元素，可构造的逻辑结构有 、 、 、 。2 n个顶点的无向图，若边数n-1，该图必是连通图。（对/错）3 G是一个非连通无向图，有28条边，则该图至少有 个顶点4 在一个无向图中，所有顶点的度数之和等于所有边数的 倍。5 在一个具有n个顶点的无向完全图中，包含 条边，在一个 具有n个顶点的有向完全图中，包含 条弧。6 如果G1是一个具有n个顶点的连通无向图，G1最多有 条边。 最少有 条边。7 具有4个顶点的无向完全图有条边。8 n个顶点的有向完全图中含有向边的数目最多为 。n 二、图的存储结构题1 邻接矩阵A= ，该图有 个顶点，如果是有向图，该 图共有 条弧，如果是无向图，该图共有 条边。2 有n个顶点的无向图，采用邻接矩阵表示，图中的边数等于邻接矩 阵中非零元素之和的一半。（正确/错误）3 在无向图的邻接矩阵中，若（vi,vj）或（vj,vi）属于G的边集合 ，则对应元素ij = ，否则ij= 。4 有向图的邻接矩阵中第i行“1”的个数是第i个顶点的 ，第i列“1” 的个数是第i个顶点的 。在无向图的邻接矩阵中，第i行(列)中 ”1”的个数是第i个顶点的 。5 一个有1000个顶点、1000条边的有向图的邻接矩阵有 个矩阵元素。（是/否）稀疏矩阵。6 一个连通图的生成树是该图的 连通子图，n个顶点的连通无向 图的邻接矩阵至少有 个非零元素。7 带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中 。 A 第i行非的元素之和 B 第i列非的元素之和 C 第i行非且非0的元素个数 D 第i列非且非0的元素个数8 在含n个顶点和e条边的有向图的邻接矩阵中，零元素的个数为_。 A.e B.2e C.n2-e D.n2-2e n 三、图的遍历题1 采用邻接表存储的图的深度优先遍历算法类似于树的_。2 采用邻接表存储的图的广度优先遍历算法类似于树的_。3 若采用邻接矩阵结构存储具有n个顶点的图，则对该图进行广度优先遍历的算法时间复杂度为_。4 以邻接表表示的具有n个顶点和e条边的图的深度优先搜索算法的时间复杂度为_。AO(n) BO(n3) CO(n2) DO(n+e) 5 如图无向图，从顶点1出发的深度优先和广度优先遍历序列分别是 和 。n 四、最小生成树及相关算法题目1 Kruskal算法时间复杂度为 ，对 图较为合适。2 Prim算法的时间复杂度为 ，它对 图较为合适。3 在一个由n个顶点的无向网中，有O(n1.5*log2n)条边，则应该选用 算法来求最小生成树，从而使计算时间较少。n 五、拓扑排序、关键路径题目1若一个有向图的邻接矩阵中对角线以下元素为，则该图的拓扑有序序列必定存在（对错）3 在AOV网中存在环意味着 ，这是 的，对程序的数据流图来说它表明存在 。4 用DFS遍历一个无环有向图，并在DFS算法退栈返回时，打印出相应的顶点，则输出的顶点序列是 。5 判断一个有向图是否存在回路除了可用拓扑排序方法以外，还可用_。 A 求关键路径的方法 B 求最短路径的Dijkstra方法 C 广度优先遍历算法 D 深度优先遍历算法第九章查找的习题一 静态查找表1.用向量和单链表表示的有序表均能用折半查找法来提高查找速度2.在线性表中采用折半查找法查找元素，该线性表应3.有n个数存放在一维数组A1.n中，在顺序查找时，这n个数的排列有序或无序其平均查找长度不同。4.在分块检索中，对256个元素的线性表分成 块最好，每块的最佳长度是 ，若每块的长度是8，其平均查找长度是 。5.在关键字随机分布的情况下，用二叉排序数的方法进行查找，其查找长度与 量级相当。A 顺序查找 B折半查找 6.对5个数据 do,for,if ,repeat,while，他们排在一个有序表中，其查找概率分别为02.,0.15,0.14,0.03,0.01，查找他们之间不存在的数据的概率分别是：0.2,0.15,0.1,0.03,0.02,0.01，1）画出对该有序表采用顺序查找和折半查找的判定树。2）分别计算顺序查找时的查找成功和不成功的平均查找长度以及折半查找时 的查找成功和不成功的平均查找长度。3）判定折半查找好还是顺序查找好。二 动态查找表1.在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得的二叉排序树与删除前的二叉排序树相同。2.已知序列17,31,13,20,35,25,8,11,40,27，画出二叉排序树，并插入9，删除17,133.序列9，2，3，8，20，10，6，构造一棵平衡的二叉排序树4.在非空m阶B-树上，除根结点外的所有非终端结点至少有 棵子树。若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有关键字个数是 ，若在某结点中删除一个关键字而导致结点合并，则此结点中原有关键字个数是 。1.设有一组关键字序列19，23，14，55，84，11，13，1)依次取D中各数据，构造一棵二叉排序树；2)按表中元素顺序构造一棵平衡二叉树（画出构造过程，注明旋转类型）3)从空树开始，按表中元素顺序构造一棵2_3树(3阶B_树)，若此后再删除55，84，画出每一步执行后2_3树的状态。2.设数据集合D=1,12,5,8,3,10,7,13,9，回答下列问题： 1）依次取D中各数据，构造一棵二叉排序树； 2）用什么遍历方法访问此二叉排序树能得到D的升序序列？ 3）画出在此二叉排序树中删除“12”后的结果。 4）依次取D中各数据，构造一棵平衡的二叉排序树；3.将关键码10,100,32,45,58,126,3,29,200,400,0 散列到表，设该散列表长度为13，采用线性探测再散列的方法解决冲突, 散列函数采用除留余数法,用%13将各关键码映像到表中. 请指出每一个产生冲突的关键码可能产生多少次冲突. 第十章 排序习题1.下列排序算法中， 排序在某趟结束后不一定选出一个元素放到其最终的位置上。 A选择 B冒泡 C归并 D堆2.时间复杂度不受数据初始状态影响，恒为0(nlog2n)的是_。 A堆排序 B冒泡排序 C直接选择排序 D快速排序3.下面的序列中_是大顶堆。 A1,2,8,5,3,9,10,4 B1,5,10,6,7,8,9,2 C9,8,7,6,4,8,2,1 D9,8,7,6,5,4,3,14.快速排序在最坏情况下时间复杂度为O(n2)，比 的性能差。 A 堆排序 B起泡排序 C 简单选择排序5.要尽快完成对实数数组的排序，要求排序是稳定的，则应选 。 A快速排序 B堆排序 C归并排序6.直接插入排序