大学计算机《数据结构》试卷及答案
一、选择题(24 分)
1.下列程序段的时间复杂度为(%%)。
i=0,s=0;%while (s<n) {s=s+i;i++;}
(A) O(n1/2) (B) O(n1/3) (C) O(n) (D) O(n2)
2.设某链表中最常用的操作是在链表的尾部插入或删除元素,则选用下列(%%)
存储方式最节省运算时间。
(A) 单向链表%%%%%%%%(B) 单向循环链表
(C) 双向链表%%%%%%%%(D) 双向循环链表
3.设指针 q 指向单链表中结点 A,指针 p 指向单链表中结点 A 的后继结点 B,指
针 s 指向被插入的结点 X,则在结点 A 和结点 B 插入结点 X 的操作序列为(%%)。
(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;
4.设输入序列为 1、2、3、4、5、6,则通过栈的作用后可以得到的输出序列为
(%%)。
(A) 5,3,4,6,1,2 (B) 3,2,5,6,4,1
(C) 3,1,2,5,4,6 (D) 1,5,4,6,2,3
5.设有一个 10 阶的下三角矩阵 A(包括对角线),按照从上到下、从左到右的
顺序存储到连续的 55 个存储单元中,每个数组元素占 1 个字节的存储空间,则
A[5][4]地址与 A[0][0]的地址之差为(%%)。
(A) 10 (B) 19 (C) 28 (D) 55
6.设一棵 m 叉树中有 N1 个度数为 1 的结点,N2 个度数为 2 的结点,……,
Nm 个度数为 m 的结点,则该树中共有(%%)个叶子结点。