预览加载中,请您耐心等待几秒...
1/3
2/3
3/3

在线预览结束,喜欢就下载吧,查找使用更方便

如果您无法下载资料,请参考说明:

1、部分资料下载需要金币,请确保您的账户上有足够的金币

2、已购买过的文档,再次下载不重复扣费

3、资料包下载后请先用软件解压,在使用对应软件打开

HYPERLINK"http://202.43.154.166/entity/function/homeworkpaper/homeworkpaper_info.jsp?paperId=4613"\t"_blank"201209学期算法与数据结构作业1单项选择题第1题算法的时间复杂度的表示方法是:()。A、实现算法的程序在指定机器上执行的时间B、标准程序在机器上的执行时间C、基本操作重复次数,即问题规模n的某个函数D、与刻画基本操作重复次数的函数同阶无穷大的函数f(n)答案:D第2题在一个双向链表中,假设结点的域分别为left,right,以及data。其中left、right分别为两个链域,data是数据域。下一段程序是实现在h结点之后插入p结点的功能,其中h结点不空,h的下一个结点亦不空。判断哪一段程序是正确的:()。A、p->right=h->rightp->left=hh->right=pp->right->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=p答案:B第3题一个深度为L的满K叉树有如下性质:第L层上的结点都是叶子结点,其余各层上每个结点都有K棵非空子树。如果按层次顺序从1开始对全部结点编号,问各层的结点数是多少?()。A、第i层的结点数2i-1B、第i层的结点数Ki-1C、第i层的结点数是KD、第i层的结点数是1+2+3+…+K答案:B第4题最好情况下插入排序的比较次数是:()。A、O(n)B、nC、n-1D、O(n*n)答案:C第5题在树中,树的度与结点的度之间的关系是:()。A、树的度就是结点的度B、树的度为2,结点的度可以是0,1和2C、结点度中最大值为树的度D、树的度与结点的度无关答案:C判断题第6题栈满是数据对象栈的固有操作。答案:错误第7题在单向链表中,在X指向的结点后插入结点,对应的方法与X是否是头指针无关。答案:错误第8题线性表中的元素只能是简单类型。答案:错误第9题指针就是地址,有人在数组中采用指示下标值的方法实现单向链表。另外的人说这不是链表结构,他的说法对吗?答案:错误第10题在求最短路径的Dijkstra算法和Floyd算法中,Dijkstra算法只能求从一点到其他各点的最短路径,而Floyd算法可以求图中两两点之间的最短路径。答案:错误填空题第11题针对插入与删除操作,顺序文件效率不高。如果需要在顺序文件上实现插入与删除操作,解决问题基本方法是___。答案:批处理第12题数据结构针对数据对象,要研究其___,逻辑结构及其操作。答案:物理结构第13题栈的特点是___,因此栈又称为___表。答案:先进后出,先进后出第14题在数组a中存贮有线性表,数组长度为n,如果在每一个位置上插入元素的概率相同,则插入一个元素平均需要移动___个元素,因此,其时间复杂度为___。答案:n(n+1)/2,O(n)第15题在求图的最小代价生成树中,有两种算法,它们分别是___和___。答案:Prim,Kruskal问答题第16题用数组结构实现堆栈时,由于数组结构的特点,我们完全可以访问数组中的任何一个元素,为什么只是从栈顶访问元素?答案:由于数组结构的固有特点,我们完全可以访问数组中的任何一个元素,但是,用数组结构实现堆栈时,面对的是堆栈,数组只是堆栈的物理结构,椎栈限定所有的插入与删除操作只能在一端进行,如果是任意访问数组的元素,则破坏了堆栈的结构。第17题为什么要采用循环队列?答案:以连续空间实现队列时,有可能造成大量的数据移动或队列假满的现象,采用循环队列可以避免队列假满或大量移动数据的问题。第18题已知指针ha和hb的类型均为*linklisk,分别指向两个单链表的头结点,且头结点的数据域中存放链表的长度(链表中的元素均为整数)。试写一算法linklisk*connect(linklisk*ha,linklist*hb);将这两个链表连接在一起(即令其中一个表的首元结点连在另一表的最后一个结点之后),算法返回连接后链表的头结点,并要求算法尽可能短的时间完成连接运算。答案:node*mergeLink(node*ha,node*hb){intc;node*p;p=ha->data>hb->data?hb:ha;while(p->link!=NULL)