数据结构期末习题答案.doc

第一章 绪 论一，选择题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要满足五个基本特性 DA和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(n3) DO(n2) 10连续存储设计时，存储单元的地址（ ）。A一定连续 B一定不连续 C不一定连续 D部分连续，部分不连续二，判断题1数据结构的抽象操作的定义与具体实现有关。( ) 2数据结构是数据对象与对象中数据元素之间关系的集合。3在顺序存储结构中，有时也存储数据结构中元素之间的关系。( )4数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用的需要建立的。5算法和程序原则上没有区别，在讨论数据结构是两者是通用的。6同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据项的个数都相等。7数据的逻辑结构与数据元素本身的内容和形式无关。8算法的优劣与算法描述语言无关，但与所用计算机有关。( )9健壮的算法不会因非法的输入数据而出现莫名其妙的状态。( )10算法可以用不同的语言描述，如果用C 语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。( ) 一，选择题1C2C3D4C5C6B7D8C9D10A二，判断题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(i1;i=n;i+)for(j;j=i;j+)for(k1;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+1 n n(n+3)/2 n(n+1)/281+（1+2+（1+2+3）+（1+2+n）=n(n+1)(n+2)/6 O(n3)9. (n+3)(n-2)/2 10. O(n)四，应用题1什么是数据? 它与信息是什么关系?2什么是数据结构? 数据结构是研究什么内容的学科？有关数据结构的讨论涉及哪三方面?3评价一个好的算法，从哪几方面考虑？4. 若将数据结构定义为一个二元组（D，R）,说明符号D，R 应分别表示什么？5解释算法与程序的区别？6有下列几种用二元组表示的数据结构，画出它们分别对应的逻辑图形表示，并指出它们分别属于何种结构。（1）A=（K，R），其中：K=a，b，c，d，e，f，gR=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，hR=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，6R=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=h B. p-next=NIL C. p-next-next=h D. p-data=-12下面关于线性表的叙述中，错误的是哪一个？（ ）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=NULL Bheadnext=NULL Cheadnext=head Dhead!=NULL10在顺序表中查找第i个元素的时间效率最高的算法时间复杂度是（ ）。AO(1) BO() CO(log2n) DO(n) 11最好的情况下，在顺序表中按值查找一个元素的算法时间复杂度是（ ）。AO(n) BO() CO(log2n) DO(1) 12. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1=ilink=head Bp-link=NIL Cp=NIL Dp= head一，选择1.A2.B3.C4.A5.D6.D7.A8.D9.B10.A11D12.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）/2 3 n-i+14O(1)，O(n) 5f-next=p-next; f-prior=p; p-next-prior=f; p-next=f;6p-prior s-prior-next7物理上相邻 指针 84 29u=p-next; p-next=u-next; free(u); O(1) ; 10L-next-next=L 四，算法设计1试写一算法在带头结点的单链表结构上实现线性表操作LOCATE（L，X）。2试写一算法在带头结点的单链表结构上实现线性表操作LENGTH（L）。3试写一算法实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1, a2, ,an）逆置为（an, an-1, ,a1）。4 试写一算法，对单链表实现就地逆置。5 设线性表A =（a1， a2， ,an），B=（b1, b2, ,bn），试写一个按下列规则合并A，B为线性表C的算法，即使得C=（a1, b1, , am ,bm ,bm+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;/Locate 2int 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;/reverse 4void 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=front B. rear=front Crear+1=front D. (rear-l) MOD n=front4当利用大小为n的数组顺序存储一个栈时，假定用top= =n表示栈空，则向这个栈插入一个元素时首先应执行 语句修改top指针。Atop+ Btop- Ctop=0 Dtop5. 若已知一个栈的入栈序列是1,2,3,n，其输出序列为p1,p2,p3，pN,若pN是n，则pi是( )。 A. i B. n-i C. n-i+1 D. 不确定6. 一个递归算法必须包括（ ）。A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D.终止条件和迭代部分7. 执行完下列语句段后，i值为：（ ） int f(int x) return (x0) ? x* f(x-1):2); int i ; i =f(f(1);A2 B. 4 C. 8 D. 无限递归8. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( )。A 6 B. 4 C. 3 D. 29. 栈和队列的共同点是（ ）。A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点10. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。A线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈11. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( )。A仅修改队头指针 B. 仅修改队尾指针 C. 队头、队尾指针都要修改 D. 队头,队尾指针都可能要修改12. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（ ）的数据结构。A队列 B多维数组 C栈 D. 线性表13. 假设以数组Am存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ ）。A(rear-front+m)%m Brear-front+1 C(front-rear+m)%m D(rear-front)%m14. 循环队列存储在数组A0.m中，则入队时的操作为（ ）。A. rear=rear+1 B. rear=(rear+1) mod (m-1)C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1) 15. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( ) A. 1和 5 B. 2和4 C. 4和2 D. 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栈 33 x 2 + * 5 - 154data+top=x； 5 队尾指针 写入6(M+1) MOD N (M+1)% N； 7top=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，否则返回0SeqStack 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 ;/ 不等则返回0else 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,其子串的数目是（ ）。A8 B37 C36 D9一，选择 1.B2.C3B4.B二，填空1空格串是指_，其长度等于_。 2组成串的数据元素只能是_。 3一个字符串中_称为该串的子串 。 4INDEX（DATASTRUCTURE， STR）=_。7设T和P是两个给定的串，在T中寻找等于P的子串的过程称为_，又称P为_。二，填空1由空格字符（ASCII值32）所组成的字符串 空格个数 2字符3任意个连续的字符组成的子序列 45 7模式匹配 模式串 第五章 数组和广义表一，选择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. c D. d3.稀疏矩阵一般的压缩存储方法有两种,即（）A 二维数组和三维数组 B三元组和散列C三元组和十字链表 D散列和十字链表4. 二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,8,列下标j=1,2,10。若A按行先存储，元素A8,5的起始地址与当A按列先存储时的元素（ ）的起始地址相同。设每个字符占一个字节。A. A8,5 B. A3,10 C. A5,8 D. A0,95. 对稀疏矩阵进行压缩存储目的是（ ）。A便于进行矩阵运算 B便于输入和输出 C节省存储空间 D降低运算的时间复杂度6. 设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B1.n(n+1)/2中，对上述任一元素aij(1i，jn，且ij)在B中的位置为( )。A. i(i-l)/2+j B. j(j-l)/2+i C. j(j-l)/2+i-1 D. i(i-l)/2+j-17. AN，N是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组TN（N+1）/2中，则对任一上三角元素aij对应Tk的下标k是（