16秋北航《算法与数据结构》在线作业一

《16秋北航《算法与数据结构》在线作业一》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、北航《算法与数据结构》在线作业一一、单选题（共25道试题，共100分。）1.在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（　　）。A.q->next=p->next;p->next=q;B.p->next=q->next;q=p;C.q->next=p->next;p->next=q;D.p->next=q->next;q->next=p;正确答案：2.快速排序的记录移动次数（　）比较次数，其总执行时间为O(nlog2n)。A.大于B.大于等于C.小于等于D.小于正确

2、答案：3.下述几种排序方法中,平均查找长度最小的是（）A.插入排序B.选择排序C.快速排序D.归并排序正确答案：4.对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（）为标准操作A.条件判断B.结点移动C.算术表达式D.赋值语句正确答案：5.对于含有n个顶点e条边的无向连通图，利用Prim算法生成最小代价生成树其时间复杂度为()。A.O(log2n)B.O(n2)C.O(ne)D.O(elog2e)正确答案：6.下列关于栈的叙述正确的是（）。A.栈是非线性结构B.栈是一种树状结构C.栈具有先进先出的

3、特征D.栈具有后进先出的特征正确答案：7.堆是一个键值序列{k1,k2,…,kn},对i=1,2,…,

4、_n/2_

5、,满足()A.ki≤k2i≤k2i+1B.ki

6、正确答案：10.具有65个结点的完全二叉树其深度为（）。A.8B.7C.6D.5正确答案：11.某二叉树结点的前序序列为E、A、C、B、D、G、F，中序遍历为A、B、C、D、E、F、G。该二叉树结点的后序序列为()。A.B,D,C,A,F,G,EB.B,D,C,F,A,G,EC.E,G,F,A,C,D,BD.E,G,A,C,D,F,B正确答案：12.某程序的时间复杂度为（3n+nlog2n+n2+8）,其数量级表示为（）。A.O（n）B.O（nlog2n）C.O（n2）D.O（log2n）正确答案：13.

7、单链表的一个存储结点包含（）A.数据域或指针域B.指针域或链域C.指针域和链域D.数据域和链域正确答案：14.若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是（）。A.根结点无右子树的二叉树B.根结点无左子树的二叉树C.根结点可能有左二叉树和右二叉树D.各结点只有一个儿子的二叉树正确答案：15.对于顺序表，以下说法错误的是（）A.顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址B.顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列C.顺序表的特点是:逻辑结构中相邻的结

8、点在存储结构中仍相邻D.顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中正确答案：16.在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（）。A.HL=p;p->next=HL;B.p->next=HL;HL=p;C.p->next=HL;p=HL;D.p->next=HL->next;HL->next=p;正确答案：17.设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为（）。A.O（nloge）B.O（n+e）C.O(n*e)D.O(n

9、的平方)正确答案：18.非空的循环单链表head的尾节点（由p所指向）满足（）。A.p->next=NULLB.p=NULLC.p->next=headD.p=head正确答案：19.对于单链表表示法，以下说法错误的是（）A.数据域用于存储线性表的一个数据元素B.指针域或链域用于存放一个指向本结点所含数据元素的直接后继所在结点的指针C.所有数据通过指针的链接而组织成单链表D.NULL称为空指针，它不指向任何结点，只起标志作用正确答案：20.设有1000个无序的元素,希望用最快的速度挑选出其中前10个最大的

10、元素,最好（）排序法。A.起泡排序B.快速排序C.堆排序D.基数排序正确答案：21.下列有关图遍历的说法中不正确的是（）。A.连通图的深度优先搜索是个递增过程B.图的广度优先搜索中邻接点的寻找具有“先进先出”的特征C.非连通图不能用深度优先搜索法D.图的遍历要求每个顶点仅被访问一次正确答案：22.下列图的说法中正确的是（）。A.一个具有n个顶点的无向完全图的边数为n(n-1)B.连通图的生成树是该图的一个极大连通子图C.图的广