4、__次移动；在最坏的情况下要做______n(n-1)/2___________次比较。二、选择题（共15小题，每题1分，共计15分）1．在数据结构的讨论中把数据结构从逻辑上分为（C）A内部结构与外部结构B静态结构与动态结构C线性结构与非线性结构D紧凑结构与非紧凑结构2．算法分析的两个主要方面是（A）。A．空间复杂性和时间复杂性B．正确性和简明性C．可读性和文档性D．数据复杂性和程序复杂性3．一个非空广义表的表头（ D ） A．不可能是子表 B．只能是子表 C．只能是原子 D．可以是子表
5、或原子4．在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行(B)A．s->next=p；p->next=sB．s->next=p->next；p->next=sC．s->next=p->next；p=sD．p->next=s；s->next=p5．将一个递归算法改为对应的非递归算法时，通常需要使用（A）。A．栈B．队列C．循环队列D．优先队列6．图的邻接矩阵表示法适用于表示（ C ）A．无向图B．有向图C．稠密图D．稀疏图7．深度为5的二叉树其结点数最多为C。A、16；B、30；C、31；D、32。8．设单循环链表中结点的结构为（
6、data,next）,且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪一个操作（D）《数据结构》试卷第7页共7页徐州工程学院试卷A．s=rear；rear=rear->next；deletes；B．rear=rear->next；deleterear；C．rear=rear->next->next；deleterear；D．s=rear->next->next；rear->next->next=s->next；deletes；9．线性表采用链式存储时，结点的存储地址（ B ） A．必须是不连续的B．连续与
7、否均可 C．必须是连续的D．和头结点的存储地址相连续10．根据集合{25，30，16，48}，按照依次插入结点的方法生成一棵二叉搜索树，在等概率情况下成功查找一个元素的平均查找长度为（A）A．2B．2.5C．3D．411.含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( D ) A．e B．2e C．n2－e D．n2－2e12.对线性表进行折半搜索时，要求线性表必须（C）A．以链接方式存储且结点按关键码有序排列B．以数组方式存储C．以数组方式存储且结点按关键码有序排列D．以链接方式存储
