1、3 上述定义表明，函数f顶多是函数g的c倍，除非n 小于n0。因此对于足够大的n（如nn0），g是f 的一个上限（不考虑常数因子c）。在为函数f 提供一个上限函数g 时，通常使用比较简单的函数形式。比较典型的形式是含有n的单个项（带一个常数系数）。表1-1列出了一些常用的g函数及其名称。对于表1-1中的对数函数logn，没有给出对数基，原因是对于任何大于1的常数a和b都有logan=logbn/logba,所以logan和logbn都有一个相对的乘法系数1/logba，其中a是一个常量。表1-1常用的渐进函数 函数 名称 1 常数 logn 对数 n 线性 nlogn n个logn n2 平方
2、 n3 立方 2n 指数 n!阶乘 1.9 算法的空间复杂度指的是什么？算法的空间复杂度是指算法在执行过程中占用的额外的辅助空间的个数。可以将它表示为问题规模的函数，并通过大写O符号表示空间复杂度。1.10 对于下面的程序段，分析带下划线的语句的执行次数，并给出它们的时间复杂度T（n）。（1）i+;（2）for（i=0;in;i+）if（aix）x=ai;（3）for（i=0;i+）for（j=0;jn;j+）printf（“%d”,i+j）;（4）for（i=1;i=n-1;i+）k=i;for（j=i+1;jaj+1）k=j;t=ak;ak=ai;ai=t;（5）for（i=0;j+）+x
3、;s=s+x;（1）O（1）；（2）O（n）；（3）O（n2）；（4）O（n2）；（5）O（n2）4 第2章 线性表及其顺序存储 2.1 选择题（1）表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均个数为（E），删除一个元素所需移动元素的平均个数为（A）。A（n1）/2 Bn Cn+1 Dn1 En/2 F（n+1）/2 G（n2）/2（2）设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列为e2、e4、e3、e6、e5和e1，则栈S的容量至少应该为（C）。A
4、6 B4 C3 D2（3）设栈的输入序列为1、2、3 n，若输出序列的第一个元素为n，则第i个输出的元素为（B）。A不确定 Bni+1 Ci Dni（4）在一个长度为n的顺序表中删除第i个元素（1=i=n）时，需向前移动（A）个元素。Ani Bni+1 Cni1 Di（5）若长度为n的线性表采用顺序存储结构存储，在第i个位置上插入一个新元素的时间复杂度为（A）。AO（n）BO（1）CO（n2）DO（n3）（6）表达式a*（b+c）d的后缀表达式是（B）。Aabcd*+Babc+*d Cabc*+d D+*abcd（7）队列是一种特殊的线性表，其特殊性在于（C）。A插入和删除在表的不同位置执行
5、B插入和删除在表的两端位置执行 C插入和删除分别在表的两端执行 D插入和删除都在表的某一端执行（8）栈是一种特殊的线性表，具有（B）性质。A先进先出 B先进后出 C后进后出 D顺序进出（9）顺序循环队列中（数组的大小为n），队头指示front指向队列的第1个元素，队尾指示rear指向队列最后元素的后1个位置，则循环队列中存放了n 1个元素，即循环队列满的条件为（B）。A（rear+1）%n=front1 B（rear+1）%n=front C（rear）%n=front Drear+1=front（10）顺序循环队列中（数组的大小为6），队头指示front和队尾指示rear的值分别为3和0，当
6、从队列中删除1个元素，再插入2个元素后，front和rear的值分别为（D）。A5和1 B2和4 C1和5 D4和2 2.2什么是顺序表？什么是栈？什么是队列？5【答】：当线性表采用顺序存储结构时，即为顺序表。栈是一种特殊的线性表，它的特殊性表现在约定了在这种线性表中数据的插入与删除操作只能在这种线性表的同一端进行（即栈顶），因此，栈具有先进后出、后进先出的特点。队列也是一种特殊的线性表，它的特殊性表现在约定了在这种线性表中数据的插入在表的一端进行，数据的删除在表的另一端进行，因此队列具有先进先出，后进后出的特点。2.3设计一个算法，求顺序表中值为x的结点的个数。顺序表的存储结构定义如下：#i
7、nclude#define N 100 /*预定义最大的数据域空间*/typedef int datatype;/*假设数据类型为整型*/typedef struct datatype aN;/*此处假设数据元素只包含一个整型的关键字域*/int size;/*线性表长度*/sequence_list;/*预定义的顺序表类型*/算法count（）用于求顺序表H中值为x的结点的个数。int count（sequence_list*H,datatype x）int j=0;int i;for（i=0;isize;i+）if（H-ai=x）j+;return j;2.4 设计一个算法，将一个顺序表倒
8、置。即，如果顺序表各个结点值存储在一维数组a中，倒置的结果是使得数组a中的a0等于原来的最后一个元素，a1 等于原来的倒数第2个元素，a的最后一个元素等于原来的第一个元素。实现顺序表倒置的算法程序如下：void verge（seqlist*L）int t,i,j;i=0;j=L-length-1;while（idatai;L-datai+=L-dataj;L-dataj-=t;2.5已知一个顺序表中的各结点值是从小到大有序的，设计一个算法，插入一个值为x的结点，使顺序表中的结点仍然是从小到大有序。实现本题要求的算法程序如下：6 void insertx（seqlist*L,datatype x
9、）int j;if（L-lengthlength-1;while（j=0&L-datajx）L-dataj+1=L-dataj;j-;L-dataj+1=x;L-length+;2.6 将下列中缀表达式转换为等价的后缀表达式。（1）5+6*7（2）（5-6）/7（3）5-6*7*8（4）5*7-8（5）5*（7-6）+8/9（6）7*（5-6*8）-9【答】：（7）5+6*7 后缀表达式：5 6 7*+（8）（5-6）/7 后缀表达式：5 6-7/（9）5-6*7*8 后缀表达式：5 6 7*8*-（10）5*7-8 后缀表达式：5 7*8-（11）5*（7-6）+8/9 后缀表达式：5 7
10、6-*8 9/+（12）7*（5-6*8）-9 后缀表达式：7 5 6 8*-*9-2.7 循环队列存储在一个数组中，数组大小为n，队首指针和队尾指针分别为front和rear，请写出求循环队列中当前结点个数的表达式。循环队列中当前结点个数的计算公式是：（n+rear-front）%n 2.8编号为1,2,3,4的四列火车通过一个栈式的列车调度站，可能得到的调度结果有哪些？如果有n列火车通过调度站，请设计一个算法，输出所有可能的调度结果。方法一：算法思想：逐次输出所有可能，用回溯法。即：总体：对原始序列中的每一个元素，总是先入栈，后出栈 1入栈后的操作：a.该元素出栈；b.下一个元素入栈；2出
11、栈后的操作：a.（栈中其他元素）继续出栈；b.（原始序列中）下一个数入栈；注意：回溯法，关键在于回溯，即在某分支结点X：处理X的一个子分支，再退回分支X，接着处理X的下一个子分支,若所有X的子分支处理完，再退回上一层分支节点。所谓“退回”，7 实际上就是恢复。程序代码：（2_8_1.c）#include#define MAX 26 typedef struct s char aMAX;int top;Stack;/*定义一些全局变量*/Stack S;/*定义全局性的栈*/char dMAX,seqMAX;/*dMAX用于存储原始入栈序列，seqMAX用于存储输出序列*/int len;/*定
12、义将通过栈的元素个数*/int count=0;/*用于统计输出序列的个数 */void initStack（Stack*S）/*初始化空栈*/S-top=-1;void push（Stack*S,char x）/*进栈*/if（S-top=MAX）return;S-top+;S-aS-top=x;char pop（Stack*S）/*出栈*/if（S-top=-1）printf（ERROR,POP Empty Stack）;return-1;S-top-;return S-aS-top+1;int isEmpty（Stack*S）/*判断栈是否为空*/if（S-top=-1）return 1
13、;return 0;void outSeq（char*seq,int len）/*输出顶点序列*/int i;ilen;i+）printf（%2c,seqi）;printf（n）;void scheduler（int pos,int seq_pos）8 /*pos:处理到原始数据中的第pos个元素，seq_pos：若出栈，应放在当前输出数组的第seq_pos个位置*/int i=0;char t;/*对任何一个数，总是先进栈，再出栈。另外，这里不需要循环，类似于“查找数组中元素”用递归*/if（pos=len&isEmpty（&S）outSeq（seq,len）;count+;int main
14、（）int i;printf（nplease input the num be scheduled:）;scanf（%d,&len）;/*用len存储待调度的火车数量*/for（i=0;i1时，perm（R）由（r1）perm（R1）,（r2）perm（R2）,（rn）perm（Rn）构成。依此递归定义，可设计产生perm（R）的递归算法如下：递归解法：（2_8_2.c）#include int cont=1;/*全局变量，用于记录所有可能的出栈序列个数*/void print（int str,int n）;/*求整数序列str从k到n的全排列*/void perm（int str,int k
15、,int n）int i,temp;if（k=n-1）print（str,n）;else for（i=k;i+）temp=strk;strk=stri;stri=temp;perm（str,k+1,n）;/*递归调用*/temp=stri;stri=strk;strk=temp;/*本函数判断整数序列str是否满足进出栈规则,若满足则输出*/void print（int str,int n）int i,j,k,l,m,flag=1,b2;i+）/*对每个stri判断其后比它小的数是否为降序序列*/m=0;jstrj）if（m=0）bm+=strj;else if（strjb0）flag=0;e
16、lse b0=strj;if（flag）/*满足出栈规则则输出str中的序列*/10 printf（%2d:,cont+）;i+）printf（%d,stri）;int main（）int str100,n,i;printf（input a int:/*输出排列的元素个数*/scanf（%d,&n）;i+）/*初始化排列集合*/stri=i+1;printf（input the result:perm（str,0,n）;当参与进出栈的元素个数为4时，输出的结果如下图所示。该算法执行的时间复杂度为O（n!）。随着n的增大，算法的执行效率非常的低。非递归解法：（2_8_3.c）对一组数穷尽所有排列
17、，还可一种更直接的方法，将一个排列看作一个长整数，则所有排列对应着一组整数，将这组整数按从小到大的顺序排成一个数列，从对应最小的整数开始，按数列的递增顺序逐一列举每个排列对应的每一个整数，这能更有效地完成排列的穷举。从一个排列找出对应数列的下一个排列可在当前排列的基础上作部分调整来实现。倘若当前排列为1,2,4,6,5,3，并令其对应的长整数为124653。要寻找比长整数124653更大的排列，可从该排列的最后一个数字顺序向前逐位考察，当发现排列中的某个数字比它前一个数字大时，如本例中的6比它的前一位数字4大，则说明还有可能对应更大整数的排列。但为顺序从小到大列举出所有的排列，不能立即调整得太
18、大，如本例中将数字6与数字4交换得到的排列为126453就不是排列124653的下一个排列。为得到排列124653的下一个排列，应从已考察过的那部分数 11 字中选出比数字4大，但又是它们中最小的那一个数字，比如数字5，与数字4交换。该数字也是从后向前考察过程中第一个比4大的数字，5与4交换后，得到排列125643。在前面数字1，2，5固定的情况下，还应选择对应最小整数的那个排列，为此还需将后面那部分数字的排列颠倒，如将数字6，4，3的排列顺序颠倒，得到排列1,2,5,3,4,6，这才是排列1，2，4，6，5，3的下一个排列。按照以上想法可以编写非递归程序实现n个数的全排列，对满足进出栈规则的
19、排列则计数并输出。/*本程序输出1 2.n个序列进栈出栈的序列*/#include int pl（int n）int a100;/*最大处理范围为99个数*/int flag=1,flag1=0;FILE*rf;int i,j,k,x,count=0;rf=fopen（stack.txt,w）;/*pl.txt用于存放进出栈序列结果*/for（i=1;i=n;i+）/*初始序列*/ai=i;while（flag）/*还剩余未输出的排列*/flag1=1;/*判断本次排列是否符合进栈出栈序列 */for（i=1;i+）j=i+1;while（jai）j+;/*找ai后第一个比ai小的元素aj*/
20、k=j+1;while（k=n）/*如果aj后还有比ai小且比aj大的元素,则此排列无效*/if（ak aj）flag1=0;k+;if（flag1）for（i=1;i1&aij&aiaj）i-;12 k=aj;/*交换两元素的值*/aj=ai;ai=k;k=j+1;/*对交换后后面的数据由小到大排序*/for（i=k+1;i=k&xnext=NULL Bp=NULL Cp-next=head Dp=head（3）在带头结点的单链表中查找x应选择的程序体是（C）。Anode*p=head-next;while（p&p-info!=x）p=p-next;if（p-info=x）return p
21、else return NULL;Bnode*p=head;return p;Cnode*p=head-next;Dnode*p=head;while（p-info!（4）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（D）。A必须是连续的 B部分地址必须是连续的 C一定是不连续的 D连续不连续都可以（5）在一个具有n个结点的有序单链表中插入一个新结点并保持单链表仍然有序的时间复杂度是（B）。AO（1）BO（n）CO（n2）DO（nlog2n）（6）用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时（D）。A仅修改队头指针 B仅修改队尾
22、指针 C队头、队尾指针都要修改 D队头,队尾指针都可能要修改（7）若从键盘输入n个元素，则建立一个有序单向链表的时间复杂度为（B）。AO（n）BO（n2）CO（n3）DO（nlog2n）（8）下面哪个术语与数据的存储结构无关（D）。A顺序表 B链表 C散列表 D队列（9）在一个单链表中，若删除p所指结点的后续结点，则执行（A）。Ap-next=p-next-next;Bp=p-next;p-next=p-next-next;Cp-next=p-next;Dp=p-next-next;（10）在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（B）。As-next=p;p-
23、next=s;Bs-next=p-next;Cs-next=p-next;p=s;Dp-next=s;s-next=p;3.2 设计一个算法，求一个单链表中的结点个数。单链表存储结构定义如下（相关文件：linklist.h）#include 14#include typedef struct node int data;struct node*next;linknode;typedef linknode*linklist;/*尾插法创建带头结点的单链表*/linklist creatlinklist（）linklist head,r,s;int x;head=r=（linklist）mallo
24、c（sizeof（linknode）;printf（n请输入一组以0结束的整数序列：x）;while（x）s=（linklist）malloc（sizeof（linknode）;s-data=x;r-next=s;r=s;r-next=NULL;return head;/*输出带头结点的单链表*/void print（linklist head）linklist p;p=head-next;printf（List is:while（p）printf（%5d,p-data）;p=p-next;基于上述结构定义，求单链表中的结点个数的算法程序如下：int count（linklist head）i
25、nt c=0;linklist p=head;while（p）15 c+;return c;3.3设计一个算法，求一个带头结点单链表中的结点个数。带头结点的单链表的存储结构定义同题3.2，实现本题功能的算法程序如下（3_3.c）#include linklist.h int count（linklist head）int c=0;linklist p=head-next;while（p）c+;main（）/*测试函数*/linklist head;head=creatlinklist（）;print（head）;printf（nLength of head is:%d,count（head）;
26、getch（）;当输入5个数据时，产生的输出结果如下图所示：3.4设计一个算法，在一个单链表中值为y的结点前面插入一个值为x的结点。即使值为x的新结点成为值为y的结点的前驱结点。#include linklist.h void insert（linklist head,int y,int x）/*在值为y的结点前插入一个值为x的结点*/linklist pre,p,s;pre=head;16 p=head-next;p-data!=y）pre=p;if（p）/*找到了值为y的结点*/s=（linklist）malloc（sizeof（linknode）;pre-next=s;void main
27、（）/*测试程序*/linklist head;int y,x;/*创建单链表*/print（head）;/*输出单链表*/printf（n请输入y与x的值:scanf（%d%d,&y,&insert（head,y,x）;程序的一种运行结果如下图所示：3.5设计一个算法，判断一个单链表中各个结点值是否有序。#include linklist.h int issorted（linklist head,char c）/*当参数c=a时判断链表是否为升序，当参数c=d是判断链表是否为降序*/int flag=1;switch（c）17 case a:/*判断带头结点的单链表head是否为升序*/while（p&p-next&flag）if（p-datanext-data）p=p-next;else flag=0;break;case d:/*判断带头结点的单链表head是否为降序*/while（p&flag）if（p-data=p-next-data）p=p-next;return flag;int main（）/*测试程序*/linklist head;he
