《数据结构-C语言版》第一章绪论单项选择题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.在对算法的时间复杂度进行估计的时候,下列最佳的时间复杂度是______。
2A.nB.nlognC.nD.logn7.设使用某算法对n个元素进行处理,所需的时间是T(n)=100nlog2n+200n+2000,则该算法的渐近时间复杂度为_______。
A.O(1)B.O(n)C.O(200n)D.O(nlog2n)1CDCBBDD第二章线性表单项选择题1.链表不具有的特点是________。
A.可随机访问任一元素B.插入和删除时不需要移动元素C.不必事先估计存储空间D.所需空间与线性表的长度正比2.设顺序表的每个元素占8个存储单元。
第1个单元的存储地址是100,则第6个元素占用的最后一个存储单元的地址为。
A.139B.140C.147D.1483.在线性链表存储结构下,插入操作算法。
A.需要判断是否表满B.需要判断是否表空C.不需要判断表满D.需要判断是否表空和表满4.在一个单链表中,若删除p所指结点的后继结点,则执行。
A.p->next=p->next->next;B.p->next=p->next;C.p=p->next->next;D.p=p->next;p->next=p->next->next;5.将长度为 n的单链表接在长度为m的单链表之后的算法时间复杂度为。
A.O(n)B.O(1)C.O(m)D.O(m+n)6.需要预分较大空间,插入和删除不需要移动元素的线性表,其存储结构是。
A.单链表 B.静态链表 C.线性链表 D.顺序存储方式ACCABB填空题1.在带表头结点的单链表中,当删除某一指定结点时,必须找到该结点的_____结点。
2.在单链表中,指针p所指结点为最后一个结点的条件是。
3.将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数是。
4.在一个长度为n的顺序表中第i个元素(1≤i≤n)之前插入一个元素时,需向后移动元素的个数是。
5.在长度为 n的顺序表中插入一个元素的时间复杂度为。
1前驱2p->next==NULL23.14.n-i+15.O(n)例题解析【例2-1】编写一个算法将一个单链表逆转,要求在原表上进行,不允许重新建链表。
解:该算法可以在遍历原表的时候将各结点的指针逆转,从原表的第一个结点开始,头结点的指针在最后修改成指向原表的最后一个结点,即新表的第一个结点。
实现本题功能的函数如下:voidinverse(Lnode*h){s=h->next;if(s==NULL) return;q=NULL;p=s;while(p!=NULL){p=p->next;s->next=q; /*逆转指针*/q=s; /*指针前移*/s=p; }h->next=q; /*头指针h的后继是p*/}【例2-2】编写一算法将两个按元素值递增有序排列的单链表A和B归并成一个按元素值递增有序排列的单链表C。
解:对于两个或两个以上的,结点按元素值有序排列的单链表进行操作时,应采用“指针平行移动,依次扫描完成”的方法。
从两表的第一个结点开始顺链表逐个将对应数据元素进行比较,复制小的并插入c表尾。
当两表中之一已到表尾,则复制另一个链表的剩余部分,插入到c表尾。
设pa、pb分别指向两表当前结点,p指向c表的当前表尾结点。
若设A中当前所指的元素为a,B中当前所指的元素为b,则当前应插入到C中的元素c为a a bca bb例如:A=(3,5,8,11)B=(2,6,8,9,11,15,20)则C=(2,3,5,6,8,8,9,11,11,15,20)实现本题功能的函数如下:Lnode*hb(Lnode*pa,Lnode*pb){Lnode*p,*q,*pc;pc=(Lnode*)malloc(sizeof(Lnode)); /*建立表c的头结点pc*/3p=pc; /*p指向C表头结点*/while(pa!=NULL&&pb!=NULL){q=(Lnode*)malloc(sizeof(Lnode)); /*建立新结点q*/if(pb->data<pa->data) /*比较A、B表中当前结点的数据域值的大小*/{q->data=pb->data; /*B中结点值小,将其值赋给q的数据域*/pb=pb->next; /*B中指针pb后移*/}else{q->data=pa->data; /*相反,将A结点值赋给q的数据域*/pa=pa->next; /*A中指针pa后移*/}p->next=q; /*将q接在p的后面*/p=q; /*p始终指向C表当前尾结点*/}while(pa!=NULL) /*若表A比B长,将A余下的结点链在C表尾*/{q=(Lnode*)malloc(sizeof(Lnode));q->data=pa->data;pa=pa->next;p->next=q;p=q;}while(pb!=NULL) /*若表B比A长,将B余下的结点链在C表尾*/{q=(Lnode*)malloc(sizeof(Lnode));q->data=pb->data;pb=pb->next;p->next=q;p=q;}p->next=NULL;p=pc; /*p指向表C的头结点pc*/pc=p->next; /*改变指针状态,使pc指向p的后继*/free(p); /*释放p空间*/return(pc);}此算法的时间复杂度为O(m+n),其中m,n分别是两个被合并表的表长。
4第三章栈和队列单项选择题1.在初始为空的堆栈中依次插入元素f,e,d,c,b,a以后,连续进行了三次删除操作,此时栈顶元素是。
A.cB.dC.bD.e2.若某堆栈的输入序列是1,2,3,...,n,输出序列的第一个元素为n,则第i个输出元素为。
A.iB.n-iC.n-i+1D. 哪个元素无所谓3.向一个栈顶指针为h的带头结点链栈中插入指针s所指的结点时,应执行。
A.h->next=s;B.s->next=h;C.s->next=h;h=h->next;D.s->next=h->next;h->next=s;4.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是。
A.edcbaB.decbaC.dceabD.abcde5.栈和队列的共同点是。
A. 都是先进后出B. 都是先进先出C. 只允许在端点处插入和删除元素D. 没有共同点6.对于循环队列。
A.无法判断队列是否为空B.无法判断队列是否为满C.队列不可能满D.以上说法都不是7.若用一个大小为6的数组来实现循环队列,且当前队尾指针rear和队头指针front的值分别为0和3。
当从队列中删除一个元素,再加入两个元素后,rear和front的值分别为。
A.1和5B.2和4C.4和2D.5和18.判定一个循环队列QU(最多元素为m0)为满队列的条件是。
A.QU->front==QU->rearB.QU->front!=QU->rearC.QU->front==(QU->rear+1)%m0D.QU->front!=(QU->rear+1)%m09.判定一个循环队列QU(最多元素为m0)为空的条件是。
A.QU->front==QU->rearB.QU->front!=QU->rearC.QU->front==(QU->rear+1)%m0D.QU->front!=(QU->rear+1)%m0BCDCCDACA填空题1.在求表达式值的算符优先算法中使用的主要数据结构是。
2.设有一个空栈,现输入序列为1,2,3,4,5。
经过push,push,pop,push,pop,push,pop,push后,输出序列是。
3.仅允许在同一端进行插入和删除的线性表称为。
7.在顺序栈s中,栈为空的条件是,栈为满的条件是_____。
4.用S表示入栈操作,X表示出栈操作,若元素入栈顺序为1234,为了得到1342出栈顺5序,相应的S、X操作串为。
5.用一个大小为1000的数组来实现循环队列,当前rear和front的值分别为0和994,若要达到队满的条件,还需要继续入队的元素个数是。
1.栈2.2343.栈4.s.top==s.base, s.top-s.base>=s.stacksize SXSSXSXX5.993例题解析【例3-1】编程实现:用除法把十进制数转换成二进制数。
解:算法思想:用初始十进制数除以2把余数记录下来并且若商不为0则再用商去除以2直到商为0,这时把所有的余数按出现的逆序排列起来(先出现的余数排在后面,后出现的余数排在前面)就得到了相应的二进制数,如把十进制数35转换成二进制数的过程如图3-1所示。
35余数结果:1001117 18 14 02 01 1图3-1 十进制数转换成二进制数的过程由题意可知,我们可以用一个栈来保存所有的余数,当商为0时则让栈里的所有余数出栈则可以得到正确的二进制数,算法可描述如下:voidconversion(){StackS;intn;InitStack(&S);printf("Inputanumbertoconvert:\n");scanf("%d",&n);if(n<0){printf("\nThenumbermustbeover0.");6return;}if(n==0)Push(S,0);while(n!=0){Push(S,n%2);n=n/2;}printf("theresultis:");while(!StackEmpty(*S)){printf("%d",Pop(S));}}}第四章串单项选择题1.串是一种特殊的线性表,其特殊性体现在。