数据结构期末习题答案

第一章绪 论一，选择题1组成数据的基本单位是（）a 数据项b 数据类型c 数据元素d数据变量2数据结构是研究数据的（）以及它们之间的相互关系。a 理想结构，物理结构b理想结构，抽象结构c 物理结构，逻辑结构d抽象结构，逻辑结构3算法分析的两个主要方面是（）a 正确性和简单性b 可读性和文档性c 数据复杂性和程序复杂性d 时间复杂度和空间复杂度4算法分析的目的是（）。a 找出数据结构的合理性b研究算法中的输入和输出的关系c 分析算法的效率以求改进d分析算法的易懂性和文档性5. 算法的时间复杂度取决于（）a问题的规模b.待处理数据的初态c. a 和 b以上都不是6. 一个算法应该是（）。a程序b 问题求解步骤的描述c 要满足五个基本特性d a和c.7. 下面关于算法说法错误的是（）a. 算法最终必须由计算机程序实现b. 为解决某问题的算法同为该问题编写的程序含义是相同的c. 算法的可行性是指指令不能有二义性d.以上几个都是错误的精品资料8. 从逻辑上可以把数据结构分为（）两大类。 a动态结构、静态结构b顺序结构、链式结构c线性结构、非线性结构d初等结构、构造型结构9程序段for ( i=n-1;i=1;i-)for (j=1jaj+1)aj 与 aj+1 对换；其中 n 为正整数，则最后一行的语句频度在最坏情况下是（）a. o（ n）b o(nlogn)c. o(n 3)d o(n 2 ) 10 连续存储设计时，存储单元的地址（）。a一定连续b 一定不连续c 不一定连续d部分连续，部分不连续二，判断题1. 数据结构的抽象操作的定义与具体实现有关。()2. 数据结构是数据对象与对象中数据元素之间关系的集合。3. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。()4. 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用的需要建立的。5. 算法和程序原则上没有区别，在讨论数据结构是两者是通用的。6. 同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据项的个数都相等。7. 数据的逻辑结构与数据元素本身的内容和形式无关。8. 算法的优劣与算法描述语言无关，但与所用计算机有关。()9. 健壮的算法不会因非法的输入数据而出现莫名其妙的状态。()10 算法可以用不同的语言描述，如果用 c 语言或 pascal语言等高级语言来描述，则算法实际上就是程序了。()一，选择题1 c2 c3 d4 c5c6 b7 d8 c9 d10 a二，判断题1.2. 3.4. 5. 6. 7.8.9.10. 三，填空1. 数据的物理结构包括的表示和的表示。2. 对于给定的n 个元素 , 可以构造出的逻辑结构有， _四种。3. 一个数据结构在计算机中称为存储结构。4. 抽象数据类型的定义仅取决于它的一组 _，而与 _无关，即不论其内部结构如何变化，只要它的_不变，都不影响其外部使用。5. 线性结构中元素之间存在关系 , 树形结构中元素之间存在关系 ,图形结构中元素之间存在关系。6. 一个算法有5 个特性 :、，有零个或多个输入、有一个或多个输出。7. 已知如下程序段for（ i= n ； i=1;i + ）语句 1x:=x+1 ；语句 2for( j=n;j=i ;j+)语句 3 y:=y+1;语句 4。语句 1 执行的频度为；语句 2 执行的频度为；语句 3 执行的频度为； 语句 4 执行的频度为8. 在下面的程序段中，对的赋值语句的频度为 （表示为n 的函数）for(i 1;i=n;i+) for(j ;j=i;j+)for(k 1;k=j;j+) delta ；9. 计算机执行下面的语句时，语句s 的执行次数为 。for(i=l ； i=i;j-)s;10. 下面程序段的时间复杂度为 。(n1) sum=1 ；for (i=0;sumn;i+) sum+=1;三，填空题1. 数据元素数据元素间关系2. 集合线性结构树形结构图状结构或网状结构3. 表示（又称映像） 。4. 逻辑特性在计算机内部如何表示和实现数学特性5. 一对一一对多多对多6. 有穷性确定性可行性7 n+1nn(n+3)/2n(n+1)/28 1+ （ 1+2+ （ 1+2+3 ） +（ 1+2+n ） =n(n+1)(n+2)/6o(n 3)9. (n+3)(n-2)/210. o(n)四，应用题1. 什么是数据? 它与信息是什么关系?2. 什么是数据结构?数据结构是研究什么内容的学科？有关数据结构的讨论涉及哪三方面?3. 评价一个好的算法，从哪几方面考虑？4. 若将数据结构定义为一个二元组（d， r） ,说明符号 d ， r应分别表示什么？ 5解释算法与程序的区别？ 6有下列几种用二元组表示的数据结构，画出它们分别对应的逻辑图形表示，并指出它们分别属于何种结构。（1 ） a= （k ， r），其中：k=a ， b， c， d， e， f，g r=rr=a ， b， b， c， c， d， d，e， e， f， f， g（2 ） b= （k ， r），其中：k=a ， b， c， d， e， f，g， h r=rr=d， b， d， g， d， a， b， c， g， e， g，h， a， f（3 ） c= （ k ，r ），其中：k=1 ， 2 ， 3， 4 ， 5 ，6 r=rr=(1, 2) ，(2, 3) ，（ 2， 4），（ 3，4 ），（ 3 ，5），（3 ，6 ），（ 4，5），（ 4,6 ）这里的圆括号对表示两结点是双向的。7. 分析以下程序段的时间复杂度。（1 ）a=0 ； b=1 ；for（ i=2 ；i=n ；i+ ）s=a+b ； b=a ； a=s ；（2 ）inti ， j， k；for（ i=0 ；in； i+ for（ j=0 ； jn； j+ cij=0 ；for（ k=0 ；kn； k+ cij=cij+aik+bkj；8. 求下列算法段的语句频度及时间复杂度（1 ）for(i=1; i=n; i+)for(j =1; j =i ; j+) x=x+1;（2 ）for （ i=1;i=n;i+）for (j=1;j=i;j+)for ( k=1;knext=hb. p-next=nilc. p-next-next=hd. p-data=-1 2下面关于线性表的叙述中，错误的是哪一个？（）a线性表采用顺序存储，必须占用一片连续的存储单元。b线性表采用顺序存储，便于进行插入和删除操作。c线性表采用链接存储，不必占用一片连续的存储单元。d线性表采用链接存储，便于插入和删除操作。3. 线性表是具有n 个（）的有限序列（n0 ） 。a表元素b字符c数据元素d 数 据 项4若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。a顺序表b双链表c 带头结点的双循环链表d单循环链表5某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。a单链表b 仅有头指针的单循环链表c双链表d仅有尾指针的单循环链表 6设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用()最节省时间。a. 单链表b. 单循环链表c.带尾指针的单循环链表d. 带头结点的双循环链表7在带有头结点的单链中插入一个新结点时不可能修改（）。a 头 指针b 头结点指针域c 开始结点指针域d 其它结点指针域8. 双向链表中有两个指针域，llink和 rlink ，分别指向前驱及后继，设p 指向链表中的一个结点， q 指向一待插入结点，现要求在p 前插入 q，则正确的插入为（）。a. p-llink=q;q-rlink=p;p-llink-rlink=q;q-llink=p-llink;b. q-llink=p-llink;p-llink-rlink=q;q-rlink=p;p-llink=q-rlink;c. q-rlink=p;p-rlink=q;p-llink-rlink=q;q-rlink=p;d. p-llink-rlink=q;q-rlink=p;q-llink=p-llink;p-llink=q; 9对于一个头指针为head 的带头结点的单链表，判定该表为空表的条件是（）。ahead=nullbhead next=nullc head next=headdhead!=null 10 在顺序表中查找第i 个元素的时间效率最高的算法时间复杂度是（）。ao(1)b o(n )c o(log 2n)d o(n)11 最好的情况下，在顺序表中按值查找一个元素的算法时间复杂度是（）。ao(n)b o(n )c o(log 2 n)d o(1)12. 若长度为n 的线性表采用顺序存储结构，在其第i 个位置插入一个新元素的算法的时间复杂度为（）(1=ilink=headb p-link=nilc p=nild p= head一，选择1.a2.b3.c4.a5.d6.d7.a8.d9.b10.a11 d12.c13.c14.c15.a二，判断1. 链表中的头结点仅起到标识的作用。()2线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。()3顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。()4顺序存储方式只能用于存储线性结构。()5线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。6. 线性表的特点是每个元素都有一个前驱和一个后继。()7. 取线性表的第i 个元素的时间同i 的大小有关。()8. 循环链表不是线性表。()9. 线性表就是顺序存储的表。()10.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。()二，判断1. 2. 3. 4. 5.6. 7. 8. 9. 10. 三，填空1. 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用 存储结构。2. 线性表l= （ a1,a2,an ）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是 。3. 在一个长度为n 的顺序表中第i 个元素（ 1=inext=p ； s-prior= ； p-prior=s ； =s ；7. 顺序存储结构通过 表示元素之间的关系;链式存储结构通过 表示元素之间的关系。8. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共 个，单链表为 个。9. 已知指针p 指向单链表l 中的某结点，则删除其后继结点的语句是： , 时间复杂度是。10. 带头结点的双循环链表l 中只有一个元素结点的条件是：。三，填空1顺序2（ n-1 ） /23 n-i+14 o(1) ， o(n)5. f-next=p-next; f-prior=p; p-next-prior=f; p-next=f;6. p-priors-prior-next7. 物理上相邻指针8 429 u=p-next; p-next=u-next; free(u); o(1) ; 10 l-next-next=l四，算法设计1. 试写一算法在带头结点的单链表结构上实现线性表操作locate （ l， x）。2. 试写一算法在带头结点的单链表结构上实现线性表操作length （ l）。3. 试写一算法实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1, a 2,an）逆置为（ an, a n-1,a 1）。4. 试写一算法，对单链表实现就地逆置。5. 设线性表 a = （a 1， a 2，,an），b=（b 1, b 2,bn），试写一个按下列规则合并a，b 为线性表 c 的算法，即使得c= （ a 1, b 1, a m ,b m ,b m+1,bn）当 mn 时；线性表 a ，b 和 c 均以单链表作存储结构，且 c 表利用 a 表和 b 表中的结点空间构成。注意：单链表的长度值m 和 n 均未显式存储。1lnode* locate(linklist l,int x)/链表上的元素查找,返回指针for(p=l-next;p&p-data!=x;p=p-next); return p;/locate2int length(linklist l)/求链表的长度for(k=0,p=l;p-next;p=p-next,k+); return k;/length3void reverse(sqlist &a)/顺序表的就地逆置for(i=0,j=a.length-1;ij;i+,j-)a.elemia.elemj;/reverse4void linklist_reverse(linklist &l)/链表的就地逆置;为简化算法 ,假设表长大于2p=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_reverse分析 :本算法的思想是,逐个地把l 的当前元素q 插入新的链表头部,p 为新表表头 .5void merge1(linklist &a,linklist &b,linklist &c)/把链表 a 和 b 合并为 c,a 和 b 的元素间隔排列,且使用原存储空间p=a-next;q=b-next;c=a; while(p&q)s=p-next;p-next=q; /将 b 的元素插入if(s)t=q-next;q-next=s; /如 a 非空,将 a 的元素插入p=s;q=t;/while/merge1第三章栈和队列一，选择1. 对于栈操作数据的原则是（）。a. 先进先出b.后进先出c.后进后出d.不分顺序3. 最大容量为n 的循环队列， 队尾指针是rear ，队头是 front ，则队空的条件是（）。a. (rear+1) mod n=frontb. rear=frontc rear+1=frontd. (rear-l) mod n=front4 当利用大小为n 的数组顺序存储一个栈时，假定用top= =n表示栈空，则向这个栈插入一个元素时首先应执行语句修改top 指针。atop+b top-c top=0d top5. 若已知一个栈的入栈序列是1,2,3,n，其输出序列为p 1,p 2 ,p 3， pn ,若 pn 是 n，则pi 是()。a. ib. n-ic. n-i+1d.不确定6. 一个递归算法必须包括（）。a. 递归部分b. 终止条件和递归部分c.迭代部分d. 终止条件和迭代部分7. 执行完下列语句段后，i 值为：（）intf(int x) return(x0) ? x* f(x-1):2);int i;i =f(f(1);a2b. 4c. 8d.无限递归8. 设栈 s 和队列 q 的初始状态为空，元素e1 ，e2 ，e3 ，e4,e5 和 e6 依次通过栈s ，一个元素出栈后即进队列q，若 6 个元素出队的序列是e2 ， e4， e3,e6,e5,e1则栈 s 的容量至少应该是 ()。a 6b. 49. 栈和队列的共同点是（）。c. 3d. 2a. 都是先进先出c.只允许在端点处插入和删除元素b.都是先进后出d.没有共同点10. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。a线性表的顺序存储结构b.队列c.线性表的链式存储结构d.栈11. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点， 则在进行删除操作时()。a仅修改队头指针b.仅修改队尾指针c.队头、队尾指针都要修改d.队头 ,队尾指针都可能要修改12. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。a队列b 多维数组c 栈d.线性表13. 假设以数组am 存放循环队列的元素, 其头尾指针分别为front 和 rear ，则当前队列中的元素个数为（）。a(rear-front+m)%mbrear-front+1c (front-rear+m)%md (rear-front)%m14. 循环队列存储在数组a0.m 中，则入队时的操作为（）。a. rear=rear+1b. rear=(rear+1) mod (m-1)c. rear=(rear+1) mod md. rear=(rear+1)mod(m+1)15. 若用一个大小为6 的数组来实现循环队列，且当前rear 和 front 的值分别为0 和 3，当从队列中删除一个元素，再加入两个元素后，rear 和 front 的值分别为多少？()a. 1 和 5b. 2 和 4c. 4 和 2d. 5 和 1一，选择1.b3.b4 b5.d6.b7.b8.c9.c10.d11.d12.c13.a14.d15.b二，填空1 是限定仅在表尾进行插入或删除操作的线性表。3. 中缀表达式3*（ x+2 ）-5 所对应的后缀表达式为；后缀表达式“45*32+- ”的值为。4. 顺序栈用data1.n 存储数据，栈顶指针是top, 则值为 x 的元素入栈的操作是 。5 向一个循环队列中插入一元素时，需首先移动，然后再向所指位置新插入的元素。6. 用下标0 开始的 n 元数组实现循环队列时，为实现下标变量m 加 1 后在数组有效下标范围内循环，可采用的表达式是：m= 7. 用长度为n的数组顺序存储一个栈时，若用top=n 表示栈空，则表示栈满的条件为。二，填空1栈3 3 x 2 + * 5 -154 data+top=x；5 队尾指针写入6 (m+1) mod n(m+1)% n ；7 top=0三，应用题1指出下列程序段的功能(1) void demo1(seqstack *s)int i; arr64 ; n=0 ;while ( stackempty(s) arrn+=pop(s); for (i=0, i n; i+) push(s, arri); /demo1(2) seqstack s1, s2, tmp; datatype x;./ 假设栈 tmp 和 s2 已做过初始化while ( ! stackempty (&s1)x=pop(&s1) ;push(&tmp,x);while ( ! stackempty (&tmp) )x=pop( &tmp);push( &s1,x);push( &s2, x);(1) 程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底， 栈底的元素放到栈顶。此栈中元素个数限制在64 个以内。(2) 程序段的功能是利用tmp 栈将一个非空栈s1 的所有元素按原样复制到一个栈s2 当中去。四，算法设计题1 回文是指正读反读均相同的字符序列，如abba 和abdba 均是回文，但good 不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)1 根据提示，算法可设计为：/以下为顺序栈的存储结构定义#define stacksize 100 /假定预分配的栈空间最多为100 个元素typedef char datatype;/假定栈元素的数据类型为字符typedef structdatatype datastacksize; int top;seqstack;int ishuiwen( char *t)/判断 t 字符向量是否为回文，若是，返回1，否则返回0 seqstack s;int i , len; char temp;initstack( &s);len=strlen(t); /求向量长度for ( i=0; ilen/2; i+)/将一半字符入栈push( &s, ti); while( !emptystack( &s)/ 每弹出一个字符与相应字符比较temp=pop (&s);if( temp!=si)return 0 ;/不等则返回0 else i+;return 1 ; /比较完毕均相等则返回1第四章串一，选择1. 下面关于串的的叙述中，哪一个是不正确的？（）a串是字符的有限序列b 空串是由空格构成的串c模式匹配是串的一种重要运算d 串既可以采用顺序存储，也可以采用链式存储2. 设有两个串p 和 q ，其中 q 是 p 的子串， 求 q 在 p 中首次出现的位置的算法称为（）a求子串b联接c匹配d 求串长3串的长度是指（）a串中所含不同字母的个数b 串中所含字符的个数c串中所含不同字符的个数d 串中所含非空格字符的个数4若串 s= software ,其子串的数目是（）。a 8b 37c 36d 9一，选择1.b2.c3 b4.b二，填空1. 空格串是指 ，其长度等于 。2. 组成串的数据元素只能是 。3. 一个字符串中 称为该串的子串。4. index （datastructure， str ） = 。7设 t 和 p 是两个给定的串， 在 t 中寻找等于p 的子串的过程称为 ，又称 p 为 。二，填空1. 由空格字符（ascii 值 32 ）所组成的字符串空格个数2. 字符3. 任意个连续的字符组成的子序列4 57模式匹配模式串第五章数组和广义表一，选择1. 已知广义表l= （ x,y,z ）， a ，（u ， t， w） ，从 l 表中取出原子项t 的运算是（）。a. head （ tail （ tail（ l） ）b. tail （ head （ head （ tail（ l） ）c. head （ tail （head （tail（ l） ）d. head （tail(head （ tail（tail （l） ） )）2. 广义表 a=(a,b,(c,d),(e,(f,g),则下面式子的值为（）。head(tail(head(tail(tail(a)a. (g)b. (d)c. cd. d3. 稀疏矩阵一般的压缩存储方法有两种,即（）a. 二维数组和三维数组b三元组和散列c三元组和十字链表d散列和十字链表4. 二维数组 a 的每个元素是由6 个字符组成的串， 其行下标 i=0,1,8, 列下标 j=1,2,10 。若 a 按行先存储，元素a8,5 的起始地址与当a 按列先存储时的元素（）的起始地址相同。设每个字符占一个字节。a. a8,5b. a3,10c. a5,8d. a0,95. 对稀疏矩阵进行压缩存储目的是（）。a便于进行矩阵运算b便于输入和输出c节省存储空间d 降低运算的时间复杂度6. 设 a 是 n*n 的对称矩阵，将a 的对角线及对角线上方的元素以列为主的次序存放在一维数组 b1.n(n+1)/2中，对上述任一元素a ij(1 i， jn，且 i j) 在 b 中的位置为 ()。a. i(i-l)/2+jb. j(j-l)/2+ic. j(j-l)/2+i-1d. i(i-l)/2+j-17. an ， n是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组tn （n+1 ）/2 中，则对任一上三角元素aij 对应 tk 的下标 k 是（）。a i（i-1 ） /2+jb j（ j-1 ） /2+ic i（j-i ） /2+1d j（ i-1 ）/2+18. 设广义表l= （ a,b,c ） ，则 l 的长度和深度分别为（）。a. 1 和 1b. 1 和 3c. 1 和 2d. 2 和 39. 数组 a0.4,-1.-3,5.7中含有元素的个数（）。a 55b 45c 36d 1610. 下面说法不正确的是()。a. 广义表的表头总是一个广义表b. 广义表的表尾总是一个广义表1.d2.d3.c4.b5.c6.b7.b8.c9.b10.ac.广义表难以用顺序存储结构d.广义表可以是一个多层次的结构一，选择二，判断1. 一个稀疏矩阵a m*n 采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m 和 n 的值互换，则就完成了a m*n 的转置运算。（）2. 从逻辑结构上看，n 维数组的每个元素均属于n 个向量。（）3. 稀疏矩阵压缩存储后，必会失去随机存取功能。（）4. 对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。（）5. 数组可看成线性结构的一种推广，因此与线性表一样可对它进行插入，删除操作。（）6. 所谓取广义表的表尾就是返回广义表中最后一个元素。（）7. 二维以上的数组其实是一种特殊的广义表。（）8. 广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（）9. 若一个广义表的表头为空表，则此广义表亦为空表。（）1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 四应用题1. 画出下列广义表的两种存储结构图(),a,(b,(c,d),(e,f)。2. 设某表 h 如下：abcxa1a2b1c1c210. 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。（） 二，判断其中 a,b,c 为子表名， a1,a2,b1,c1,c2,x为其元素。试用广义表形式表示h, 并写出运算head(h) 和 tail(h)函数从 h 中取出单元素a2 的运算；（1 ） h(a(a 1 ,a 2） ,b(b 1） ,c(c 1， c2） ,x） head(tail(head(h)=a2五，算法设计1. 设任意 n 个整数存放于数组a(1:n) 中，试编写程序，将所有正数排在所有负数前面2. 设二维数组a1.m, 1.n含有 m*n个整数。判断a 中所有元素是否互不相同? 输出相关信息 (yes/no) 。1. 本题属于排序问题，只是排出正负，不排出大小。可在数组首尾设两个指针i 和 j， i 自小至大搜索到负数停止， j 自大至小搜索到正数停止。然后 i 和 j 所指数据交换， 继续以上过程， 直到i=j 为止。void arrange(int a,int n)/n 个整数存于数组a 中，本算法将数组中所有正数排在所有负数的前面int i=0,j=n-1,x;/ 用类 c 编写，数组下标从0 开始while(ij)while(i0)i+; while(ij & aj0)j-;if(ij) x=ai; ai+=aj; aj-=x; /交换 ai与 aj/ 算法 arrange结束 .算法讨论 对数组中元素各比较一次，比较次数为n。最佳情况 (已排好 ,正数在前 ,负数在后 )不发生交换，最差情况(负数均在正数前面)发生 n/2 次交换。用类c 编写，数组界偶是0.n-1 。空间复杂度为o(1).2. 判断二维数组中元素是否互不相同，只有逐个比较,找到一对相等的元素，就可结论为不是互不相同。 如何达到每个元素同其它元素比较一次且只一次？在当前行，每个元素要同本行后面的元素比较一次（下面第一个