数据结构(1,2,3章)课后题答案

1、授课教师：耿国华 教授西北大学可视化技术研究所西北大学可视化技术研究所第一章：绪论n1.2判断题（在各题后填写判断题（在各题后填写“”或或“”）：）： （1）线性结构只能用顺序结构来存放，非线性 结构只能用非顺序结构来存放。（） （2）算法就是程序。（） （3）在高级语言（如C或 PASCAL）中，指针类型是原子类型。（）西北大学可视化技术研究所西北大学可视化技术研究所n1.3填空题：填空题： （1）变量的作用域是指 变量的有效范围 （2）抽象数据类型具有 数据抽象 、 信息隐蔽 的特点。 （3）一种抽象类型包括 数据对象 、 结构关系 和 基本操作 。西北大学可视化技术研究所西北大学可视化技

2、术研究所 （4）当需要用一个形式参数直接改变对应实参的值时，该形式参数应说明为 指针类型 。 （5）数据结构的逻辑结构分为 集合结构 、 线性结构 、 树形结构 和 图结构 四种。 （6）数据结构的存储结构分为 顺序存储结构 和 链式存储结构 两种。西北大学可视化技术研究所西北大学可视化技术研究所 （7）在线性结构、树形结构和图结构中，数据元素之间分别存在着 一对一 、 一对多 和 多对多 的联系。 （8）算法是规则的有限集合，是为解决特定问题而规定的 操作序列 。 （9）算法具有 有限性 、确定性、 可行性 、 输入 、输出五大特性。 西北大学可视化技术研究所西北大学可视化技术研究所n1.4

3、 1.4 选择题选择题 （1）若需要利用形式参数直接访问修改实参值，则应将形参说明为 A 参数。 A.指针 B.值参数西北大学可视化技术研究所西北大学可视化技术研究所 （2）执行下面的程序段的时间复杂度为 C 。 for(int i=0;im;i+) for(int j=0;jn;j+) aij=i*j; A.O(m2) B. O(n2) C. O(m*n) D. O (m+n)西北大学可视化技术研究所西北大学可视化技术研究所n(3)执行下面程序段时，语句S的执行次数为 C 。 for(int i=0;i=n;i+) for(int j=0;j=i;j+) S; A. n2 B. n2/2 C

4、. (n+1) (n+2)/2 D. n(n+1)/2西北大学可视化技术研究所西北大学可视化技术研究所n5.5.计算下列程序段中x=x+1的语句频度： for(i=1;i=n;i+) for(j=1;j=i;j+) for(k=1;k=j;k+) x=x+1; 思路:语句频度即为时间频度，拆分循环语句， 先从后两个for循环开始思考，最后循环i值。 第一步： 西北大学可视化技术研究所1(1)1 2 3 .2iji iji 西北大学可视化技术研究所n第二步:计算结果 2ni= 111(1 + i)i222nniiii22211(12.)(1 2 .)22nn 1(21)(1)1(1)()()26

5、22nnnn n32623nnn西北大学可视化技术研究所n6.6.编写算法，求一元多项式： 算法描述： void dxs(int a,int n,int x) int temp=x; /temp保存x的幂次方 int sum=0; /sum保存多项式的计算结果 int i,j,k; int bn; /bi保存多项式的每一项的带全值 for(j=0;j=n;j+) bj=1; b0=a0; /x的0次方与x的0次方的系数的乘积 b1=a1*x; /x的1次方与x的1次方的系数的乘积n西北大学可视化技术研究所西北大学可视化技术研究所 for(j=2;j=n;j+) /从x的2次方开始，到x的n次方

6、结束 for(k=2;k=j;k+) temp=temp*x; /保存x的m次方 bj=aj*temp; /x的m次方与x的m次方的系数的乘积 temp=x; for(i=0;i=n;i+)sum=sum+bi; cout多项式的值是：sumnext= P-next; A. P-next=S; b.在P结点前插入S结点的语句序列是： H. Q= P; L. P= L; I. while(P-next!=Q) P=P-next; 西北大学可视化技术研究所西北大学可视化技术研究所 E. S-next= P-next; A. P-next=S; c. 在表首插入S结点的语句序列是 F. S-next

7、= L; M. L= S; 。d. 在表尾插入S结点的语句序列是： L. P= L; J. while(P-next!=NULL) P=P-next; A. P-next=S; G. S-next= NULL; 。西北大学可视化技术研究所供选择的语句有： A. P-next=S; B. P-next= P-next-next; C. P-next= S-next; E. S-next= P-next; F. S-next= L; G. S-next= NULL; H. Q= P; I. while(P-next!=Q) P=P-next; J. while(P-next!=NULL) P=P-

8、next; K. P= Q; L. P= L; M. L= S; N. L= P;西北大学可视化技术研究所 （3）某线性表中最常用的操作是存取序号为i的元素和在最后进行插入和删除运算，则采用 D 存储方式 时间性能最好。 A双向链表 B双向循环链表 C单向循环链表 D顺序表 （4）下列选项中， D 项是链表不具有的特点。 A插入和删除运算不需要移动元素 B所需要的存储空间与线性表的长度成正比 C不必事先估计存储空间大小 D可以随机访问表中的任意元素西北大学可视化技术研究所 (5)在链表中最常用的操作是删除表中最后一个结点和在最后一个结点之后插入元素，则采用 C 最节省时间。 A. 头指针的单向

