数据结构与算法-考研试题(中科院软件所 1998 链表)

判断题（1998中科院软件所）

没有提供指针类型的语言，无法构造链式结构，该说法【】

答案解析

错

【解析】

有的高级语言中没有指针数据类型，不能动态生成结点，但可以用静态链表来实现线性表的链式存储结构。

讨论

数据结构与算法

如果入栈序列为ABCD，不可能出现的出栈序列是【】

算术表达式(a+b)*(c-d/e)的后缀表达式为【】

假设有两个按元素值递增有序排列的线性表A和B，均以带头结点的单链表作为存储结构，编写算法将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（A表和B表）的结点空间存放表C。

试写出在双向链表da中的插入操作算法，算法中插入位置的获取可直接引入getnodep(da,i)，其中参数da为双向链表，i是要插入的数据，要求算法中含有双向链表da的结点结构描述。

已知结点指针p、q分别表示双向链表中任意两个相邻结点（即p->rlink=q且q->llink=p），请写出删除q所指结点的程序段。

在非空双向循环链表中q所指的结点后面插入p所指的结点的过程已经依次进行了以下3步：p->llink=q；p->rlink=q->rlink；q->rlink=p；第4步应该是____________________；（写出该步对应的语句）。

将下图所示的s所指点加到p所指点之后，其语句应为【】

双向链表的优势是____________________。

线性表选用顺序存储结构表示的适用场合是____________________。

将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为__________。

链表

线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。【】

现有非空双向链表 L，其结点结构为：prer|data|next。prer 是指向前直接前驱结点的指针，next 是指向直接后继结点的指针。若要在 L 中指针 p 所指向的结点（非尾结点）之后插入指针 s 指向的新结点，则在执行了语句序列： “s->next=p->next;p->next=s”后，还要执行【】

线性表采用单循环链表存储的主要特点是【】

函数 Reverselist(LinkList headptr)的功能是将含有头结点的单链表就地逆置。处理思路是将链表中的指针逆转，即将原链表看成由两部分组成，已经完成逆置的部分和未完成逆置的部分，令s指向未逆置部分的第一个结点，并将该结点插入已完成部分的表头(头结点之后)，直到全部结点的指针域都修改完成为止。例如，某单链表如图所示，逆置过程中指针s的变化情况如图(a)(b)所示。链表结点类型定义如下：typedef struct Node{ int data， struct Node *next;}Node， *LinkList;void ReverseList (LinkList headptr){//含头结点的单链表就地逆置， headptr为头指针 LinkList p，s; if(__(1)__) return;//空链表(仅有头结点)时无需处理 p=__(2)__;//令p指向第一个元素结点 if (!p->next) return;//链表中仅有一个元素结点时无需处理 s= p->next;//s指向第二个元素结点 __(3)__=NULL;//设置第一个元素结点的指针域为空 while (s){ p=s;//令p指向未处理链表的第一个结点 s=__(4)__; p-> next= headptr-> next;//将p所指结点插入已完成部分的表头 headptr-> next=__(5)__; }}

线性表采用单链表存储时的特点是【】。

线性表的静态链表存储结构与顺序存储结构相比优点是【】

顺序表存储方式只能用于存储线性结构。

若用单链表来表示队列则应该选用【】

用数组表示的循环队列的队首和队尾位置分别为1和 max_size，试给出判断队列为空和为满的边界条件。

设栈的输入序列为1,2,3,...,n，输出序列为a1,a2,a3,...,an，若存在1≤k≤n使得 ak=n，则当k≤i≤n时，ai 为【】

线性表

设A是一个线性表（a1,a1,...,an），采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为多少？若元素插在ai与ai+1之间（0≤i≤n-1）的概率为，则平均每插入一个元素所要移动的元素个数又是多少？

在含有n个元素的顺序表中，算法时间复杂度为O(1)的操作是【】

假设线性表的长度为n，且采用顺序存储结构存储。当在线性表的任何位置上插入一个数据元素的概率相同时，插入一个数据元素需要移动元素的平均个数为【】。

表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均个数为_______，删除一个元素需要移动元素的平均个数为_______。供选择的答案：A.(n-1)/2 B.n C.n+1 D.n-1 E.n/2 F.(n+1)/2 G.(n-2)/2

若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法时间复杂度为【】。（1≤i≤n+1）

线性表是具有n个【】的有限序列。

下列对顺序存储的有序表 (长度为 n)实现给定操作的算法中平均时间复杂度为 O(1)的是【】

若某线性表长度为n且采用顺序存储方式，则运算速度最快的操作是【】。

对于长度为n的线性表(即n个元素构成的序列)，若采用顺序存储结构(数组存储)，则在等概率下，删除一个元素平均需要移动的元素数为【】。

下列描述中，正确的是【】