数据结构习题

第一章绪论

一、填空题

1．数据是描述客观事物的数、字符以及所有能输入到计算机且能够被计算机程序加工处理的符号集合。_________是数据的基本单位；___________是数据的最小单位。通常被计算机加工处理的数据不是孤立无关的，而是彼此之间存在着某种联系，将这种数据间的联系称为________。

2．数据结构进行形式化定义时，可以从逻辑上认为数据结构DS是_________的集合D和D上_________的集合R所构成的二元组：DS=（D，R）。

3．已知某数据结构的二元组形式表示为：A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，

06>，<03，07>，<03，08>，<03，09>}。则此数据结构属于_____________结构。4．一个算法的时间复杂度通常用问题规模大小的函数来表示，当一个算法的时间复杂度与问题规模n大小无关时，则表示为__________；成正比关系时，则表示为___________；成对数关系时，则表示为___________；成平方关系时，则表示为__________。

5．数据结构的逻辑结构包括_____________、树型结构和图型结构三种类型，其中树型结构和图型结构合称为_____________；数据结构的存储结构主要包括____________和____________两种类型。

6．线性结构的特点是：第一个结点_______前驱结点，其余结点有且仅有_______个前驱结点；最后一个结点_______后继结点，其余每个结点有且仅有_______个后继结点。

7．树型结构的特点是：根结点没有________结点，其余每个结点有且仅有________个前驱结点；叶子结点_________后继结点，其余结点可以有_________个后继结点。

8．图型结构的特点是：每个结点可以有_________个前驱结点和后继结点。

9．程序段for（i=1，s=0；s

二、分析下列用二元组形式表示的数据结构，指出他们分别属于何种类型的数据结构。

1.A=（K，R），其中：K={a，b，c，d，e，f，g，h}，R={r}，r={，

c>，，，，，}。

2.B=（K，R），其中：K={a，b，c，d，e，f，g，h}，R={r}，r={，

g>，，，，，}。

3.C=（K，R），其中：K={ a，b，c，d，e }，R={r}，r={，，，

，，，}。

4.D=（K，R），其中：K={48，25，64，57，82，36，75}，R={r1，r2}，r1={<25，

36>，<36，48>，<48，57>，<57，64>，<64，75>，<75，82>}；r2={<48，25>，

<48，64>，<64，57>，<64，82>，<25，36>，<25，75>}。

5.E=（K，R），其中：K={1，2，3，4，5，6，7}，R={r}，r={<1，2>，<2，1>，

<1，4>，<4，1>，<2，3>，<3，2>，<3，4>，<4，3>，<1，3>，<3，1>}。

三、指出下列各函数的功能并求出其时间复杂度。

1.void prime(int n)

int i;

for(i=2;i<=sqrt(n);i++) if (n %i==0) break;

if (i>sqrt(n)) printf(“yes”); else printf(“no”);

}

2.long sum1(int n)

{

long sum,w,i;

for(sum=0,i=1;i<=n;i++){ w=1; for(j=1;j<=i;j++) w=w×i; sum=sum+w; } return(sum);

}

3.long sum2(int n)

{

long sum,w,i;

for(sum=0, w=1,i=1;i<=n;i++){ w=w×i; sum=sum+w;}

return(sum);

}

4.void sort(int r[ ],int n)

