第一阶段测考试试题汇总--答案

《第一阶段测考试试题汇总--答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、1、算法有哪些特征？怎样评价一个算法？答：算法有五个特性，分别为确定性、有穷性、可行性、0个或多个输入、1个或多个输出。评价算法可以从时间复杂度和空间复杂度来衡量其效率。2、头指针和头结点的类型不一样吗？答：略3、什么是静态分配？什么是动态分配？答：①静态分配是指变量或数据的空间是在程序加载时分配，其空间大小在程序运行不会改变，空间的分配和释放不能通过代码控制；②动态分配是指数据空间是在程序运行过程中分配的，空间的释放也是在程序运行过程中通过代码完成。4、在单链表中，什么是头结点？什么是头指针？什么是首元结点？答：头结点：为保护头指针而在链表

2、中增设的结点，其数据域一般不用，指针域用以存储首元结点的地址；头指针：链表访问的起点，在带头结点的单链表中存储头结点的地址，在不带头结点的单链表中存储首元结点的地址；首元结点：第一个元素结点。首元节点头指针头结点(头指针可以指向头结点或者首元节点)5、在单链表、双向链表和单循环链表中，若仅知道指针P指向某结点，不知道头指针，能否将结点*P从相应的链表中删去？若可以，其时间复杂度为多少？答：不管是什么链表，要将结点P从链表中删除均需找到P的前驱结点。如果是单链表，在不知头指针的条件下无法找到前驱，故无法删除；如果是双向链表，则可通过P的前驱指针

3、找到其前驱结点，故可直接删除，无需查找，其时间复杂度为0(1)；如果是循环链表，则可通过指针移动找到其前驱，其时间复杂度为0(N)e6、顺序栈和链栈哪一种更好？为什么？IIII7、递归算法效率是否非常低?II8、在顺序队列操作中，什么是“假溢出”现象？怎样解决这种现象？答：在顺序队列中，可能会因为频繁的入队和出队操作造成队列有剩余空间却无法完成入队操作的现象，即为“假溢出”现象。可采用循环队列来解决此问题，通过求余运算将队列从逻辑上构造成一个环状结构。9、循环队列的优点是什么？如何判定它的空和满?答、循环队列可以解决顺序队列中出现的假溢出现象

4、，但仅凭头尾指针是否相等无法区分队空和队满。此时有两种方案可以解决此问题。一是使用标识符,如length来记录队列元素个数，当length==O时队列为空，当length==MAXQSIZE时队列已满；另一种方案是少用一个元素空间,约定以队列头指针在队尾指针的下一个位置作队列呈满状态的标志，头尾指针相等时队列为空。10、下述算法的功能是什么？LinkListDemo(LinkListL)ListNode*P,*Q;if(L&&L->next)Q=L;L=L->next;P=L;While(P->next)P=P->next;P->next=Q

5、;Q->next=NULL;returnL;答：将链表的头结点移至链表末尾，原链表首元结点作为新的头结点。11、下述算法的功能是什么？SqQueueQ1,Q2;intx,1,m=0;while(!QueueEmpty(QI))x二DeQueue(QI);EnQueue(Q2,x);m++;for(1=0;Km;1++){x二DeQueue(Q2);EnQueue(QI,x);EnQueue(Q2,x);答：将队列QI的元素复制到队列Q2中。12、下述算法的功能是什么？voiddemo2(SqQueue*Q){intx;SqStackS;lni

6、tStack(&S);while(!QueueEmpty(Q)){x二DeQueue(Q);push(S,x);Iwhile(!StackEmpty(S)){x=pop(S);Enqueue(Q,x);II答：将队列Q的元素按逆序存储，其第一个元素的起始位置将下移一段距离,此距离为队列的长度。13、指岀下列程序段的功能是什么？1)voiddemol(SqStack*S)int1,arr[64],n=0;while(!StackEmpty(S))arr[n++]二pop(S);for(1=0;Kn;1++)push(s,arr[1]);}答：将

7、栈中元素按逆序存放。14、设计算法，实现顺序表的选择排序(元素类型为整型)voidSelectSort(SqListL){for(i=0;iL・elem[i];}}}15、设计算法，实现顺序表的冒泡排序(元素类型为整型)voidBubbleSort(SqListL){change=l;for(i=l;i

8、l;i++){change=0;for(j=0;j