《数据结构》试卷B.doc

《数据结构》试卷B.doc一、单项选择题（在每小题的四个备选答案中选出一个正确答案，并将其号码填 在题干的括号内。每小题2分，共30分）
1•计算机中算法是指（ ）。


在一个单链表中，若指针p所指结点不是最后结点，在p之后插入指针s所指
结点，则应执行的语句序列为（ ）。
A. s~>next二p； p->next二s; s->next二p->next;p->next二s；
C. s~>next二p->next;p:=s; D. p->next二s;s->next二p;
对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是 （ ）
A ・ head二二NULL B ・ head~>next二二NULL C ・ head->next二二head
D. head!=NULL
循环队列用数组A [0.. m-1]存放其元素值，已知其头尾指针分别是front和
rear,
则当前队列中的元素个数是（
）。
A. (rear—front+m)
MOD m
B rear—front+1
C. rear—frontT
D. rear—front
ro
1 01
= 该图共有（2）条弧;
（1） A、 9（2） A、 5
0 11⑷可以看出,
此图共有（1）个顶点。如果是有向图,
B、3B、4
C、C、
D、1D、2
中缀表达式A- （B+C/D） *E的后缀形式是
A、 AB-C+D/E* B、 ABC+D/-E*
C、
ABCD/E*+-
D、 ABCD/+E*-
下列程序段的算法复杂度为（）
1=0；
s=0;
while(s<n)
{I++; s=s+i; }
A^ 0 （n」）B、0 （n） C^ （亦） D^ 0 （l°g 2n）
&下面哪一方法可以判断出一个有向图是否有环（回路）：

对于一个具有n个顶点的无向图，若采用邻接表表示，则存放表头结点的数组
的大小为（ ）
A. n B. n+1 C. n-1 D. n+边数
在一个具有n个顶点的无向图中，要连通全部顶点至少需要（ ）条边。
A. n B. n+1 C. n~l D. n/2
在有向图中每个顶点的度等于该顶点的（ ）0




12.
(
输入序列为（A, B, C, D）,
顺序通过一个栈后，不可能得到的输出序列有
丿
A、 (A, B, C, D)
B、 (D, C, B, A)
C、 (A, C, D, B)
D、 (C, A, B, D)
13.
无向图的邻接矩阵是一个（
)

一个向量的第一个元素的存储位址为100,每个元素的长度为2个字节，则 第5个元素的起始位址为（）
A、 110 B、 108 C、 100 D112
设有两个串p和q,其中q是p的子串，求q在P中首次出现的位置的算法
称为（ ）

二、判断题（判断