{

int i,j;

for(i=1; i

if(r[j]>r[j+1]) {temp=r[j];r[j]=r[j+1];r[j+1]=temp;}

}

补充：

0.分析下面算法（程序段），给出最大语句频度，该算法的时间复杂度是__ __。

for (i=0;i

for (j=0;j

A[i][j]=0;

1 分析下面算法（程序段），给出最大语句频度，该算法的时间复杂度是__ __。

s=0;

for (i=0;i

for (j=0;j

for (k=0;k

s=s+B[i][j][k];

sum=s;

2 分析下面算法（程序段）给出最大语句频度，该算法的时间复杂度是__ __。

i=s=0;

while (s

{ i++;

s+=i; //s=s+i

}

3。分析下面算法（程序段）给出最大语句频度，该算法的时间复杂度是____。

i=1;

while (i<=n)

i=i*2;

补充答案：

0. N^2

1.N^3

2.根号N

3.log(N)

第一章参考答案

一、填空题

1． 数据元素，数据项，结构

2． 数据，关系

3． 树型

4． O(1)，O(n)，O(log 2n)，O(n 2)

5． 线性结构，非线性结构，顺序结构，链式结构

6． 无，一，无，一

7． 前驱，一，无，任意

8． 任意

9． O(n 1/2)

分析：设程序段中的循环体执行k 次，则有不等式∑∑+==≤<1

11k i k i i n i 成立，解此不等式得到不等式2/14/122/34/12-+<≤-+n k n ，因此)()(n O k n f ==。

10． O(1)

二、分析下列用二元组形式表示的数据结构，指出他们分别属于何种类型的数据结构。

1． 线性结构

2． 树型结构

3． 图型结构

4． 图型结构

分析：数据结构D 中的关系集合R 有两个关系r1和r2。如果只考虑关系r1，则为线性结构；如果只考虑关系r2，则为树型结构；如果把关系r1和r2联合起来考虑，则为图型结构。

5． 图型结构

分析：若用图形来表示则可以看出r 是E 上的对称关系，为了简化起见，我们通常把和这两个有序偶对用一个无序偶对(x ，y)或(y ，x)来代替。在用图形表示时，我们把x 结点和y 结点之间两条相反的弧用一条无向边来代替。

三、指出下列各函数的功能并求出其时间复杂度。

1． 函数的功能是判断n 是否是一个素数，其时间复杂度为O(n 1/2)。

分析：函数prime 中出现的库函数sqrt 为平方根函数，因此

)(1)(n O n n f =-=。

2． 函数的计算∑=n

i i 1

!的值，其时间复杂度为O(n 2)。 3． 函数的计算∑=n

i i 1

!的值，其时间复杂度为O(n)。

4． 函数的功能是对数组r 中的n 个元素进行冒泡排序，其时间复杂度为O(n 2)。 分析：)(2/)1()()(21n

O n n i n n f n =-=-=∑-。

第二章线性表

一、填空题

1．设长度为n的顺序线性表在任何位置上插入或删除操作都是等概率的，则插入一个元素时平均需要移动_______个元素，删除一个元素时平均需要移动______个元素。

2．在顺序线性表中插入一个元素时，插入位置开始后的所有元素均需要________移动一个位置。

3．在顺序线性表中删除一个元素时，被删除元素后的所有元素均需要__________移动一个位置。

4．线性表的链式存储结构中，元素之间的线性关系是通过结点中的________来实现的。

5．线性表的顺序存储结构中逻辑上相邻的元素，物理位置__________相邻；线性表的链式存储结构中逻辑上相邻的元素，物理位置____________相邻。

6．已知单链表的长度为n，则在给定值为x的结点后插入一个新结点的时间复杂度为__________。

7．已知单链表的长度为n，则删除给定值为x的结点的时间复杂度为__________。8．在单链表中设置头结点的作用是________________________________。

9．双向链表中每个结点含有两个指针域，其中一个指针域指向_______结点，另一个指针域指向______结点。

10．在长度为n的线性表中顺序查找某个结点值为X的时间复杂度为______________。

二、选择题

1．在长度为n的顺序线性表中删除第i个元素(1<=i<=n)，则需要向前移动的元素个数为（）。

⑴n-i ⑵n+1-i ⑶n-1-i ⑷i 2．建立一个长度为n的单链表的时间复杂度为（）。

⑴O(n) ⑵O(1) ⑶O(n2) ⑷((log2n)

3．设指针p指向单链表中的结点A，结点A的后继结点是结点B，则删除结点B的操作为（）。

⑴p->next=p ⑵p=p->next

⑶p=p->next->next ⑷p->next=p->next->next 4．设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B之间插入结点X的操作为（）。

⑴s->next=p->next；p->next=s；⑵q->next=s；s->next=p；

⑶p->next=s->next；s->next=p；⑷p->next=s；s->next=q；5．在长度为n的顺序线性表中的第i个元素(1<=i<=n+1)之前插入一个新元素时，则需要向后移动的元素个数为（）。

⑴n-i ⑵n+1-i ⑶n-1-i ⑷i 6．在长度为n的有序线性表中插入一个元素后仍然保持有序的平均时间复杂度为（）。

⑴O(log2n) ⑵O(1) ⑶O(n2) ⑷

O(n)

7．设指针p指向双向链表中的结点A，指针s指向被插入的结点X，则在结点A之

⑴p->rlink=s；s->llink=p；p->rlink->llink=s；s->rlink=p->rlink；

⑵s->llink=p；s->rlink=p->rlink；p->rlink=s；p->rlink->llink=s；

⑶p->rlink=s；p->rlink->llink=s；s->llink=p；s->rlink->p->rlink；

⑷s->llink=p；s->rlink=p->rlink；p->rlink->llink=s；p->rlink=s；

8．指针p指向双向链表中的结点A，则删除结点A的操作是（）。

⑴p->llink->rlink=p->rlink；p->rlink->llink=p->llink；

⑵p->rlink->llink=p->rlink；p->llink->llink=p->llink；

⑶p->llink->rlink=p->llink；p->rlink->llink=p->rlink；

⑷p->rlink->rlink=p->rlink；p->rlink->rlink=p->rlink；

9．线性表采用链式存储结构时，要求存储单元的地址（）。

⑴必须是连续的⑵部分地址必须是连续的

⑶一定是不连续的⑷连续不连续都可以

10．设head为单链表的头指针，则不带头结点的单链表为空的判定条件是（）。

⑴head==NULL ⑵head->next==NULL

⑶head->next==head ⑷head!=NULL

11．设head为单链表的头指针，则带头结点的单链表为空的判定条件是（）。

⑴head==NULL ⑵head->next==NULL

⑶head->next==head ⑷head!=NULL

12．设head和tail分别为单向循环链表的头指针和尾指针，则下列等式成立的是（）。

⑴head==tail ⑵head->next==tail

⑶tail->next==head ⑷head->next==tail->next

三、算法设计题

顺序存储结构的类型定义：typedef struct {int a[m]; int n; } sqlist;

链式存储结构的类型定义：typedef struct node {int data; struct node *next;} lklist;

1.建立一个有n个结点的单链表，要求从尾部进行插入。

2.建立一个有n个结点的单链表，要求从头部进行插入。

3.用顺序存储结构实现线性表就地逆置算法，即在原表的存储空间内将线性表（a1，

a2，……，a n）逆置为(a n，a n-1，……，a1)。

4.用链式存储结构实现线性表就地逆置算法，即在原表的存储空间内将线性表（a1，

a2，……，a n）逆置为(a n，a n-1，……，a1)。

5.已知集合A、B，求集合C=A∩B算法，要求集合A、B和C均用采用顺序存储

结构表示。

6.已知集合A、B，求集合C=A∩B算法，要求集合A、B和C均用采用链式存储

结构表示。

7.设计在带有头结点的单向链表中删除值为X的结点算法。

第二章参考答案

一、填空题

1． n/2，(n-1)/2

分析：当在顺序线性表中的第i （1<=i<=n+1）个位置之前插入一个新元素时，从第i 个元素起向后的n+1-i 个元素均要向后移动一个位置。因此在等概率情况下，插入操作中元素的平均移动次数为∑

+==-++=112)1(11)(n i n i n n n f ；当在顺序线性表中删除第i （1<=i<=n ）个位置上的元素，从第i+1个元素起向后的n-i 个元素均要向前移动一个位置。因此在等概率情况下，删除操作中元素的平均移动次数为

∑=-=-=n i n i n n

n f 121)(1)(。 2．

向后 3．

向前 4．

指针域 5．

一定，不一定 6．

O(n) 7．

O(n) 8． 消除空表的特殊性，统一表示和处理空表和非空表的情形，从而简化插入和删除等操作的某些细节。

9． 前驱，后继

10． O(n)

二、填空题

1． (1)

2． (1)

分析：建立一个单链表的过程实际上就是在空链表的基础之上从单链表的头部或从单链表的尾部不断插入新结点的过程，因此建立单链表的时间复杂度为O(n)。

3． (4)

4． (2)

5． (2)

6． (4)

分析：在有序的线性表中插入一个元素后仍然保持有序的过程分为两步：第一步查找插入位置，第二步插入新元素。在线性表中查找插入位置的平均时间复杂度为f 1(n)=O(n)，在顺序线性表中插入新元素的平均时间复杂度为f 2(n)=O(n)，而在链式线性表中插入新元素的平均时间复杂度为f 2(n)=O(1)，因此本题中的平均时间复杂度f(n)=O(n)+O(1)=O(n) 或 f(n)=O(n)+O(n)=O(n)。

7． (4)

分析：在双向链表或双向循环链表中插入一个新结点的操作比较繁琐，通常需要修改4个指针域，根据排列公式可知共有4!=24种方案。在这24种方案中，有些方案是可行的，有些方案是不可行的。我们的通常做法是先连接哪些不破坏有用信息的指针域，然后再根据需要连接其余的指针域，在操作过程中注意修改有关结点指针域的操作顺序，以免丢失链域信息而造成链表中断的错误。

8． (1)

分析：在双向链表或双向循环链表中删除一个结点的操作比较相对插入一个新结点而言稍微简单一些，只需要修改两个指针域。首先找到指向前驱结点的指针（p->left）和指向后继结点的指针（p->right），然后再分别表示出前驱结点中的右指针域（p->left->right）和后继结点的左指针域（p->right->left），最后分别修改前驱结点中的右指针域和后继结点的左指针域。

9．(4)

10．(1)

11．(2)

12．(3)

三、算法设计题

1.建立一个有n个结点的单链表，要求从尾部进行插入。

分析：本题的算法思想是设置指针变量q始终指向当前链表中的最后一个结点，新生成的结点直接在尾部进行插入。这种设置指针变量q的方法使得操作比较简单，否则每次在尾部插入新结点时需要用一个临时指针变量从链表头部移到链表尾部。

void createlklistfromtail (lklist *&head )

{

int i; lklist *p,*q;

for (i=1,head=0;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;q=p;}

}

}

提示：以下形式参数表中出现在形式参数名前加符号“&”的现象，这种现象在我们常见的T urbo C 2.0版本中不能使用，但在Borland C 3.1及其以后版本中可以使用，它的作用是使得对形式参数的修改可以影响到对应的实在参数。以后算法设计题中经常用到。

2.建立一个有n个结点的单链表，要求从头部进行插入。

void createlklistfromhead (lklist *&head )

{

int i; lklist *p,*q;

for (i=1,q=head=0;i<=n;i++)

{

p=(lklist *)malloc(sizeof(lklist));

scanf("%d",&(p->data)); p->next=head; head=p;

}

}

提示：不断从头部插入新结点的方法来构造单向链表比不断从尾部插入新结点的方法来构造单向链表稍微操作简单一些。但顺序打印从尾部插入建立的单向链表所得到的序列与建立单向链表输入的序列一样，而顺序打印从头部插入建立的单向链表所得到的序列与建立单向链表输入的序列正好相反。

3.用顺序存储结构实现线性表就地逆置算法，即在原表的存储空间内将线性表（a1，a2，……，a n）逆置为(a n，a n-1，……，a1)。

void invertsqlist(sqlist &list)

{

int i,temp,n=list.n;

}

提示：本题中的循环次数只能是顺序线性表的长度一半，如果循环次数是顺序线性表的长度，则经过逆置后再逆置而还原到初始状态。

4.用链式存储结构实现线性表就地逆置算法，即在原表的存储空间内将线性表（a1，a2，……，a n）逆置为(a n，a n-1，……，a1)。

分析：本题的算法思想是依次将单链表中的结点取出来并用指针q指向它，然后再用从头部插入的方法建立一个新的单链表。

void invertlklist(lklist *&head)

{

lklist *p=head,*q; /*head=0;*/

q=p；p=p->next; q->next=0;

while(p!=0){q=p; p=p->next; q->next=head; head=q;}

}

5.已知集合A、B，求集合C=A∩B算法，要求集合A、B和C均用采用顺序存储结构表示。

分析：本题的算法思想是顺序取出集合A中的元素A[i]，然后再在集合B中从前向后进行顺序查找，如果找到等于该元素的结点则将其放入集合C中，否则什么也不做。本题算法思想同样适用于其后的第6题。

void intersectionsqlist(sqlist lista, sqlist listb,sqlist &listc)

{

int i,j;

for(listc.n=0,i=0;i<=lista.n-1; i++)

{

for(j=0;j<=listb.n-1; j++) if (listb.a[j]==lista.a[i]) break;

if(j<=listb.n-1) {listc.a[listc.n]=lista.a[i]; listc.n++;}

}

}

6.已知集合A、B，求集合C=A∩B算法，要求集合A、B和C均用采用链式存储结构表示。

void intersectionlklist(lklist *lista, lklist *listb,lklist *&listc)

{

lklist *p,*q,*s;

for(listc=0,p=lista;p!=0; p=p->next)

{

for(q=listb;q!=0;q=q->next) if (p->data==q->data) break;

if(q!=0) {s=(lklist *)malloc(sizeof(lklist)); s->data=p->data; s->next=listc; listc=s;}

}

}

7.设计在带有头结点的单向链表中删除值为X的结点算法。

分析：本题的算法思想是首先在单链表中查找值为x的结点，如果单链表为空或在单链表中找不到值为x的结点则给出相应的提示信息，否则进行删除操作。为了便于删除操作的实现而设置指针变量p指向被删除的结点，指针变量q始终指向其前驱结点。

void deletelklist(lklist *&head, int x)

{

lklist *q,*p;

else for(q=head,p=head->next; p!=0; q=p, p=p->next) if (p->data==x) break;

if (p==0) printf(“Not found %d in this linklist\n”,x); else { q->next=p->next; free(p);}

}

提示：在链表中引入头结点后可以消除空表的特殊性，统一表示和处理空表和非空表的情形，从而简化插入和删除等操作的某些细节。具体涉及到本题中，如果没有引入头结点，则在找到值为x的结点后要区分该结点是第一个结点还是其它结点，而引入头结点后，则这两种情况就可以统一处理。如果本题中的单链表没有带头结点，则需要将上述黑体中的代码改为代码if (p==head) head=p->next; else q->next=p->next;。

第三章栈和队列

一、填空题

1.线性表、栈和队列从逻辑上来说都是____________结构。可以在线性表的_______

位置插入和删除元素；对于栈只能在__________插入和删除元素；对于队列只能在___________插入元素和在_________删除元素。

2.栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称

为__________表；队列的插入和删除运算分别在队列的两端进行，进行插入的一端叫做__________，进行删除的一端叫做___________，先进队的元素必定先出队，所以又把队列称为____________表。

3.假设用向量S[1：m]来存储顺序栈，指针top指向当前栈顶的位置。则当栈为空

时满足的条件是____________；当栈为满时满足的条件是_____________。

4.设有一个空栈，现有输入序列1、2、3、4、5，经过push、push、pop、push、

pop、push、push、pop、pop、pop后，输出序列为__________________。5.在一个顺序循环队列中为了方便入队列和出队列的操作通常约定头指针front指

向实际队头元素的____________，尾指针rear指向当前实际队尾元素的____________。若该顺序循环队列有m个存储单元，则队列满时共有__________个元素。

6.设有一个顺序循环队列如上题中的约定，则该队列满的条件是_________，队列

空的条件是_________。

7.不论是顺序栈（队列）还是链式栈（队列），插入（删除）运算的时间复杂度均

为________。

8.系统在函数调用前自动把调用后的____________压入堆栈；当函数调用结束后，

系统又自动作退栈处理，并将程序执行流程无条件转移到所保存的_____________处继续执行。

二、选择题

1．设栈的输入序列是1、2、3、…、n，输出序列的第一个元素是n，则第i个输出元素是（）。

①n-i ②n-i-1 ③n-i+1 ④不确定2．设元素进栈次序为A、B、C、D、E，则下列不可能的出栈序列是（）。

①ABCDE ②BCDEA ③EABCD ④EDCBA

3．设用一维数组s[m]表示栈的存储空间，用top指向当前栈顶元素（其初始值为-1），则进行出栈时的操作序列是（）。

①x=s[op]；②x=s[top]；top=0；

③x=s[top]；top=top-1；④x=s[top]；top==top+1；

4．设指针hs指向栈顶，指针s指向插入的结点A，则插入结点A时的操作为（）。

①hs->next=s；②s->next=hs；hs=s；

③s->next=hs->next；hs->next=s；④s->next=hs；hs=hs->next；5．设用一维数组s[m]表示栈的存储空间，用top指向当前栈顶元素（其初始值为-1），则进行入栈时的操作序列是（）。

①s[top] =x；②top=top+1；s[top]=x；

③top==top-1；s[top]=x；④s[top]=x；top==top+1；

6．设front是链式队列的头指针，rear是链式队列的尾指针，s指向插入的结点A，则插入结点A的操作为（）。

③rear->next=s；rear=s；④s->next=front；front=s；7．设front是链式队列的头指针，rear是链式队列的尾指针，则删除队头元素的操作为（）。

①front=front->next；②rear=rear->next ；

③rear=front->next ；④front=rear->next；

8．对于一个具有m个存储单元的顺序循环队列，设front为队头指针，rear为队尾指针，则该队列中队列元素的个数计算公式为（）。

①rear-front ②front-rear

③(rear-front)%m ④(rear-front+m)%m

9．设用一维数组q[m]作为顺序循环队列的存储空间，front指向队头元素的前一个位置，rear指向队尾元素的当前位置，则入队列的操作序列为（）。

①q[rear] =x；rear=rear+1；②q[rear]=x；rear=rear-1；

③rear=(rear+1)%m；q[rear] =x；④rear=(rear-1)%m；q[rear]=x；10．设用一维数组q[m]作为顺序循环队列的存储空间，front指向队头元素的前一个位置，rear指向队尾元素的当前位置，则出队列的操作序列为（）。

①x=q[front]；front=front+1；②front=(front+1)%m；x=q[front]；

③x=q[front]；front=front-1；④front=(front-1)%m；x=q[front]；

三、算法设计题

1．设有两个顺序栈S1和S2共享一个存储区S[0：m-1]，为了尽量利用存储空间减少溢出的可能性，采用栈顶相向、迎面增长的存储方式，要求分别设计两个栈的入栈和出栈操作。

2．设计算法判断表达式中的圆括号是否配对出现。

3．设用一个单向循环链表来表示队列（也称循环队列），该队列只设一个队尾指针rear，不设队头指针front，要求设计出该队列的入队列和出队列操作。

4．假设以一个一维向量q[0：m-1]作为顺序循环队列的存储空间，同时设变量rear 和len分别指示顺序循环队列中的队尾元素的位置和实际队列中的元素个数，要求设计出该队列的入队列和出队列操作。

5．将数字1、2、……、n按顺时针方向排列成环形，按顺时针方向从1开始计数，计满时则输出该位置上的数字并从环中删除该数字，然后从下一个数字开始继续计数，直到环中所有数字均被输出为止，要求设计一个算法完成此功能。

第三章参考答案

一、填空题

1． 线性，任何，栈顶，队尾，队头

2． 先进后出（FILO ），队尾，队头，先进先出（FIFO ）

3． top==0，top==m

4． 23541

5． 前一个位置，所在位置，（所在位置，下一个位置）m-1

分析：在顺序循环队列中约定头指针front 和尾指针rear 所指向的位置，是牺牲掉一个存储单元而方便表示队列空和队列满的条件，因此顺序循环队列中实际可用的存储单元只有m-1个。

6． (rear+1)%m==front ，rear==front

7． O(1)

8． 返回地址，返回地址

二、选择题

1. (3)

分析：设栈的输入序列是1、2、3、……、n ，输出序列的第一个元素是n ，则输出序列必定是n 、n-1、n-2、……、1，因此第i 个输出元素是n+1-i 。

2. (3)

3. (3)

4. (2)

5. (2)

6. (3)

7. (1)

8. (4)

分析：顺序循环队列中的元素个数=?

??<+-≥-front rear m front rear front rear front rear ，整理合并可写成(rear-front+m)%m 。

9. (3)

10. (2)

三、算法设计题

1. 设有两个顺序栈S1和S2共享一个存储区S[0：m-1]，为了尽量利用存储空间减少溢出的可能性，采用栈顶相向、迎面增长的存储方式，要求分别设计两个栈的入栈和出栈操作。

分析：本题算法思想是引入形式参数flag ，当形式参数flag 的值为1时表示对栈1进行操作，flag 的值为2时表示对栈2进行操作。

typedef struct {int s[m]; int top1; int top2;} sqstack;

void push(sqstack &stack , int x,int flag)

{

if (stack.top1+1==stack.top2) printf(“s tack is full\n”);

else

{

if (flag==1) {stack.top1++; stack.s[stack.top1]=x;}

else if(flag==2){stack.top2--; stack.s[stack.top2]=x;}else printf(“input error\n”);

}

}

void pop(sqstack &stack , int &y, int flag)

{

if (flag==1)

if(stack.top1<0) printf(“empt y\n”); else { y=stack.s[stack.top1];stack.top1--; }

else if(flag==2)

if(stack.top2>=m) printf(“empty\n”); else { y=stack.s[stack.top2];stack.top2++; }

else printf(“input error\n”);

}

2.设计算法判断表达式中的圆括号是否配对出现。

分析：本题的算法思想是顺序扫描表达式，当扫描到左圆括号时进栈而扫描到右圆括号时出栈，如果扫描到右圆括号时不能出栈或扫描表达式结束时栈中仍有左圆括号则意味表达式中圆括号不匹配，否则表达式中圆括号匹配。

typedef struct {int s[m]; int top;} sqstack;

int matchbracket()

{

char ch; sqstack stack; stack.top= -1;

do

{

ch=getchar();

if (ch==…(?) {stack.top=stack.top+1; stack.s[stack.top]=ch;}

else if (ch==…)?)if (stack.top<0) return(0); else stack.top=stack.top-1;

}while(ch!= …#?);

if (stack.top<0) return(1); else return(0);

}

3.设用一个单向循环链表来表示队列（也称链式循环队列），该队列只设一个队尾指针rear，不设队头指针front，要求设计出该队列的入队列和出队列操作。

typedef struct node {int data; struct node *next;} lklist;

void inlkqueue(lklist *rear, int x)

{

lklist *p;

p=(lklist *) malloc(sizeof(lklist)); p->data=x;

if (rear==0) {rear=p; rear->next=rear;}else {p->next=rear->next; rear->next=p; rear=p;}

}

void outlkqueue(lklist *rear, int *y)

{

lklist *p;

if (rear==0) printf(“queue is empty\n”);

else if {rear->next==rear} {y=rear->data; rear=0; }

else { p=rear->next; y=p->data; rear->next=p->next; free(p);}

}

4.假设以一个一维向量q[0：m-1]作为顺序循环队列的存储空间，同时设变量rear 和len分别指示顺序循环队列中的队尾元素的位置和实际队列中的元素个数，要求设计出该队列的入队列和出队列操作。

分析：本题中出队列的算法思路是设置一个临时变量front指向当前队列中队头元素的实际位置，考虑到表达式queue.rear+1-queue.len的值可能为负，因此设置front 的值为(queue.rear+1-queue.len+m)%m。

typedef struct{ int q[m]; int rear; int len; } sqqueue;

void insqqueue(sqqueue &queue, int x)

{

if (queue.len==m) printf(“queue is full\n”);

else {queue.rear=(queue.rear+1)%m; queue.q[queue.rear]=x;queue.len++;} }

void outsqqueue(sqqueue &queue, int *y)

{

int front;

if (queue.len==0) printf(“queue is emptyl\n”);

else {front=queue.rear+1-queue.len+m}%m; y=queue.q[queue.front];queue.len--;}

}

5.编写一个算法解决约瑟夫（Josephus）环问题。其问题是：设有n个人围坐在一张圆桌周围，现从第一个人开始从1报数，报到k的人出离开圆桌，接着从下一个人从1开始重新报数，……，以此类推，直到他们都离开圆桌，求出他们离开圆桌的先后顺序。

分析：本题的算法思路是设置变量sum和num，其中变量sum表示当前已经离开圆桌的人数个数，变量num表示当前的报数。

void Josephus( int n, int k)

{

int i,num,sum,r[100];

for(i=0;i

for(sum=num=i=0; sum

if (r[i]!=-1) {

num++;

if (num % k==0) {

printf("%d\t",i); num=0;sum++; r[i]= -1;

}

}

}

第四章 字符串和数组

一、填空题

1. 设字符串S1=“ABCDEF”，S2=“PQRS”，则运算S=CONCAT(SUB(S1，2，LEN(S2))，SUB(S1，LEN(S2)，2)的结果为S=_________________。

2. 判断两个字符串相等的充要条件是____________________________。

3. 下列程序段实现子串t 在主串s 中位置的算法，要求在下划线处填上正确语句。 int index(char s[ ], char t[ ])

{

i=j=0;

while(i

if(s[i]==t[j]){i=i+l; j=j+l;}else{i=_______; j=______;}

if (j==strlen(t))return(i-strlen(t));else return (-1);

}

4. 设二维数组A 有m 行n 列，每个数组元素占L 个字节的存储单元，按行的顺序存放在m*n 个连续的存储单元中。已知A[0][0]的地址为1000，则A[i][j]的地址为______________________________________。

5. 设三维数组A[3][4][5]中的每个元素占10个字节的存储单元，按行的顺序存放在一组连续的存储空间中。已知A[0][0][0]的首地址为1000，则数组元素A[1][2][3]的首地址为___________________________。

6. 设对称矩阵A 有n 行n 列，每个数组元素占L 个字节的存储单元，按行的顺序将下三角矩阵中的元素（包括对角线上的元素）存放在n*(n+1)/2个存储单元中，已知A[0][0]的地址为1000，则A[i][j]（i>=j ）的地址为

___________________________。

7. 设有n 行n 列的三对角矩阵A ，每个数组元素占L 个字节的存储单元，按照从上到下从左到右的顺序将三条对角线上的元素存放在3n-2个连续的存储单元中，已知A[0][0]的地址为1000，则三对角线上元素A[i][j]的地址为

_________________。

8. 已知稀疏矩阵A=???

???????????-00005100

00030200，则A 的三元组表为__________________。

二、算法设计题

1. 设用顺序存储结构存储字符串S1和S2，要求设计一个函数完成对两个字符串的比较。若S1>S2时则返回正数；若S1=S2时则返回0；若S1

2. 用顺序存储结构实现在字符串S 中删除所有其值等于ch 的字符的算法。

3. 设单链表中存放n 个字符，试设计算法判断字符串是否关于中心对称。

第四章参考答案

一、填空题

1. “BCDEDE ”

2. 字符串的长度相等且对应位置上的字符相等

3. i-j+1，0

分析：在查找子串位置的过程中，当发现s[i]!=t[j]时需要重新调整指针i 和j 的值后继续查找。指针j 的值肯定调整到子串的开始位置0，而指针i 的值则相应调整到i-j 的后一个位置i-j+1。

4. 1000+(i*n+j)*L

5. 1330

分析：A[1][2][3]的首地址=1000+(1*4*5+2*5+3)*10=1330。

6. 1000+(i*(i+1)/2+j)*L

分析：A[i][j]的首地址=1000+(1+2+……+i+j)*L=1000+(i*(i+1)/2+j)*L 。

7. (2*i+j)*L

分析：A[i][j]的首地址

=?

??>+=+-++-=0*)*2(*))1(23*)1((0*i L j i L i j i i L j ，经合并整理可得A[i][j]的首地址=(2*i+j)*L 。

8. 4 4 4

??????

? ??-532122301

220

二、算法设计题

1. 设用顺序存储结构存储字符串S1和S2，要求设计一个函数完成对两个字符串的比较。若S1>S2时则返回正数；若S1=S2时则返回0；若S1

{

int i;

for(i=0;s1[i]!=0;i++) if (s1[i]!=s2[i]) break; return(s1[i]-s2[i]);

}

2. 用顺序存储结构实现在字符串S 中删除所有其值等于ch （假设ch=?A ?）的字符的算法。

void deletestring(char s[ ],char ch)

{

int i=0,j;

while(s[i]!=0) if (s[i]==ch) {for(j=i+1; s[j]!=0; j++) s[j-1]=s[j]; s[j-1]=0;}else i++; }

3. 设计一个算法判断字符串S 中的字符是否关于中心对称。

typedef struct {char s[m]; int top;} sqstack;

int stringsymmetry(char s[ ])

{

int i; sqstack stack; stack.top= -1;

for(i=0;s[i]!=0;i++) if (s[i]==stack.s[stack.top]) stack.top=stack.top-1; else return(0);

return(1);

}

第五章树

一、填空题

1.设一棵树的二元组形式表示为T=（D，R），其中D={A，B，C，D，E，F，G}，

R={(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)}，则该树的度数为________，树的深度为________，叶子结点的个数为_________，分支结点的个数为_________，C结点的双亲结点为__________，C结点的孩子结点为__________。

2.二叉树有_________种不同形态。

3.对于一棵具有n个结点的二叉树，当它为一棵__________二叉树时具有最小高

度，其最小高度为_______________。

4.一棵深度为k的满二叉树的结点总数为___________；一棵深度为k的完全二叉

树的结点总数最少有___________个，最多有____________个。

5.已知一棵二叉树中度数为0的结点个数为n0，度数为1的结点数为n1，则该树

中度数为2的结点数为n2，则n0=___________。

6.一棵树中度数为1的结点数为n1，度数为2的结点数为n2，……，度数为m的

结点度为n m，则该树中度数为0的结点数为____________个。

7.已知一棵二叉树的顺序存储结构表示为ABCDE?F（其中字符?表示空结点），

则其前序序列为_____________，中序序列为___________，后序序列为_____________。

8.按照从上到下、从左到右的顺序对有n个结点的完全二叉树从1开始顺序编号，

则编号为i（i!=1且2i+1<=n）的结点其双亲结点的编号为________，其左孩子结点的编号为________，其右孩子结点的编号为________。

9.对于一棵具有n个结点的二叉树，当用二叉链表作为存储结构时，其二叉链表中

的指针域的总数为______个，其中______个用于链接孩子结点，_______个为空指针域。

10.设某棵二叉树的前序遍历序列为ABCDEFGH，中序遍历序列为BCAEDGHF，

则该二叉树的后序遍历序列为____________________。

11.如果按中序遍历某二叉树的遍历序列为abc，问有________种不同的二叉树可以

得到这一遍历序列。

12.设哈夫曼树中有n个叶子结点，则该哈夫曼树中总共有___________结点。

二、选择题

1．假设一棵二叉树中，双分支结点数为15个，单分支结点数为30个，则终端结点数为（）。

①15 ②16 ③17 ④47 2．假设一棵三叉树的结点数为50，则它的最小高度为（）。

①3 ②4 ③5 ④6

3．一棵二叉树上第5层的结点数最多为（）。

①15 ②16 ③8 ④32 4．将完全二叉树中的所有结点按照从上到下、从左到右的顺序存放在n个连续的存储单元中，第一个结点存放在R[1]中。若结点R[i]有左孩子，则左孩子的结点是（）。第一个结点存放在R[0]中呢？（）

①R[2i+1] ②R[2i] ③R[i/2] ④R[2i-1]

5. 设一棵具有n个结点的满二叉树有m个叶子结点和k个分枝结点，则下列等成立的是（）。

数据结构试题库答案

数据结构试题及答案 一、单项选择题 (1)一个算法应该就是（)。 A)程序???B）问题求解步骤得描述 C）要满足五个基本属性??D) A与C (2)算法指得就是（)。 A）计算机程序???B）解决问题得计算方法 C)排序算法???D）解决问题得有限运算序列。 (3)与数据元素本身得形式、内容、相对位置、个数无关得就是数据得(）。 A) 存储结构B) 逻辑结构C）算法D)操作 (4)从逻辑上可以把数据结构分为( ）两大类。 A）动态结构、静态结构??B) 顺序结构、链式结构 C）线性结构、非线性结构???D）初等结构、构造型结构 (5)下列叙述中正确得就是(）。 A)一个逻辑数据结构只能有一种存储结构 B）数据得逻辑结构属于线性结构,存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理得效率 D）一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理得效率 (6)数据得基本单位就是（） ?A) 数据项??B) 数据类型C)数据元素??D)数据变量 (7)下列程序得时间复杂度为（) i=０；s＝０; wｈｉlｅ(s

数据结构试题库

数据结构试题库 一、单项选择题 1．下列程序段所代表的算法的时间复杂度为（D ）。 x=n; y=0; while (x>=(y+1)*(y+1)) y++; (A)O(n) (B)O(n2) (C)O(log2n) (D)O(n) 2．在一个长度为n的以顺序结构存储的线性表中，假设在线性表的任何位置删除元素的概率相等，则删除一个元素时线性表所需移动元素的平均次数为（B ）。 (A) n2 (B)(n-1)/2 (C)(n+1)/2 (D)n/2 3．在一个栈顶指针为HS的链栈中插入一个*s结点时，应执行执行操作为（C ）。 (A)HS->next=s;(B)s->next=HS->next;HS->next=s; (C)s->next=HS;HS=s;(D)s->next=HS;HS=HS>next; 4．假设以带头结点的循环链表表示队列Q，并且队列只设一个头指针front，不设队列尾指针。若要进队一个元素*s，则在下列程序算法的空白处应添加的操作语句是（A ）。 void AddQueue(struct linkqueue Q) { p=Q->front; while(p->next!=Q->front) p=p->next; } (A)p->next=s;s->next=Q->front; (B)Q->front->next=s;Q->front=s; (C)s->next=p;p->next=Q->front; (D)Q->front->next=s;s->next=p; 5．设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（B ）。 (A)2h-1(B)2h-1+1 (C)2h-1 (D)2h-1-3

《数据结构》题库及答案

《数据结构》题库及答案 一、选择题 1．线性表的顺序存储结构是一种 的存储结构，线性表的链式存储结构是一种 的存储结构。 a. 随机存储； b.顺序存储； c. 索引存取； d. HASH 存取 2．一个栈的入栈序列是a,b,c,d,e ，则栈的不可能的输出序列是 。 a. edcba; b. decba; c. dceab; d.abcde 3．一个队列的入队序列是1，2，3，4，则队列的输出序列是 。 a. 4,3,2,1; b. 1,2,3,4; c. 1,4,3,2; d.3,2,4,1 4．在一个单链表中，已知p 结点是q 结点的直接前驱结点，若在p 和q 之间插入结点s ，则执行的操作是 。 a. s->nxet=p->next; p->next=s; b. p->next=s->next; s->next=p; c. q->next=s; s->next=p; d. p->next=s; s->next=q; 5．设有两个串p,q ，求q 在p 中首次出现的位置的运算称作 。 a.联接 b.模式匹配 c.求子串 d.求串长 6．二维数组M 的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i 的范围从0到8，列下标j 的范围从1到10，则存放M 至少需要 个字节。 a. 90 b.180 c.240 d.540 7．在线索二叉树中，结点p 没有左子树的充要条件是 。 a. p->lch==NULL b. p->ltag==1 c. p->ltag==1且p->lch=NULL d. 以上都不对 8．在栈操作中，输入序列为（A ，B ，C ，D ），不可能得到的输出序列为：______ A 、（A ， B ， C ， D ） B 、（D ，C ，B ，A ） C 、（A ，C ，D ，B ） D 、（C ，A ，B ，D ） 9．已知某二叉树的后序序列是dabec ，中序序列是debac ，则它的先序序列是 。 A 、acbed B 、decab C 、deabc D 、cedba 10．设矩阵A 是一个对称矩阵，为了节省存储空间，将其下三角部分（见下图）按行序存放在一维数组B[1..n(n-1)/2]中，对任一上三角部分元素)(j i a ij ，在一维数组B 的存放位置是 。

数据结构试题(含答案)

一．是非题 （正确的打“√”，错误的打“×”。） 1. 数据结构可用三元式表示（D，S，P）。其中：D是数据对象，S是D上的关系， P是对D的基本操作集。× 2. 线性表的链式存储结构具有可直接存取表中任一元素的优点。× 3. 字符串是数据对象特定的线性表。 4. 二叉树是一棵结点的度最大为二的树。× 5．邻接多重表可以用以表示无向图，也可用以表示有向图。× 6．可从任意有向图中得到关于所有顶点的拓扑次序。× 7．一棵无向连通图的生成树是其极大的连通子图。× 8．二叉排序树的查找长度至多为log2ｎ。× 9．对于一棵m阶的B-树.树中每个结点至多有m 个关键字。除根之外的所有非终端结点至少有┌m/2┐个关键字。× 10．对于目前所知的排序方法，快速排序具有最好的平均性能。 11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。× 12. 二维数组是其数据元素为线性表的线性表。 13. 连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。× 14. 折半查找不适用于有序链表的查找。 15. 完全二叉树必定是平衡二叉树。 16. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。 17. 队列是与线性表完全不同的一种数据结构。× 18. 平均查找长度与记录的查找概率有关。 19. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。× 20. 算法的时间复杂性越好，可读性就越差；反之，算法的可读性越好，则时间复杂性就越差。× 二．选择题 1. 若对编号为1，2，3的列车车厢依次通过扳道栈进行调度，不能得到 ( e ) 的序列。 a:1,2,3 b:1,3,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,1 2. 递归程序可借助于( b )转化为非递归程序。 a:线性表 b: 栈 c:队列 d:数组 3. 在下列数据结构中( c )具有先进先出（FIFO）特性， ( b )具有先进后出(FILO）特性。 a:线性表 b:栈 c:队列 d:广义表 4. 对字符串s=’data-structure’ 执行操作replace(s,substring(s,6,8),’bas’)

数据结构习题库

知识点： 01．绪论 02．顺序表 03．链表 04．栈 05．链队列 06．循环队列 07．串 08．数组的顺序表示 09．稀疏矩阵 10．广义表 11．二叉树的基本概念 12．二叉树遍历、二叉树性质 13．树、树与二叉树的转换 14．赫夫曼树 15．图的定义、图的存储 16．图的遍历 17．图的生成树 18．静态查找（顺序表的查找、有序表的查找） 19．动态查找（二叉排序树、平衡树、B树） 20．哈希查找 21．插入排序（直接插入、折半插入、2路插入、希尔排序）22．选择排序（简单选择、树形选择、堆排序） 23．快速排序、归并排序

101A1（1）．数据的逻辑结构是（A）。 A．数据的组织形式 B．数据的存储形式 C．数据的表示形式 D．数据的实现形式 101A1（2）．组成数据的基本单位是（C）。 A．数据项 B．数据类型 C．数据元素 D．数据变量 101B1（3）．与顺序存储结构相比，链式存储结构的存储密度（B）。 A．大 B．小 C．相同 D．以上都不对 101B2（4）．对于存储同样一组数据元素而言，（D）。 A．顺序存储结构比链接结构多占空间 B．在顺序结构中查找元素的速度比在链接结构中查找要快 C．与链接结构相比，顺序结构便于安排数据元素 D．顺序结构占用整块空间而链接结构不要求整块空间101B2（5）．下面程序的时间复杂度为（B）。 x=0； for（i=1；ii；j++） state； A．n（n+1）/2 B．（n-1）（n+2）/2 C．n（n+1）/2 D．（n-1）（n+2） 101D3（8）．下面程序的时间复杂度为（A）。

数据结构试题及答案(10套最新)

单选题(每题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; 都具有相同的(A )。 A.行号 B .列号 C .元素值 D .非零元素个数 9. 快速排序在最坏情况下的时间复杂度为(D )。 A. O(log 2n) B . O(nlog 2n) C . 0(n) D 10.10. 从二叉搜索树中查找一个元素时，其时间复杂度大致 为 A. O(n) B. O(1) C. O(log 2 n) D. O(n 二、 运算题(每题6分，共24分) 1. 1. 数据结构是指数据及其相互之间的 _________________ 。当结点之 间存在M 对N (M N)的联系时，称这种结构为 __________________________ 。 2. 2. 队列的插入操作是在队列的_ _尾 ________ 行，删除操作是在队 列的 ____ 首 _____ 行。 3. 3. 当用长度为N 的数组顺序存储一个栈时，假定用top==N 表示栈 C. p->next=HL; p=HL; 3. 3. A. C. D. HL=p; p-> next=HL; 对线性表，在下列哪种情况下应当采用链表表示? 经常需要随机地存取元素 B. 表中元素需要占据一片连续的存储空间 一个栈的输入序列为1 2 3， 4. 4. 列的是(C ) A. 2 3 1 C. 3 1 2 AOV 网 是一种(D ) 有向 图 B .无向图 (B ) 经常需要进行插入和删除操作 D.表中元素的个数不变 则下列序列中不可能是栈的输出序 B. 3 2 1 5. 5. 6. .无向无环图 D .有向无环图 采用 开放定址法处理散列表的冲突时，其平均查找长度( B. 高于链接法处理冲突 D .高于二分查找 7. 8. 6. A.低于链接法处理冲突 .与链接法处理冲突相同 7. 参数。 A.值 8. B)。 若需要利用形参直接访问实参时，应将形参变量说明为( B .函数 C .指针 D .引用 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点 9. .0(n 2) (C )。 2 )

数据结构考试题库含答案

数据结构习题集含答案 目录

选择题 第一章绪论 1.数据结构这门学科是针对什么问题而产生的（A ） A、针对非数值计算的程序设计问题 B、针对数值计算的程序设计问题 C、数值计算与非数值计算的问题都针对 D、两者都不针对 2.数据结构这门学科的研究内容下面选项最准确的是（D ） A、研究数据对象和数据之间的关系 B、研究数据对象 C、研究数据对象和数据的操作 D、研究数据对象、数据之间的关系和操作 3.某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那 么下面关于数据对象、数据元素、数据项描述正确的是（C ） A、某班级的学生成绩表是数据元素，90分是数据项 B、某班级的学生成绩表是数据对象，90分是数据元素 C、某班级的学生成绩表是数据对象，90分是数据项 D、某班级的学生成绩表是数据元素，90分是数据元素 4.*数据结构是指（A ）。 A、数据元素的组织形式 B、数据类型 C、数据存储结构 D、数据定义 5.数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。 A、存储结构 B、逻辑结构 C、链式存储结构 D、顺序存储结构 6.算法分析的目的是（C ） A、找出数据的合理性 B、研究算法中的输入和输出关系 C、分析算法效率以求改进 D、分析算法的易懂性和文档型性

7.算法分析的主要方法（A ）。 A、空间复杂度和时间复杂度 B、正确性和简明性 C、可读性和文档性 D、数据复杂性和程序复杂性 8.计算机内部处理的基本单元是（B ） A、数据 B、数据元素 C、数据项 D、数据库 9.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储 比顺序存储要（B ）。 A、低 B、高 C、相同 D、不好说 10.算法的时间复杂度取决于（ C ） A 、问题的规模B、待处理数据的初始状态 C、问题的规模和待处理数据的初始状态 D、不好说 11.数据结构既研究数据的逻辑结构，又研究物理结构，这种观点（B ）。 A、正确 B、错误 C、前半句对，后半句错 D、前半句错，后半句对 12.在数据结构中，从逻辑上可以把数据结构分成（ C ） A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 13.线性表的顺序存储结构是一种( )的存储结构，线性表的链式存储结构是一种（ A ） 存储结构。 A、随机存取 B、顺序存取 C、索引存取 D、散列存取 14.*下列程序的时间复杂度是（A ） for (i=1; i<=n; ++i){ for (j=1; j<=n; ++j){ c [i][j]=0;

数据结构题库教材

2013-2014学年二学期数据结构期末考试模拟试卷(1~6卷) 一、应用题(3小题，共24分) 1已知某字符串S中共有8种字符，各种字符分别出现2次、1次、4次、5次、7次、3 次、4次和9次，对该字符串用［0,1］进行前缀编码，问该字符串的编码至少有多少位。 【解答】以各字符出现的次数作为叶子结点的权值构造的哈夫曼编码树如图所示。其带权路 径长度=2X 5+1X 5+3X 4+5X 3+9X 2+4X 3+4X 3+7X 2=98，所以，该字符串的编码长度至少为98位。 2.已知关键码序列为(Ja n, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec), 散列表的地址空间为0~16,设散列函数为H(x)= ［i/2」(取下整数)，其中i为关键码 中第一个字母在字母表中的序号，采用链地址法处理冲突构造散列表，并求等概率情况下查找成功的平均查找长度。 【解答】H(Ja n)=10/2=5, H(Feb)=6/2=3, H(Mar)=13/2=6, H(Apr)=1/2=0 H(May)=13/2=6, H(Ju n)=10/25, H(Jul)=10/25, H(Aug)=1/2=0 H(Sep)=19/2=8, H(Oct) =15/2=7, H(Nov) =14/2=7, H(Dec) =4/2=2 采用链地址法处理冲突，得到的开散列表如下： 平均查找长度=(1 X 7+2X 4+3X 1)/12=18/12

3.分析下面各程序段的时间复杂度 (1)s1(int n) { int p=1,s=0; for (i=1;iv=n;i++) { p*=i;s+=p; } return(s); } ——0(n) (2)s2(int n) x=0;y=0; For (k=1;kv=n;k++) x++; For (i=1;iv=n;i++) For (j=1;jv=n;j++) y++; ——0(n) 1?下述算法的功能是什么？ ListNode *Demo l(LinkList L P ListNode *p) ("L是有头结蛊的单链表 ListNodc *q=L->rLCxt P (1) V ‘V … 」(1 )返回结点*p的直接前趋结点地址。 q=q->nest; if (q) return q, else ?ro< #*p not in L"); I ⑵ i/oid Demo2(LisINode *p ,ListNode +q) 〔//p t*q*8S 表中的 两个结点 (2)交换结点*p和结点*q (p和q的值不变)。 DataTypetemp; temp=p->data, p->data=q->data; q-x^ata^emp, 1.对给定的一组权值W=( 5, 2, 9, 11, 8, 3, 7),试构造相应的哈夫曼树，并计算它的带权路径长度。【解答】构造的哈夫曼树如图所示。

算法与数据结构题库与答案

一、单项选择题 1 某算法的时间复杂度是O(n 2 ) ，表明该算法（）。 A 问题规模是n2 B 问题规模与n2成正比 C 执行时间等于n2 D 执行时间与n2成正比 2、关于数据结构的描述，不正确的是（）。 A数据结构相同，对应的存储结构也相同。 B数据结构涉及数据的逻辑结构、存储结构和施加其上的操作等三个方面。 C数据结构操作的实现与存储结构有关。 D定义逻辑结构时可不考虑存储结构。 3、按排序策略分来，起泡排序属于（）。 A插入排序B选择排序C交换排序D归并排序 4、利用双向链表作线性表的存储结构的优点是（）。 A便于进行插入和删除的操作 B 提高按关系查找数据元素的速度 C节省空间D便于销毁结构释放空间 5、一个队列的进队顺序为1,2,3,4，则该队列可能的输出序列是（）。 A 1,2,3,4 B 1,3,2,4 C 1,4,2,3 D 4,3,2,1 6、 Dijkstra算法是按（）方法求出图中从某顶点到其余顶点最短路径的。 A按长度递减的顺序求出图的某顶点到其余顶点的最短路径 B按长度递增的顺序求出图的某顶点到其余顶点的最短路径 C通过深度优先遍历求出图中从某顶点到其余顶点的所有路径 D通过广度优先遍历求出图的某顶点到其余顶点的最短路径 7、字符串可定义为n（ n≥ 0）个字符的有限（）。其中，n是字符串的长度，表明字符串中字符的个数。 A集合B数列C序列D聚合 8、在二维数组A[9][10]中，每个数组元素占用 3 个存储单元，从首地址SA 开始按行连续存放。在这种情况下，元素A[8][5]的起始地址为（）。 A SA+141 B SA+144 C SA+222 D SA+255 9、已知广义表为L(A(u,v,(x,y),z),C(m,(),(k,l,n),(())),((())),(e,(f,g),h))，则它的长度是（）。 A2B3C4D5 10.对于具有n(n>1)个顶点的强连通图，其有向边条数至少有_____。 A. n+1 B. n C. n-1 D. n-2 11.一个递归算法必须包括 __________ 。 A. 递归部分 B . 结束条件和递归部分 C. 迭代部分 D. 结束条件和迭代部分 12.从逻辑上看可以把数据结构分为__________两大类。 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 13、若在长度为n 的顺序表的表尾插入一个新元素的渐进时间复杂度为（）。 A O(n) B O(1) C O(n 2) D O(log 2n) 14.采用顺序搜素方式搜索长度为 n 的线性表时，在等概率情况下，搜索成功时的平均搜索 长度为 __________。 A. n B. n/2 C . (n+1)/2 D. (n-1)/2 15、非空的循环单链表first的链尾结点（由p 所指向）满足（）。 A p->link==NULL; B P==NULL;

数据结构试题及答案

第一章概论 一、选择题 1、研究数据结构就是研究（Ｄ）。 Ａ. 数据的逻辑结构?B。数据的存储结构 C。数据的逻辑结构和存储结构?D．数据的逻辑结构、存储结构及其基本操作(研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作) 2、算法分析的两个主要方面是（Ａ）。 A．空间复杂度和时间复杂度???B。正确性和简单性 C。可读性和文档性D．数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。(线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素,有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继)（链表、栈、队列、数组、串） A. 图Ｂ. 树??C．广义表(线性表的推广) D．栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、（ B ）等5个特性。 Ａ．可执行性、可移植性和可扩充性? B. 可执行性、有穷性和确定性 C。确定性、有穷性和稳定性??? D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C ）。 for(i=0；i

数据结构相关题库及答案

第三章栈和队列 一、判断题： 1、栈和队列都是限制存取点的线性结构(易) 2、栈和队列是两种重要的线性结构。(易) 3、带头结点的单链表形式的队列，头指针F指向队列的头结点，尾指针R指向队列的最后一个结点(易) 4、在对不带头结点的链队列作出队操作时，不会改变头指针的值。(易) 答案：1-4 √√×× 二、选择题： 1、一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是C____。 A、 edcba B、 decba C、 dceab D、 abcde 2、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi 为_C___。 A、 i B、 n=i C、 n-i+1 D、不确定 3、栈结构通常采用的两种存储结构是_A___。 A、顺序存储结构和链式存储结构 B、散列方式和索引方式 C、链表存储结构和数组 D、线性存储结构和非线性存储结构 4、判定一个顺序栈ST（最多元素为m0）为空的条件是_B___。A、top !=0 B、top= =0 C、top !=m0 D、top= =m0-1 5、判定一个顺序栈ST（最多元素为m0）为栈满的条件是D。A、top！=0 B、top= =0 C、top！=m0 D、top= =m0-1 6、队列操作的原则是( A ) A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删 除 7、向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行__ _C_。(不带空的头结点) (易) A、HS—＞next=s;9 B、s—＞next= HS—＞next; HS—＞next=s; C、s—＞next= HS; HS=s; D、s—＞next= HS; HS= HS—＞next

数据结构试题及答案(10套最新)

一、单选题（每题 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的单链存储的线性表，在表头插入元素的时间复杂度 为_________，在表尾插入元素的时间复杂度为____________。

数据结构试题库与答案

数据结构试题库及答案 第一章 概论 一、选择题 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

数据结构试题及答案

一、判断题： 1、线性表的逻辑顺序与物理顺序总是一致的。( ) 2、线性表的顺序存储表示优于链式存储表示。( ) 3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。( ) 4、二维数组是其数组元素为线性表的线性表。( ) 5、每种数据结构都应具备三种基本运算：插入、删除和搜索。( ) 6、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个 方面。( ) 7、线性表中的每个结点最多只有一个前驱和一个后继。（） 8、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。（） 9、栈和队列逻辑上都是线性表。（） 10、单链表从任何一个结点出发，都能访问到所有结点（） 11、删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。（） 12、快速排序是排序算法中最快的一种。（） 13、多维数组是向量的推广。（） 14、一般树和二叉树的结点数目都可以为0。（） 15、直接选择排序是一种不稳定的排序方法。（） 16、98、对一个堆按层次遍历，不一定能得到一个有序序列。（） 17、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。（） 18、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。（） 19、堆栈在数据中的存储原则是先进先出。（） 20、队列在数据中的存储原则是后进先出。（） 21、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。（） 22、哈夫曼树一定是满二叉树。（） 23、程序是用计算机语言表述的算法。（） 24、线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。（） 25、用一组地址连续的存储单元存放的元素一定构成线性表。（） 26、堆栈、队列和数组的逻辑结构都是线性表结构。（） 27、给定一组权值，可以唯一构造出一棵哈夫曼树。（） 28、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。（）

数据结构题库汇总

数据结构习题 习题一 一、选择题 1、算法分析的两个主要方面是：（） A．正确性和简明性B．时间复杂度和空间复杂度 C．数据复杂性和程序复杂性D．可读性和文档性 2、在数据结构中，从逻辑上可以把数据结构分成（）。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．逻辑结构和存储结构 3、计算机算法具备输入、输出和（）等5个特性： A．有穷性、确定性和稳定性B．可行性、可移植性和可扩充性 C．有穷性、确定性和可行性D．易读性、稳定性和安全性 4、算法分析的目的是（）。 A．找出算法的合理性 B．研究算法的输人与输出关系 C．分析算法的有效性以求改进 D．分析算法的易懂性 二、填空题 1、数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。 2、线性结构中元素之间存在的关系，树形结构中元素之间存在的关系， 图形结构中元素之间存在的关系。 3、________是数据不可分割的最小单元，是具有独立含义的最小标识单位。例如构成一个数据元素的字段、域、属性等都可称之为________。 4、数据的________指数据元素及其关系在计算机存储器内的表示。_________是逻辑结构在计算机里的实现，也称之为映像。 5、所谓算法（Algorithm）是对特定问题求解方法和步骤的一种描述，它是指令的一组__________，其中每个指令表示一个或多个操作。 三、问答题 1、用大O形式写出下面算法的时间复杂度： i＝0； s=0； while(s＜n） ｛ i++; s+=i; ｝ 2、写出以下算法的时间复杂度： for（i＝0; i＜m; i＋＋） for（j＝0 ; j＜t; j＋＋） c[i][j]=0； for（i=0；i＜m；i＋＋） for（j=o; j

数据结构考试试题库含答案解析

数据结构习题集含答案 目录 目录 (1) 选择题 (2) 第一章绪论 (2) 第二章线性表 (4) 第三章栈和队列 (6) 第四章串 (7) 第五章数组和广义表 (8) 第六章树和二叉树 (8) 第七章图 (11) 第八章查找 (13) 第九章排序 (14) 简答题 (19) 第一章绪论 (19) 第二章线性表 (24) 第三章栈和队列 (26) 第四章串 (28) 第五章数组和广义表 (29) 第六章树和二叉树 (31) 第七章图 (36) 第八章查找 (38) 第九章排序 (39) 编程题 (41) 第一章绪论 (41) 第二章线性表 (41) 第三章栈和队列 (52) 第四章串 (52) 第五章数组和广义表 (52) 第六章树和二叉树 (52) 第七章图 (52) 第八章查找 (52) 第九章排序 (57)

选择题 第一章绪论 1.数据结构这门学科是针对什么问题而产生的？（A ） A、针对非数值计算的程序设计问题 B、针对数值计算的程序设计问题 C、数值计算与非数值计算的问题都针对 D、两者都不针对 2.数据结构这门学科的研究内容下面选项最准确的是（D ） A、研究数据对象和数据之间的关系 B、研究数据对象 C、研究数据对象和数据的操作 D、研究数据对象、数据之间的关系和操作 3.某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90 分，那么下面关于数据对象、数据元素、数据项描述正确的是（C ） A、某班级的学生成绩表是数据元素，90分是数据项 B、某班级的学生成绩表是数据对象，90分是数据元素 C、某班级的学生成绩表是数据对象，90分是数据项 D、某班级的学生成绩表是数据元素，90分是数据元素 4.*数据结构是指（A ）。 A、数据元素的组织形式 B、数据类型 C、数据存储结构 D、数据定义 5.数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。 A、存储结构 B、逻辑结构 C、链式存储结构 D、顺序存储结构 6.算法分析的目的是（C ） A、找出数据的合理性 B、研究算法中的输入和输出关系

数据结构试题及答案

好风光好感动1、线性表的逻辑顺序与物理顺序总是一致的。( x ) 2、线性表的顺序存储表示优于链式存储表示。( X ) 3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。( v ) 4、二维数组是其数组元素为线性表的线性表。( v ) 5、每种数据结构都应具备三种基本运算：插入、删除和搜索。( x ) 6、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个 方面。( v ) 7、线性表中的每个结点最多只有一个前驱和一个后继。（x ） 8、线性的数据结构可以顺序存储，也可以存储。非线性的数据结构只能存储。（x ） 9、栈和队列逻辑上都是线性表。（v ） 10、单链表从任何一个结点出发，都能访问到所有结点（v ） 11、删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。（x ） 12、快速排序是排序算法中最快的一种。（x ） 13、多维数组是向量的推广。（x） 14、一般树和二叉树的结点数目都可以为0。（v） 15、直接选择排序是一种不稳定的排序方法。（x ） 16、98、对一个堆按层次遍历，不一定能得到一个有序序列。（v ） 17、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。（x ） 18、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。（x ） 19、堆栈在数据中的存储原则是先进先出。（x ） 20、队列在数据中的存储原则是后进先出。（x ） 21、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。（x ） 22、哈夫曼树一定是满二叉树。（x ） 23、程序是用计算机语言表述的算法。（v） 24、线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。（v ） 25、用一组地址连续的存储单元存放的元素一定构成线性表。（v ） 26、堆栈、队列和数组的逻辑结构都是线性表结构。（v ） 27、给定一组权值，可以唯一构造出一棵哈夫曼树。（x ） 28、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。（v ） 29、希尔排序在较率上较直接接入排序有较大的改进。但是不稳定的。（v ）

数据结构考试题库含参考答案

第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）。【北京邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（）【中科院计算所1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 【南京理工大学1999 一、1（2分）【武汉交通科技大学1996 一、1（4分）】4．一个算法应该是（）。【中山大学1998 二、1（2分）】 A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C. 5. 下面关于算法说法错误的是（）【南京理工大学2000 一、1（1.5分）】 A．算法最终必须由计算机程序实现 B. 为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的

6. 下面说法错误的是（）【南京理工大学2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。【武汉交通科技大学1996 一、4（2分）】 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。【北方交通大学2000 二、1（2分）】 A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？【北方交通大学2001 一、1（2分）】 A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（）【北方交通大学2001 一、2（2分）】 A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学2001 一、10（3分）】

数据结构习题及答案

第一章 1．在数据结构中，从逻辑上可以把数据结构分为（C ） A．动态结构和静态结构 B. 紧凑结构和非紧凑结构 C．线性结构和非线性结构 D. 内部结构和外部结构 ● 2.在数据结构中,与所使用的计算机无关的是( A ) A. 逻辑结构 B. 存储结构 C. 逻辑和存储结构 D. 物理结构 3.下面程序的时间复杂度为____O（mn）_______。 for (int i=1; i<=m; i++) for (int j=1; j<=n; j++ ) S+=i 第二章线性表 ●链表不具备的特点是（A） A 可以随机访问任一结点（顺序） B 插入删除不需要移动元素 C 不必事先估计空间 D 所需空间与其长度成正比 2. 不带头结点的单链表head为空的判定条件为（A ），带头结点的单链表head为空的判定条件为（B ） A head==null B head->next==null C head->next==head D head!=null ●3.在线性表的下列存储结构中，读取元素花费时间最少的是（D） A 单链表 B 双链表 C 循环链表 D 顺序表 ● 4.对于只在表的首、尾两端进行手稿操作的线性表，宜采用的存储结构为(C) A 顺序表 B 用头指针表示的单循环链表 C 用尾指针表示的单循环链表 D 单链表 ● 5.在一个具有n 个结点的有序单链表中插入一个新的结点，并保持链表元素仍然有序， 则操作的时间复杂度为( D ) A O(1) B O(log2n) C O(n2) D O(n) ● 6.在一个长度为n (n>1)的单链表上，设有头和尾两个指针，执行(B)操作与链表的长 度有关 A 删除单链表中第一个元素 B 删除单链表中最后一个元素 C 在第一个元素之前插入一个新元素 D 在最后一个元素之后插入一个新元素 ●7.与单链表相比，双向链表的优点之一是(D) A 插入删除操作更简单 B 可以进行随机访问 C 可以省略表头指针或表尾指针 D 顺序访问相邻结点更容易 ●8.若list是某带头结点的循环链表的头结点指针，则该链表最后那个链结点的指针域 (头结点的地址)中存放的是( B ) A list的地址 B list的内容 C list指的链结点的值 D 链表第一个链结点的地址 ●9.若list1和list2分别为一个单链表与一个双向链表的第一个结点的指针，则( B ) A list2比list1占用更多的存储单元 B list1与list2占用相同的存储单元 C list1和list2应该是相同类型的指针变量 D 双向链表比单链表占用更多的存储单元 10.链表中的每个链结点占用的存储空间不必连续，这句话正确吗？ (不正确) 11. 某线性表采用顺序存储结构，元素长度为4，首地址为100，则下标为12的（第13个）元素的存储地址为148。V 100+4*12=148 11.在顺序表的（最后一个结点之后）插入一个新的数据元素不必移动任何元素。 12.若对线性表进行的操作主要不是插入删除，则该线性表宜采用（顺序）存储结构，若频繁地对线性表进行插入和删除操作，则该线性表宜采用( 链 )存储结构。