《数据结构》课后题及答案.doc 62页

'第一章　绪论一、选择题1、()是数据的基本单位。 A)数据结构　　B)数据元素　　C)数据项　　　D)数据类型2、以下说法不正确的是()。 Ａ)数据结构就是数据之间的逻辑结构。 Ｂ)数据类型可看成是程序设计语言中已实现的数据结构。Ｃ)数据项是组成数据元素的最小标识单位。 Ｄ)数据的抽象运算不依赖具体的存储结构。3、计算机算法是解决问题的有限运算序列,它具备输入、输出和（　　）等5个特性。A)可执行性、可移植性和可扩充性　　　　B)可行性、确定性和有穷性C)确定性、有穷性和稳定性　　　　　　D)易读性、稳定性和安全性4、一般而言，最适合描述算法的语言是()。A)自然语言B)计算机程序语言C)介于自然语言和程序设计语言之间的伪语言D)数学公式5、通常所说的时间复杂度指()。A)语句的频度　　B)算法的时间消耗C)渐近时间复杂度　　D)最坏时间复杂度6、A算法的时间复杂度为O(n3)，B算法的时间复杂度为O(2n)，则说明()。 A)对于任何数据量，A算法的时间开销都比B算法小 B)随着问题规模n的增大，A算法比B算法有效 C)随着问题规模n的增大，B算法比A算法有效 D)对于任何数据量，B算法的时间开销都比A算法小7、算法分析的目的是（）。A)找出数据结构的合理性　　　　B)研究算法中的输入和输出的关系C)分析算法的效率以求改进　　　D)分析算法的易懂性和文档性8、下面程序段的时间复杂度为（）。for(i=0;inext=HL;　　　B)p->next=HL;HL=p;C)p->next=HL;p=HL;　　　D)p->next=HL->next;HL->next=p;13、在一个单链表HL中，若要在指针q所指的结点的后面插入一个由指针p所指的结点，则执行()。A)q->next=p->next;p->next=q;　　B)p->next=q->next;q=p;C)q->next=p->next;p->next=q;　　D)p->next=q->next;q->next=p;14、在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行()。A)p=q->next;p->next=q->next;　B)p=q->next;q->next=p;C)p=q->next;q->next=p->next;　D)q->next=q->next->next;q->next=q;15、在双向链表中，在指针p所指的结点前插入一个指针q所指的结点，操作是（）。A)p->Prior=q;　q->Next=p;　p->Prior->Next=q;　q->Prior=q；B)p->Prior=q;　p->Prior->Next=q;　q->Next=p;　q->Prior=p->Prior;C)q->Next=p;　q->Prior=p->Prior;　p->Prior->Next=q;　p->Prior=q;D)q->Prior=p->Prior;　q->Next=q;　p->Prior=q;　p->next=q;一、填空题99 1、对于一个具有n个结点的单链表，在已知结点*p的后插入一个新结点的时间复杂度为（　　　　　）,在给定值为x的结点后插入一个新结点的时间复杂度为（　　　　）。2、根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成（　　　　　　）和（　　　　　　　）。3、顺序存储结构是通过()表示元素之间的关系的;链式存储结构是通过()表示元素之间的关系的。4、对于双向链表,在两个结点之间插入一个新结点需修改()个指针，单链表为()个。5、循环单链表的最大优点是(　)。6、在无头结点的单链表中，第1个结点的地址存放在头指针中，其他结点的存储地址存放在(　　　)结点的next域中。7、带头结点的双循环链表L为空表的条件是（　　　　　　　　　　　　）。8、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用(　　　)存储结构。9、求顺序表和单链表的长度算法的时间复杂度分别是(　　　)和(　　　)。10、顺序表存储结构的优点是()、()、()；缺点是()。11、单链表存储结构的优点是()、()；缺点是()、()。12、在单链表中，设置头结点的作用是()。13、链接存储的特点是利用()来表示数据元素之间的逻辑关系。14、带头结点的双循环链表DL为空表的条件是：()。15、以下算法的功能是：在一个非递减的顺序表中，删除所有值相等的多余元素。在画线处填上适当的语句，将程序补充完整。#definemaxlen100typedefstruct{elemtypea[maxlen];intlength;}sqlist;voiddelequil(sqlist&S){intj=1,i=2;while(_________________){if(S.a[i]!=S.a[j]){____________;______________;}i++;}______________;}16．设双链表的结点的存储结构如下：删除链表中指针p所指结点的两步主要操作是：LlinkDataRlinkp99 ()，()。一、问答题与算法题1、试描述头指针、头结点、首结点的区别、并说明头指针和头结点的作用。2、何时选用顺序表、何时选用链表作为线性表的存储结构为宜?3、为什么在单循环链表中设置尾指针比设置头指针更好?4、下述算法的功能是什么?LinkListABC(LinkListL){//L是无头结点单链表　if(L&&L->next){Q=L;L=L->next;P=L;　　while(P->next)P=P->next;　　P->next=Q;Q->next=NULL;　}　returnL;　　}5、写出下图双链表中对换值为23和15的两个结点相互位置时修改指针的有关语句。结点结构为：(prior,data,next)6、VoidAA(SqList&L,inti,intx){if(i>=1&&i<=Length(L)){FOR(j=Length(L);j>=i;j--)A[j+1]=A[j];A[i]=x;}elseexit(ERROR);}99 假定调用该算法时线性表L的内容为（15，26，37，48，55），i为3,x为51，则调用返回后该单链表的内容变为什么?7、重写建立单连表的算法CreatList_L(Linklist&L,intn)，要求顺序输入n个元素的值(即先输入a1,a2…..).CreatList_L(LinkList&L；intn)8、设顺序表L是一个递减有序表，试写一算法，插入元素x，插入后仍保持L的有序性。Voidsinsert(Sqlist&S,intx)9、写一算法，在带头结点的单链表上实现线性表的求表长ListLength(L)运算。intListLength(LinkListL)10、写出从一个带头结点的单链表中删除其值等于给定值x的结点的算法函数。Intdelete(LinkList&L,intx){99 11、已知递增有序的两个带头结点的单链表La，Lb分别存储了一个非空集合A,B。设计算法实现求两个集合的并集的运算A=A∪Bvoidmergelist(linklist&La,linklistLb)12、设计算法将不带表头结点的单向链表就地逆转。13、删除整数数组中值相等的多余整数(只保留第一次出现的那个整数)。VoiddelDuplicate(intA[]，int&n)99 第三章栈和队列一、选择题1、对于栈，操作数据的原则是（）。A)先进先出B)后进先出C)后进后出D)不分顺序2、一般情况下，将递归算法转换成非递归应通过设置（　　）实现。A)数组；　　　B)线性表；　　　C)队列；　　　　D)栈。3、栈和队列的共同点是（）A)都是先进后出　　　B)都是先进先出C)只允许在端点处插入和删除元素　　D)没有共同点4、若栈的入栈序列是abcde，则栈的不可能的输出序列是(　　　)。 A)edcbaB)decbaC)dceabD)abcde5、在对栈的操作中，能改变栈的结构的是(　　)。 A)StackLength(S) B)StackEmpty(S)C)GetTop(S)D)ClearStack(S)6、在一个栈顶指针为HS的链栈中将一个S指针所指的结点入栈,执行(　　　)。 A)HS->next=s; 　　B)S->next=HS->next;HS->next=s; C)S->next=HS;HS=s; 　　　D)S->next=HS;HS=HS->next;7、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列是p1,p2,p3，…，pn，若p1=n，则pi=(　　)。 A)I　　　　　B)n-i　　　　C)n-i+1　　　　　　D)不确定8、若用一个大小为６的数组来实现循环队列，且当前尾指针rear和头指针front的值分别为０和３，当从队列中删除一个元素，再加入两个元素后，尾指针rear和头指针front的值分别是（　　　）。A)１和５；　　　B)２和４；　　C)４和２；　　　D)５和１。9、要使输入序列为ABC变为序列BAC时，使用的栈操作序列为（）A)push,pop,push,pop,push,popB)push,push,push,pop,pop,popC)push,push,pop,pop,push,popD)push,pop,push,push,pop,pop10、设用一个大小m=60的顺序表A［m］表示一个循环队列，如果当前的尾指针rear=32，头指针front＝15,则当前循环队列的元素个数是(　　)。A)42；　　　B)16；　　　C)17；　　　　　D)41。11、设用顺序表a[n]表示循环队列，头、尾指针分别为front和rear，则判断队列为空的条件是（　　），判断队列满的条件是（　　）。（1）A)a.front+1==a.rear；　　　　　B)a.front==a.rear+1；C)a.front==0；　　　D)a.front==a.rear。（2）A)(a.rear-1)%n=a.front；　　B)(a.rear+1)%n=a.front；C)a.rear=(a.front-1)%n；　D)a.rear=(a.front+1)%n。12、循环队列存储在数组A[0..m]中，则入队时的操作为（）。A)rear=rear+1B)rear=(rear+1)mod(m-1)C)rear=(rear+1)modmD)rear=(rear+1)mod(m+1)13、在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印，该缓冲区应该是一个（　　）结构。A)栈；　　　B)队列；　　C)数组；　　D)线性表。14、设栈用向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确99 操作是()。A．V[++top]=x;B.V[top++]=x;C.V[--top]=x;D.V[top--]=x;15、若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈(i=1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。A.|top[2]-top[1]|=0B.top[1]+1=top[2]C.top[1]+top[2]=mD.top[1]=top[2]16.表达式a*(b+c)-d的后缀表达式是()。【南京理工大学2001一、2（1.5分）】A．abcd*+-B.abc+*d-C.abc*+d-D.-+*abcd一、填空题1、在栈中，可进行插入和删除操作的一端称()。2、在作进栈运算时,应先判别栈是否(　),在作退栈运算时应先判别栈是否(　　)。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(　　　)。3、栈的特点是(　　　)，队列的特点是（　　　　）。4、由于链栈的操作只在链表头部进行，所以没有必要设置(　　　)结点。5、带头结点的单链表L是空表的条件是（）；顺序栈S是空栈的条件是（）；顺序栈S满的条件是（）；不带头结点的链栈L是空栈的条件是（）；循环队列Q是空队列的条件是（）；循环队列Q是满队列的条件是（　）6、用数组Q（其下标在0…n-1之间，共有n个元素）表示一个循环队列，front为当前队头元素的前一个位置，rear为队尾元素的位置，假设队列中的元素个数总小于n，则求队列中元素个数的公式是（　　　　　　　　　　　）。7、设元素入栈的顺序是１、２、3、…、n，则所有可能的出栈序列共有（　　　　）种。8、在具有n个单元的循环队列中，队满时共有（　　　　　　）个元素。9、设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是()，而栈顶指针值是()H。(设栈为顺序栈，每个元素占4个字节)10、用PUSH表示入栈操作，POP表示出栈操作，若元素入栈的顺序为1234，为了得到1342的出栈顺序，相应的PUSH和POP的操作串为()。二、问答题与算法题1、设将整数1，2，3，4依次进栈，若入、出栈次序为Push(s,1),Pop(s,x1),Push(s,2),Push(s,3),Pop(s,x2),Pop(s,x3),Push(s,4),Pop(s,x4),则出栈的数字序列为何?2、设用不带头结点的单链表表示栈，请分别写出入栈和出栈的算法。(1)intpush_L(Linkstack&sSelemTypee)99 (2)intpop_L(Linkstack&sSelemType&e)3、假设用带头结点的单循环链表表示队列，并设置一个指向尾结点的指针（无头指针），请分别写出队列的入队和出队算法。(1)intEnQueue_L(Queueptr&QLQelemTypee)(2)intDeQueue_L(Queueptr&QLQelemType&e)4、指出下述程序段的功能是什么? (1)voidabc1(Stack　&S){　　inti，arr[64],n=0;　　while(!StackEmpty(S)){Pop(S，e);arr[n++]=e};for(i=0,idata);p=p->next;}p=L;//利用原来的链表只修改数据域的值（反序）while(!stackempt(S)){pop(S,e);p->data=e;p=p->next;}returnOK;}5、回文是指正读反读均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不是回文。试写一个算法判定给定的用带头结点的单链表表示的字符串是否为回文。 Inthw1(linklistL)99 6、写一个将不带头结点的链栈S中所有结点均删去的算法voidClearStack(LinkStack&S)。7、写一个返回不带头结点的链栈S中结点个数的算法.intStacksize(LinkStackS)。8、利用栈操作，写一个算法把一个不带头结点的链表的元素反序存放（同第二章12题，这里要求利用栈操作）。voidinvert2(LinkList&L)。9、试将下列递归过程改写为非递归过程。voidtest(int&sum){intx；scanf(x)；if(x=0)sum=0else{test(sum);sum+=x;}printf(sum)；}99 10、从键盘上输入一个逆波兰表达式，用伪码写出其求值程序。规定：逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔,操作符只可能有+、-、*、/四种运算。例如：23434+2*$第四章串一、选择题1、串是一种特殊的线性表，其特殊性体现在(　)。 A)可以顺序存储　　B)数据元素是一个字符C)可以链接存储　　D)数据元素可以是多个字符2、有两个串P和Q，求P在Q中首次出现的位置的运算称(　　)。 A)模式匹配　　B)连接　C)求子串　　D)求串长3、设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身）的个数为（）。A）n2B）(n2/2)+(n/2)C）(n2/2)+(n/2)-1D）(n2/2)-(n/2)-14、设串s1="ABCDEFG",s2="PQRST",函数concat(x,y)返回x和y串的连接串，subString(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，Strlength(s)返回串s的长度，则concat(subString(s1,2,Strlength(s2)),subString(s1,Strlength(s2),2)))的结果串是()。A)BCDEF　　B)BCDEFG　　C)BCPQRST　　　D)BCDEFEF5、顺序串中，根据空间分配方式的不同，可分为()。 A)直接分配和间接分配 B)静态分配和动态分配 C)顺序分配和链式分配 D)随机分配和固定分配6、设串S=”abcdefgh”，则S的所有非平凡子串（除空串和S自身的串）的个数是（）。A)8；B)37；C)36；D)35。7、设主串的长度为n，模式串的长度为m，则串匹配的KMP算法时间复杂度是（）。A)O(m)；B)O(n)；C)O(m+n)；D)O(n*m)。8、已知串S=‘aaab’,其Next数组值为（）。A．0123B．1123C．1231D．1211二、填空题1、在空串和空格串中，长度不为0的是()。2、空格串是指()，其长度等于()。3、按存储结构不同，串可分为()、（）、（）。99 4、C语言中，以字符(　　)表示串值的终结。5、在块链串中，为了提高存储密度，应该增大().6、假设每个字符占1个字节，若结点大小为4的链串的存储密度为50%，则其每个指针占(　)个字节。7、串操作虽然较多，但都可通过五种操作（）、（）、（）、（）、（）构成的最小子集中的操作来实现。8、设串S=’Ilikecomputer.’，T=’com’，则Length(S)=（）。Index(S,T,1)=()9、在KMP算法中，next[j]只与（）串有关，而与（）串无关。10、字符串’ababaaab’的nextval函数值为（）。11、两个字符串相等的充分必要条件是（）。12．实现字符串拷贝的函数strcpy为：voidstrcpy(char*s,char*t)/*copyttos*/{while(________)；}一、问答题与算法题1、简述下列每对术语的区别：空串和空格串：串常量和串变量：主串和子串：目标串和模式串。2、在C语言中假设有如下的串说明：　chars1[30]="Stocktom",s2[30]="March51999",s3[30],　(１)在执行下列语句后，s3的值是什么?strcpy(s3,s1);strcat(s3,",");strcat(s3,s2);　(２)调用函数strcmp(s1,s2)的返回值是什么?　(３)调用函数strcmp(s1[5],"Ton")的返回值是什么?　(４)调用函数strlen(strcat(s1,s2))的返回值是什么?３、利用C的库函数strlen,strcpy和strcat写一算法voidStrInsert(char*S,char*T,inti),将串T插入到串S的第i个位置上。若i大于S的长度，则插入不执行。voidStrInsert(char*S,char*T,inti)99 4、利用C的库函数strlen和strcpy(或strcpy)写一算法voidStrDelete(char*S,inti,intm)删去串S中从位置i开始的连续m个字符。若i≥strlen(S),则没有字符被删除；若i+m≥strlen(S),则将S中从位置i开始直至末尾的字符均删去。voidStrDelete(char*S,inti,intm)//串删除5、若S和T是用结点大小为1的带头结点的单链表存储的两个串，试设计一个算法找出S中第一个不在T中出现的字符。　Intindexst(LinkListS,linkLintT)　6、在KMP算法中，求下列模式串的next[j]。（1）‘abaabcac’（2）’aaabaaba’99 7、设目标为t=‘abcaabbabcabaacbacba’,模式为p=‘abcabaa’（1）计算模式p的naxtval函数值；（2）不写出算法,只画出利用KMP算法进行模式匹配时每一趟的匹配过程。11．写一个递归算法来实现字符串逆序存储，要求不另设串存储空间。第五章数组与广义表一、选择题1、稀疏矩阵的一般压缩方法是()。 A)二维数组B)广义表C)三元组表D)一维数组2、设矩阵A是一个对称矩阵，为了节省空间，将其下三角部分按行优先存放在一维数组B中。对下三角矩阵中任一元素aij(i>=j)，在一维数组B中下标ｋ的值是(　)。 A)i(i-1)/2+j-1　B)i(i-1)/2+jC)i(i+1)/2+j-1D)i(i+1)/2+j3、在稀疏矩阵的三元组表示法中，每个三元组表示()。 A)矩阵中数据元素的行号、列号和值B)矩阵中非零元素的值 C)矩阵中非零元素的行号和列号D)矩阵中非零元素的行号、列号和值4、对稀疏矩阵进行压缩存储是为了(　)。 A)便于进行矩阵运算B)便于输入和输出C)节约存储空间D)降低运算的时间复杂度5、99 假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（）。A）808B）818C）1010D）10206、设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为()。A）BA+141B）BA+180C）BA+222D）BA+2257、广义表是线性表的推广，它们之间的区别在于(　　)。 A)能否使用子表　B)能否使用原子项 C)表的长度 　D)是否能为空8、已知广义表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）））)）9、已知广义表:A=(a,b),B=(A,A),C=(a,(b,A),B),下列运算的结果是:tail(head(tail(C)))=()。A）（a）B）AC）aD）(b)E）bF）(A)10、广义表运算式Tail(((a,b),(c,d)))的操作结果是（）。A）()B）c,dC）((c,d))D）d11、广义表（（a,b,c,d））的表头是（），表尾是（）。A）aB）（）C）（a,b,c,d）D）（b,c,d）12、设广义表L=（（a,b,c）），则L的长度和深度分别为（）。A）1和1B）1和3C）1和2D）2和313、下面说法不正确的是()。A）广义表的表头总是一个广义表B）广义表的表尾总是一个广义表C）广义表难以用顺序存储结构D）广义表可以是一个多层次的结构14、已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是()。A）head(tail(LS))B）tail(head(LS))C）head(tail(head(tail(LS)))D)head(tail(tail(head(LS))))15、设一个广义表中结点的个数为n，则求广义表深度算法的时间复杂度为()。A)O(1)B)O(n)C)O(n2)D)O(log2n)一、填空题1、n维数组中的每个元素都最多有()个直接前趋。2、对于一个一维数组A[12]，若一个数据元素占用字节数为S，首地址为1，则A[i](i>=0)的存储地址为()，若首地址为d，则A[i]的存储地址为()。3、已知二维数组A[m][n]采用行优先顺序存储，每个元素占k个存储单元，并且第一个元素的存储地址LOC（A[0][0]），则A[i][j]的地址是()。4、多维数组中，数据元素的存放地址直接可通过地址计算公式计算出。因此，数组是一种()存取结构。5、矩阵的压缩存储就是为多个相同的非零元素分配()个存储空间，零元素不分配空间。6、递归是算法设计的重要方法，递归由（）项和（）项构成。用递归的方法求广义表LS的深度DEPTH(LS)，写出基本项和递归项。基本项：99 递归项：7、广义表(a,(a,b),d,e,((i,j),k))的长度是（），深度是（）。8、广义表((a),((b),c),(((d))))的长度是（），深度是（）。9、设广义表S=((a,b),(c,d))，GetHeat(S)和GetTail(S)是取广义表的表头和表尾函数。则GetHeat(GetTail(S))=()，GetTail(GetHeat(S))=()。10、设广义表S=(a,b,(c,d),(e,(f,g)))，GetHeat(S)和GetTail(S)是取广义表的表头和表尾函数。则GetHeat(GetTail(GetHeat(GetTail(GetTail(S)))))=()11、二维数组a[4][5][6]（下标从0开始计，a有4*5*6个元素），每个元素的长度是2，则a[2][3][4]的地址是()。(设a[0][0][0]的地址是1000,数据以行为主方式存储)12、设有二维数组A[0..9,0..19],其每个元素占两个字节，第一个元素的存储地址为100，若按列优先顺序存储，则元素A[6,6]存储地址为()。13、己知三对角矩阵A[1..9,1..9]的每个元素占2个单元，现将其三条对角线上的元素逐行存储在起始地址为1000的连续的内存单元中，则元素A[7,8]的地址为()。14、广义表A=（（（a，b），（c，d，e））），取出A中的原子e的操作是（）。15、设广义表A(((),(a,(b),c)))，则head(tail(head(tail(head(A))))=（）。一、问答题与算法题１、给出C语言的三维数组A[m][n][s]地址计算公式。２、设有三对角矩阵An╳n=，将其三条对角线上的元素逐行地存储到向量B[0...3n-3]中，使得B[k]=aij,求：　　(1)用i,j表示k的下标变换公式。(2)用k表示i,j的下标变换公式。３、设二维数组A5╳6的每个元素占4个字节，已知Loc(a00)=1000，A共占多少个字节?A的终端结点A45的起始地位为何?按行和按列优先存储时，A25的起始地址分别为何?99 4、已知一个稀疏矩阵如下图所示：0400000000-3001800000000050000-7000200006000(1)写出它的三元组顺序存储表示；(2)给出它的行逻辑链接的顺序存储表示； 5、画出下列广义表的图形表示：(1)A=((a,b),(c,d))(2)B=(a,(b,(c,d)),(e))6、画出广义表LS=((),(e),(a,(b,c,d)))的头尾链表存储结构。99 7、画出广义表LS=(((b,c),d),(a),((a),((b,c),d)),e,())的具有共享结构的存储表示。8、设广义表LS=(soldier,(teacher,student),(worker,farmer))，用取表头函数GetHead()和取表尾函数GetTail()分离出原子student。9、画出下列矩阵的十字链表10、设任意n个整数存放于数组A(1:n)中，试编写程序，将所有正数排在所有负数前面（要求算法复杂性为0(n)）。第六章　树和二叉树一、选择题1、设高度为h的二叉树只有度为0和2的结点，则此类二叉树的结点数至少有（B）个，至多有（E）个。A)2h；B)2h-1；C)2h+1；D)2h-1；E)2h-1；F)2h+1。2、高度为h的完全二叉树至少有（D）个结点，至多有（B）个结点。A)2h；B)2h-1；C)2h+1；D)2h–1。3、具有n个结点的满二叉树有（）个叶结点。A)n/2；B)(n-1)/2；C)(n+1)/2；D)n/2+1。4、一棵具有n个叶结点的哈夫曼树，共有（）个结点。A)2nB)2n-1C)2n+1D)2n-1；99 5、一棵具有25个叶结点的完全二叉树最多有（）个结点。A)48；B)49；C)50；D)51。6、已知二叉树的前序遍历序列ABCDEF,中序遍历序列CBAEDF,则后序遍历序列是（）。A．CBEFDAB．FEDCBAC．CBEDFAD．不定７、已知二叉树的中序遍历序列是debac，后序遍历序列是dabec，则前序遍历序列是（）。A)acbed；B)decab；C)deabc；D)cedba。8、在线索化二叉树中，t所指结点没有左子树的充要条件是（）。A)t->left=nullB)t->ltag=1C)t->ltag=1且t->left=nullD)以上都不对9、如图所示的4棵二叉树中，（）不是完全二叉树。ABCD10、算术表达式a+b*（c+d/e）转为后缀表达式后为（）A．ab+cde/*B．abcde/+*+C．abcde/*++D．abcde*/++11、设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为（）个。A．5B．6C．7D．812、设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。A．M1B．M1+M2C．M3D．M2+M313、具有10个叶结点的二叉树中有（）个度为2的结点，A．8B．9C．10D．ll14、一个具有1025个结点的二叉树的高h为（）A．11B．10C．11至1025之间D．10至1024之间15、对于前序遍历与中序遍历结果相同的二叉树为（）;对于前序遍历和后序遍历结果相同的二叉树为（）的二叉树。A．空二叉树B．只有根结点C．根结点无左孩子D．根结点无右孩子E．空二叉树或所有非叶结点只有左子数F．空二叉树或所有非叶结点只有右子树16、．一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）A．所有非叶结点均无左孩子B．所有非叶结点均无右孩子C．只有一个叶子结点D．A和B同时成立17、某二叉树的中序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。A．空或只有一个根结点B．任一非叶结点无左子树C．高度等于其结点数D．任一非叶结点无右子树18、线索二叉树是一种（）结构。A．逻辑B．逻辑和存储C．物理D．线性19、n个结点的线索二叉树上含有的线索数为（）A．2nB．n－lC．n＋lD．n20、由3个结点可以构造出多少种不同的二叉树？（）A．2B．3C．4D．599 二．填空题1、含有100个结点的树有()条边。2、一棵二叉树有67个结点，结点的度要么是0，要么是2。这棵二叉树中度为2的结点有()个。3、含A、B、C三个结点的不同形态的树有（　　）棵，不同形态的二叉树有（　　）棵。4、一棵含有n个结点的2叉树，可能达到的最大深度是（）和最小深度是（）。5、一棵哈夫曼树有19个结点，则其叶子结点的个数是()。6、设二叉树的中序遍历序列是：ABCDEFG，后序遍历序列是：BDCAFGE。则该二叉树的前序遍历序列是：（　　　　　），该二叉树的对应的森林包含（　　　）棵树。7、将一棵有50个结点的完全二叉树从根结点开始，由根向下，每一层从左至右，顺序地存储在一个一维数组bt[1..50]中，这棵二叉树最下面一层上最左边一个结点存储在数组元素()中。8、已知一棵树T的边集为{（I，M），（I，N），（E，I），（B，E），（B，D），（C，B），（G，J），（G，K），（A，G），（A，F），（H，L），（A，H），（C，A）}。则该树的根结点是（　　）、叶结点是：（　　　　　　　　　）、树的深度是：（　　）。9、已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有（　　）个叶子结点。10、一棵有n个结点的满二叉树有（）个度为1的结点、有（）个分支（非终端）结点和（）个叶子，该满二叉树的深度为（）。11、．设F是由T1,T2,T3三棵树组成的森林,与F对应的二叉树为B,已知T1,T2,T3的结点数分别为n1,n2和n3则二叉树B的左子树中有（）结点，右子树中有（）个结点。12、含4个度为2的结点和5个叶子结点的完全二叉树，可有（　　）个度为1的结点。13、一棵树T中，包括一个度为1的结点，两个度为2的结点，三个度为3的结点，四个度为4的结点和若干叶子结点，则T的叶结点数为（　　）。14、n（n大于1）个结点的各棵树中，其深度最小的那棵树的深度是（　　）。它共有（　　）个叶子结点和（　　）个非叶子结点，其中深度最大的那棵树的深度是（　　），它共有（　　）个叶子结点和（　　）个非叶子结点。15、已知二叉树前序为ABDEGCF，中序为DBGEACF，则后序一定是（　　）。16、有数据WG={7，19，2，6，32，3，21，10}，则所建Huffman树的树高是（　　），带权路径长度WPL为（　　）。17、现有按中序遍历二叉树的结果为abc，问有（　　）种不同的二叉树可以得到这一遍历结果。18、．一个无序序列可以通过构造一棵（　　）树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。19、先根次序遍历森林正好等同于按（　　）遍历对应的二叉树；后根次序遍历森林正好等同于（　　）遍历对应的二叉树。20、有一份电文中共使用6个字符:a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9，则字符c的哈夫曼编码是（），电文的编码总长度为（）。问答题与算法题１、voidABC(BiTreeBT){if(BT==NULL)return;ABC(BT->lchild);Printf(“%c”,BT->data);99 ABC(BT->rchild);}该算法的功能是______________________________________请模仿写出另外两个类似此算法的算法，并标明这两个算法的功能。2、写出下列算法的功能．VoidLevelOrderTraverse(BiTreeT,Status(*vist)(TelemTypee)){InitQueue(Q);EnQueue(Q,T);While(!QueueEmpty(Q)){DeQueue(Q,p);if(Visit(p->data))returnERROR;if(p->lchild)EnQueue(Q,p->lchild);if(p->rchild)EnQueue(Q,p->rchild);}returnOK;}3、写出下列算法的功能．StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TelemType(e))){InitStack(S);Push(S,T);While(!StackEmpty(Q)){Pop(S,p);if(Visit(p->data))returnERROR;if(p->rchild)Push(S,p->rchild);if(p->lchild)Push(S,p->lchild);}returnOK;}4、写出下列算法的功能．voidABC(BiTreeBT,int&c1,int&c2){if(BT!=NULL){ABC(BT->lchild,c1,c2);c1++;if(BT->lchild==NULL&&BT->rchild==NULL)c2++;ABC(BT->rchild,c1,c2);99 }}5、已知二叉树T的数据域均为正数，写一个算法求数据域的最大值。Intmaxdata(BitreeT)6、已知非空二叉树T的数据域均为字符型数据，数据域的值是’A’只有一个结点，写一个算法求这个结点的双亲。CharParent(BitreeT)7、已知非空二叉树T，写一个算法求两度点的个数。8、用递归方法写一个算法求二叉树的叶子数intLeafnum(BiTreeT),先写出基本项和归纳项，然后写算法9、写一个算法求二叉树的深度intDepth(BiTreeT)99 10、写一个算法交换二叉树所有结点的左右子树StatusChangchild(BiTreeT)11、试分别画出具有3个结点的有序树和3个结点的二叉树的所有不同形态。12、一棵有11个结点的二叉树的静态链表存储结构如下表。67852mfakblcrdse9104111Lift[i]Data[i]Right[i]画出该二叉树，将此二叉树转化为树或森林。13、已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树，并画出它的后序线索二叉树。99 14、对于n个结点的完全二叉树，用1~n的连续整数顺序编号，试回答下列问题：（1）它共有多少层？各层的结点数分别是多少？（2）各层最左边的结点的编号分别是多少？各层最右边的结点的编号分别是多少？（3）对于编号为的结点，它的层是多少？它的双亲（若存在）的编号是多少？它的左孩（若存在）和右孩（若存在）的编号分别是多少？15、下图所示的森林：　　(1)求树（a）的先根序列和后根序列；(2)求森林先序序列和中序序列；（3）将此森林转换为相应的二叉树；　　16、对于如下所示的图，试写出其先序、中序和后序以及按层遍历的结果，并画出其顺序存储结构和二叉链表存储结构。17、试画出上题所示的二叉树的先序线索二叉树和后序线索二叉树。99 18、分别画出下图所示各棵树所对应的二叉树，然后将这些二叉树连接成一棵树。HFAJIGDCBKE19、欲传输一段电文如下：CATEATDATACAECATAEAAE请你设计出这段电文中的每个字符的哈夫曼二进制编码。并计算整段电文的编码长度．20、给定叶子结点的权值集合{15，3，14，2，6，9，16，17}，构造相应的哈夫曼树，并计算它的带权路径长度。99 第七章　图一、选择题1、一个具有n个顶点的无向连通图最多有（）边，最少有（）边。A)n2；B)n(n-1)；C)n(n-1)/2；D)n；E)n-1；F)n+1。2、一个具有n个顶点的有向强连通图最多有（）边，最少有（）边。A)n2；B)n(n-1)；C)n(n-1)/2；D)n；E)n-1；F)n+1。3、在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。A）1；B）2；C）1/2；D）4。4、有N个顶点的有向图用邻接矩阵A表示时，顶点入Vi的度是（）。A．B．C．D．+5、．无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。A．a,b,e,c,d,fB．a,c,f,e,b,dC．a,e,b,c,f,dD．a,e,d,f,c,b6、下面哪一方法可以判断出一个有向图是否有环（回路）：A．深度优先遍历B.拓扑排序C.求最短路径D.求关键路径7、图1给出一个无向图。从顶点1出发，DFS遍历的输出序列是（），BFS遍历的输出序列是（）。A)1354267；B)1347625；C)1534276；D)1247653。8、已知有8个顶点A、B、C、D、E、F、G、H的无向图，其邻接矩阵存储结构如下表。从A点开始，DFS遍历的输出序列是（）。A)BCDGHFE；B)ABCDGFHE；C)ABGHFECD；D)ABFHEGDC。ABCDEFGHA01010000B10101110C01010000D10100010E01000001F01000011G0101010199 H000011109、用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是()。A．逆拓扑有序B．拓扑有序C．无序的10、已知一有向图的邻接表存储结构如下：从顶点1出发，DFS遍历的输出序列是（(1)），BFS遍历的输出序列是（(2)）。（1）A)12354；B)12345；C)13452；D)14352。（2）A)12345；B)13245；C)12354；D)14352。11、设图有n个顶点和e条边，则采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为()。A.O(n)B.O(n+e)C.O(n2)D.O(n3)12、设图有n个顶点和e条边，求解最短路径的Floyd算法的时间复杂度为()。A．O（n）B.O（n+e）C.O（n*n）D.O（n*n*n）一、填空题1、在一个图中,所有顶点的度数之和等于所有边数的（）倍。2、在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的（）倍。3、具有4个顶点的无向完全图有（）条边。4、具有6个顶点的无向图至少应有（）条边才能确保是一个连通图。5、对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小（）。6、对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则表头向量的大小为（），所有邻接表中的结点总数是（）。7、图的深度优先遍历算法类似于二叉树的（）遍历；图的宽度优先遍历算法类似于二叉树的（）遍历8、判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以利用（）度优先遍历算法。9、在一个无向图的邻接表中，若表结点的个数是m，则图中边的条数是()条。10、具有n个顶点的图，求最小生成树的Prim算法时间复杂度是（）。它适用（）图。11、具有e条边的图，求最小生成树的Kuruscal算法时间复杂度是（）。它适用（）图。12、具有n个顶点和ｍ条边的图，采用邻接表存储结构。则深度优先搜索算法DFS、广度优先搜索算法BFS、求拓扑排序、求关键路径的时间复杂度是都是（）。13、求n个顶点的有向图某顶点到其他各顶点的最短路径的Dijkstra算法时间复杂度是（）。14、n个顶点的有向图每对顶点间最短路径的Floyd算法时间复杂度是____________。15、如果含n个顶点n条边的无向图成一个环，则该图有多少棵生成树。____________。16、G是一个非连通的无向图，共有28条边，则该图至少有多少顶点。__________。99 17、一个含n个顶点的无向连通图的每条边的权重都是a(a>0),则它的最小生成树的权重等于（）。18、已知有向图的邻接矩阵为A56，试问该矩阵的第3行的非零元素之和表示（），第3行的非零元素之和表示（）。一、问答题与算法题１、在下图所示的各无向图中：　　　　　(１)哪些图是连通图?对非连通图给出其连通分量。(２)哪些图是森林?２、在右图所给的有向图中：　　　(1)请给出每个顶点的度，入度和出度。　(2)请给出其邻接矩阵、邻接表及逆邻接表。31３、已知右边所给的有向图，求：5（1）邻接表；42（2）逆邻接表；（3）画出十字链表。21４、已知如下图所示的无向图，求：（1）邻接矩阵；3（2）邻接表；99 545、对下图所示的连通图，请用Prim算法构造其最小生成树。 　　　　6、用Kruskal算法求下图的最小生成树(写出步骤)。12①②851520③6④10⑤489⑥7、已知AOE网如图5：顶点表示活动，弧及权重表示活动持续的时间（单位为天）。找出所有关键路径；求出活动V3的最早开始时间。99 8、已知如下所示的有向图，试列出图中的全部可能的拓扑有序序列。1234659、已知一个图的顶点集V和边集G分别为：V={0，1，2，3，4，5，6，7，8}E={<0，1>，<0，2>，<1，3>，<1，4>，<2，4>，<2，5>，<3，6>，<3，7>，<4，7>，<4，8>，<5，7>，<6，7>，<7，8>}。若采用邻接表存储，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，则按照教材中介绍的进行拓扑排序的算法，写出得到的拓扑序列（答案是惟一的）。10、已知一个图如下：1）分别写出从顶点1开始的DFS和BFS遍历序列；2）找出一棵生成树；3）求顶点4到各点的最短路径；11、A,B是图G的两个顶点。写一个算法，判断他们是否连通。IntAlinkB(GraphG,VertexTypeA,VertexTypeB)99 12、写一个算法，求图G的连通分支数。Intnum(GraphG)第九章　查找一、选择题1、对线性表进行二分查找时，要求线性表必须（）。A)以顺序方式存储；B)以顺序方式存储，且结点按关键字值有序排列；C)以链接方式存储；D)以链接方式存储，且结点按关键字值有序排列。2、用二分查找法查找具有n个结点的线性表时，查找每个元素的平均比较次数是（）。A)O（n2）；B)O（n*log2n）；C)O（n）；D)O（log2n）。3、利用逐个插入结点的方法建立序列（50，72，43，85，75，20，35，45，65，30）对应的二叉树排序以后，查找元素35时，需要进行（）次元素比较。A)4；B)5；C)7；D)10。4、设哈希表的长度为m=14，哈希函数H（key）=keyMOD11，表中已有4个结点，其地址分别是：addr（15）=4；addr（38）=5；addr（61）=6；addr（84）=7；其余地址空。如果采用二次探测再散列处理冲突，则关键字49的结点的地址是（）。A)8；B)3；C)5；D)9。5、一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该平衡二叉树共有（）结点。A)2k-1-1；B)2k-1+1；C)2k-1；D)2k+1。6、有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素查找概率相等的情况下，查找成功所需的平均比较次数为（）。A)35/12；B)37/12；C)39/12；D)43/12。7、若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为()A)顺序存储结构B)链式存储结构C)索引存储结构D)散列存储结构8、具有5层结点的平衡二叉树至少有（）个结点。A)12；B)11；C)10；D)9。9、既希望较快的查找又便于线性表动态变化的查找方法是()A．顺序查找B.折半查找C.索引顺序查找D.哈希法查找10、在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作()型调整以使其平衡。A.LLB.LRC.RLD.RR11、设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=keyMOD13,散列地址为1的链中有（）个99 记录。A．1B.2C.3D.412、假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？()A．k-1次B.k次C.k+1次D.k（k+1）/2次13、散列函数有一个共同的性质，即函数值应当以()取其值域的每个值。A.同等概率B.最小概率C.最大概率D.平均概率14、散列表的地址区间为0-17,散列函数为H(K)=Kmod17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。（1）元素59存放在散列表中的地址是（）。A．8B.9C.10D.11（2）存放元素59需要搜索的次数是（）。A．2B.3C.4D.515、下面关于B和B+树的叙述中，不正确的是()A.B树和B+树都是平衡的多叉树。B.B树和B+树都可用于文件的索引结构。C.B树和B+树都能有效地支持顺序检索。D.B树和B+树都能有效地支持随机检索。16、二叉查找树的查找效率与二叉树的(（1）)有关,在(（2）)时其查找效率最低。(1):A.高度B.结点的多少C.树型D.结点的位置(2):A.结点太多B.完全二叉树C.呈单枝树D.结点太复杂。二、填空题１、己知一个有序表为(1,8,12,25,29,32,40,62,98),当二分查找值为29和98的元素时,分别需要()次和()次比较才能查找成功；若采用顺序查找时,分别需要()次和()次比较才能查找成功。２、采用散列（Hash）技术进行查找，需要解决的两个问题是（）、（）。３、在各种查找方法中，平均查找长度与结点个数n无关的是（）。4、对于长度为255的表，采用分块查找，每块的最佳长度为（）。长度是（）。对哈希表查找，若用链表处理冲突，则平均查找长度是（）。５、在分块查找中，对256个元素组成的线性表分成（）块最好，每块最佳长度是（）。若每块的长度是8，则平均查找长度是（）。6、在n个记录的有序顺序表中进行折半查找，最大比较次数是（）。7、假设有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少需要进行（）次探测8、设有一个长度为10的已排好序的表，用二分查找法进行查找，若查找不成功，至少与关键字比较（　　）次。9、高度为8的平衡二叉树的结点数至少有（）个。10、动态查找表和静态查找表的重要区别在于前者包含有（）和（）运算，而后者不包含这两种运算。11、查找算法基本上分成（）查找，（）查找和（）查找三类。处理哈希冲突的方法有（）、（）、（）和（）四种。12、以下是有序的二分查找的递归算法，在画线处填入适当成分将算法补充完整。99 intBinsch(ElemTyeA[],intlow,inthigh,KeyTypeK){if(){intmid=(low+high)/2;if()returnmid;//查找成功，返回元素的下标elseif(Knext==L且L->prior==L；8、顺序。9．、O(1),O(n)；10．逻辑顺序与物理顺序一致、可随机访问、节省存储空间、占用连续存储空间、不便于插入、删除和动态增长。11．不需占用连续存储空间，便于插入、删除和动态增长，不能随机访问、只能顺序存取，需额外存储空间、12．在任何位置查入和删除操作一致。13．指针14．DL->next=DL->prior=DL15．(1)i<=S.length∥L.length为元素个数(2)j++∥有值不相等的元素(3)S.a[j]:=S.a[i]∥元素前移(4)L.length=j∥元素个数16．p->prior->next=p->next;p->next->prior=p->prior三、问答题与算法题1、头指针：结点或头结点的指针变量。其作用是存放第一个结点或头结点的地址，从头指针出发可以找到链表中所有结点的信息。头结点：是附加在链表的第一个结点之前的一个特殊结点，其数据域一般不存放信息。其作用是为了简化运算，将空表与非空表统一起来，将第一个结点与其他结点的处理统一起来。首结点：是链表的第一个结点。2、(1)基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。(2)基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。3、99 尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next和rear,查找时间都是O(1)。若用头指针来表示该链表，则查找终端结点的时间为O(n)4、:将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针5、S=P->Prior;P->Prior=S->Prior;S->Prior->Next=P;S->Prior=P;S->Next=P->Next;P->Next=S;S->Next->Prior=S;6、15，26，51，37，48，55。7、CreatList_L(LinkList&Lintn){L=(LinkList)molloc(sizeof(Lnode));//建立头结点L->next==NULL;q=L;For(i=1;i<=n;++i){P=(LinkList)molloc(sizeof(Lnode));Scanf(&(p->data));p->next=NULL;　　q->next=p;　　　q=p;}returenOK;}8、Voidsinsert(Sqlist&S,intx){inti=0;n=S.Length;while(x=i;j++)S.elem[j+1]=S.elem[j];//元素后移S.elem[i]=x;//插入}}9、intListLength(LinkListL){q=L->next;i=0;while(q){i++;q=q->next;}returni;}10、intdelete(LinkList&L,intx){p=L->next;//p为定位指针q=L;//q为定位指针的前导while((p->data!=x)&&p){q=p;//q前进p=p->next;//p前进}if(!q)returnERROR;//查找失败q->next=p->next;free(p);returnOK;}99 11、voidmergelist(linklist&La,linklistLb){pa=La->next;pb=Lb->next;pc=La;while(pa&&pb)if(pa->datadata){pc->next=pa;pc=pa;pa=pa->next;}elseif(pa->data==pa->data){pc->next=pa;pc=pa;pa=pa->next;pb=pb->next;}else({pc->next=pb;pc=pb;pb=pb->next;}pc->next=pa?pb:pb;}12、Voidinvertlinklist(linklist&L){if(!L)returnOK;//空表p=L->next;if(!p)returnOK;//仅有一个结点的表else{q=p->next;//q指向p的后继p->next=NULL;while(q){r=q->next;//r指向q的后继q->next=p;//逆置p=q;//p前进q=r;//q前进}L=p;//第一个结点}}13、VoiddelDuplicate(intA[]，int&n){for(i=0;inext==NULL，S.top==S.base，S.top-S.base==S.stacksize，L==NULL，Q.front==Q.rear，（Q.rear＋１）%maxQsize==Q.front;6、Q.rear-Q.front+n)%n；7、；8、n-19、2，1008；10、push、pop、push、push、pop、push、pop、pop.99 三、问答题与算法题1、１３２４；2、(1)intpush_L(Linkstack&sSelemTypee){p=(LinkStack)molloc(sizeof(Snode));if(!p)returnERROR;p->data=e;p->next=s;s=p;ReturnOk;}(2)intpop_L(Linkstack&sSelemType&e){if(!S)returnERROR;q=s;e=s->data;s=s->next;free(q);RetuenOk;}3、(1)intEnQueue_L(Queueptr&QLQelemTypee){p=Queueptr}molloc(sizeof(Qnode));if(!p)returnERROR;p->data=e;p->next=QL->next->next;QL->next->next=p;RetuenOk;}(2)intDeQueue_L(Queueptr&QLQelemType&e){if(QL->next==QL)}returnERROR;p=QL->nextwhile(p->next!=QL)p=p->next;p->next=QL->next;e=QL->next;free(QL);QL=p;ReturnOk;}4、(1)栈S元素反序存放；(2)把栈s1复制到s2；(3)把栈S中值等于m的元素删除；(4)队列Q元素反序存放;(5)　链表中的元素反序存放；5、Inthw(LinkListL)　{initstack(S);bool=1;n=0;99 p=L->next;while(p){n++;p=p->next;}//求串长p=L->next;//p指向第一个结点for(i=0;idata);p=p->next;}if(n%2==1)p=p->next;while(p&&bool)　{pop(S,ch);　if(ch!=p->data)bool=0;p=p->next;}returnbool;　　｝6、voidClearStack(LinkStack&S)。{while(!S){p=s;s=s->next;free(p);}returnOK;}7、intStacksize(LinkStackS)。{n=0;p=s;While(!p){n++;p=p->next;}returnn;}8、见４、(5)9、voidtest(int&sum){intx,sun=0;initstack(S);scanf(“%d”,&x);while(x){push(S,x);scanf(“%d”,&x);}while(!emptystack(S)){pop(S,x);sum+=x;}printf(“sum=%dn”,sum);}10、floatexpr()//从键盘输入逆波兰表达式，以‘$’表示输入结束，本算法求逆波兰式表达式的值。｛floatOPND[30];//OPND是操作数栈。　init(OPND);//两栈初始化。floatnum=0.0;//数字初始化。scanf(“%c”,&x);//x是字符型变量。while(x!=’$’)99 {switch{case‘0’<=x<=’9’:while((x>=’0’&&x<=’9’)||x==’.’)//拼数if(x!=’.’)//处理整数{num=num*10+（ord(x)-ord(‘0’)）;scanf(“%c”,&x);}else//处理小数部分。{scale=10.0;scanf(“%c”,&x);while(x>=’0’&&x<=’9’){num=num+(ord(x)-ord(‘0’)/scale;scale=scale*10;scanf(“%c”,&x);}}//elsepush(OPND,num);num=0.0;//数入栈，下个数初始化casex=‘’:break;//遇空格，继续读下一个字符。casex=‘+’:push(OPND,pop(OPND)+pop(OPND));break;casex=‘-’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2-x1);break;casex=‘*’:push(OPND,pop(OPND)*pop(OPND));break;casex=‘/’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2/x1);break;default://其它符号不作处理。}//结束switchscanf(“%c”,&x);//读入表达式中下一个字符。}//结束while（x！=‘$’）printf(“后缀表达式的值为%f”,pop(OPND));}//算法结束。第四章串一、选择题1B；2A；３C；4D；5B；6D；7C；8A。二、填空题１、空格串；2、由空格字符构成的串，空格字符的个数；3、静态分配的顺序串、动态分配顺序串、块连串；4、‘’　5、块的大小；6、２；7、StrAssing，StrCompare，StrLength，Concat，SubString；8、14,6；9、模式，目标（主）；10、01010421；11、长度相等且相应位置上的字符相同。12、*s++=*t++或（*s++=*t++）!=‘’三、问答题与算法题1、空串是指不包含任何字符的串，它的长度为零。空格串是指包含一个或多个空格的串，空格也是字符,长度不为零。　　串常量是指在程序中只可引用但不可改变其值的串。串变量是可以在运行中改变其值的。　主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子串的串就称为主串。　　目标串和模式串:在串匹配运算过程中，将主串称为目标串，而将需要匹配的子串称为模式串，两者是相对的。2、(１)"Stocktom,March51999"；(２)正数；(３)正数；(４)１８emp[Maxsize];//定义一个临时串99 　if(i+m=strlen(S)&&inext;n=1;while(p){q=T->next;while(q){if(p->data==q->data)returnn;q=q->next;}p=p->next;n++;}return0;}6、‘abaabcac’（2）’aaaabaab’j12345678j12345678模式串abaabcac模式串aaaabaabnext[j]01122312next[j]012341237、（1）p的nextval函数值为0110132。（p的next函数值为0111232）。（2）利用KMP(改进的nextval)算法，每趟匹配过程如下：第一趟匹配：abcaabbabcabaacbacba99 abcab(i=5,j=5)第二趟匹配：abcaabbabcabaacbacbaabc(i=7,j=3)第三趟匹配：abcaabbabcabaacbacbaa(i=7,j=1)第四趟匹配：abcaabbabcabaacbacba(成功)abcabaa(i=15,j=8)8、voidInvertStore(charA[])//字符串逆序存储的递归算法。{charch;staticinti=0;//需要使用静态变量scanf("%c",&ch);if(ch!=".")//规定"."是字符串输入结束标志{InvertStore(A);A[i++]=ch;//字符串逆序存储}A[i]="";//字符串结尾标记}//结束算法InvertStore。第五章、数组与广义表一、选择题1C，2A，3D，4C，5A，6B，7A，8D，9F，10A，11C、B，12C，13A，14C，15B。二、填空题1、1；2、1+s*i，d+s*i；3、Loc(A[0][0])+(i*n+j)*k)；4、随机；5、1；6、基本项，递归项，基本项：DEPTH(LS)=1当LS是空表DEPTH(LS)=0当LS是原子递归项：DEPTH(LS)=1+MAX(DEPTH())，.7、5,3；8、3，4；9、（c,d）,(b)；10、d；11、1164；12、232；13、1038；14、head(tail(tail(head(tail(head(A))))))；15、(b)。三、问答题与算法题１、LOC(i,j,k)=LOC(0,0,0)+(i*n*s+j*s+k)L２、k=2i+j-3３、A共占120字节；A的终端结点A45的起始地址是1116。99 按行和按列优先存储时，A25的起始地址分别1068和1108。4、(1)ije(2)ije12412424-324-327127131831844544552-752–7row1234567562562rpos[row]12457896466465、6、78、Gethead(Gettail(Gethead(Gettail(LS))))9、99 10．voidArrange(intA[],intn)//n个整数存于数组A中，本算法将数组中所有正数排在所有负数的前面{inti=0,j=n-1,x;//用类C编写，数组下标从0开始while(i0)i++;while(idata);BAC(BT->lchild);BAC(BT->rchild);}后序遍历二叉树voidACB(BiTreeBT){if(BT==NULL)return;ACB(BT->lchild);99 ACB(BT->rchild);Printf(“%c”,BT->data);}2、按层遍历二叉树；3、先序遍历二叉树（非递归算法）；4、用c1统计结点数，用c2统计叶子数；5、intmaxdata(BiTreeT){InitStack(S);Push(S,T);max=0;While(!StackEmpty(S)){while(Getop(S,p)&&p)push(S,p->lchild);pop(S,p);if(!StackEmpty(S)){Pop(S,p);if(p->data>max)max=p->data;Push(S,p->rchild);}}returnmax;}6、CharParent(BitreeT){InitStack(S);P=T;While(P||!StackEmpty(S))If(P){pop(S,p);P=P->lchild;}Else{pop(S,p);if(p->rchild->data==’A’||p->lchild->data==’A’)returnp->data;P=P->rchild;}}7、在6题中增加C=0;及if(p->rchild||p->lchild)C++;即可。8、intleafnum(BitreeT){if(!T)return0;elseif(!(T->lchild)&&~!(T->rchild))return1;elsereturnleafnum(T->lchild)+leafnum(T->rchild);}9、模仿上例。10、写一个算法交换二叉树所有结点的左右子树voidChangchild(BiTreeT){if(T){Changchild(T->lchild);Changchild(T->rchild);Temp=T->lchild;T->lchild=T->rchild;T->rchild=Temp;}}99 11、12、n2+2n3+…+(m-1)nm13、14、15、(1)[]+1层，分别是；（2）最左边结点的编号，最右边；（3）16、(1)ABCDEF;BDEFCA；(2)ABCDEFGHIJK;BDEFCAIJKHG林转换为相应的二叉树；99 17、（略）18、（略）19、字符次数编码A91整段电文的编码长度为45C3001D1000E4010T401120、图略，WPL=229第七章　图一、选择题1、C,E；2、B,D；３、B,A；4、B；5、D；6、A,B；7、C,A8、C,9、A,10、C,B,11、B,12、D。二、填空题1、2；2、1；3、6；4、５；5、；6、n，２e；7、先序（根），按层；8、深；9、m/2；10、O（n2），稠密图；11、O（eloge）,稀疏图；12、O（n+m）；13、O（n2）;14、O（n3）；15、n；16、9；17、(n-1)a；18、第3个顶点的出度，第3个顶点的入度三、问答题与算法题1、（1）（a）(c)(d)是连通图，(b)是非连通图，两个连通分量是{1，4}，{2，3}，（2）(b)是森林２、(1)顶点度入度出度V1312V2211V3321V4211(2)图略99 ３、邻接表逆邻接表十字链表４、（略）5、6、12①②56③④⑤49⑥7、关键路径：v1v2v3v5v6及v1v4v6；活动V3的最早开始时间是13。8、152364；152634；156234；561234；512354；516234；512634；5123649、99 拓扑序列为025143678。10、I=1I=2I=3I=4I=512015151212(4,1)(4,2,1)(4,2,1)(4,6,1)(4,6,1)25(4,2)38(4,2,8)511111111(4,5)(4,5)(4,5)(4,5)6101010(4,6)(4,6)(4,6)vj23651S{4,2}{4,2,3}{4,2,3,6}{4,2,3,6,5}{4,2,3,5,1}11、IntAlinkB(GraphG,VertexTypeA,VertexTypeB){for(v=0;vR.key==key)returnP;elseif(P->R.keylchild;elseP=P->rchild;returnNULL;}14、图略，ASL=42/1215、用链地址法解决冲突的哈希表是一个指针数组，数组分量均是指向单链表的指针，（第i个）单链表结点有两个域，一个是哈希地址为i的关键字，另一个是指向同义词结点的指针。删除算法与单链表上删除算法类似。typedefstructnode{keytypekey；structnode*next；}HSNode；*HSListtypedefstructnode*HLK；voidDelete（HLKHT[]，keytypeK）//用链地址法解决冲突，从哈希表中删去关键字为K的记录{i=H（K）；//用哈希函数确定关键字K的哈希地址if（HT[i]==null）{printf（“无被删除记录n”）；exit（0）；}HLKp,q;p=H[i]；q=p；//p指向当前记录（关键字），q是p的前驱while（p&&p->key！=k）{q=p；p=p->next；}if（p==null）{printf（“无被删除记录”）；exit(0);}if（q==H[i]）//被删除关键字是链表中第一个结点{HT[i]=HT[i].next；free（p）；}else{q->next=p->next；free（p）；}}//结束Delete16、利用二叉排序树的性质，从根结点开始查找，若根结点的值小于等于x，则根结点及其左子树均应删除，然后以右子树的根结点为树根，重新开始查找。若根结点的值大于x，则顺左子树向下查找，直到某结点的值小于等于x，则该结点及其左子树均应删除。下面设计一查找算法，确定被删除子树的根结点，再设计一删除算法，删除以被删结点为根的子树。typedefstructnode{intdata；structnode*left，*right;}BiTNode，*BSTree；voidDelTree(BSTreer）//非递归删除以r为根的二叉排序树{BSTreeS[]；//栈，容量足够大，栈中元素是二叉排序树结点的指针102 top=0；while（r!=null||top>0）{while（r!=null）//沿左分枝向下{S[++top]=r；r=r->left；}if（top>0）//退栈，沿栈顶结点的右子树向下删除，释放被删除结点空间{p=S[top--]；r=p->right；free（p）；}}}//DelTreevoidDeleteAllx(BSTreeＴ，int　x）//在BST中删除所有不大寓于x的结点{BSTreep=T，q；while（T&&T->data≤x）//根结点的值小于等于x{p=T；T=T->right；p->right=null；DelTree（p）；}//删除二叉树p,删除持续到“根”结点值大于x或T为空树为止if(T){q=T；p=T->left；while（p&&p->data>x）//沿根结点左分枝向下，查小于等于x的结点{while（p&&p->data>x）{q=p；p=p->left；}//q记p的双亲if（p）//p结点的值小于等于x{q->left=p->right；p->right=null；DelTree（p）；}p=q->left；//再查原p的右子树中小于等于x的结点}}}//DeleteAllx第十章　内部排序一、选择题1、D,B,D；2、C；3、D；4、B；5、C；6、A；7、C；8、D；9、C,10、B,11、A,12、B,13、A,14、D,15、C,B,16、B。二、填空题1、比较，移动；2、简单选择排序；3、起泡排序，快速排序，4、EACSPDFXQMHY；5、O(n),O(log2n)；6、O(n)；7、快速排序、归并排序；8、希尔排序、选择排序、快速排序、堆排序；9插入排序,选择排序；10、堆排序，快速排序。三、问答题与算法题1、1,6,4,3,9,12,8,18,18,101,3,4,6,8,9,10,12,18,182、(8,9,4,3,6,1),10,(12,18,18)(1,6,4,3),8,(9),10,12,(18,18)1,(3,4,6),8,9,10,12,18,(18)1,3,(4,6),8,9,10,12,18,181,3,4,6,8,9,10,12,18,183、初始堆：18,12,18,8,10,9,4,3；交换后：3,12,18,8,10,9,4,{18}调整后：18,12,9,8,10,3,4,{18}4,12,9,8,10,3,{18,18}12,10,9,8,4,3,{18,18}3,10,9,8,4,{12,18,18}10,8,9,3,4,{12,18,18}4,8,9,3,{10,12,18,18}102 9,8,4,3,{10,12,18,18}3,8,4,{9,10,12,18,18}8,3,4,{9,10,12,18,18}4,3,{8,9,10,12,18,18}4,3,{8,9,10,12,18,18}3,{4,8,9,10,12,18,18}4、(1)分析:从第n个记录开始依次与其双亲（n/2）比较，若大于双亲则交换，继而与其双亲的双亲比较，以此类推直到根为止。voidsift(RecTypeR[],intn){//假设R[1..n-1]是大堆，本算法把R[1..n]调成大堆j=n;R[0]=R[j];for(i=n/2;i>=1;i=i/2)if(R[0].key>R[i].key){R[j]=R[i];j=i;}elsebreak;R[j]=R[0];}//sift(2)voidHeapBuilder(RecTypeR[],intn){for(i=2;i<=n;i++)sift(R,i);}102'