数据结构（本科）期末综合练习一（单选题）
单选题
1. 一个数组元素a[i] 与( A )的表示等价。
A. *(a+i) B. a+i C. *a+i D. &a+i
2. 若需要利用形参直接访问实参，则应把形参变量说明为( B )参数。 A. 指针 B. 引用 C. 传值 D. 常值
3. 下面程序段的时间复杂度为( C )。 for(int i=0; i for(int j=0; j 22 A. O(m) B. O(n) C. O(m*n) D. O(m+n) 4. 执行下面程序段时，执行S语句的次数为( )。 for(int i=1; i<=n; i++) for(int j=1; j<=i; j++) S; 22 A. n B. n/2 C. n(n+1) D. n(n+1)/2 5. 下面算法的时间复杂度为( )。 int f(unsigned int n) { if(n==0 || n==1) return 1; else return n*f (n-1); } 2 A. O(1) B. O(n) C. O(n) D. O(n!) 6. 一种抽象数据类型包括数据和( )两个部分。 A. 数据类型 B. 操作 C. 数据抽象 D. 类型说明 7. 当一个作为实际传递的对象占用的存储空间较大并可能被修改时，应最好说明为( )，以节省参数值的传输时间和存储参数的空间。 A. 基本类型 B. 引用型 C. 指针型 D. 常值引用型 8. 当需要进行标准I/O操作时，则应在程序文件中包含iostream.h头文件，当需要进行文件I/O操作时，则应在程序文件中包含( )头文件。 A.fstream.h B.stdlib.h C.iomanip.h D.string.h 9. 一个记录r理论上占有的存储空间的大小等于所有域类型长度之和，实际上占有的存储空 1 间的大小即记录长度为( )。 A. 所有域长度之和 B. 最大域所占字节长度 C. 任意一个域长度 D. sizeof(r)的值 10. 输出一个二维数组b[m][n]中所有元素值的时间复杂度为( )。 2 A. O(n) B. O(m+n) C. O(n) D. O(m*n) 2 11. 一个算法的时间复杂度为(3n+2nlog2n+4n-7)/(5n)，其数量级形式的复杂度表示为( )。 2 A. O(n) B. O(nlog2n) C. O(n) D. O(log2n) 2 12. 某算法的时间代价为T(n)=100n+10nlog2n+n+10，其时间复杂度为（ ）。 2 A. O(n) B. O(nlog2n) C. O(n) D. O(1) 23 13. 某算法仅含程序段1和程序段2，程序段1的执行次数3n，程序段2的执行次数为0.01n，则该算法的时间复杂度为（ ）。 23 A. O(n) B. O(n) C. O(n) D. O(1) 14. 以下说法错误的是（ ）。 A. 抽象数据类型具有封装性。 B. 抽象数据类型具有信息隐蔽性。 C. 使用抽象数据类型的用户可以自己定义对抽象数据类型中数据的各种操作。 D. 抽象数据类型的一个特点是使用与实现分离。 15. 在二维数组中，每个数组元素同时处于（ ）个向量中。 A. 0个 B. 1个 C. 2个 D. n个 16. 多维数组实际上是由嵌套的（ ）实现的。 A. 一维数组 B. 多项式 C. 三元组表 D. 简单变量 17. 在一个长度为n的顺序表中顺序搜索一个值为x的元素时，在等概率的情况下，搜索成功时的数据平均比较次数为（ ）。 A. n B. n/2 C.(n+1)/2 D.(n-1)/2 18. 在一个长度为n的顺序表中向第i个元素（0≤i≤n-1）位置插入一个新元素时，需要从后向前依次后移（ ）个元素。 A. n-i B. n-i+1 C. n-i-1 D. i 19. 在一个长度为n的顺序表中删除第i个元素（0≤i≤n-1）时，需要从前向后依次前移（ ）个元素。 A. n-i B. n-i+1 C. n-i-1 D. i 2 20. 在一个长度为n的顺序表中删除一个值为x的元素时，需要比较元素和移动元素的总次数为（ ）。 A. (n+1)/2 B. n/2 C. n D. n+1 21. 在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为（ ）。 2 A. O(n) B. O(1) C. O(n) D. O(log2n) 22. 在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（ ）。 2 A. O(n) B. O(n/2) C. O(1) D. O(n) 23. 在一个长度为n的有序顺序表中搜索值为x元素的时间效率最高的算法的渐进时间复杂度为（ ）。 A. O(1) B. O(n) C. O(log2n) D. O(n) 24. 在二维数组A[8][10]中，每一个数组元素A[i][j] 占用3个存储空间，所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储空间是（ ）。 A. 80 B. 100 C. 240 D. 270 25. 设有一个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 26. 设有一个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 27. 设有两个串t和p，求p在t中首次出现的位置的运算叫做（ ）。 A. 求子串 B. 模式匹配 C. 串替换 D. 串连接 28. 不带头结点的单链表first为空的判定条件是（ ）。 A. first == NULL; B. first->link == NULL; C. first->link == first; D. first != NULL; 29. 带头结点的单链表first为空的判定条件是（ ）。 A. first==NULL; B. first->link==NULL; C. first->link==first; D. first!=NULL; 30. 设单链表中结点的结构为（data, link）。已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行的操作是（ ）。 A. s->link=p->link; p->link=s; B. q->link=s; s->link=p; 3