浙江理工大学考研专业课试题991数据结构2016.pdf

1、第 1 页 ，共 4 页浙浙 江江 理理 工工 大大 学学2016 年硕士学位研究生招生入学考试试题年硕士学位研究生招生入学考试试题考试科目考试科目：数据结构数据结构代码代码：991（请考生在答题纸上答题请考生在答题纸上答题，在此试题纸上答题无效在此试题纸上答题无效）一一、单选题单选题：(每小题每小题 2 分分，共共 30 分分)1. 带头结点的单链表 simpleList 为空的判定条件是。A. simpleList = nullB. simpleList-next = nullC. simpleList-next = simpleListD. simpleList! = null2. 某线

2、性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，故采用_存储方式最节省运算时间。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. 两者长度均固定

3、D. 两者长度均可变5. 稀疏矩阵一般的压缩存储方法有两种，即_。A. 二维数组和三维数组B. 三元组和散列C. 三元组和十字链表D. 散列和十字链表6. 不带头结点的单链表 simpleList 为空的判定条件是。A. simpleList = nullB. simpleList-next = nullC. simpleList-next = simpleListD. simpleList! = null7. 某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，故采用_存储方式最节省运算时间。A. 单链表B. 仅有头结点的单循环链表C. 双链表D. 仅有尾指针的单循环链表8

4、. 向一个栈顶指针为 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(ij),在一组数组

5、B 的下标位置 K 的值是_。A. i(i-1)/2+j-1B. i(i-1)/2+jC. i(i+1)/2+j-1D. i(i+1)/2+j11. 如 右图 所示 的一 棵二 叉排 序树 其不 成功 的平 均查 找长 度为_。A. 21/7B. 28/7C. 15/6D. 21/612.对给出的一组关键字14,5,19,20,11,19。若按关键字非递减排序，每一趟排序结果为14,5,19,20,11,19，则其采用的排序算法是_。A. 简单选择排序B. 快速排序C. 希尔排序D. 二路归并排序13.设有 1000 个无序的元素，希望用最快的速度挑选出其中前 10 个最大的元素，最好选用_排

6、序法。A. 冒泡排序B. 快速排序C. 堆排序D. 基数排序14. 一组记录的排序码为(46,79,56,38,40,84)，则利用堆排序(建立大根堆)的方法建立的初始堆为_。A. 79, 46, 56,38,40,80B. 84, 79, 56,38,40,46C. 84, 79, 56,46,40,38D. 84, 56, 79,40,46,3815.采用顺序查找法查找长度为 n 的线性表时，每个元素的平均查找长度为_。A. nB. n/2C. (n+1)/2D. (n-1)/2二二、填空题填空题：(每空每空 3 分分，共共 30 分分)1. 在循环双链表的 P 所指结点之前插入 S 所指

7、结点的操作如下：S-next = P;S-prior =;P-prior-next =;P-prior = S;623074155648第 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. 一个有

8、 n 个顶点的无向图最多有_条边。9. 在堆排序和快速排序中，若原始记录接近正序或反序，则选用_比较好。三三、简答题简答题：(每小题每小题 20 分分，共共 40 分分)1. 现有稀疏矩阵 A 如下图所示，要求画出以下各种表示法。(1) 三元组表示法；(2) 带行指针向量的单链表表示法；2. 设二叉树 BTree 的存储结构如下：12345678910left00237580101datajhfdbacegiright0009400000其中，BTree 为树根结点指针，left、right 分别为结点的左、右孩子指针域，在这里使用结点编号作为指针域值，0 表示指针域值为空；data 为结点的

9、数据域。请完成如下问题：(1) 画出二叉树 BTree 的逻辑结构；(2) 写出按先序、中序和后序遍历二叉树 BTree 所得到的结点序列；(3) 画出二叉树 BTree 的后线索化树。15 0 0 22 015013 30 000 0 06 000 0 00 0091 0 00 000 0 280 00第 4 页 ，共 4 页四四、编程题编程题：(共共 50 分分)1. 如果一个线性表是由循环双链表来实现的，该链表只有表头指针而没有表尾指针。(该题该题 15分分)请编写程序实现对该线性表进行如下运算：(1)删除第一个元素；(2)删除最后一个元素；(3)在第一个元素前面插入新元素；(4)在最后一个元素的后面插入新元素。注：链表中的结点定义为如下:typedef struct nodeelemType data;struct node *prior;struct node *next; DNode;(2) 设计一个将输入数据建立成链表、输出链表数据、利用原空间把链表反转的程序。(该题该题 15分分)(3)设 G=(V,E)以邻接表存储，如下图所示，试画出图的深度优先和广度优先生成树。(该题该题 20 分分)123451341241232423455逆邻接表