(5) stack[top]=p->lchild 3 （5分，每空1分） （1）low<=high (2) (low+high)/2 (3) high=mid-1 (4) low=mid+1 (5) 1
4. （5分，每空1分） （1）minidx=i+1 (2) minval>A[j] (3) minval=A[j] (4) i!=j
(5) A[i+1]=A[minidx]
5（10分，不同答案，酌情得分） 输入顶点和弧信息，建立其邻接表 计算每个顶点的入度 对其进行拓扑排序 排序过程中求顶点的Ve[i] 将得到的拓扑序列进栈 按逆拓扑序列求顶点的Vl[i]
计算每条弧的e[i]和l[i],找出e[i]=l[i]的关键活动
第 2 学期 数据结构试卷A
一、 选择题（本大题共15小题，每题2分，共30分；答案填在下表内） 1.从一个长度为100的顺序表中删除第30个元素时需向前移动 个元素
A、70 B、71 C、69 D、30
2.在一个具有N个单元的顺序表中,假定以地址低端(即下标为1的单元)作为底,以top作为顶指针,则当做进栈处理时top变化为______。
A、 top不变 B、top=0 C、top=top-1 D、top=top+1
3.从一个具有n个结点的单链表中查找其值等于x结点时,在查找成功情况下,则平均比较____个结点。 A、n B、n/2 C、(n-1)/2 D、(n+1)/2
4.在一个单链表中,若要删除p指针所指结点的后继结点,则执行
A、p-> next; p-> next=p-> next-> next; B、p-> next=p-> next-> next; C、p=p-> next;
36
D、p=p-> next->>next;
5.在一个链队列中,假定front和rear分别为队首和队后指针,则进行插入S结点的操作时应执行___。
A、front-> next=s； front=s； B、s-> next=rear; rear=s； C、rear-> next=s; rear=s； D、s-> next=front; front=s；
6.在一棵度为3的树中度为3的结点数为3个,度为2的结点数为1个,度为1的结点数为1个,那么度为0的结点数为____个
A、6 B、7 C、 8 D、9
7.假定一棵二叉树的结点数为33个,则它的最小高度为__,最大高度为___
A、 4,33 B、5,33 C、6,33 D、6,32
8. 在一棵完全二叉树中,若编号为i的结点有右孩子,则该结点的右孩子编号为___。 A、2i B、2i+1 C、2i-1 D、i/2
9.在一个有向图中,所有顶点的入度之和等于所有弧数和___倍。 A、1 B、2 C、3 D、4
10.对于一个具有N个顶点的图,若用邻接矩阵表示,则该矩阵的大小为___。 A、 N B、(N-1) C、(N+1) D、 N
2
2
2
11.已知一个图如图所示，在该图的最小生成树中各边上数值之和为____。
A、21 B、26 C、28 D、33
12.已知一个图如图所示，由该图行到的一种拓朴序列为
37
A、v1 v4 v6 v2 v5 v3 B、v1 v2 v3 v4 v5 v6 C、v1 v4 v2 v3 v6 v5 D、v1 v2 v4 v6 v3 v5
13.二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M[2][4]的起始地址与M按列存储时元素 的起始地址相同。
A、m[2][4] B、M[4][2] C、M[3][1] D、M[3][1]
14.具有6个结点的无向图至少应有 条边才能保证是连通图。
A、 5 B、 6 C、 7 D、 8
15.采用邻接表存储的图的深度优先遍历类似于二叉树的 。
A 先序遍历B中序遍历 C. 后序遍历 D. 按层遍历 二、填空题（本大题共5小题，每空1分，共8分；答案填在下表内） 1 2 3 4 5 6 7 8 1.数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储结构表示，根据数据元素之间关系的不同特性，通常有下列四类基本结构：集合、线性结构、（1） 和 （2） 。 2.评价算法的标准很多，通常是以执行算法所需要的 （3） 和所占用的（4） 来判别一个算法的优劣。 3.线性表的顺序存储结构特点是表中逻辑关系相邻的元素在机器内的（5） 也是相邻的。 4.空格串的长度为串中所包含 （6） 字符的个数，空串的长度为 （7） 5.加上表示指向前驱和 （8）
三、判断题（对的打“√”，错的打“×”。每小题1分，共10分） （ ）1.线性表的唯一存储形式是链表。
（ ）2.已知指针P指向键表L中的某结点，执行语句P=P-〉next不会删除该链表中的结点。 （ ）3.在链队列中，即使不设置尾指针也能进行入队操作。
（ ）4.如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。
38
（ ）5.设与一棵树T所对应的二叉树为BT，则与T中的叶子结点所对应的BT中的结点也一定是叶子
结点。
（ ）6.快速排序是不稳定排序。
（ ）7.任一AOE网中至少有一条关键路径，且是从源点到汇点的路径中最短的一条。
（ ）8.若图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条（其中n为
G的顶点数）。
（ ）9.给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。 （）10.基数排序是多关键字排序。从最低位关键字起进行排序。 四、应用题。（共44分）
1.画出该图的邻接矩阵和邻接表。根据邻接表从A开始求DFS和BFS序列。（12分）
2.假设用于通信的电子由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的概率分别为{0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10}画出哈夫曼树，并为这8个字母设计哈夫曼编码。（8分）
3. 已知序列{70，73，69，23，93，18,11，68}请给出直接插入排序作升序排序每一趟的结果和快速排序作升序排序时一趟的结果。（10分）
4.设有一组关键字关键码集为 {47，7，29，11，16，92，22，8，3}，哈希表表长为11， Hash(key)=key mod 11，用线性探测法处理冲突，构造哈希表，并求它成功查找的ASL。（8分）
5. 二叉树的先序遍历序列为 A B C D E F G H I，中序遍历序列为 B C A E D G H F I，画出这棵二叉树。(6分) 五、算法设计题（8分）
定义有序表抽象数据类型，并据此类型设计折半查找算法。
2学期数据结构试卷A 参考答案及评分标准
一、 选择题本大题共15小题，每题2分，共30分 1 A 2 D 3 D 4 B 5 C 6 C 7 C 8 B 9 A 10 D 11 B 12 A 13 D 14 A 15 A 二、 填空题（本大题共5小题，每空1分，共8分） 1 2 3 4 5 6 7 8 39
树型结构 图型结构 时间 空间 位置 空格 零 后继 三、判断题（每小题1分，共10分） 1 × 四、 应用题44分） 1.（12分）
011000 101000 100001 010010 000101 001010
0 1 2 3 4 5 2 √ 3 √ 4 × 5 × 6 √ 7 × 8 × 9 × 10 × A B C D E F 1 0 0 0 1 3 2 2 3 ∧ ∧ 5 4 5 4 ∧ ∧ DFS序列:ABDEFC BFS序列:ABCDFE 2. （8分） 7 0010 19 10 2 00000 6 0001 32 01 3 00001 21 11 10 011 3. （10分） 直接插入排序
70，73，69，23，93，18,11，68 [70，73]，69，23，93，18,11，68 [70，69，73]， 23，93，18,11，68 [23,70，69，73]， 93，18,11，68 [23,70，69，73， 93]，18,11，68 [18,23,70，69，73， 93]， 11，68 [11，18,23,70，69，73， 93]， 68 [11，18,23,68,70，69，73， 93]
40