试题出自试卷《南京邮电大学2007年811数据结构真题解析》

答：
（1）我所设计的是单链表，它是一种线性结构，属于链式存储结构。

（2）Insert（x）函数的实现如下所示：

//单链表中插入新的结点
bool ListInsert(LNode*& L, int i, int x) {
    int j = 0;
    LNode* p = L, * s;
    if (i < 0)
        return false;
    while (j < i - 1 && p != NULL) {
        j++;
        p = p->next;
    }
    if (p == NULL)
        return false;
    else
    {
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        s->next = p->next;
        p->next = s;
        return true;
    }
}

（3）单链表的创建和求最小元素的时间复杂度为O(n)，其中n为单链表中结点个数。具体算法实现如下：

typedef struct LNode {
    int data;
    struct LNode* next;
}LNode,LinkList;//单链表的结构体
//头插法构造单链表
void Create (LNode*& L, int a[], int n) {
    LNode* s;
    L = (LNode*)malloc(sizeof(LNode));
    L->next = NULL;
    for (int i = 0; i < n; i++) {
        s = (LNode*)malloc(sizeof(LNode));
        s->data = a[i];
        s->next = L->next;
        L->next = s;
    }
}
//在单链表中寻找最小的结点
LNode* min(LNode*& L) {
    LNode* min = L->next;
    LNode* p = L->next->next;
    while (p) {
        if (p->data < min->data) {
            min = p;
            p = p->next;
        }
    }
    return min;
}

【考点】本题考查数据结构--绪论--数据结构的三要素--数据的运算。