数据结构第2章
班级： 15工19 姓名： 张雨学号： 20150200155
一、判断题。
1、线性表的特点是每个元素都有一个前驱和一个后继。(
2、取一维数组的第i个元素的时间同i的大小有关。(
3、单链表结点有两个域：数据域和指向下一个结点地址的指针域。 （
4、双链表结点有两个指针域：指向前、后结点地址的指针。 （
5、在单链表中的第i个位置插入一个新结点，无需从头查找该结点。 （
6、线性表的链表存储方式任何情况下都优于顺序存储方式。 （
二、选择题。
1、线性表的顺序存储方式中，存储单元的地址（ a ）。
a、一定连续 b、一定不连续 c、不一定连续 d、部分连续，部分不连续。
2、线性表的链式存储方式中，存储单元的地址（ c ）。
a、一定连续 b、一定不连续 c、不一定连续 d、部分连续，部分不连续。
3、线性表的特点是（ a ）。
a、 第一个元素只有一个后继元素，最后一个元素只有一个前驱元素，其它元素有且仅有前驱或后继；
b、元素和元素之间是多对多关系；
c、一个元素可以有多个后继，但只有一个前驱； d、一个元素可以有多个前驱，但只有一个后继。
4、数据结构在计算机内存中的表示是指( a )。
a、数据的存储结构 b、数据结构 c、数据的逻辑结构 d、数据元素之间的关系。
5、线性表是具有n个（ c ）的有限序列。
a、表元素 b、字符 c、数据元素 d、数据信息。
6、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ a ）存储方式最节省时间。
a、顺序表 b、双链表 c、带头结点的双循环链表 d、单循环链表。
7、设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( d )最节省时间。
a、 单链表 b、单循环链表 c、 带尾指针的单循环链表(好插不好删) d、带头结点的双循环链表。
8、非空的循环单链表的头结点为head，后继域为next，其尾结点p满足（ a ）。
a、p→next=head b、p→next=null c、p=null d、p= head
9、双向链表中有两个指针域，prior和next分别指向前趋及后继。完成在双循环链表结点p之后插入s的操作是（ d ）。
a、 p→next=s ; s→prior=p; p→next→prior =s ; s→next=p→next;
b、 p→next→prior =s; p→next=s; s→prior=p; s→next=p→next;
c、 s→prior=p; s→next=p→next; p→next=s; p→next→prior=s ;
d、 s→prior =p; s→next=p→next; p→next→prior =s ; p→next=s;
10、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ b ）。
a、p->next=s; s->next=p->next; b、 s->next=p->next; p->next=s;
c、p->next=s; p->next=s->next; d、 p->next=s->next; p->next=s;
11、单链表中，指针p指向的结点的后继为q指向的结点，在指针为p的结点之后、q之前插入指针为s的结点，正确的操作是：（ d ）。
a、p->next=s; s=p; b、p=s;p=q c、p=q;s=p; d、s->next=q; p->next=s;
12、单链表中，指针p指向的结点的后继为q指向的结点，删除q指针的正确的操作是：（ a ）。
a、p->next=q->next; free(q); b、p->next=q; free(q); c、free(p); d、free(q);
13、 在双向链表存储结构中，prior和next分别指向前趋及后继，删除p所指的结点时需修改指针（ a ）。
a、p->next->prior=p->prior；p->prior->next=p->next; b、p->next=p->next->next；p->next->prior=p;
c、p->prior->next=p；p->prior=p->prior->priord、p->prior=p->next->next；p->next=p->prior->prior;
14、带附加头节点的单链表l为空表的条件是（ b ）。
a、l==null b、l->next==null c、l->next==null d、l->next==l
15、不带附加头结点的单链表l为空表的条件是（ a ）。
a、l==null b、l->next==null c、l->next==null d、l->next==l
16、以下哪项不是单链表的特点（ b ）。
a、存储空间可以连续，也可以不连续 b、插入时，不用查找插入位置。
c、插入时不用移动其他元素的存储位置 d、删除时不用移动其他元素的存储位置。
17、删除在顺序存储方式的线性表中第i个元素，（ c ）。
a、需要从第一个元素可是查找第i个元素。 b、不必移动顺序表中的元素。
c、第i个元素之后的所有元素需要前移。 d、第i个元素前移。
18、在顺序存储方式的线性表中的第i个位置插入一个元素（ c ）。
a、需要从第一个元素可是查找第i个元素。 b、不必移动顺序表中的元素。
c、第i个位置后的元素后移，第i个位置插入元素。 d、只需将插入的元素放在第i个位置。
19、在（ b ）运算中，使用顺序表比链表好。
a、插入 b、根据序号查找 c、 删除 d、根据元素值查找。
20、在非空的线性表中，有且只有一个直接前驱和一个直接后继的结点是 （ c ）
a、开始结点 b、终端结点 c、内部节点 d、所有结点。
21、在一个长度为n的顺序表中，如果要在第i个元素前插入一个元素，要后移（ d ）个元素。
a、n b、n-1 c、i d、n-i+1
22、在一个数组中查找第i个元素（i在有效范围内），则需要（ b ）。
a、从头开始查找 b、无需查找，直接引用标号 c、从尾部查找 d、以上答案都不对。
23、在一个长度为n(n>1)的单链表上，设有头和尾两个指针，执行（ b ）操作与链表的长度有关。
a、删除单链表中的第一个元素b、删除单链表中的最后一个元素
c、在单链表第一个元素前插入一个新元素 d、在单链表最后一个元素后插入一个新元素。
24、与单链表相比，双链表的优点之一是（ d ）。
a、插入、删除操作更简单 b、可以进行随机访问
c、可以省略表头指针或表尾指针 d、顺序访问相邻结点更灵活。
25、指针p指向单链表的结点，输出该结点值的语句为（ b ），设结点值为整数类型。
a、 printf(“%d”,p->next); b、printf(“%d”,p->data); c、printf(“%d”,p); d、 printf(“%c”,p);
三、算法分析题。
1、简述以下算法的功能。
status a（linklist l）
if （l&&l->next）未到表尾。
q=l；
l=l->next；
p=l；while(p->next) p=p->next；
p-> next =q；
q->next= null；}
return ok；}答：将头结点改为尾结点。
2、一个算法，功能是在带有附加头结点的单链表l中查找数据元素值为x的结点，查到后返回其在链表中的位置，查不到时返回0。请把下列算法中缺少的语句（底部划线部分）补上。
单链表的存储结构定义为：
typedef struct lnode
lnode，*linklist；
算法如下：status search (linklist *l, elemtype x)
int i=0；
struct lnode *p；
p=l->next；
while ((p!=null)&&p->data!=x))
p=p->next；
i++；if (p==null) i=0；
return(i)；
四、算法设计题。
1、写算法实现在递增有序的顺序表中，插入值x后仍然有序。
status listinsert(sqlist &l,elemtype x)
在递增顺序表l中插入x
if( return error当前存储空间已满。
m=while (m>=0)
找到x待查的位置。
if(x< m不是待插的位置，则与前一个值比较大小。
else break此时的x就应该插在第m个元素之后，所以跳出循环，记录此时的m
for(j=>=m-1;j--)
待插位置及之后的元素后移。
将x放入第m个位置。
第2章作业题
2 3如图2 18所示，在恒定的总水头差之下水自下而上透过两个土样，从土样1顶面溢出。1 以土样2底面c c为基准面，求该面的总水头和静水头 2 已知水流经土样2的水头损失为总水头差30 求b b面的总水头和静水头 3 已知土样2的渗透系数为0.05cm s，求单位时间内土样横截面单位面积的流量 4...
第2章作业题
第二章作业题。一 选择题。1.三态门输出高阻状态时，是正确的说法。a.用电压表测量指针不动 b.相当于悬空 c.电压不高不低 d.测量电阻指针不动。2.以下电路中可以实现 线与 功能的有 a.与非门 b.三态输出门 c.集电极开路门 d.漏极开路门。3 以下电路中常用于总线应用的有 门 门 c.漏极...
第2章作业题
第二章作业。要求 1 必须抄题目 2 题与题必须留一定的空隙，以方便批改 3 字迹尽量工整 4 请独立完成，不能够抄袭。一 简答题。1 组成放大器的基本原则是什么？二 计算题 5道题 1 电路如下图所示，已知ubeq 0.6v，50试求 1 静态工作点ibq icq uceq 2 画出微变等效电路？...