数据结构试卷1一、单项选择题：(每小题2分，共20分)1. 在一个长度为n的顺序表中顺序搜索一个值为x的元素时，在等概率的情况下，搜索成功时的数据平均比较次数为________。

A. nB. n/2C.(n+1)/2D.(n-1)/22. 不带头结点的单链表first为空的判定条件是_________。

A. first->next == NULL;B. first == NULL;C. first->next == first;D. first != NULL;3. 栈的插入和删除操作在__________进行。

A. 栈顶B. 栈底C. 任意位置D. 指定位置4. 假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为__________。

A. front==rearB. front!=NULLC. rear!=NULLD. front==NULL5. 设有一个广义表A ( (x, (a, b) ), (x, (a, b), y) )，运算Head (Head (Tail (A) ) ) 的执行结果为________。

A．y B．(a, b) C．(x,(a,b)) D．x6. 在一棵具有n个结点的二叉树中，所有结点的空子树个数等于_________。

A. nB. n-1C. n+1D. 2*n7. 利用n个值作为叶结点的权重，生成的霍夫曼树中共包含有_________个结点。

A. nB. n+1C. 2*nD. 2*n-18. 设无向图的顶点个数为n，则该图最多有________条边。

A. n-1B. n(n-1)/2C. n(n+1)/2D. n(n-1)9. 任何一个无向连通图的最小生成树_________。

A．只有一棵 B. 一棵或多棵C. 一定有多棵D. 可能不存在10. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为_______排序法。

A．选择B.二路归并C.交换 D.插入二、填空题（每空1分，共20分）1. 数据结构是一门研究非数值计算的程序设计问题中计算机的____________以及它们之间的___________和运算等的学科。

2. 顺序表中逻辑上相邻的元素的物理位置________相邻。

单链表中逻辑上相邻的元素的物理位置__________相邻。

3. 在单链表中，除了首元结点外，任一结点的存储位置由___________________ 指示。

4. ________ 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。

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)每个顶点的入度和出度； (2)邻接矩阵；(3)邻接表；4. 试对图2所示的AOE 网络，解答下列问题。

(1) 求每个事件的最早开始时间Ve （i ）和最迟开始时间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%13,给定键值序列为87,25,31,8,27,13,68,95,18,12,70,63, 47，处理冲突的方法为线性探测再散列，试在0~18的散列地址空间中对该关键字序列构造哈希表，并计算该表的成功查找的平均查找长度。

图2四、算法设计题（每小题10分，共30分）1.已知单链表L 中的元素有序，写一算法，删除其重复结点，即实现如图3的操作。

(a)为删除前，(b)为删除后。

2. 编写递归算法，求二叉树中以元素值为x 的结点为根的子树的深度。

3. 编写一个双向起泡的排序算法，即相邻两遍向相反方向起泡。

图3 删除重复结点(a) H(b)数据结构试卷2一、单项选择题（从下列各题四个备选答案中选出一个正确答案，每小题2分，共20分）1.算法分析的两个主要方面是（）A.空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性2．在以下的叙述种正确的是 ( )A.线性表的顺序存储结构优于链式存储结构B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是后进先出3. 循环队列用数组A[0,m-1]存放其元素值，已知其头尾指针分别是 front和 rear,则当前队列中的元素个数是（）A. ( rear-front+m)%mB. rear-front+1C. rear-front-1D. rear-front4. 带头结点的单链表head为空的判定条件是 ( )A. head==NULLB.head->next==NULLC. head->next==headD.head!=NULL5.在双循环链表的p指针所指结点之后插入s指针所指结点的操作是（）。

A.p->next=s; s->priou=p; p->next->priou=s; s->next=p->nextB.p->next=s; p->next->priou=s; s->priou=p; s->next=p->nextC.s->priou=p;s->next=p->next;p->next=s; p->next->priou=s;D.s->priou=p;s->next=p->next;p->next->priou=s; p->next=s;6.稀疏矩阵一般的压缩存储方法有两种，即（）A. 二维数组和三维数组表B. 三元组和散列C. 三元组表和十字链表D.散列和十字链表7.广义表A=（a,b,(c,d),(e,(f,g))）,则下面式子的值为（）；Head(Tail(Head(Tail(Tail(A)))))A．（g） B.(d) C.c D.d8.有分别带权为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（）A. 23B.37C.44D.469.有拓扑序列的图一定是（）。

A.有环图B.无向图C.强连通图D.有向无环图10.利用逐点插入法建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，查找元素35要进行( )元素间的比较。

A．4次 B．5次 C. 7次 D．10次二、填空（每空1分，共20分）1．长度为n的顺序表，插入和删除元素的时间复杂性为__________;顺序存储的栈和队列，插入和删除元素的时间复杂性为__________。

2.非空单循环链表L中,指针p所指结点是尾结点的条件是__________________。

3.在一个单链表中p所指结点之后插入一个由指针s所指结点，应执行s->next=________;和p->next=_____________的操作。

4．有n个结点的树，则该树中所有结点的度之和为____________。

5.设有二维数组A[0..9,0..19]，其每个元素占两个字节，第一个元素的存储地址为100，若按行优先顺序存储，则元素A[4,6]的存储地址为________ ，按列优顺序存储，元素A[4,6]的存储地址为__________ 。

6.试找出满足下面条件的所有二叉树：前序序列和中序序列相同____________________；中序序列和后序序列相同_________________。

7．二叉树以二叉链表为存储结构，在有n(n>0)个结点的二叉树中，空链域的个数为_____________。

8．假定一棵二叉树的结点数为18，则它的最小高度为_______，最大高度为__________。

9.一个连通图的生成树是一个_______连通子图，n个顶点的生成树有_______条边。

10．具有n个顶点的无向完全图，边的总数为_______条；而在n个顶点的有向完全图中，边的总数为_______条。

11.设s=’IAMASTUDENT’,t=’GOOD’,q=’WORKER’; 函数SubString(s,5,7)的值为____________;函数Index(s,t) 的值为________;函数Replace(s,’STUDENT’,q)的值为______________。

三、回答下列问题（1—4题每题5分，5题10分，共30分）1．已知一棵二叉树的前序遍历的结果是ABECDFGHIJ, 中序遍历的结果是EBCDAFHIGJ, 试画出这棵二叉树。

2．假设字符a,b,c,d,e,f的使用频度分别是0.07,0.09,0.12,0.22,0.23,0.27，构造哈夫曼3．对如图1，用prim算法构造一棵最小生成树，写出构造过程。

4．设哈希函数为H(k)=k MOD 13 ,用线性探测法解决冲突，请画出在0—12的哈希空间中，对于关键字序列32,17,10,73,45,89,92,36,80,27,19,58构造哈希表，并计算在等概率情况下的平均查找长度。