数据结构期中考试模试卷2014

一. 单选题（每题1分，共14分）

1．数据结构所讨论的基本数据单位是（　B　）。

A、数据对象      B、数据元素      C、数据项      D、数据类

2. 在数据结构的讨论中把数据结构从逻辑上分为（　C　）两大类。

A.  内部结构与外部结构           B.  静态结构与动态结构

C.  线性结构与非线性结构         D.  紧凑结构与非紧凑结构。

3．若一个算法的时间复杂度用T(n)表示，其中n的含义是（　A  ）

A．问题规模    　　　B．指令条数

C．循环层数    　　　D．函数数量

4. 算法分析的目的是（　C　）。

A. 研究算法的输入与输出之间的关系

B. 找出数据结构的合理性

C. 分析算法的效率以求改进算法

D. 分析算法的可读性与可移植性

5、采用线性链表表示一个向量时，要求占用的存储空间地址（D　　）

A.  必须是连续的                  B. 部分地址必须是连续

C.  一定是不连续的              D. 可连续可不连续

6. 在一个当前长度为n的顺序表中向第j个元素（1A、n-j         B、n-j+1  　　　C、n-j-1       　D、j

7、带头结点的单链表为空的判定条件可以是：（B　　）

 　A、head==NULL

 　B、head一>next＝＝NULL

 　C、head一>next= = head

 　D、head!＝NULL

8、设单链表中指针P指向结点A，若要删除A之后的结点（若存在），则需要修改指针的操作为（　A　）

A、pnext=pnextnext　　　B、p=pnext

C、p=pnextnext　　　　　　D、pnext=p

9、若有一个最大长度为size，且设有队首指针front和队尾指针rear的顺序循环队列，试问判断队列满的条件应是下列哪一个语句（　D　）

A、front==rear                　B、front- rear==size    

C、front+rear==size;    　   　　D、front==(rear+1)%size

10. 设一个栈的入栈序列为1，2，3，4，5，6，则出栈序列不可能的是（B　  ）。

A、3，2，5，6，4，1　　　　　B、1，5，4，6，2，3

C、2，4，3，5，1，6　　　　　D、4，5，3，6，2，1

11、数据结构从总体上可分为两大类，串的逻辑结构与（　D　）的逻辑结构不属于同一类。

A线性表      B、栈      C、队列      D、树

12、对一非空广义表，其表尾是指（C　　）

A、广义表的最后一个元素

B、广义表的最后一个单个元素

C、广义表的最后一个子表元素

D、除第一个元素外的所有其余元素

13. 广义表A=(( ),(a),(b,(c,d)))的长度为（B　）

A、2　　　B、3　　　C、4　　　D、5

14. 每种数据结构都具备的三种最基本运算是（　A　）

A、插入、删除、遍历　　　　　B、输入、输出、删除

C、初始化、创建、销毁　　　　D、输入、输出、遍历

二、填空题(每小题2分，共28分)

1、数据结构学科讨论的是__非数值计算_________问题的数学模型及其涉及的基本操作在计算机中的表示与实现。

2、数据的物理结构是数据的逻辑结构在计算机存储器中的映象，它需要解决的主要问题是____数据元素之间的关系如何映象____________。

3、抽象数据类型（ADT）是编程语言提供的用户可自定义的一种数据类型，它主要由______数据_____和______操作_____两大部分组成。

4. 当算法中所有语句的频度之和T（n）与求解问题的规模无关时，那么该算法的时间复杂度为_O（1）__________阶。

5、线性结构反映数据元素间的逻辑关系是___一对一________的，图形结构中的数据元素之间的关系是___多对多________的，而树形结构中数据元素间的关系则是____一对多_______的。

6．以数组A[60]存放顺序循环队列的元素。假设当前队列有50个元素，且头指针front的值是47，则队列的尾指针rear的值应是_____37______。

6. 在双向循环链表中，设指针p指向待删除的结点，则删除结点p需执行的语句为_q->next = p->next;

______p->next->prior = q

7. 先进先出队列与优先级队列与队列的不同，主要是在于___入队_______操作的处理。

8. 矩阵中的非0元素与矩阵的规模之比称为稀疏因子δ，如果δ的值不大于________0.05___，则称矩阵为稀疏矩阵。

9. 对于一个n×n的对称矩阵可以只用一个有____n(n+1）/2______个存储单元的一维数组来存储。

10、广义表表达式中()的__最大嵌套层数_________称为广义表的深度。

三.判断题(每小题1分，共8分)

1. 一个完整算法可以没有输入，但必须有输出。T

2. 线性的数据结构可以顺序存储，也可以链接存储。而非线性的数据结构只能链接存储。F

3. 线性表的链式存储结构一定优于顺序存储结构。F

4. 非空线性表中任意一个数据元素都有且仅有一个直接前驱元素。F

5、双循环链表中，任一结点的前驱指针均为不空。T

6. 空串就是空格串。F

7. 两个串相等的充要条件是两个串的长度相等且对应位置的字符相等。T

8. 栈和队列都是数据元素存取点的线性结构。T

四、算法或程序设计题(共50分)

1. 设计一个算法，计算数列2-4+6-8+10……±m的∑值并返回，该数列存放在一个整型数组中。要求时间复杂度为O(1)。（本题10分）

status fun(a[ ],n)   //a为存放数列的数组，n是数组的长度

{

}

2、阅读下面算法，指出其功能并给出其时间复杂度。（8分）

status fun(LinkList &LA, LinkList &LB)

{

　　n=LB.Length();

　　for( i=1; i<=n; i++){

　　 　LB.Read(e, i );   　　    

  　　 if (LA.Search( e )==FALSE ) 

　　　 　　LA.Add( e );           

       }

    return;

　}

Locate操作的功能是查询在表中是否存在指定元素e，若存在返回TRUE，否则返回FALSE。Add操作的功能是将元素插入在链表尾端。其时间复杂度为O(n2)或O(n×m)

3、阅读下列算法．填空以完善该算法（8分）

功能：在带有头结点的单链表中读取指定元素e的前驱

starus ReadPrior(e, &x)

{

　pp=head;

　cp=pp->next;

　while(__cp!=NULL&&cp->data!=e______________){

   　　pp=cp;

   　　cp=cp->next;

   　  }       

if(__cp==NULL||cp->data!=e_________________ )

　　　return FAIL;　　//表中无元素e

　if(__pp==head_____________)

　　return FAIL; 　//元素无前驱

　__x=p->data______________;  //返回前驱

　return OK;

}

4. 设计算法：将一个非单调的有序单链表（带头结点）修改成单调的有序单链表，即删除表中所有值相同的多余元素。（16分）

void Purge( )

{

pp=head->next;

   while(pp!=NULL)

   {

cp=pp->next;

while(cp&&cp->data==pp->data)

        {

            t=cp;

cp=cp->next;

           delete t; 

pp->next=cp ;

        }

        pp=cp ;

   }

}