数据结构习题-分章

习题1 DS概述

一、单项选择题

1. 数据结构是指（ ）。

A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义

2. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（ ）。

A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 3. 树形结构是数据元素之间存在一种（ ）。

A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系

4. 设语句x++的时间是单位时间，则以下语句的时间复杂度为（ ）。

for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++;

A.O(1)

B.O(n)

2 C.O(n)

D.O(n)

35. 算法分析的目的是（1），算法分析的两个主要方面是（2）。

（1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系

C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性

C.可读性和文档性 D.数据复杂性和程序复杂性 6. 计算机算法指的是（1），它具备输入，输出和（2）等五个特性。 （1） A.计算方法 B.排序方法

C.解决问题的有限运算序列 D.调度方法

（2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性

C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性

7. 数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（ ）。

A.低 B.高 C.相同 D.不好说 8. 数据结构作为一门独立的课程出现是在（ ）年。

A.1946 B.1953 C.1964 D.1968 9. 数据结构只是研究数据的逻辑结构和物理结构，这种观点（ ）。

A.正确 B.错误

C.前半句对，后半句错 D.前半句错，后半句对 10. 计算机内部数据处理的基本单位是（ ）。

A.数据 B.数据元素 C.数据项 D.数据库

11 下面程序的时间复杂为（ ）

for（i=1，s=0； i<=n； i++） {t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；}

234

(A) O(n) (B) O(n) (C) O(n) (D) O(n)

12设某数据结构的二元组形式表示为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>}，则数据结构A是（ ）。 (A) 线性结构 (B) 树型结构 (C) 物理结构 (D) 图型结构

