练 习 题 1
1.单项选择题 (从下列各题四个备选答案中选出一个正确答案,将其代号 (A,B,C,D)写在题干前面的括号内 )
( )(1)一个数据对象是 ____的集合。
A.相同类型的数据项 B.相同类型的数据元素
C.不同类型的数据项 D.不同类型的数据元素
( )(2)___是数据的基本单位。
A.数据项 B.关键字
C.数据元素 D.数据类型
2.一个算法具有哪几个特点？举例说明之。
3.下列描述不符合算法的什么特征和要求？
(1) void suanfa1( )
{ int i,s；
s=0；
for(i=0； i>=0； i++)
s++；
}
(2) float suanfa2(float x)
{ float y；
y=sqrt(x)；
return(y)；
}
4.执行和分析下面的 C程序,
main( )
{ int i,j；
for(i=0,j=0； j++,i<5； i++)
printf("%d,",i)；
printf("%d,%d",i,j)；
}
试问
(1)表达式,i++” 共计执行多少次？
(2)表达式 "j++" 共计执行多少次？
(3)程序的输出结果是多少？
5.执行和分析下面的算法,回答问题 。
int suanfa1(int m,int n)
{ int i,j,s=0；
for(i=1； i<=m； i++)
{ for(j=1； j<=n； j++)
s++；
printf("%d",s)；
}
return s；
}
(1) 试问语句 "printf("%d",s)； " 共计执行多少次？
(2) 试问语句 "s++； " 共计执行多少次？
(3） 该算法的时间复杂度是多少？
(4）当 m=n=5时,算法的 输出结果是什么？
(5） 当 m=n=5时,算法的返回值是多少？
6.执行和分析下面的算法,回答问题 。
int suan_fan(int n)
{ int i,j,x=0；
for(i=1； i<n； i++)
{ for(j=1； j<i； j++)
x++；
printf("x=%d\n",x)；
}
return x；
}
(1) 试问语句,x++；,共计执行多少次？
(2) 试分析算法的时间复杂度；
(3) 假定 n=6,试指出算法的输出结果；
(4) 假定 n=6,算法的返回值是多少？
7.执行和分析下面的算法,回答问题,
void abc(int n)
{ int i=1；
while(i<=n)
i=i*2；
printf("i=%d\n",i)；
}
(1) 试问,i<=n” 共计执行多少次？
(2) 试问,i=i*2” 共计执行多少次?
(3) 试分析算法的时间复杂度；
(4) 假定 n=1000,试指出算法的输出结果 。
练 习 题 2
1.下列表示哪是线性表？
(1)(10,-3,55,7)
(2)(1,2,3,4,...)
(3){A,B,C,D,E}
(4){'a','b','c'}
2.线性表的顺序存储结构有什么优点和缺点?
3.对单链表可以进行哪几种操作？
4.试比较单链表、双链表、循环链表的优、缺点。
5.线性表的存储结构,在什么情况下使用顺序结构？
在什么情况下使用链表结构？为什么？
6.在下列双向链表中,已知指针 p指向结点 A，在 A,C之间插入结点 B，写出要执行的操作：
CA
B
p
f
7.已知线性表 L=(a1,a2,...,an)存放在一维数组 A[0..n-1]
中,将线性表 L就地逆置 为 L=(an,...,a2,a1),试写出算法。
练 习 题 3
1.设输入元素 B,C,A,D到栈中,能得当哪几种输出?
不能得到哪几种输出序列？
(1) A,B,C,D (7) B,A,C,D (13) C,A,B,D (19) D,B,C,A
(2) A,B,D,C (8) B,A,D,C (14) C,A,D,B (20) D,B,A,C
(3) A,C,B,D (9) B,C,A,D (15) C,B,A,D (21) D,C,B,A
(4) A,C,D,B (10) B,C,D,A (16) C,B,D,A (22) D,C,A,B
(5) A,D,B,C (11) B,D,A,C (17) C,D,A,B (23) D,A,B,C
(6) A,D,C,B (12) B,D,C,A (18) C,D,B,A (24) D,A,C,B
2.设链式栈的栈顶头指针为 top，弹出栈顶元素送 e,试写出退栈算法 pop(top,e)。
练 习 题 5
5.1 试分别画出有 3行 4列元素的数组 a[1..3,1..4 ]的以行为主序和以列序为主序的顺序存储结构图。
5.2 选择题 (从下列各题四个备选答案中选出 1个正确答案,
将其代号 (A,B,C,D)写在题干前面的括号内 )
( )1.____是 'Data**element'的子串。
A.Data B.'Dataelement' C.'**ele' D.'data'
( )2.设数组 a[0..6,0..5]的基地址为 1024,每个元素占 2个存储单元,若以 行 序为主序顺序存储,则元素 a[2,4]的存储地址是 __。
A.1058 B.1056 C.1098 D.答案 A,B,C都不对
( )3.设数组 a[0..6,0..5]的基地址为 1024,每个元素占 2个存储单元,若以 列 序为主序顺序存储,则元素 a[2,4]的存储地址是 ___。
A.1084 B.1056 C.1098 D.答案 A,B,C都不对
( )4.设数组 a[1..5,1..7]的基地址为 1000,每个元素占 2个存储单元,若以 行 序为主序顺序存储,则元素 a[4,3]的存储地址是 ___。
A.1044 B.1048 C.1046 D.答案 A,B,C都不对
( )5.广义表 (a,(b,c),(d))的表尾是 ____。
A.(d) B.((d)) C.(b,c),(d) D.((b,c),(d))
( )6.广义表 (a,(b,c,d,( ),( )),((e)))的长度是 ____。
A.3 B.4 C.5 D.6
( )7.广义表 (a,(b,(c),((d)),( )),((f,g),h))的深度是 ___。
A.3 B.4 C.5 D.6
( )8.深度为 5的完全二叉树至少有 ____个结点 。
A.25 B.15 C.32 D.16
课 堂 练 习
画出表达式二叉树
A + B * (C + D)/（ E -F） - G
课 堂 练 习画出表达式二叉树
A + B * (C + D )/（ E - F） - G
+
*
/
B +
-
C D
E F
表达式二叉树
A
-
G
课 堂 练 习
设输入关键字序列 (数列 )：
58,60,10,80,19,55,90,4,70,12
生成 (画出 )二叉排序树,
课 堂 练 习
分别画 出二叉树 T：
1.前序线索二叉树 2.后序线索二叉树
3.中序线索二叉树 4.中序线索二叉树 链表
F
A
G
B
IC E
二叉树 T
H
D
课堂练习
试画出图 G的 邻接多重表
E
D G
BA
C
图 G
F
H
课堂练习
用 普里姆 (Prim)算法求网 G的一棵最小生成树,写出求解过程 。
C
A
D
E
B
F
网 G
3
7
1
8
7
455 6
6
G5
9
6
作 业 7
7.1 试画出下列 存储结构图：
1.图 G1的邻接表,逆邻接表,十字链表；
2.图 G2的邻接多重表；
3.图 G3的数组表示 (表示顶点的数组和关系的数组 )。
E
D G
CA
B
G2
F
HC
E F
BA
D
G1
C
A
D
E
B
F
G3
3
7
1
8
7
455 6
6
D5
9
6
7.2 对图 G3完成以下操作：
1.从顶点 A出发,求 G3的一棵 BFS生成树,画出该 BFS生成树；
2.从顶点 B出发,求 G3的一棵 DFS生成树,画出该 DFS生成树；
3.从顶点 A出发,用 Prim算法求 G3的一棵最小生成树,写出求解过程；
4.用 Kruskal算法求 G3的一棵最小生成树,写出求解过程 。
C
A
D
E
B
F
G3
3
7
1
8
7
455 6
6
D5
9
6