1、第 1 章 绪1.1 有下列几种二元组表示的数据结构，试画出它们分别对应的图形表示，并指出它们分别属于何种结构。(1) A= ( D，R )，其中，D = a 1，a 2，a 3，a 4 ， R= (2) B= ( D，R )，其中，D = a，b，c，d，e， R= (a，b)，(b ，c)，(c，d)，(d，e)(3) C= ( D，R )，其中，D = a，b，c，d，e ，f ，g， R= (d，b)，(d ，g)，(b，a)，(b，c)，(g，e)，(e ，f)(4) K= ( D，R )，其中，D = 1，2，3，4，5，6， R= ，(1) 集合(2) 线性表 abcde(3)
2、树 (4) 图 fgabcde1.2 设 n 为正整数，求下列各程序段中的下划线语句的执行次数。(1) i=1; k=0while(i:DeleteElem( T e ) for (i=1; i:Locate ( T e ) 的时间复杂度。解：设表长为 n，等概率下，每个元素被定位的概率为：p=1/n定位成功第 i 个元素，需比较 i 次 21)(11)( nnfii3.对于有头结点的单链表，分别写出定位成功时，实现下列定位语句序列。(1) 定位到第 i 个结点 ai； p=head; j=0;while ( p j+;(2) 定位到第 i 个结点的前驱 ai-1； p=head; j=0;w
3、hile ( p j+;(3) 定位到尾结点； p=head; while ( p -next ) p=p-next; (4) 定位到尾结点的前驱。 p=head; while ( p-next-next ) p=p-next;4.描述一下三个概念的区别：头指针，头结点，首元结点。并给予图示。头指针：是一个指针变量，里面存储的是链表中首结点的地址，并以此来标识一个链表。头结点：附加在第一个元素结点之前的一个结点，头指针指向头结点。首元结点：指链表中的第一个元素结点。 头 结 点 a12. an 首 (元 )结 点 尾 (元 )结 点头 指 针5. 对于无头结点单链表，给出删除第 i 个结点的算
4、法描述。template T LinkList:Delete(int i)template T LinkList:Delete(int i) / 在单链表上删除第 i 个数据元素if ( head=NULL) throw “表空!”; / 空表，不能删else if ( i=1) / 删除第 1 个元素p=Head; x=p-data; / 保存被删元素值Head= p-next ; delete p ; else / 元素定位到第 ai-1 p=Head; j=1 ; / 定位查找起始位置while p-next j+ ; if ( !p-next | ji-1 ); / 定位失败throw
5、 “删除位置不合理”;else / 定位成功，进行结点删除q=p-next;x=pdata;p-next=q-next; delete q;retrun x; / 返回被删除元素值/#6. 用教材定义的顺序表的基本操作实现下列操作：template int DeleteElem(SqList L, T e)#include “SqList.h“template int DeleteElem(SqList L, T e) /i = L.LocateElem(e) ; / 按值查找if (!i) / 未找到return 0; else / 找到delete (i) ; / 删除被找到的元素7. 已
6、知 L 是有表头结点的单链表，且 P 结点既不是首元结点，也不是尾结点，试写出实现下列功能的语句序列。(1) 在 P 结点后插入 S 结点；(2) 在 P 结点前插入 S 结点；(3) 在表首插入 S 结点；(4) 在表尾插入 S 结点.【解】(1) s-next=p-next; p-next=s;(2) q=L;while( q-next!=p) q=q-next;s-next=p 或 q-next ; q -next=s;(3) s-next=L-next; L-next=s;(3) q=L;while( q-next!=NULL) q=q-next;s-next= q-next ; q-
7、next=s;上机练习题要求：给出问题分析、算法描述、源程序及运行截图，在线提交。编程实现：删除单链表中值为 e 的元素。第 3 章 栈与队列1. 铁路进行列车调度时, 常把站台设计成栈式结构的站台，如右图所示。试问：若进站的六辆列车顺序如上所述, 那么是否能够得到325641 和 154623 的出站序列, 如果不能, 说明为什么不能; 如果能, 说明如何得到(即写出“ 进栈“或“ 出栈“ 的序列)。解：325641 可以154623 不可以。1234562. 简述以下算法的功能（栈的元素类型为 int ）。(1) status algo_1( SqStack S ) int i, n, A
8、 255;n=0;while (!S.StackEmpty() ) n+; An= S.Pop(); for ( i=1; i S; / 建立一个栈while( N!=0) / N 非零i=N%B ; / 从低到高 ，依次求得各位N=N/B;S.push(i); / 各位入栈 while ( !S.StackEmpty() / 栈不空 i= S.pop();If (i9) i=A+10-i;cout s; / 创建一个栈char *p=exp; / 工作指针 p 指向表达式首while ( *p!=) / 不是表达式结束符switch(p) case (: /左括号，入栈s.push(ch);
9、 break;case ) / 右括号if (s.StackEmpty() return 0; / 栈空，不匹配，多右括号else s.Pop(); break; / 左括号出栈/switchp+; / 取表达式下一个字符 / whileif (!s.StackEmpty() / 表达式结束，栈不空return 0 ; /不匹配，多左括号elsereturn 1 ; / 匹配 /#5. 简述栈和队列的逻辑特点，各举一个应用实例。6. 写出下列中缀表达式的后缀表达式。(1)-A+B-C+D(2)(A+B)*D+E/(F+A*D)+C(3) Awhile( i1) cout1) courj;recurision(j-1);
