# 



# 数构习题

## 第一章

1.在数据结构中，从逻辑上可以把数据结构分成()。<span title="C">---查看</span>

　　A.动态结构和静态结构

　　B.紧凑结构和非紧凑结构

　　C.线性结构和非线性结构

　　D.内部结构和外部结构

​	

2.与数据元素本身的形式、内容、相对位置、个数无关的是数据的()。<span title="C">---查看</span>

　　A.存储结构

　　B.存储实现

　　C.逻辑结构

　　D.运算实现

​	

3.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着()<span title="B">---查看</span>

​		A.数据具有同一特点

​		B.不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致

​		C.每个数据元素都一样

​		D.数据元素所包含的数据项的个数要相等

​	

4.以下说法正确的是()。<span title="D">---查看</span>

　　A.数据元素是数据的最小单位<span title="数据项是数据的最小单位；数据元素是数据的基本单位">---查看</span>

　　B.数据项是数据的基本单位<span title="数据项是数据的最小单位；数据元素是数据的基本单位">---查看</span>

　　C.数据结构是带有结构的各数据项的集合<span title="数据结构是带有结构的各数据元素的集合">---查看</span>

　　D.一些表面上很不相同的数据可以有相同的逻辑结构

​	

5.算法的时间复杂度取决于()<span title="D">---查看</span>

​		A.问题的规模

​		B.待处理数据的初态

​		C.计算机的配置

　　 D.A和B
　　

6.以下数据结构中，()是非线性数据结构。<span title="A">---查看</span>

　　A.树

　　B.字符串

　　C.队列

　　D.栈

​	

5.试分析下列各算法的时间复杂度。

```c
x = 90;
y = 100;

while (y > 0) {
    if (x > 100) {
        x = x - 10;
        y--;
    } else
        x++;
}
```

> $O(1)$

```c++
for (i = 0; i < n; i++)
    for (j = 0; j < m; j++)
        a[i][j] = 0;
```

> $O(n×m)$

```c++
s = 0;
for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
        s += B[i][j];
sum = s;
```

> $O(n^2)$

```c++
i = 1;
while (i <= n)
    i = i * 3;
```

> $O(log_3n):3^{f(n)}\leq n$

```c++
x = 0;
for (i = 1; i < n; i++)
    for (j = 1; j <= n - i; j++)
        x++;
```

> $O(n^2):n-1+n-2+...+1=n(n-1)/2$

```c
x = n; // n > 1
y = 0;
while (x > (y + 1) * (y + 1)) {
    y++;
}
```

> $\mathrm{O}(\sqrt{n}):x\geqslant(f(n)+1)^2,\text{又由于}x=n,\text{ 所以 }f(n)\leqslant\sqrt{n}-1$

​	

​	

## 第二章

1.顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是()<span title="B">---查看</span>

　　A. 110

　　B. 108

　　C. 100

　　D. 120
	
　　2.在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是()。<span title="A">---查看</span>

　　A.访问第i个结点(1≤i≤n)和求第i个结点的直接前驱(2≤i≤n)

　　B.在第i个结点后插入一个新结点(1≤i≤n)

　　C.删除第i个结点(1≤i≤n)

　　D.将n个结点从小到大排序
	
　　 :star2:3.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为()。<span title="B">---查看</span>

　　A. 8

　　B. 63.5

　　C. 63

　　D. 7
	
　　4.链接存储的存储结构所占存储空间()。<span title="A">---查看</span>

　　A.分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针

　　B.只有一部分，存放结点值

　　C.只有一部分，存储表示结点间关系的指针

　　D.分两部分，一部分存放结点值，另一部分存放结点所占单元数
	
　　5.线性表若采用链式存储结构时，要求内存中可用存储单元的地址()<span title="D">---查看</span>

　　A.必须是连续的

　　B.部分地址必须是连续的

　　C.一定是不连续的

　　D.连续或不连续都可以
	
　　6.线性表L在()情况下适用于使用链式结构实现。<span title="B">---查看</span>

　　A.需经常修改L中的结点值

　　B.需不断对L进行删除插入

　　C.L中含有大量的结点

　　D.L中结点结构复杂
	
　　7.单链表的存储密度()。<span title="C">---查看</span>

　　A.大于1

　　B.等于1

　　C.小于1

　　D.不能确定
	
　　8.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是()<span title="A">---查看</span>

　　A.n

　　B. 2n-1

　　C. 2n

　　D. n-1
	
　　:star2:9.在一个长度为n的顺序表中，在第i个元素(1≤i≤n+1)之前插入一个新元素时须向后移动()个元素。<span title="B">---查看</span>

　　A.n-i

　　B. n-i+1

　　C. n-i-1

　　D.i
	
　　10.线性表L=(a1,a2,…,am),下列说法正确的是()。<span title="D">---查看</span>

　　A.每个元素都有一个直接前驱和一个直接后继

　　B.线性表中至少有一个元素

　　C.表中诸元素的排列必须是由小到大或由大到小

　　D.除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继
	
　　:star2:11.创建一个包括n个结点的**有序**单链表的时间复杂度是()。<span title="C">---查看</span>

　　A. $O(1)$

　　B.$O(n)$

　　C. $O(n^2)$

　　D. $O(nlog_2n)$
	

:star2:12.以下说法错误的是()。<span title="D">---查看</span>

　　A.求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低

　　B.顺序存储的线性表可以随机存取

　　C.由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活

​      D.线性表的链式存储结构优于顺序存储结构

​	

13.在单链表中，要将s所指结点插入到p所指结点之后，其语句应为()。<span title="D">---查看</span>

　　A. s->next=p+1; p->next=s;

　　B.(\*p).next=s;(\*s).next=(*p).next;

　　C. s->next=p->next; p->next=s->next;

　　D. s->next=p->next; p->next=s;
　　	

14.在双向链表存储结构中，删除p所指的结点时须修改指针()<span title="A">---查看</span>

　　A. p->prior->next=p->next; p->next->prior=p->prior;

　　B. p->next=p->next->next; p->next->prior=p;

　　C. p->prior->next=p; p->prior=p->prior->prior;

　　D. p->prior=p->next->next; p->next=p->prior->prior;
　	

　15.在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是()。<span title="C">---查看</span>

　　A. p->next=q; q->prior=p; p->next->prior=q; q->next=q;

　　B. p->next=q; p->next->prior=q; q->prior-p; q->next=p->next;

　　C. q->prior=p; q->next=p->next; p->next->prior=q; p->next=q;

　　D. q->prior=p; q->next=p->next; p->next=q; p->next->prior=q;

​	

​	

## 第三章