《02331数据结构4 月份历年真题附答案.doc》由会员分享,可在线阅读,更多相关《02331数据结构4 月份历年真题附答案.doc(9页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、_全国2014年4月高等教育自学考试数据结构试题课程代码:02331本试卷满分100分,考试时间150分钟. 考生答题注意事项: 1.本卷所有试题必须在答题卡上作答。答在试卷上无效。试卷空白处和背面均可作草稿纸。 2.第一部分为选择题。必须对应试卷上的题号使用28铅笔将“答题卡”的相应代码涂黑。 3.第二部分为非选择题。必须注明大、小题号,使用05毫米黑色字迹签字笔作答。 4.合理安排答题空间。超出答题区域无效。 第一部分选择题一、单项选择题(本大题共15小题,每小题2分,共30分)在每小题列出的四个备选项中只有一个是符合题目要求的,请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无
2、分。1.与数据存储结构无关的概念是A.栈B.链表C.顺序表D.二叉链表2. 顺序表中有10个数据元素,若第一个元素的存储地址是1000,则最后一个元素地址是1036,第5个元素的地址 是A1010B.1016C.1018D.10193.设栈的初始状态为空,元素1、2、3、4、5、6依次入栈,得到的出栈序列是(2,4,3,6,5,1),则栈的容量至少是A.2B.3C.4D.64.下列关于队列的叙述中,错误的是A.队列是一种先进先出的线性表B.队列是一种后进后出的线性表C.循环队列中进行出队操作时要判断队列是否为空D.在链队列中进行入队操作时要判断队列是否为满5.对稀疏矩阵进行压缩存储的目的是A.
3、便于运算B.节省存储空间C.便于输入输出D.降低时间复杂度6.一棵二叉树的第7层上最多含有的结点数为A.14B.64C.127D.1287.下列选项为完全二叉树的是8.用邻接表表示n个顶点e条边的无向图,其边表结点的总数是A. neB. eC. 2eD. n+e9.无向图中所有顶点的度数之和与所有边数之比是A.1/2B.1C.2D.410.采用邻接矩阵存储图时,广度优先搜索遍历算法的时间复杂度为A. O(n)B. O(n+e)C. O(n2)D. O(n3)11.对序列(15,9,7,8,20,-1,4)进行排序,若一趟排序后的结果为(-1,15,9,7,8,20,4),则采用的排序方法是A.
4、归并排序B.快速排序C.直接选择排序D.冒泡排序12.比较次数与待排序列初始状态无关的排序方法是A.快速排序B.冒泡排序C.直接插入排序D.直接选择排序13.查找较快,且插入和删除操作也比较方便的查找方法是A.分块查找B.二分查找C.顺序查找D.折半查找14.下列关于m阶B树的叙述中,错误的是A.根结点至多有m棵子树B.所有叶子都在同一层次上C.每个非根内部结点至少有棵子树D.结点内部的关键字可以是无序的15.在散列查找中处理冲突时,可以采用开放定址法。下列不是开放定址法的是A.线性探查法B.二次探查法C.双重散列法D.拉链法非选择题部分注意事项:用黑色字迹的签字笔或钢笔将答案写在答题纸上,不
5、能答在试题卷上。二、填空题(本大题共10小题,每小题2分,共20分)16.数据结构研究的内容包括数据的逻辑结构、_和数据的运算。17.头指针为L的带头结点的双循环链表,结点的前趋指针域为prior,后继指针域为next,判断该链表为空的条件是_。18.普里姆(Prim)算法完成的功能是求图的_。19.若三维数组a456的基地址是100,每个元素占用2个存储单元,则数组a中最后一个元素的存储地址是_。20.二叉树的线索链表利用_存放遍历时得到的前趋或后继结点的指针。21.采用邻接矩阵存储n个顶点e条边的无向图,其邻接矩阵的大小为_。22.若无向图中任意两个不同的顶点间都有路径,则称该图为_。23
6、.在直接插入排序、冒泡排序和快速排序中,平均时间性能最佳的是_。24.假设m个关键字互为同义词,若用线性探查法把这m个关键字存入散列表中,至少要进行的探查次数是_。25.顺序查找算法的平均时间复杂度为_。三、解答题(本大题共4小题,每小题5分,共20分)26.用X代表进栈操作,S代表出栈操作。给出利用栈将字符串a*b-c改变为ab*c-的操作步骤。例如:将ABC改变为BCA,则其操作步骤为XXSXSS。27.假定电文字符集为A,B,C,D,E,F,G,H,它们在电文中出现的次数分别为19,6,12,5,38,3,13,4),为这8个字符设计哈夫曼编码。画出哈夫曼树并给出编码。要求在构造哈夫曼树
7、的过程中,权值较小结点放在左侧,编码时左分支生成代码0,右分支生成代码1。28.设图以邻接表存储,如题28图所示。(1)写出从顶点v1出发图的深度优先搜索遍历序列。(2)写出从顶点v1出发图的广度优先搜索遍历序列。29.(1)一个排序方法稳定的含义是什么?(2)快速排序是稳定的吗?举例说明。四、算法阅读题(本大题共4小题,每小题5分,共20分)30.阅读下列算法,并回答问题:void f30(SeqStack S) int k=0;CirQueue Q;SeqStack T;InitQueue(&Q); /初始化队列QInitStack(&T); /初始化栈Twhile (!StackEmpt
8、y(&S) k+;if (k%2!=0) Push(&T, Pop(&S);else EnQueue(&Q, Pop(&S); /第一个循环while (!QueueEmpty(&Q) /第二个循环Push(&S, DeQueue(&Q);while(!StackEmpty(&T) /第三个循环Push(&S,Pop(&T);设栈S=(1,2,3,4,5,6,7),其中7为栈顶元素。调用函数f30(S)后,(1)第一个循环结束后,栈T和队列Q中的内容各是什么?(2)第三个循环语句结束后,栈S中的内容是什么?31.二叉树的二叉链表类型定义如下:typedef struct node DataTy
9、pe data;struct node *lchild, *rchild; BinNode;typedef BinNode *BinTree;阅读下列算法,并回答问题:void f31(BinTree BT) BinNode *s;if (BT) s=BT-lchild;BT-lchild=BT-rchild;BT-rchild=s;f31(BT-lchild);f31(BT-rchild);(1)该算法的功能是什么?(2)以下算法功能是否等价于上面的算法?void f3la(BinTree BT) BinNode *s;if(BT) f31a(BT-lchild);f31a(BT-rchil
10、d);s=BT-lchild;BT-lchild=BT-rchild;BT-rchild=s;32.单链表类型定义如下:typedef struct node int data;struct node *next; ListNode;typedef ListNode *LinkList;用不带头结点的单链表存储待排数据,链表头指针为head。下列直接选择排序算法对链表按升序进行排序,请在答题纸相应位置填写适当内容使算法完整。void f32(LinkList head) ListNode *p, *q, *r;int tmp;p=head;while(p) q=p;r=-next;while(
11、 (1) ) if( (2) ) q=r;r=r-next;tmp=q-data;q-data=p-data;p-data=tmp;p= (3) ;33.实现二分查找的递归章法如下,在答题纸相应位置填写适当的内容使算法完整。typedef structKeyType key;InfoType otherinfo;NodeType;typedef NodeType SeqListn+l;int f33(SeqList R, int low, int high, KeyType K) int mid;if(lowhigh)return 0;mid= (1) ;if(Rmid.key=K)return (2) ;if(Rmid.keyK)f33(R, mid+l, high, K);else (3) ;五、算法设计题(本题10分)34.单链表类型定义如下:typedef struct node int data;struct node *next; ListNode;typedef ListNode *LinkList;设计算法在带头结点的单链表L中删除数据值最小的结点(设链表中各结点数据值均不相同)。函数的原型为:void f34(LinkList L)_
限制150内