13 数据的最小单位是（ ）。 (A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量 14 程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的时间复杂度为（ ）。

(A) O(n) (B) O(nlog2n) (C) O(n) (D) O(n/2) 15 下列程序段的时间复杂度为（ ）。

for(i=0； i

for(i=0； i

i=0，s=0； while (s

1/21/32

(A) O(n) (B) O(n) (C) O(n) (D) O(n) 17 以下数据结构中哪一个是非线性结构？( )

A. 队列 B. 栈 C. 线性表 D. 二叉树

二、填空题

1. 数据结构按逻辑结构可分为两大类，分别是______________和_________________。

2. 数据的逻辑结构有四种基本形态，分别是________________、__________________、__________________和__________________。

3. 线性结构反映结点间的逻辑关系是__________________的，非线性结构反映结点间的逻辑关系是__________________的。

4. 一个算法的效率可分为__________________效率和__________________效率。

5. 在树型结构中，树根结点没有__________________结点，其余每个结点的有且只有__________________个前趋驱结点；叶子结点没有__________________结点；其余每个结点的后续结点可以__________________。

6. 在图型结构中，每个结点的前趋结点数和后续结点数可以__________________。

7. 线性结构中元素之间存在__________________关系；树型结构中元素之间存在__________________关系；图型结构中元素之间存在__________________关系。

8. 下面程序段的时间复杂度是__________________。

for(i=0;i

A[i][j]=0;

23

9. 下面程序段的时间复杂度是__________________。

i=s=0; while(s

10. 下面程序段的时间复杂度是__________________。

s=0;

for(i=0;i

11. 下面程序段的时间复杂度是__________________。

i=1; while(i<=n) i=i*3;

12. 衡量算法正确性的标准通常是____________________________________。

13. 算法时间复杂度的分析通常有两种方法，即___________和___________的方法，通常我们对算法求时间复杂度时，采用后一种方法。

14 for(i=1，t=1，s=0；i<=n；i++) {t=t*i；s=s+t；}的时间复杂度为_________。

15通常从四个方面评价算法的质量：_________、_________、_________和_________。 16 一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。

数据的物理结构主要包括_____________和______________两种情况。顺序存储结构、链式存储结构

三、求下列程序段的时间复杂度。

1. x=0;

for(i=1;i

2. x=0;

for(i=1;i

3. int i,j,k;

for(i=0;i

for(k=0;k

c[i][j]=a[i][k]*b[k][j]

}

4. i=n-1;

while((i>=0)&&A[i]!=k)) j--; return (i);

5. fact(n)

{ if(n<=1)

return (1);

else

return (n*fact(n-1)); }

习题1 参考答案 DS概述

一、单项选择题

1. A 2. C 3. D 4. B 5. C、A 6. C、B 7. B 8. D 9. B 10. B 11.B 12B 13A 14A 15A 16A 17D 二、填空题

1. 线性结构，非线性结构 2. 集合，线性，树，图 3. 一对一，一对多或多对多 4. 时间，空间

5. 前趋，一，后继，多 6. 有多个

7. 一对一，一对多，多对多 8. O(n) 9. O(n) 10. O(n) 11. O(log3n)

12. 程序对于精心设计的典型合法数据输入能得出符合要求的结果。 13. 事后统计，事前估计 14 O(n)

15正确性 易读性 强壮性 高效率 15 O(n)

三、算法设计题

1. O(n) 2. O(n) 3. O(n) 4. O(n) 5. O(n)

22322习题2 顺序表和链表

一、单项选择题

1. 线性表是________。

A．一个有限序列，可以为空 B．一个有限序列，不可以为空 C．一个无限序列，可以为空 D．一个无限序列，不可以为空

2. 在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时，需向前移动 个元素。 A．n-i B．n-i+l C．n-i-1 D．i 3. 线性表采用链式存储时，其地址________。

A．必须是连续的 B．一定是不连续的 C．部分地址必须是连续的 D．连续与否均可以

4. 从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较________个元素结点。

A．n/2 B．n C．（n+1）/2 D．（n-1）/2

5. 在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是____。

A． p->next=s; s->prior=p;

p->next->prior=s; s->next=p->next; B． s->prior=p; s->next=p->next; p->next=s; p->next->prior=s; C． p->next=s; p->next->prior=s; s->prior=p; s->next=p->next; D． s->prior=p; s->next=p->next; p->next->prior=s; p->next=s;

6. 设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为________。

A．p->next=p->next->next; B．p=p->next; C．p=p->next->next; D．p->next=p;

7. 在一个长度为n的顺序表中向第i个元素(0< i

A．n-i B．n-i+l C．n-i-1 D．i

8. 在一个单链表中，已知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

9. 以下关于线性表的说法不正确的是______。

A．线性表中的数据元素可以是数字、字符、记录等不同类型。 B．线性表中包含的数据元素个数不是任意的。

C．线性表中的每个结点都有且只有一个直接前趋和直接后继。 D．存在这样的线性表：表中各结点都没有直接前趋和直接后继。 10. 线性表的顺序存储结构是一种_______的存储结构。

A．随机存取 B．顺序存取 C．索引存取 D．散列存取

11. 在顺序表中，只要知道_______，就可在相同时间内求出任一结点的存储地址。 A．基地址 B．结点大小 C．向量大小 D．基地址和结点大小

12. 在等概率情况下，顺序表的插入操作要移动______结点。 A．全部 B．一半 C．三分之一 D．四分之一 13. 在______运算中，使用顺序表比链表好。 A．插入 B．删除

O(n)。

6 q->llink=p; q->rlink=p->rlink; p->rlink->llink=q; p->rlink=q; 7线性表为：（78，50，40，60，34，90）

四、算法设计题

1．算法思想为：

（1）应判断删除位置的合法性，当i<0或i>n-1时，不允许进行删除操作； （2）当i=0时，删除第一个结点：

（3）当０

delete(LinkList *q,int i)

{ //在无头结点的单链表中删除第i个结点 LinkList *p,*s; int j; if(i<0)

printf(\ else if(i= =0) { s=q; q=q->next; free(s); }

else

{ j=0; s=q;

while((jnext;

j++; }

if (s= =NULL)

printf(\ delete\

else

{ p->next=s->next; free(s); } } }

2．由于在单链表中只给出一个头指针，所以只能用遍历的方法来数单链表中的结点个数了。算法描述如下：

int ListLength ( LinkList *L ) { //求带头结点的单链表的表长 int len=0; ListList *p; p=L;

while ( p->next!=NULL ) { p=p->next; len++; }

return (len); }

3．设单循环链表的头指针为head，类型为LinkList。逆置时需将每一个结点的指针域作以修改，使其原前

趋结点成为后继。如要更改q结点的指针域时，设s指向其原前趋结点，p指向其原后继结点，则只需进行q->next=s;操作即可，算法描述如下：

void invert(LinkList *head)

{ //逆置head指针所指向的单循环链表 linklist *p, *q, *s; q=head; p=head->next;

while (p!=head) //当表不为空时，逐个结点逆置 { s=q; q=p; p=p->next; q->next=s; } p->next=q; }

4．定义类型LinkList如下：

typedef struct node { int data;

struct node *next,*prior; }LinkList;

此题可采用插入排序的方法，设p指向待插入的结点，用q搜索已由prior域链接的有序表找到合适位置将p结点链入。算法描述如下：

insert (LinkList *head) { LinkList *p,*s,*q;

p=head->next; //p指向待插入的结点，初始时指向第一个结点 while(p!=NULL)

{ s=head; // s指向q结点的前趋结点

q=head->prior; //q指向由prior域构成的链表中待比较的结点

while((q!=NULL) && (p->data>q->data)) //查找插入结点p的合适的插入位置

{ s=q;

q=q->prior; } s->prior=p;

p->prior=q; //结点p插入到结点s和结点q之间 p=p->next;

} }

5．算法描述如下：

delete(LinkList *head, int max, int min) { linklist *p, *q; if (head!=NULL) { q=head; p=head->next;

while((p!=NULL) && (p->data<=min)) { q=p;

p=p->next; }

while((p!=NULL) && (p->datanext; q->next=p;

} }

6．算法描述如下：

delete(LinkList *head, int max, int min) { LinkList *p,*q; q=head; p=head->next; while (p!=NULL)

if((p->data<=min) || (p->data>=max)) { q=p; p=p->next; }

else

{ q->next=p->next;

free(p); p=q->next; } }

8．只要从终端结点开始往前找到第一个比x大(或相等)的结点数据，在这个位置插入就可以了。算法描述如下：

int InsertDecreaseList( SqList *L, elemtype x ) { int i;

if ( (*L).len>= maxlen) { printf(“overflow\ return(0); }

for ( i=(*L).len ; i>0 && (*L).elem[ i-1 ] < x ; i--) (*L).elem[ i ]=(*L).elem[ i-1 ] ; // 比较并移动元素 (*L).elem[ i ] =x; (*L).len++; return(1); }

9. int CountX(LNode* HL,ElemType x) { int i=0; LNode* p=HL;//i为计数器 while(p!=NULL)

{ if (P->data==x) i++; p=p->next;

}//while, 出循环时i中的值即为x结点个数 return i; }//CountX

11 设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C用链式存储结构

表示。

typedef struct node {int data; struct node *next;}lklist; void intersection(lklist *ha,lklist *hb,lklist *&hc) {

lklist *p,*q,*t;

for(p=ha,hc=0;p!=0;p=p->next)

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

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

}

12设计在单链表中删除值相同的多余结点的算法。

typedef int datatype;

typedef struct node {datatype data; struct node *next;}lklist; void delredundant(lklist *&head) {

lklist *p,*q,*s;

for(p=head;p!=0;p=p->next) {

for(q=p->next,s=q;q!=0; )

if (q->data==p->data) {s->next=q->next; free(q);q=s->next;} else {s=q,q=q->next;} } }

13设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。

typedef char datatype;

typedef struct node {datatype data; struct node *next;}lklist; void split(lklist *head,lklist *&ha,lklist *&hb,lklist *&hc) {

lklist *p; ha=0,hb=0,hc=0; for(p=head;p!=0;p=head) {

head=p->next; p->next=0;

if (p->data>='A' && p->data<='Z') {p->next=ha; ha=p;}

else if (p->data>='0' && p->data<='9') {p->next=hb; hb=p;} else {p->next=hc; hc=p;} } }

14 设计两个有序单链表的合并排序算法。

void mergelklist(lklist *ha,lklist *hb,lklist *&hc) {

lklist *s=hc=0;

while(ha!=0 && hb!=0)

if(ha->datadata){if(s==0) hc=s=ha; else {s->next=ha; s=ha;};ha=ha->next;} else {if(s==0) hc=s=hb; else {s->next=hb; s=hb;};hb=hb->next;} if(ha==0) s->next=hb; else s->next=ha; }

15设计判断单链表中元素是否是递增的算法。

int isriselk(lklist *head) {

if(head==0||head->next==0) return(1);else

for(q=head,p=head->next; p!=0; q=p,p=p->next)if(q->data>p->data) return(0); return(1);

}

五、算法阅读

（1）该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为

新的开始结点，返回新链表的头指针。 （2）查询链表的尾结点

（3）将第一个结点链接到链表的尾部，作为新的尾结点 （4）返回的线性表为（a2,a3,?,an,a1）

字符串的长度是指（C ）。

(A) 串中不同字符的个数 (B) 串中不同字母的个数 (C) 串中所含字符的个数 (D) 串中不同数字的个数

二、填空题

1. 计算机软件系统中，有两种处理字符串长度的方法：一种是___________，第二种是___________________。 2. 两个字符串相等的充要条件是_____________________和___________________。

3. 设字符串S1= “ABCDEF”，S2= “PQRS”，则运算S=CONCAT（SUB（S1，2，LEN（S2）），SUB（S1，LEN（S2），2））后的串值为___________________。

4. 串是指___________________。

5. 空串是指___________________，空格串是指___________________。 三、算法设计题

1. 设有一个长度为s的字符串，其字符顺序存放在一个一维数组的第1至第s个单元中（每个单元存放一个字符）。现要求从此串的第m个字符以后删除长度为t的子串，m

2. 设s和t是表示成单链表的两个串，试编写一个找出s中第1个不在t中出现的字符（假定每个结点只存放1个字符）的算法。

习题参考答案 串

一、单项选择题 1．B

2．D

3．C

4．D

5．B

6．C

7．D

8．C

9．D

二、填空题

1. 固定长度，设置长度指针

2. 两个串的长度相等，对应位置的字符相等 3. “BCDEDE”

4. 含n个字符的有限序列 （n≥0）

5. 不含任何字符的串，仅含空格字符的字符串 三、算法设计题 1．算法描述为：

int delete(r,s,t,m) //从串的第m个字符以后删除长度为t的子串 char r[ ]; int s,t,m; { int i,j;

for(i=1;i<=m;i++)

r[s+i]=r[i]; for(j=m+t-i;j<=s;j++)

r[s-t+j]=r[j]; return (1); } //delete

2．算法思想为：

（1）链表s中取出一个字符；将该字符与单链表t中的字符依次比较；

（2）当t中有与从s中取出的这个字符相等的字符，则从t中取下一个字符重复以上比较； （3）当t中没有与从s中取出的这个字符相等的字符，则算法结束。

设单链表类型为LinkList；注意，此时类型 LinkList中的data成分为字符类型。

LinkString find(s,t) LinkString *s, *t; { LinkString *ps, *pt; ps=s;

while(ps!=NULL) { pt=t;

while((pt!=NULL)&&(ps->data!=pt->data)) pt=pt->next; if(pt= =NULL)

ps=NULL;

else

{ ps=ps->next;

s=ps;

} } return s; } //find

1. 设计在顺序存储结构上实现求子串算法。

void substring(char s[ ], long start, long count, char t[ ])

{

long i,j,length=strlen(s);

if (start<1 || start>length) printf(\ else if (start+count-1>length) printf(\else { for(i=start-1,j=0; i

习题5 数组和广义表

一、单项选择题

1. 设二维数组A[0?m-1][0?n-1]按行优先顺序存储在内存中，第一个元素的地址为p，每个元素占k个字节，则元素aij的地址为（ ）。

A.p +[i*n+j-1]*k B.p+[(i-1)*n+j-1]*k C.p+[(j-1)*n+i-1]*k D.p+[j*n+i-1]*k

2. 已知二维数组A10×10中，元素a20的地址为560，每个元素占4个字节，则元素a10的地址为（ ）。 A.520 B.522 C.524 D.518 3. 若数组A[0?m][0?n]按列优先顺序存储，则aij地址为（ ）。 A.LOC(a00)+[j*m+i] B. LOC(a00)+[j*n+i]

C.LOC(a00)+[(j-1)*n+i-1] D. LOC(a00)+[(j-1)*m+i-1]

4. 若下三角矩阵An×n，按列顺序压缩存储在数组Sa[0?(n+1)n/2]中，则非零元素aij的地址为（ ）。（设每个元素占d个字节）

(j?2)(j?1)+i-1]*d

2(j?2)(j?1)B. [(j-1)*n-+i]*d

2(j?2)(j?1)C．[(j-1)*n-+i+1]*d

2(j?2)(j?1)D．[(j-1)*n-+i-2]*d

2A. [(j-1)*n-5. 设有广义表D=(a,b,D)，其长度为（ ），深度为（ ）。

A.无穷大 B.3 C.2 D.5 6. 广义表A=（a），则表尾为（ ）。

A.a B.(( )) C.空表 D.(a)

7. 广义表A=((x,(a,B)),(x,(a,B),y))，则运算head(head(tail(A)))的结果为（ ）。 A.x B.(a,B) C.(x,(a,B)) D.A 8. 下列广义表用图来表示时，分支结点最多的是（ ）。 A.L=((x,(a,B)),(x,(a,B),y)) B.A=(s,(a,B))

C.B=((x,(a,B),y)) D.D=((a,B),(c,(a,B),D) 9. 通常对数组进行的两种基本操作是（ ）。

A.建立与删除 B.索引和修改 C.查找和修改 D.查找与索引

10. 假定在数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数为（ ）。

A.80 B.100 C.240 D.270

11. 数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为（ ）。

A.SA+141 B.SA+144 C.SA+222 D.SA+225 12. 稀疏矩阵一般的压缩存储方法有两种，即（ ）。 A.二维数组和三维数组 B.三元组和散列 C.三元组和十字链表 D.散列和十字链表

13. 若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点（ ）。

A.正确 B.不正确 14. 一个广义表的表头总是一个（ ）。

A.广义表 B.元素 C.空表 D.元素或广义表

15. 一个广义表的表尾总是一个（ ）。

A.广义表 B.元素 C.空表 D.元素或广义表 16. 数组就是矩阵，矩阵就是数组，这种说法（ ）。 A.正确 B.错误 C.前句对，后句错 D.后句对

17 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。

A．688 B．678 C．692 D．696

18 设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（C ）。

(A) O(n) (B) O(nlog2n) (C) O(1) (D) O(n2) 19 设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为（ B ）。 (A) 10 (B) 19 (C) 28 (D) 55 二、填空题

1. 一维数组的逻辑结构是______________，存储结构是______________；对于二维或多维数组，分为______________和______________两种不同的存储方式。

2. 对于一个二维数组A[m][n]，若按行序为主序存储，则任一元素A[i][j]相对于A[0][0]的地址为______________。

3. 一个广义表为(a,(a,b),d,e,((i,j),k))，则该广义表的长度为_____，深度为_____。 4. 一个稀疏矩阵为 ? 2 0 ? ，则对应的三元组线性表为_____________。 0 0

5. 一个n×n的对称矩阵，如果以行为主序或以列为主序存入内存，则其容量为______________。 6. 已知广义表A=((a,b,c),(d,e,f))，则运算head(tail(tail(A)))=____________。 7. 设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a85的地址为______________。

8. 已知广义表Ls=(a,(b,c,d),e)，运用head和tail函数取出Ls中的原子b的运算是______________。 9. 三维数组R[c1?d1,c2?d2,c3?d3]共含有______________个元素。（其中：c1≤d1,c2≤d2,c3≤d3）

10. 数组A[1?10，-2?6，2?8]以行优先的顺序存储，设第一个元素的首地址是100，每个元素占3个存储长度的存储空间，则元素A[5，0，7]的存储地址为______________。

11设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角线上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有_ i(i+1)/2+j-1_个数据元素。

三、判断题

1. 数组可看作基本线性表的一种推广，因此与线性表一样，可以对它进行插入、删除等操作。（ ） 2. 多维数组可以看作数据元素也是基本线性表的基本线性表。（ ） 3. 以行为主序或以列为主序对于多维数组的存储没有影响。（ ） 4. 对于不同的特殊矩阵应该采用不同的存储方式。（ ）

5. 采用压缩存储之后，下三角矩阵的存储空间可以节约一半。（ ）

6. 在一般情况下，采用压缩存储之后，对称矩阵是所有特殊矩阵中存储空间节约最多的。（ ） 7. 矩阵不仅是表示多维数组，而且是表示图的重要工具。（ ） 8. 距阵中的数据元素可以是不同的数据类型。（ ） 9. 矩阵中的行列数往往是不相等的。（ ）

10. 广义表的表头可以是广义表，也可以是单个元素。（ ） 11. 广义表的表尾一定是一个广义表。（ ）

12. 广义表的元素可以是子表，也可以是单元素。（ ） 13. 广义表不能递归定义。（ ）

?3000????00?15????0000?

本文来源：https://www.bwwdw.com/article/zwk.html