下载文档原格式
1.设n为正整数，利用大"O"记号，将下列程序段的执行时间表示为n的函数。
(1) i=1; k=0;while(i<n){ k=k+10*i;i++;}(2) i=1; j=0;while(i+j<=n){if (i>j) j++;else i++;}(3)x=n; // n>1while (x>=(y+1)*(y+1))y++;第二章线性表2.1下述算法的功能是什么?LinkList Demo(LinkList L){ // L是无头结点单链表ListNode *Q,*P;if(L&&L->next){Q=L;L=L->next;P=L;while (P->next) P=P->next;P->next=Q; Q->next=NULL;}return L;}// Demo答：该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。
2.9设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。
答：因已知顺序表L是递增有序表，所以只要从顺序表终端结点（设为i位置元素）开始向前寻找到第一个小于或等于x的元素位置i后插入该位置即可。
在寻找过程中，由于大于x的元素都应放在x之后，所以可边寻找，边后移元素，当找到第一个小于或等于x的元素位置i时，该位置也空出来了。
算法如下：//顺序表存储结构如题2.7void InsertIncreaseList( Seqlist *L , Datatype x ){int i;if ( L->length>=ListSize)Error(“overflow");for ( i=L -> length ; i>0 && L->data[ i-1 ] > x ; i--)L->data[ i ]=L->data[ i ] ; //比较并移动元素L->data[ i ] =x;L -> length++;}2.14已知单链表L是一个递增有序表，试写一高效算法，删除表中值大于min且小于max的结点(若表中有这样的结点)，同时释放被删结点的空间，这里min和max是两个给定的参数。
文档来源为:从网络收集整理.word 版本可编辑.欢迎下载支持.第1章 绪论1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。
解：数据是对客观事物的符号表示。
在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
数据对象是性质相同的数据元素的集合，是数据的一个子集。
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
存储结构是数据结构在计算机中的表示。
数据类型是一个值的集合和定义在这个值集上的一组操作的总称。
抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。
是对一般数据类型的扩展。
1.2 填空题：1.常见的数据结构有__结构，_____结构，____结构等三种。
2.常见的存储结构有_________结构，______结构等两种。
3.数据的基本单位是____，它在计算机中是作为一个整体来处理的。
4.数据结构中的结构是指数据间的逻辑关系，常见的结构可分为两大类，______和_____。
5.《数据结构》课程讨论的主要内容是数据的逻辑结构、存储结构和________。
1.2设有数据结构(D,R)，其中{}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r =试按图论中图的画法惯例画出其逻辑结构图。
解：1.3设有以下三个函数：()10002124++=n n n f ，()3450015n n n g+=，()n n n n h log 5005.3+=请判断以下断言正确与否：(1) f(n)是O(g(n)) (2) h(n)是O(f(n)) (3) g(n)是O(h(n)) (4) h(n)是O(n 3.5) (5) h(n)是O(nlogn)解：(1)对 (2)错 (3)错 (4)对 (5)错第二章序列2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。
一、选择题1、在数据结构中。
与所使用的计算机无关的是（D ）。
A、存储结构B、物理结构C、物理和存储结构D、逻辑结构2、非线性结构中每个结点（D）。
A、无直接前驱结点B、只有一个直接前驱和直接后继结点C、无直接后继结点D、可能有多个直接前驱和多个直接后继结点3、可以把数据的逻辑结构划分成（D ）。
A、内部结构和外部结构B、动态结构和静态结构C、紧凑结构和非紧凑结构D、线性结构和非线性结构4、算法指的是（D ）。
A、计算机程序B、解决问题的计算方法C、排序算法D、解决问题的有限运算序列5、在决定选取何种存储结构时，一般不考虑（A ）。
A、各结点的值如何B、结点个数的多少C、对数据有哪些运算D、所用编程语言实现这种结构是否方便6、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（C ）。
A、数据的处理方法B、数据元素的类型C、数据元素之间的关系D、数据的存储方法7、通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（ B ）。
A、数据元素具有同一特点B、不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致C、每个数据元素都一样D、数据元素所包含的数据项的个数要相等8、以下说法正确的是（A ）。
A、数据元素是数据的基本单位B、数据项是数据的基本单位C、数据结构是带结构的数据项的集合D、一些表面上很不相同的数据可以有相同的逻辑结构二、简答题：下面是几种数据的逻辑结构)S=，分别画出对应的数据D(R,逻辑结构，并指出它们分别属于何种结构。
defcD==Rba}{r},,{,,,=fed<d<>>ba<racbbd,,,,,>,,},><(><){,=fee>d<><bb<racbdc,,,,,>},,<>,)(>{,<=fde<<d><>rba>cbcdadb,,,,,,},,,,><><(>,{)<一、选择题1、下面关于线性表的叙述中，错误的是（D ）。
第一章绪论一．选择题1．下面关于算法说法正确的是（）A．算法最终必须由计算机程序实现B．为解决某问题的算法同为该问题编写的程序含义是相同的C．算法的可行性是指指令不能有二义性D．以上几个都是错误的2．以下哪一个术语与数据的存储结构无关？（）A．栈 B．哈希表 C．线索树 D．循环队列3．算法复杂度通常是表达算法在最坏情况下所需要的计算量，O(1)的含义是（）A．算法执行一步就完成B．算法执行1秒钟就完成C．算法执行常数步就完成 D．算法执行可变步数就完成4．数据结构研究的内容是（）。
A．数据的逻辑结构 B．数据的存储结构C．建立在相应逻辑结构和存储结构上的算法 D．包括以上三个方面5．一个正确的算法应该具有 5 个特性，除输入、输出特性外，另外 3 个特性是（）。
A．确定性、可行性、有穷性 B．易读性、确定性、有效性C．有穷性、稳定性、确定性 D．可行性、易读性、有穷性6．以下关于数据的逻辑结构的叙述中正确的是（）。
A．数据的逻辑结构是数据间关系的描述B．数据的逻辑结构反映了数据在计算机中的存储方式C．数据的逻辑结构分为顺序结构和链式结构D．数据的逻辑结构分为静态结构和动态结构7．下列时间复杂度中最坏的是（）A．O(1) B．O(n) C．O(log2n） D．O(n2)8．算法的时间复杂度取决于（）A．待处理数据的初态 B．问题的规模C．程序本身所占的空间 D．问题的规模和待处理数据的初态二．综合应用题1.有下列运行时间函数：（1）f1(n)=1000; （2）f2(n)=n2+1000n; （3）f3(n)=3n3+100n2+n+1;分别写出相应的大O表示的运算时间。
2.下面函数mergesort执行的时间复杂度为多少?假设函数调用为mergesort(1,n)，merge 函数时间复杂度为 O(n)void mergesort(int i,int j){int m;if(i!=j){mergesort(i,m);mergesort(m+1,j);merge(i,j,m);//本函数时间复杂度为 O(n)}}第二章线性表一．选择题1．下述哪一条是顺序存储结构的优点？（）A．存储密度大 B．插入运算方便C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示2．下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元。
第1章绪论1.1选择题1. 算法的时间复杂度取决于（）A）问题的规模B）待处理数据的初态C）A和B2.计算机算法指的是解决问题的步骤序列，它必须具备（）这三个特性。
A）可执行性可移植性可扩充性B）可执行性、确定性、有穷性C）确定性、有穷性、稳定性D）易读性、稳定性、安全性5．从逻辑上可以把数据结构分为（）两大类。
A）动态结构、静态结构B）顺序结构、链式结构C）线性结构、非线性结构D）初等结构、构造型结构6．在下面的程序段中，对x的赋值的语句频度为（）for(i=0;i<n;i++)for(j=0;j<n;j++) x=x+1;A）O(2n) B）O(n) C．O(n2) D．O(log2n)7．下面的程序段中，n为正整数，则最后一行的语句频度在最坏情况下是（）for(i=n-1;i>=1;i--)for(j=1;j<=i;j++)if (A[j]>A[j+1])A[j]与A[j+1]对换；A. O（n）B）O(nlog2n) C）O(n3) D）O(n2)1.2填空题2. 对于给定的n个元素,可以构造出的逻辑结构有_____________，_____________，_____________，_____________四种。
4．数据结构中评价算法的两个重要指标是_____________。
5. 数据结构是研讨数据的_____________和_____________，以及它们之间的相互关系，并对与这种结构定义相应的_____________，设计出相应的_____________。
6．一个算法具有5个特性：_____________、_____________、_____________，有零个或多个输入、有一个或多个输出。
9．已知如下程序段for(i=n;i>0;i--) {语句1}{ x=x+1; {语句2}for(j=n;j>=i;j--) {语句3}y=y+1; {语句4}}语句1执行的频度为_____________；语句2执行的频度为_____________；语句3执行的频度为_____________；语句4执行的频度为_____________。
10.下面程序段中带下划线的语句的执行次数的数量级是_____________。
i=1; while(i<n) i=i*2;11. 下面程序段的时间复杂度为_____________。
(n>1)sum=1;for (i=0;sum<n;i++) sum+=1;第2章线性表2.1选择题1．对于线性表最常用的操作是查找指定序号的元素和在末尾插入元素，则选择（）最节省时间A）顺序表B）带头结点的双循环链表C）单链表D）带尾结点的单循环链表2．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法时间复杂度为（）(1≤i≤n+1)。
A）O(0) B）O(1) C）O(n) D）O(n2)3．双向链表中有两个指针域，prior和next，分别指向前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为（）Ap->prior=q; q->next=p; p->prior->next=q; q->prior=p->prior;Bq->prior=p->prior;p->prior->next=q;q->next=p; p->prior=q->next;C）q->next=p; p->next=q; p->prior->next=q; q->next=p;Dp->prior->next=q; q->next=p; q->prior=p->prior; p->prior=q;4．在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（）A）O(nlog2n）B）O(1）C）O(n）D）O(n2）5．在一个以h 为头指针的单循环链中，p 指针指向链尾结点的条件是（）A）p->next==NULL B）p->next==hC）p->next->next==h D）p->data==-16．对于一个具有n个结点的线性表，建立其单链表的时间复杂度是（）A）O(n) B）O(1) C）O(nlog2n) D）O(n2)8．在双向链表存储结构中，删除p所指的结点时须修改指针（）A)p->prior->next=p->next ; p->next->prior=p->prior;B）p->prior=p->prior->prior p->prior->next=p;C）p->next->prior=p p->next=p->next->nextD)p->next=p->prior->prior p->prior=p->next->next;9．线性表采用链式存储时，其元素地址（）A）必须是连续的B）一定是不连续的C）部分地址是连续的D）连续与否均可2.2填空题1．线性表L=（a1，a2，…，an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_____________。
2．在单链表中设置头结点的作用是_____________。
主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。
另外，不论链表是否为空，链表头指针不变。
3．线性表的顺序存储是通过_____________来反应元素之间的逻辑关系，而链式存储结构是通过_____________来反应元素之间的逻辑关系。
4．当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，则采用_____________存储结构最节省时间，相反当经常进行插入和删除操作时，则采用_____________存储结构最节省时间。
5．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为_____________，在给定值为x的结点后插入一个新结点的时间复杂度为_____________。
7. 对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____________个，单链表为_____________个。
8. 循环单链表的最大优点是_____________。
9．若要在一个不带头结点的单链表的首结点*p结点之前插入一个*s结点时，可执行下列操作：s->next=_____________;p->next=s;t=p->data;p->data= _____________;s->data=_____________;10．某线性表采用顺序存储结构，每个元素占据4个存储单元，首地址为100，则下标为11的（第12个）元素的存储地址为_____________。
11．带头结点的双循环链表L中只有一个元素结点的条件是_____________。
2.3 判断题1．取线性表的第i个元素的时间同i的大小有关（）2．线性表的特点是每个元素都有一个前驱和一个后继（）3．顺序存储方式的优点是存储密度大，且插入、删除运算效率高（）4．线性表采用链表存储时，结点的存储空间可以是不连续的（）5．链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序存储结构中效率高（）6．顺序存储方式只能用于存储线性结构（）9．顺序存储结构的主要缺点是不利于插入或删除操作（）10．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好（）第3章桟和队列3.1选择题1．一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1≤i≤n）个元素是（）A）不确定B）n-i+1 C）i D）n-i2．设栈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）23．若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是（）A）top=top+1; V[top]=x B）V[top]=x; top=top+1C）top=top-1; V[top]=x D）V[top]=x; top=top-14．如果我们用数组A[1..100]来实现一个大小为100的栈，并且用变量top来指示栈顶，top 的初值为0，表示栈空。
请问在top为100时，再进行入栈操作，会产生（）A）正常动作B）溢出C）下溢D）同步5．栈在（）中应用。
A）递归调用B）子程序调用C）表达式求值D）A，Ｂ，Ｃ7．用链接方式存储的队列，在进行删除运算时（）A）仅修改头指针B）仅修改尾指针C）头、尾指针都要修改D）头、尾指针可能都要修改8．循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是( )A）(rear-front+m)%m B）rear-front+1C）rear-front-1 D）rear-front9．若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( )A）1和5 B）2和4 C）4和2 D）5和110．栈和队列的共同点是（）A）都是先进先出B）都是先进后出C）只允许在端点处插入和删除元素D）没有共同点11．在一个链队列中，假定front和rear分别为队头和队尾指针，则插入*s结点的操作为（）A）front->next=s;front=s; B）s->next=rear;rear=s;C）rear->next=s;rear=s; D）s->next=front;front=s;12．判定一个栈S（元素个数最多为MAXSIZE）为空和满的条件分别为（）A）S->top!=-1 S->top!=MAXSIZE-1B）S->top=-1 S->top=MAXSIZE-1C）S->top=-1 S->top!=MAXSIZE-1D）S->top!=-1 S->top=MAXSIZE-13.2填空题1．栈是_____________的线性表，其运算遵循_____________的原则。
