1、 2013 年全国硕士研究生统一入学考试自命题试题 （副卷） * 学科与专业名称：计算机技术，软件工程 考试科目代码与名称： 830 数据结构 考生注意：所有答案必须写在答题 纸（卷）上，写在本试题上一律不给分。 一 . 选择题 (每题 2 分，共 30 分 ) 1 在数据结构中，从逻辑上可以把数据分为 （ ） 。 A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D. 内部结构和外部结构 2. 设某无向图中有 n 个顶点 e 条边，则该无向图中所有顶点的度之和为（ ）。 A n B. e C. 2n D. 2e 3. 在内 部排序中 ,排序时不稳定的有 ( )
2、。 A. 插入排序 B. 冒泡排序 C. 快速排序 D. 归并排序 4. 在循环队列中，若 front 与 rear 分别表示 队 头元素和队尾元素的位置，则判断循环队列空的条件是 ( ) 。 A front=rear+1 B rear=front+1 C front=rear D front=0 5. 设单链表中指针 p 指着结点 A,若要删除 A 之后的结点 (若存在 ),则需要修改指针的操作为( )。 A. p-next=p-next-next B. p=p-next C. p=p-next-next D. p-next=p 6. 最坏情况下堆排序的时间复杂度是 ( )。 A. O(lo
3、g2n) B. O(log2n2) C. O(nlog2n) D. O(n2) 7. 设使用的邻接表表示某有向图，则顶点 vj 在表结点中出现的次数等于（ ）。 A. 顶点 vj 的度 B. 顶点 vj 的出度 C. 顶点 vj 的入度 D. 无法确定 8 树最适合用来表示（ ） 。 A 有序数据元素 B 无序数据元素 C 元素之间具有分支层次关系的数据 D 元素之间无联系的数据 9 具有 n 个顶点的 连通 图至少应有（ ）条边。 A n-1 B n C n(n-1)/2 D 2n 10. 时间复杂度不受数据初始状态影响而恒定为 O(nlog2n） 的是 （ ） 。 A 堆排序 B 冒泡排序
4、 C 希尔排序 D 快速排序 考试科目： 数据结构 共 6 页，第 1 页 11 任何一颗二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序（ ） 。 A 不变 B 发生改变 C 不能确定 D 以上全不对 12. 一组记录（ 50， 40， 95， 20， 15， 70， 60， 45， 80）进行冒泡排序时，第一趟需进行相邻记录的交换的次数为 （ ） 。 A.5 B. 6 C. 7 D.8 13. 循环队列中是否可以插入下一个元素 （ ） 。 A. 与曾经进行过多少次插入操作有关 . B. 只与队尾指针的值有关 ,与队头指针的值无关 . C. 只与数组大小有关 ,与队首指针和队尾指针的值
5、无关 D. 与队头指针和队尾指针的值有关 . 14. 某二叉树的先序遍历序列为 abdgcefh, 中 序遍历序列为 dgbaechf， 则它的左子树的结点数目为 （ ）。 A 3 B 4 C 5 D 6 15. 对于元素是整数 ( 占 2个字节 )的对称矩阵 A,采用以行序为主的压缩存储方式 ( 下三角 ),若 A00的地址是 400, 则元素 A85的存储地址是（ C ）。 A.440 B. 480 C.482 D. 582 二填空题 (每 题 2 分，共 20 分 ) 1 稀疏矩阵一般的压缩存储方法 主要 有两种 ，即 和 。 2 线性结构中元素之间存在 的关系，树形结构中元素之间存在
6、的关系 。 3 由 n 个权值构成的哈夫曼树共有 个结点。 4 在散列表 (hash)查找中，评判一个散列函数优劣的两个主要条件是： 和 。 5 线索二叉树的左线索指向 ， 右线索指向 。 6 在一棵二叉树中，度为零的结点的个数为 n0，度为 2 的结点的个数为 n2，则该二叉树有 个叶子结点。 7 有一个 100 90 的稀疏矩阵，非 0 元素有 10，设每个整型数占 2 个字节，则用三元组表示该矩阵时，所需的字节数是 。 8 带头结点的循环单链表 L 为空的条件是 。 9 设给定权值集合 w=9,2,5,7 ，对应 huffman 树的加权路径长度 WPL 为 。 10 若某记录序列的关键
7、字序列是（ 50， 40， 95， 20， 15， 70），用 简单选择 法 进行 排序，第一次收集的结果是 。 考试科目： 数据结构 共 6 页，第 2 页 三判断题（每题 1 分，共 10 分 ， 正确的选 t，错误的选 f） 1 采用邻接表存储的图的深度优先遍历相当于树的中序遍历 。 （ ） 2 无向图的邻接矩阵一定是对称的 。（ ） 3线性表中的每一个元素都有一个前驱和后继元素。（ ） 4 B 和 B+树都能有效地支持随机查找 。（ ） 5 拓扑排序是按 AOE 网中每个结点事件的最早发生事件对结点进行排序 。 （ ） 6一颗满二叉树同时又是一颗平衡树。（ ） 7 对初始堆进行层次遍历
8、可以得到一个有序序列 。（ ） 8. 冒泡 排序是稳定的。 ( ) 9. 哈夫曼树中权值最小的结点离跟最近 。（ ） 10 带权无向图的最小生成树是唯一的。 ( ) 四 . 简答题 （ 50 分） 1. 对图 1.所示 的有向带权图，使用 Dijkstra（迪杰斯特拉）算法求出从顶点 0 到其余各顶点的最短路径， 要求写出过程。（ 10 分） 图 1. 2. 设使用堆排序法对 关键字序列 T=(10, 27, 5, 50, 60, 7, 40, 43, 75）进行排序：（ 10 分） （ 1） 画出初始大根堆对应的完全二叉树 （ 2） 写出大根堆序列 （ 3） 画出第一趟排序后新堆对应的完全二
9、叉树 3. 简述下列算法的功能。（ 6 分） typedef struct BiTNode int data; Struct BiTNode *lchild; Struct BiTNode *rchild; BiTNode,*BiTree; int func(BiTree T) 考试科目： 数据结构 共 6 页，第 3 页 4 10 100 30 50 20 60 10 3 2 0 1 if (T NULL) return(0); else if (T-data = 0) return(1 func(T-lchild)+ func(T-rchild); else return(func(T-l
10、child)+ func(T-rchild); 4. 使用 Prime 算法构造出图 1 所示的图 G 的一棵最小生成树（要求写出构造过程）。 （ 10 分） 图 1 5. 假设二叉树采用顺序存储 结构，如图 2 所示。 （ 6 分） （ 1） 画出二叉树表示 （ 2） 写出先序遍历，中序遍历，后序遍历的结果 A B C D E F G H I 图 2 6设关键字序列为（ 64, 5, 95, 53, 18, 25, 65, 27, 16），散列函数为 H(key)=key%7，采用链地址法解决冲突，请回答： （ 8 分） （ 1） 画出散列表示意图（用头插法向单链表中插入结点） （ 2） 查
11、找关键字 95 时，需要依次与哪些关键字比较 （ 3） 求等概率下查找成功的平均查找长度 五算法填空， （每空 2 分 ,共 18 分） 1. 设计一个函数功能为：在带头结点的单 链表中删除值最小的元素。请将代码补充完整。 考试科目： 数据结构 共 6 页，第 4 页 v2 v4 v1 v5 v3 v6 16 21 11 14 33 6 19 18 6 5 typedef int DataType; typedef struct Node DataType data; struct Node * next; LinkList; void deleteMin(LinkList *L) LinkL
12、ist *p=L-next,*q; q=p; while( ) if( p-data data) q=p; ; if(!q) return; p=L; while(p-next!=q) p=p-next; ; ; 2 以下 程序使用 冒泡 排序 法对 存放在 a1， a2， ， an中的序列进行排序，完成程序中的空格部分，其中 n 是元素个数，要求按升序排列。 typedef struct int key; infotype otherinfo; Node; void bsort (Node a , int n) NODE temp; int i,j,flag; for(j=1; ;j+); flag=0; for(i=1; ;i+) if(ai.keyai+1.key) flag=1; temp=ai; ; ; if( )break; 考试科目： 数据结构 共 6 页，第 5 页 .六编写算法（ 22 分 ） 1设计在顺序有序 表中实现折半查找的算法。（ 10 分） 2设计 AOV-网 拓扑排序的算法（ 12 分） 考试科目： 数据结构 共 6 页，第 6 页
