数据结构复习题(4A)

A. p = L; p-> next = L; B. p-> next = L; p = L; C. p-> next = L; L = p; D. L = p; p-> next = L; 标准答案：C

27.设单循环链表中结点的结构为（data, link），且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行的操作是（ ）。

A. s = rear; rear = rear->link; delete s; B. rear = rear->link; delete rear;

C.rear = rear->link->link; delete rear;

D.s = rear->link->link; rear->link->link = s->link; delete s; 标准答案：D

28.某算法的时间代价为T(n)=100n+10nlog2n+n2+10，其时间复杂度为（ ）。

A. O(n) B. O(nlog2n) C. O(n2) D. O(1) 标准答案：C

29.在一个长度为n的顺序表中向第i个元素（0≤i≤n-1）位置插入一个新元素时，需要从后向前依次后移（ ）个元素。

A. n-i B. n-i+1 C. n-i-1 D. i 标准答案：A

30.在一个长度为n的顺序表的任一位置插入一个新元素的时间复杂度为（ ）。

2

A. O(n) B. O(n/2) C. O(1) D. O(n) 标准答案：A

31.多维数组实际上是由嵌套的（ ）实现的。

A. 一维数组 B. 多项式 C. 三元组表 D. 简单变量 标准答案：A

32.设有一个n×n的对称矩阵A，将其下三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么第i行的对角元素A[i][i]存放于B中（ ）处。

A. (i+3)*i/2 B. (i+1)*i/2 C. (2n-i+1)*i/2 D. (2n-i-1)*i/2 标准答案：A

33.利用双向链表作线性表的存储结构的优点是（ ）。

A. 便于单向进行插入和删除的操作 B. 便于双向进行插入和删除的操作 C. 节省空间 D. 便于销毁结构释放空间 标准答案：B

34.在数据结构的讨论中把数据结构从逻辑上分为（ ）。

A. 内部结构与外部结构 B. 静态结构与动态结构 C. 线性结构与非线性结构 D. 紧凑结构与非紧凑结构 标准答案：C

35.单链表A长度为m，单链表B长度为n，若将B联接在A的末尾，其时间复杂度应为（ ）。

A. O(1) B. O(m) C. O(n) D. O(m+n) 标准答案：B

36.带表头的双向循环链表的空表满足（ ）。

A. first＝NULL; B. first->rLink==first C. first->lLink==NULL D. first->rLink==NULL 标准答案：B

37.一个记录r理论上占有的存储空间的大小等于所有域类型长度之和，实际上占有的存储空间的大小即记录长度为( )。

A. 所有域长度之和 B. 最大域所占字节长度 C. 任意一个域长度 D. sizeof(r)的值

5

标准答案：D

38.采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（ ）。

A. n B. n/2 C. (n-1)/2 D. (n+1)/2 标准答案：D

39.在二维数组中，每个数组元素同时处于（ ）个向量中。

A. 0个 B. 1个 C. 2个 D. n个 标准答案：C

40.设单链表中结点的结构为（data, link）。已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行的操作是（ ）。

A. s->link=p; p->link=s; B. p->link=s; s->link=p;

C. s->link=p->link; p=s; D. s->link=p->link; p->link=s; 标准答案：D

41.非空的循环单链表first的尾结点（由p所指向）满足的条件是（ ）。

A. p->link==NULL; B. p==NULL; C. p->link==first; D. p==first; 标准答案：C

42.从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需要平均比较的结点数是（ ）。

A. n B. n/2 C. (n-1)/2 D. (n+1)/2 标准答案：D

43.采用线性链表表示一个向量时，要求占用的存储空间地址（ ）。

A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 可连续可不连续 标准答案：D

44.在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（ ）。

A. O(1) B. O(n) C. O(n2) D. O(nlog2n) 标准答案：B

45.在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）位置插入一个新元素时，需要从后向前依次后移（ ）个元素。

A. n-i B. n-i+1 C. n-i-1 D. i 标准答案：B

46.在一个单链表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; 标准答案：B

47.下面程序段的时间复杂度为( )。

