一、填空题
1．数据是描述客观事物的数、字符以及所有能输入到计算机且能够被计算机程序加工处理的符号集合。_________是数据的基本单位；___________是数据的最小单位。通常被计算机加工处理的数据不是孤立无关的，而是彼此之间存在着某种联系，将这种数据间的联系称为________。
2．数据结构进行形式化定义时，可以从逻辑上认为数据结构DS是_________的集合D和D上_________的集合R所构成的二元组：DS=（D，R）。
3．已知某数据结构的二元组形式表示为：A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}。则此数据结构属于_____________结构。
4．一个算法的时间复杂度通常用问题规模大小的函数来表示，当一个算法的时间复杂度与问题规模n大小无关时，则表示为__________；成正比关系时，则表示为___________；成对数关系时，则表示为___________；成平方关系时，则表示为__________。
5．数据结构的逻辑结构包括_____________、树型结构和图型结构三种类型，其中树型结构和图型结构合称为_____________；数据结构的存储结构主要包括____________和____________两种类型。
6．线性结构的特点是：第一个结点_______前驱结点，其余结点有且仅有_______个前驱结点；最后一个结点_______后继结点，其余每个结点有且仅有_______个后继结点。
7．树型结构的特点是：根结点没有________结点，其余每个结点有且仅有________个前驱结点；叶子结点_________后继结点，其余结点可以有_________个后继结点。
8．图型结构的特点是：每个结点可以有_________个前驱结点和后继结点。
9．程序段for（i=1，s=0；s 二、分析下列用二元组形式表示的数据结构，指出他们分别属于何种类型的数据结构。 1.A=（K，R），其中：K={a，b，c，d，e，f，g，h}，R={r}，r={ 2.B=（K，R），其中：K={a，b，c，d，e，f，g，h}，R={r}，r={ 3.C=（K，R），其中：K={ a，b，c，d，e }，R={r}，r={ 4.D=（K，R），其中：K={48，25，，57，82，36，75}，R={r1，r2}，r1={<25，36>，<36，48>，<48，57>，<57，>，<，75>，<75，82>}；r2={<48，25>，<48，>，<，57>，<，82>，<25，36>，<25，75>}。 5.E=（K，R），其中：K={1，2，3，4，5，6，7}，R={r}，r={<1，2>，<2，1>，<1，4>，<4，1>，<2，3>，<3，2>，<3，4>，<4，3>，<1，3>，<3，1>}。 三、指出下列各函数的功能并求出其时间复杂度。 1.void prime(int n) { int i; for(i=2;i<=sqrt(n);i++) if (n %i==0) break; if (i>sqrt(n)) printf(“yes”); else printf(“no”); } 2.long sum1(int n) { long sum,w,i; for(sum=0,i=1;i<=n;i++){ w=1; for(j=1;j<=i;j++) w=w×i; sum=sum+w; } return(sum); } 3.long sum2(int n) { long sum,w,i; for(sum=0, w=1,i=1;i<=n;i++){ w=w×i; sum=sum+w;} return(sum); } 4.void sort(int r[ ],int n) { int i,j; for(i=1; i } 补充： 0.分析下面算法（程序段），给出最大语句频度 ，该算法的时间复杂度是 __ 0. N^2 __。 for (i=0;i 1 分析下面算法（程序段），给出最大语句频度 ，该算法的时间复杂度是__ N^3 __。 s=0; for (i=0;i sum=s; 2 分析下面算法（程序段）给出最大语句频度 ，该算法的时间复杂度是__根号N __。 i=s=0; while (s s+=i; //s=s+i } 3。 分析下面算法（程序段）给出最大语句频度 ，该算法的时间复杂度是__ log(N)__。 i=1; while (i<=n) i=i*2; 第一章参 一、填空题 1．数据元素，数据项，结构 2．数据，关系 3．树型 4．O(1)，O(n)，O(log2n)，O(n2) 5．线性结构，非线性结构，顺序结构，链式结构 6．无，一，无，一 7．前驱，一，无，任意 8．任意 9．O(n1/2) 分析：设程序段中的循环体执行k次，则有不等式成立，解此不等式得到不等式，因此。 10．O(1) 1．线性结构 2．树型结构 3．图型结构 4．图型结构 分析：数据结构D中的关系集合R有两个关系r1和r2。如果只考虑关系r1，则为线性结构；如果只考虑关系r2，则为树型结构；如果把关系r1和r2联合起来考虑，则为图型结构。 5．图型结构 分析：若用图形来表示则可以看出r是E上的对称关系，为了简化起见，我们通常把 三、指出下列各函数的功能并求出其时间复杂度。 1．函数的功能是判断n是否是一个素数，其时间复杂度为O(n1/2)。 分析：函数prime中出现的库函数sqrt为平方根函数，因此。 2．函数的计算的值，其时间复杂度为O(n2)。 3．函数的计算的值，其时间复杂度为O(n)。 4．函数的功能是对数组r中的n个元素进行冒泡排序，其时间复杂度为O(n2)。 分析：。 第二章 线性表 一、填空题 1．设长度为n的顺序线性表在任何位置上插入或删除操作都是等概率的，则插入一个元素时平均需要移动_______个元素，删除一个元素时平均需要移动______个元素。 2．在顺序线性表中插入一个元素时，插入位置开始后的所有元素均需要________移动一个位置。 3．在顺序线性表中删除一个元素时，被删除元素后的所有元素均需要__________移动一个位置。 4．线性表的链式存储结构中，元素之间的线性关系是通过结点中的________来实现的。 5．线性表的顺序存储结构中逻辑上相邻的元素，物理位置__________相邻；线性表的链式存储结构中逻辑上相邻的元素，物理位置____________相邻。 6．已知单链表的长度为n，则在给定值为x的结点后插入一个新结点的时间复杂度为__________。 7．已知单链表的长度为n，则删除给定值为x的结点的时间复杂度为__________。 8．在单链表中设置头结点的作用是________________________________。 9．双向链表中每个结点含有两个指针域，其中一个指针域指向_______结点，另一个指针域指向______结点。 10．在长度为n的线性表中顺序查找某个结点值为X的时间复杂度为______________。 二、选择题 1．在长度为n的顺序线性表中删除第i个元素(1<=i<=n)，则需要向前移动的元素个数为（ ）。 ⑴ n-i ⑵ n+1-i ⑶ n-1-i ⑷ i 2．建立一个长度为n的单链表的时间复杂度为（ ）。 ⑴ O(n) ⑵ O(1) ⑶ O(n2) ⑷ ((log2n) 3．设指针p指向单链表中的结点A，结点A的后继结点是结点B，则删除结点B的操作为（ ）。 ⑴ p->next=p ⑵ p=p->next ⑶ p=p->next->next ⑷ p->next=p->next->next 4．设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B之间插入结点X的操作为（ ）。 ⑴ s->next=p->next； p->next=s； ⑵ q->next=s； s->next=p； ⑶ p->next=s->next； s->next=p； ⑷ p->next=s； s->next=q； 5．在长度为n的顺序线性表中的第i个元素(1<=i<=n+1)之前插入一个新元素时，则需要向后移动的元素个数为（ ）。 ⑴ n-i ⑵ n+1-i ⑶ n-1-i ⑷ i 6．在长度为n的有序线性表中插入一个元素后仍然保持有序的平均时间复杂度为（ ）。 ⑴ O(log2n) ⑵ O(1) ⑶ O(n2) ⑷ O(n) 7．设指针p指向双向链表中的结点A，指针s指向被插入的结点X，则在结点A之后插入结点X的操作为（ ）。 ⑴ p->rlink=s； s->llink=p； p->rlink->llink=s； s->rlink=p->rlink； ⑵ s->llink=p； s->rlink=p->rlink； p->rlink=s； p->rlink->llink=s； ⑶ p->rlink=s； p->rlink->llink=s； s->llink=p； s->rlink->p->rlink； ⑷ s->llink=p； s->rlink=p->rlink； p->rlink->llink=s； p->rlink=s； 8．指针p指向双向链表中的结点A，则删除结点A的操作是（ ）。 ⑴ p->llink->rlink=p->rlink； p->rlink->llink=p->llink； ⑵ p->rlink->llink=p->rlink； p->llink->llink=p->llink； ⑶ p->llink->rlink=p->llink； p->rlink->llink=p->rlink； ⑷ p->rlink->rlink=p->rlink； p->rlink->rlink=p->rlink； 9．线性表采用链式存储结构时，要求存储单元的地址（ ）。 ⑴ 必须是连续的 ⑵ 部分地址必须是连续的 ⑶ 一定是不连续的 ⑷ 连续不连续都可以 10．设head为单链表的头指针，则不带头结点的单链表为空的判定条件是（ ）。 ⑴ head==NULL ⑵ head->next==NULL ⑶ head->next==head ⑷ head!=NULL 11．设head为单链表的头指针，则带头结点的单链表为空的判定条件是（ ）。 ⑴ head==NULL ⑵ head->next==NULL ⑶ head->next==head ⑷ head!=NULL 12．设head和tail分别为单向循环链表的头指针和尾指针，则下列等式成立的是（ ）。 ⑴ head==tail ⑵ head->next==tail ⑶ tail->next==head ⑷ head->next==tail->next 三、算法设计题 顺序存储结构的类型定义：typedef struct {int a[m]; int n; } sqlist; 链式存储结构的类型定义：typedef struct node {int data; struct node *next;} lklist; 1.建立一个有n个结点的单链表，要求从尾部进行插入。 2.建立一个有n个结点的单链表，要求从头部进行插入。 3.用顺序存储结构实现线性表就地逆置算法，即在原表的存储空间内将线性表（a1，a2，……，an）逆置为(an，an-1，……，a1)。 4.用链式存储结构实现线性表就地逆置算法，即在原表的存储空间内将线性表（a1，a2，……，an）逆置为(an，an-1，……，a1)。 5.已知集合A、B，求集合C=A∩B算法，要求集合A、B和C均用采用顺序存储结构表示。 6.已知集合A、B，求集合C=A∩B算法，要求集合A、B和C均用采用链式存储结构表示。 7.设计在带有头结点的单向链表中删除值为X的结点算法。 第二章参 一、填空题 1．n/2，(n-1)/2 分析：当在顺序线性表中的第i（1<=i<=n+1）个位置之前插入一个新元素时，从第i个元素起向后的n+1-i个元素均要向后移动一个位置。因此在等概率情况下，插入操作中元素的平均移动次数为；当在顺序线性表中删除第i（1<=i<=n）个位置上的元素，从第i+1个元素起向后的n-i个元素均要向前移动一个位置。因此在等概率情况下，删除操作中元素的平均移动次数为。 2．向后 3．向前 4．指针域 5．一定，不一定 6．O(n) 7．O(n) 8．消除空表的特殊性，统一表示和处理空表和非空表的情形，从而简化插入和删除等操作的某些细节。 9．前驱，后继 10．O(n) 二、填空题 1．(1) 2．(1) 分析：建立一个单链表的过程实际上就是在空链表的基础之上从单链表的头部或从单链表的尾部不断插入新结点的过程，因此建立单链表的时间复杂度为O(n)。 3．(4) 4．(2) 5．(2) 6．(4) 分析：在有序的线性表中插入一个元素后仍然保持有序的过程分为两步：第一步查找插入位置，第二步插入新元素。在线性表中查找插入位置的平均时间复杂度为f1(n)=O(n)，在顺序线性表中插入新元素的平均时间复杂度为f2(n)=O(n)，而在链式线性表中插入新元素的平均时间复杂度为f2(n)=O(1)，因此本题中的平均时间复杂度f(n)=O(n)+O(1)=O(n) 或 f(n)=O(n)+O(n)=O(n)。 7．(4) 分析：在双向链表或双向循环链表中插入一个新结点的操作比较繁琐，通常需要修改4个指针域，根据排列公式可知共有4!=24种方案。在这24种方案中，有些方案是可行的，有些方案是不可行的。我们的通常做法是先连接哪些不破坏有用信息的指针域，然后再根据需要连接其余的指针域，在操作过程中注意修改有关结点指针域的操作顺序，以免丢失链域信息而造成链表中断的错误。 8．(1) 分析：在双向链表或双向循环链表中删除一个结点的操作比较相对插入一个新结点而言稍微简单一些，只需要修改两个指针域。首先找到指向前驱结点的指针（p->left）和指向后继结点的指针（p->right），然后再分别表示出前驱结点中的右指针域（p->left->right）和后继结点的左指针域（p->right->left），最后分别修改前驱结点中的右指针域和后继结点的左指针域。 9．(4) 10．(1) 11．(2) 12．(3) 三、算法设计题 1.建立一个有n个结点的单链表，要求从尾部进行插入。 分析：本题的算法思想是设置指针变量q始终指向当前链表中的最后一个结点，新生成的结点直接在尾部进行插入。这种设置指针变量q的方法使得操作比较简单，否则每次在尾部插入新结点时需要用一个临时指针变量从链表头部移到链表尾部。 void createlklistfromtail (lklist *&head ) { int i; lklist *p,*q; for (i=1,head=0;i<=n;i++) { p=(lklist *)malloc(sizeof(lklist)); scanf("%d",&(p->data));p->next=0; if(i==1)head=q=p;else {q->next=p;q=p;} } } 提示：以下形式参数表中出现在形式参数名前加符号“&”的现象，这种现象在我们常见的Turbo C 2.0版本中不能使用，但在Borland C 3.1及其以后版本中可以使用，它的作用是使得对形式参数的修改可以影响到对应的实在参数。以后算法设计题中经常用到。 2.建立一个有n个结点的单链表，要求从头部进行插入。 void createlklistfromhead (lklist *&head ) { int i; lklist *p,*q; for (i=1,q=head=0;i<=n;i++) { p=(lklist *)malloc(sizeof(lklist)); scanf("%d",&(p->data)); p->next=head; head=p; } } 提示：不断从头部插入新结点的方法来构造单向链表比不断从尾部插入新结点的方法来构造单向链表稍微操作简单一些。但顺序打印从尾部插入建立的单向链表所得到的序列与建立单向链表输入的序列一样，而顺序打印从头部插入建立的单向链表所得到的序列与建立单向链表输入的序列正好相反。 3.用顺序存储结构实现线性表就地逆置算法，即在原表的存储空间内将线性表（a1，a2，……，an）逆置为(an，an-1，……，a1)。 void invertsqlist(sqlist &list) { int i,temp,n=list.n; for(i=1;i<=n/2;i++){temp=list.a[i-1]; list.a[i-1]=list.a[n-i]; list.a[n-i]=temp;} } 提示：本题中的循环次数只能是顺序线性表的长度一半，如果循环次数是顺序线性表的长度，则经过逆置后再逆置而还原到初始状态。 4.用链式存储结构实现线性表就地逆置算法，即在原表的存储空间内将线性表（a1，a2，……，an）逆置为(an，an-1，……，a1)。 分析：本题的算法思想是依次将单链表中的结点取出来并用指针q指向它，然后再用从头部插入的方法建立一个新的单链表。 void invertlklist(lklist *&head) { lklist *p=head,*q; /*head=0;*/ q=p； p=p->next; q->next=0; while(p!=0){q=p; p=p->next; q->next=head; head=q;} } 5.已知集合A、B，求集合C=A∩B算法，要求集合A、B和C均用采用顺序存储结构表示。 分析：本题的算法思想是顺序取出集合A中的元素A[i]，然后再在集合B中从前向后进行顺序查找，如果找到等于该元素的结点则将其放入集合C中，否则什么也不做。本题算法思想同样适用于其后的第6题。 void intersectionsqlist(sqlist lista, sqlist listb,sqlist &listc) { int i,j; for(listc.n=0,i=0;i<=lista.n-1; i++) { for(j=0;j<=listb.n-1; j++) if (listb.a[j]==lista.a[i]) break; if(j<=listb.n-1) {listc.a[listc.n]=lista.a[i]; listc.n++;} } } 6.已知集合A、B，求集合C=A∩B算法，要求集合A、B和C均用采用链式存储结构表示。 void intersectionlklist(lklist *lista, lklist *listb,lklist *&listc) { lklist *p,*q,*s; for(listc=0,p=lista;p!=0; p=p->next) { for(q=listb;q!=0;q=q->next) if (p->data==q->data) break; if(q!=0) {s=(lklist *)malloc(sizeof(lklist)); s->data=p->data; s->next=listc; listc=s;} } } 7.设计在带有头结点的单向链表中删除值为X的结点算法。 分析：本题的算法思想是首先在单链表中查找值为x的结点，如果单链表为空或在单链表中找不到值为x的结点则给出相应的提示信息，否则进行删除操作。为了便于删除操作的实现而设置指针变量p指向被删除的结点，指针变量q始终指向其前驱结点。 void deletelklist(lklist *&head, int x) { lklist *q,*p; if (head->next==0) printf(“This linklist is empty\\n”); else for(q=head,p=head->next; p!=0; q=p, p=p->next) if (p->data==x) break; if (p==0) printf(“Not found %d in this linklist\\n”,x); else { q->next=p->next; free(p);} } 提示：在链表中引入头结点后可以消除空表的特殊性，统一表示和处理空表和非空表的情形，从而简化插入和删除等操作的某些细节。具体涉及到本题中，如果没有引入头结点，则在找到值为x的结点后要区分该结点是第一个结点还是其它结点，而引入头结点后，则这两种情况就可以统一处理。如果本题中的单链表没有带头结点，则需要将上述黑体中的代码改为代码if (p==head) head=p->next; else q->next=p->next;。 第三章 栈和队列 一、填空题 1.线性表、栈和队列从逻辑上来说都是____________结构。可以在线性表的_______位置插入和删除元素；对于栈只能在__________插入和删除元素；对于队列只能在___________插入元素和在_________删除元素。 2.栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为__________表；队列的插入和删除运算分别在队列的两端进行，进行插入的一端叫做__________，进行删除的一端叫做___________，先进队的元素必定先出队，所以又把队列称为____________表。 3.假设用向量S[1：m]来存储顺序栈，指针top指向当前栈顶的位置。则当栈为空时满足的条件是____________；当栈为满时满足的条件是_____________。 4.设有一个空栈，现有输入序列1、2、3、4、5，经过push、push、pop、push、pop、push、push、pop、pop、 pop后，输出序列为__________________。 5.在一个顺序循环队列中为了方便入队列和出队列的操作通常约定头指针front指向实际队头元素的___前一个位置_________，尾指针rear指向当前实际队尾元素的_____所在位置_______。若该顺序循环队列有m个存储单元，则队列满时共有__________个元素。 6.设有一个顺序循环队列如上题中的约定，则该队列满的条件是_________，队列空的条件是_________。 7.不论是顺序栈（队列）还是链式栈（队列），插入（删除）运算的时间复杂度均为________。 8.系统在函数调用前自动把调用后的____________压入堆栈；当函数调用结束后，系统又自动作退栈处理，并将程序执行流程无条件转移到所保存的_____________处继续执行。 二、选择题 1．设栈的输入序列是1、2、3、…、n，输出序列的第一个元素是n，则第i个输出元素是（ ）。 ① n-i ② n-i-1 ③ n-i+1 ④不确定 2．设元素进栈次序为A、B、C、D、E，则下列不可能的出栈序列是（ ）。 ① ABCDE ② BCDEA ③ EABCD ④ EDCBA 3．设用一维数组s[m]表示栈的存储空间，用top指向当前栈顶元素（其初始值为-1），则进行出栈时的操作序列是（ ）。 ① x=s[op]； ② x=s[top]；top=0； ③ x=s[top]；top=top-1； ④ x=s[top]；top==top+1； 4．设指针hs指向栈顶，指针s指向插入的结点A，则插入结点A时的操作为（ ）。 ① hs->next=s； ② s->next=hs； hs=s； ③ s->next=hs->next； hs->next=s； ④ s->next=hs； hs=hs->next； 5．设用一维数组s[m]表示栈的存储空间，用top指向当前栈顶元素（其初始值为-1），则进行入栈时的操作序列是（ ）。 ① s[top] =x； ② top=top+1；s[top]=x； ③ top==top-1；s[top]=x； ④ s[top]=x；top==top+1； 6．设front是链式队列的头指针，rear是链式队列的尾指针，s指向插入的结点A，则插入结点A的操作为（ ）。 ① front->next=s； front=s； ② s->next=rear； rear=s； ③ rear->next=s； rear=s； ④ s->next=front； front=s； 7．设front是链式队列的头指针，rear是链式队列的尾指针，则删除队头元素的操作为（ ）。 ① front=front->next； ② rear=rear->next ； ③ rear=front->next ； ④ front=rear->next； 8．对于一个具有m个存储单元的顺序循环队列，设front为队头指针，rear为队尾指针，则该队列中队列元素的个数计算公式为（ ）。 ① rear-front ② front-rear ③ (rear-front)%m ④ (rear-front+m)%m 9．设用一维数组q[m]作为顺序循环队列的存储空间，front指向队头元素的前一个位置，rear指向队尾元素的当前位置，则入队列的操作序列为（ ）。 ① q[rear] =x；rear=rear+1； ② q[rear]=x；rear=rear-1； ③ rear=(rear+1)%m；q[rear] =x； ④ rear=(rear-1)%m；q[rear]=x； 10．设用一维数组q[m]作为顺序循环队列的存储空间，front指向队头元素的前一个位置，rear指向队尾元素的当前位置，则出队列的操作序列为（ ）。 ① x=q[front]；front=front+1； ②front=(front+1)%m；x=q[front]； ③ x=q[front]；front=front-1； ④front=(front-1)%m；x=q[front]； 三、算法设计题 1．设有两个顺序栈S1和S2共享一个存储区S[0：m-1]，为了尽量利用存储空间减少溢出的可能性，采用栈顶相向、迎面增长的存储方式，要求分别设计两个栈的入栈和出栈操作。 2．设计算法判断表达式中的圆括号是否配对出现。 3．设用一个单向循环链表来表示队列（也称循环队列），该队列只设一个队尾指针rear，不设队头指针front，要求设计出该队列的入队列和出队列操作。 4．假设以一个一维向量q[0：m-1]作为顺序循环队列的存储空间，同时设变量rear和len分别指示顺序循环队列中的队尾元素的位置和实际队列中的元素个数，要求设计出该队列的入队列和出队列操作。 5．将数字1、2、……、n按顺时针方向排列成环形，按顺时针方向从1开始计数，计满时则输出该位置上的数字并从环中删除该数字，然后从下一个数字开始继续计数，直到环中所有数字均被输出为止，要求设计一个算法完成此功能。 第三章参 一、填空题 1．线性，任何，栈顶，队尾，队头 2．先进后出（FILO），队尾，队头，先进先出（FIFO） 3．top==0，top==m 4．23541 5．前一个位置，所在位置， m-1 分析：在顺序循环队列中约定头指针front和尾指针rear所指向的位置，是牺牲掉一个存储单元而方便表示队列空和队列满的条件，因此顺序循环队列中实际可用的存储单元只有m-1个。 6．(rear+1)%m==front，rear==front 7．O(1) 8．返回地址，返回地址 二、选择题 1.(3) 分析：设栈的输入序列是1、2、3、……、n，输出序列的第一个元素是n，则输出序列必定是n、n-1、n-2、……、1，因此第i个输出元素是n+1-i。 2.(3) 3.(3) 4.(2) 5.(2) 6.(3) 7.(1) 8.(4) 分析：顺序循环队列中的元素个数=，整理合并可写成(rear-front+m)%m。 9.(3) 10.(2) 三、算法设计题 1.设有两个顺序栈S1和S2共享一个存储区S[0：m-1]，为了尽量利用存储空间减少溢出的可能性，采用栈顶相向、迎面增长的存储方式，要求分别设计两个栈的入栈和出栈操作。 分析：本题算法思想是引入形式参数flag，当形式参数flag的值为1时表示对栈1进行操作，flag的值为2时表示对栈2进行操作。 typedef struct {int s[m]; int top1; int top2;} sqstack; void push(sqstack &stack , int x,int flag) { if (stack.top1+1==stack.top2) printf(“stack is full\\n”); else { if (flag==1) {stack.top1++; stack.s[stack.top1]=x;} else if(flag==2){stack.top2--; stack.s[stack.top2]=x;}else printf(“input error\\n”); } } void pop(sqstack &stack , int &y, int flag) { if (flag==1) if(stack.top1<0) printf(“empty\\n”); else { y=stack.s[stack.top1];stack.top1--; } else if(flag==2) if(stack.top2>=m) printf(“empty\\n”); else { y=stack.s[stack.top2];stack.top2++; } else printf(“input error\\n”); } 2.设计算法判断表达式中的圆括号是否配对出现。 分析：本题的算法思想是顺序扫描表达式，当扫描到左圆括号时进栈而扫描到右圆括号时出栈，如果扫描到右圆括号时不能出栈或扫描表达式结束时栈中仍有左圆括号则意味表达式中圆括号不匹配，否则表达式中圆括号匹配。 typedef struct {int s[m]; int top;} sqstack; int matchbracket() { char ch; sqstack stack; stack.top= -1; do { ch=getchar(); if (ch==‘(’) {stack.top=stack.top+1; stack.s[stack.top]=ch;} else if (ch==‘)’) if (stack.top<0) return(0); else stack.top=stack.top-1; }while(ch!= ‘#’); if (stack.top<0) return(1); else return(0); } 3.设用一个单向循环链表来表示队列（也称链式循环队列），该队列只设一个队尾指针rear，不设队头指针front，要求设计出该队列的入队列和出队列操作。 typedef struct node {int data; struct node *next;} lklist; void inlkqueue(lklist *rear, int x) { lklist *p; p=(lklist *) malloc(sizeof(lklist)); p->data=x; if (rear==0) {rear=p; rear->next=rear;}else {p->next=rear->next; rear->next=p; rear=p;} } void outlkqueue(lklist *rear, int *y) { lklist *p; if (rear==0) printf(“queue is empty\\n”); else if {rear->next==rear} {y=rear->data; rear=0; } else { p=rear->next; y=p->data; rear->next=p->next; free(p);} } 4.假设以一个一维向量q[0：m-1]作为顺序循环队列的存储空间，同时设变量rear和len分别指示顺序循环队列中的队尾元素的位置和实际队列中的元素个数，要求设计出该队列的入队列和出队列操作。 分析：本题中出队列的算法思路是设置一个临时变量front指向当前队列中队头元素的实际位置，考虑到表达式queue.rear+1-queue.len的值可能为负，因此设置front的值为(queue.rear+1-queue.len+m)%m。 typedef struct{ int q[m]; int rear; int len; } sqqueue; void insqqueue(sqqueue &queue, int x) { if (queue.len==m) printf(“queue is full\\n”); else {queue.rear=(queue.rear+1)%m; queue.q[queue.rear]=x;queue.len++;} } void outsqqueue(sqqueue &queue, int *y) { int front; if (queue.len==0) printf(“queue is emptyl\\n”); else {front=queue.rear+1-queue.len+m}%m; y=queue.q[queue.front];queue.len--;} } 5.编写一个算法解决约瑟夫（Josephus）环问题。其问题是：设有n个人围坐在一张圆桌周围，现从第一个人开始从1报数，报到k的人出离开圆桌，接着从下一个人从1开始重新报数，……，以此类推，直到他们都离开圆桌，求出他们离开圆桌的先后顺序。 分析：本题的算法思路是设置变量sum和num，其中变量 sum表示当前已经离开圆桌的人数个数，变量num表示当前的报数。 void Josephus( int n, int k) { int i,num,sum,r[100]; for(i=0;i if (num % k==0) { printf("%d\",i); num=0;sum++; r[i]= -1; } } } 第四章 字符串和数组 一、填空题 1.设字符串S1=“ABCDEF”，S2=“PQRS”，则运算S=CONCAT(SUB(S1，2，LEN(S2))，SUB(S1，LEN(S2)，2)的结果为S=_________________。 2.判断两个字符串相等的充要条件是____________________________。 3.下列程序段实现子串t在主串s中位置的算法，要求在下划线处填上正确语句。 int index(char s[ ], char t[ ]) { i=j=0; while(i if (j==strlen(t))return(i-strlen(t));else return (-1); } 4.设二维数组A有m行n列，每个数组元素占L个字节的存储单元，按行的顺序存放在m*n个连续的存储单元中。已知A[0][0]的地址为1000，则A[i][j]的地址为______________________________________。 5.设三维数组A[3][4][5]中的每个元素占10个字节的存储单元，按行的顺序存放在一组连续的存储空间中。已知A[0][0][0]的首地址为1000，则数组元素A[1][2][3]的首地址为___________________________。 6.设对称矩阵A有n行n列，每个数组元素占L个字节的存储单元，按行的顺序将下三角矩阵中的元素（包括对角线上的元素）存放在n*(n+1)/2个存储单元中，已知A[0][0]的地址为1000，则A[i][j]（i>=j）的地址为___________________________。 7.设有n行n列的三对角矩阵A，每个数组元素占L个字节的存储单元，按照从上到下从左到右的顺序将三条对角线上的元素存放在3n-2个连续的存储单元中，已知A[0][0]的地址为1000，则三对角线上元素A[i][j]的地址为_________________。 8.已知稀疏矩阵A=，则A的三元组表为__________________。 二、算法设计题 1.设用顺序存储结构存储字符串S1和S2，要求设计一个函数完成对两个字符串的比较。若S1>S2时则返回正数；若S1=S2时则返回0；若S1 3.设单链表中存放n个字符，试设计算法判断字符串是否关于中心对称。 第四章参 一、填空题 1.“BCDEDE” 2.字符串的长度相等且对应位置上的字符相等 3.i-j+1，0 分析：在查找子串位置的过程中，当发现s[i]!=t[j]时需要重新调整指针i和j的值后继续查找。指针j的值肯定调整到子串的开始位置0，而指针i的值则相应调整到i-j的后一个位置i-j+1。 4.1000+(i*n+j)*L 5.1330 分析：A[1][2][3]的首地址=1000+(1*4*5+2*5+3)*10=1330。 6.1000+(i*(i+1)/2+j)*L 分析：A[i][j]的首地址=1000+(1+2+……+i+j)*L=1000+(i*(i+1)/2+j)*L。 7.(2*i+j)*L 分析：A[i][j]的首地址=，经合并整理可得A[i][j]的首地址=(2*i+j)*L。 8.4 4 4 二、算法设计题 1.设用顺序存储结构存储字符串S1和S2，要求设计一个函数完成对两个字符串的比较。若S1>S2时则返回正数；若S1=S2时则返回0；若S1 { int i; for(i=0;s1[i]!=0;i++) if (s1[i]!=s2[i]) break; return(s1[i]-s2[i]); } 2.用顺序存储结构实现在字符串S中删除所有其值等于ch（假设ch=’A’）的字符的算法。 void deletestring(char s[ ],char ch) { int i=0,j; while(s[i]!=0) if (s[i]==ch) {for(j=i+1; s[j]!=0; j++) s[j-1]=s[j]; s[j-1]=0;}else i++; } 3.设计一个算法判断字符串S中的字符是否关于中心对称。 typedef struct {char s[m]; int top;} sqstack; int stringsymmetry(char s[ ]) { int i; sqstack stack; stack.top= -1; for(i=0;s[i]!=0;i++) {stack.top++; stack.s[stack.top]=s[i];} for(i=0;s[i]!=0;i++) if (s[i]==stack.s[stack.top]) stack.top=stack.top-1; else return(0); return(1); } 第五章 树 一、填空题 1.设一棵树的二元组形式表示为T=（D，R），其中D={A，B，C，D，E，F，G}，R={(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)}，则该树的度数为________，树的深度为________，叶子结点的个数为_________，分支结点的个数为_________，C结点的双亲结点为__________，C结点的孩子结点为__________。 2.二叉树有_________种不同形态。 3.对于一棵具有n个结点的二叉树，当它为一棵__________二叉树时具有最小高度，其最小高度为_______________。 4.一棵深度为k的满二叉树的结点总数为___________；一棵深度为k的完全二叉树的结点总数最少有___________个，最多有____________个。 5.已知一棵二叉树中度数为0的结点个数为n0，度数为1的结点数为n1，则该树中度数为2的结点数为n2，则n0=___________。 6.一棵树中度数为1的结点数为n1，度数为2的结点数为n2，……，度数为m的结点度为nm，则该树中度数为0的结点数为____________个。 7.已知一棵二叉树的顺序存储结构表示为ABCDEF（其中字符表示空结点），则其前序序列为_____________，中序序列为___________，后序序列为_____________。 8.按照从上到下、从左到右的顺序对有n个结点的完全二叉树从1开始顺序编号，则编号为i（i!=1且2i+1<=n）的结点其双亲结点的编号为________，其左孩子结点的编号为________，其右孩子结点的编号为________。 9.对于一棵具有n个结点的二叉树，当用二叉链表作为存储结构时，其二叉链表中的指针域的总数为______个，其中______个用于链接孩子结点，_______个为空指针域。 10.设某棵二叉树的前序遍历序列为ABCDEFGH，中序遍历序列为BCAEDGHF，则该二叉树的后序遍历序列为____________________。 11.如果按中序遍历某二叉树的遍历序列为abc，问有________种不同的二叉树可以得到这一遍历序列。 12.设哈夫曼树中有n个叶子结点，则该哈夫曼树中总共有___________结点。 二、选择题 1．假设一棵二叉树中，双分支结点数为15个，单分支结点数为30个，则终端结点数为（ ）。 ① 15 ② 16 ③ 17 ④ 47 2．假设一棵三叉树的结点数为50，则它的最小高度为（ ）。 ① 3 ② 4 ③ 5 ④ 6 3．一棵二叉树上第5层的结点数最多为（ ）。 ① 15 ② 16 ③ 8 ④ 32 4．将完全二叉树中的所有结点按照从上到下、从左到右的顺序存放在n个连续的存储单元中，第一个结点存放在R[1]中。若结点R[i]有左孩子，则左孩子的结点是（ ）。第一个结点存放在R[0]中呢？（ ） ① R[2i+1] ② R[2i] ③ R[i/2] ④ R[2i-1] 5. 设一棵具有n个结点的满二叉树有m个叶子结点和k个分枝结点，则下列等成立的是（ ）。 ① n=2k+1 ② m+k=2n ③ n=2m+1 ④ n=2k-1 6．设森林F中有三棵树，第一、第二和第三棵树的结点树分别为m1、m2和m3，则与森林F对应的二叉树的根结点的右子树上的结点个数是（ ）。 ① m1 ② m1+m2 ③ m3 ④ m2+m3 7．设A、B为一棵二叉树上的两个结点，中序遍历时A在B前的条件是（ ）。 ① A在B的右方 ② A在B的左方 ③ A是B的祖先 ④ A是B的子孙 8．一棵具有k层的满三叉树有（ ）个结点数。 ① (3 k-1)/2 ② 3 k-1 ③ (3 k-1)/3 ④ 3 k 9．设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少有（ ）个。 ① 2h ② 2h-1 ③ 2h+1 ④ h+1 10．若采用顺序存储结构存储深度为h且有n个结点的二叉树，则最多将浪费（ ）个存储单元。 ① 0 ② 2 h-1-n ③ 2 h+1-n ④ 2 h-n 11．已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，则它的前序遍历序列是（ ）。 ① acbed ② decab ③ deabc ④ cedba 12．在一棵非空二叉树的中序遍历序列中，根结点的右边（ ）。 ① 只有右子树上的所有结点 ② 只有右子树上的部分结点 ③ 只有左子树上的部分结点 ④ 只有左子树上的所有结点 三、应用题 1．设一棵树的二元组形式表示为{(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)}，要求用孩子兄弟表示法表示出该树的存储结构并将该树转化为对应的二叉树。 2．根据5个叶子结点的权值集合{3、6、9、2、5}构成一棵哈夫曼树并计算这棵哈夫曼树的带权路径长度。 四、算法设计题 typedef struct node {int data; struct node *lchild; struct node *rchild;} bitree; 1.设计复制一棵二叉树的算法。 2.设计判断两个二叉树是否等价的算法。 3.设计层次遍历二叉树中所有结点的算法。 4.设计统计二叉树中叶子结点总数的算法。 5.设计交换二叉树中所有结点左右子树的算法。 6.建立一棵二叉树的链式存储结构的算法。 第五章参 一、填空题 1．3，3，4，3（分支结点即度不为0的结点），A，F和G 2．5 3．完全， 4．2k-1，2k-1，2k-1 5．n0=1+n2 6．n0=1+n2+2n3+…+(m-1)nm 分析：设m叉树中的结点总数为n，则下面两个等式同时成立，经两式相减得到等式n0=1+n2+2n3+…+(m-1)nm。 n=n0+n1+n2+n3+…+nm （如果从结点数的角度考虑） n-1=n1+2n2+3n3+…+mnm （如果从分支数的角度考虑） 7．ABDECF，DBEACF，DEBFCA 8．i/2，2i，2i+1 9．2n，n-1，n+1 分析：用二叉链表作为二叉树的存储结构时，第个结点有两个指针域，则有n个结点的二叉链表有2n个指针域，其中有n-1个指针域指向非根结点，因此整个二叉链表中还有n+1个指针域。线索二叉树的线索就是利用这多余的n+1个指针域来作为线索而方便查找某个结点的前驱结点和后继结点。 10．CBEHGFDA 分析：由前序遍历序列可知，根结点最先被访问，这就可以确定A是根结点，而又由中序遍历序列可知二叉树的根结点是其左右子树的分隔点，从而可以确定以A为根结点的左子树上的结点为BC，右子树上的结点为DEFGH。以此类推，直到将这棵二叉树构造出来。实际上，只要给定某棵二叉树的前序遍历序列和中序遍历序列（或中序遍历序列和后序遍历序列）可以唯一地确定这棵二叉树。但如果给定的是某棵二叉树的前序遍历序列和后序遍历序列则不能唯一确定这棵二叉树。 11．5 分析：三个结点的二叉树形状共有5种，如果再考虑到三个结点的排列顺序则每种情况又分为6种子情况，但中序遍历序列是abc的只能是1种子情况。因此中序遍历序列是abc的共有5种二叉树可以得到这一结果。 12．2n-1 由构造哈夫曼树的过程可知，哈夫曼树中不存在度数为1的结点，只有度数为0的结点和度数为2的结点。 二、选择题 1．(2) 2．(3) 用归纳法可以证明三叉树中的第i层上最多有3i-1个结点。本题中的三叉树的结点树为50个，因此该三叉树的最小高度为5。 3．(2) 4．(2)、（1） 5．(1) 分析：根据满二叉树的定义可知满二叉树中没有度数为1的结点，因此有等式n=m+k和等式m=k+1成立，从而得到等式n=2k+1和等式n=2m-1成立。 6．(4) 森林转化为二叉树的规则是首先将森林中的各棵树的根结点看成是兄弟结点，然后再按照树转化为二叉树的规则进行转化。因此，本题中经转化而得到的二叉树的根结点的右子树上结点数等于第二、第三棵树上的结点数之和。 7．(2) 设结点C为结点A和B的最近的公共祖先，则根据中序遍历时A在B的之前知：如果C就是A，则B一定在A的右子树上，如果C就是B，则A一定在B的左子树上，如果C不是A也不是B，则A一定在C的左子树上而B一定在C的右子树上。 8．(1) 分析：用归纳法可以证明三叉树中的第i层上最多有3i-1个结点，因此根据等比数列求和分式可知具有k层的三叉树最多有(3k-1)/2个结点。 9．(3) 10．(2) 分析：顺序存储结构比较适合于完全二叉树，如果是一般二叉树则要将其扩充成完全二叉树以后才能够用顺序存储结构。深度为h的二叉树扩充成完全二叉树最多需要2h-1个存储单元，而实际利用的只是其中的n个存储单元，因此最多浪费2h-1-n个存储单元。 11．(4) 12．(1) 三、应用题 1．略 2．哈夫曼树略，带树路径等于55 四、算法设计题 1.设计复制一棵二叉树的算法。 void copybitree(bitree *bt1,bitree *&bt2) { if (bt1==0) {bt2=0; return;} bt2=(bitree *)malloc(sizeof(bitree)); bt2->data=bt1->data; copybitree(bt1->lchild,bt2->lchild);copybitree(bt1->rchild,bt2->rchild); } 2.设计判断两个二叉树是否等价的算法。 int judgebitree(bitree *bt1,bitree *bt2) { if (bt1==0 && bt2==0) return(1); else if (bt1==0&&bt2!=0 || bt1!=0&&bt2==0 ||bt1->data!=bt2->data) return(0); else return(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild)); } 3.设计层次遍历二叉树中所有结点的算法。 分析：本题的算法思想是设置一个顺序循环队列，队列中的单元用来存储二叉树上结点的指针。先将二叉树上的根指针入队列，在队列非空的情况下取出队头元素访问所指向的结点且将该结点中的左右指针域入队列。 void levelorder(bitree *bt) { struct {int front,rear; bitree *q[m];}queue; bitree *p=bt; queue.rear=queue.front=0; if(bt!=0) {queue.rear=(queue.rear+1)%m; queue.q[queue.rear]=p;} while (!(queue.front==queue.rear)) { queue.front=(queue.front+1)%m; p=queue.q[queue.front]; visitnode(p); if(p->lchild!=0){queue.rear=(queue.rear+1)%m; queue.q[queue.rear]=p->lchild;}; if(p->rchild!=0){queue.rear=(queue.rear+1)%m; queue.q[queue.rear]=p->rchild;}; } } 4.设计统计二叉树中叶子结点总数的算法。 void countleaf(bitree *bt,int &count) { if(bt==0) return; if(bt->lchild==0 && bt->rchild==0) count++; if(bt->lchild!=0) countleaf(bt->lchild,count); if(bt->rchild!=0) countleaf(bt->rchild,count); } 5.设计交换二叉树中所有结点左右子树的算法。 void swapbitree(bitree *bt) { bitree *p; if(bt==0) return; swapbitree(bt->lchild); swapbitree(bt->rchild); p=bt->lchild; bt->lchild=bt->rchild; bt->rchild=p; } 6.建立一棵二叉树的链式存储结构的算法。 void createbitree(threadbitree *&bt) { char ch; scanf("%c",&ch); if(ch=='#') {bt=0; return;} bt=(threadbitree*)malloc(sizeof(threadbitree)); bt->data=ch; createbitree(bt->lchild); createbitree(bt->rchild); } 提示：遍历是二叉树各种操作的基础，可在在遍历过程中对结点进行各种操作，如求已知结点的孩子结点、判定结点所在的层次、求二叉树的深度、统计二叉树中结点总数、复制二叉树等操作，也可以在遍历过程中生成结点，如建立二叉树的链式存储结构。 第六章 图 一、填空题 1．设无向图G中的顶点数为n，则图G中最少有________条边，最多有________条边；设有向图G中的顶点数为n，则图G中最少有________条边，最多有________条边。 2．设无向图G中有n个顶点和e条边，用邻接矩阵作为存储结构时，则访问任何一个顶点的所有邻接点的时间复杂度为__________；用邻接表作为存储结构时，则访问任何一个顶点的所有邻接点的平均时间复杂度为__________。 3．设有向图G有n个顶点，采用邻接矩阵作为存储结构，则该矩阵中含有_______个数组元素。 4．设无向图G中有e条边且所有顶点的度数之和为m，则m与e之间的关系为_____。 5．设无向图G中有n个顶点和e条边，则用邻接矩阵作为图的存储结构进行深度优先遍历或广度优先遍历的时间复杂度为_________；用邻接表作为图的存储结构进行深度优先遍历或广度优先遍历的时间复杂度为_________；图的深度优先或广度优先遍历的空间复杂度为____________。 6．设有向图G有n个顶点和e条边且用邻接表作为存储结构，则进行拓扑排序时的时间复杂度为__________。 7．在一个有向图G中若有弧 8．在有向图的邻接矩阵中，第i行上非零元素个数之和等于顶点i的_________，第i列上非零元素个数之和等于顶点i的_________。 9．设有向图G的邻接表中第1条单链表中有结点2、5、4，第2条单链表中有结点3、5，第3条单链表中有结点5，第4条单链表为空，第5条单链表中有结点4、3，则从该图中顶点1出发的深度优先遍历序列为__________________，广度优先遍历序列为____________________。 10．设用邻接矩阵作为图的存储结构，则用普里姆算法求连通图的最小生成树的时间复杂度为_____________。 二、选择题 1．无向图的深度优先遍历算法类似于二叉树的（ ）。 ① 中序遍历 ② 先序遍历 ③ 后序遍历 ④ 层次遍历 2．图的广度优先遍历算法类似于二叉树的（ ）。 ① 中序遍历 ② 先序遍历 ③ 后序遍历 ④ 层次遍历 3．设无向图G的二元组形式表示为G=（D，R），其中D={a，b，c，d，e，f}，R={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，从顶点a出发按深度优先遍历该图，则可以得到的一种顶点序列为（ ）。 ① abecdf ② acfebd ③ aebcfd ④ aedfcb 4．设无向图G中有e条边且采用邻接表作为存储结构，则邻接表中有（ ）表结点。 ① e/2 ② e ③ 2e ④ n+e 5．连通具有n个顶点的无向图至少需要（ ）条边。 ① n ② n+1 ③ n/2 ④ n-1 6．已知有向图G的二元组形式表示为G=（D，R），其中D={1，2，3，4，5，6}，R={<1，2>，<2，3>，<1，4>，<4，5>，<4，6>，<6，5>，<5，3>}，则由图G1得到的一种拓扑排序序列为（ ）。 ① v1，v4，v6，v2，v5，v3 ② v1，v2，v3，v4，v5，v6 ③ v1，v4，v2，v3，v6，v5 ④ v1，v2，v4，v6，v3，v5 7．设强连通图G有n个顶点，则该图至少有（ ）条边。 ① n ② n+1 ③ n(n-1) ④ n-1 8．关键路径是AOE网中的（ ）。 ① 从源点到汇点的最长路径 ② 最长的回路 ③ 从源点到汇点的最短路径 ④ 最短的回路 三、已知无向图G的邻接矩阵，按要求完成下列各题。 1．给出无向图G中各顶点的度数； 2．给出无向图G的邻接表； 3．分别给出应用Kruskal和Prim算法构造最小生成树的过程。 四、算法设计题 1．设计图的深度优先遍历算法（用邻接表作为存储结构）。 2．设计图的广度优先遍历算法（用邻接矩阵作为存储结构）。 3．设计将无向图的邻接矩阵转化成无向图的邻接表的算法。 第六章参 一、填空题 1．0，n(n-1)/2，0，n(n-1) 2．O(n)，O(e/n) 分析：如果在邻接矩阵中访问无向图中第i个元素的所有邻接点，则需要对该邻接矩阵中的第i行或第i列进行一趟扫描，因此时间复杂度为O(n)。如果在邻接表中访问无向图中第i个元素的所有邻接点，则需要访问邻接表中第i条单链表，因为n条单链表的长度之和为2e，所以每条单链表的平均长度为2e/n，因此平均时间复杂度为O(e/n)。 3．n2 4．m=2e 5．O(n2)，O(n+e)，O(n) 分析：图的遍历过程实质上是对每个顶点查找其邻接点的过程，其耗费的时间取决于所采用的存储结构。当用邻接矩阵作为图的存储结构时，时间复杂度为O(n2)，而当用邻接表作为图的存储结构时，时间复杂度为O(n+e)。在图的遍历过程中为了避免同一个顶点被访问多次，在遍历图的过程中必须记录已被访问过的顶点，因此需要设置一个长度为n的标志数组用来记录哪些已被访问过。 6．O(n+e) 分析：初始化栈的时间复杂度为O(n)；建立求各顶点入度并将入度为0的顶点入栈的时间复杂度为O(n+e)；在拓扑排序过程中每一个顶点进一次栈和出一次栈，入度减1的操作在循环语句执行e次，总的时间复杂度为O(n+e)。 7．(i，j，k) 8．出度，入度 9．1、2、3、5、4，1、2、5、4、3 分析：图的深度优先遍历是一个递归的过程，当访问过某个顶点之后要在其邻接点中查找未被访问过的顶点进行深度优先遍历，否则要依次回退到最近被访问过的尚有未被访问过的邻接顶点并从该顶点出度进行深度优先遍历。图的广度遍历是当访问过某个顶点之后访问其未被访问过的邻接点，然后再依次从这些顶点出度分别访问它们未被访问过的邻接点。 10．O(n2) 分析：利用普里姆算法求最小生成树的时间主要耗费在一个双重循环语句中，外循环执行n-1次，而内循环的功能是求最小值和重新选择具有最小代价的边各执行n次，因此总的时间复杂度为O(n2)。 二、选择题 1．(2) 2．(4) 3．(4) 4．(3) 5．(4) 6．(1) 7．(1) 8．(1) 三、应用题 1．TD(1)=TD(2)=TD(3)=TD(4)=3，TD(5)=4 2．v1->2->4->5；v2->1->3->5；v3->2->4->5；v4->1->3->5；v5->1->2->3->4 3．Prim算法：(1，2)，(2，3)，(2，5)，(5，4) Kruskal算法：(2，5)，(2，3)，(2，1)，(5，4) 四、算法设计题 1．设计图的深度优先遍历算法。 int visited[m]; typedef struct node1{int info;int adjvertex; struct node1 *nextarc;}glinklistnode; typedef struct node2{int vertexinfo;glinklistnode *firstarc;}glinkheadnode; void createadjlist(glinkheadnode g[ ]) { int i,j,k; glinklistnode *p; for(i=0;i scanf("%d,%d",&i,&j); p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=j; p->nextarc=g[i].firstarc; g[i].firstarc=p; p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=i; p->nextarc=g[j].firstarc; g[j].firstarc=p; } } void dfs(glinkheadnode g[ ], int v0) { glinklistnode *p; printf("%d\",v0); visited[v0]=1; p=g[v0].firstarc; while(p!=0) { if(visited[p->adjvertex]==0)dfs(g,p->adjvertex); p=p->nextarc; } } 2．设计图的广度优先遍历算法（用邻接矩阵作为存储结构）。 int visited[m]; typedef struct {int vertex[m]; int edge[m][m];}gadjmatrix; void createadjmatrix(gadjmatrix *g) { int i,j,k; for(i=0; i for(i=0; i for (k=0;k } void bfs(gadjmatrix g, int v0) { struct {int front; int rear; int q[m];}queue; int i,j; printf("%d\",v0); visited[v0]=1; queue.front=queue.rear=0; queue.rear=(queue.rear+1)%m; queue.q[queue.rear]=v0; while(queue.front!=queue.rear) { queue.front=(queue.front+1)%m; i=queue.q[queue.front]; for(j=0;j printf("%d\",j); visited[j]=1; queue.rear=(queue.rear+1)%m; queue.q[queue.rear]=j; } } } 3．设计将无向图的邻接矩阵转化成无向图的邻接表的算法。 typedef struct {int vertex[m]; int edge[m][m];}gadjmatrix; typedef struct node1{int info;int adjvertex; struct node1 *nextarc;}glinklistnode; typedef struct node2{int vertexinfo;glinklistnode *firstarc;}glinkheadnode; void adjmatrixtoadjlist(gadjmatrix g1,glinkheadnode g2[ ]) { int i,j; glinklistnode *p; for(i=0;i<=n-1;i++) g2[i].firstarc=0; for(i=0;i<=n-1;i++) for(j=0;j<=i;j++) if (g1.edge[i][j]==1) { p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=j; p->nextarc=g[i].firstarc; g[i].firstarc=p; p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=i; p->nextarc=g[j].firstarc; g[j].firstarc=p; } } 第七章 排序 一、填空题 1.对一组记录关键字（50，40，95，20，15，70，60，45，80）进行直接插入排序时，当把第7个记录60插入到有序表时，从后向前为寻找插入位置需要比较_______次。 2.在对一组记录关键字（50，40，95，20，15，70，60，45，80）进行希尔排序时，假定取d1=4，d2=2，则第二趟排序后的结果为____________________________。 3.在对一组记录关键字（50，40，95，20，80，70，60，45，15）进行冒泡排序时，第一趟需要进行相邻记录的交换次数为___________，在整个排序过程中需要进行__________趟才能完成。 4.在对一组记录关键字（50，40，95，20，15，70，60，45，80）进行快速排序时，若以第一个关键字50作为基准记录，则第一趟排序后的结果为___________________。 5.在对一组记录关键字（50，40，95，20，15，70，60，45，80）进行简单选择排序时，第4趟排序后的结果为_________________________。 6.在直接插入和简单选择排序中，若初始记录关键字基本有序，则选用___________排序，若初始记录关键字基本反序，则选用____________排序。 7.在对一组记录关键字（50，40，95，20，15，70，60，45，80）进行堆排序时，则根据这组记录关键字构成的初始堆为_________________________。 8.在堆排序过程中，由n个待排序的记录关键字建成初始堆需要进行___________次筛选；由初始堆到堆排序结束需要进行___________次筛选，每次筛选时对记录关键字进行比较的数量级为__________；堆排序算法的时间复杂度为__________。 9.在堆排序和快速排序中，若原始记录关键字接近正序或反序，则最好选用________排序，若原始记录关键字无序，则最好选用_________排序。 10.在归并排序中，若待排序的记录关键字个数为20，则需要进行__________趟归并，在第三趟归并中是把长度为__________的有序表归并成长度为__________的有序表。 11.在堆排序、快速排序和归并排序中，若从节省存储空间的角度考虑，则首先选取____________方法，其次选择_____________方法；若从平均情况下速度最快的角度考虑，则选择____________方法。 12.从未排序序列中依次取出元素与已排序序列中的元素作比较，将其放入已排序序列中的正确位置上，此方法称为___________；从未排序序列中挑选元素，并将其放入已排序序列的一端，此方法称为___________；依次将每两个相邻的有序表合并成一个有序表的排序方法叫做___________；当两个元素比较出现反序时就相互交换位置的排序方法叫做____________。 13.快速排序的平均时间复杂度为___________，空间复杂度为____________；快速排序的最坏时间复杂度为__________，空间复杂度为_________。 14.堆中的所有非叶子结点Ri与该结点的左右孩子结点R2i和R2i+1之间的关系是_____________________________。 15.设初始记录关键字序列（502，87，513，，902，170，7），则利用基数排序思想经过第一趟的分配和回收后的结果序列为_______________________________。 二、选择题 1．直接插入排序和冒泡排序的时间复杂度为（ ）。 ① O(n) ② O(n2) ③ O(log2n) ④ O(nlog2n) 2．简单选择排序的时间复杂度为（ ）。 ① O(n) ② O(n2) ③ O(log2n) ④ O(nlog2n) 3．已知一组记录关键字（45，80，55，40，42，85），则利用快速排序的方法，以第一个记录关键字作为基准而得到的一次划分结果是（ ）。 ① （40，42，45，55，80，85） ② （42，40，45，80，85，55） ③ （42，40，45，55，80，85） ④ （42，40，45，85，55，80） 4．每次将待排序的元素划分为左右两个子区间，其中左区间中所有元素的关键字均小于基准元素的关键字，右区间中所有元素的关键字均大于等于基准元素的关键字，则此排序的方法叫做（ ）。 ① 堆排序 ② 快速排序 ③ 冒泡排序 ④ 希尔排序 5．设一组记录关键字为（25，50，15，35，80，85，20，40，36，70），其中含有5个长度为2的有序表，则用归并排序的方法对该序列进行一趟归并后的结果为（ ）。 115，25，35，50，20，40，80，85，36，70 215，25，35，50，80，20，85，40，70，36 315，25，35，50，80，85，20，36，40，70 415，25，35，50，80，20，36，40，70，85 6．根据一组记录关键字（45，80，55，40，42，85）建立的初始堆为（ ）。 ① （80，45，55，40，42，85） ② （85，80，55，40，42，45） ③ （85，80，55，45，42，40） ④ （85，55，80，42，45，40） 7．下列（ ）中比较关键字的次数与记录关键字的初始序列无关。 ① 插入排序 ② 选择排序 ③ 冒泡排序 ④ 希尔排序 8．设待排序的记录关键字序列基本有序，则下列（ ）的效率最高。 ① 插入排序 ② 选择排序 ③ 快速排序 ④ 归并排序 三、判断下列初始序列是否为堆，若不是堆则将它们调整为堆。 1.100，85，95，75，80，60，82，40，20，10，65 2.100，95，85，82，80，75，65，60，40，20，10 3.100，85，40，75，80，60，65，95，82，10，20 四、算法设计题 1．设计直接插入排序算法在链式存储结构上的实现。 2．设计双向冒泡排序算法在顺序存储结构上的实现。 3．设关键字序列（k1，k2，…，kn-1）是堆，设计算法将关键字序列（k1，k2，…，kn-1，x）调整为堆。 第七章参 一、填空题 1.3 2.(15，20，50，40，60，45，80，70，95) 3.7，8 4.(45，40，15，20，50，70，60，95，80) 5.(15，20，40，45，50，70，60，95，80) 6.直接插入排序，简单选择排序 7.(15，20，60，45，40，70，95，50，80) 8.n/2，n-1，O(log2n)，O(nlog2n) 9.堆排序，快速排序 分析：堆排序在任何情况下的时间复杂度均为O(nlog2n)，而快速排序在关键字序列基本有序或反序的情况下的时间复杂度为O(n2)。 10.5，4，8 11.堆排序，快速排序，快速排序 分析：堆排序、快速排序和归并排序的平均时间复杂度均为O(nlog2n)，但快速排序的系数在这三种排序中最小。堆排序的空间复杂度为O(1)，快速排序的平均空间复杂度为O(log2n)，归并排序的时间复杂度为O(n)。 12.插入排序，选择排序，归并排序，交换排序 13.O(nlog2n)，O(log2n)，O(n2)，O(n) 14.Ri<=R2i&& Ri<=R2i+1 || Ri>=R2i&& Ri>=R2i+1 15.(170，502，902，513，，87，7) 二、选择题 1.(2) 2.(2) 3.(3) 4.(2) 5.(1) 6.(2) 7.(2) 8.(1) 三、应用题 1．对 2．对 3．不对，调整后的初始堆是(100，95，65，85，80，60，40，75，82，10，20) 四、算法设计题 1.设计直接插入排序算法在链式存储结构上的实现。 void straightinsertsort(lklist *&head) { lklist *s,*p,*q; int t; if (head==0 || head->next==0) return; else for(q=head,p=head->next;p!=0;p=q->next) { /* 以上for循环查找插入位置 */ else { q->next=p->next; p->next=s->next; s->next=p; t=p->data;p->data=s->data;s->data=t; } } } 2.设计双向冒泡排序算法在顺序存储结构上的实现。 void dbbubblesort(int a[n]) { int i,j,t; for(i=1;i<=n/2;i++) { } } 3.设关键字序列（k1，k2，…，kn-1）是堆，设计算法将关键字序列（k1，k2，…，kn-1，x）调整为堆。 void adjustheap(int r[ ],int n) { int j=n,i=j/2,temp=r[j-1]; while (i>=1) if (temp>=r[i-1])break; else{r[j-1]=r[i-1]; j=i; i=i/2;} r[j-1]=temp; } 第八章 查找 一、填空题 1.假设在有序表R[0：19]上进行二分查找，则比较一次查找成功的结点数有______个，比较两次查找成功的结点数有________个，比较三次查找成功的结点数有_______个，比较四次查找成功的结点数有________个，比较五次查找成功的结点数有_______个，平均查找长度为_______。 2.假设查找表R[0：11]中每个元素的查找概率相等，则对该查找表进行顺序查找的平均查找长度为_________，对该查找表进行二分查找的平均查找长度为____________。 3.假设对线性表R[0：59]进行分块查找，共分10块，每块长度为6，利用顺序查找方法查找索引表和块，则查找每一个元素的平均查找长度为__________。 4.在分块查找中，首先在_________中查找，然后再在_________中查找。分块查找的平均查找长度等于查找索引表的平均长度与查找相应子块的平均查找长度的________。 5.对于长度为n的线性表，若利用顺序查找方法，则时间复杂度为__________，若利用二分查找方法，则时间复杂度为____________，若利用分块查找方法，则时间复杂度为____________。（假定总块数和每块长度均接近的值）。 6.设HASH表中实际存储的数据元素个数为n，HASH表的长度为m，则m应________n，装填因子=__________。装填因子的值越大，则存取元素时发生冲突的可能性就越_________，否则存取元素时发生冲突的可能性就越__________。 7.HASH查找技术处理冲突的方法有____________和_____________两种。 8.将一组关键字记录（18，34，58，26，75，67，48，93，81）映射到长度为11的散列表中。设散列函数为H（k）=k %11，采用线性探测法解决冲突，则平均查找长度为__________，采用链地址法解决冲突，则平均查找长度为__________。 9.在二叉排序树上查找元素的时间复杂度为_________，删除元素的时间复杂度为__________。 10.在一棵二叉排序树上按_________遍历得到的序列是一个有序序列。 11.采用分块查找时，若线性表有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分___________个结点为最佳。 12.假设N个关键字均具有相同的Hash函数值，则用线性探测方法将这N个关键字映射存储到Hash表中时，共需要作__________________次探测。 二、选择题 1．对顺序表进行二分查找时，要求顺序表必须满足的条件是______________。 ① 以顺序存储方式存储 ② 以链式方式存储 ③ 以顺序存储方式存储且数据元素有序 ④ 以链式方式存储且数据元素有序 2．已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当利用二分查找方法查找值为90的元素时，总共需要和关键字比较____________次。 ① 1 ② 2 ③ 3 ④ 4 3．如果要求一个线性表既能够进行较快的插入和删除又能够反映数据元素之间的逻辑关系，则应该_____________。 ① 以顺序方式存储 ② 以链式方式存储 ③ 以散列方式存储 ④ 以上均可以 4．设散列表的地址空间为R[0：m-1]，散列函数为H(k)=k mod P，为了减少发生冲突的可能性，通常情况下最好选择P为___________。 ① 小于等于m的最大奇数 ② 小于等于m的最大素数 ③ 小于等于m的最大偶数 ④ 小于等于m的最大合数 5．散列函数将记录的关键字值转化为记录的存储地址，则选择好的______________是散列查找的关键。 ① 散列函数 ② 除余法中的质数 ③ 冲突处理 ④ 散列函数和冲突处理 三、算法设计题 1．若线性表中各结点的查找概率不等，则可用如下策略提高顺序查找的效率，若找到指定结点则将该结点和其前驱结点（如果存在）交换。设计在顺序存储结构上实现上述策略的顺序查找算法。 2．设计在链式存储结构上建立二叉排序树的算法。 3．设计判断一棵二叉树是否为二叉排序树的算法。 4．设计指定结点在二叉排序树中所在层次的算法。 5．设散列表采用线性探测解决冲突，设计在散列表中查找指定关键字的算法。 6．设散列表采用链地址法解决冲突，设计在散列表中查找指定关键字的算法。 第八章参 一、填空题 1.1，2，4，8，5，3.7 2.6.5，37/12 3.9 4.索引表，块，和 5.O(n)，O(log2n)，O(n1/2) 6.大于等于，n/m，大，小 7.开放定址法，链地址法 8.16/9，13/9 9.O(log2n)，O(log2n) 10.中序 11.25 12.n(n-1)/2 分析：关键字k1需要0次，k2需要1次，k3需要2次，…，kn需要n-1次，则总共需要n(n-1)/2次。 二、选择题 1.(3) 2.(2) 3.(2) 4.(2) 5.(4) 三、算法设计题 1.若线性表中各结点的查找概率不等，则可用如下策略提高顺序查找的效率，若找到指定结点则将该结点和其前驱结点（如果存在）交换。设计在顺序存储结构上实现上述策略的顺序查找算法。 int sqsearch(int a[n],int x) { for(i=0;i<=n-1;i++) if (a[i]==x){t=a[i];a[i]=a[i-1];a[i-1]=t; return(i);} return(0); } 2.设计在链式存储结构上建立二叉排序树的算法。 分析：建立二叉排序树的过程实际上就是在空二叉排序树的基础上不断插入新结点的过程，因此本算法主要部分是在二叉排序树上插入结点的算法。 void bstinsert(bitree *&bt,int key) { } void createbsttree(bitree *&bt) { } 3.设计判断一棵二叉树是否为二叉排序树的算法。 分析：根据二叉排序树的特性可知中序遍历二叉排序树可以得到一个有序的序列，因此本算法的思想是根据中序遍历时前驱结点的值（根结点的前驱结点值可设置为机内最小的整数）是否小于等于当前结点的值来判断是否是二叉排序树。 int minnum=-32768,flag=1; typedef struct node{int key; struct node *lchild,*rchild;}bitree; void inorderjudge(bitree *bt) { if (bt!=0) { inorderjudge(bt->lchild); if(minnum>bt->key)flag=0; minnum=bt->key; inordergudge(bt->rchild); } } 4.设计指定结点在二叉排序树中所在层次的算法。 分析：本题的算法思想是在查找的过程中记录下结点所在的层次，当到某个结点的左子树或右子树中查找时则层数加1，如果找到结点则改变标志变量flag的值并返回。 typedef struct node{int key; struct node *lchild,*rchild;}bitree; int lev=0,flag=0; void level(bitree *bt,int x) { if (bt!=0) { {flag=1;return;} } } 5.设散列表采用线性探测解决冲突，设计在散列表中查找指定关键字的算法。 struct record {int key; int flag;}; int hashsqsearch(struct record hashtable[ ],int k) { } 6.设散列表采用链地址法解决冲突，设计在散列表中查找指定关键字的算法。 typedef struct node {int key; struct node *next;} lklist; lklist *hashlksearch(lklist *hashtable[ ],int k) { int i=k % p; lklist *s; for(s=hashtable[i]->next; s!=0; s=s->next) if (s->key==k) return(s); return(0); }
Copyright © 2019-2025 51dongshi.net 版权所有
违法及侵权请联系：TEL:177 7030 7066 E-MAIL:11247931@qq.com 本站由北京市万商天勤律师事务所王兴未律师提供法律服务
