南阳理工学院软件学院数据结构.doc

一、选择题：（每题 2 分，共 30 分）
1. 设某数据结构的二元组形式表示为DS=(D，R)，D={a,b,c,d,e，f}，R={<a,b>，<a，c>，<b,c>，<b，e>，<e,f>，<f,a>}，则数据结构DS是（ D ）。
A.集合 B.线性结构 C.树形结构 D.图形结构
2. 在计算机中通常作为一个整体进行考虑和处理的数据的基本单位是（A ）。
A.数据元素 B.数据对象 C.数据项 D.数据类型
3. 若在长度为n的顺序表第i个元素之前插入一个元素，则需要向后移动的元素个数是（ B ）。
A.i B.n-i+1 C.i-1 D.n-i
4. 头指针为L的带头结点的循环双链表,结点的前趋指针域为prior，后继指针域为next，判断该链表为空的条件是（ B ）。
A.L->prior==NULL||L->next==NULL B.L->prior==NULL&&L->next==NULL
C.L->prior==L&&L->next==L D.L->prior==L->next
5. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1~8，j的值为1~10，数组从内存首地址BA开始顺序存放，当以列为主存储时，元素A[5][8]的存储首地址为（ ）。
A.BA+41 B.BA+180 C.BA+222 D.BA+225
6. 设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，则下列属于该有向图G的一种拓扑排序序列的是（ ）。
A.1，2，3，4 B.2，3，4，1
C.1，4，2，3 D.1，2，4，3
7. 广义表A=(x，((y，z)，a，b))，则表尾是（ D ）
A.b B.（b） C.((y，z)，a，b) D.(((y，z)，a，b)）
8. 一棵二叉树的先序遍历序列为：ABDGCEHF，中序遍历序列为：DGBAEHCF，其后序遍历序列为（A ）。
A.GDBHEFCA B.GDBCEFHA
C.GDBACEFH D.GDBHECFA
9. 假设以I和O分别表示入栈和出栈操作，若栈的初态和终态均为空，则下面所示的操作序列中（ ）是合法的。
A.OIOIIOIO B.IOOIOIIO C.IIIOIOIO D.IIIOOIOO
10. 无向图的邻接矩阵中1的个数与所有边数之比是（ ）。
A.1:2 B.1:1 C.2:1 D.4:1
11. 分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（ ）。
A.(100,80,90,60,120,110,130) B.(100,120,110,130,80,60,90)
C.(100,60,80,90,120,110,130) D.(100,80,60,90,120,130,110)
12. 折半查找有序表（8，10，14，16，24，34，54，74，92，104）。若查找表中元素62，则它将依次与表中（ ）比较大小，且查找结果是失败的。
A.24,74,34,54 B.34,92,74,54 C.24,54 D.34,92,50
13. 下列排序算法中，（ ）不能保证每趟排序至少能将一个元素放到其最终的位置上。
A.希尔排序 B.快速排序 C.冒泡排序 D.简单选择排序
14. 对n个元素的线性表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（ ）。
A.(n-1)/2 B.n/2 C.(n+1)/2 D.n
15. 把一棵树转换为二叉树后，这棵二叉树的形态是（ D ）。
A.有多种 B.有多种，但根结点都没有右孩子
C.有多种，但根结点都没有左孩子 D.唯一的

二、填空题：（每空2分，共 10分）
1. 在头指针为head的循环链表中，判断指针变量P指向尾结点的条件是_______________________。
2. 在一个具有n个结点的线索二叉树中有___________个指针是用来作为线索处理的。
3. 假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为_____9_____个，树的深度为_____3______。
4. 一个有n个顶点的有向完全图中弧的数目为____________条。

三、判断题：（每题2分，共10分）
1. 堆是完全二叉树，完全二叉树不一定是堆。 （ ）
2. 在静态查找中，折半查找的元素必须是有序的，其存储结构可以采用顺序存储或者链式存储。 （ ）
3. 用带有头结点的链式方式存储的队列，在进行插入运算时仅修改尾指针。 （ ）
4. 已知一棵完全二叉树的结点个数为1001中，叶子结点的个数为500。 （ ）
5. 串是一种特殊的线性表，其特殊性体现在数据元素可以是多个字符。 （ ）

四、应用题：(每题6分，共 30分）
1. 单链表L的结点结构为(data，next)，要求：
（1）写出判断该链表是否为空的条件；
（2）若该链表当前的状态如下图所示，则写出在r结点之后插入一个已存在的结点p的过程。

2. 设散列表的长度为11，散列函数H(k)=k mod 8，初始记录关键字序列为(25，12，31，8，27，39，13，68，)，若发生冲突采用线性探查法处理，要求：
（1）计算出每一个元素的散列地址并在下图中填写出散列表：
0
1
2
3
4
5
6
7
8
9
10

（2）求出在查找每一个元素概率相等情况下成功的平均查找长度。

3. 己知无向网G=(V，E)，其中V=(A，B，C，D，E)，该网如下图所示，要求：
（1）写出该网对应的邻接矩阵arcs；
（2）画出无向网G的最小生成树。

4. 给出对序列{12,2,16,30,28,10,16*,20,6,18}进行二路归并排序时每一趟的结果，并判断其稳定性如何。

5. 画出以权值分别为8，6，3，4，5的五个叶子结点构成的哈夫曼树，并求其带权路径长度WPL。

五、算法设计题：（每题10分，共20分）
1. Please write the improved bubble sort algorithm.（10分）

2. 采用顺序存储表示方法，实现循环队列中的出队和入队算法，试写出：
（1） 顺序队列的结构定义；（2分）
（2） 循环队列的入队操作；（4分）
（3） 循环队列的出队操作。（4分）

参考答案：

一、选择题（每题2分）
1—5 DABCB 6-10 ADADC 11-15 CAACD
二、填空题（每空2分）
1. p->next==head 2. n+1 3. 9 3 4. n(n-1)
三、判断题（每题2分）
1.√ 2.╳ 3.√ 4. ╳ 5.╳
四、应用题
1.（1）L->next==NULL或者！L->next（2分）
（2）p->next=r->next; （2分）
r->next=p; （2分）
2.（1）（4分）
0
1
2
3
4
5
6
7
8
9
10
8
25

27
12
13
68
31
39

（2）ASL=1/8(1+1+1+1+1+2+1+3)=11/8=1.375（2分）

3.（评分标准：矩阵3分，图3分，全正确6分。）

4.（1）（评分标准：每一趟1分）
初始结果：12 2 16 30 28 10 16* 20 6 18
第一趟： 2 12 16 30 10 28 16 * 20 6 18
第二趟： 2 12 16 30 10 16* 20 28 6 18
第三趟： 2 10 12 16 16* 20 28 30 6 18
第四趟： 2 6 10 12 16 16* 18 20 28 30
（2） 稳定（2分）

5.（1）（4分）

（2）（2分）
WPL=5*2+6*2+3*3+4*3+8*2=59

五、算法设计题
1.
void BubbleSort(SqList &L)
{
int m,flag,i;
m=L.length-1;flag=1;（1分）
while(m>0&&flag) （1分）
{
flag=0; （1分）
for(i=1;i<=m;i++) （1分）
{
if(L.R[i].key>L.R[i+1].key)（1分）
{
flag=1; （1分）
L.R[0]=L.R[i+1]; （1分）
L.R[i+1]=L.R[i]; （1分）
L.R[i]=L.R[0]; （1分）
}
}
m--; （1分）
}
}
或者
int Partition(SqList &L,int low,int high)
{
KeyType pivotkey;
L.R[0]=L.R[low];
pivotkey=L.R[low].key;（1分）
while(low<high)（1分）
{
while(low<high&&L.R[high].key>=pivotkey)
（1分）
--high;（1分）
L.R[low]=L.R[high];（1分）
while(low<high&&L.R[low].key<=pivotkey)
（1分）
++low;（1分）
L.R[high]=L.R[low];（1分）
}
L.R[low]=L.R[0];（1分）
return low;（1分）
}

void QSort(SqList &L,int low,int high)
{
int pivotloc;
if(low<high)
{
pivotloc=Partition(L,low,high);
QSort(L,low,pivotloc-1);
QSort(L,pivotloc+1,high);
}
}

void QuickSort(SqList &L)
{
QSort(L,1,L.length);
}
2.（1）结构定义：
#define MAXQSIZE 100
typedef struct{
QElemType *base;
int front;
int rear;
}SqQueue; （2分）

（2）循环队列入队算法：
Status EnQueue(SqQueue &Q,QElemType e)
{
if((Q.rear+1)%MAXQSIZE ==Q.front)
Return ERROR;
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAXQSIZE ;
return OK;
} （4分）

（3）循环队列出队算法：
Status DeQueue(SqQueue &Q,QElemType &e)
{
if(Q.front ==Q.rear)
return ERROR;
E=Q.base[Q.front]
Q.front=(Q.front+1)%MAXQSIZE ;
return OK;
} （4分）
若没写出代码，仅写出算法思想各题给6分。

第 5 页 共 5 页