模拟练习题一、单项选择题1、若某线性表中最常用的操作是取第i个元素和查找第i个元素的的前驱元素，则采用（）的存储方式最节省时间。A．顺序表B．双链表C．单链表D．单循环链表2、与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。A．存储结构B．存储实现C．逻辑结构D．运算实现3、用链表表示线性表的优点是（）。A．便于随机存取B.花费的存储空间较顺序存储少C．便于插入和删除D.数据元素的物理顺序与逻辑顺序相同4、设单向循环链表中结点的结构为（data,link），且rear是指向非空的带表头结点的单向循环链表的尾结点的指针。若想删除该链表的第一个结点，则应执行下列哪一个操作？（）A．s=rear;rear=rear->link;free(s);B．rear=rear->link;free(rear);C．rear=rear->link->link;free(rear);D．s=rear->link->link;rear->link->link=s->link;free(s);5、设双向循环链表中结点的结构为（data,lLink,rLink），且不带表头结点。若想在指针p所指结点之后（右链方向）插入指针s所指的结点，则应执行下列哪个操作？（）A．p->rLink=s;s->lLink=p;p->rLink->lLink=s;s->rLink=p->rLinkB．p->rLink=s;p->rLink->lLink=s;s->lLink=p;s->rLink=p->rLinkC．s->lLink=p;s->rLink=p->rLink;p->rLink=s;p->rLink->lLink=s;D．s->lLink=p;s->rLink=p->rLink;p->rLink->lLink=s;p->rLink=s;6、在具有n个结点的有序单链表中插入一个新结点并使该链表仍然有序的时间复杂度是（）。A．O(1)B．O(n)C．O(nlogn)D．O(n2)7、设单循环链表中结点的结构为（data,link），且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪个操作？（）。A．s=rear;rear=rear->link;deletes;B．rear=rear->link;deleterear;C．rear=rear->link->link;deleterear;D．s=rear->link->link;rear->link->link=s->link;deletes;8、将下图所示的s所指结点加到p所指结点之后，其语句为（）。pnextsnextA．s->next=p+1；p->next=s；B．(*p).next=s；(*s).next=(*p).next；C．s->next=p->next；p->next=s；D．s->next=p->next；p->next=s->next；9、队列和栈的主要区别是（）。A．逻辑结构不同B．存储结构不同C．所包含的运算个数不同D．限定插入和删除操作的位置不同10、已知广义表的表头为a，表尾为（b，c），则此广义表为（）。A．（a，（b，c））B．（a，b，c）C．（（a），b，c）D．（（a，b，c））11、对表长为n的顺序表进行顺序查找，在查找概率相等的情况下，查找成功的平均查找长度为（）。A．(n-1)/2B．n/2C．(n+1)/2D．n12、如图所示的4棵树中，是满二叉树的为（）。(A)(B)(C)(D)13、一个二叉树按顺序方式存储在一个维数组中，如图01234567891011121314ABCDEFGHIJ则结点E在二叉树的第（）层。A．1B、2C．3D．414、n个顶点的强连通图中至少含有（）。A．n-l条有向边B．n条有向边C．n(n-1)／2条有向边D．n(n-1)条有向边15、对有n个结点的顺序表进行快速排序，在最坏情况下其关键码比较次数为（）。A．O(n)B．O(log2n)C．O(nlog2n)D．O(n2)16、在下面各种链表结构中，能在O(1)时间内完成在指定结点之前插入元素X的结构是（）。A．单链表B．单向循环链表C．带表头结点的单链表D．双向循环链表17、若让元素1,2,3依次进栈，则出栈次序不可能出现（）。A．3，1，2B．2，1，3C．3，2，1D．1，3