算法与数据结构复习知识.pptVIP

一、绪论 ;习题： 1、写出下列算法的时间复杂度。 （1） for(i=0;in;i+ +) c[i]=i； （2）for(i=0;im;i+ +) for(j=0;jn;j+ +) a[i][j]=i*j； 2、数据结构的研究对象包括（ ）。 3、从逻辑上可以把数据结构分为（ ）和（ ） 两种类型。;二、线性表;顺序表的存储结构： ;习题：给出顺序表的结构定义，在顺序表List中元素数组下标位置i插入一个元素x。 #define MAXSIZE 100 struct list //顺序表结构 { int v[MAXSIZE]; //元素数组 int len; //顺序表当前包含的元素个数 }; typedef struct list List; int insert(List *L , int i , int x) { //略 };（三）单循环链表： 使单链表的最后一个节点的指针域的值不为NULL, 而是指向头结点。这样，整个链表就形成了一个环，这种链表称为单循环链表。;习题： 1．线性表若采用链式存储结构时，要求内存中可用存储单元的地址（????? ）。 A）必须是连续的??????? B）部分地址必须是连续的 C）一定是不连续的????? D）连续或不连续都可以 2．链表不具备的特点是（ ）。 A） 插入和删除不需要移动元素 B）可随机访问任一节点 C） 不必预分配空间 D）所需空间与其长度成正比;3. 不带头结点的单链表head为空的判定条件是（ ）。 A）head = = NULL B）head—next = = NULL C）head—next = = head D）head ! = NULL 4．带头结点的单链表head为空的判定条件是（ ）。 A）head = = NULL B）head—next = = NULL C）head—next = = head D）head ! = NULL 5．带头结点的循环单链表head为空的判定条件是（ ）。 A）head = = NULL B）head—next = = NULL C）head—next = = head D）head ! = NULL;6．在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是(???? ?? )。 A）p=p-next;??????????B）p-next=p-next-next; C）p-next=p;??????????D）p=p-next-next; 7．在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为__________ 。;三、栈和队列;（二）队列 队列（queue )是限定只能在表的一端进行插入，在表的另一端进行删除的线性表。 ??尾(rear)——允许插入的一端； 队头(front)——允许删除的一端。 队列特点：先进先出(FIFO)或后进后出(LILO)。 ;顺序队列的存储结构： #define maxsize 100 typedef struct { elemtp elem[maxsize]; int rear,front; }squeuetp； rear指示队尾元素； front指示队头元素前一位置。;循环队列：把队列设想成环形。 为了区分队空、队满状态，少用一个元素空间：front所指单元不放元素。 队空：sq.front==sq.rear 队满：(sq.rear+1)%M==sq.front;习题： 1．栈是限定在（??? ）处进行插入或删除操作的线性表。 ? A）端点???????? B）栈底?????????C）栈顶??????????D）中间 2．栈的特点是（??? ）。 ? A）先进先出??????? B）后进先出???????? C）后进后出?????????????? D）不进不出 3．顺序栈存储空间的实现使用（??? ）存储栈元素。 ? A）链表????? ?B）数组???????C）循环链表???? ?D）变量 ;4．顺序栈是空栈的条件是（??? ）。 ? A）top= =0??????????? B）top= =1??????????? C）top= =-1??