算法与数据结构（C＆Java）（第2版） 习题及答案

习题集第一章习题一、填空题1.数据结构被形式地定义为（D，R），其中D是_________的有限集合，R是_________的有限集合。2.3.线性结构中元素之间存在_________关系，树形结构中元素之间存在_________关系，图形结构中元素之间存在_________关系。4.数据的存储结构可用4种基本的存储方法表示，分别是_____、_____、_____、_____。5.数据常用的运算有5种，分别是_____、_____、_____、_____、_____。6.数据结构中评价算法的两个重要指标是和。7.一个算法具有5个特性：_____、_____、_____、有零个或多个输入、有一个或多个输出。8.下面程序段的时间复杂度为_____。sum=1;for(i=0;sum<n;i++)sum+=1；9.下面程序段的时间复杂度为_____。i=1;while(i<=n)i=i*3;10.链式存储的特点是利用_____来表示数据元素之间的逻辑关系。二、选择题1.数据结构研究的内容不涉及（）A．数据如何组织B.数据如何存储C．数据的运算如何实现D.算法用什么语言来描述2.数据结构中，与所使用的计算机无关的是数据的什么结构（）。A.存储B.物理C.逻辑D.物理和存储3.算法分析的目的是（）。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.下列函数中渐进时间复杂度最小的是（）A．Tn=logC.Tn=n9.下面程序的时间复杂度是（）for(inti=0;i<m;i++)for(intj=0;j<n;j++)a[i][j]=i*j;A.O(n2)B.O(m*n)C.O(10.某算法的时间复杂度为O(n2A．问题规模是n2B.执行时间等于C．执行时间与n2成正比D.问题规模与n三、分析题阅读下列算法：Voidsuan-fa(intn){inti，j，k，s，x；for(s=0,i=0;i<n;i++)for(j=i;j<n;j++)s++;i=1;j=n;x=0;while(i<j){i++；j--；x+=2；}Printf(s=“%d”,x=“%d”，s，x)；}分析算法中语句“s++”的执行次数；分析算法中语句“x+=2”的执行次数；分析算法的时间复杂度；假定n=5;试写出执行该算法的输出结果。四、简答题1.简述将一个现实问题转化为可用计算机解决的问题的过程。2.简述构建或使用函数应关注哪些属性。3.当你为解决某一问题而选择数据结构时，应从哪些方面考虑？答：通常考虑算法运行所需要的存储空间量和时间量。后者又涉及三方面：程序运行时所需输入的数据总量，计算机执行每条指令所需时间和程序中指令重复执行的次数。4.设有数据逻辑结构S=（D，R），试按各小题所给条件画出这些逻辑结构的图示，并确定相对应关系R，哪些结点是开始结点，哪些结点是终端结点。（1）D={d1，d2，d3，d4}R={（d1，d2）,（d2，d3）,（d3，d4）}（2）D={d1，d2，，d9}

R={（d1，d2），（d1，d3），（d3，d4），（d3，d6），（d6，d8），（d4，d5），（d6，d7），（d8，d9）}（3）D={d1，d2，，d9}R={（d1，d3），（d1，d8），（d2，d3），（d2，d4），（d2，d5），（d3，d9），（d5，d6），（d8，d9），（d9，d7），（d4，d7），（d4，d6）}第二章习题一、判断题（）1.线性表中每个元素都有一个直接前驱和一个直接后继。（）2.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（）3.线性表的物理存储空间中也一定是连续的。（）4.顺序表结构适合于进行顺序存取，而链表适合于进行随机存取。（）5.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（）6.链表的物理存储结构具有与链表表达的逻辑结构一样的顺序。（）7.链表的每个结点中都恰好包含一个指针。（）8.带头结点的单循环链表中，任一结点的后继结点的指针域均不为空。（）9.在单链表中，要访问某个结点，只要知道该结点的指针即可，因此，单链表是一种随机存取结构。（）10.在具有头结点的链式存储结构中，头指针指向链表中的第一个数据结点。二、选择题A.存储结构B.逻辑结构C.顺序存储结构D.链式存储结构2.一个向量的第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。A.110

B.108C.100

D.1203.在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（）。A.访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B.在第i个结点后插入一个新结点（1≤i≤n）C.删除第i个结点（1≤i≤n）D.将n个结点从小到大排序4.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。A.8

B.63.5C.63

D.75.链接存储的存储结构所占的存储空间（）。A.分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B.只有一部分，存放结点值C.只有一部分，存储表示结点间关系的指针D.分两部分，一部分存放结点值，另一部分存放结点所占单元数6.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续或不连续都可以7.线性表L在（）情况下适合使用链式结构实现。A.需经常修改L中的结点值

B.需不断对L进行删除插入C.L中含有大量的结点D.L中结点结构复杂8.在非空双向循环链表（结点指针域分别为pre和next）中q所指的结点前插入一个由p所指的链结点的过程依次为（）。A.q−>pre=p;p->next=q;B.t=q−>pre;t->next=p;p->next=q;C.t=q−>pre;t->next=p;p->pre=t;p->next=q;D.t=q−>pre;t->next=p;p->next=q;q->pre=p;p->pre=t;9.带头结点的单链表L为空的判定条件是（）。A.L==NULL

B.L−>next==NULLC.L−>next==L

D.L!=NULL10.设单循环链表中结点的结构为(data,next),且rear是指向非空的带头结点的单循环链表的尾结点的指针。若要删除链表的第一个结点，正确的操作是（）A．s=rear;rear=rear->next;free(s);B.rear=rear->next;free(s);C.rear=rear->next->next;free(s);D.s=rear->next->next;rear-next->next=s->next;free(s);三、填空题1.在顺序表中插入或删除一个元素，需要平均移动__________个元素，具体移动的元素个数与__________有关。2.在顺序表中访问任意一结点的时间复杂度均为__________，因此，顺序表也称为__________的数据结构。3.顺序表中逻辑上相邻的元素在物理位置上__________相邻，单链表中逻辑上相邻的元素在物理位置上__________相邻。4.5.在n个结点的单链表中要删除已知结点*p，须找到它的__________，其时间复杂度为__________。6.当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用存储结构。7.有一个无头结点的单链表，结点有数据域data,指针域next,表头指针为h,通过遍历链表，将链表中所有的链接方向逆转。要求逆转后的链表的表头指针h指向原链表的最后一个结点。算法如下所示，请在空格处填入正确的语句。VoidInverse(&h){Ifreturn;p=h->next;pr=NULL;while{h->next=pr;pr=h;h=p;;}h->next=pr;}8.对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为，在给定值为x的结点后插入一个新结点的时间复杂度为。四、简答题1.试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？2.描述以下三个概念的区别：头指针、头结点、首元结点（第一个元素结点）。在单链表中设置头结点的作用是什么？3.阅读下面的算法，说明算法实现的功能。Node*link(node*head1,*head2){Node*p,*q;P=head1;While(p->next!=head1)p=p->next;q=head2；while（q->next!=head2）q=q->next;p->next=head2;q->next=head1;return(head1);}4.请简要说明下列函数的主要功能。voidfunc(LinkListL1,LinkListL2){LNode*p,*q,*r;q=L2->next;while(q){P=L1;while(p->next){if(p->next->data==q->data){r=p->next;p->next=r->next;free(r);}p=p->next；}q=q->next；}return；}五、算法设计题1.编写算法实现顺序表的按序号查找和按值查找。2.编写算法实现单链表的建立。3.编写算法实现单链表的按序号查找和按值查找。4.编写算法实现单链表逆置。5.已知带头结点的单链表有data和next两个域，设计一个算法，将该链表中的重复元素结点删除。第三章习题一、判断题（）1.在表结构中最常用的是线性表，栈和队列不常用。（）2.对于不同的使用者，一个表结构既可以是栈，又可以是队列，或是线性表。（）3.同一组不重复输入序列执行不同的入出栈组合操作，所得结果也可能相同。（）4.栈和队列是非线性数据结构。（）5.栈和队列的存储方式既可是顺序方式，又可是链接方式。（）6.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。（）7.队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出形式的结构。（）8.一个栈的输入序列是12345，则栈的输出序列不可能是12345。（）9.队列在程序调用时必不可少，因此递归离不开队列。（）10.设立尾指针的循环链表表示队列，则入队和出队算法的时间复杂度均为O(1)。二、选择题1.判定一个顺序栈ST（最多元素为m0）为空的条件是（）。A.ST->top<0B.ST->top=0C.ST->top<>m0

D.ST->top=m02.判定一个队列QU（最多元素为m0）为满队列的条件是（）。A.QU->rear－QU->front==m0B.QU->rear－QU->front－1==m0C.QU->front==QU->rearD.QU->front==QU->rear+13.数组Q［n］表示一个循环队列，f为当前队列头元素的前一位置，r为队尾元素的位置，假定队列中元素的个数小于n，计算队列中元素的公式为（）。A.r−fB.（n＋f−r）%nC.n＋r−f

D.（n＋r−f）%n4.向一个栈顶指针为top的链栈中插入一个S所指结点时，则执行（）。A.top->next=S;B.S->next=top->next;top->next=S;C.S->next=top;top=S;

D.S->next=top;top=top->next;5.若已知一个栈的入栈序列是1，2，3，，n，其输出序列为p1，p2，p3，，pn，若p1=n，则pi为（）。A.iB.n=iC.n−i+1

D.不确定6.有六个元素按照6、5、4、3、2、1的顺序进栈，问下列哪一个不是合法的出栈序列（）。A.543612B.453126C.346521D.2341567.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（）。A.1和5B.2和4C.4和2

D.5和18.为解决计算机主机与打印机之间的速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（）A.栈B.队列C.树D.图9.执行完下列语句段后，i值为（）intf(intx){return((x>0)?x*f(x-1):2);}inti;i=f(f(1));A.2B.4C.8D.1010.输入序列为ABC，可以变为CBA时，经过的栈操作为（）A.push,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop三、填空题1.线性表、栈和队列都是________结构，可以在线性表的________位置插入和删除元素；对于栈只能在________插入和删除元素；对于队列只能在________插入和________删除元素。2.栈是一种特殊的线性表，允许插入和删除运算的一端称为________，不允许插入和删除运算的一端称为________。3.________是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。4.在一个循环队列中，队头指针指向队头元素的________位置。5.在具有n个单元的循环队列中，队满时共有________个元素。6.向栈中压入元素的操作是先________后________。7.从循环队列中删除一个元素时，其操作是先________，后________。8.带表头结点的空循环双向链表的长度等于________。9.在循环队列中，队列长度为n,存储位置从0到n-1编号，以rear指示实际的队尾元素，现要在此队列中插入一个新元素，新元素的位置是________。10.用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1,2,3,4，则为了得到1,3,4,2的出栈顺序，相应的S和X操作串为。四、简答题1.说明线性表、栈与队列的异同点。2.顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？3.设循环队列的容量为40（序号从0～39），现经过一系列的入队和出队运算后，有：（1）front=11，rear=19;（2）front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？4.（1）什么是递归程序。（2）递归程序的优、缺点。（3）递归程序在执行时，应借助于什么来完成。（4）递归程序的入口语句、出口语句一般用什么语句实现。5.写出下列程序段的输出结果（队列中的元素类型QElemType为char）。voidmain（）{QueueQ;InitQueue（Q）;Charx=‘e’;y=’c’;EnQueue（Q,‘h’）;EnQueue（Q,‘r’）;EnQueue（Q,‘y’）;DeQueue（Q,x）;EnQueue（Q,x）;DeQueue（Q,x）;EnQueue（Q,‘a’）;while（!QueueEmpty（Q））{DeQueue（Q,y）;printf（y）;}Printf（x）;}6.简述以下算法的功能（栈和队列的元素类型均为int）。voidalgo3（Queue&Q）{StackS;intd;InitStack（S）;while（!QueueEmpty（Q））{DeQueue（Q,d）;Push（S,d）;while（!StackEmpty（S））{Pop（S,d）;EnQueue（Q,d）;}}五、算法设计题（可以仅写出算法思想，也可以用C语言函数实现）1.假设一个算术表达式中包含圆括号、方括号和花括号三种类型的括号，编写一个判别表达式中，括号是否正确配对的函数correct（exp）；其中，exp为字符串类型的变量（可理解为每个字符占用一个数组元素），函数用来判别该数学表达式是否正确。2.假设一个数组squ[m]存放循环队列的元素。若要使这m个分量都得到利用，则需另一个标志tag，以tag为0或1来区分尾指针和头指针值相同时队列的状态是“空”还是“满”。试编写相应的入队和出队的算法。第四章习题一、选择题1．设主串T=“abaabaabcabaabc”,模式串S=“abaabc”,采用KMP算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是（）A.9B.10C.12D.152.已知字符串S为“abaabaabacacaabaabcc”,模式串t为“abaabc”,采用KMP算法进行匹配，第一次出现“不匹配”时，i=j=5,则下次开始匹配时，i和j的值分别是（）。A.i=1,j=0B.i=5,j=0C.i=5,j=2D.i=6,j=23.下面关于串的叙述中，哪一个是不正确的（）。A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储4.若串S为“Myself”，则其子串的数目是（）A.20B.21C.22D.235.串是一种特殊的线性表，其特殊性体现在（）A.可以顺序存储B.数据元素是一个字符C.可以链接存储D.数据元素可以是多个字符二、填空题1.组成串的数据元素只能是。2.设正文串长度为n,模式串长度为m,则串匹配的KMP算法的时间复杂度为。3.设T和P是两个给定的串，在T中寻找等于P的子串的过程称为，又称P为。4.模式串P=’abaabcac’的next函数值序列为。5.使用“求子串”substring(S,pos,len)和“连接”concat(S1,S2)的串操作，可从串s=’conduction’中的字符得到串t=’cont’,则求t的串表达式为。6.设目标T=”abccdcdccbaa”，模式P=“cdcc”，则采用朴素匹配算法第次匹配成功。7.实现字符串拷贝的函数strcpy为voidstrcpy(char*s,char*t)/*copytos*/{while;}8.下列程序判断字符串s是否对称，对称则返回1，否则返回0,；如f(“abba”)返回1，f(“abab”)返回0。intf{inti=0,j=0;while(s[j]);for(j--;i<j&&s[i]==s[j];i++,j--);return;}三、应用分析题1.在字符串模式匹配的KMP算法中，求模式的next数组值的定义如下：next（1）当j=1时，为什么要取next[1]=0?（2）为什么要取max⁡{K}（3）其他情况是什么情况，为什么取next[j]=1?2.设字符串S='aabaabaabaac',P='abcabaa'。（1）计算S和P的next值。（2）若S作主串，P作模式串，试给出利用BF算法和KMP算法的匹配过程。四、算法设计题1.若X和Y是用结点大小为1的单链表表示的串，试设计一个算法找出X中第一个不在Y中出现的字符。2.试设计一个算法，在顺序串上实现串的比较运算strcmp（S，T）。3.若S和T是用结点大小为1的单链表存储的两个串，试设计一个算法将S中首次与串T匹配的子串逆置。第五章习题一、选择题1、设二维数组A[1..m,1..n]按行存储在数组B[1..m*n]中，则二维数组元素Ai,j在一维数组B中的下标为（A．i-1*n+jB.C.i*(j-1)D.j*m+i-12、设有一个12×12的对称矩阵M，将其上三角部分的元素mi,j1≤i≤j≤12按行优先存入C或Java语言的一维数组N中，那么元素m6,6A．50B.51C.55D.663、适用于压缩存储稀疏矩阵的两种存储结构是（）A．三元组表和十字链表B.三元组表和邻接矩阵C．十字链表和二叉链表D.邻接矩阵和十字链表4、对矩阵压缩存储是为了（）A．方便运算B.方便储存C.提高运算速度D.减少储存空间5、在稀疏矩阵的快速转置算法中，num[col]表示源矩阵M中（）A．第col行中非零元的个数B.第col行中零元的个数C．第col列中非零元的个数D．第col列中零元的个数6、对n阶对称矩阵作压缩存储时，需要表长为（）的顺序表。A．n/2B.n2/2C.n(n+1)/2D.n(n-1)/27、一个非空广义表的表尾（）A．不能是子表B.只能是子表C.只能是原子D.是原子或子表8、广义表（（））的表头是（）。A．（）B.NULLC.（（））D.（（（）））9、某字符串满足concat(head(s),head(tail(tail(s))))=”ac”,则s=().A.aabcB.acbaC.acccD.acac10、下面说法不正确的是（）A．广义表的表头总是一个广义表B.广义表的表尾总是一个广义表C．广义表难以用顺序存储结构D.广义表可以是一个多层次结构二、填空题1.数组的存储结构采用存储方式。2.二维数组A[10..20,5..10]采用行序为主序方式存储，每个数据元素占4个存储单元，且[10,5]的存储地址是1000，则A[18,9]的存储地址是。3.对于数组An*n,每个数组元素所占存储单元数为L，其元素aij按行优先与按列优先存储时地址之差为4.有一个10阶对称矩阵A，采用压缩存储方式（下三角），以行序为主序，且A[0][0]=1,每个元素占1个单元，则A[8][5]的地址为。5.已知三对角矩阵A[1..9,1..9]的每个元素占2个单元，现将其三条对角线上的元素逐行存储在起始地址为1000的连续内存单元中，则元素A[7,8]的地址为。6.广义表（A，B，C，D）的表尾是。7.设有广义表LS=（（a,b,c）,(d,e,f)）,取出原子e的运算是。8.广义表A（b,A）的长度为，深度为。9、广义表(a,(a,b),d,e,((i,j),k))的长度是，深度是。10.已知广义表A=(((a,b),(c),(d,e))),head(tail(tail(head(A))))的结果是。三、分析题1.按行优先顺序列出四维数组A[2][3][2][3]所有元素在内存中的存放次序。2.作出矩阵X的三元组表和十字链表。四、算法设计题1、若在矩阵中存放一个元素A[i−1][j−1]满足：A[i−1][j−1]是第i行元素中的最小值，且又是第j列元素中的最大值，则称此元素为该矩阵的一个马鞍点。假设以二维数组存储矩阵，试编写求矩阵中所有马鞍点的算法，并分析该算法在最坏情况下的时间复杂度。2、给定n×m矩阵Aa..b,c..d,并设Ai,j≤A[i,j+1](a≤i≤b,c≤j≤d-1)和A第九章一、1.D2．B3．A4.B5.A6.D7.A8.B9.D10.C二、填空题1.顺序查找2.83.1、2、8、3.74.28,6,12,205.散列查找6.关键字的值7.n(n-1)28.2.9、2.9、2.2、1.29.有时不相同10.11