for(int i=0; i

A. O(m2) B. O(n2) C. O(m×n) D. O(m+n) 标准答案：C

48.在一个长度为n的顺序表中删除一个值为x的元素时，需要比较元素和移动元素的总次数为（ ）。

A. (n+1)/2 B. n/2 C. n D. n+1 标准答案：C

49.在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（ ）。

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

6

标准答案：C

50.在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为（ ）。

A. O(n) B. O(1) C. O(n2) D. O(log2n) 标准答案：B

51.链表不具有的特点是( )。

A. 可随机访问任一个元素 B. 插入删除不需要移动元素

C. 不必事先估计存储空间 D. 所需空间与线性表的长度成正比 标准答案：A

52. 输出一个二维数组b[m][n]中所有元素值的时间复杂度为( )。

A. O(n) B. O(m+n) C. O(n2) D. O(m×n) 标准答案：D

二、填空题（共有题目24题）

1.在以HL为表头指针的带表头附加结点的单链表和循环单链表中，链表为空的条件分别为HL->next==NULL和HL->next==HL。

2.线性表的链接存储只能通过链接指针顺序访问。

3.链表是一种采用链式（或链接_）存储结构存储的线性表。 4.在线性表的单链接存储结构（结点）中，若一个元素所在结点的地址为p，则其后继结点的地址为p->next，后继结点的值为p->next->data。

5.若设L是指向带表头的单链表, 语句 L->link=L->link->link的作用是删除单链表中的第一个结点。 6.在单链表中除了表头结点外，任意结点的存储位置由其直接前驱结点的指针域的值所指示。

7.在双向链表中，每个结点包含两个指针域，一个指向其前驱（双亲、父）结点，另一个指向其后继（孩子、子）结点。

8.链接存储表示的结点存储空间一般在程序的运行过程中进行动态地分配_和释放。 9.在链表中进行插入和删除操作的效率比在顺序存储结构中进行相同操作的效率高。

10.在线性表的单链接存储结构（结点）中，若一个元素所在结点的地址为p，p为一个数组a中的下标，则其后继结点的地址为&a[p].next 或(a+p)->next。

11.在线性表的顺序存储结构中，若一个元素的下标为i，则它的前驱元素的下标为i-1，后继元素的下标为i+1_。

12.单链表中逻辑上相邻的结点而在物理位置上不一定相邻。

13.链表对于数据元素的插入和删除不需要移动结点，只需要改变相应结点的指针域的值。

14.在循环双向链表中表头结点的左指针域指向表尾结点，最后一个结点的右指针域指向表头结点。 15.对于一个单链接存储的线性表，在表头插入结点的时间复杂度为O(1)，在表尾插入元素的时间复杂度为O(n)。

16.在循环单链表中，最后一个结点的指针域指向表头_结点。 17.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为O(n)，在表尾插入元素的时间复杂度为O(1)。

18.链表与顺序表、索引表、散列表等都是数据逻辑结构的存储表示。

19.在线性表的单链接存储结构中，每个结点包含有两个域，一个叫数值域，另一个叫指针域。 20.在单链表设置表头结点的作用是插入和删除表中第一个元素时不必对表头指针进行特殊处理。 21.在双向链表中， 每个结点除了数据域外, 还有两个指针域, 它们分别指向前驱结点和后继结点。 22.链表只适用于顺序查找。

23.设双向循环链表每个结点结构为(data,llink,rlink)，则结点*p的前驱结点的地址为p->llink。 24.线性表是具有相同属性_的数据元素的一个有限序列。 25.逻辑顺序与物理顺序一致的数据结构是________。 三、判断题（共有题目17题）

1.数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。对

7

2.多维数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。对 3. 线性表若采用链式存储表示时，其存储结点的地址可连续也可不连续。对 4.在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。错 5.用字符数组存储长度为n的字符串，数组长度至少为n+1。对 6.数据元素是数据的最小单位。错

7.在对双向循环链表做删除一个结点操作时，应先将被删除结点的前驱结点和后继结点链接好再执行删除结点操作。 对

8. 如果采用如下方法定义一维字符数组：

int maxSize = 30;

char * a = new char[maxSize]; 错

9.线性表若采用链式存储表示, 在删除时不需要移动元素。对 10.数据的逻辑结构与数据元素本身的内容和形式无关。对 11. 如果采用如下方式定义一维字符数组：

const int maxSize = 30; char a[maxSize];

则这种数组在程序执行过程中不能扩充。对

12.算法和程序原则上没有区别，在讨论数据结构时二者是通用的。 错 13. 顺序表和一维数组一样，都可以按下标随机（或直接）访问。对 14.在线性链表中删除中间的结点时，只需将被删结点释放。 错 四、程序填空题（共有题目3题）

1.下面程序段实现的功能是向单链表的表头插入一个元素X，请补充完整程序。

void InsertFirstList(struct sNode **HL,ElemType x) { struct sNode *newp; newp=malloc(sizeof(struct sNode)); if(newp==NULL) {

printf(\内存动态空间用完，退出运行！\\n\ exit(1); }

newp->data=X; newp->next=*HL; *HL=newp;}

2.下面程序段实现的功能是向单链表的表尾插入一个元素X，请补充完整程序。

void InsertLastList(struct sNode **HL,ElemType x) { struct sNode *newp; newp=malloc(sizeof(struct sNode)); if(newp==NULL) {

printf(\内存动态空间用完，退出运行！\\n\exit(1); } newp->data=x; newp->next=NULL或 0; if(*HL==NULL) *HL=newp; Else

{struct sNode *p=*HL; while(p->next!=NULL) p=p->next; p->next=newp;

8