一、单项选择题

下列每题给出的四个选项中，只有一个选项最符合试题要求。

　　1. 若某线性表最常用的操作是存取第i个元素及其前驱的值，则采用______存储方式更节省操作时间。

　　A.单链表

　　B.双链表

　　C.单循环链表

　　D.顺序表

　　D

　　[解析] 选项A、B和C中的三个存储结构在存取第i个元素及其前驱的值，都需遍历数组，时间复杂度为O(n)。故本题选D。

　　2. 设有两个指针p和q分别指向某单链表中的两个元素，若p所指向元素为q所指向元素的前驱，则______成立。

　　A.p->next==q->next

　　B.q->next==p

　　C.p->next==q

　　D.p==q

　　C

　　[解析] p所指向元素为q所指向元素的前驱，那么q所指向元素的后继为p所指向的元素。故本题选C。

　　3. 在长度为10的顺序表中删除元素可能需要移动若干元素，最坏情况下的删除需要移动的元素个数是______。

　　A.10

　　B.9

　　C.8

　　D.7

　　B

　　[解析] 顺序表中第一个位置上删除一个元素时，需将后面第2个元素至第n个元素均向前移动一位。故本题 ……此处隐藏26047个字…… ，采用C、C++或Java语言描述算法，关键之处给出注释。

　　根据算法思想设计的代码如下所示。

　　#define MAX_VERTEX_NUM 20

　　typedef struct ArcNode{

　　int adjvex; //该弧所指向的顶点的位置

　　struct ArcNode * nextarc; //指向下一条弧的指针

　　}ArcNode;

　　typedef struct VNode{

　　int data; //顶点信息

　　ArcNode * firstarc; //指向第一条依附该顶点的弧的指针

　　}VNode,AdjList[MAX_VERTEX_NUM];

　　typedef struct{

　　AdjList vertices;

　　int vexnum,arcnum; //图的当前顶点数和弧数

　　int kind; //图的种类标志

　　}ALGraph;

　　void Create(ALGraph *G){

　　int i,j;

　　scanf("%d %d",&i,&j);

　　G->vexnum=i;

　　G->arcnum=j;

　　ArcNode *node;

　　//构建顶点信息表

　　for(int k=0;k