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

数据结构模拟试卷 一. 单选题1分，共14分） 1．数据结构所讨论的基本数据单位是（　B　）。 A、数据对象 B、数据元素 C、数据项 D、数据类 2. 在数据结构的讨论中把数据结构从逻辑上分为（　C　）两大类。 A. 内部结构与外部结构 B. 静态结构与动态结构 C. 线性结构与非线性结构 D. 紧凑结构与非紧凑结构。 3．若一个算法的时间复杂度用T(n)表示，其中n的含义是 A．问题规模 ．条数 C．循环层数 ．函数数量. 算法分析的目的是（　C　）。 A. 研究算法的输入与输出之间的关系 B. 找出数据结构的合理性 C. 分析算法的效率以求改进算法 D. 分析算法的可读性与可移植性 5、采用线性链表表示一个向量时，要求占用的存储空间地址（D　　） A. 必须是连续的 B. 部分地址必须是连续 C. 一定是不连续的 D. 可连续可不连续 6. 在一个当前长度为n的顺序表中向第j个元素（1j=n）之前插入一个新元素时，需向后移动（　　B）个元素 A、n-j B、n-j+1 　　　C、n-j-1 　D、j 7、带头结点的单链表为空的判定条件是：?　A、==NULL?　B、hea一＝＝NULL?C、一= = head?　D、!＝NUL 8、设单链表中指针P指向结点A，若要删除A之后的结点（若存在），则需要修改指针的操作为（　A　） A、p?next=p?next?next　　　B、p=p?next C、p=p?next?next　　　　　　D、p?next=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)))的长度为二、填空题(每小题分，共分) 2、数据的物理结构是数据的逻辑结构在计算机存储器中的映象，它需要解决的主要问题是____数据元素之间的关系如何映象____________。 3、抽象数据类型（ADT）是编程语言提供的用户可自定义的一种数据类型，它主要由______数据_____和______操作_____两大部分组成。 4. 当算法中所有语句的频度之和T（n）与求解问题的规模无关时，那么该算法的时间复杂度为_O（1）__________阶。 5、线性结构反映数据元素间的逻辑关系是___一对一________的，图形结构中的数据元素之间的关系是___多对多________的，而树形结构中数据元素间的关系则是____一对多_______的。 6．以数组A[60]存放循环队列的元素假设当前队列有50个元素，队列的尾指针值q-next = p-next; ______p-next-prior = q 7. 先进先出队列与优先级队列与队列的不同，主要是在于___入队_______操作的处理。 8. 矩阵中的非0元素与矩阵的规模之比称为稀疏因子δ，如果δ的值不大于________0.05___，则称矩阵为稀疏矩阵。 9. 对于一个n×n的对称矩阵可以只用一个有____n(n+1）/2______个存储单元的一维数组来存储。 10、广义表表达式中()的__最大嵌套层数_________称为广义表的深度。 三.判断题(每小题1分，共分)一个完整算法可以没有输入，但必须有输出。线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。线性表的链式存储结构优于顺序存储结构。非空线性表中任意一个数据元素都有且仅有一个直接前驱元素。(共分)O(1)。（本题10分） status fun(a[ ],n) //a为存放数列的数组，n是数