2015年山东烟台大学数据结构考研真题.doc

发布时间：2023-11-14 发布人：admin 分类：说明书资料大小：0.08M 资料格式：doc 举报版权申诉

第1页 / 共3页

第2页 / 共3页

第3页 / 共3页

文本预览

2015 年山东烟台大学数据结构考研真题 D. 栈 D. 串 ) x=x+1; B.0(n) B. 链表 C. 哈希表 B. 二叉树 C. ) 这三个特性。 )? 稀疏矩阵 D.初等结构、构造型结构 D. 易读性、稳定性、安全性 C. 计算的环境 D.数据的类型 ) B.待处理数据的值一、选择题(本大题共 25 小题，每小题 2 分，共 50 分) 1. 算法的时间复杂度主要取决于( A. 问题的规模 2.计算机算法必须具备( A. 可执行性、可移植性、可扩充性 B.可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 3. 从逻辑上可以把数据结构分为( )两大类。 A. 动态结构、静态结构 B.顺序结构、链式结构 C. 线性结构、非线性结构 4. 以下与数据的存储结构无关的术语是( A. 循环队列 5. 以下数据结构中，哪一个是线性结构( A. 广义表 6. 在下面的程序段中，对 x 的赋值语句的频度为( for(k=1;k,,, ,,,,,},则图 G 的拓扑序列是( A.V1,V3,V4,V6,V2,V5,V7 C. V1,V3,V4,V5,V2,V6,V7 )定义一个完整的数据结构。 B. V1,V3,V2,V6,V4,V5,V7 D. V1,V2,V5,V3,V4,V6,V7 IOIOII00 B.Ie C. 数据关系 D. 抽象数据类型 G=(V,E), 其 B.广义表 C. 已知有向图 C. 0(n) ) C.III0000I D. III0000I0 D. 0(logen) D. 字符串 )。 ) 0(2n) B.数据对象 ) 是中 ) 14. 设单链表中指针 p 指向结点 A,若要删除 A 的直接后继，则所需修改指针的操作为( A.p->next=p->next->next D.p->next=p B.p=p->next C.p=p->next->next

) ) C.i(j-i)/2+1 )。 ) A. 插入排序 ) B.索引文件 B.n D.n+2 B.cedba D.4:1 C.deabc D.becab ) D.n 1 B.n C.n+1 B.直接插入排序 i*(i- 1)/2+j B.jG- 1)/2+1 1:2 B. 1:1 C.2:1 C. 冒泡排序 D.快速排序 C. 顺序文件 D.多关键字文件 15. 下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是( A.堆排序 16. 数据表 A 中每个元素距其最终位置较近，则最省时间的排序算法是( B . 堆排序 C.直接选择排序 D.快速排序 17. 适合于磁带存储的文件是( A. 散列文件 18. 一棵二叉树的中根遍历序列为 debac,后根遍历序列为 dabec,,则先根遍历序列为 ( ) A.acbed 19. 在一个有向图中，所有顶点的度数之和与图的边数的比是( A. 20. 含有 n 个结点的二叉树用二叉链表表示时，空指针域个数为( A.n- 1 21. 对 n 个不同值进行冒泡排序，在元素无序的情况下比较的次数为( A.n*(n- 1)/2 22. 对称矩阵 A[N]N],A[1][1]为首元素，将下三角(包括对角线)元素以行优先顺序存储到一维数组元素 T[1]至 T[N(N+1)/2]中，则任一下三角元素 A[i][j]存于 T[k]中，下标 k 为( A. 1)/2+1 23. 设有数组 A[i,j],数组的每个元素长度为 3 字节，i 的值为 1 到 8,j 的值为 1 到 10,数组从内存首地址 adr 开始顺序存放，当用以列为主存放时，元素 A[5,8]的存储首地址为 ( adr+180 A. B. 24. 链表不具有的特点是( ) A、插入/删除不需要移动元素 C、不必事先估计存储空间 25. 已知二叉树中叶子数为 40,仅有一个孩子的结点数为 20,则总结点数为( A 、91 二、填空题(本大题共 15 小题，每小题 2 分，共 30 分) 1. 在数据结构中，数据的存储结构有顺序存储方式（）（）（）和（）散列存储方式等四种。 2. 一个算法输入的数据中所含数据元素的数目，或与此数目有关（）称为（） 3. 稠密图 G 采用（）字储结构较省空间。稀疏图 G1 采用（）存储结构较省空间。 4. 双链表中，存储一个结点有三个域，一个是数据域，两个是指针域，指针分别指向（）和（）。 5. 在有 n 个元素的链队列中，入队和出队操作的时间复杂度分别（） 6.在循环队列中，存储空间为 0 到 n-1。设队头指针 front 指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么其队空标志为（）队满标志为（） 7. 具有 n 个结点的二叉树，采用二叉链表存储，则二叉链表中指向孩子结点的非空指针有（）个。 8. 连通图 G 有 n 个顶点，图 G 的生成树的边数为（）,具有 n 个顶点的无向图的边数最多为（） 9. 冒泡排序的平均时间复杂度为（） , 它是一种（）的排序算法。 10、排序过程中(不考虑基数排序)的两种基本操作是关键字的（）和记录的（） D、所需空间与线性长度成正比 B、可随机访问任一元素 )。 adr+141 C. adr+222 D. adr+225 ) D.j(- B 、92 C 、98 D 、99

G, int visited[v]=1; w!=0; 。 11.Pπim 算法适合于求（）图的最小生成树；Kruskal 算法适合于求（）图的最小生成树。 12,二又树中，指针口所指节点为叶子节点的条件是（）和（） 13. 具有 n 个节点的完全二叉树中，编号最大的分支节点的编号头（） 14,以下是在顺序表 L 中的第 i 个位置插入元素 x 的算法，请在（）处用适当句子予以填充。 void SeqListInsert(SeqList L,int i,ElemType x) {for(j=L.length- 1;j>=i- 1;j--) L.data[i- 1]=x; L.length++; 15. 下列算法完成的功能是 void DFS(AlGraph { for(w=GraphFirstAdj(G,v); if(!visited[w])DFS(G,w); }// 三、算法设计题(本大题共 5 小题，每小题 8 分，共 40 分) 1. 以数据集合{3,5,7,11,13}为权值构造哈夫曼树，并计算带权路径长度。 2. 一棵二叉树 BT 的存储结构为二叉链表， (1)写出 BT 的二叉链表的类型定义 (2)写出求 BT 叶子结点个数的递归算法。(要求；写出求解思路、算法模型 f、相应 C/C++ 代码)。 3. 一矩阵 A(如下图),首元素为 a[0,0]。 v) printf(v); w=GraphNextAdj(G,v,w)) //访问 v 顶点(输出 v) DFS (1)写出 A 对应的三元组线性表； (2)画出 A 对应的十字链表。 4. 已知一组关键字为{22,18,51,2,53,38,32,4,69,67,59,11}。按表中的元素顺序依次插入到一棵初始为空的二叉排序树中。画出该二叉排序树，并求在等概率的情况下查找成功的平均查找长度。 5. 设待排序的表有 10 个记录，其关键字分别为{6,8,7,9,0,1,3,2,4,5}。写出采用直接选择排序方法进行排序的全过程。四、综述题(本大题共 4 小题，共 30 分) 1. 数组是否属于线性表?请说明原因。(本小题 6 分) 2. 分别叙述使用普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法构造带权连通图生成树的基本思路(或步骤);分析二者的异同，叙述两种算法分别适用于什么特征的图。(本小题 8 分) 3,线性表的查找有哪几种常用方法?他们的查找效率如何?(本小题 8 分) 4. 请从时间复杂度和稳定性两个方面分析比较以下几种排序方法的性能：直接插入排序、冒泡排序、快速排序、堆排序和归并排序。(本小题 8 分)

分享到：

赞收藏

资料库

2015年山东烟台大学数据结构考研真题.doc

相关推荐

考研

热门标签

最新资料