东莞理工学院城市学院（本科）试卷（B卷）
2016 -2017 学年第二学期
开课单位：计信系，考试形式：闭卷，允许带入场
科目：数据结构班级：15级软件工程1∽6班，姓名：学号：
一、填空题（每题2分，共12分）
1、数据结构在计算机中基本存储方式有结构和结构。
2、栈(又称为堆栈)是操作受限的线性结构，其操作的基本原则是，插入和删除元素的一端称为。
3、深度为k（根的深度为1）的完全二叉树至少有_______ ____个结点，至多有________ _____个结点。
4、对于一个有n个顶点的完全无向图，具有条边；而对于一个有n个顶点的完全有向图，具有条弧。
5、在进行排序时，最基本的操作是和。
6、哈希函数是一种映象，是从到的一种映象。
二、单项选择题（请将答案写在题目后的括号中。
每题2分，共40分）
1、下面结构中，不属于数据逻辑结构的是（）。
（A）线性链表（B）树形结构
（C）线性结构（D）网状结构
2、下面说法正确的是（）。
（A）数据元素是数据的最小单位
（B）数据项是数据的基本单位
（C）数据结构是带有结构的各数据项的集合
（D）上述说法都是错误的
3、有下列算法，其时间复杂度是（）。
x=1 ;
while (x<=n)
x=x*2 ;
}
（A） O(n) （B） O(n2) （C） O(㏒2n) （D） O(n㏒2n)
4、线性表若采用链式存储结构，要求内存中可用存储单元的地址是（）。
（A）必须是连续的（B）部分地址必须是连续的
（C）一定是不连续的（D）连续或不连续都可以
5、设p是非空单链表中结点q的直接前驱结点，删除q的正确操作是（）。
（A） p->next=q->next；free(p) ; （B） p->next=q->next；free(q) ;
（C） q->next=p->next；free(p) ; （D） q->next=p->next；free(q) ; 6、栈和队列的共同点时（）。
（A）都是先进先出（B）都是后进先出
（C）只允许在端点处插入和删除元素（D）没有共同点
7、设有一个栈顶指针为top的顺序栈S，top为0时表示栈空，则向堆栈S中压入一个元
素x执行的操作是（）。
（A） S[top++]=x；（B） S[++top]=x；
（C） S[--top]=x；（D） S[top--]=x；
8、设循环队列Q的最多元素个数为m，队尾指针是rear，队首指针是front，则队列为满的条件是（）。
（A） == ；（B） != ；
（C） +1)%m!=；（D） +1)%m==；
9、广义表((a),((b),c),(((d,e),(a,b)))))的长度是，深度是。
（）
（A） 4, 4 （B） 4, 5 （C） 3, 5 （D） 3, 4
10、有一个12阶下三角矩阵A，上三角的所有元素均为0， A[0][0]的地址是BA，若每个元素占3个存储单元，采用行优先压缩存储，则A[6][5]的地址是（）。
（A） BA+75 （B） BA+78
（C） BA+81 （D） BA+84
11、在二叉树中，指针P所指的结点是非叶子结点的条件是（）。
（A） P->Lchild ==NULL&& P->Rchild==NULL ；
（B） P->Lchild !=NULL&& P->Rchild !=NULL ；
（C） P->Lchild ==NULL &&P->Rchild !=NULL ；
（D） P->Lchild !=NULL ||P->Rchild !=NULL ；
12、将一棵一般的树转换为二叉树后，这棵二叉树的形态是（）。
（A）唯一的（B）有多种，但根结点都没有左子结点
（C）有多种（D）有多种，但根结点都没有右子结点
13、设由n（n≥2）个权值都互不相同的字符构成的哈夫曼树，关于该树的叙述中，错误的是（）。
（A）该树一定是一棵完全二叉树
（B）树中一定没有度为1的结点
（C）树中两个权值最小的结点一定是兄弟结点
（D）树中任一非叶子结点的权值一定不小于下一层任一结点的权值
14、以下描述中，关于无向图邻接矩阵的特性不正确的是（）。
（A）邻接矩阵是对称方阵。
（B）若顶点v i在顶点数组中的存储位置为i，则其度数是第i行的非0元素的个数。
（C）无向图的边数是上(或下)三角形矩阵中非0元素个数。
（D）图的度是矩阵中非0元素个数。
15、对于有向图，下述关于图、顶点的度、入度、出度的论述中，错误的是（）。
（A）顶点的度是顶点的入度、出度之和
（B）图的度是图的入度、出度之和
（C）顶点的入度等于顶点的出度
（D）图的入度等于图的出度
16、对于有n个顶点e(e>n)条边的带权无向图，以下关于该图的最小生成树的描述正确的是（）。
（A）最小生成树是唯一的。
（B）最小生成树中所有边上的权值之和是唯一的。
（C）最小生成树有n条边。
（D）最小生成树有n个顶点e-1条边。
17、适用于折半查找的表的存储方式以及元素排列要求是（）。
（A）顺序存储方式，元素有序（B）顺序存储方式，元素无序
（C）链接存储方式，元素无序（D）链接存储方式，元素有序
18、采用线性探测法解决冲突，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的关键字（）。
（A）不一定都是同义词（B）一定都是同义词
（C）一定都不是同义词（D）都相同
19、从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为（）。
（A）归并排序（B）冒泡排序
（C）选择排序（D）插入排序
20、若一组记录的排序码为（46，79，56，38，40，84），则采用快速排序法，以第一个记录为基准得到的依次划分结果是（）。
（A） 38，40，46，56，79，84 （B） 40，38，46，79，56，84 （C） 40，38，46，56，79， 84 （D） 40，38，46，84，56，79
三、分析题（每题8分，共40分）
1、设有一棵二叉树的顺序存储结构如下。
⑴画出该二叉树；⑵分别写出该二叉树的中序遍历序列和后序遍历序列；
2、若以{7, 9, 13, 6, 5, 3, 17, 10}作为叶子结点的权值，请构造对应的Huffman树，然后求出其带权路径长度WPL。
3、设有带权的无向图的顺序存储结构如下：⑴画出该图；⑵给出用普里姆(Prime)算法从顶点V2出发的最小生成树。
4、将关键字序列（29，33，23，43，38，27，31，25，21）依次插入到初态为空的二叉排序树中，请画出所得到的树T；然后画出删除23之后的二叉排序树T1；最后再画出在T1中插入23之后的二叉排序树T2。
5、线性表的关键字集合{31，25，18，29，42，36，73，53，17，16，47，94，43}，共有13个元素，已知散列函数为：H（key） = key MOD 11，采用链地址法处理冲突，请给出对应的散列表结构。
四、编写算法（8分）
设单链表的结点结构定义如下，试写一个函数Delete_linkList实现通过一趟遍历删除以L为头结点的单链表中值在x到y(x的大小任意y)之间的所有结点。
typedef struct Lnode
{ int data; /*数据域，保存结点的值 */
struct Lnode *next; /*指针域*/
}LNode; /*结点的类型 */
函数的原型为：void Delete_linkList(LNode *L, int x, int y)。