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

数据结构模拟试卷一. 单选题（每题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个元素（1jnextNULLC、head一next= = headD、head!NULL8、设单链表中指针P指向结点A，若要删除A之后的结点（若存在），则需要修改指针的操作为（A）A、pnext=pnextnextB、p=pnextC、p=pnextnextD、pnext=p9、若有一个最大长度为size，且设有队首指针front和队尾指针rear的顺序循环队列，试问判断队列满的条件应是下列哪一个语句（D）A、front=rear B、front- rear=sizeC、front+rear=size; D、front=(rear+1)%size10. 设一个栈的入栈序列为1，2，3，4，5，6，则出栈序列不可能的是（B ）。A、3，2，5，6，4，1B、1，5，4，6，2，3C、2，4，3，5，1，6D、4，5，3，6，2，111、数据结构从总体上可分为两大类，串的逻辑结构与（D）的逻辑结构不属于同一类。A线性表 B、栈 C、队列 D、树12、对一非空广义表，其表尾是指（C）A、广义表的最后一个元素B、广义表的最后一个单个元素C、广义表的最后一个子表元素D、除第一个元素外的所有其余元素13. 广义表A=( ),(a),(b,(c,d)的长度为（B）A、2B、3C、4D、514. 每种数据结构都具备的三种最基本运算是（A）A、插入、删除、遍历B、输入、输出、删除C、初始化、创建、销毁D、输入、输出、遍历二、填空题(每小题2分，共28分)1、数据结构学科讨论的是_非数值计算_问题的数学模型及其涉及的基本操作在计算机中的表示与实现。2、数据的物理结构是数据的逻辑结构在计算机存储器中的映象，它需要解决的主要问题是_数据元素之间的关系如何映象_。3、抽象数据类型（ADT）是编程语言提供的用户可自定义的一种数据类型，它主要由_数据_和_操作_两大部分组成。4. 当算法中所有语句的频度之和T（n）与求解问题的规模无关时，那么该算法的时间复杂度为_O（1）_阶。5、线性结构反映数据元素间的逻辑关系是_一对一_的，图形结构中的数据元素之间的关系是_多对多_的，而树形结构中数据元素间的关系则是_一对多_的。6以数组A60存放顺序循环队列的元素。假设当前队列有50个元素，且头指针front的值是47，则队列的尾指针rear的值应是_37_。6. 在双向循环链表中，设指针p指向待删除的结点，则删除结点p需执行的语句为_q-next = p-next;_p-next-prior = q7. 先进先出队列与优先级队列与队列的不同，主要是在于_入队_操作的处理。8. 矩阵中的非0元素与矩阵的规模之比称为稀疏因子，如果的值不大于_0.05_，则称矩阵为稀疏矩阵。9. 对于一个nn的对称矩阵可以只用一个有_n(n+1）/2_个存储单元的一维数组来存储。10、广义表表达式中()的_最大嵌套层数_称为广义表的深度。三.判断题(每小题1分，共8分)1. 一个完整算法可以没有输入，但必须有输出。T2. 线性的数据结构可以顺序存储，也可以链接存储。而非线性的数据结构只能链接存储。F3. 线性表的链式存储结构一定优于顺序存储结构。F4. 非空线性表中任意一个数据元素都有且仅有一个直接前驱元素。F5、双循环链表中，任一结点的前驱指针均为不空。T6. 空串就是空格串。F7. 两个串相等的充要条件是两个串的长度相等且对应位置的字符相等。T8. 栈和队列都是限制数据元素存取点的线性结构。T四、算法或程序设计题(共50分)1. 设计一个算法，计算数列2-4+6-8+10m的值并返回，该数列存放在一个整型数组中。要求时间复杂度为O(1)。（本题10分）status fun(a ,n) /a为存放数列的数组，n是数组的长度2、阅读下面算法，指出其功能并给出其时间复杂度。（8分）status fun(LinkList &LA, LinkList &LB)n=LB.Length();for( i=1; inext;while(_cp!=NULL&cp-data!=e_) pp=cp; cp=cp-next; if(_cp=NULL|cp-data!=e_ )return FAIL;/表中无元素eif(_pp=head_)return FAIL; /元素无前驱_x=p-data_; /返回前驱return OK;4. 设计算法：将一个非单调的有序单链表（带头结点）修改成单调的有序单链表，即删除表中所有值相同的多余元素。（16分）void Purge(