06数据结构（50分）
一、单选题（在每小题的四个备选答案中，选出一个正确的答案，并将其号码填写在题干后面的括号内。每小题1分，共10分）
1.数据的基本单位是（ ）
A.数据项 B.数据类型 C.数据对象 D.数据元素
2.若频繁的对线性表进行插入和删除操作，则该线性表应该采用_______存储结构。（ ） A.顺序 B.链式 C.散列 D.任意
3.若进栈序列为3，5，7，9，进栈过程中可以出栈，则不可能的出栈次序是（ ） A.7，5，3，9 B.9，7，5，3 C.7，5，9，3 D.9，5，7，3 4.下面的说法中，正确的是（ ）
A.字符串的长度指串中包含的字母的个数 B.字符串的长度指串中包含的不同字符的个数 C.一个字符串不能说是其自身的一个子串 D.若T包含在S中，则T一定是S的一个子串 5.广义表（（a，b），（c，d））的表尾是（ ）
A.d B.c，d C.（c，d） D.（（c，d）） 6.n个顶点的连通图，其生成树有_______条边。（ ） A.n-1 B.n C.n+1 D.不确定
7.若一棵二叉树有8个度为2的结点，则该二叉树的叶节点个数为（ ） A.7 B.8 C.9 D.不确定
8.在有n个节点的二叉链表中有_______个空链域。（ ） A.n+1 B.n C.n-1 D.不确定
9.在等概率的情况下，采用顺序插查找法查找长度为n的线性表，平均查找长度为（ ） A.n B.n/2 C.(n+1)/2 D.(n-1)/2
10.下列排序方法中，排序的比较次数与序列的初始排列状态无关的是（ ） A.选择排序 B.插入排序 C.冒泡排序 D.快速排序
二、填空题（本大题共10小题，每小题1分，共10分）
1.假定一个顺序队列的队首和队尾分别为f和r，则判断队空的条件为__________________。 2.在顺序存储的线性表中插入或删除一个元素平均约移动表中__________________的元素。 3.设有一个二维数组A[5][4]，按行序优先存储，A[0][0]的存储地址是10，每个数组元素占2个字节，则A[3][2]的存储地址是______________。 4.深度为k的二叉树至多有______________个结点。（k≥1）
5.在有n个结点，e条边的有向图的邻接表中有_________________个表结点。 6.对一棵二叉树进行___________遍历时，得到的结点序列是一个关键字的有序序列。 7.在一个图中，所有顶点的度数之和是边数的____________倍。
8.若有序表（15，21，33，46，58，80，87）中折半查找元素33时，与关键字比较________次查找成功。
9.设哈希表长m=14，哈希函数H(key)=key MOD 11。表中已有4个元素：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 15 38 61 84 1
如果用二次探测再散列处理冲突，关键字为49的记录的存储位置是______________。 10.具有n个顶点的无向完全图，有____________________条边。
三、判断题（本大题共5小题，每小题1分，共5分）
1.算法在执行时，对同样的输入可以得到不同的结果。（ ） 2.线性表的链式存储结构的内存单元地址一定不连续。（ ） 3.队列允许插入的一段成为队尾，允许删除的一端称为队头。（ ） 4.拓扑排序是内部排序。（ ）
5.树转换成二叉树，其根结点的右子树一定为空。（ ）
四、综合应用题（本大题共3小题，每小题5分，共15分）
1.画出具有三个结点的二叉树的所有形态（不考虑数据信息的组合情况）。（5分） 2.写出下图的邻接矩阵，并写出其从V1出发的深度优先搜索遍历序列（5分）
V1 V4 V3 V2 V5
3.将下图所示的树转换成二叉树，并写出该二叉树的先序遍历序列。（5分） B F
C D A E G 五、算法设计（本大题共1小题，共10分）
1.已知线性表采用链式存储结构，结点类型定义如下，试编写一个算法，在带头结点的单链表L中，删除所有值为x的结点。 typedef struct LNode
2
{ElemType data; struct LNode *next; }LNode,*Linklist;
07数据结构（50分）
一、单项选择题（10分，每题1分）
1.按二叉树的定义，具有3个结点的二叉树有________种。（ ） A.3 B.4 C.5 D.6
2.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（ ）
A.i B.n=i C.n-i+q D.不确定 3.下面结论________是正切的。（ ）
A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B. 树的后根遍历序列与其对应的二叉树的先序遍历序列相同 C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D.以上都不对
4.评价一个算法时间性能的主要标准是（ ） A.算法易于调试 B.算法易于理解 C.算法的稳定性和正确性 D.算法的时间复杂度 5.线性表的顺序存储结构是一种__________的存储结构。（ ） A.随机存取 B.顺序存取 C.索引存取 D.散列存取
6.在顺序表中，只要知道__________，就可在相同时间内求出任一结点的存储地址。（ ） A.基地址 B.结点大小 C.向量大小 D.基地址和结点大小 7.在中序线索二叉树中，若某结点有右孩子，则该结点的直接后继是（ ） A.左子树的最右下结点 B.右子树的最右下结点 C.左子树的最左下结点 D.右子树耳朵最左下结点 8.一个栈的入栈序列是abcde，则栈的不可能输出序列是（ ） A.edcba B.decba C.dceab D.abcde 9.广义表是线性表的推广，它们之间的区别在于（ ）
A.能否使用子表 B.能否使用原子项 C.表的长度 D.是否能为空
10.若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点的个数是（ ） A.9 B.11 C.12 D.不确定
二、填空题（每空1分，共10分）
1.顺序表中逻辑上相邻的元素的物理位置_____________________。
2.在分块查找方法中，首先查找索引表，然后再用顺序查找方法查找相应的______________。
3.分配排序的两个基本过程是_______________________。
3
4.在拓扑排序中，拓扑序列的第一个顶点必定是_________________为0的顶点。 5.有n个结点的二叉链表中。其中空的指针域为__________________________。 6.有向图的邻接表表示适于求顶点的____________________。
7.有向图的邻接矩阵表示中，第i____________________上非零元素的个数为顶点vi的入度。 8.在树的_________________表示法中，求指定结点的双亲或祖先十分方便，但是求指定结点的孩子或其他后代可能要遍历整个数组。
9.由五个分别带权值为9,2,3,5,14的叶子结点构成一棵哈夫曼树，该树的带权路径长度为____________________。
10.具有n个顶点的有向图最多有________________条边。
三、填空题（30分）
1.写出头插法建立单链表的算法（5分）
2.求单源最短路径（从源点0开始），要求写出过程。（5分）
2 50 10 20 3 60 1 10 30 0 100 4 3.已知某二叉树的中序遍历序列：dfaechi 后序遍历序列：fdbehica （1） 请构造出该二叉树；（3分） （2） 写出前序遍历序列；（2分）
4.设查找的关键字序列{15,4,30,41,11,22,1}。画出对应的二叉排序树。（5分） 5.写出图的广度优先搜索算法（用邻接表存储）（5分） 6.线性表的关键字集合：
{19,14,23,01,68,20,84,27,55,11,10,79}已知散列函数为：H（k）=k，采用拉链法处理冲突，并设计出链表结构。（5分）
08数据结构（50分）
一、单项选择题（10分，每题1分）
1.若一个栈的输入序列为1，2，3，…，n，输出序列的第一个元素是i，则第i个输出元素是（）
A．i-j-1 B.i-j C.j-i+1 D.不确定的 2.循环队列存储在数组A[0..m]中，则入队的操作为（）
4
A.rear=rear+1 B.rear=(rear+1)mod(m-1) C.rear=(rear+1)mod m D.rear=(rear+1)mod(m+1)
3.二维数组A的每个元素是由6个字符组成的串，其行下表i=0，1，…，8，列下表j=1,2，…，10。若A按行序为主序存储，元素A[8][5]的起始地址与当A按列序为主序存储时的元素_________的起始地址相同。（设每个字符占一个字节）（） A.A[8][5] B.A[3][10] C.A[5][8] D.A[0][9] 4.下面说法不正确的是（）
A.广义表的表头总是一个广义表 B.广义表的表尾总是一个广义表 C.广义表难以用顺序存储结构 D.广义表可以是一个多层次的结构 5.算术表达式A+B*C-D/E转为前缀表达式后为（）
A.-A*C/DE B.-A+B*CD/E C.-+ABC/DE D.-+A*BC/DE 6.有n个叶子的哈夫曼树的结点总数为（） A.不确定 B.2n C.2n+1 D.2n-1
7. 若X是中序线索二叉树中一个有左孩子的结点，且X不为根，则X的前驱为（ ） A.X的双亲 B.X的右子树中最左的结点 C.X的左子树中最右结点 D.X的左子树中最右叶结点
8.无向图G=（V，E），其中V={a，b，c，d，e，f}，E={{a，b}，{a，e}，{a，c}，{b，e}，{c，f}，{f，d}，{e，d}}，对该图进行广度优先遍历，得到的顶点序列正确的是（ ） A.a，b，e，c，d，f B.a，c，f，e，b，d C.a，e，b，c，f，d D.a，e，d，f，c，b
9.假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行_________探测。（ ）
A.k-1次 B.k次 C.k+1次 D.k（k+1）/2次
10.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是（ ）
A.直接插入排序 B.快速排序 C.直接选择排序 D.堆排序
二、填空题（5分，每题1分）
1.在有序表A[1..12]中，采用折半查找算法查等于A[12]的元素，所比较的元素下标依次为_____________________________。
2.求图的最小生成树有两种算法，________________ 算法适合于求稀疏图的最小生成树。 3.一棵左子树为空的二叉树在先序线索化后，其中的空链域的个数为_____________。 4.在单链表L中，指针p所指结点有后继结点的条件是________________________。 5.一个深度为k，具有最少结点数的完全二叉树按层次，（同层次从左到右）用自然数依次对结点编号，则编号是i的结点所在的层次号是_______________________（跟所在的层次号规定为1层）。
三、判断题（5分，每题1分）
1.链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序存储结构中效率高。 （ ）
5