02331数据结构全国2009年10月高等教育自学考试

200910月高等教育课程代一、单项选择题（15230分 对于三个函数f(n)=2008n3+8n2 陈述中成立的是（） p、qr依次指向某循环链表中三个相邻的结点，交换结点*q和结点*r在表中次序的程序段是（）A．p->next=r；q->next=r->next；r->next=q；B．p->next=r；r->next=q；q->next=r->next；C．r->next=q；q->next=r->next；p->next=r；D．r->next=q；p->next=r；q->next=r-a，b，c3个元素的出栈序列个数是（） 判定条件为（）A．rear= B．(front+1)％n=C．rear+1= D．(rear+1)％n=str returnp-} A［10［6］A［3［4］A［4［3］ 对广义表L=(a，())执行操作tail(L)的结果是 为7，3，5，l，2，则与F对应的二叉树的右子树中的结点个数为（ 若连通无向图G含有21条边，则G的顶点个数至少为 ）D）二、填空题（102120分） 同的栈。其中栈1为空的条件是top1=0，栈2为空的条件是top2=n-1，则“栈满”的判定条件是 L=a（，()） 在5阶B-树中，每个结点至多含4个关键字，除根结点之外，其他结点至少含 若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法 文件三、解答题(4520分n×nAi+j＜n+laij0，现将A中其它元素按行优先顺序依次到长度为n(n+1)/2的一维数组sa中，其中元素a1，n在sa［0sa［p，设元素ai，j在sa［k］中，写出由i,j和n计算k的一般电文的编码为111000010100，请根据该树进行译码，写出原来的电文。12四、算法阅读题(4520分)简述算法f30的功能。#defineMaxNum20intvisited[MaxNum]；voidDFS(Graph*g，int/*从顶点vi出发进行深度优先搜索，顶点vj时置visited[j]为1*/intf30(Graph*g){int (i=0；i<g->n；i++)／*g->ng的顶点数目 (i=k=0；i<g->n; (visited[i]==0) }return} LNode，*LinkList；阅读算法f31，并回答问题：f31(A，B)A简述算法f31 LinkList p,q; (p&& p=p- if(p->id>q->id) elsep->score=60;q=q-}}}=OneordnDeam=＂Oepos简述算法f32 strlen(char*s)；/*返回串s的长度*/ ／*若串t在串st中出现，则返回在串st中首次出现的下标值，否则返回-1*/ f32(char*s,char*t,intpos［］) i,j,k,ls,lt; (ls==0||1t==0) doj=index(s+i,t); }}while(i+1t<=1s&&j>=0); } 阅读算法f33在哪些情况下算法f33返回空指针简述算法f33BSTNode*f33(BSTreeT,KeyType{BSTNodeif(T==NULL)returnNULL;p=f33(T->1child,x);if(p!=NULL)re