当前位置:首页 >> 理学 >> 《数据结构》第二章习题参考答案 殷人昆版

《数据结构》第二章习题参考答案 殷人昆版


《数据结构》第二章习题参考答案
一、 判断题 (在正确说法的题后括号中打“√” 错误说法的题后括号中打“×” , ) 1、顺序存储方式插入和删除时效率太低,因此它不如链式存储方式好。( × ) 2、链表中的头结点仅起到标识的作用。( × ) 3、所谓静态链表就是一直不发生变化的链表。( × ) 4、线性表的特点是每个元素都有一个前驱和一个后继。( × ) 5、在顺序表中,逻辑上相邻的元素在物理位置上不一定相邻。 × ) ( 6、线性表就是顺序存储的表。( × ) 7、课本 P84 2.4 题 (1)√(2)×(3)×(4)×(5)√(6)×(7)×(8)√ (9)×(10)×(11)√(12)√

二、单项选择题 1、下面关于线性表的叙述中,错误的是哪一个?( B ) A.线性表采用顺序存储,必须占用一片连续的存储单元。 B.线性表采用顺序存储,便于进行插入和删除操作。 C.线性表采用链接存储,不必占用一片连续的存储单元。 D.线性表采用链接存储,便于插入和删除操作。 2、链表不具有的特点是( B ) A.插入、删除不需要移动元素 B.可随机访问任一元素 C.不必事先估计存储空间 D.所需空间与线性长度成正比 3、(1) 静态链表既有顺序存储的优点,又有动态链表的优点。所以,它存取表 中第 i 个元素的时间与 i 无关。 (2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了,以后不能增 加。 (3) 静态链表与动态链表在元素的插入、删除上类似,不需做元素的移动。 以上错误的是( B ) A. (1)(2) , B. (1) C. (1)(2) , ,(3) D.(2) 4、在单链表指针为 p 的结点之后插入指针为 s 的结点,正确的操作是( B ) A.p->link =s; s-> link =p-> link; B.s-> link =p-> link; p-> link =s; C.p-> link =s; p-> link =s-> link; D.p-> link =s-> link; p-> link =s; 5、 若某线性表最常用的操作是取任一指定序号的元素及其前驱, 则利用 ( C ) 存储方式最节省时间。 A.单链表 B.双链表 C.顺序表 D.带头结点的双循环链表 6、 对于顺序存储的线性表, 访问结点和增加、 删除结点的时间复杂度为 ( C ) 。 A.O(n),O(n) B. O(n),O(1) C. O(1),O(n) D. O(1),O(1) 7、在一个以 h 为头的单循环链中,p 指针指向链尾的条件是( A ) A. p->next=h B. p->next=NULL C. p->next->next=h D. p->data=-1

三、填空题

1、当线性表的元素总数基本稳定,且很少进行插入和删除操作,但要求以最快 的速度存取线性表中的元素时,应采用___顺序____存储结构。 2、线性表 L=(a1,a2,?,an)用数组表示,假定删除表中任一元素的概率相同, 则删除一个元素平均需要移动元素的个数是__(n-1)/2______。 3、在单链表中设置头结点的作用是___可以使链表的操作统一、编程简洁___。 4、一个头指针为 head 的带头结点的单链表为空表的条件是:_head->link ==NULL 。 5.在一个长度为 n 的顺序表中第 i 个元素(1<=i<=n)之前插入一个元素时,需 向后移动____n-i+1___个元素。 6、对于一个具有 n 个结点的单链表,在已知的结点*p 后插入一个新结点的时间 复杂度为__O(1)__,在给定值为 x 的结点后插入一个新结点的时间复杂度为 __O(n)___。 四、综合题 1、线性表可用顺序表或链表存储。问: (1)两种存储表示各有哪些主要优缺点? (2)如果要求对 n 个表长动态变化的表进行处理,表的总数可能也发生改变, 在此情况下,应选用哪种存储表示?为什么? 参考解答: (1)顺序存储时,逻辑上相邻的数据元素,其物理存放地址也相邻。顺序存储的 优点是存储密度大,存储空间利用率高,可实现随机存取;缺点是插入或删除元 素时不方便。 链式存储时,相邻数据元素可随意存放,但所占存储空间分两部分,一部分 存放结点值, 另一部分存放表示结点间关系的指针。链式存储的优点是插入或删 除元素时很方便,使用灵活;缺点是存储密度小,存储空间利用率低,只能顺序 存取。 (2)宜选用链式存储结构,有利于高效进行动态内存开辟和插入、删除操作。 2、试述头结点,首元结点,头指针这三个概念的区别。 参考解答: 在线性表的链式存储结构中,头指针指链表的指针,若链表有头结点则是链表的 头结点的指针,头指针具有标识作用,故常用头指针冠以链表的名字。头结点是 为了操作的统一、方便而设立的,放在第一元素结点之前,其数据域一般无意义 (也可存放链表的长度、用做监视哨等),有头结点后,对在第一元素结点前插 入结点和删除第一结点, 其操作与对其它结点的操作统一了。而且无论链表是否 为空,头指针均不为空。首元结点也就是第一元素结点,它是头结点后边的第一 个结点。 3、课本 P83 2.3 题 参考解答:64 , 63 4、课本 P85 2.10 题 参考解答:

(1)
//删除最小元素并返回其值 x,空出最小元素的位置用最后一个元素填补 void SeqList<T>::DelMin(T& x){ if(IsEmpty()){cerr<<”表为空!”<<endl;exit(1);} int len = Length(); T temp, val; GetData(1, temp); for(int i=1;i<=len;i++){ GetData(i,val); if(val < temp) temp=val; } x=temp; int pos = Search(temp); GetData(len,val); SetData(pos,val); Remove(len,val); } 其他解答略……

5、课本 P85 2.14 题 参考解答:

(1)template <class T>
LinkNode<T>* List<T>::Locate(int i) //返回第 i 个元素的地址 { if(i < 1 || i>Length()) return NULL; //i 不合理,返回空指针 LinkNode<T>* p = first->link; int k = 1; while(p!= NULL && k < i)//扫描直到链尾,找第 i 个结点 { p = p->link; k++; } return p; }

(4)template <class T>
void List<T>::Create(T* a,int n) { LinkNode<T>* p = first; for(int i = 0;i<n;i++) {

if(i==0) first->link = new LinkNode<T>(a[i]); else p->link = new LinkNode<T>(a[i]); p = p->link; } }

(5)template <class T>
void List<T>::tidyup(){ LinkNode<T>* p = first->link,*q; while(p->link!= NULL) { if(p->data!=p->link->data) p = p->link; else{ q = p->link; p->link = q->link; delete q; } } } 其他解答略……

6、课本 P86
参考解答:

2.17 题

void InverseList(ListNode* h){ ListNode* pr=NULL, *p = h->link; while(p!=NULL){ h->link = pr; pr = h; h = p; p = p->link; } }

7、课本 P86 2.22 题 参考解答:
void List<T> :: DelRange(T min, T max){ LinkNode *p = first; while(p->link != NULL) { linkNode * q = p->link; if(q->data>min&&q->data<max){ p->link = q->link; delete q;

} p = p->link; } }


更多相关文档:

《数据结构》第二章习题参考答案 殷人昆版.doc

《数据结构》第二章习题参考答案 殷人昆版 - 《数据结构》第二章习题参考答案

数据结构第二版_主编殷人昆课后答案_图文.ppt

数据结构第二版_主编殷人昆课后答案 - 数据结构 ? 第一单元课后参考答案 1

殷人昆《数据结构》习题答案_图文.pdf

殷人昆《数据结构》习题答案_其它课程_小学教育_教育专区。殷人昆《数据结构》习题答案,殷人昆 数据结构习题精解 605,计算机数据结构习题 殷人昆,数据结构第二版殷人昆...

《数据结构》第三章习题参考答案 殷人昆版.doc

《数据结构》第章习题参考答案 殷人昆版 - , 《数据结构》第章习题参考答案 一、 判断题 (在正确说法的题后括号中打“√” 错误说法的题后括号中打“×...

数据结构第二版 主编殷人昆课后答案_图文.ppt

数据结构第二版 主编殷人昆课后答案 - 数据结构 ? 第一单元课后参考答案 1

数据结构第二版_主编殷人昆课后答案课件._图文.ppt

数据结构第二版_主编殷人昆课后答案课件. - 数据结构 ? 第一单元课后参考答案 1 一、单选题 1. 一个数...

《数据结构》课后习题答案(第2版).doc

《数据结构》课后习题答案(第2版) - 第一章 1 填空题 (1)数据元素 (2

数据结构第二章参考答案.doc

数据结构第二章参考答案_工学_高等教育_教育专区。习题 2 1. 填空题 (1)

数据结构(C语言版)习题及答案第二章.doc

数据结构(C语言版)习题及答案第二章_理学_高等教育_教育专区。数据结构(C语言版)习题及答案 习题2.1 选择题 1、线性表的顺序存储结构是一种( A )的存储结构...

数据结构课后习题及解析第二章.doc

数据结构课后习题及解析第二章 - 第二章习题 1. 描述以下三个概念的区别:头指

数据结构(C语言版)第2版习题答案严蔚敏.doc

数据结构(C语言版)第2版习题答案严蔚敏_计算机软件及应用_IT/计算机_专业

数据结构习题及参考答案.doc

数据结构习题及参考答案_信息与通信_工程科技_专业资料。习题 1 一、单项选择题 1. 数据结构是指( )。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D....

1.严蔚敏版《数据结构》习题集及参考答案.doc

严蔚敏版《数据结构(C 语言版) 》习题集以及参考答案第1章 绪论 1.1 简述

数据结构(C语言版)课后习题参考答案_图文.pdf

数据结构(C语言版)课后习题参考答案 - 数据结构 秦锋 2011年3月第1版

数据结构(C语言版)(第2版)课后习题答案.doc

数据结构(C语言版)(第2版)课后习题答案_计算机软件应用_IT/计算机_专业资料。数据结构(C语言版)(第2版)严蔚敏 人民邮电大学 课后习题答案 ...

陈慧南版数据结构课后习题7参考答案.doc

陈慧南版数据结构课后习题7参考答案 - 7.1 7.3 7.8 以下列序列为输入,从空树开始构造 AVL 搜索树。 (1)A,Z,B,Y,C,X (2)A,V,L,T,R,E,I,S,O...

数据结构(c语言版)课后习题答案完整版.doc

数据结构(c语言版)课后习题答案完整版 - 第1章 绪论 5.选择题:CCBDCA 6.试分析下面各程序段时间复杂度。 (1)O(1) (2)O(m*n) (3)O(n2) (4)O...

数据结构课后习题答案.doc

数据结构课后习题答案 - 第 1 章绪论 1 .简述下列概念:数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结 构、抽象数据类型。 答案: 数据:是客观...

数据结构习题解析-面向对象方法和C 语言描述-殷人昆.doc

数据结构习题解析-面向对象方法和C 语言描述-殷人昆 - 第 1 章 绪论 1-

严蔚敏版数据结构习题及参考答案.doc

严蔚敏版数据结构习题及参考答案 数据结构详细解析数据结构详细解析隐藏>> 习题1 一、单项选择题 A1. 数据结构是指( )。 A.数据元素的组织形式 B.数据类型 C....

更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com