高等教育自学考试数据结构试题.doc

全国2011年10月高等教育自学考试数据结构试题一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1、在数据的逻辑结构中，树结构和图结构都是（ ）A.非线性结构B.线性结构C.动态结构D.静态结构2.在一个长度为n的顺序表中插入一个元素的算法的时间复杂度为（ ）A.O（1）B.（log n）C.O（n）D.O（n2）3.指针p1和p2分别指向两个无头结点的非空单循环链表中的尾结点，要将两个链表链接成一个新的单循环链表，应执行的操作为（ ）A.p1next=p2next;p2next=p1next;B. p2next=p1next;p1next=p2next;C. p=p2next; p1next=p;p2next=p1next;D. p=p1next; p1next= 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 node char dataNodeSize; struct 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.已知1012的二维数组A，按“行优先顺序”存储，每个元素占1个存储单元，已知A11的存储地址为420，则A55的存储地址为（ ）A.470B.471C.472D.4739.在一棵二叉树中，度为2的结点数为15，度为1的结点数为3，则叶子结点数为（ ）A.12B.16C.18D.2010.在带权图的最短路径问题中，路径长度是指（ ）A.路径上的顶点数B.路径上的边数C.路径上的顶点数与边数之和D.路径上各边的权值之和11.具有n个顶点、e条边的无向图的邻接矩阵中，零元素的个数为（ ）A.eB.2eC.n2-2eD.n2-112.要以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）=key11,散列地址为1的链中有_个记录。25.多关键字文件的特点是除主文件和主索引外，还建有_。三、解答题（本大题共4小题，每小题5分，共20分）26.对于下列稀疏矩阵（注：矩阵元素的行列下标均从1开始）（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）=key13,用拉链法解决冲突。（1）画出该散列表；（2）求等概率情况下查找成功的平均查找长度ASL;（3）写出删除值为70的关键字时所需进行的关键字比较次数。(1)(2)(3)四、算法阅读题（本大题共4小题，每小题5分，共20分）30.阅读下列算法，并回答问题：（1）假设L=（3，7，7，11，20，20，20，51，51），写出执行函数f30（&L）后的L；（2）简述f30的功能。 void f30(SeqList*L) L为非空的有序表 int i=1,k=0; while(iLlength） 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）若向量BT为：ABCDEFG 1 2 3 4 5 6 7画出执行函数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)(2)33.已知有向图的邻接表和邻接矩阵定义如下：define MaxNum 50图的最大顶点数typedef struct node int adjvex;邻接点域struct node *next; 链指针域 EdgeNode;边表结点结构typedef struct char vertex；顶点域 EdgeNode *firstedge;边表头指针 VertexNode;顶点表结点结构typedef struct VertexNode adjlist MaxNum; 邻接表 int n,e; 图中当前顶点数和边数 ALGraph;邻接表描述的图typedef struct char vertexMaxNum; 顶点表 int adjmatrix MaxNumMaxNum;邻接矩阵 int n,e;图中当前顶点数和边数 AMGraph;邻接矩阵描述的图下列算法是将邻接表描述的图G1改为邻接矩阵描述的图G2，在空白处填上适当内容使算法完整：void f33（ALGraph G1,AMGraph *G2） int i, j; EdgeNode *p;G2n=G1.n; G2e= (1) ;for (i=0; iG1.n; i+) G2vertexi= (2) ;p=G1.adjlisti.firstedge;for (j=0; jG1.n; j+） G2adjmatrixij=0;while (p) G2adjmatrixipadjvex=1; (3) ; (1)(2)(3)五、算法设计题（本题10分）34.设顺序表是一个递增有序表。编写算法，要求利用二分查找法确定插入位置，将元素插入到中，使保持有序。