第二章 顺序表、链表(答案).doc

一、选择1线形表若采用链式存储结构时，要求内存中可用存储单元的地址（ D ）A必须是连续的 B.部分地址必须是连续的C一定是不连续的 D.连续或不连续都可以2线性表是具有n个（ C ）的有限序列（n0）。 A表元素 B字符 C数据元素 D数据项 E信息项3若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A ）存储方式最节省时间。A顺序表 B双链表 C带头结点的双循环链表 D单循环链表4某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( D )存储方式最节省运算时间。A单链表 B.双链表 C.单循环链表 D.带头结点的双循环链表5. 链表不具备的特点是（ A ）A. 可随机访问任一结点 B. 插入删除不需要移动元素C. 不必事先估计存储空间 D. 所需空间与其长度成正比6.带头结点的单链表head为空的判定条件是（ C ）.A. head=NULL B. Head-next=NULLC. head-next=head D.head!=NULL7. 如果最常用的操作是取第i个结点及其前驱,则采用（ D ）存储方式最节省时间. A. 单链表 B. 静态链表 单循环链表 D. 顺序表8. 在一个长度为n(n1)的单元链表上,设有头和尾两个指针,执行（ B ）操作与链表的长度有关. A. 删除单链表中的第一个元素 B. 删除单链表中的最后一个元素 C. 在单链表第一个元素前插入一个新元素 D. 在单链表最后一个元素后插入一个新元素9. 与单链表相比,双链表的优点之一是（ D ）. A. 插入、删除操作更简单 B. 可以进行随机访问 C. 可以省略表头指针或表尾指针 D. 顺序访问相邻结点更灵活10.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是( B )A.110 B.108 C.100 D.12011. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：（ A ）A. 访问第i个结点（1in）和求第i个结点的直接前驱（2in） B. 在第i个结点后插入一个新结点（1in）C. 删除第i个结点（1in） D. 将n个结点从小到大排序12. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ B ）个元素A. 8 B. 63.5 C. 63 D. 713 线性表在 情况下适用于使用链式结构实现。（ B ）. 需经常修改中的结点值 . 需不断对进行删除插入 . 中含有大量的结点 . 中结点结构复杂14. 非空的循环单链表head中,尾结点(由p所指向)满足（C ）.A. pnext=NULL B. p=NULLC. pnext=head D. p=head15. 设指针P指向双链表的某一结点，则双链表结构的对称性可用（A）式来刻画。Ap-prior-next=p-next- prior；Bp-prior-prior=p-next- prior；Cp-next-next=p-prior-prior； D p-prior-next=p-next-next；16用链表表示线性表的优点是 ( C )。A.便于随机存取 B.花费的存储空间比顺序表少 C.便于插入与删除 D.数据元素的物理顺序与逻辑顺序相同17.设单链表中指针p指向接点A，接点A存在后继结点，若要删除结点A的后继结点，则需要修改指针的操作为_A_Ap-next=p-next-next B.p=p-next C.p=p-next-next D.p-next=p18.在非空循环双向链表中，在q所指的接点前插入一个由p所指结点的过程依次为：p-next=q;p-prior=q-prior;_;q-prior-next=p.A.q-next=p B.q-prior-next=p C.p-prior-next=p D.p-next-prior=p.二、填空1、算法是指令的有限序列，其中每一条指令表示一个或多个操作，此外，一个算法还具有五个重要特性，它们分别是 _有穷性_ 、_确定性_ 、_可行性_ 、有零或多个输入和有一或多个输出。2、算法优劣的五个标准是正确性、可使用性、_可读性_、_健壮性_、_高效性_。3、数据结构被形式地定义为（D, R），其中D是 数据元素 的有限集合，R是D上的 关系 有限集合。4、一个算法的效率可分为 时间 效率和 空间 效率。5、非空单循环链表head中*p是尾结点的条件是（指针head指向头结点）_p-next=head_.6、向一个长度为n的向量的第i个元素(1in+1)之前插入一个元素时，需向后移动 n-i+1 个元素。7设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语句序列为_p-llink-rlink=p-rlink _p-rlink-llink=p-llink_（设结点中的两个指针域分别为llink和rlink）。8设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中_n-i+1_个数据元素；删除第i个位置上的数据元素需要移动表中_n-i_个元素; 删除一个元素，需要平均移动 _(n-1)/2_元素。9、在一个单链表中，在p所指结点之后插入一个由指针s所指结点，应执行s-next=_p-next_和p-next=_s_的操作。10、在一个单链表中，在p所指结点之前插入一个由指针s所指结点，可执行以下操作：s-next=_p-next_;p-next=s;t=p-data;p-data=_s-data_;s-data=_t_;三、程序题1、在单链表（表头指针为head）的元素中找出最后一个值为e的元素，返回其指针；如果找不到，返回NULL。完成以下程序。typedef struct LinkNodeint data;struct LinkNode *next;NODE;NODE *search_link(Node *head,int e)NODE *p,*q;q=_null_;for(p=head;_p_;p=p-next) if(p-data=e) _q=p_;return q;2、以下函数first_insert()的功能在已知链表的首结点之前插入一个指定值的节点；函数reverse_copy()的功能是按已知链表复制出一个新链表，但新链表的结点链接顺序与已知链表的结点链接顺序相反；函数print_link()用来输出链表中各结点的值；函数free_link()用来释放链表全部结点空间。typedef struct nodeint val;struct node *next;Node;void first_insert(Node *p,int v)Node *q=(Node *)malloc(sizeof(Node);q-val=v;_q-next=p_;_p=q_;Node *reverse_copy(Node *p)Node *u;for(u=NULL;p;p=p-next) first_insert(_u, p-val_)return u;void print_link(Node *p)for(;_p_;_p=p-next_) printf(% dt,p-val);printf(n);void free_link(Node *p)Node *u;while(p!=NULL) u=p-next;free(p);_p=u_;四、简答试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序