东北大学13春学期《数据结构Ⅱ》在线作业1

13春学期《数据结构Ⅱ》在线作业1
试卷总分：100
单选题
一、单选题（共 20 道试题，共 100 分。）
V
1.
在分块索引的在顺序表中查找，算法中采用的最佳技术是
A.
穷举法
B.
贪心法
C.
分治法
D.
分支限界法
满分：5 分
2.
若要在单链表中的结点 p 之后插入一个结点 s ，则应执行的语句是
A. s- next=p- next; p- next=s;
B. p- next=s; s- next=p- next;
C.
p- next=s- next; s- next=p;
D.
s- next=p; p- next=s- next;
满分：5 分
3.
下面说法错误的是
(1 ）算法原地工作的含义是指不需要任何额外的辅助空间
（ 2 ）在相同的规模 n 下，复杂度 O(n) 的算法在时间上总是优于复杂度 O(2 n ) 的算法
（ 3 ）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
（ 4 ）同一个算法，实现语言的级别越高，执行效率就越低
A.
(1)
B.
(1),(2)
C.
(1),(4)
D.
(3)
满分：5 分
4.
某带头结点的单链表的头指针为 head ，判定该链表为非空的条件是
A. head==NULL
B. head- next==NULL
C.
head!=NULL
D. head- next!=NULL
满分：5 分
5.
在对 n 个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第 i 趟排序之前，无序区中关键字元素的个数为
A.
i
B.
i+1
C.
n-i
D.
n-i+1
此题选: D 满分：5 分
6.
已知一组关键字为 {25,48,36,72,79,82,23,40,16,35} ，其中每相邻两个为有序子序列。对这些子序列进行一 趟两两归并的结果是
A.
.{25,36,48,72,23,40,79,82,16,35}
B.
.{25,36,48,72,16,23,40,79,82,35}
C.
.{25,36,48,72,16,23,35,40,79,82}
D.
.{16,23,25,35,36,40,48,72,79,82}
此题选: D 满分：5 分
7.
在长度为 n 的顺序表中删除第 i 个元素 (1 ≤ i ≤ n) 时，元素移动的次数为
A. n-i+1
B. i
C. i+1
D. n-i
此题选: D 满分：5 分
8.
数据元素及其关系在计算机存储器内的表示，称为数据的
A. 逻辑结构
B. 存储结构
C.
线性结构
D.
非线性结构
满分：5 分
9.
假设以数组 A[m] 存放循环队列的元素。已知队列的长度为 length ，指针 rear 指向队尾元素的下一个存储位置， 则队头元素所在的存储位置为
A. (rear-length+m+1) ％ m
B. (rear-length+m) ％ m
C.
(rear-length+m-1) ％ m
D.
(rear-length) ％ m
满分：5 分
10.
在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为
A.
O(n)
B.
O(n+e)
C.
O(n 2 )
D.
O(n 3 )
满分：5 分
11.
在按层次遍历二叉树的算法中，需要借助的辅助数据结构是
A. 队列
B. 栈
C. 线性表
D.
有序表
满分：5 分
12.
三维数组 A[4][5][6] 按行优先存储方法存储在内存中，若每个元素占 2 个存储单元，且数组中第一个元素的存 储地址为 120 ，则元素 A ［３］ [4][5] 的存储地址为
A. 356
B. 358
C. 360
D. 362
满分：5 分
13.
能进行二分查找的线性表 , 必须以
A. 顺序方式存储 , 且元素按关键字有序
B.
链式方式存储 , 且元素按关键字有序
C.
顺序方式存储 , 且元素按关键字分块有序
D.
链式方式存储 , 且元素按关键字分块有序
满分：5 分
14.
对关键字序列 (56 ， 23 ， 78 ， 92 ， 88 ， 67 ， 19 ， 34) 进行增量为 3 的一趟希尔排序的结果为
A.
(19 ， 23 ， 56 ， 34 ， 78 ， 67 ， 88 ， 92)
B.
(23 ， 56 ， 78 ， 66 ， 88 ， 92 ， 19 ， 34)
C.
(19 ， 23 ， 34 ， 56 ， 67 ， 78 ， 88 ， 92)
D.
(19 ， 23 ， 67 ， 56 ， 34 ， 78 ， 92 ， 88)
此题选: D 满分：5 分
15.
用有向无环图描述表达式 (A+B)*((A+B)/A) ，至少需要顶点的数目为
A. 5
B. 6
C. 8
D. 9
满分：5 分
16.
下列编码中属于前缀编码的是
A. {1,01,000,001}
B. {1,01,011,010}
C.
{0,10,110,11}
D. {0,1,00,11}
满分：5 分
17.
下述哪一条是顺序存储结构的优点
A.
存储密度大
B.
插入运算方便
C.
删除运算方便
D.
可方便地用于各种逻辑结构的存储表示
满分：5 分
18.
下面的叙述不正确的是
A.
线性表在链式存储时，查找第 i 个元素的时间同 i 的值成正比
B. 线性表在链式存储时，查找第 i 个元素的时间同 i 的值无关
C. 线性表在顺序存储时，查找第 i 个元素的时间同 i 的值成反比
D. 线性表在顺序存储时，查找第 i 个元素的时间同 i 的值无关
满分：5 分
19.
若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的
A. 层次遍历算法
B. 前序遍历算法
C.
中序遍历算法
D. 后序遍历算法
满分：5 分
20.
在平衡二叉树中插入一个结点后引起了不平衡，设最低 ( 最接近于叶子 ) 的不平衡点是 A ，并已知 A 的左、右孩子的平衡因子分别为 -1 和 0 ，则应进行的平衡旋转是
A. LL 型
B. LR 型
C.
RL 型
D. RR 型
满分：5 分