重庆大学2018年数据结构 ( 第1次 )

张老师

第1次作业
一、单项选择题（本大题共60分，共 20 小题，每小题 3 分）
1. 在长度为n的顺序表求最小值的时间复杂度为（）。
A.
O（1）
B.
O（n）
C.
O（n2）
D.
O（logn）
2. 顺序表中数据元素的存取方式是（）。
A.
顺序存取
B.
链式存取
C.
随机存取
D.
散列存取
3. 对于一个具有n个结点的单链表，,在给定值为x的结点后插入一个新结点的平均时间复杂度为（ ）。
A.
O(0)
B.
O(1)  
C.
O(n)  
D.
O(n2)
4. 在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的（ ）。
A.
行号
B.
列号         
C.
元素值      
D.
地址
5. 数组A［0..5］［0..5］的每个元素占5个字节，将其以列为主序存储在起始地址为1000的内存单元中，则元素A［5］［5］的地址是（　　　）。
A.
1175       
B.
1180
C.
1205
D.
1210
6. 下面程序段的时间复杂度是（ ）。 i ＝ 0； while（i<=n） i = i * 3；
A.
O（3n）   
B.
O(log3n)  
C.
O(n3)     
D.
O(n2)  
7. 假设顺序表中第一个数据元素的存储地址是1000，每个元素占用4个字节，则第7个元素的存储地址是 （）。
A.
1028
B.
1024
C.
1004
D.
1007
8. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( )。
A.
6
B.
4
C.
3
D.
2
9. 判断带头结点的循环单链表L中只有一个结点的条件是（ ）。
A.
L==NULL
B.
L->next==L
C.
L->next->next==L
D.
L->next==NULL
10. 下面关于算法说法错误的是（ ）。
A.
算法最终必须由计算机程序实现
B.
为解决某问题的算法同为该问题编写的程序含义是相同的
C.
算法的可行性是指指令不能有二义性   
D.
以上几个都是错误的
11. 用单链表表示的链队列中，队头在链表的（ ）位置。
A.
链头
B.
链尾
C.
链中
D.
以上都不对
12. 世界上第一台电子计算机问世的时间是（）。
A.
1946
B.
1920
C.
1948
D.
1950
13. 如果对含有n（n>1）个元素的线性表运算只有4种：删除第一个元素；删除最后一个元素；在第一个元素前插入新元素；在最后一个元素后面插入新元素，则最好使用（）。
A.
只有尾结点指针没有头结点指针的循环单链表
B.
只有尾结点指针没有头结点指针的非循环双链表
C.
只有头结点指针没有尾结点指针的循环双链表
D.
既有头结点指针也有尾头结点指针的循环单链表
14. （ ）描述算法最容易出现二义性。
A.
自然语言
B.
程序设计语言      
C.
伪代码
D.
流程图
15. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）。
A.
不确定
B.
n-i+1
C.
i
D.
n-i
16. 设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为（ ）。
A.
10
B.
19
C.
28
D.
55
17. 在括号匹配的检验中，用（）作为转换过程中的数据存储结构。
A.
线性表
B.
栈
C.
队列
D.
单链表
18. 数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为（ ）。
A.
r－f;
B.
（n＋f－r）% n;
C.
n＋r－f;
D.
（n＋r－f）% n
19. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）。
A.
必须是连续的
B.
部分地址必须是连续的
C.
一定是不连续的
D.
连续或不连续都可以
20. 某字符串满足：concat(head(s),head(tail(tail(s))))=“ac”,(head,tail的定义同广义表),则S=( ) 。
A.
aabc
B.
acba  
C.
accc  
D.
acac
二、判断题（本大题共40分，共 20 小题，每小题 2 分）
1. 线性结构中，每一个结点都至少有一个直接前驱和一个直接后继。
2. 数组是同类型值的集合。
3. 数组不适合作为任何二叉树的存储结构。
4. 稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。
5. 二维数组和多维数组均不是特殊的线性结构。
6. 在稀疏矩阵的顺序存储中，利用一个数组来存储非零元素，该数组的长度应等于对应三元组线性表的长度。
7. 已知单链表中某一结点由p指向，求此后继结点存储地址的操作为p=p->next。
8. 栈不能用链式存储结构存放。
9. 在广义表的存储结构中，每个结点均包含有3个域。
10. 从逻辑结构上看，n维数组的每个元素均属于n个向量。
11. 带头结点的双循环链表L为空表的条件是：L->next==L。
12. 在顺序表中插入或删除一个元素，平均需要移动大量的元素，具体移动的元素个数仅与该元素在表中的位置有关。
13. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。
14. 表达式检验结束时，若栈空，则表明表达式中匹配正确。
15. 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。
16. 一个稀疏矩阵Am*n采用三元组形式表示， 若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。
17. 迷宫求解问题中经常用到顺序表来存储数据。
18. 在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为元素值域和子表指针域。
19. 表达式求值问题中经常用到顺序表来存储数据。
20. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。
答案：
一、单项选择题（60分，共 20 题，每小题 3 分）
1. B 2. C 3. C 4. A 5. A 6. B 7. B 8. C 9. C 10. D 11. A 12. A 13. C 14. A 15. B 16. B 17. B 18. D 19. D 20. C
二、判断题（40分，共 20 题，每小题 2 分）
1. × 2. × 3. × 4. √ 5. × 6. √ 7. √ 8. × 9. √ 10. √ 11. × 12. × 13. √ 14. √ 15. × 16. × 17. × 18. √ 19. × 20. ×