《高等教育自学考试数据结构试题.doc》由会员分享，可在线阅读，更多相关《高等教育自学考试数据结构试题.doc（8页珍藏版）》请在三一文库上搜索。
1、C.2/3D.3/4全国2011年10月高等教育自学考试数据结构试题一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未 选均无分。1、在数据的逻辑结构中，树结构和图结构都是（）A. 非线性结构B.线性结构C.动态结构D.静态结构2在一个长度为n的顺序表中插入一个元素的算法的时间复杂度为（）A.0 （1）B.O（ log n）C.O （ n）D.O （n2）3指针p1和p2分别指向两个无头结点的非空单循环链表中的尾结点，要将两个链表链接成一个新的单循环链表, 应执行的操作为（）A. p1 >
2、; next=p2 > next;p2 > next=p1 > next;B. p2 > next=p1 > next;p1 > next=p2 > next;C. p=p2 > next; p1 > next=p;p2 > next=p1 > next;D. p=p1 > next; p1 > next= p2 > next; p2> next=p;4设栈的初始状态为空，入栈序列为1, 2, 3, 4, 5, 6,若出栈序列为 2, 4, 3, 6, 5, 1,则操作过程中栈中兀素个数最多时为（）A.2
3、个B.3个C.4个D.6个5队列的特点是（）A. 允许在表的任何位置进行插入和删除B. 只允许在表的一端进行插入和删除C. 允许在表的两端进行插入和删除D. 只允许在表的一端进行插入，在另一端进行删除6个链串的结点类型定义为# define NodeSize 6typedef struct no dechar dataNodeSize;struct no de* next;Lin kStrNode;如果每个字符占1个字节，指针占2个字节，该链串的存储密度为（7广义表A= (a,B,(a,B,(a,B,)的长度为(A.1C.3B. 2D.无限值8已知10X 12的二维数组A，按“行优先顺序”存储
4、，每个元素占1个存储单元，已知 A11的存储地址为420,则A55的存储地址为（）A.470B.471C. 472D.4739在一棵二叉树中，度为2的结点数为15，度为1的结点数为3，则叶子结点数为（）A.12B.16D.20C.1810. 在带权图的最短路径问题中，路径长度是指（）A.路径上的顶点数B.路径上的边数C.路径上的顶点数与边数之和D.路径上各边的权值之和11. 具有n个顶点、e条边的无向图的邻接矩阵中，零元素的个数为（）A.eB.2eD.n2-12小C.n -2e12. 要以O （n log n）时间复杂度进行稳定的排序，可用的排序方法是（）A.归并排序B.快速排序C.堆排序D.
5、冒泡排序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，则该算法的
6、渐近时间复杂度为 17. 在单链表中，除了第1个元素结点外，任一结点的存储位置均由 指示。18. 栈的修改是按的原则进行。19. 字符串中任意个连续的字符组成的子序列称为该串的20. 假设一个10阶的上三角矩阵 A按行优先顺序压缩存储在一维数组B中，若矩阵中的第一个元素aii在B中的存储位置k=0，则元素a55在B中的存储位置k=。21. 在一棵具有n个结点的严格二叉树中，度为1的结点个数为 。22. 对于稀疏图，采用表示法较为节省存储空间。23. 在排序过程中，如果 ，则称其为外部排序。24. 设有一组记录的关键字为19, 14, 23, 1 , 68, 12, 10, 78, 25,用链地
7、址法构造散列表，散列函数为h ( key)=key % 11,散列地址为1的链中有个记录。25多关键字文件的特点是除主文件和主索引外，还建有 三、解答题(本大题共 4小题，每小题5分，共20分)26.对于下列稀疏矩阵(注：矩阵元素的行列下标均从1开始)-00000107-100d050000000006-29 一(1)画出三元组表；(2)画出三兀组表的行表。(1)(2)27.已知一个森林的前序遍历序列为CBADHEGF，后序遍历序列为 ABCDEFGH。(1) 画出该森林；(2 )画出该森林所对应的二叉树。(1)(2)28. 对关键字序列(429, 653, 275, 897, 170, 90
8、8, 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的关键字时所需进行的关键字比较次数。(1)(2)(3)四、算法阅读题(本大题共 4小题，每小题5分，共20分)30. 阅读下列算法，并回答问题：(1) 假设 L= (3, 7, 7, 11, 20, 20,
9、 20, 51 , 51),写出执行函数 f30 (&L )后的 L;(2) 简述f30的功能。void f30(SeqList*L)/ L为非空的有序表int i=1,k=0;while(i v L > length)if(L > datai!=L > datak)L > data+k=L > datai;i+;L > length=k+1 ;(1)31. 阅读下列算法，并回答问题：(1) 假设栈S= (3, 8, 6, 2, 5),其中5为栈顶元素，写出执行函数f31 (&S)后的S;(2) 简述函数f31的功能。void f31(Sta
10、ck *S)Queue Q; InitQueue(&Q);while(!StackEmpty(S)En Queue(&Q,Pop(&S);while(!QueueEmpty(Q)Push(&S,DeQueue(&Q);(1)(2)32假设具有n个结点的完全二叉树顺序存储在向量BT1. n中，阅读下列算法，并回答问题:(1)若向量BT为：ABCDEFG1234567画出执行函数f32 ( BT,7,1)的返回结果； 简述函数f32的功能。Bin Tree f32(DataType BT,i nt n,i nt i)Bi nTree p;if (i>
11、n) return NULL;p= ( BinTNode* ) malloc(sizeof(BinTNode);p> data=BTi;p> lchild=f32(BT,n,i*2);p> rchild=f32(BT,n,i*2+1);return p;G1改为邻接矩阵描述的图(1)33.已知有向图的邻接表和邻接矩阵定义如下:# define MaxNum 50typedef struct node int adjvex;struct node *n ext; EdgeNode;typedef structchar vertex ；EdgeNode *firstedge; V
12、ertexNode;typedef struct VertexNode adjlist MaxNum;int n ,e; ALGraph;typedef structchar vertexMaxNum;int adjmatrix MaxNumMaxNum;int n ,e; AMGraph;下列算法是将邻接表描述的图/图的最大顶点数/邻接点域/链指针域/边表结点结构/顶点域/边表头指针/顶点表结点结构/邻接表/图中当前顶点数和边数/邻接表描述的图/顶点表/邻接矩阵/图中当前顶点数和边数/邻接矩阵描述的图G2，在空白处填上适当内容使算法完整void f33 (ALGraph G1,AMGraph *G2 ) int i, j;EdgeNode *p;G2> n=G1.n;G2> e= (1);for (i=0; i v G1.n; i+) G2> vertexi= (2);p=G1.adjlisti.firstedge;for (j=0; j v G1.n; j+ ) G2 > adjmatrixij=0;while (p) G2 > adjmatrixip > adjvex=1;(3);(1)(2)(3)五、算法设计题(本题 10分)34.设顺序表L是一个递增有序表。编写算法，要求利用二分查找法确定插入位置，将元素x插入到L中，使L保 持有序。