9、循环链表 B双向链表 C带尾指针的单向循环链表 D带头指针双向循环链表 (6)在线性表中最常用的操作是存取第i个元素及其前趋的值，可采用 A 存储方式。 A顺序表 B单向链表 C双向循环链表 D单向循环链表西北大学可视化技术研究所n5.写一个算法，从顺序表中删除自第i个元素开始的k个元素。 算法描述：以待移动元素下标m为中心， 计算应移入位置： for ( m= i1+k; mlast; m+) Lelem mk = Lelem m ;西北大学可视化技术研究所n8.假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表

10、C，并要求利用原表（即A表和B表的）结点空间存放表C。西北大学可视化技术研究所n 算法描述：要求利用现有的表A和B中的结点空间来建立新表C，可通过更改结点的next域来重新建立新的元素之间的线性关系。为保证新表递减有序可以利用头插法建立单链表的方法，只是新建表中的结点不用malloc，而只需要从A和B中选择合适的点插入到新表C中即可。西北大学可视化技术研究所合并两个有序的单链表算法演示 LinkList MergeLinkList(LinkList A,LinkList B) /*将递增有序的单链表A和B合并成一个递减有序的单链表C*/ Node *pa,*pb,*smaller; LinkL

11、ist C; /*将C初始置为空表，pa和pb分别指向两个单链表A和B中的第一个结点，r初值为C*/ pa=A-next; pb=B-next; C=A; C-next=NULL; /*初始化操作*/西北大学可视化技术研究所 /*当两个表中均未处理完时，比较选择将较大值结点插入到新表C中。*/ while(pa!=NULL&pb!=NULL) if(pa-datadata) smaller=pa; pa=panext; smallernext = cnext; /* 头插法头插法 */ cnext = smaller; else smaller=pb; pb=pbnext; small

12、ernext = cnext; cnext = smaller; if(pa) /*若表A未完，将表A中后续元素链到新表C表*/ smaller=pa; pa=panext; smallernext = cnext; cnext = smaller; /*否则将表B中后续元素链到新表C表尾*/ else smaller=pb; pb=pbnext; smallernext = cnext; cnext = smaller; return(C); 西北大学可视化技术研究所n10.已知有单链表表示的线性表中含有三类字符的数据元素（如字母字符，数字字符和其它字符），试编写算法来构造三个以循环链表表示

13、的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。 西北大学可视化技术研究所n 算法描述:只要新建三个头结点，然后在原来的单链表中依次查询，找到一类字符结点时，就摘下此结点链接到相应头结点指明的新链表中就可以实现题目的要求。n 算法提示： 设已建立三个带头结点的空循环链表 A,B,C.西北大学可视化技术研究所nvoid DivideList( LinkList L, LinkList A, LinkList B, LinkList C) ListNode *p=L-next, *q; ListNode *a=A, ListNode *b=B;

14、 ListNode *c=C; while ( p ) if ( p-data=a &p-datadata=A &p-datanext;/指向下一结点 else if( p-data=0 & p-datanext; b-next=q; q-next=B; b=b-next; else /分出其他字符结点 q=p; p=p-next; c-next=q; q-next=C; c=c-next; /结束西北大学可视化技术研究所第三章 限定性线性表-栈和队列n1、按书上图3.1（b）所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答 ：（1）如进站的车厢序列为123，则可能

15、得到的出站车厢序列是什么？答案：123 132 213 231 321 （2）如进站的车厢序列为123456，能否得到435612和135426的出站序列，并说明原因。（即写出以“S”表示进站，以“X”表示出站的栈操作序列）。西北大学可视化技术研究所n答案：435612不可以 原因 （1）S：1234 X：43 （2）S：5 X: 5 （3）S：6 X: 6 （4）X：21 135426 可以 原因（1）S：1 X：1 （2）S：23 X: 3 （3）S：45 X: 54 （4）X：2 （5）S：6 X: 6 西北大学可视化技术研究所n3、给出栈的两种存储结构形式名称，在这两种栈的存储结构中如

16、何判断栈空和栈满？答案：链栈和顺序栈 链栈：栈空：头指针为空：即if（head-next=NULL） 栈满：结点存储空间申请失败 顺序栈：栈空：栈下标小于零：即 if（stack-toptopMAX） 西北大学可视化技术研究所n4、按照四则运算加、减、乘、除和幂（）运算优先关系的惯例，画出对下列算术表达式求值时运算数栈和运算符栈的变化过程： A-B*C/D+E F 答案 ： 西北大学可视化技术研究所n ABC-*/=optr(*)T(1)=B*C+=optr(/)T(2)=T(1)/DA-DT(1)/AT(2)-T(3)FE+=optr(-)T(3)=A-T(2)+右边界右边界#=optr()

17、T(4)=EFT(3)T(4)+右边界右边界#rear%MAXSIZE=q-front &tag=1) /*队列已满 return(FALSE); q-elementq-rear = x; /*装元素*/ q-rear=(q-rear+1)%MAXSIZE; if(q-rear%MAXSIZE=q-front)/*判断并设置 标志位tag*/ tag=1;return(true);西北大学可视化技术研究所出队操作：Int deletequeue(seqqueue *q,element *x) if(q-front=q-rear & tag=0)return(FALSE); *x

18、=q-elementq-front; q-front=(q-front+1)%MAXSIZE; if(q-front=q-rear) tag=0; /*设标志tag*/ return（true）；西北大学可视化技术研究所9、设4个元素1、2、3、4依次进栈，而出栈操作可随时进行（进出栈可任意交错进行，但要保证进栈不破环1、2、3、4的相对次序，）请写出所有不可能的和可能的出栈次序。 所有可能的：1234 1243 1324 1432 2134 2143 2314 2341 2431 3214 3241 3421 4321 所有不可能的： 1342 1423 2413 3124 3142 3412 4312 4213 4231 4