结点的数据结构为： priordatanext答： int f (Dlistnode *h)
{ Dlistnode *p,*q; int j=1; p=p->next; q=q->prior; while(p!=q && p->prior!=q)
if (p->data==q->data) { p=p->next; q=q->prior; }
（ √ ）6. 在顺序表中按下标序号访问任意一结点的时间复杂度均为O(1) 。
（ √ ）7. 带头结点的单向链表L为空的判定条件是L->next=null。
（ √ ）8. 在顺序表中插入或删除一个元素，需要平均移动表中一半元素。
（ × ）9. 线性表的逻辑顺序与存储顺序总是一致的。。
（ √ ）10. 任何一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖
B 在地址为p的结点之后插入一个结点
C 删除开始结点
D 删除地址为p的结点的后继结点
9. 在n个结点的顺序表中，算法的时间复杂度是O(1) 的操作是 A ：
A 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
B 在第i个结点后插入一个新结点（1≤i≤n）
C 删除第i个结点（1≤i≤n）
B head->next==NULL
C head->next==head
D head->next-> prior==NULL
14. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址： D
A 必须是连续的
B部分地址必须是连续的
C 一定是不连续的
D 连续或不连续都可以
15. 在长度为n的顺序表的第i个位置上插入一个元素（1≤ i ≤n+1），元素的移动次数
12. 若一个算法中的语句频度之和为T(n) = 37n+4nlogn+5n2，则算法的时间复杂度为
______D______ 。
A O（1） B O(n) C O (nlogn) D O(n2)
13. 有一个带头结点的双向循环链表，头指针为head, 则其为空的条件是： C
A head->prior==NULL
六、阅读分析题（5分）
以下算法的功能是求单链表的表长运算ListLength(L)。请将空白处补充完整。
int Listlength(LinkList L)
{ // L是有头结点的单链表，该函数返回其长度；
int i;
ListNode *p;
i=0;
p=L;
while (
p->next
)
{ i++; p=p->next ; }
while(p&&q)
{s=p->next;p->next=q; //将B的元素插入
if(s) { t=q->next;
q->next=s; //如A非空,将A的元素插入
}
p=s;q=t;
}//while
}//merge
2. 编写算法，判断带头结点的双向循环链表L是否对称。 对称是指：设各元素值a1,a2,...,an, 则有ai=an-i+1 ， 即指：a1= an，a2= an-1 ... ...
为：___A_____ 。
A n-i+1
B n-i
Ci
D i-1
五、简答题（每题5分，共15分）
1. 描述以下三个概念的区别：头指针、头结点、首元结点（第一个元素结点）。在单链
表中设置头结点的作用是什么？
答：首元结点是指链表中存储线性表中第一个数据元素a1的结点。为了操作方便，通常在
链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据
存储结构表示同一逻辑结构的问题。
头结点
head-->datalink
头指针
首元结点
简而言之： 头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针； 头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息 首元素结点是指链表中存储线性表中第一个数据元素a1的结点。
华东理工大学网络学院
《数据结构》（ch1绪论和ch2线性表）
班级
学号
姓名
成绩
一、 名词解释（每小题2分，共10分）
1.数据结构 2. 线性结构
3.存储结构 4. 逻辑结构 5.非线性结构
答：1.数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的
内容:数据的逻辑结构、存储结构和数据的运算。
else{ j=0; break;} return j; }
??
??
??
??
第1 / 6页
5. 在n个结点的带头结点的单链表中，要在已知结点*A O（1） B O(n) C O (n+1) D O(n2)
6. 以下对循环链表的叙述错误的是 D ：
A 单链表和双向链表经首尾相接都可以形成循环链表
B 循环链表可以用头指针表示，也可以用尾指针表示
C 从循环链表的任何一个结点出发都能访问到表中的其他结点
D构成循环链表需要增加存储空间
7. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 B
个元素。
A 8 B 63.5
C 63 D 7
8. 在n个结点的单链表中，算法的时间复杂度是O(n) 的操作是 A ：
A 求链表的第i个结点
D 将n个结点从小到大排序
10. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是
B
A 110 B 108
C 100 D 120
11. 对于只在表的首、尾进行插入操作的线性表，宜采用的存储结构为： C
A 顺序表
B 用头指针表示的单循环链表
C 用尾指针表示的单循环链表 D 单链表
于采用的存储结构。
四、单选题（每题2分，共30分）
1.有程序如下：
i=1; k=0;
while(i<n)
{ k=k+10*i;
i++;
}
则该程序段的时间复杂度为： B
A O（1） B O(n) C O (n+1) D O(n2)
2. 从逻辑上可以把数据结构分成 C
A 动态结构和静态结构
B 顺序结构和链式结构
树形结构和网状（图形）结构四种逻辑结构。
3. 一个算法具有有穷性、 确定性 、 可行性 、输入和输出五个重要特性。
4. 在一个单链表中p所指结点之后插入s所指结点时,应执行s->next= p->next
和p->next= S
的操作。
三、判断正误（在正确的说法后面打勾，反之打叉）（每小题1分，共10分）
元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行
统一处理。头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。若链表
中附设头结点，则不管线性表是否为空表，头指针均不为空。否则表示空表的链表的头指
针为空。这三个概念对单链表、双向链表和循环链表均适用。是否设置头结点，是不同的
（ × ）1. 线性数据结构只能用顺序结构存放，非线性数据结构只能用链式存储存
放。
（ √ ）2. 单链表中逻辑上相邻的元素未必在存储的物理位置次序上相邻。
（ × ）3. 链式存储是一种随机存取的数据结构。
（ √ ）4 顺序表中逻辑上相邻的元素的物理位置必定相邻。
（ × ）5. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
(2) 应采用顺序存储表示。因为顺序存储表示的存取速度快，但修改效率低。 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这 时采用顺序存储表示较好。
3.简要说明算法与程序的区别。 答：算法是解决特定问题的操作序列，可以用多种方式描述。程序是算法在计算机中的实
现，与具体的计算机语言有关。
return i
；
}
七、编程题（每题10分，共20分）
1. 把单链表A和B合并为C，要求合并时A和B的元素间隔排列，且使用原存储空间。
数据结构定义如下：
typedef struct node
{int data;
struct node *next;
} Listnode;
typedef Listnode *Linklist;
B p->next=s; p->next->prior=s; s->prior=p; s->next=p->next
C s->prior=p; s->next=p; p->next=s; p->next->prior=s
D s->prior=p; p->next=s; s->next=p->next ;p->next->prior=s;
2.顺序存储结构和链式存储各有优缺点。请回答如下问题： （1）如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总 数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？
(2) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取 表中的元素，这时，应采用哪种存储表示？为什么？ 答： (1) 如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总 数也可能自动改变、在此情况下，应选用链式存储表示。 理由为：如果采用顺序存储表示，必须在一个连续的可用空间中为这n个表分配空间。初 始时因不知道哪个表增长得快，必须平均分配空间。在程序运行过程中，有的表占用的空 间增长得快，有的表占用的空间增长得慢；有的表很快就用完了分配给它的空间，有的表 才用了少量的空间，在进行元素的插入时就必须成片地移动其他的表的空间，以空出位置 进行插入；在元素删除时，为填补空白，也可能移动许多元素。这个处理过程极其繁琐和 低效。 如果采用链式存储表示，一个表的存储空间可以连续，可以不连续。表的增长通过动 态存储分配解决，只要存储器未满，就不会有表溢出的问题；表的收缩可以通过动态存储 释放实现，释放的空间还可以在以后动态分配给其他的存储申请要求，非常灵活方便。对 于n个表(包括表的总数可能变化)共存的情形，处理十分简便和快捷。所以选用链式存储 表示较好。