数据结构教程 第二十五课 单元测验

教学目的： 复习前面所学的内容,检验学习效果,拾遗补缺

教学重点：

教学难点：

授课内容：

    测验题:

一，填空：

       1. 基本数据结构有＿＿＿＿，＿＿＿＿，＿＿＿＿，＿＿＿＿四种。
       2. 存储结构可根据数据元素在机器中的位置是否连续分为＿＿＿＿，＿＿＿＿。
       3. 算法的基本要求有＿＿＿＿＿，＿＿＿＿＿，＿＿＿＿，＿＿＿＿。
       4. 度量算法效率可通过＿＿＿＿＿＿＿，＿＿＿＿＿＿＿两方面进行。
       5. 栈的定义：＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿。

二，简答：

       1. 举例说明数据对象、数据元素、数据项的定义。
       2. 类Ｃ语言和Ｃ语言有哪些主要区别？
       3. 线性表的基本操作有哪些？
       4. 写出类Ｃ语言定义的线性表的静态分配顺序存储结构。

三，算法设计：

       1. 下面是线性表的存储结构和插入算法，请补充算法中空缺部分。

          #define LIST_INIT_SIZE 100

          #define LISTINCREMENT 10

          typedef struct{

          ElemType *elem; //存储空间基址

          int length; //当前长度

          int listsize; //当前分配的存储容量以一数据元素存储长度为单位

          }SqList;

          status ListInsert(List *L,int i,ElemType e) {

          ____________ *p,*q;

          if (i<1||i>L->length+1) return ERROR;

          q=&(L->elem[i-1]);

          for(p=&L->elem[L->length-1];p>=q;--p)

          ________________;

          *q=e;

          __________________;

          return OK;

          }/*ListInsert Before i */
       2. 下面是栈的顺序存储结构和入栈、出栈算法，请补充算法中空缺部分。

    typedef struct{

    SElemType *base;

    SElemType *top; //设栈顶栈底两指针的目的是便于判断栈是否为空

    int StackSize; //栈的当前可使用的最大容量.

    }SqStack;

    Status Push(SqStack &S,SElemType e); {

    if(S.top - s.base>=S.stacksize) {

    S.base=(ElemType *) realloc(S.base,

    (S.stacksize + STACKINCREMENT) * sizeof(ElemType));

    if(!S.base)exit(OVERFLOW);

    S.top=S.base+S.stacksize;

    S.stacksize+=STACKINCREMENT;

    }

    *S.top++=＿＿＿＿＿;

    return OK;

    } //Push

    Status Pop(SqStack &S,SElemType &e); {

    if(＿＿＿＿＿＿＿＿)

    return ERROR;

    ＿＿＿＿＿=*--S.top;

    return OK;

    }//Pop

四，问答：

       1. 用图示法说明在单向线性链表中插入结点的过程。
       2. 有一学生成绩单，画出用链式存储结构时的成绩单数据的存储映像。
       3. 用Ｃ语言实现单向线性链表。写出存储结构定义及基本算法。