答：StrLength (s)=14, StrLength (t)=4, SubStr( s，8，7)=” STUDENT”, SubStr(t，2，1)=”O”, StrIndex(s,“A”)=3, StrIndex (s，t)=0, StrRep(s，“STUDENT”，q)=” I AM A WORKER”,
7. 简述下列每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变量的值。
答：空串：不含任何字符；空格串：所含字符都是空格。
串变量和串常量:串常量在程序的执行过程中只能引用不能改变；串变量的值在程序执行过程中是可以改变和重新赋值的。
主串与子串：子串是主串的一个子集。
串变量的名字与串变量的值:串变量的名字表示串值的标识符。
8. 设有二维数组A(6×8)，每个元素占6个字节存储，顺序存放，A的起地址为1000，计算： (1)数组A的体积(即存储量)； (2)数组的最后一个元素A的起地址； (3)按行优先存放时，元素A1,4的起地址；
(4)按列优先存放时，元素A4,7的起地址。 (1)6*8*6=288 (2)1000+47*6=1282 (3)1000+(8+4)*8=1096 (4)1000+(6*7+4)*8=1368
9. 分别画出含三个结点的无序树与二叉树的所有不同形态。 答：无序树形态如下：
二叉树形态如下：
10. 分别写出图1中所示二叉树的先序遍历、中序遍历、后序遍历的结点访问序列。
答：先序遍历序列:ABDEHICFJG 中序遍历序列:DBHEIAFJCG 后序遍历序列:DHIEBJFGCA
11. 试找出分别满足下列条件的所有二叉树。 (1) 先序序列与中序序列相同。 (2) 后序序列与中序序列相同。 (3) 先序序列与后序序列相同。
答：(1) 先序序列和中序序列相同：空树或缺左子树的单支树； (2) 后序序列和中序序列相同：空树或缺右子树的单支树； (3) 先序序列和后序序列相同：空树或只有根结点的二叉树。
12. 已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，试画出这棵二叉树。 答：这棵二叉树为:
13. 分别写出图2中所示二叉树的先序遍历、中序遍历、后序遍历的结点访问序列。
答：先序遍历序列:ABDGCEHF 中序遍历序列:DGBAEHCF 后序遍历序列:GDBHEFCA
14. 给定权值(7,18,3,32,5,26,12,8)，构造的哈夫曼树。 答：哈夫曼树为:
15. 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为7,19,2,6,32,3,21,10，试为这8个设计哈夫曼编码。 答：哈夫曼树为:
在上述哈夫曼树的每个左分支上标以0，右分支上标以1，并设这8个字母分别为A、B、C、D、E、F、G和H，则它们的哈夫曼树为分别为:
A：0000 B：10 C：00110 D：0010 E：01 F：00111 G：11 H：0001
16. 画出无向图G1的邻接矩阵和邻接表示意图，并写出每个顶点的度。 答：（1）邻接矩阵:
（2）邻接链表：
（3）每个顶点的度：
顶点 度
V1 3 V2 3 V3 2 V4 3 V5 3
17. 画出有向图G2的邻接矩阵、邻接表和逆邻接表示意图，并写出每个顶点的入度和出度。 答：（1）邻接链表：
（2）逆邻接链表：
（3） 顶点 入度 出度 V1 3 0 V2 2 2 V3 1 2 V4 1 3 V5 2 1 V6 2 3
18. 对应图G3，写出从v1出必的深度优先遍历序列和广度优先遍历序列各三个。
答：深度优先查找遍历序列：V1 V2 V3 V4 V5; V1 V3 V5 V4 V2; V1 V4 V3 V5 V2 广度优先查找遍历序列：V1 V2 V3 V4 V5; V1 V3 V2 V4 V5; V1 V4 V3 V2 V5
19. 何谓二叉排序树?
答：一棵二叉排序树(又称二叉查找树)或者是一棵空树，或者是一棵同时满足下列条件的二叉树： (1)若它的左子树不空，则左子树上所有结点的键值均小于它根结点键值。 (2)若它的右子树不空，则右子树上所有结点的键值均大于它根结点键值。 (3)它的左、右子树也分别为二叉排序树。
20. 顺序查找时间为O(n)，二分查找时间为O(log2n)，散列查找时间为O(1)，为什么有高效率的查找方法而不放弃低效率的方法?
答：衡量算法的标准有很多，时间复杂度只是其中之一。尽管有些算法时间性能很好，但是其他方面可能就存在着不足。比如散列查找的时间性能很优越，但是需要关注如何合理地构造散列函数问题，而且总存在着冲突等现象，为了解决冲突，还得采用其他方法。
二分查找也是有代价的，因为事先必须对整个查找区间进行排序，而排序也是费时的，所以常应用于频繁查找的场合。对于顺序查找，尽管效率不高，但却比较简单，常用于查找范围较小或偶而进行查找的情况。
21. 简述多重散列法解决冲突的基本思想。
答：此法要求设立多个散列函数Hi，i=1，…，k。当给定值K与闭散列表中的某个键值是相对于某个散列函数Hi的同义词因而发生冲突时，继续计算该给定值K在下一个散列函数Hi+1下的散列地址，直到不再产生冲突为止。
22. 简述公共溢出区法解决冲突的基本思想。
答：散列表由两个一维数组组成。一个称为基本表，另一个称为溢出表。插入首先在基本表上进行；假如发生冲突，则将信息存人溢出表。
23. 在结点个数为n(n>1)的各棵树中，高度最小的树的高度是多少?它有多少个叶结点?多少个分支结点?高度最大的树的高度是多少?它有多少个叶结点?多少个分支结点?
答：结点个数为n时，高度最小的树的高度为1，有两层，它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-l，有n层，它有1个叶结点，n-1个分支结点。
24. 什么是内部排序?什么是排序方法的稳定性?
答：假定给定含有n个记录的文件(r1，r2，…，rn)，其相应的关键字为(k1，k2，…，kn)，则排序就是确定文件的一个序列r1，r2，…，rn，使得k1≤k2≤…≤kn，从而使得文件中n个记录按其对应关键字有序排列。如果整个排序过程在内存中进行，则排序叫内部排序。
假设在待排序的文件中存在两个或两个以上的记录具有相同的关键字，若采用某种排序方法后，使得这些具有相同关键字的记录在排序前后相对次序依然保持不变，则认为该排序方法是稳定的，否则就认为排序方法是不稳定的。
五、分析题。(每小题4分，共8分) 1. 分析下面语句段执行的时间复杂度。 (1) for(i＝1；i<＝n；i++) for(j＝1；j<＝n；j++) s++；
(2) for(i＝1；i<＝n；i++) for(j＝i；j<＝n；j++)
s++；
(3) for(i＝1；i<＝n；i++)
for(j＝1；j<＝i；j++) s++； (4) i＝1； k＝0；
while(i<＝n-1){
k+＝10*i； i++； }
(5) for (i＝1；i<＝n；i++) for (j＝1；j<＝i ；j++) for (k＝1；k<＝j；k++) x=x+1；
(1) Ο(n2
) (2) Ο(n2
) (3) Ο(n2
) (4) Ο(n-1) (5) 2. 写出下列程序段的运行结果(栈中的元素类型是char)： main( )
{ SeqStack s，*p;； char x，y； p=&s;
Init_Queue(p);
x= ‘c’； y= ‘k’；
push (p，x)； push (p，’a’)；push (p，y); x=pop (p);
push (p，’t’); push (p，x)； x=pop (p)； push (p，’s’);
while (!Empty_SeqStack(p)) { y=pop (p)；
printf(“％c”，y)； }
printf(“％c＼n”，x)； } 答：stack
3. 写出下列程序段的运行结果(队列中的元素类型是char)：main( )
{ SeQueue a, *q;
Ο(n3
) char x，y；
q=&a； x=’e’； y=’c’; Init_Queue(q);
In_Queue(q，’h’); In_Queue(q, ’r’); In_Queue(q, y); x=Out_Queue (q)； In_Queue(q，x)； x= Out_Queue (q); In_Queue(q，’a’ )； while (!Empty_SeqStack(q)) { y= Out_Queue(q)； printf(“%c”，y)； }
printf(“%C\\n”，x)； }
答：char