发布时间 : 星期日 文章软件基础基本概念问答2012更新完毕开始阅读dd4c4fc91eb91a37f1115cb6
Li=L0+(i-1)*m。其中L0为第一个数据元素的存储地址，m为一个数据元素占用的存储单元的个数。
插入和删除数据时，会引起大量的数据移动。
23．什么是算法，一个算法应该具有的特性是什么。
算法（Algorithm）是求解问题的方法的步骤序列。 一个算法应该具有下列特性：
⑴有穷性：一个算法必须在有穷步之后结束。 ⑵确定性：算法的每一步必须有确切的定义。
⑶可行性：算法中的每一步都可以通过基本运算得以实现。 ⑷输入：一个算法具有零个或多个输入。
⑸输出：一个算法具有一个或多个输出，输出同输入之间存在某种特定的关系。
24．对一个算法要求有那些。
设计一个算法通常要考虑以下的要求。
⑴正确：算法的执行结果应当满足预先规定的功能和性能要求。 ⑵可读：一个算法应当思路清晰、层次分明、简单明了、易读易懂。 ⑶健壮：当输入不合法数据时，应能作适当处理，不至引起严重后果。 ⑷高效：有效使用存储空间和有较高的时间效率。
25. 什么是算法的时间复杂度和空间复杂度。
算法的时间复杂度：指执行算法时所需的时间（与问题的规模有关）。 算法的空间复杂度：指在实现算法时所需的存储量。
26. 叙述线性表的定义及其逻辑特征。
线性表：由n(n≥0)个相同类型的数据元素a1，a2，...，an组成的有限序列，记作： L=（a1，a2，? an）
线性表的逻辑特征为：
有且仅有一个开始数据元素a1，它没有直接前驱，y有且仅有一个直接后继a2； 有且仅有一个最后数据元素an，它没有直接后继，仅有一个直接前驱an-1； 其余的数据元素 ai (1 对于仅有一个数据元素的线性表(n=1)，数据元素a1既是开始数据元素又是最后数据元素，它没有直接前驱，也没有直接后继。 27. 什么是顺序表、链表。 线性表中各元素依次存储在连续的一块存储空间中，用这种存储形式存储的线性表称其为顺序表。即逻辑结构上相邻的数据元素，其在物理位置上也是相邻的。 线性表的链式存储结构是把线性表的数据元素存放在结点中，结点(node)由数据元素域和一个或若干个指针域组成，指针域存放其他结点的存储地址。用链式存储方式存储的线性表称线性链表，简称链表。 28. 描述在顺序表和链表上进行插入和删除操作的实现算法。 1）在顺序表上完成插入元素的操作步骤和在设计算法时注意的问题。 在具有n个元素的线性表的第i（1≤i≤n+1）个位置上插入一个值为 x 的新元素，在顺 序表上完成插入元素的操作步骤如下： (1) 从第n个元素开始，一直到第i个元素，依次向后移动一个位置，空出第i个元素的位置； (2) 将x置入空出的第i个位置； (3) 顺序表长度加1。 在设计算法时注意以下问题： (1) 检查顺序表是否已存满数据元素，若满则产生溢出错误。 (2) 检查插入位置的有效性，这里 i 的有效范围是：1≤i≤n+1，其中 n 为顺序表的长度。 (3) 注意数据的移动方向，从最后一个元素开始依次向后移动一个位置，直到第i个元素为止。 2）在顺序表上完成删除运算的主要步骤。 在顺序表上完成删除运算的主要步骤如下： (1) 从第i+1个元素开始，一直到第n个元素，依次向前移动一个位置， (2) 顺序表长度减1。 实现删除运算算法应注意以下问题： (1) 删除第i个元素，i 的取值为 1≤i≤n ,否则第i个元素不存在，因此，要检查删除位置的有效性。 (2) 当表空时不能做删除，因表空时 L->Length的值为0，图2-6 中的条件（i>=1 且 i<=n）包括了对表空的检查，即当n=0时该条件不成立，删除失败。 (3) 删除 ai 之后，顺序表长度减1。 3）设p指向单链表中某一结点，请给出在p所指结点之后插入值为 x 的新结点的算法描述。 插入操作的算法描述如下： (1) 生成一个新结点q，将x赋值于q的数据域； (2) 使q的指针域指向p结点的后继； (3) 使p结点的指针域指向q所指结点。 (4) 插入操作结束。 29. 叙述栈和队列的定义及其逻辑特征。 栈是只能在表的一端进行插入和删除的线性表。栈中允许插入和删除的一端称为栈顶(top)，另一端是固定端，称为栈底(bottom)。由于只允许在栈顶进行插入和删除，所以栈的操作是按“后进先出”的原则进行的，因此，栈又称为后进先出 (Last In First Out，简称 LIFO) 的线性表。 插入和删除操作分别在两端进行的线性表称为队列(queue)。向队列中插入元素的过程称为入队(enqueue)，删除元素的过程称为出队(dequeue)。允许入队的一端称为队尾(rear)，允许出队的一端称为队头(front)。由于队列中出队的数据元素一定是队列中最早入队的数据元素，所以队列又称为“先进先出表”(First In First Out，简称FIFO)。 30. 描述在顺序栈、链栈、顺序队和链队上进行插入和删除操作的实现算法。 顺序栈入栈： int Push_SeqStack (SeqStack *s, DataType x) {if (Full_SeqStack(s)) return -1; /*栈满*/ else { s->data[s->top]=x; s->top++; return 0;} } 顺序栈出栈： int Pop_SeqStack(SeqStack *s, DataType *x) { if (Empty_SeqStack (s) ) return -1; /*栈空，返回-1 */ else { s->top--; *x=s->data[s->top]; /*栈顶元素存入*x */ return 0; } } 链栈入栈： void Push_LinkStack（LinkStack *top, DataType x） { LinkStack *s; s=(LinkStack *)malloc(sizeof（LinkStack））; s->data=x; s->next=top->next; top->next=s;} 链栈出栈： int Pop_LinkStack (LinkStack *top, DataType *x) { StackNode *p; if （Empty_LinkStack(top)） return -1; /*栈空，返回-1 */ else { p=top->next; /*p指向栈顶元素 */ top->next=p->next; /*将p所指结点从链栈中删除*/ *x = p->data; /*栈顶元素值存入*x中 */ free(p); /*释放p所指结点占用的空间*/ return 0; /*操作成功，返回0 */ } } 顺序队入队操作： int In_SeqQueue ( c_SeqQ *q , DataType x) { int result; if (q->num==MAXSIZE) {printf(＂队满＂); result=-1; } /*队满不能入队*/ else { q->data[q->rear]=x; q->rear=(q->rear+1)%MAXSIZE; q->num++; result=0; } /*入队成功*/ return result;} 顺序队出队操作： int Out_SeqQueue (c_SeqQ *q , DataType *x) { int result; if (num==0) { printf(“队空”);result=-1;} /*队空不能出队*/ else { *x=q->data[q->front]; /*读出队头元素*/ q->front=(q->front+1) % MAXSIZE; q->num--; result=0;} return result;} 链队入队： void In_LinkQueue(LinkQ *q , DataType x) { QNode *p; p=(QNode*)malloc(sizeof(QNode)); /*申请新结点*/ p->data=x; p->next=NULL; q->rear->next=p; q->rear=p; } 链队出队： int Out_LinkQ(LinkQ *q , DataType *x) { QNode *p; int result; if (q->front->next==NULL) { printf (\队空\ /*出队失败*/ else { p=q->front->next; q->front->next=p->next; *x=p->data;/*队头元素放x中*/ free(p); /*当队列中只有一个元素时，出队后队空，此 if (q->front->next==NULL)时还要修改队尾指针*/ q->rear=q->front; result=0; }return result;} 31. 叙述数组的定义及其逻辑特征。 数组是由同类型数据元素组成的有序集合，称构成数组的各数据元素为数组元素，每一个数组元素都有自己的编号，称为该数组元素的下标，数组元素在数组中的位置由数组元素的下标确定。称其元素只有一个下标的数组为一维数组，元素有两个下标的数组为二维数组，依次类推。 数组可以看作线性表的推广。比如：一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，依此类推 32. 叙述数组与矩阵和向量的关系。 程序设计语言中，用一维数组表示向量，用二维数组表示矩阵。 33. 叙述特殊矩阵的存储策略。 为了节省存储空间，根据特殊矩阵的特征，使存储的数据尽可能的少。