算法与数据结构习题2

《算法与数据结构习题2》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法与数据结构》习题2一、单项选择题1．算法的时间复杂度的表示方法是（）。A、实现算法的程序在指定机器上执行的时间B、标准程序在机器上的执行时间C、基本操作重复次数，即问题规模n的某个函数D、与刻画基本操作重复次数的函数同阶无穷大的函数f(n)2．在一个双向链表中，假设结点的域分别为left,right,以及data。其中left、right分别为两个链域，data是数据域。下一段程序是实现在h结点之后插入p结点的功能，其中h结点不空，h的下一个结点亦不空。判断哪一段程序是正确的（）。A、p->right=h->rightp->left=hh->right=pp->right->

2、right=pB、p->right=h->rightp->left=hh->right=pp->right->left=pC、h->right=pp->left=hp->right=h->rightp->right->left=pD、p->right=h->rightp->left=hh->right=ph->right->left=p3．在树中，树的度与结点的度之间的关系是（）。A、树的度就是结点的度B、树的度为2，结点的度可以是0，1和2C、结点度中最大值为树的度D、树的度与结点的度无关4．文件的基本组织方式有（）。A、顺序组织、索引组织、散列组织和链接方式B、磁盘组织、磁带组

3、织C、数据库组织D、关键字与非关键字5．为了区别循环队列中队满与队空的条件，采用的方法是（）。A、不需要特别的方法B、牺牲一个存贮空间C、把队头永远放到队尾的前端D、每次出队后，移动数据6．一个具有n个顶点的连通无向图的生成树中有（）条边。A、n-1B、nC、n/2D、n+17．在待排序的元素序列基本有序的前提下，效率最高的排序算法是（）。A、选择排序B、插入排序C、快速排序D、归并排序8．关键路径是事件结点网络中（）。A、最长的回路B、最短的回路C、从开始结点到完成结点的最长路径D、从开始结点到完成结点的最短路径第6页共6页9．下面说法错误的是（）。A、算法原地工作的含义是指不需

4、要任何额外的辅助空间B、在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法C、所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界D、同一个算法，实现语言的级别越高，执行效率就越高10．由3个结点可以构造出（）种不同的有向树。A、2B、3C、4D、511．如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（）方法最快。A、冒泡排序B、快速排序C、希尔排序D、堆排序12．最大容量为n的循环队列，队尾指针是rear，队头指针是front，则队空的条件是（）。A、（rear+1）MODn=frontB、rear=frontC、rea

5、r+1=frontD、（rear-1）MODn=front13．4个圆盘的Hanoi塔，总的移动次数为（）。A、7B、-8C、15D、1614．一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（）。A、CABDEFGB、ABCDEFGC、DACEFBGD、ADCFEG15．动态存储管理系统中，通常可有（）种不同的分配策略。A、1B、2C、3D、416.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用（）存储方式最节省运算时间。A．单链表B．给出表头指针的单循环链表C．双链表D．带头结点的双循环链表17.在循环双链表的p所指的结点之前插入s

6、所指结点的操作是（）。第6页共6页A．p->prior=s；s->next=p；p->prior->next=s；s->prior=p->priorB．p->prior=s；p->prior->next=s；s->next=p；s->prior=p->priorC．s->next=p；s->prior=p->prior；p->prior=s；p->prior->next=sD．s->next=p；s->prior=p->prior；p->prior->next=s；p->prior=s18.如果最常用的操作是取第i个结点及其前驱，则采用（）存储方式最节省时间。A．单链表B．双链表C

7、．顺序表D．单循环链表19.与单链表相比，双链表的优点之一是（）。A．顺序访问相邻结点更灵活B．可以进行随机访问C．可以省略表头指针或表尾指针D．插入、删除操作更简单20.单链表中，增加一个头结点的目的是为了（）。A．使单链表至少有一个结点B．标识表结点中首结点的位置C．方面运算的实现D．说明单链表是线性表的链式存储二、判断题1.在单向链表中，在X指向的结点后插入结点，对应的方法与X是否是头指针无关。（）2.在求最短路径的Dijkstra算法和Floyd算法中，Dij