浙 江 理 工 大 学
2014年硕士学位研究生招生入学考试试题
考试科目：数据结构 代码：991 （请考生在答题纸上答题，在此试题纸上答题无效）
一、单选题：(每小题2分，共30分)
1. 不带头结点的单链表simpleList为空的判定条件是 。 A. simpleList == null B. simpleList->next == null C. simpleList->next = simpleList D. simpleList! = null
2. 某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，故采用_______________存储方式最节省运算时间。 A. 单链表 B. 仅有头结点的单循环链表 C. 双链表 D. 仅有尾指针的单循环链表
3. 向一个栈顶指针为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; 4. 一维数组和线性表的区别是_____________。 A. 前者长度固定，后者长度可变 B. 后者长度固定，前者长度可变 C. 两者长度均固定 D. 两者长度均可变
5. 设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分按行序存放在一维数组B[1, n(n-1)/2]中，对任一下三角部分中任一元素aij(i?j),在一组数组B的下标位置K的值是______。 A. i(i-1)/2+j-1 B. i(i-1)/2+j C. i(i+1)/2+j-1 D. i(i+1)/2+j
6.在线索化二叉树中，P所指的结点没有左子树的充要条件是_______________________。 A. P->left == null B. P->ltag =1 C. P->ltag ==1 且 P->left ==null D. 以上都不对
7. 如果Tree2是由有序树Tree1转换而来的二叉树，那么Tree1中结点的后序就是Tree2中结点的____________________。 A. 先序 B.中序 C. 后序 D. 层次序 8. 判定一个有向图上是否存在回路除了可以利用拓扑排序方法外，还可以用_____________。 A. 求关键路径的方法 B. 求最短路径的Dijkstra方法 C. 广度优先遍历算法 D. 深度优先遍历算法 9.采用邻接表存储的图的深度优先遍历算法类似于二叉树的____________________。 A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历
10.采用折半查找法查找长度为n的线性表时，每个元素的平均查找长度为____________。 A. O(n2) B.O(nlog2n) C. O(n) D.O(log2n)
11. 二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历：HFIEJKG 。该二叉树根的右子树的根是：
A. E B. F C. G D. H
第 1 页 ，共 3 页
12. 已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={
14. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key MOD 13，散列地址为1的链中有（ ）个记录。 A. 1 B. 2 C. 3 D. 4
15. 对数列{25，84，21，47，15，27，68，35，20}进行排序，元素序列的变化情况如下：
第一趟25，84，21，47，15，27，68，35，20，第二趟20，15，21，25，47，27，68，35，84，第三趟15，20，21，25，35，27，47，68，84，第四趟15，20，21，25，27，35，47，68，84，则采用的排序方法是（ ）。 A. 希尔排序 B. 简单选择排序 C. 快速排序 D. 归并排序 二、填空题：(每空3分，共30分)
1. 在循环双链表的P所指结点之前插入S所指结点的操作如下： S->next = P;
S->prior = ; P->prior->next = S; P->prior = S;
2. 分析以下程序段的时间复杂度为______________________。 k=1;
While (k<=n) k = k*2;
3. 向一个长度为n的顺序表中的第i个元素(0?i?n?1)之前插入一个元素时，需向后移动_____________个元素。
4. 设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为W1，W2，...，Wn。问能否从这n件物品中选择若干件放入背包，使得放入的重量之和正好是S。设布尔函数Knap(S，n)表示背包问题的解，Wi(i=1，2，...，n)均为正整数，并已顺序存储地在数组W中。请在下列算法的下划线处填空，使其正确求解背包问题。
Knap(S，n) 若S=0
则Knap←true
否则若（S<0）或(S>0且n<1)
则Knap←false
否则若Knap (1) =true 则print(W[n])；Knap ←true
否则 Knap←Knap (2)
5. 下列程序判断字符串s 是否对称，对称则返回1，否则返回0；如 f(\返回1，f(\返回0； int f( (1) ) {
int i=0, j=0;
while (s[j]) (2) ;
for (j--; i 第 2 页 ，共 3 页 6. 一个有n个顶点的无向图最多有_________条边。 7. 在堆排序和快速排序中，若原始记录接近正序或反序，则选用_________比较好。 三、判断题：(每小题2分，共20分) 1. 算法的时间复杂度取决于问题的规模( ) 2. 从逻辑上可以把数据结构分为顺序结构、链式结构两大类( ) 3. 某算法仅含程序段1和程序段2，程序段1的执行次数为3n2，程序段2的执行次数为0.01n3， 则该算法的时间复杂度为O(n2)( ) 4. 对于顺序存储的长度为n的线性表，访问结点和增加、删除结点的时间复杂度分别为O(n)和 O(n) ( ) 5. 用链接方式存储的队列（不带头结点），在进行删除运算时仅修改头指针( ) 6. 线性表L=（a1，a2，…，an）用数组表示，假定删除表中任一元素的概率相同，则删除一个 元素平均需要移动元素的个数是(n-1)/2( ) 7. 假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素 个数为(rear-front+m)%m( ) 8. 设无向图的顶点个数为n，则该图最多有n(n-1)/2条边( ) 9. 一个n个顶点的连通无向图，其边的个数至少为n-1( ) 10. 要连通具有n个顶点的有向图，至少需要n条边( ) 四、简答题：(每小题20分，共40分) 1. 已知如右图所示的有向图，请给出该图的： （1） 每个顶点的入度、出度； （2） 邻接矩阵； （3） 邻接表； （4） 逆邻接表； （5） 强连通分量。 2. 设二叉树BTree的存储结构如下： 1 2 3 4 5 left data right 0 j 0 0 h 0 2 f 0 3 d 9 7 b 4 6 5 a 0 7 8 c 0 8 0 e 0 9 10 g 0 10 1 i 0 其中，BTree为树根结点指针，left、right 分别为结点的左、右孩子指针域，在这里使用结点编号作为指针域值，0表示指针域值为空；data为结点的数据域。请完成如下问题： (1) 画出二叉树BTree的逻辑结构； (2) 写出按先序、中序和后序遍历二叉树BTree所得到的结点序列； (3) 画出二叉树BTree的后线索化树。 五、编程题：(每小题15分，共30分) 1. 有线性表(a1, a2, …, an)，采用单链表存储，头指针为H，每个结点中存放线性表中一个元素，现查找某个元素值等于X的结点。分别写出下面三种情况的查找语句。要求时间尽量少。 (1)线性表中元素无序。(2)线性表中元素按递增有序。 (3)线性表中元素按递减有序。 2. 设计一个将输入数据建立成链表、输出链表数据、利用原空间把链表反转的程序。 第 3 页 ，共 3 页
2014年浙理工数据结构
