内容发布更新时间 : 2024/5/5 8:12:42星期一 下面是文章的全部内容请认真阅读。
20XX年全国硕士研究生统一入学考试自命题试题（副卷）
********************************************************************************************
学科与专业名称：计算机技术，软件工程 考试科目代码与名称：830 数据结构 考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。 一.选择题(每题2分，共30分) 1．在数据结构中，从逻辑上可以把数据分为（ ）。 A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D. 内部结构和外部结构 2.设某无向图中有n个顶点e条边，则该无向图中所有顶点的度之和为（ ）。 A．n B.e C.2n D.2e 3. 在内部排序中,排序时不稳定的有( )。 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. 最坏情况下堆排序的时间复杂度是( )。 22A.O(log2n)B.O(log2n) C.O(nlog2n) D.O(n) 7. 设使用的邻接表表示某有向图，则顶点vj在表结点中出现的次数等于（ ）。 A.顶点vj的度B.顶点vj的出度 C.顶点vj的入度D. 无法确定 8．树最适合用来表示（ ）。 A．有序数据元素 B．无序数据元素 C．元素之间具有分支层次关系的数据D．元素之间无联系的数据 9．具有n个顶点的连通图至少应有（ ）条边。 A．n-1 B．nC．n(n-1)/2 D．2n 10. 时间复杂度不受数据初始状态影响而恒定为O(nlog2n）的是（ ）。 A．堆排序 B．冒泡排序 C．希尔排序D．快速排序 考试科目： 数据结构 共 6页，第 1 页
11．任何一颗二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序（ ）。 A．不变 B．发生改变 C．不能确定D．以上全不对 12.一组记录（50，40，95，20，15，70，60，45，80）进行冒泡排序时，第一趟需进行相邻记录的交换的次数为（ ）。 A.5B.6 C.7 D.8 13. 循环队列中是否可以插入下一个元素 （ ）。 A. 与曾经进行过多少次插入操作有关. B.只与队尾指针的值有关,与队头指针的值无关. C.只与数组大小有关,与队首指针和队尾指针的值无关 D.与队头指针和队尾指针的值有关. 14. 某二叉树的先序遍历序列为 abdgcefh, 中序遍历序列为 dgbaechf， 则它的左子树的结点数目为（ ）。 A．3B．4C．5D．6 15. 对于元素是整数( 占2个字节)的对称矩阵A,采用以行序为主的压缩存储方式( 下三角),若A[0][0]的地址是400, 则元素A[8][5]的存储地址是（ C ）。 A.440B. 480 C.482 D. 582 二．填空题(每题2分，共20分) 1．稀疏矩阵一般的压缩存储方法主要有两种，即和。 2．线性结构中元素之间存在的关系，树形结构中元素之间存在的关系。 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．若某记录序列的关键字序列是（50，40，95，20，15，70），用简单选择法进行排序，第一次收集的结果是。 考试科目： 数据结构 共6 页，第 2 页
三．判断题（每题1分，共10分，正确的选t，错误的选f） 1．采用邻接表存储的图的深度优先遍历相当于树的中序遍历。（） 2．无向图的邻接矩阵一定是对称的。（ ） 3．线性表中的每一个元素都有一个前驱和后继元素。（ ） 4．B和B+树都能有效地支持随机查找。（） 5．拓扑排序是按AOE网中每个结点事件的最早发生事件对结点进行排序。 （ ） 6．一颗满二叉树同时又是一颗平衡树。（） 7．对初始堆进行层次遍历可以得到一个有序序列。（） 8. 冒泡排序是稳定的。( ) 9. 哈夫曼树中权值最小的结点离跟最近。（ ） 10．带权无向图的最小生成树是唯一的。( ) 四. 简答题（50分） 1. 对图1.所示的有向带权图，使用Dijkstra（迪杰斯特拉）算法求出从顶点0到其余各顶点的最短路径， 要求写出过程。（10 分） 11 52 0 3213 104 6 图 1. 2. 设使用堆排序法对关键字序列 T=(10, 27, 5, 50, 60, 7, 40, 43, 75）进行排序：（10 分） （1） 画出初始大根堆对应的完全二叉树 （2） 写出大根堆序列 （3） 画出第一趟排序后新堆对应的完全二叉树 3. 简述下列算法的功能。（6分） typedef struct BiTNode{ int data; Struct BiTNode *lchild; Struct BiTNode *rchild; }BiTNode,*BiTree; intfunc(BiTree T) 考试科目： 数据结构 共6 页，第 3 页