资源描述:
《考题解答08专升本数据结构.doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、08专升本数据结构考题解答一、单项选择题(共12小题,每小题2分,共24分)1.用非递归方法实现递归算法时通常要使用A.循环队列B.栈C.二叉树D.双向队列2.对于一个具有n个顶点和e条弧的赋权有向图,如果用赋权邻接矩阵表示这个图,请问求单源最短路径的Dijkstra算法的时间复杂度为A.O(n)B.O(n+e)C.O(n*n)D.O(2e)3.设语句x++的执行时间时单位时间,以下语句的时间复杂度是for(i=1;i<=n;i++)for(j=1;j<=n;j++)x++;A.O(1)B.O(n
2、)C.O(n*n*n)D.O(n*n)4.一高度为h的非空二叉树(假设只含根节点的树的高度为1)最多有几个节点A.2hB.2h-1C.2h-1D.2h5.赋权有向图G用用赋权邻接矩阵A存储,则节点i的入度等于A.第i行非∞的元素之和B.第i列非∞的元素之和C.第i行非∞且非0的元素个数D.第i列非∞且非0的元素个数6.设双链表的节点类型定义如下,typedefstructnode*link;typedefstructnode{ListItemelement;linkleft;linkright;}
3、*p,*q,*r;删除双链表中节点p(由p指向的节点)的操作是正确的做法如下图:A.q=p->left;r=p->right;q->right=r;r->left=q;正确的B.q=p->right;r=p->left;q->right=r;r->left=q;把A的p和q反过来,结果错了。C.q=p->left;r=p->right;q->left=r;r->right=q;错误,与B一样,只是把p和q反过来。D.q=p->left;r=p->right;q->right=r->left;什么也
4、没有变化。7.会引起循环队列队头位置发生变化的操作是A.出队列B.入队列C.取队首元素D.取队尾元素8.如图1所示,若从顶点1出发进行广度优先搜索,则得到的访问序列是A.1,8,3,4,5,6,7,2B.1,2,3,7,5,6,4,8C.1,2,5,4,3,6,7,8D.1,2,3,4,5,6,7,89.下列排序算法中,不受数据初始状态影响,时间复杂度为O(n*logn)的是A.堆排序B.冒泡排序C.直接选择排序D.快速排序10.用指针实现二叉树,在n个节点的二叉树中含有多少个空指针?A.nB.n
5、-1C.n+1D.2n11.用一棵二叉搜索树进行()得到的是有序序列。A.前序遍历B.中序遍历C.后序遍历D.层次遍历12.合并排序算法的时间复杂度是A.O(n2)B.O(nlogn)C.O(logn)D.O(n)一、填空题(共7小题,每空2分,共16分)13.在一个长度为n的顺序表的第i(1<=i<=n)个元素之前插入一个元素,需要后移___n-i+1____个元素。14.设某哈夫曼树有n个叶子节点,则该哈夫曼树的总结点数为__2n-1__。15.设有一个序列8,53,37,28,当使用直接插入
6、排序从小到大排序时,比较次数是____5____。16.设SQ为循环队列,存储在数组queue[0…m-1]中,则SQ入队操作对其队尾指针rear的修改是___(rear+1)%m___。17.设待排序的序列中存在多个记录具有相同的键值,经过排序,这些记录的相对次序仍然保持不变,则称这种排序是__稳定的____,否则称为___不稳定的___。18.在一个具有n个顶点的无向图中,要连通所有的顶点至少需要__n-1__条边。19.在有向图中,以顶点v为起点的弧的数目称为v的___出度__。二、应用题(
7、共4小题,每小题10分,共40分)20.已知关键字序列(12,77,21,65,38,7,40,53),采用直接插入排序按递增排序,给出每一趟的结果。12,77,21,65,38,7,40,5312,21,77,65,38,7,40,5312,21,65,77,38,7,40,5312,21,38,65,77,7,40,537,12,21,38,65,77,40,537,12,21,38,40,65,77,537,12,21,38,40,53,65,7721.已知散列表长度为10(散列空间0..9
8、),使用线性重新散列技术解决冲突,现有一组单词(SUN,MON,TUE,WED,THU,FRI,SAT),其对应的散列函数值分别为(3,2,6,3,2,5,6),请画出这组单词插入后的散列表。0123456789MONSUNWEDTHUTUEFRISAT22.假设一个二叉树的先序为EBADCFHGIKJ,中序序列是ABCDEFGHIJK,(1)画出二叉树;(2)写出后序序列。先序为EBADCFHGIKJ,中序序列是ABCDEFGHIJK,根是EE/ABCDFGHIJK中BADCF