第1和2章习题及答案.doc

3数据结构第1章 绪论 第2章 线性表 习题课答案一、选择题1 在下面的程序段中，对x的赋值语句的频度为（ C ）FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1;A O(2n) BO(n) CO(n2) DO(log2n) 2 一个算法应该是（ B ）。 A程序 B问题求解步骤的描述 C要满足五个基本特性 DA和C.3 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。A单链表 B仅有头指针的单循环链表 C双链表 D仅有尾指针的单循环链表4 链表不具有的特点是（ B ） A插入、删除不需要移动元素 B可随机访问任一元素 C不必事先估计存储空间 D所需空间与线性长度成正比5 完成在双循环链表结点p之后插入s的操作是（ D ）； A p-next=s ; s-priou=p; p-next-priou=s ; s-next=p-next;B p-next-priou=s; p-next=s; s-priou=p; s-next=p-next;C s-priou=p; s-next=p-next; p-next=s; p-next-priou=s ;D s-priou=p; s-next=p-next; p-next-priou=s ; p-next=s;二、判断题1 数据元素是数据的最小单位。( )2 数据的物理结构是指数据在计算机内的实际存储形式。( )3 对任何数据结构链式存储结构一定优于顺序存储结构。( )4 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( )三、填空1 一个数据结构在计算机中 表示（又称映像） 称为存储结构。2 在一个长度为n的顺序表中第i个元素（1=inext-next=L_4 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。void reverse(linklist h) /* h为附加头结点指针； */ linklist p,q; p=h-next; h-next=NULL;while(1)_ p!=null 链表未到尾就一直作_) q=p; p=p-next; q-next=h-next; h-next=(2)_ q将当前结点作为头结点后的第一元素结点插入_; 5 在单链表中设置头结点的作用是_主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表头指针不变。_6 设单链表中某指针p所指结点（即p结点）的数据域为data，链指针域为next，请写出在p结点之前插入s结点的操作： s-next=p-next;p-next=s;x=p-data;p-data=s-data;s-data=x;p=s; 三、算法设计题1 设有带头结点的单链表L，编程对表中任一值只保留一个结点，删除其余值相同的结点。 Void delete(linklist &L) linklist p,q ,tmp; P=L-next; While( p-next != NuLL) q=p; While ( q - next != NuLL) if ( q-next-data = p-data ) tmp = q-next ; q-next= tmp-next;free(tmp); /if Else q=q-next; /else /内层while p=p-next; /外层while /delete2 编写一个算法来交换单链表中指针P所指结点与其后继结点，HEAD是该链表的头指针，P指向该链表中某一结点。 题目分析 单链表中查找任何结点，都必须从头指针开始。本题要求将指针p所指结点与其后继结点交换，这不仅要求知道p结点，还应知道p的前驱结点。这样才能在p与其后继结点交换后，由原p结点的前驱来指向原p结点的后继结点。 LinkedList Exchange（LinkedList HEAD，p） HEAD是单链表头结点的指针，p是链表中的一个结点。本算法将p所指结点与其后继结点交换。q=head-next； q是工作指针，指向链表中当前待处理结点。 pre=head； pre是前驱结点指针，指向q的前驱。 while（q!=null & q!=p）pre=q；q=q-next； 未找到p结点，后移指针。 if（p-next=null）printf（“p无后继结点n”）; p是链表中最后一个结点，无后继。 else处理p和后继结点交换 q=p-next； 暂存p的后继。 pre-next=q； p前驱结点的后继指向p的后继。 p-next=q-next；p的后继指向原p后继的后继。 q-next=p ；原p后继的后继指针指向p。 算法结束。3 假设一个单循环链表，其结点含有三个域pre、data、link。其中data为数据域；pre为指针域，它的值为空指针（NIL）；link为指针域，它指向后继结点。请设计算法，将此表改成双向循环链表。void StoDouble（DuLinkList &la）la是结点含有pre，data，link三个域的单循环链表。其中data为数据域,pre为空指针域，link是指向后继的指针域。本算法将其改造成双向循环链表。while（la-link-pre=null）la-link-pre=la；