数据结构练习第二章线性表
一、选择题
1. 下面关于线性表的叙述错误的是（）。
A.线性表采用顺序存储必须占用一片连续的存储空间
B. 线性表采用链式存储不必占用一片连续的存储空间
C. 线性表采用链式存储便于插入和删除操作的实现
D. 线性表采用顺序存储便于插入和删除操作的实现
2. 设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针
的操作序列为（）。
A.q=p->next；p->data=q->data；p->next=q->next；free(q)；
B. q=p->next；q->data=p->data；p->next=q->next；free(q)；
C. q=p->next；p->next=q->next；free(q)；
D. q=p->next；p->data=q->data；free(q)；
3. 设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为
（）。
n) C. O(1) D. O(n2)
A. O(n)
B. O(nlog
2
4．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（）。
A. O(log
n) B. O(1) C. O(n2) D. O(n)
2
5．设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（）。
A. head==0
B.head->next==0
C. head->next==head
D.head!=0
6．设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（）。
A. head==0
B. head->next==0
C. head->next==head
D. head!=0
7．建立一个长度为n的有序单链表的时间复杂度为（）
A. O(n)
B. O(1)
C. O(n2)
D. O(log
n)
2
8．设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（）个元素。
A. n-i
B. n+l -i
C. n-1-i
D. i
9．设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（）。
A. p->right=s； s->left=p； p->right->left=s； s->right=p->right；
B. s->left=p；s->right=p->right；p->right=s； p->right->left=s；
C. p->right=s； p->right->left=s； s->left=p； s->right=p->right；
D. s->left=p；s->right=p->right；p->right->left=s； p->right=s；
10．设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列（）存储方式最节省运算时间。
A. 单向链表 B .单向循环链表
C. 双向链表
D. 双向循环链表
11．设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为（）。
A. s->next=p->next；p->next=-s；
B. q->next=s； s->next=p；
C. p->next=s->next；s->next=p；
D. p->next=s；s->next=q；12．在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）之前插入一个新元素时，需要从后向前依次后移（）个元素。
A．n-i B．n-i+1 C．n-i-1 D．i
13．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（）。
A. q->next=p->next;p->next=q;
B. p->next=q->next;q=p;
C. q->next=p->next;p->next=q;
D. p->next=q->next;q->next=p;
14．在单链表中，存储每个结点需要有两个域，一个是数据域，另一个是指针域，指针域指向该结点的（）
A.直接前趋
B.直接后继
C.开始结点
D.终端结点
15．将两个各有n个元素的有序表合并成一个有序表，其最少的比较次数为（）
A.n
B.2n-1
C.2n
D.n2
16．线性表采用链式存储结构时，要求内存中可用存储单元的地址( )
A. 必须是连续的
B. 必须是部分连续的
C. 一定是不连续的
D. 连续和不连续都可以
17．设h是指向非空带表头结点的循环链表的头指针，p是辅助指针。执行程序段
p=h;
while (p->next->next!=h)
p=p->next;
p->next=h;
后（其中，p->next为p指向结点的指针域），则( )
A. p->next指针指向链尾结点
B. h指向链尾结点
C. 删除链尾前面的结点
D. 删除链尾结点
18．设顺序表有19个元素，第一个元素的地址为200，且每个元素占3个字节，则第14个元素的存储地址为( )
A.236
B.239
C.242
D.245
19．设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为( )
A.5
B.6
C.7
D.9
20．设p为指向双向循环链表中某个结点的指针，p所指向的结点的两个链域分别用p→llink和p→rlink表示，则同样表示p指针所指向结点的表达式是( )
A.p→llink
B.p→rlink
C.p→llink→llink
D.p→llink→rlink
21．一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元
素的存储地址是( )
A. 110
B. 108
C. 100
D. 120
22．关于存储相同数据元素的说法中正确的是（）
A．顺序存储比链式存储少占空间
B.顺序存储比链式存储多占空间
C.顺序存储和链式存储都要求占用整块存储空间
D.链式存储比顺序存储难于扩充空间
23．已知一个单链表中，指针q指向指针p的前趋结点，若在指针q所指结点和指针p所指结点之间插入指针s所指结点，则需执行（）
A．q→next=s；p→next=s； B.q→next=s；s→next=p；
C.q→next=s；q→next=p；
D.q→next=s；s→next=q；24．在长度为n的线性表中删除一个指针p所指结点的时间复杂度是（）A．O(n) B.O(1)
C.O(log
2
n) D.O(n2)
25．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（）
A.单链表
B.仅有头指针的单循环链表
C.双链表
D.仅有尾指针的单循环链表26．从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动的元素的个数是（）
A.n-i
B.n-i+1
C.n-i-1
D.i
27．对于长度为n的顺序表执行删除操作，则其结点的移动次数（）
A.最少为0，最多为n
B.最少为1，最多为n
C.最少为0，最多为n-1
D.最少为1，最多为n-1
28．在一个单链表中，若p所指结点是q所指结点的前驱结点，则删除结点q 的正确操作是（）
A. p->next=q
B. p->next=q->next
C. p=q->next
D. p->next=q->next->next
29．在一个具有n个结点的有序单链表中插入一个新结点，并使插入后仍然有序，则该操作的时间复杂性量级为（）
A．O（1）B．O（n）
C．O（nlog
2
n） D．O(n2)
30．顺序存储的线性表（a
1,a
2
,…,a
n
）,在任一结点前插入一个新结点时所需移
动结点的平均次数为（）
A．n B．n/2
C．n+1 D．(n+1)/2
31．设单链表中指针p指向结点A，若删除A后的结点存在，则需要修改指针的操作为（）。
A．p->next=p->next->next B．p=p->next
C．p=p->next->next D．p->next=p
32．线性表的链式存储实现有利于（）运算。
A．插入 B．读表元
C．查找 D．定位
33．从一个长度为n的顺序表中删除第i个元素(1≤i≤n)，需向前移动（）
个元素。
A．n-i B．n-i+1
C．n-i-1 D．i
34．在一个长度为n的顺序存储线性表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需向后移动（）个元素。
A．n-i B．n-i+1
C．n-i-1 D．i
35．在一个单链表中，已知*q结点是*p结点的前趋结点，若在*q和*p之间插入*s结点，则需执行（）。
A．s->next=p->next; p->next=s; B．q->next=s; s->next=p;
C．p->next=s->next; s->next=p; D．p->next=s; s->next=q;
36．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（）。
A.HL = p; p->next = HL;
B.p->next = HL; HL = p;
C.p->next = HL; p = HL;
D.p->next = HL->next; HL->next = p;
37．在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行（）。
A.p = q->next ; p->next = q->next;
B.p = q->next ; q->next = p;
C.p = q->next ; q->next = p->next;
D.q->next = q->next->next; q->next = q;
38．线性表采用链式存储时，其地址（）。
A．必须是连续的 B．部分地址必须是连续的
C．一定是不连续的 D．连续与否均可以
39．在一个长度为n的线性表中插入第i个元素的操作中，i的取值范围是A．1≤i≤n B．0≤i≤n C．1≤i≤ n+1 D．1≤i≤n-1 40．如果要查找单链表中的第i个元素，应该从（）开始进行查找。
A．第i个结点 B．头结点C．尾结点 D．任意一个结点41．在一个长度为n的线性表中顺序查找值为x的元素时，查找时的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为（）。
A.n
B.n/2
C. (n+1)/2
D. (n-1)/2
42．在一个单链表HL中，若要在指针q所指的结点的后面插入一个由指针p所指的结点，则执行（）。
A.q->next = p->next ; p->next = q;
B.p->next = q->next; q = p;
C.q->next = p->next; p->next = q;
D.p->next = q->next ; q->next = p;
43. 在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行( )。
A. s→link=p→link; p→link=s;
B. p→link=s; s→link=q;
C . p→link=s→link; s→link=p; D. q →link=s; s→link =p;
44. 线性链表不具有的特点是（）。
A．随机访问 B．不必事先估计所需存储空间大小
C．插入与删除时不必移动元素 D．所需空间与线性表长度成正比
45. 下述哪一条是顺序存储结构的优点？（）。
A．插入运算方便 B．可方便地用于各种逻辑结构的存储表示C．存储密度大D．删除运算方便
46. 下面关于线性表的叙述中，错误的是哪一个？（）。
A．线性表采用顺序存储，必须占用一片连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于插入和删除操作。
47. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。
A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表
48．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。
A. 单链表
B. 仅有头指针的单循环链表
C. 双链表
D. 仅有尾指针的单循环链表
49．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。
A. 带头结点的双循环链表
B.单循环链表
C. 带尾指针的单循环链表
D. 单链表
50．若线性表最常用的操作是存取第I个元素及其前驱和后继元素的值，为节省时间应采用的存储方式( )。
A.单链表
B.双向链表
C.单循环链表
D.顺序表
51．静态链表中指针表示的是( )
A.下一元素的地址
B.内存储器的地址
C.下一元素在数组中的位置
D.左链或右链指向的元素的地址
52．在n个结点的线性表的数组实现中，算法的时间复杂性是O(1)的操作是( )
A. 访问第i个结点(1≤i<=n)和求第i个结点的直接前驱(2≤i<=n)
B. 在第i个结点后插入一个新结点(1≤i<=n)
C. 删除第i个结点(1≤i<=n)
D. 以上都不对
53．(1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。
(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。
(3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。
以上错误的是（）。
A．（1），（2） B．（1） C．（1），（2）,(3) D.（2）54．对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)
55．单链表中，增加一个头结点的目的是为了( ）。
A．使单链表至少有一个结点 B．标识表结点中首结点的位置
C．方便运算的实现 D．说明单链表是线性表的链式存储
56．对于双向循环链表,在p指针所指的结点之后插入s指针所指结点的操作应
为（）。
A．p->right=s ; s->left=p; p->right->left=s ; s->right=p->right;
B．p->right=s ; p->right->left=s ; s->left=p; s->right=p->right;
C．s->left=p; s->right=p->right; p->right=s ; p->right->left=s ; ;
D．s->left=p; s->right=p->right; p->right->left=s ; p->right=s ;
57．对于一个线性表既要求能够进行较快速的插入和删除，又要求存储结构能反
映数据之间的逻辑关系，则应该用( )。
A. 顺序存储方式
B. 链式存储方式
C. 散列存储方式
D. 以上均可以
58．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）。
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;
59．线性表的顺序存储结构是一种（）。
A. 随机存取的存储结构
B. 顺序存取的存储结构
C. 索引存取的存储结构
D. Hash存取的存储结构
60．顺序表是线性表的（B）
A、链式存储结构
B、顺序存储结构
C、索引存储结构
D、散列存储结构
61．带头结点的单链表head为空的条件是（B）
A、head=NULL
B、head->next=NULL
C、head->next=head
D、head!=NULL 62．链表不具有的特点是（B）
A．插入、删除不需要移动元素 B．可随机访问任一元素
C．不必事先估计存储空间 D．所需空间与线性长度成正比
63．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删
除运算，则利用（A）存储方式最节省时间。
A．顺序表 B．双链表
C．带头结点的双循环链表 D．单循环链表
64．下面关于线性表的叙述中，错误的是哪一个？（B）
A．线性表采用顺序存储，必须占用一片连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于插入和删除操作。
二、填空题
1．设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移
动表中_______个数据元素；删除第i个位置上的数据元素需要移动表中_______
个元素。n+1-i，n-i
2. 设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语句
序列为_________________________________________________________（设结
点中的两个指针域分别为llink和rlink）。p>llink->rlink=p->rlink;
p->rlink->llink=p->rlink
3．设指针变量p指向单链表中结点A，则删除结点A的语句序列为：
q=p->next；p->data=q->data；p->next=___________；feee(q)；q->next 4．在带头结点的单链表L中, 第一个元素所对应的结点的指针表达式是_____________。L->next
5．在双向循环链表中，在结点*Ｐ之前插入结点*Ｓ的语句序列是：S-> prior = P-> prior ; S->next=P; P->prior=S; __________________。S-> prior->next=S;
6．在有n个元素的链队列中，入队和出队操作的时间复杂度分别为_____O(1)____和______O(1)____。
7．在双链表中，存储一个结点有三个域，一个是数据域，另两个是指针域，分别指向_ _和_ 。前驱、后继
8．在循环队列中，存储空间为0~n-1。设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么其队空标志为rear=front，队满标志为_ ______。_(rear+1)%n=front
9．下面程序段的功能是利用从尾部插入的方法建立单链表的算法，请在下划线处填上正确的内容。
typedef struct node {int data; struct node *next;} lklist;
void lklistcreate(_____________ *&head )
{
for (i=1;i<=n;i++)
{
p=(lklist
*)malloc(sizeof(lklist));scanf(“%d”,&(p->data));p->next=0;
if(i==1)head=q=p;else {q->next=p;____________;}
}
}
lklist，q=p
10．设指针p指向单链表中结点A，指针s指向被插入的结点X，则在结点A的前面插入结点X时的操作序列为：
1) s->next=___________；2) p->next=s；3) t=p->data；
4) p->data=___________；5) s->data=t；p->next，s->data
11．设指针变量p指向单链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X需要执行的语句序列：s->next=p->next; _________________;。p->next=s
12．设指针变量head指向双向链表中的头结点，指针变量p指向双向链表中的第一个结点，则指针变量p和指针变量head之间的关系是p=_________和head=__________（设结点中的两个指针域分别为llink和rlink）。head->rlink，p->llink
13．设指针变量p指向双向链表中的结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为_________=p；s->right=p->right；__________=s； p->right->left=s；（设结点中的两个指针域分别为left和right）。s->left=p，p->right
14．设指针变量p指向单链表中结点A，指针变量s指向被插入的新结点X，则进行插入操作的语句序列为__________________________（设结点的指针域为
next）。s->next=p->next; p->next=s
15．在一个单链表HL 中，若要向表头插入一个由指针p指向的结点，则应执行语句：。p->next=HL; HL=p;
16．在采用独立结点构成的双向链表中，设p和q 分别是具有Dnode * 类型的指针变量。若双向链表中p结点之后插入一个q结点，其操作步骤为：
；
；
；
；
q->right=p->right;
if (p->right) p->right->left=q;
q->left=p;
p->right=q;
17．对于一个顺序存储的线性表，在表头插入元素的时间复杂度为____________,在表尾插入元素的时间复杂度为________________。O(n) O(1)
18．在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动___n-i+1_____个元素。
19．设双链表中结点的前趋指针和后继指针的域名分别为t1和r1，指针s指向双链表中的一个结点（该结点既非头结点，也非尾结点），则删除s指针所指向结点的操作为“s->tl->r1=s->r1；”和“__s->rl->tl=s->tl_______”。
20．设有指针head指向不带表头结点的单链表，用next表示结点的一个链域，指针p指向与链表中结点同类型的一个新结点。现要将指针p指向的结点插入表中，使之成为第一个结点，则所需的操作为“p→next=head；”和“__head=p________”。
21．单链表中逻辑上相邻的两个元素在物理位置上_____不一定_____相邻。22．在一个长度为n的数组中删除第i个元素（1≤i≤n）时，需要向前移动的元素的个数是_____n-i_____。
23．在顺序表上读表元算法的时间复杂度为___O（1）____。
24．双链表中前驱指针为prior，后继指针为next，在指针P所指结点前插入指针S所指的结点，需执行下列语句：
S→next=P;S→prior=P→prior;P→prior=S;__p->prior->next=s_____;
25．设某非空双链表，其结点形式为若要删除指针q所指向的结点，则需执行下述语句段：
q->prior->next＝q->next; _q->next->prionr=p->prior____。
26．对长度为n的顺序表执行删除操作，其删除算法在最坏情况下的时间复杂性为__O（n）。
27．在一个长度为n的顺序表中插入一个元素，最少需要移动元素，最多需要移动元素，0，n;
28．双向循环链表的优点是既可以方便的找到后继结点又可以方便的找到前驱结点。
29．在一个长度为n的顺序表中删除一个元素，最少需移动个元素，最多需移动________个元素。0 n－1
30．在长度为n的顺序表中插入第i个元素（假设i值可操作），要将元素从第
个到第 个元素向 （前或后）移动。 n 、 i+1 、 后
31．将指向单链表中的某个结点的指针p 移动到该结点的后继结点表示
为 。 p=p->next
32．在线性表的单链接存储结构中，每个结点包含有两个域，一个叫 域，另一个叫 域。元素值、指针
33．在下面数组a 中链接存储着一个线性表，表头指针为a[0].next ，则该线性
表为 。
( 38 , 56 , 25 , 60 , 42 , 74 )
34．对于一个长度为n 的顺序存储的线性表，在表头插入元素的时间复杂度
为 ，在表尾插入元素的时间复杂度为 。O(n)、O(1)
35．对于一个长度为n 的单链接存储的线性表，在表头插入元素的时间复杂度
为 ，在表尾插入元素的时间复杂度为 。O (1)、O(n)
36．在线性表的顺序存储中，若一个元素的下标为i ，则它的前驱元素的下标
为 ，后继元素的下标为 。i-1、i+1
37．在线性表的单链接存储中，若一个元素所在结点的地址为p ，则其后继结点
的地址为 ，若假定p 为一个数组a 中的下标，则其后继结点的下标
为 。p->next 、a[p].next
38．在循环单链表中，最后一个结点的指针指向 结点。表头
39．在双向链表中每个结点包含有两个指针域，一个指向其 结点，
另一个指向其 结点。前驱、后继
40．在循环双向链表中表头结点的左指针域指向 结点，最后一个结
点的右指针域指向 结点。表尾、表头
41．在以HL 为表头指针的带表头附加结点的单链表和循环单链表中，链表为空
的条件分别为 和 。HL->next = = NULL 、
HL->next = = HL
42．队列的插入操作在 进行，删除操作在 进行。队尾、队首
43．栈又称为 表，队列又称为 表。后进先出(LIFO)、先进先
出(FIFO)
44．向一个顺序栈插入一个元素时，首先使 后移一个位置，然后把待插
入元素 到这个位置上。栈顶指针、存储
45．从一个栈中删除元素时，首先取出 ，然后再前移一位 。
栈顶元素、栈顶指针
46．在一个循环顺序队列Q 中，判断队空的条件为 ，判断队满的条件
为 。front = = rear 、(rear+1)%QueueMaxSize = = front
47．在一个顺序栈中，若栈顶指针等于 ，则为空栈；若栈顶指针等
于 ，则为满栈。–1 、StackMaxSize-1
48．在一个链栈中，若栈顶指针等于NULL ，则为 ；在一个链队中，若
队首指针与队尾指针的值相同，则表示该队列为 或该队列为 。栈
a data next
空、空队、队列只有一个元素
49．在下面的数组a中链接存储着一个线性表，表头指针为a[o].next，则该线
性表为_________________________________________________。
a 0 1 2 3 4 5 6 7
8
dat Array a
nex
t
（38，56，25，60，42，74）；
50．在以HL为表头指针的带表头附加结点的单链表和循环单链表中，判断链表
为空的条件分别为________________和____________________。HL→next
=NULL； HL=HL→next；
51．用具有n个元素的一维数组存储一个循环队列，则其队首指针总是指向队首
元素的___________，该循环队列的最大长度为__________。前一个位置； n-1；52．当堆栈采用顺序存储结构时，栈顶元素的值可用———————表示；当堆
栈采用链接存储结构时，栈顶元素的值可用_______________表示。S.stack
[S.top]; HS→data;
53．设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单
链表中data为x的结点，指针py指向data为y的新结点 , 若将结点y插入结
点x之后，则需要执行以下语句:_______； ______;【华中理工大学 2000 一.4
（2分）】py->next=px->next; px->next=py
54．在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，
需向后移动________个元素。【北京工商大学 2001 二.4（4分）】n-i+1
55．在单链表中设置头结点的作用是________。【哈尔滨工业大学 2000 二.1
（1分）】有头结点后，插入元素和删除元素的算法统一了，不再需要判断是否
在第一个元素之前插入和删除第一个元素。另外，不论链表是否为空，链表指针
不变。
56．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时
间复杂度为________,在给定值为x的结点后插入一个新结点的时间复杂度为
________。【哈尔滨工业大学 2001 一.1（2分）】 O(1)，O(n)
57．在双向循环链表中,向p所指的结点之后插入指针f所指的结点，其操作是
_______、_______、_______、________。【中国矿业大学 2000 一.1（3分）】
f->next=p->next; f->prior=p; p->next->prior=f; p->next=f;
58．顺序存储结构是通过________表示元素之间的关系的;链式存储结构是通过
________表示元素之间的关系的。【北京理工大学 2001 七.2 （2分）】物理
上相邻指针
59．在单链表L中，指针p所指结点有后继结点的条件是：________
【合肥工业大学 2001 三.3 （2分）】p->next!=null
60.单链表与多重链表的区别是。链域数目不同
三、判断题
1．（）线性表的顺序存储结构比链式存储结构更好。F
2．( )线性表就是顺序存储的表。×
3．（）线性表中的所有元素都有一个前驱元素和后继元素。F
4．（）非空的双向循环链表中任何结点的前驱指针均不为空。T
5．（）不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。T
6．( )对链表进行插入和删除操作时不必移动链表中结点。T
7．( )线性表只能用顺序存储结构实现。×
8．( )如果某数据结构的每一个元素都最多只有一个直接前驱和一个直接后继，则该数据结构必为线性表。×
9．( )进栈操作时，必须判断栈是否已满。×
10．( )进栈、出栈操作的时间复杂度是O(n)。×
11．( )采用链式结构存储线性表时，其地址可以是不连续的。√
12．( )线性表中的每个元素都有一个前驱元素和后继元素。×
13．( )采用顺序结构存储线性表时，其地址可以是不连续的。×
14．（）如果某数据结构的每一个元素都最多只有一个直接前驱和一个直接后继，则该数据结构必为线性表。√
15．（）线性表的唯一存储形式就是链表。×
16．（）线性表不能采用链式存储。×
17．（）在单链表中插入结点主要通过移动元素实现。×
18．( )所谓静态链表就是一直不发生变化的链表。×
19．( )集合与线性表的区别在于是否按关键字排序。×
20．（）用头部插入结点的方法建立单链表时，插入元素的顺序和链表中的元素顺序相同。×
21．（）线性表中的每个元素都有一个前驱元素和后继元素。×
22．（）线性表中每个元素都有一个直接前驱和一个直接后继。×
23．（）线性表采用顺序存储表示时，必须占用一片连续的存储单元。√24．( )数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构。×
25．( )数据的逻辑结构是指数据的各数据项之间的逻辑关系。×
26．()算法的优劣与算法描述语言无关，但与所用计算机有关。×27．( )健壮的算法不会因非法的输入数据而出现莫名其妙的状态。√28．（）算法的运行时间涉及加、减、乘、除、转移、存、取、等基本运算。要想准确地计算总运算时间是不可行的。×
29．( )数据的物理结构是指数据在计算机内的实际存储形式。√
30．( )数据结构的抽象操作的定义与具体实现有关。×
31．( )数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。√
32．（）算法独立于具体的程序设计语言，与具体的计算机无关。√
33．（）Huffman树、平衡二叉树都是数据的逻辑结构。√
34．（）抽象数据类型与计算机内部表示和实现无关。√
35．（）在一个设有头指针和尾指针的单链表中,执行删除该单链表中最后一个元素的操作与链表的长度无关。×
36．( )顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。×
37．（）顺序存储方式只能用于存储线性结构。×
38．( ) 线性表只能用顺序方式存放。X
39．( ) 在带表头结点的双循环链表中，每个结点的前趋和后继指针均不为空。√
40．（）顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半的元素需要移动。×
41．( )顺序存储方式的优点是存储密度大，且插入、删除运算效率高。×42．（）在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。×
43. （）在单链表中，要取得某元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。×
四、简答题
1．线性结构与非线性结构的差别
前驱与后继之间通常为一对多或多对多的关系。
2．比较顺序表与单链表的优缺点。
顺序表优点：随机查找，存储密度大
顺序表缺点：插入、删除不便，静态分配，表长固定
单链表优点：插入、删除方便，动态分配，表长灵活
单链表缺点：查找不便，存储密度小
3．简要说明算法与程序的区别。
算法是解决特定问题的操作序列，可以用多种方式描述。程序是算法在计算机中的实现，与具体的计算机语言有关。
4．说明以下三个概念的关系：头指针，头结点，首元素结点。
头指针指向头结点，头结点的后继域指向首元素结点。
5．设有编码为A，B，C，D的4列火车，依次进入一个栈式结构的站台，试写出这4列火车开出站台的所有可能的顺序。
根据栈的数学性质，n个元素的出栈序列数目恰好符合卡塔南数列。
C n =C
2n
n/(n+1)=1/n+1*(2n)!/n!(2n-n)!
这里:
1/n+1*(2n)!/n!(2n-n)!=1/5*8!/(4!*4!)=14
ABCD ABDC ACBD ACDB ADCB
BACD BADC BCAD BCDA BDCA
CBAD CBDA CDBA DCBA
分析解答：
6．写出在双向链表中，在指针p所指结点前插入一个结点*S的语句序列。答：
答：（1）S->prior=P->prior; （2）P->prior->next=S; （3）S->next=P; （4）P->prior=S;
7．试叙述一维数组与有序表的异同。
一维数组属于特殊的顺序表，和有序表的差别主要在于有序表中的元素按值排列（非递增或非递减），而一维数组中的元素没有按元素值排列顺序的要求。8．试比较顺序存储和链式存储的优缺点。
顺序存储查找效率高，插入和删除效率低；链式存储插入和删除效率高，查找效
第2章线性表 一、选择题 1. 链表不具备的特点是（）。 A．可随机访问任意结点 B. 插入删除不需要移动元素 C. 不必事先估计存储空间 D. 所需空间与其长度成正比 2. 不带头结点的单链表head为空的判定条件是（）。 ==NULL B. head->next==NULL >next==head !=NULL 3.带头结点的单链表head为空的判定条件是（）。 ==NULL B. head->next==NULL >next==head !=NULL 4．带头结点的双循环链表L为空表的条件是（）。 A．L==NULL B．L->next->==NULL C．L->prior==NULL >next==L 5.非空的循环链表head的尾结点（由P所指向）满足（）。 A．p->next==NULL B．p==NULL C．p->next==head ==head 6.在循环双链表的p所指结点之前插入s所指结点的操作是（）。 A．p->prior=s;s->next=p;p->prior->next=s;s->prior=p->prior; B．p->prior=s;p->prior->next=s;s->next=p;s->prior=p->prior; C．s->next=p;s->prior=p->prior;p->prior=s;p->right->next=s; D. s->next=p;s->prior=p->prior;p->prior->next=s;p->prior=s; 7.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用（）存储方式最节省运算时间。 A．单链表 B．给出表头指针的单循环链表 C．双链表 D. 带头结点的双循环链表 8.某线性表最常用的操作是在最后一个结点之后插入一个节点或删除第一个结点，故采用（）存储方式最节省运算时间。 A．单链表 B．仅有头结点的单循环链表 C．双链表 D. 仅有尾指针的单循环链表 9.需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是（）。 A．单链表 B．静态链表 C．线性链表 D. 顺序存储结构 10.如果最常用的操作是取第i个结点及前驱，则采用（）存储方式最节省时间。 A．单链表 B．双链表 C.单循环链表 D.顺序表 11.在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（）。 A．O(1) B．O(n) C．O(n*n) D. O(nlog2n) 12.在一个长度为n(n>1)的单链表上，设有头和尾两个指针，执行()操作与链表的长度有关。A．删除单链表中的第一个元素 B．删除单链表中的最后一个元素 C. 在单链表第一个元素前插入一个新元素 D.在单链表最后一个元素后插入一个新元素 13.设线性表有n个元素，以下算法中，()在顺序表上实现比在链表上实现效率更高。A．输出第i(0<=i<=n-1)个元素值 B．交换第0个元素与第1个元素的值 C. 顺序输出这n个元素的值 D.输出与给定值x相等的元素在线性表中的序号 14.设线性表有2n个元素，算法()，在单链表上实现比在顺序表上实现效率更高。 A．删除所有值为x的元素 B．在最后一个元素的后面插入一个新元素 C. 顺序输出前k个元素 D.交换第i个元素和第2n-i-1个元素的值(i=0,1,…,n-1)
数据结构试题 一、单选题 1、在数据结构的讨论中把数据结构从逻辑上分为（C ） A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。 2、采用线性链表表示一个向量时，要求占用的存储空间地址（D ） A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续的 D 可连续可不连续 3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（ D ）。 A n B n/2 C (n-1)/2 D (n+1)/2 4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ D ）。 A s→link = p→link;p→link = s; B p→link = s; s→link = q; C p→link = s→link;s→link = p; D q→link = s;s→link = p; 5、如果想在4092个数据中只需要选择其中最小的5个，采用（ C ）方法最好。 A 起泡排序 B 堆排序 C 锦标赛排序 D 快速排序 6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（ B ）。 A 求子串 B 模式匹配 C 串替换 D 串连接 7、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放
该数组至少需要的存储字数是（ C ）。 A 80 B 100 C 240 D 270 8、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。 A 栈 B 队列 C 循环队列 D 优先队列 9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ C ）。 10、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ D ）。 A ( front - rear + 1) % m B ( rear - front + 1) % m C ( front - rear + m) % m D ( rear - front + m) % m 11、一个数组元素a[i]与（ A ）的表示等价。 A *（a+i） B a+i C *a+i D &a+i 12、若需要利用形参直接访问实参，则应把形参变量说明为（ B ）参数。 A 指针 B 引用 C 值 D 变量 13、下面程序段的时间复杂度为（ C ） for (int i=0;i 第二章线性表 1、描述一下三个概念的区别：头指针，头结点，首元结点。并给予图示。 2、对于有头结点的单链表，分别写出定位成功时，实现下列定位语句序列。(1)定位到第i 个结点a i ； (2)定位到第i 个结点的前驱a i-1； (3)定位到尾结点； (4)定位到尾结点的前驱。 3、已知L 是有表头结点的单链表，且P 结点既不是首元结点，也不是尾结点，试写出实现下列功能的语句序列。 (1)在P 结点后插入S 结点；(2)在P 结点前插入S 结点；(3)在表首插入S 结点；(4)在表尾插入S 结点 . p=head; p=head; j=0; while ( p && jnext; j++;} p=head; j=0; while ( p && j 4、设计算法：在顺序表中删除值为e 的元素，删除成功，返回1；否则，返回0。 5、设计一个算法，将一个带头节点的数据域依次为a 1，a 2，…，a n （n ≥3）的单链表的所有节点逆置，即第一个节点的数据域变为a n ，…，最后一个节点的数据域为a 1。（注意：先用自然语言描述算法基本思想，然后用类C++语言描述） int Sqlist 习题二 一、选择题 1．在一个长度为n的顺序表中删除第i个元素（0＜i 第二章习题 1.描述以下三个概念的区别：头指针，头结点，首元素结点。 2.填空： （1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 （2）在顺序表中，逻辑上相邻的元素，其物理位置相邻。在单链表中，逻辑上相邻的元素，其物理位置相邻。 （3）在带头结点的非空单链表中，头结点的存储位置由指示，首元素结点的存储位置由指示，除首元素结点外，其它任一元素结点的存储位置由指示。3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是：。 b. 在P结点前插入S结点的语句序列是：。 c. 在表首插入S结点的语句序列是：。 d. 在表尾插入S结点的语句序列是：。 供选择的语句有： （1）P->next=S; （2）P->next= P->next->next; （3）P->next= S->next; （4）S->next= P->next; （5）S->next= L; （6）S->next= NULL; （7）Q= P; （8）while(P->next!=Q) P=P->next; （9）while(P->next!=NULL) P=P->next; （10）P= Q; （11）P= L; （12）L= S; （13）L= P; 4.设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 5.写一算法，从顺序表中删除自第i个元素开始的k个元素。 6.已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。 7.试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）。 （1）以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。 （2）以单链表作存储结构。 8.假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（即A 表和B表的）结点空间存放表C。 填空题（10 * 1’ = 10’） 一、概念题 .当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。 .当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。 .带头结点的单链表L中只有一个元素结点的条件是L->Next->Next==Null。 .循环队列的引入，目的是为了克服假溢出。 .长度为0的字符串称为空串。 .组成串的数据元素只能是字符。 .设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。 .为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。 .广义表的深度是广义表中括号的重数 .有向图G可拓扑排序的判别条件是有无回路。 .若要求一个稠密图的最小生成树，最好用Prim算法求解。 . 直接定址法法构造的哈希函数肯定不会发生冲突。 .排序算法所花费的时间，通常用在数据的比较和交换两大操作。 .通常从正确性﹑可读性﹑健壮性﹑时空效率等几个方面评价算法的（包括程序）的质量。 .对于给定的n元素，可以构造出的逻辑结构有集合关系﹑线性关系树形关系﹑图状关系四种。 .存储结构主要有顺序存储﹑链式存储﹑索引存储﹑散列存储四种。 .抽象数据类型的定义仅取决于它的一组逻辑特性，而与存储结构无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。 .一个算法具有五大特性：有穷性﹑确定性﹑可行性，有零个或多个输入﹑有一个或多个输入。 .在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句：s->prior= p->prior; s->next= p; p->prior- next= s; p->prior= s;。 .在单链表中设置头结点的作用是不管单链表是否为空表，头结点的指针均不空，并使得对单链表的操作（如插入和删除）在各种情况下统一。 .队列是限制在表的一端进行插入和在另一端进行删除的线性表，其运算遵循先进先出原则。 .栈是限定尽在表位进行插入或删除操作的线性表。 .在链式队列中，判定只有一个结点的条件是(Q->rear==Q->front)&&(Q->rear!=NULL)。 .已知链队列的头尾指针分别是f和r，则将x入队的操作序列是node *p=(node *)malloc(node); p->next=x; p->next=NULL; if(r) {r->next=p; r=p;} else {r=p; f=p;}。 .循环队列的满与空的条件是(rear+1)%MAXSIZE==fornt和(front=-1&&rear+1==MAXSIZE)。 .串是一种特殊的线性表，其特殊性表现在数据元素都是由字符组成。 .字符串存储密度是串值所占存储位和实际分配位的比值，在字符串的链式存储结构中其结点大小是可变的。 .所谓稀疏矩阵指的是矩阵中非零元素远远小于元素总数，则称该矩阵为矩阵中非零元素远远小于元素总数，则称该矩阵为稀疏矩阵。 .一维数组的逻辑结构是线性结构，存储结构是顺序存储结构；对二维或多维数组，分别按行优先和列优先两种不同的存储方式。 .在有向图的邻接矩阵表示中，计算第i个顶点入度的方法是求邻接矩阵中第i列非0元素的个数。 网中，结点表示活动，边表示活动之间的优先关系，AOE网中，结点表示事件，边表示活动。 .按排序过程中依据不同原则对内部排序方法进行分类，主要有选择排序﹑交换排序﹑插入排序归并排序等4类。 .在堆排序、快速排序和归并排序中若只从排序结果的稳定性考虑，则应选择归并排序方法；若只从平均情况下排序最快考虑，则应选择快速排序方法；若只从最坏情况下排序最快且要节省类存考虑，则应选择堆排序方法。 .直接插入排序用监视哨的作用是存当前要的插入记录，可又省去查找插入位置时对是否出界的判断。 .设表中元素的初始状态是按键值递增的，则直接插入排序最省时间，快速排序最费时间。 .下列程序判断字符串s是否对称，对称则返回1，否则返回0；如?(“abba”)返回1，?（”abab”）返回0. Int f (char*s) { Int i=0,j=0; 求串长*/ 第二章地理信息系统空间数据结构 2.1 地理空间数据及其特征 【学时安排】 1 学时 【目的要求】 1、掌握地理信息系统的数据类型； 2、理解地理信息系统的数据来源； 3、掌握空间数据的特点。 【重点难点】 地理信息系统的数据类型与特征。 【教学方法与手段】 示例式教学方法，多媒体教学手段。 一、GIS空间数据的来源与类型 空间数据是GIS的核心，也有人称它是GIS的血液，因为GIS的操作对象是空间数据，因此设计和使用GIS 的第一步工作就是根据系统的功能，获取所需要的空间数据，并创建空间数据库。 1、地理数据的来源 GIS中的数据来源和数据类型繁多，概括起来主要有以下几种来源： ⑴地图数据。来源于各种类型的普通地图和专题地图，这些地图的内容丰富，图上实体间的空间关系直观，实体的类别或属性清晰，实测地形图还具有很高的精度，是地理信息的主要载体，同时也是地理信息系统最重要的信息源。 ⑵影像数据。主要来源于卫星遥感和航空遥感，包括多平台、多层面、多种传感器、多时相、多光谱、多角度和多种分辨率的遥感影像数据，构成多源海量数据，也是GIS的最有效的数据源之一。 ⑶地形数据。来源于地形等高线图的数字化，已建立的数字高程模型( DEM和其他实 测的地形数据等。 ⑷属性数据。来源于各类调查报告、实测数据、文献资料、解译信息等。 ⑸元数据。来源于由各类纯数据通过调查、推理、分析和总结得到的有关数据的数据，例如数据来源、数据权属、数据产生的时间、数据精度、数据分辨率、源数据比例尺、数据转换方法等。 2、空间数据的类型 空间数据根据表示对象的不同，又具体分为七种类型(图2-1) ，它们各表示的具体内容 如下： (1) 类型数据。例如考古地点、道路线、土壤类型的分布等。 (2) 面域数据。例如随机多边形的中心点，行政区域界线、行政单元等。 (3) 网络数据。例如道路交点、街道、街区等。 (4) 样本数据。例如气象站、航线、野外样方分布区等。 (5) 曲面数据。例如高程点、等高线、等值区域等。 (6) 文本数据。例如地名、河流名称、区域名称等。 (7) 符号数据。例如点状符号、线状符号、面状符号(晕线) 等。 一、单选题（每题2 分，共20分） 1. 1.对一个算法的评价，不包括如下（B ）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结 点，则执行( A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 3.对线性表，在下列哪种情况下应当采用链表表示？(B ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种（ D ）。 A．有向图B．无向图C．无向无环图D．有向无环图 6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（B）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.7.若需要利用形参直接访问实参时，应将形参变量说明为（D ）参数。 A．值B．函数C．指针D．引用 8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具 有相同的（A）。 A．行号B．列号C．元素值D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为（D ）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( C )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、二、运算题（每题 6 分，共24分） 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M 对N（M：N）的联系时，称这种结构为_____________________。 2. 2.队列的插入操作是在队列的___尾______进行，删除操作是在队列的 ____首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则 表示栈满的条件是___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度 为____O(1)_____，在表尾插入元素的时间复杂度为____O n________。 第一章概论 一、选择题 1、研究数据结构就是研究（D ）。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作（研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作） 2、算法分析的两个主要方面是（ A ）。 A. 空间复杂度和时间复杂度 B. 正确性和简单性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。（线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素，有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继）（链表、栈、队列、数组、串） A. 图 B. 树 C. 广义表（线性表的推广） D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（B ）等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是（ C ）。 for(i=0;i 6、算法是（D ）。为了解决某一问题而规定的一个有限长的操作序列 A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 7、某算法的语句执行频度为（3n+nlog2n+n2+8）,其时间复杂度表示（C ）。 A. O(n) B. O(nlog2n) C. O(n2) D. O(log2n) 8、下面程序段的时间复杂度为（ C ）。 i=1; while(i<=n) i=i*3; A. O(n) B. O(3n) C. O(log3n) D. O(n3) 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（B ）和运算等的学科。（关系和操作） A. 结构 B. 关系 C. 运算 D. 算法 10、下面程序段的时间复杂度是（ A ）。 i=s=0; while(s 《数据结构-C语言版》 第一章绪论 单项选择题 1．在数据结构中，数据的基本单位是_____ ____。 A. 数据项 B. 数据类型 C. 数据元素 D. 数据变量 2．数据结构中数据元素之间的逻辑关系被称为__ ____。 A. 数据的存储结构 B. 数据的基本操作 C. 程序的算法 D. 数据的逻辑结构3．在数据结构中，与所使用计算机无关的是数据的____ ___。 A. 存储结构 B. 逻辑和物理结构 C. 逻辑结构 D. 物理结构4．在链式存储结构中，数据之间的关系是通过____ ____体现的。 A. 数据在内存的相对位置 B. 指示数据元素的指针 C. 数据的存储地址 D. 指针 5．计算算法的时间复杂度是属于一种____ ___。 A. 事前统计的方法 B. 事前分析估算的方法 C. 事后统计的方法 D. 事后分析估算的方法 6．在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是____ __。 A. n2 B. nlogn C. n D. logn 7．设使用某算法对n个元素进行处理，所需的时间是T(n)=100nlog2n+200n+2000，则该算法的渐近时间复杂度为____ ___。 A. O(1) B. O(n) C. O(200n) D. O(nlog2n) CDCBBDD 第二章线性表 单项选择题 1．链表不具有的特点是____ ____。 A. 可随机访问任一元素 B. 插入和删除时不需要移动元素 C. 不必事先估计存储空间 D. 所需空间与线性表的长度正比 2．设顺序表的每个元素占8个存储单元。第1个单元的存储地址是100，则第6个元素占用的最后一个存储单元的地址为。 A. 139 B. 140 C. 147 D. 148 3．在线性链表存储结构下，插入操作算法。 A. 需要判断是否表满 B. 需要判断是否表空 C. 不需要判断表满 D. 需要判断是否表空和表满 4．在一个单链表中，若删除p所指结点的后继结点，则执行。 A. p->next = p->next->next; B. p->next = p->next; C. p = p->next->next; D. p = p->next; p->next = p->next->next; 5．将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为。A. O(n) B. O(1) C. O(m) D. O(m+n) 6．需要预分较大空间，插入和删除不需要移动元素的线性表，其存储结构是。 A. 单链表 B. 静态链表 C. 线性链表 D. 顺序存储方式ACCABB 填空题 1．在带表头结点的单链表中，当删除某一指定结点时，必须找到该结点的_____结点。2．在单链表中，指针p所指结点为最后一个结点的条件是。 3．将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是。4．在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动元素的个数是。 5．在长度为n的顺序表中插入一个元素的时间复杂度为。 1前驱 2 p->next==NULL 《数据结构》第二章练习题 1.单项选择题 2.1链表不具备的特点是（） A 可随机访问任一结点 B 插入删除不需要移动元素 C 不必事先估计存储空间 D 所需空间与其长度成正比 2.2 不带头节点的单链表head为空的判定条件是（） A head==NULL B head->next==NULL C head->next==head D head!=NULL 2.3带头节点的单链表head为空的判定条件是（） A head==NULL B head->next==NULL C head->next==head D head!=NULL 2.4 带头结点的双循环链表L为空的条件是（） A L==NULL B l->next->==NULL C L->prior==NULL D L->next==L 2.5 非空的循环单链表head尾结点（由P所指向）满足（) A P->next==NULL B P==NULL C P->next==head D P==head 2.6在双循环链表中的P所指结点之前插入s所指结点的操作是（） A p->prior=s;s->next=p;p->prior>next=s;s->prior=p->prior; B p->prior=s;p->prior>next=s;s->next=p;s->prior=p->prior; C s->next=p;s->prior=p->prior; p->prior=s;p->right->next=s; D s->next=p;s->prior=p->prior;p->prior->next=s;p->prior=s; 2.7若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用（）存储方式最节省运算时间 A 单链表 B 给出表头指针的单循环链表 C 双链表 D 带头结点的双循环链表 2.8某线性表最常用的操作时在最后一个结点之后插入一个结点或删除第一个结点，故采用（）存储方式最节省运算时间 A 单链表B仅有头结点的单循环链表 第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 2.6．数据的存储结构主要有哪两种？它们之间的本质区别是什么？ 答：主要有：顺序存储结构和链式存储结构两种。 区别: 顺序存储结构是借助元素在存储器的相对位置来表示数据间的逻辑关系，而链式存储结构是借助指针来表示数据间的逻辑关系。 2.7 设数据结构的集合为D={d1,d2,d3,d4,d5},试指出下列各关系R所对应的数据结构B=(D,R)中哪些是线性结构，哪些是非线性结构。 （1）R={(d1,d2),(d2,d4),(d4,d2),(d2,d5),(d4,d1)}; ( 2 ) R={(d5,d4),(d4,d3),(d3,d1),(d1,d2)}; ( 3 ) R={(di,di+1)|i=4,3,2,1}; ( 4 ) R={(di,dj)|i 2.〉链表：扩展性强，易于删除，添加；内存中地址非连续；长度可以实时变化；适用于需要进行大量增添或删除元素操作而对访问元素无要求的程序。 （2）缺点 顺序表：插入，删除操作不方便；扩展性弱；不易删除，添加。 链表：不易于查询，索引慢。 （3）顺序表和链表的优缺点是互相补充的关系。 2.17 试比较单向链表与双向链表的优缺点。 答：（1）优点 单向链表：耗存储空间小； 双向链表：可以从任何一点开始进行访问; （2）缺点： 单向链表：访问时必须从头开始，耗时。 双向链表：耗存储空间大。 （3）两者为互补关系 2.22 CQ[0:10]为一循环队列，初态front=rear=1,画出下列操作后队的头，尾指示器状态： （1）d,e,h,g,入队； （2）d,e出队； （3）I,j,k,l,m入队； （4）b出队； 试卷一 一、单选题（每题 2 分，共20分） 1. 对一个算法的评价，不包括如下（）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2. 在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 7. 若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8. 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。 A．行号B．列号C．元素值D．非零元素个数 二、填空题（每空1分，共28分） 1. 数据结构是指数据及其相互之间的______________。当结点之间存在M对N（M：N）的联系时，称这种结构为_____________________。 2. 队列的插入操作是在队列的___尾______进行，删除操作是在队列的____首______进行。 3. 当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是___top==0_____________。 4. 对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为_________，在表尾插入元素的时间复杂度为____________。 7. 二叉树是指度为2的____________________树。一棵结点数为N的二叉树，其所有结点的度的总和是_____________。 8. 对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个______________。对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的__________________。 9. 对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为_____________个，其中_______________个用于指向孩子，_________________个指针是空闲的。 10. 若对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到一维数组A中，即编号为0的结点存储到A[0]中。其余类推，则A[ i ]元素的左孩子元素为________,右孩子元素为 第一章绪论 一、选择题 1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像 2 A.结构 B.关系 C.运算 D.算法 2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。 1 A.算法 B.数据元素 C.数据操作 D.逻辑结构 2 A.操作 B.映像 C.存储 D.关系 3.在数据结构中，从逻辑上可以把数据结构分成。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。A.随机存取 B.顺序存取 C.索引存取 D.散列存取 5.算法分析的目的是1，算法分析的两个主要方面其一是指2，其二是指正确性和简单性。1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2 A.空间复杂度和时间复杂度 B.研究算法中的输入和输出的关系 C.可读性和文档性 D.数据复杂性和程序复杂性k 6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。 1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。A.正确 B.不正确 8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。 A.必须连续的 B.部分地址必须连续的 C.一定是不续的D连续不连续都可以 9.以下的叙述中，正确的是。A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。A.正确B.不正确 二、填空题1.数据逻辑结构包括三种类型、和，树形结构和图形结构合称为。2.在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。3.算法的五个重要特性是、、、、。 4.下面程序段的时间复杂度是。 for( i = 0; i < n; i++) for( j = 0; j < m; j++) A[i][j] = 0; 5.下面程序段的时间复杂度是。 i = s = 0; while ( s < n) { i ++; /* i = i +1*/ s += i; /* s = s + i*/ } 6.下面程序段的时间复杂度是。 s = 0; for( i = 0; i < n; i++) for( j = 0; j < n; j++) s += B[i][j]; sum = s; 7.下面程序段的时间复杂度是。 i = 1; while ( i <= n ) i = i * 3; 第二章空间数据结构和空间数据库本章概述：地理信息系统的操作对象是空间地理实体，建立一个地理信息系统的首要任务是建立空间数据库，即将反映地理实体特性的地理数据存储在计算机中，这需要解决地理数据具体以什么形式在计算机中存储和处理即空间数据结构问题和如何描述实体及其相互关系即空间数据库模型问题。本章重点介绍主要的空间数据结构和空间数据库模型。 §2.1 地理实体及其描述 介绍地理实体的概念，地理实体需要描述的内容，实体的空间特征和实体间的空间关系。 §2.2 矢量数据结构 讲述矢量数据的图形表示、获取方式和表示(即矢量编码方法)。§2.3 栅格数据结构 讲述栅格数据的图形表示、栅格数据的组织、栅格结构的建立和栅格数据的表示。 §2.4 矢量栅格一体化数据结构 针对矢量栅格数据结构互为优缺点状况，介绍集两者优点为一体的矢量栅格一体化数据结构的概念和具体数据结构设计方法。 §2.5 三维数据结构 主要阐述基于栅格的八叉树三维数据结构的基本原理和存储结构。在矢量结构方面，介绍常用的三维边界表示法的方法原理、特点和应用。§2.6 空间数据模型 首先介绍数据库有关基础知识，传统数据模型如何存储图形数据及其局限性，重点阐述面向对象技术、面向对象模型和用于地理信息系统的空间数据库管理系统的类型。 §2.7 空间数据库的设计、建立和维护 介绍空间数据库的设计的内容、建立过程和维护方法。 您可能还想看前贴【GIS原理学习（一）】【GIS原理学习（二）】【GIS 原理学习（三）】【GIS原理学习（四）】 §2.1 地理实体及其描述 地理信息系统是以地理实体作为描述、反映现实世界中空间对象的单体。在地理信息系统中需要描述地理实体的名称、位置、形状、功能等内容，这些内容反映了地理实体的时间、空间和属性三种特性，其中空数据结构第二章线性表测试题
数据结构线性表2答案
(完整版)数据结构课后习题及解析第二章
数据结构课后习题及答案
地理信息系统空间数据结构
数据结构试题及答案
数据结构试题答案
数据结构复习题目和答案
数据结构第二章练习题 - 副本
数据结构习题与答案
第二章数据结构习题作业
数据结构试题及答案修2
数据结构作业及答案
第二章 空间数据结构和空间数据库
相关主题
文本预览