深度优先遍历序列为：abdce 广度优先遍历序列为：abedc 29．（１）对关键字35、20、33和48进行查找的比较次数为３、２、１、１； （２）平均查找长度ASL?3?2?1?1?29?
55四、算法阅读题（本大题共4小题，每小题5分，共20分）
30． ①S1=S1－>next ②s2=s2－>next
③s2(或s2!=NULL或s2&&!s1) ④s1(或s1!=NULL或s1&&!s2) ⑤return 0
31.（1）查询链表的尾结点
（2）将第一个结点链接到链表的尾部，作为新的尾结点 （3）返回的线性表为（a2,a3,?,an,a1） 32. ①(i＋1)%2(或1－i) ②Q－>rear[i]
③(Q－>rear[i]＋)%Maxsize 33.(1)Leafhead
F H G D ∧ （2）中序遍历二叉树，按遍历序列中叶子结点数据域的值构建一个以Leafhead为头
指针的逆序单链表（或按二叉树中叶子结点数据自右至左链接成一个链表）。
五、算法设计题（本题共10分） 34．（1）该函数的功能是：调整整数数组a[]中的元素并返回分界值i，使所有＜x的元
素均落在a[1..i]上，使所有≥x的元素均落在a[i＋1..h]上。
（2）int f(int b[],int n) 或 int f(int b[],int n) { {
int p,q； int p,q；
p=arrange(b,0,n－1,0)； p=arrange(b,0,n－1,1)； q= arrange(b,p+1,n－1,1)； q= arrange(b,0,p,0)； return q－p； return p－q； } }
2003.1数据结构试题
一、单项选择题(本大题共15小题，每小题2分，共30分。在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号内) 1.下面程序段的时间复杂度是( D ) for(i=0;i<n;i++)
for(j=1;j<m;j++)
A[i][j]=0；
A.O(n) B.O(m+n+1) C.O(m+n) D.O(m*n)
2.在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是( B ) A.p=p->next; B.p->next=p->next->next; C.p->next=p; D.p=p->next->next;
3.在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next= head,则( D )
A.p指向头结点 B.p指向尾结点
C.*p的直接后继是头结点 D.*P的直接后继是尾结点 4.判定“带头结点的链队列为空”的条件是( C ) A.Q.front==NULL B.Q.rear==NULL C.Q.front==Q.rear D.Q.front!=Q.rear
5.设有两个串T和P，求P在T中首次出现的位置的串运算称作( D ) A.联接 B.求子串 C.字符定位 D.子串定位 6.广义表A=(a,(b),(),(c,d,e))的长度为( A ) A.4 B.5 C.6 D.7
7.一棵含18个结点的二叉树的高度至少为( C ) A.3 B.4 C.5 D.6
8.已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为( D ) A.DEBAFC B.DEFBCA C.DEBCFA D.DEBFCA 9.无向图中一个顶点的度是指图中( B )
A.通过该顶点的简单路径数 B.与该顶点相邻接的顶点数 C.通过该顶点的回路数 D.与该顶点连通的顶点数
10.已知一个图如下所示，从顶点a出发进行广度优先遍历可能得到的序列为( C )
A.a c e f b d B.a c b d f e C.a c b d e f D.a c d b f e
11.在下列排序方法中，平均时间性能为O(nlogn)且空间性能最好的是( B ) A.快速排序 B.堆排序 C.归并排序 D.基数排序
12.已知一组关键字为{25,48,36,72,79,82,23,40,16,35}，其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是( A ) A.{25,36,48,72,23,40,79,82,16,35} B.{25,36,48,72,16,23,40,79,82,35} C.{25,36,48,72,16,23,35,40,79,82} D.{16,23,25,35,36,40,48,72,79,82} 13.设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为( B )
A.21 B.23 C.41 D.62
14.索引非顺序文件的特点是( A )
A.主文件无序，索引表有序 B.主文件有序，索引表无序 C.主文件有序，索引表有序 D.主文件无序，索引表无序 15.倒排文件的主要优点是( C )
A.便于进行插入和删除运算 B.便于进行文件的恢复 C.便于进行多关键字查询 D.节省存储空间
二、填空题(本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分) 16.抽象数据类型的特点是将___数据_____和____运算____封装在一起，从而现实信息隐藏。 17.从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需___前移___一个位置。 18.在队列中，允许进行插入操作的一端称为____队尾____，允许进行删除操作的一端称为___队头___。
19.如图两个栈共享一个向量空间，top1和top2分别为指向两个栈顶元素的指针，则“栈满”
的判定条件是__top1=top2-1____。
20.设S1="good",S2=" ",S3="book"，则S1，S2和S3依次联接后的结果是_ good book__。
21.假设三维数组A[10][9][8]按行优先顺序存储，若每个元素占3个存储单元，且首地址为100，则元素A[9][8][7]的存储地址是__2257_____。
22.已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为__（(n-1)/k）*(k-1)+1_或 n - (n-1)/k__。 23.能够成功完全拓扑排序的图一定是一个__有向无环图__。
24.如果在排序前，关键字序列已接近正序或逆序，则在堆排序和快速排序两者之中，选用__堆排序__较为适当。
25.假设哈希表的表长为m，哈希函数为H(key)，若用线性探查法解决冲突，则探查地址序列的形式表达为__hi=(H(key)+I)/m___。
三、解答题(本大题共4小题，每小题5分，共20分)
26.假设通信电文使用的字符集为{a,b,c,d,e,f}，名字符在电文中出现的频度分别为：34，5，12，23，8，18，试为这6个字符设计哈夫曼编码。请先画出你所构造的哈夫曼树(要求树中左孩子结点的权值小于右孩子结点的权值)，然后分别写出每个字符对应的编码。
27.已知一个图如下所示，其顶点按a、b、c、d、e、f顺序存放在邻接表的顶点表中，请画出该图的邻接表，使得按此邻接表进行深度优先遍历时得到的顶点序列为acbefd，进行广度优先遍历时得到的顶点序列为acbdfe。
答案：
28.已知两个4×5的稀疏矩阵的三元组表分别如下： 0 1 4 16 0 1 1 32 1 2 2 18 1 2 2 －22 2 3 4 －25 2 2 5 69
3 4 2 28 3 3 4 25
4 4 2 51
请画出这两个稀疏矩阵之和的三元组表。 解:
29.从空树起，依次插入关键字40，8，90，15，62，95，12，23，56，32，构造一棵二叉排序树。
(1)画出该二叉排序树
(2)画出删去该树中元素值为90的结点之后的二叉排序树。
四、算法阅读题(本大题共4小题，每小题5分，共20分)
30.如图所示，利用同一循环向量空间实现两个队列，其类型Queue2定义如下：
typedef struct {
DataType data[MaxSize]; int front[2],length[2]; } Queue2;
对于i=0或1,front[i]和length[i]分别为第i个队列的头指针和长度域。请在空缺处填入合