本科随堂测的验(带答案).doc

第1次测验 算法的时间复杂度取决于（ ） A．问题的规模 B. 待处理数据的初态 C. A和B 从逻辑上可以把数据结构分为（ ）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 数据的逻辑结构：指反映数据元素之间的逻辑关系的数据结构,其中的逻辑关系是指数据元素之间的前后件关系,而与他们在计算机中的存储位置无关.逻辑结构包括：1.集合；2.线性结构；3.树形结构；4.图形结构.《数据结构》数据结构课程中数据的逻辑结构分为线性结构和非线性结构.对于数据结构课程而言,简单地说,线性结构是n个数据元素的有序（次序）集合.它有四个基本特征：1．集合中必存在唯一的一个第一个元素；2．集合中必存在唯一的一个最后的元素；3．除最后元素之外,其它数据元素均有唯一的后继；4．除第一元素之外,其它数据元素均有唯一的前驱.数据结构中线性结构指的是数据元素之间存在着“一对一”的线性关系的数据结构.如（a1,a2,a3,.,an）,a1为第一个元素,an为最后一个元素,此集合即为一个线性结构的集合.相对应于线性结构,非线性结构的逻辑特征是一个结点元素可能对应多个直接前驱和多个后驱.常用的线性结构有：线性表,栈,队列,双队列,数组,串.关于广义表,是一种非线性的数据结构.常见的非线性结构有：树(二叉树等),图(网等). 以下属于逻辑结构的是（ ）。 A．顺序表 B. 哈希表 C. 有序表 有序表是排好序的线性表 D. 单链表 下述哪一条是顺序存储结构的优点？（ ） A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示 链式存储结构:(1)占用额外的空间以存储指针(浪费空间)(2)存取某个元素速度慢(3)插入元素和删除元素速度快(4)没有空间限制,存储元素的个数无上限,基本只与内存空间大小有关.顺序存储结构:(1)空间利用率高(2)存取某个元素速度快(3)插入元素和删除元素存在元素移动,速度慢,耗时(4)有空间限制,当需要存取的元素个数可能多于顺序表的元素个数时,会出现溢出问题.当元素个数远少于预先分配的空间时,空间浪费巨大.在存取元素频繁,但删除或插入操作较少的情况宜用顺序表.堆排序,二分查找适宜用顺序表. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。 A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。 A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表因为有尾指针，所以时间时间复杂度为O(1),其他的都要O(n) 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ ）存储方式最节省运算时间。 A．单链表 B．双链表 C．单循环链表 D．带头结点的双循环链表双循环链表能够通过头结点的前驱就是尾结点，能够迅速找到尾结点，然后进行插入和删除操作 链表不具有的特点是（ ） A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 对于顺序表，访问第i位置结点和增加、删除结点的时间复杂度为（ ）。 A. O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 线性表以链接方式存储时，访问第i位置元素的时间复杂性为（ ） A．O(i) B．O(1) C．O(n) D．O(i-1) 下面程序段的时间复杂度是　O(n) 　。4 int i=1,k=100; while(in) { k=k+1; i+=2; } 在单链表L中，指针p所指结点有后继结点的条件是：p-next!=NULL。 长度为n的顺序表，在其第i个元素（1≤i≤n+1）之前插入一个元素时，需向后移动 n-i+1 个元素，删除第i个元素（1≤i≤n）时，需向前移动__n-i 个元素。 请写出顺序表的类型定义。 请写出单链表的类型定义。 第2次测验 一、选择题 对于栈操