2.8 数据结构练习题及参考答案
练习题
1.求下列各程序段的时间复杂度。
（1）y=SIN(x)
（2）1.for i=1 to n-1
2. y←y+1
3. for j=0 to 2n
4. x←x+1
5. end(j)
6. end(i)
(3)1.x←1;y←1
2.for k=1 to n
3. x←x+1
4. end(k)
5.for i=1 to n
6. for j=1 to n
7. y←y+1
8. end(j)
9.end(i)
(4)1.i←1
2.while(i<n) and (x≠A[i])
3.i←i+1
4.if(A[i]=x) then return(i)
5.end(while)
2.已知线形表（a 
，a
，…，a
）中的元素值按递增有序排列，选用顺序表结构存放，试编写算法删除线性表中值介于c与d（c≤d）之间的元素。
3.已知顺序存放的线性表为（a
，a
，…，a
，
，
…，
），试设计算法，用尽可能少的辅助空间，将线性表中a，b元素位置对换，即成为（
，
…，
，a
，a
，…，a
）。
4.在用尾叉法建立线性链表算法中（见例2.9）把语句8.移入while循环内是否可以？为什么？
5.试设计建立一个无头结点的单链表的算法。
6.修改例2.8中算法PRINT，用来打印一个带有头结点的单链表内容。
7.设计算法，求带头结点的循环链表的长度，如图2.27所示。
8.在带头结点的单循环链表的第i个结点前插入元素值为x的结点。
9.删除带头结点单循环链表的第i个结点。
10.算法INVERT2中语句7是否必要？能否改为head←p？
11.算法INVERT2中语句5能否改写成：p←r；q←p？
12.设计另一种逆置链表的算法：另建一链表p（初值为空），依次删除原链表头指针head所指的结点插入到p表表头。
13.设计循环队列的插入、删除算法，设置变量flg作为对满和队空的标志。（flg=1队满，flg=0队空）
14.已知一个带头结点循环链表构成的队列（如图2.28所示），并且只设一个指向队尾的指针rear，试用算法描述语言写出下列操作：
（1）在队尾指针后增加一个由s指针指向的结点，且仍保持为循环链表。
（2）删除头结点后的结点，且仍保持为循环链表。
15.已知RV（n）算法为：
RV（n）
1.if（n>0）then
2. {white (n mod 10)
3. RV (n div 10)}
4.return
画出RV（1 2 3 4 5）的执行路线及执行结果。
16.已知F(n)算法为：
1.F（n）
2.if （n<=）then F←1
3.else F←2*F(n-1)+3*F(n-2)
4.return(F)
画出F（b）的执行路线及执行结果。
17.已知函数hef(m,n)=
编制hef（m，n）程序，并画出hef（100，18）的执行路线及执行结果。
18.设（6×7）稀疏矩阵B如下
B=
分别用下列三种方式表示，并叙述访问元素B[6，5]的过程。
1. 三元组表示。
2. 带辅助变量的三元组表示。
3. 十字链表表示。
19.在用递归算法求二叉树结点数算法NODE1中：
（1）在算法的if语句之前将变量n清除为0是否正确？在算法末尾加上else←0是否正确？为什么？
（2）算法中把n设为局部变量是否正确？
20．用递归算法求二叉树结点数算法NODE2中：
（1）p为空时，n不置0行不行？
（2）和NODE1比较，找一些规律。
（3）n
是局部变量还是全局变量？是否既可以是全局变量，又是局部变量？
21．用函数形式求二叉树结点数算法NODE3中：
（1）在算法中是否要增加左右子树均为空时n←1的语句？
（2）在语句2中去掉1，结果如何？
（3）当p=nil是n不置0，结果如何？
22．用递归算法求二叉树叶子结点数的算法LEAF1中，加上p=nil时将n←0行不行？
23．用递归算法求二叉树叶子结点数的算法LEAF2中：
（1）算法中去除p=nil时n←0行不行？
（2）说明语句n
←n的作用
24．比较LEAF1和LEAF2算法中的全局变量n：
（1）当n作为累加值时，p=nil及p
nil时对n各做何操作？
（2）当n作为赋值作用时，p=nil及p
nil时对n各做何操作？
25．用函数形式求而乍数叶子结点数的算法LEAF3中：
（1）在算法中去掉第2个条件，使成为：
If （p=nil）then n←0
Else n←（LEAF3（L（p））+LEAF3（R（p）））
将得到什么结果？
（2）如果将条件写成下面几种：
①P为空 叶子树为0
②P左右子树均为空 叶子树为1
③P左右子树为空 叶子树为右子树的叶子数
④p右子树为空 叶子树为左子树的叶子数
⑤P左右子树均不空 叶子树为左、右子树的叶子数之和
将得到什么结果？
26．在求二叉树高度算法HIGH1中：
（1）p=nil时h不置0是否可以？
（2）其中h
是局部变量还是全局变量？是否可以是全局变量，又是局部变量？
27．试用函数形式编写求二叉树高度的算法.
28.试用序列
和
，分别生成两棵二叉树排序树，比较其异同。
29．由序列（51，17，60，32，6，10，23，3，80，40
，44，7）构成的二叉排序树中
（1）画出删除结点“17”的过程。
（2）能否再用另一种方式进行删除？比较两种方式的优缺点。
30．给定权值为w=
构造哈夫曼树，请问构成的哈夫曼树是否唯一的？为什么？
31．已知有序序列（1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，16，17，18，19，20），分别用线性查找和对分查找方法查找其中2，14，18各需要花费多少次比较？并分别求出平均查找长度ASL。
32．已知1至12月份的英文字母为：JAN，FEB，MAR，APR，MAY，JUN，JUL，AUG，SEP，OCT，NOV，DEC。 要求：
（1）按月份的先后次序读入。
（2）按JAN，FEB，MAY，AUG，DEC，OCT，APR，JAN，JUN，SEP，NOV次序读入。
（3）按英文字母读入。
构成一按英文字母排序的二叉排序树，分别画出二叉排序树及平均查找长度ASL。
33．已知哈希表地址空间为0至14，哈希函数为H（K）=K mod 13，采用线性探测法处理冲突，将下列各数依次存入哈希表中，并求出等概率下的平均查找长度ASL。
（240，29，345，189，100，20，21，35，3，208，78，99，45，350）
34．采用线性插入法对关键字序列（46，32，55，81，65，11，25，43）按小到大次序，写出每趟排序结果。
35．将下面的数据建成一个堆：
（70，12，20，31，1，5，44，66，61，200，31，80，150，4，28）
36．请说明建一个堆和调整一个堆的区别。
37．对下面的数据表写出采用快速排序算法排序的每一趟结果，其中第一趟要求标明排序过程中数据移动情况。（50，12，20，31，1，5，44，166，61，100，30，80，150，4，8）
38．对下面的数据表，写出采用冒泡排序的每一趟结果。（25，10，20，31，5，44，16，61，100，3）
参考文献
1. 严尉敏，陈文博。数据结构，北京：机械工业出版社，1990
2. 蔡明志.数据结构使用C语言.北京.科学出版社，1993
3. 胡学钢.数据结构算法设计指导.北京：清华大学出版社，1999
参考答案
1.(1)这是一个单语句，频度为F（n）=1，因此时间复杂度为T（n）=O（1）。
（2）语句2.的频度为n-1，语句4的频度为（n-1）（2n+1）=2n
-n-1，因此时间复杂度T（n）=O（n
）。
（3）语句3的频度为n语句7的频度为n
，因此时间复杂度为T（n）=O（n
）。
(4)语句3的频度不仅与n有关，而且和x及数组A中各分量的值有关，这是通常考虑最坏的情况，由于while循环的最大次数为n-1，因此时间复杂度为T（n）=O（n）。
2. DEL3 （A，n，c，d）
1.i←1,j←0
2.while (A[i]<=d) do
3. if (A[i]>=c) then j←j+1
4.i←i+1
5. end(while)
6.for k=I to n
7.A[k-j] ←A[k]
8.end(k)
9.return
时间复杂度为O（n）。
3. EXCHANGE（A，m，n）
1.INVERT1(A,1,m+n)//将线性表A中（a
，…,a
）逆置//
2. INVERT1(A,1,m)//将线性表A中（a
，…,a
）逆置//
3. INVERT1(A,m+1,m+n)//将线性表A中（a
，…,a
）逆置//
4.return
时间复杂度为O（m+n）。
4可以
5． Create 2（head）
1．Head←nil
2．Read（小）
3.while(x
结束标志)do
4．GETNODE（p）；data（p）←x
5.if(head=nil)then
//r指向当前尾结点//
6．Else next（r）←p
7．r←p；read（x）
8.end(while)
9.next(r) ←nil
10.return
6.修改语句1为p←next（head）。
7． LENGTH2（head）
1．p←next（head）；n←0
2. while (p
head) do
3. n←n+1
4. p←next(p)
5.end(while)
6.return(n)
8. INS 4(head,I,x)
1.j←0;p←head
2.while(j
i-1)and (next(p) 
head) do
3.next(p) ←p;j←j+1
4．End(while)
5.if(j=i-1) then
6.{GETNODE(S);data(s) ←x
7.next(s) ←next(p);next(p) ←s}
8.else “I 不合法”
9．Return
9． DEL 4(head,i)
1. p←head; j←0
2. while(next(p) 
head) and (j
i-1) do
3. p←next(p); j←j+1
4. End(while)
5.if(next(p) 
head) then“I 不合法”
6.else{u←next(p)
7． next(p) ←next（u）
8． RET（u）}//删除第i个元素并回收空间//
9．Return
10．语句7是把head指向逆置后表头，必要。不能改成head←p，此时p为“空”。
11．不行
12 INVERT3 (head)
1.p←nil
2.while(head
nil) do
3.u←head;head←next(head)//删除head所指的结点//
4。Next（u）←p；p←u//将结点u插入p表头//
5．End(while)
6．Head ←p//head指向新表表头//
7．Return
13．Flg初始值为0
插入算法：
1. INQUE 2（Q，n，front，rear，flg，x）
2. If（front=rear）and （flg=1）then “上溢出“
3. Else{rear←（rear+1）mod n；Q[rear] ←x
4. If （front=rear）then flg←1}
5. Return
删除算法：
1. DEQDUE 2（Q，n，front，rear，flg，y）
2. If（front=rear）and （flg=0）then “下溢出“
3. Else {front←（front+1）mod n；y←Q[front]
4. If（front=rear）then flg←0}
5. Return
14．（1）next(s) ←next(rear)
Next(rear) ←rear
rear←next(rear)
(2)if (next(next(rear))=rear)then
{next(rear) ←rear
Next(rear)←rear//删除最后一个结点//
Else next （next（rear））←next（next（next（rear）））
15．执行线路如图2.31。
输出结果：5 4 3 2 1
16．F（6）的执行线路如图2.32.
执行结果：F（6）=121
17．Hef（m，n）的算法为：
Hef（m，n）
（1） If（n）then x ←m
（2） Else x←hef(n,m mod n)
（3） Return(x)
Hef(100,18)的执行线路如图2.33.
执行结果：hef（100，18）=2
18．略。
19．（1）不正确。因为是递归算法，程序段要反复执行，n是全局变量，是通过递归调用时的累计来完成其结果的求解。而n的初值置为0是一次性操作，如果放到递归算法中就会被反复执行，从而清除了原先累计的结果。
(2)不正确。因为局部变量只在本层中使用，不能为各层所共享。
20．（1）不行。求不出p为空时的结点数。
（2）NODE1中n为累计求解，NODE2中n为赋值求解。对上述两种算法在p为空和不空时均符合命题要求。
（3）
必须是全局变量。全局变量在整个程序中使用。在递归程序各层之间也可以全程使用。而局部变量只能限于定义该变量的过程中使用。递归程序中的局部变量只能在某一层中使用。不同的调用层有自己的一套局部变量。本算法中
显然只能属于某一层使用，否则在对不同层中变量赋值操作会相互破坏。
21.（1）不必要。在语句2中通过调用左、右子树的过程，实现这一问题的解。
（2）结果为0。
（3）结果为随机数。
22. 不行。n←0就不是累加型了。
23.（1）不行。去除此语句，n成为累加型。
（2）语句
←n的作用是保存n的值。
24.（1）当n作为累加值时；
当p=nil时，不改变n的值。
当p≠nil时，对左、右子树依次操作的是同一个变量n。
（2）当n作为赋值作用时；
当p=nil时，不改变n的值；
当p≠nil时，对左、右子树操作的结果将分别用一个变量保存，最后再合并。
25.（1）结果为二叉树的结点数。
（2）与原算法等价。
26.（1）不行。因为p=nil时h不置0，不符合命题要求。
（2）只能是局部变量。
27. HIGH2（p）
1.if （p=nil）then h←0
2.else h←max（HIGH2（L（p））,HIGH2(R(p))+1
3.return(h)
28.
由于初始序列不同，构成二叉排序树的深度不同。
29．
方案2较方案1深度大。
30．
相同权值构成的哈夫曼树可能不惟一，但是它们的WPL应相同。
31（1）线性查找
查找2比较次数2
查找13比较次数13
查找18比较次数18
ASL=
=10.5
（2）对分查找
查找2比较次数3
查找13比较次数4
查找18比较次数3
ASL=（1+2×2+3×3+4×4+4×8+5×5）/20=3.7
32.（1）
ASL=（1+2×2+3×3+3×4+5×2+6）12=3.5
（2）
ASL=（1+2×2+3×3+3×4+5）/12=3.1
(3)
ASL=(1+2+3+4+5+6+7+8+9+10+11+12)/12=6.5
|
ASL=(5×1+3×2+3×4+2×6+1×9)/14=43/14
34.
35．
36.建一个堆是从
结点开始到根节点，将本结点与左右孩子结点进行比较，若不满足堆要求，则进行交换，交换后可能使其下层结点不满足要求，需要沿着被交换结点的分支向下检查，发现不满足要求的，进行上下层结点的交换，因此工作量较大。
调整堆的工作是从某一个非叶子结点开始，检查以此结点为根的二叉树是否为堆，若不满足则进行上下结点交换，因此它是局部性工作，工作量相对较少。
37.
38.
