数据结构试卷1
一、单项选择题：(每小题2分，共20分)
1. 在一个长度为n的顺序表中顺序搜索一个值为x的元素时，在等概率的情况下，搜索成功时的数据平均比较次数为________。
A. n B. n/2 C.(n+1)/2 D.(n-1)/2 2. 不带头结点的单链表first为空的判定条件是_________。
A. first->next == NULL; B. first == NULL;
C. first->next == first; D. first != NULL;
D. 指定位置
3. 栈的插入和删除操作在__________进行。 A. 栈顶 B. 栈底 C. 任意位置 __________。
A. front==rear C. rear!=NULL 的执行结果为________。 A．y B．(a, b)
C．(x,(a,b))
D．x
6. 在一棵具有n个结点的二叉树中，所有结点的空子树个数等于_________。 A. n B. n-1 C. n+1 D. 2*n
7. 利用n个值作为叶结点的权重，生成的霍夫曼树中共包含有_________个结点。 A. n B. n+1 C. 2*n D. 2*n-1 8. 设无向图的顶点个数为n，则该图最多有________条边。
A. n-1 B. n(n-1)/2C. n(n+1)/2 D. n(n-1)
9. 任何一个无向连通图的最小生成树_________。
A．只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在
10. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为_______排序法。 A．选择B.二路归并C.交换 D. 插入 二、填空题（每空1分，共20分）
1. 数据结构是一门研究非数值计算的程序设计问题中计算机的____________以及它们之间的___________和运算等的学科。
2. 顺序表中逻辑上相邻的元素的物理位置________相邻。单链表中逻辑上相邻的元素的物理位置__________相邻。
3. 在单链表中，除了首元结点外，任一结点的存储位置由 ___________________ 指示。 4. ________ 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性
B. front!=NULL
D. front==NULL
4. 假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为
5. 设有一个广义表A ( (x, (a, b) ), (x, (a, b), y) )，运算Head (Head (Tail (A) ) )
表。
5. 设有二维数组A[0..19,0..10]，其每个元素占两个字节，第一个元素的存储地址为1000，若按行优先顺序存储，则元素A[4,6]的存储地址为________ ，按列优顺序存储，元素A[4,6]的存储地址为__________ 。
6. 按照二叉树的定义，有3个结点的二叉树有________种形态。 7. 具有n(n>0)个结点的完全二叉树的深度为__________。
8. 含有n个顶点e条边的无向连通图，利用Kruskal算法生成最小代价生成树其时间复杂度为__________，利用Prim算法生成最小代价生成树时间复杂度为__________。
9. 从有序表(12,18,30,43,56,78,82,95)中折半查找元素56时，其查找长度为________。 10. 快速排序在平均情况下的时间复杂度为___________，在最坏情况下的时间复杂度为____________。
三、应用题（每小题5分，共30分）
1. 输入下列整数序列，17，31，13，11，20，35，25，8，4，11，24，40，27，画出建立的二叉排序树，最后分别图示将9插入，86删除后的二叉排序树。 2. 已知二叉树T的中序遍历序列为DIGJLKBAECHF，后序遍历序列为ILKJGDBEHFCA, 请画出该二叉树，并写出先序序列。 3. 对于如图1所示的有向图，试给出 (1)每个顶点的入度和出度； (3)邻接表；
4. 试对图2所示的AOE网络，解答下列问题。
(1) 求每个事件的最早开始时间Ve（i）和
图1 3 2 4 1 5 (2)邻接矩阵； 6最迟开始时间Vl(i)。 (2) 求每个活动的最早开始时间e( )和最迟开始时间l( )。
(3) 确定哪些活动是关键活动。画出由所有关键活动构成的图，指出哪些活动加速可使整个工程提前完成。 5. 字符a,b,c,d,e,f,g的使用频度分
别是0.07,0.09,0.12,0.22,0.20,0.27,0.03，写出a,b,c,d,e,f,g的Huffman编码(在构造哈夫曼树时，要求左子树根结点的权值小于等于右子树根结点的权值)。
6. 设哈希函数H(K)=k,给定键值序列为87,25,31,8,27,13,68,95,18,12,70,63, 47，处理冲突的方法为线性探测再散列，试在0~18的散列地址空间中对该关键字序列构造哈希表，并计算该表的成功查找的平均查找长度。
图2
四、算法设计题（每小题10分，共30分）
1.已知单链表L中的元素有序，写一算法，删除其重复结点，即实现如图3的操作。(a)为删除前，(b)为删除后。 H H 10 10 10 15 15 18 ∧15 18 ∧(a) (b)
图3 删除重复结点
2. 编写递归算法，求二叉树中以元素值为x的结点为根的子树的深度。 3. 编写一个双向起泡的排序算法，即相邻两遍向相反方向起泡。