（A）、n2（B）.O（nlgn）（C）.O（n）（D）.O（n2）
3．折半查找法适用于（）。
（A）、有序顺序表（B）、有序单链表
（C）、有序顺序表和有序单链表都可以（D）、无限制
4．顺序存储结构的优势是（）。
（A）、利于插入操作（B）、利于删除操作
（C）、利于顺序访问（D）、利于随机访问
5．深度为k的完全二叉树，其叶子结点必在第（）层上。
（A）、k-1（B）、k（C）、k-1和k（D）、1至k
6．具有60个结点的二叉树，其叶子结点有12个，则度过1的结点数为（）
（A）、11（B）、13（C）、48（D）、37
7．图的Depth-FirstSearch（DFS）遍历思想实际上是二叉树（）遍历方法的推广。
（A）、先序（B）、中序（C）、后序（D）、层序
8．在下列链队列Q中，元素a出队的操作序列为（）
Q
（A）、p=Q.front->next;p->next=Q.front->next;
（B）、p=Q.front->next;Q.front->next=p->next;
（C）、p=Q.rear->next;p->next=Q.rear->next;
（D）、p=Q->next;Q->next=p->next;
9．Huffman树的带权路径长度WPL等于（）
（A）、除根结点之外的所有结点权值之和（B）、所有结点权值之和
（C）、各叶子结点的带权路径长度之和（D）、根结点的值
10．线索二叉链表是利用（）域存储后继结点的地址。
（A）、lchild（B）、data（C）、rchild（D）、root
二、填空题
1．逻辑结构决定了算法的，而存储结构决定了算法的。
2．栈和队列都是一种的线性表，栈的插入和删除只能在进行。
3．线性表（a1,a2,…,an）的顺序存储结构中，设每个单元的长度为L，元素ai的存储地址LOC（ai）为
4．已知一双向链表如下（指针域名为next和prior）：
q
p
现将p所指的结点插入到x和y结点之间，其操作步骤为：
；
；；；
5．n个结点无向完全图的的边数为，
n个结点的生成树的边数为。
6．已知一有向无环图如下：
任意写出二种拓扑排序序列：
、。
7．已知二叉树的中序遍历序列为BCA，后序遍历序列为CBA，则该二叉树的先序遍历序列为，层序遍历序列为。
三、应用题
1．设散列函数H（k）=k%13,设关键字系列为{22,12,24,6,45,7,8,13,21},要求用线性探测法处理冲突。
（6分）
（1）构造HASH表。
（2）分别求查找成功和不成功时的平均查找长度。
2．给定表（19,14,22,15,20,21,56,10）.（8分）
（1）按元素在表中的次序，建立一棵二叉排序树
（2）对
（1）中所建立的二叉排序树进行中序遍历，写出遍历序列。
（3）画出对
（2）中的遍历序列进行折半查找过程的判定树。
3．已知二个稀疏矩阵A和B的压缩存储三元组表如下：
AB
i
j
V
i
j
V
1
3
-5
2
5
2
2
4
6
3
3
7
2
5
2
4
1
3
4
2
-1
5
2
-9
5
2
9
5
5
8
写出A-B压缩存储的三元组表。
（5分）
4．已知一维数组中的数据为（18,12,25,53,18）,试写出插入排序（升序）过程。
并指出具有n个元素的插入排序的时间复杂度是多少？
（5分）
5．已知一网络的邻接矩阵如下，求从顶点A开始的最小生成树。
（8分，要有过程）
ABCDEF
（1）求从顶点A开始的最小生成树。
（2）分别画出以A为起点的DFS生成树和BFS生成树。
6．已知数据六个字母及在通信中出现频率如下表：
A
B
C
D
E
F
0.15
0.15
0.1
0.1
0.2
0.3
把这些字母和频率作为叶子结点及权值，完成如下工作（7分，要有过程）。
（1）画出对应的Huffman树。
（2）计算带权路径长度WPL。
（3）求A、B、C、D、E、F的Huffman编码。
7．已知有如下的有向网：
求顶点A到其它各顶点的最短路径（采用Dijkstra算法，要有过程）。
（6分）
三、设计题（30分，每题10分,用C语言写出算法，做在答题纸上）
1．已知线性表（a1,a2,…,an）以顺序存储结构为存储结构，其类型定义如下：
#defineLIST_INIT_SIZE100//顺序表初始分配容量
typedefstruct{
Elemtype*elem;//顺序存储空间基址
intlength;//当前长度（存储元素个数）
}SqList;
设计一个算法，删除其元素值为x的结点（假若x是唯一的）。
并求出其算法的平均时间复杂度。
其算法函数头部如下：
StatusListDelete（Sqlist&L,Elemtypex）
{
……
}
2．设顺序栈如左图所示。
其中结点定义如下：
top
typedefstruct{
Elemtype*base;//栈底指针
Elemtype*top;//栈顶指针
}Stack;
设计算法，将栈顶元素出栈并存入e中．base
3．设二叉链树的类型定义如下：
typedefintElemtype;
typedefstructnode{
Elemtypedata;
structnode*lchild,*rchild;
}BinNode,*BinTree;
试写出求该二叉树叶子结点数的算法:
StatusCountLeaves（BinTree&root,int&n）
{//nisthenumberofleaves
……
}
答案：
选择题（每题1分）
1、C2、D3、A4、D5、C6、D7、A8、B9、C10、C
一、填空题
1．设计、实现
2．特殊、栈顶
3．LOC（a1）+（i-1）*L
4．p->next=q->next;q->next->prior=p;q->next=p;p->prior=q;
5．n（n-1）/2、n-1
6．ADCBFEG、ABCDEFFG
7．ABC、ABC
二、应用题
1
（1）Hash表（4分）
地址
0
1
2
3
4
5
6
7
8
9
10
11
12
关键安
13
21
6
45
7
22
8
24
12
探测次数
1
7
1
2
3
1
3
1
1
（2）查找成功的平均查找长度：
（1分）
（5*1+1*2+2*3+1*7）/9=20/9
查找不成功的平均查找长度：
（1分）
（2+1+9+8+7+6+5+4+3+2+1）/13=
2
（1）、构造（3分）
（2）、1014151920212256（2分）
（3）、（3分）
3、（5分，每行0.5）
i
j
v
1
3
-5
2
4
6
3
3
7
4
1
3
4
2
-1
5
2
18
5
5
8
4、初始关键字：
[18]12255318
第一趟：
[1218]255318
第二趟：
[121825]5318
第三趟：
[12182553]18
第四趟：
[1218182553]（4分）
O（n2）（1分）。
5、7分
（1）4分
A
B1C
32
5D4
EF
（2）4分
6、
（1）3分
（2）WPL=0.1*3+0.1*3+0.2*2+0.15*3+0.15*3+03*21=（1分）
（3）A：
010B：
011C：
110D：
111E：
00F；10（3分）
12、A-B：
（A、B）1分
A-C：
（A、D、C）2分
A-D：
（A、D）1分
A-E：
（A、D、E）2分
三，设计题（20分）
1、（10分）
StatusListDelete（Sqlist&L,ElemTypex）
{
inti,j;
for（i=0;ilength;i++）
if（L->elem[i]==x）break;
if（i=L->length）returnERROR;
for（j=i;jlengthi-1;j++）
L->elem[j]=L->elem[j+1];
L->length--;
}（8分）
平均时间复杂度：
（2分）
设元素个数记为n，则平均时间复杂度为：
2（10分）
voidpop（Stack&S,Elemtype&e）
{
if（S.top==S.base）returnERROR;
S.top--;
e=*s.top;
}
2、（10分）
voidCountLeaves（BinTreeT,int&n）
{
if（T）
{
if（（!
（T->lchild）&&!
（T->rchild））n++;
CountLeaves（T->lchild,n）;
CountLeaves（T->rchild,n）;
}
}
习题1
一、单项选择题
1.数据结构是指（）。
A.数据元素的组织形式B.数据类型
C.数据存储结构D.数据定义
2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。
A.存储结构B.逻辑结构
C.链式存储结构D.顺序存储结构
3.树形结构是数据元素之间存在一种（）。
A.一对一关系B.多对多关系
C.多对一关系D.一对多关系
4.设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。
for（i=1;i<=n;i++）
for（j=i;j<=n;j++）
x++;
A.O
（1）B.O（）C.O（n）D.O（）
5.算法分析的目的是
（1），算法分析的两个主要方面是
（2）。
（1）A.找出数据结构的合理性B.研究算法中的输入和输出关系
C.分析算法的效率以求改进D.分析算法的易懂性和文档性
（2）A.空间复杂度和时间复杂度B.正确性和简明性
C.可读性和文档性D.数据复杂性和程序复杂性
6.计算机算法指的是
（1），它具备输入，输出和
（2）等五个特性。
（1）A.计算方法B.排序方法
C.解决问题的有限运算序列D.调度方法
（2）A.可行性，可移植性和可扩充性B.可行性，确定性和有穷性
C.确定性，有穷性和稳定性D.易读性，稳定性和安全性
7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。
A.低B.高C.相同D.不好说
8.数据结构作为一门独立的课程出现是在（）年。
A.1946B.1953C.1964D.1968
9.数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。
A.正确B.错误
C.前半句对，后半句错D.前半句错，后半句对
10.计算机内部数据处理的基本单位是（）。
A.数据B.数据元素C.数据项D.数据库
二、填空题
1.数据结构按逻辑结构可分为两大类，分别是____________?
__和_________________。
2.数据的逻辑结构有四种基本形态，分别是________________、__________________、__________________和__________________。
3.线性结构反映结点间的逻辑关系是__________________的，非线性结构反映结点间的逻辑关系是__________________的。
4.一个算法的效率可分为__________________效率和__________________效率。
5.在树型结构中，树根结点没有__________________结点，其余每个结点的有且只有__________________个前趋驱结点；叶子结点没有__________________结点；其余每个结点的后续结点可以__________________。
6.在图型结构中，每个结点的前趋结点数和后续结点数可以__________________。
7.线性结构中元素之间存在__________________关系；树型结构中元素之间存在__________________关系；图型结构中元素之间存在__________________关系。
8.下面程序段的时间复杂度是__________________。
for（i=0;ifor（j=0;jA[i][j]=0;
9.下面程序段的时间复杂度是__________________。
i=s=0;
while（s{i++;
s+=i;
}
10.下面程序段的时间复杂度是__________________。
s=0;
for（i=0;ifor（j=0;js+=B[i][j];
sum=s;
11.下面程序段的时间复杂度是__________________。
i=1;
while（i<=n）
i=i*3;
12.衡量算法正确性的标准通常是____________________________________。
13.算法时间复杂度的分析通常有两种方法，即___________和___________的方法，通常我们对算法求时间复杂度时，采用后一种方法。
三、求下列程序段的时间复杂度。
1.x=0;
for（i=1;ifor（j=i+1;j<=n;j++）
x++;
2.x=0;
for（i=1;ifor（j=1;j<=n-i;j++）
x++;
3.inti,j,k;
for（i=0;ifor（j=0;j<=n;j++）
{c[i][j]=0;
for（k=0;kc[i][j]=a[i][k]*b[k][j]
}
4.i=n-1;
while（（i>=0）&&A[i]!
=k））
j--;
return（i）;
5.fact（n）
{if（n<=1）
return
（1）;
else
return（n*fact（n-1））;
}
习题1参考答案
一、单项选择题
1.A2.C3.D4.B5.C、A6.C、B7.B8.D9.B10.B
二、填空题
1.线性结构，非线性结构
2.集合，线性，树，图
3.一对一，一对多或多对多
4.时间，空间
5.前趋，一，后继，多
6.有多个
7.一对一，一对多，多对多
8.O（）
9.O（）
10.O（）
11.O（logn）
12.程序对于精心设计的典型合法数据输入能得出符合要求的结果。
13.事后统计，事前估计
三、算法设计题
1.O（）2.O（）3.O（n）4.O（n）5.O（n）
习题2
一、单项选择题
1.线性表是________。
A．一个有限序列，可以为空B．一个有限序列，不可以为空
C．一个无限序列，可以为空D．一个无限序列，不可以为空
2.在一个长度为n的顺序表中删除第i个元素（0<=i<=n）时，需向前移动个元素。
A．n-iB．n-i+lC．n-i-1D．i
3.线性表采用链式存储时，其地址________。
A．必须是连续的B．一定是不连续的
C．部分地址必须是连续的D．连续与否均可以
4.从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较________个元素结点。
A．n/2B．nC．（n+1）/2D．（n-1）/2
5.在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是____。
A．p->next=s;s->prior=p;
p->next->prior=s;s->next=p->next;
B．s->prior=p;s->next=p->next;
p->next=s;p->next->prior=s;
C．p->next=s;p->next->prior=s;
s->prior=p;s->next=p->next;
D．s->prior=p;s->next=p->next;
p->next->prior=s;p->next=s;
6.设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为________。
A．p->next=p->next->next;B．p=p->next;
C．p=p->next->next;D．p->next=p;
7.在一个长度为n的顺序表中向第i个元素（0A．n-iB．n-i+lC．n-i-1D．i
8.在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行
A．s->next=p->next;p->next=s
B．q->next=s;s->next=p
C．p->next=s->next;s->next=p
D．p->next=s;s->next=q
9.以下关于线性表的说法不正确的是______。
A．线性表中的数据元素可以是数字、字符、记录等不同类型。
B．线性表中包含的数据元素个数不是任意的。
C．线性表中的每个结点都有且只有一个直接前趋和直接后继。
D．存在这样的线性表：
表中各结点都没有直接前趋和直接后继。
10.线性表的顺序存储结构是一种_______的存储结构。
A．随机存取B．顺序存取C．索引存取D．散列存取
11.在顺序表中，只要知道_______，就可在相同时间内求出任一结点的存储地址。
A．基地址B．结点大小
C．向量大小D．基地址和结点大小
12.在等概率情况下，顺序表的插入操作要移动______结点。
A．全部B．一半
C．三分之一D．四分之一
13.在______运算中，使用顺序表比链表好。
A．插入B．删除
C．根据序号查找D．根据元素值查找
14.在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是_______。
A．O
（1）B．O（n）
C．O（n2）D．O（log2n）
15.设有一个栈，元素的进栈次序为A,B,C,D,E,下列是不可能的出栈序列__________。
A．A,B,C,D,EB．B,C,D,E,A
C．E,A,B,C,DD．E,D,C,B,A
16.在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为______。
A．top不变B．top=0C．top--D．top++
17.向一个栈顶指针为hs的链栈中插入一个s结点时，应执行______。
A．hs->next=s;
B．s->next=hs;hs=s;
C．s->next=hs->next;hs->next=s;
D．s->next=hs;hs=hs->next;
18.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为________。
A．rear％n==frontB．（front+l）％n==rear
C．rear％n-1==frontD．（rear+l）％n==front
19.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为________。
A．rear％n==frontB．front+l=rear
C．rear==frontD．（rear+l）％n=front
20.在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为________。
A．front=front->next B．rear=rear->next
C．rear=front->next D．front=rear->next
二、填空题
1.线性表是一种典型的_________结构。
2.在一个长度为n的顺序表的第i个元素之前插入一个元素，需要后移____个元素。
3.顺序表中逻辑上相邻的元素的物理位置________。
4.要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需_______一个位置，移动过程是从_______向_______依次移动每一个元素。
5.在线性表的顺序存储中，元素之间的逻辑关系是通过_______决定的；在线性表的链接存储中，元素之间的逻辑关系是通过_______决定的。
6.在双向链表中，每个结点含有两个指针域，一个指向_______结点，另一个指向_______结点。
7.当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用_______存储结构为宜。
相反，当经常进行的是插入和删除操作时，则采用_______存储结构为宜。
8.顺序表中逻辑上相邻的元素，物理位置_______相邻，单链表中逻辑上相邻的元素，物理位置_______相邻。
9.线性表、栈和队列都是_______结构，可以在线性表的______位置插入和删除元素；对于栈只能在_______位置插入和删除元素；对于队列只能在_______位置插入元素和在_______位置删除元素。
10.根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为_________和_______；而根据指针的联接方式，链表又可分为______
升级会员 