2011年10月数据结构试题及答案

全国2011年10月高等教育自学考试数据结构试题一、单项选择题（本大题共15小题，每小题2分，共30分）1、在数据的逻辑结构中，树结构和图结构都是（）A.非线性结构B.线性结构C.动态结构 D.静态结构2在一个长度为n的顺序表中插入一个元素的算法的时间复杂度为（）A.O （1）B.O（log n）C.O （n）D.O （n2）3指针pl和p2分别指向两个无头结点的非空单循环链表中的尾结点，要将两个链表链接成一个新的单循环链表，应执行的操作为（）A. pl next=p2next;p2next=p1 next;B. p2next=p1 next;p1 next=p2next;C. p=p2next; p1 next=p;p2next=p1 next;D. p=p1 next; p1 next= p2next； p2next=p;4设栈的初始状态为空，入栈序列为1, 2, 3, 4, 5, 6,若出栈序列为2, 4, 3, 6, 5, 1,则操作过程中栈中元素个数最多时为（）A.2个 B.3个 C.4个 D.6个5队列的特点是（）A. 允许在表的任何位置进行插入和删除B. 只允许在表的一端进行插入和删除C. 允许在表的两端进行插入和删除D. 只允许在表的一端进行插入，在另一端进行删除6一个链串的结点类型定义为# define NodeSize 6typedef struct nodestruct node*next;LinkStrNode;如果每个字符占1个字节，指针占2个字节，该链串的存储密度为（）A.1/3B.1/2C.2/3D.3/47广义表A= （a,B,（a,B,（a,B,）的长度为（ ）A.1B.2C.3D.无限值8已知10X12的二维数组A,按“行优先顺序”存储，每个元素占1个存储单元，已知A11 的存储地址为420，则A55的存储地址为（）A.470B.471C.472D.4739.在一棵二叉树中，度为2的结点数为15,度为1的结点数为3,则叶子结点数为（）A.12B.16C.18D.2010在带权图的最短路径问题中，路径长度是指（）A.路径上的顶点数B.路径上的边数char dataNodeSize;C.路径上的顶点数与边数之和D.路径上各边的权值之和11.具有n个顶点、e条边的无向图的邻接矩阵中，零元素的个数为（A.eB.2eC.n2-2eD.n2T12要以O （n log n）时间复杂度进行稳定的排序，可用的排序方法是（A.归并排序B.快速排序C.堆排序D.冒泡排序13.若希望在1000个无序元素中尽快求得前10个最大元素，应借用（A.堆排序B.快速排序C.冒泡排序D.归并排序14.对有序表进行二分查找成功时，元素比较的次数()A.仅与表中元素的值有关B.仅与表的长度和被查元素的位置有关C.仅与被查元素的值有关D.仅与表中元素按升序或降序排列有关15散列文件是一种()A.顺序存取的文件B.随机存取的文件C.索引存取的文件D.索引顺序存取的文件二、填空题(本大题共10小题，每小题2分，共20分)16若一个算法中的语句频度之和为T (n) =3n3-200nlog2n+50n，则该算法的渐近时间复杂度为17在单链表中，除了第1个元素结点外，任一结点的存储位置均由指示。18栈的修改是按的原则进行。19字符串中任意个连续的字符组成的子序列称为该串的。20假设一个10阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，若矩阵中的第一个元素a11在B中的存储位置k=0，则元素a55在B中的存储位置k=。21.在一棵具有n个结点的严格二叉树中，度为1的结点个数为。22对于稀疏图，采用表示法较为节省存储空间。23.在排序过程中，如果，则称其为外部排序。24设有一组记录的关键字为19，14，23，1，68，12，10, 78，25,用链地址法构造散列表,散列函数为h (key) =key%11,散列地址为1的链中有个记录。25多关键字文件的特点是除主文件和主索引外，还建有。三、解答题(本大题共4小题，每小题5分，共20分)26对于下列稀疏矩阵(注：矩阵元素的行列下标均从1开始)0000007-1008050000000006-29(1) 画出三元组表；(2) 画出三元组表的行表。(1)(2)27.已知一个森林的前序遍历序列为CBADHEGF，后序遍历序列为ABCDEFGH。(1) 画出该森林；(2) 画出该森林所对应的二叉树。(1)(2)28对关键字序列(429，653，275，897，170，908，473，256，726)进行基数排序，写出每一趟的排序结果。29对下列关键字序列(87， 25， 310， 08， 27， 132， 68， 96， 187， 133， 70， 63， 47， 135)构造散列表，假设散列函数为h (key) =key%13,用拉链法解决冲突。(1) 画出该散列表；(2) 求等概率情况下查找成功的平均查找长度ASL;(3) 写出删除值为70的关键字时所需进行的关键字比较次数。四、算法阅读题(本大题共4小题，每小题5分，共20分)30. 阅读下列算法，并回答问题：(1) 假设 L= (3, 7, 7, 11, 20, 20, 20, 51, 51),写出执行函数 f30 (&L)后的 L；(2) 简述f30的功能。void f3O(SeqList*L)L为非空的有序表int i=l,k=0;while(i length )if(Ldatai!=Ldatak)Ldata+k=Ldatai;i+;Llength=k+1 ；(1)(2)31. 阅读下列算法，并回答问题：(1) 假设栈S= (3, 8, 6, 2, 5),其中5为栈顶元素，写出执行函数f31 (&S)后的S；(2) 简述函数f31的功能。void f31(Stack *S)Queue Q； InitQueue(&Q);while(!StackEmpty(S)EnQueue(&Q,Pop(&S);while(!QueueEmpty(Q)Push(&S,DeQueue(&Q);(1)(2)32假设具有n个结点的完全二叉树顺序存储在向量BT1. n中，阅读下列算法，并回答问题:(1 ABCDEFG1234567画出执行函数f32 (BT,7,1)的返回结果；(2)简述函数f32的功能。BinTree f32(DataType BT,int n,int i)BinTree p;if (in) return NULL;p= (BinTNode*) malloc(sizeof(BinTNode); pdata=BTi;plchild=f32(BT,n,i*2);prchild=f32(BT,n,i*2+1);return p;(1)下列算法是将邻接表描述的图G1改为邻接矩阵描述的图G2，在空白处填上适当内容使算法完33.已知有向图的邻接表和邻接矩阵定义如下：整：# define MaxNum 50图的最大顶点数void f33 (ALGraph Gl,AMGraph *G2)typedef struct node inti, j;int adjvex;邻接点域EdgeNode *p;struct node *next;链指针域G2-n=G1.n; EdgeNode;边表结点结构G2- e=(1);typedef structfor (i=0; i vertexi=(2);EdgeNode *firstedge;边表头指针p=G1.adjlisti.firstedge; VertexNode;顶点表结点结构for (j=0; jadjmatrixij=0;typedef struct while (p)VertexNode adjlist MaxNum;邻接表G2-adjmatrixip-adjvex=1;int n,e;图中当前顶点数和(3)边数 ALGraph;邻接表描述的图typedef structchar vertexMaxNum;顶点表(1)int adjmatrix MaxNumMaxNum;邻接矩阵(2)int n,e;图中当前顶点数和边数五、算法设计题（本题10分） AMGraph;邻接矩阵描述的34.设顺序表L是一个递增有序表。编写算法，要求利用二分查找法确定插入位置，将元素x插图入到L中，使L保持有序。2011年10月高等教育自学考试全国统一命题考试数据结构试题答案及评分参考（课程代码02331）、单项选择题（本大题共15小题，每小题2分，共30分）1. A2. C3. D4. B5. D6. D7. C8. C9. B10. D11. C12. A13. A14. B15. B二、填空题（本大题共10小题，每小题2分，共20分）16. O (n3)18.后进先出20. 3422.邻接表24. 417.前驱结点的链指针19.子串21. 023.需要在内、外存之间交换数据25.次关键字索引三、解答题（本大题共4小题，每小题5分，共20分）26. （1）三元组表如下：02 2712 3-123 1 -833 35（3分）45 3655 4-265 59（2）行表如下：（2分）|0丨0|2W1(2) ASL= (8X1+4X2+1X3+1X4) “4=23/14 (或 1.64)28.29.（1分）（1分）27. (1)森林:（2）对应二叉树:H / E（2分（3分）（说明：如果森林画错，但森林与二叉树之间的对应关系正确仍得2分（2分） （2分）（1分）（3分）（3）3（说明：如果每次新插入的结点都是在链表头部，则结点链接顺序应该与上图 5/6所示恰好相反，散列表也为正确。此时（3）的答案为2）（3分）（2分）（3分）（2分）（3分）四、算法阅读题（本大题共4小题，每小题5分，共20分） 30. （1） （3,7,110,51）（2）删除有序表中的重复元素31. （1） S= （5,2,6,8,3）（或者画出该树的二叉链表存储结构。每错二个指针扣1分J（2）根据完全二叉树的顺序存储结构，建立该树的二叉链表存储结构（2）算法f31利用从列Q辅助将栈S中元素逆置(2分)(1分)(2分)(2分33. (1) Gl.e(2) Gl.adjlist i j.vertex(3) p = p-next五、算法设计题(本题10分)（1分）（1分）（4分）34. 参考答案1：void f34(SeqList *L, DataType x )int i, mid, low=0, high=L-length-1; while (lowdatamidlengtihi-l; i=low; i)Ldatai+ l=Ldatai;L-dataJow=x; L-length+;参考答案2：（1分）（1分（4分）void f34(SeqList*L,Dataiype x)iiit i, mid, !ow=0, high=L-ligth-l: while (lowdatamid=x)high=mid; break;if 0dataini(f|x)higli=mid-l;elselow=mid+l;（2分）（1分）（1分）for(i=L-length-1; i high; i) L-datei+1 =L-dataiJ;L-datehigh+l=;L-length-H-;