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个队列的头指针和长度域。请在空缺处填入合适的内容，实现第i个循环队列的入队操作。 int EnQueue(Queue2*Q,int i,DataType x)
{//若第i个队列不满，则元素x入队列，并返回1，否则返回0
if(i<0||i>1)return 0; if( (1) ) return 0;
Q->data[ (2) ]=x; Q->length[ (3) ]++; return 1; } 解:
(1) (Q->front[i]+Q->length[i]%Maxsize==Q->front[(i+1)%2] (2) (Q->front[i]+->length[i]%Maxsize (3) I
31.某二叉树的线索链表存储结构如图(b)所示，其中p为指向根结点的指针，图(a)为结点结构。
阅读下列算法，并回答问题：
(1)写出执行函数调用f(p)的输出结果； (2)简述函数f的功能。 void f(BinThrTree t) {
while(t) {
printf(t->data); if(t->lchild) t=t->lchild; else
t=t->rchild; } }
答案（1）ABDFCEGH (2) 先根遍历
32.下列函数FindCycle(G,i)的功能是，对一个采用邻接表作存储结构的有向图G，利用深度优先搜索策略寻找一条经过顶点vi的简单回路。数组cycle_path用于保存搜索过程中形成的回路，cycle_path[k]=j(j≥0)表示在回路中顶点vk的下一个顶点是vj。 请在空缺处填入合适的内容，使其成为一个完整的算法。 vertex firstedge
已知邻接表的顶点表结点结构为： adjvex next
边表结点EdgeNode结构为： int cycle_path[MaxNum];
int FindCycle(ALGraph*G,int i)
{//若回路存在，则返回1，否则返回0 int j;
for(j=0;j<G->n;j++)cycle_path[j]=-1; return DFSPath(G,i,i); }
int DFSPath(ALGraph*G,int j,int i) {
EdgeNode *p; int cycled=0;
for(p=G->adjlist[j].firstedge;p&&!cycled;p=p->next) {
cycle_path[j]=p->adjvex;
if( (1 ) )cycled=1;//已找到回路 else
if(cycle_path[p->adjvex]==-1)cycled= (2) ; }
return (3) } (1) (2) (3)
32题答案： （1）p->adjvex==i
(2)DFSpath(G,p->adjvex,i) (3)cycled
33.阅读下列函数algo,并回答问题。
(1)假设整型数组A[1..8]中的元素依次为(3，8，9，1，7，4，2，6)。执行函数调用algo(A,8)时，外层while的循环体执行多少次?函数的返回值是多少? (2)简述函数algo(L,n)的功能。 int algo(int L[],intn) {
int i=0,j,s=1,t=n; while (i!=(n+1)/2) {
int x=L[s]； i=s;j=t;
while(i<j) {
while(i<j && L[j]>=x)j--; L[i]=L[j];
while(i<j && L[i]<=x)i++; L[j]=L[i]; }
L[i]=x;
if(i<(n+1)/2)s=i+1; else t=i-1; }
if(i==0)return 0; else return L[i]; } (1) (2) (3) 33题答案：
（1）外循环执行4次，函数返回值为3。 （2）将A[1]至A[8]中不小于A[1]的元素进行递增排序，如调用algo(A,8)时最终排序结果为2 1 3 4 6 7 8 9
五、算法设计题(本大题共10分)
34.假设以带头结点的单循环链表作非递减有序线性表的存储结构。请设计一个时间复杂度为O(n)的算法，删除表中所有数值相同的多余元素，并释放结点空间。例如： (7，10，10，21，30，42，42，42，51，70) 经算法操作后变为 (7，10，21，30，42，51，70) 34题答案：
Exam4(Linklist,L) {listnode *p,*q; p=L->next; while(p!=L)
{q=p->next;
while(q&&q->data==p->data) {p->next=q->next; free(q);
q=p->next; }
p->next; } }
2003年10月全国数据结构试题 （2006-7-25 2:07:00）
1.计算机识别、存储和加工处理的对象被统称为( b ) A.数据 B.数据元素 C.数据结构 D.数据类型
2.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是( b ) A.O(1) B.O(n) C.O(nlogn) D.O(n2) 3.队和栈的主要区别是( d )
A.逻辑结构不同 B.存储结构不同
C.所包含的运算个数不同 D.限定插入和删除的位置不同 4.链栈与顺序栈相比，比较明显的优点是( d )
A.插入操作更加方便 B.删除操作更加方便 C.不会出现下溢的情况 D.不会出现上溢的情况 5.采用两类不同存储结构的字符串可分别简称为( b ) A.主串和子串 B.顺序串和链串 C.目标串和模式串 D.变量串和常量串
6.在目标串T［0..n-1］=″xwxxyxy″中，对模式串P［0..m-1］=″xy″进行子串定位操作的结果是( c )
A.0 B.2 C.3 D.5
7.已知广义表的表头为a，表尾为(b,c)，则此广义表为( b ) A.(a,(b,c)) B.(a,b,c) C.((a),b,c) D.((a,b,c))
8.二维数组A按行优先顺序存储，其中每个元素占1个存储单元。若A［1］［1］的存储地址为420，A［3］［3］的存储地址为446，则A［5］［5］的存储地址为( c ) A.470 B.471 C.472 D.473
9.二叉树中第5层上的结点个数最多为( d ) A.8 B.15 C.16 D.32 10.下列编码中属前缀码的是( a )
A.{1,01,000,001} B.{1,01,011,010} C.{0,10,110,11} D.{0,1,00,11}
11.如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是( d ) A.有向完全图 B.连通图