全国高等教育自学考试数据结构试题及参考答案

全国2008年1月高等教育自学考试数据结构试题及参考答案课程代码：02331一、单项选择题（本大题共15小题，每小题2分，共30分）、多选或未选均在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。 无分。1 .逻辑上通常可以将数据结构分为（ C ）A.动态结构和静态结构B.顺序结构和链式结构C.线性结构和非线性结构D.初等结构和组合结构4.已知栈的最大容量为（C ）4。若进栈序列为1, 2, 3, 4,5,6,且进栈和出栈可以穿插进行A.5 , 4, 3, 2, 1, 6B.2, 3, 5,6,1,4C.3, 2, 5, 4, 1, 6D.1, 4, 6,5,2,35.与线性表相比，串的插入和删除操作的特点是（D)C.head!=NULLD.head next= =headA.通常以串整体作为操作对象C.算法的时间复杂度较高B.需要更多的辅助空间D.涉及移动的元素更多），则可能出现的出栈序列为2 .在下列对顺序表进行的操作中，算法时间复杂度为0（1）的是（A ）A.访问第i个元素的前驱（1i n）B.在第i个元素之后插入一个新元素 （1i n）C.删除第i个元素（1 i next= =NULL6.假设以三元组表表示稀疏矩阵，则与如图所示三元组表对应的4X5的稀疏矩阵是（注:矩阵的行列下标均从1开女台）（B)0060、70000A.0000050400 708060、00003C.70000;一5040L07800060B.-504000000-806D.70005040next)q = p - next;p next =q next;p =q - next;free(q);)(1)(2)31.算法f31的功能是借助栈结构实现整数从10进制到8进制的转换，阅读算法并回答问题:(1)画出n为十进制的1348时算法执行过程中栈的动态变化情况；(2)说明算法中while循环完成的操作。void f31(int n) /n为非负的十进制整数int e;SeqStack S;InitStack(& S);doPush(& S,n%8);n =n/8;while (n);while ( ! StackEmpty(& S)e =Pop(& S);printf ( %ld，e);(1)(2)32.已知以二叉链表作二叉树的存储结构，阅读算法f32,并回答问题:(1)设二叉树T如图所示，写出执行f32(T)的返回值;题32图(2)简述算法f32的功能。int f32(BinTree T)int m, n;if(! T)return 0;elsem= f32(T lchild);n = f 32(T rchild);if(mn)return m +1;else return n+1;(2)(33) 有向图邻接表定义如下；typedef structVertexNode adjlistMax VertexNum;int n,e;图的当前顶点数和弧数 ALGraph;邻接表类型vertexfirstedge边表结点EdegNode结构为:adjvexnext题33图其中顶点表结点VertexNode结构为：阅读下列算法f33,并回答问题：已知有向图G的邻接表如图所示，写出算法f33的输出结果；(2)简述算法f33的功能。void dfs (ALGraph *G,int v)EdgeNode * p;visitedv=TRUE;printf( %c ,G - adjlistv vertex);for(p =G - adjlistv) firstedge; p; p=p - next) if(! visitedp adjvex)dfs (G, p - adjvex);void f33(ALGraph *G)int v,w;for(v=0; v n; v +) for(w=0;wn; w+)visitedw尸FALSE;printf( %d: ,v);dfs(G,v);printf( n );(1)(2)五、算法设计题(本大题10分)34.假设以单链表表示线性表，单链表的类型定义如下：typedef struct node DataType data;struct node *next; LinkNode, *LinkList;编写算法，将一个头指针为head且不带头结点的单链表改造为一个含头结点且头指针仍为head的单向循环链表，并分析算法的时间复杂度。-本套试题共分6页，当前页是第6页-