资源描述
第 1 页 ，共 4 页浙 江 理 工 大 学2016年硕士学位研究生招生入学考试试题考试科目：数据结构 代码：991（请考生在答题纸上答题，在此试题纸上答题无效）一、单选题：(每小题2分，共30分)1. 带头结点的单链表simpleList为空的判定条件是 。A.simpleList=null B.simpleList-next=nullC.simpleList-next=simpleList D.simpleList!=null2. 某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，故采用_存储方式最节省运算时间。A. 单链表 B. 仅有头结点的单循环链表C. 双链表 D. 仅有尾指针的单循环链表3. 向一个栈顶指针为 top 的链栈中删除一个结点时，用 X 保存被删结点的值，则执行_。A.X=top;top=top-next; B.X=top-data;C.top=top-next;X=top-data; D.X=top-data;top=top-next;4. 一维数组和线性表的区别是_。A. 前者长度固定，后者长度可变 B. 后者长度固定，前者长度可变C. 两者长度均固定 D. 两者长度均可变5. 稀疏矩阵一般的压缩存储方法有两种，即_。A. 二维数组和三维数组 B. 三元组和散列C. 三元组和十字链表 D. 散列和十字链表6. 不带头结点的单链表simpleList为空的判定条件是 。A.simpleList=null B.simpleList-next=nullC.simpleList-next=simpleList D.simpleList!=null7. 某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，故采用_存储方式最节省运算时间。A. 单链表 B. 仅有头结点的单循环链表C. 双链表 D. 仅有尾指针的单循环链表8. 向一个栈顶指针为top的链栈中插入一个S所指结点时，则执行_。A.top-next=S; B.S-next=top-next;top-next=S;C.S-next=top;top=S; D.S-next=top;top=top-next;第 2 页 ，共 4 页9. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的_。A. 先序遍历 B. 中序遍历C. 后序遍历 D. 按层遍历10. 设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分按行序存放在一维数组B1,n(n-1)/2中，对任一下三角部分中任一元素aij(i j ),在一组数组B的下标位置K的值是_。A.i(i-1)/2+j-1 B.i(i-1)/2+jC.i(i+1)/2+j-1 D.i(i+1)/2+j11. 如右图所示的一棵二叉排序树其不成功的平均查找长度为_。A.21/7 B.28/7 C.15/6 D.21/612.对给出的一组关键字14,5,19,20,11,19。若按关键字非递减排序，每一趟排序结果为14,5,19,20,11,19，则其采用的排序算法是_。A. 简单选择排序 B. 快速排序C. 希尔排序 D. 二路归并排序13.设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用_排序法。A. 冒泡排序 B. 快速排序C. 堆排序 D. 基数排序14. 一组记录的排序码为(46,79,56,38,40,84)，则利用堆排序(建立大根堆)的方法建立的初始堆为_。A.79,46,56,38,40,80 B.84,79,56,38,40,46C.84,79,56,46,40,38 D.84,56,79,40,46,3815.采用顺序查找法查找长度为n的线性表时，每个元素的平均查找长度为_。A.n B.n/2C.(n+1)/2 D.(n-1)/2二、填空题：(每空3分，共30分)1. 在循环双链表的P所指结点之前插入S所指结点的操作如下：S-next=P;S-prior= ;P-prior-next= ;P-prior=S;6230 7415 5648第 3 页 ，共 4 页2. 分析以下程序段的时间复杂度为_。I=s=0;While(snext;P-data=P-next-data;P-next=_;Free(Q);5. 在HQ的链队中，判定只有一个结点的条件是_。6. 在具有n个单元的循环队列(共有Maxsize个单元)中，队满时共有_个元素。7. 线性表L=（a1，a2，an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_。8. 一个有n个顶点的无向图最多有_条边。9. 在堆排序和快速排序中，若原始记录接近正序或反序，则选用_比较好。三、简答题：(每小题20分，共40分)1. 现有稀疏矩阵A如下图所示，要求画出以下各种表示法。(1) 三元组表示法；(2) 带行指针向量的单链表表示法；2. 设二叉树BTree的存储结构如下：1 2 3 4 5 6 7 8 9 10left 0 0 2 3 7 5 8 0 10 1data j h f d b a c e g iright 0 0 0 9 4 0 0 0 0 0其中，BTree为树根结点指针，left、right 分别为结点的左、右孩子指针域，在这里使用结点编号作为指针域值，0表示指针域值为空；data为结点的数据域。请完成如下问题：(1) 画出二叉树BTree的逻辑结构；(2) 写出按先序、中序和后序遍历二叉树BTree所得到的结点序列；(3) 画出二叉树BTree的后线索化树。15 0 0 22 0 15013 3 0 0 00 0 0 6 0 00 0 0 0 0 091 0 0 0 0 00 028 0 0 0 第 4 页 ，共 4 页四、编程题：(共50分)1. 如果一个线性表是由循环双链表来实现的，该链表只有表头指针而没有表尾指针。(该题15分)请编写程序实现对该线性表进行如下运算：(1) 删除第一个元素；(2) 删除最后一个元素；(3) 在第一个元素前面插入新元素；(4) 在最后一个元素的后面插入新元素。注：链表中的结点定义为如下:typedefstructnodeelemTypedata;structnode*prior;structnode*next;DNode;(2) 设计一个将输入数据建立成链表、输出链表数据、利用原空间把链表反转的程序。(该题15分)(3)设G=(V,E)以邻接表存储，如下图所示，试画出图的深度优先和广度优先生成树。(该题20分)123451 3 41 2 4 1 2 32 4 2 3 4 5 5 逆邻接表
展开阅读全文