《考题解答08专升本数据结构.doc》由会员分享，可在线阅读，更多相关《考题解答08专升本数据结构.doc（4页珍藏版）》请在三一文库上搜索。
1、08专升本数据结构考题解答一、 单项选择题（共12小题，每小题2 分，共24分）1用非递归方法实现递归算法时通常要使用A循环队列 B栈 C二叉树D双向队列2对于一个具有n个顶点和e条弧的赋权有向图，如果用赋权邻接矩阵表示这个图，请问求单源最短路径的Dijkstra算法的时间复杂度为AO(n) BO(n+e) CO(n*n)DO(2e)3设语句x+的执行时间时单位时间，以下语句的时间复杂度是for(i=1; i=n; i+)for(j=1; jleft; r=p-right; q-right=r; r-left=q;正确的B q=p-right; r=p-left; q-right=r; r-l
2、eft=q;把A的p和q反过来，结果错了。C q=p-left; r=p-right; q-left=r; r-right=q;错误，与B一样，只是把p和q反过来。Dq=p-left; r=p-right; q-right=r-left;什么也没有变化。7会引起循环队列队头位置发生变化的操作是A出队列 B入队列 C取队首元素D取队尾元素8如图1所示，若从顶点1出发进行广度优先搜索，则得到的访问序列是A 1,8,3,4,5,6,7,2 B. 1,2,3,7,5,6,4,8 C. 1,2,5,4,3,6,7,8 D1,2,3,4,5,6,7,89下列排序算法中，不受数据初始状态影响，时间复杂度为O
3、(n*logn)的是A堆排序 B冒泡排序 C直接选择排序D快速排序10用指针实现二叉树，在n个节点的二叉树中含有多少个空指针？An Bn-1 Cn+1D2n11用一棵二叉搜索树进行( )得到的是有序序列。A前序遍历 B中序遍历 C后序遍历D层次遍历12合并排序算法的时间复杂度是AO(n2) BO(nlogn) CO(logn)DO(n)二、 填空题（共7小题，每空2 分，共16分）13在一个长度为n的顺序表的第i（1=idatadata) if(pc!=NULL) _p-next=pa;_ p=p-next; else pc=pa; p=pc; /if _pa=pa-next_;else if
4、(pc!=NULL) _p-next=pb;_ p=p-next; else pc=pb; p=pc; /if _pb=pb-next_;/if /while p-next=(pa!=NULL)?pa:pb; /*处理一个链表为空的情况*/25二叉排序（搜索）树t以二叉表为存储结构，请编写算法实现在该树上查找值为x的节点。typedef int TreeItem;typedef struct btnode *btlink;typedef struct btnode TreeItem data; Btlink lchild, rchild; /*左右孩子指针*/BiTNode算法函数原型BiTNode Locate(BiTNode *t, TreeItem x)解答：BiTNode Locate(BiTNode *t, TreeItem x)if(t = =NULL)return NULL:if( x = = t- data ) return *t; /* 注意*，因为返回类型是BiTNode*/else if( x data ) return Locate(t-lchild, x); /*左子树*/else return Locate(t-rchild, x); /*右子树*/