东北大学16春学期《数据结构Ⅰ》在线作业参考答案分析

东北大学16春学期《数据结构Ⅰ》在线作业参考答案

一、单选题：

1. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为 (满分:5)

A. 1和5

B. 2和4

C. 4和2

D. 5和1

2. 为便于判别有向图中是否存在回路，可借助于 (满分:5)

A. 广度优先搜索算法

B. 最小生成树算法

C. 最短路径算法

D. 拓扑排序算法

3. 连通网的最小生成树是其所有生成树中 (满分:5)

A. 顶点集最小的生成树

B. 边集最小的生成树

C. 顶点权值之和最小的生成树

D. 边的权值之和最小的生成树

4. 上溢现象通常出现在 (满分:5)

A. 顺序栈的入栈操作过程中

B. 顺序栈的出栈操作过程中

C. 链栈的入栈操作过程中

D. 链栈的出栈操作过程中

5. ALV树是一种平衡的二叉排序树，树中任一结点的 (满分:5)

A. 左、右子树的高度均相同

B. 左、右子树高度差的绝对值不超过1

C. 左子树的高度均大于右子树的高度

D. 左子树的高度均小于右子树的高度

6. ISAM文件的周期性整理是为了空出 (满分:5)

A. 磁道索引

B. 柱面索引

C. 柱面基本区

D. 柱面溢出区

7. 已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t 到s。若字符串S=″SCIENCESTUDY″，则调用函数Scopy(P,Sub(S,1,7))后得到 (满分:5)

A. P=″SCIENCE″

B. P=″STUDY″

C. S=″SCIENCE″

D. S=″STUDY″

8. 链栈与顺序栈相比，比较明显的优点是 (满分:5)

A. 插入操作更加方便

B. 删除操作更加方便

C. 不会出现下溢的情况

D. 不会出现上溢的情况

9. 当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为 (满分:5)

A. A．左子树的叶子结点

B. B．左子树的分支结点

C. C．右子树的叶子结点

D. D．右子树的分支结点

10. 高度为5的完全二叉树中含有的结点数至少为 (满分:5)

A. 16

B. 17

C. 31

D. 32

11. 已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为 (满分:5)

A. 0

B. 1

C. 48

D. 49

12. 快速排序在最坏情况下的时间复杂度是 (满分:5)

A. O(n2log2n)

B. O(n2)

C. O(nlog2n)

D. O(log2n)

13. for（i=0；i；i++）for（j=0；j；j++）c［i］［j］=0；for（i=0；i；i++）for（j=0；j；j++）for（k=0；k；k++）c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］；上列程序的时间复杂度为 (满分:5)

A. O（m+n×t）

B. O（m+n+t）

C. O（m×n×t）

D. O（m×t+n）

14. 根据数据元素的关键字直接计算出该元素存储地址的存储方法是 (满分:5)

A. 顺序存储方法

B. 链式存储方法

C. 索引存储方法

D. 散列存储方法

15. 在计算机内实现递归算法时所需的辅助数据结构是 (满分:5)

A. 栈

B. 队列

C. 树

D. 图

16. 除第一层外，满二叉树中每一层结点个数是上一层结点个数的 (满分:5)

A. 1/2倍

B. 1倍

D. 3倍

17. 一棵完全二叉树上有1001个结点，其中叶子结点的个数是 (满分:5)

A. 250

B. 500

C. 254

D. 以上答案都不对

18. 若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列 (满分:5)

A. 一定存在

B. 一定不存在

C. 不一定存在

D. 不确定

19. 以下说法不正确的是 (满分:5)

A. 无向图中的极大连通子图称为连通分量

B. 连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点

C. 图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点

D. 有向图的遍历不可采用广度优先搜索

20. 数据元素及其关系在计算机存储器内的表示，称为数据的 (满分:5)

A. 逻辑结构

B. 存储结构

C. 线性结构

D. 非线性结构

16春学期《数据结构Ⅰ》在线作业2

一、单选题：

1. 设哈希表长为14，哈希函数H(key)=key％11，表中已有数据的关键字为15，38，61，84，四个，现将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是 (满分:5)

A. 8

B. 3

C. 5

D. 9

2. for（i=0；i；i++）for（j=0；j；j++）c［i］［j］=0；for（i=0；i；i++）for（j=0；j；j++）for（k=0；k；k++）c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］；上列程序的时间复杂度为 (满分:5)

A. O（m+n×t）

B. O（m+n+t）

C. O（m×n×t）

D. O（m×t+n）

3. 为使平均查找长度达到最小,当由关键字集合{05,11,21,25,37,40,41,62,84}构建二叉排序树时,第一个插入的关键字应为 (满分:5)

A. 05

B. 37

D. 62

4. 已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t 到s。若字符串S=″SCIENCESTUDY″，则调用函数Scopy(P,Sub(S,1,7))后得到 (满分:5)

A. P=″SCIENCE″

B. P=″STUDY″

C. S=″SCIENCE″

D. S=″STUDY″

5. 若要在单链表中的结点p之后插入一个结点s，则应执行的语句是 (满分:5)

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;

6.设有一个顺序栈的入栈序列是a、b、c，则3个元素都出栈的可能不同排列个数为 (满分:5)

A. 4

B. 5

C. 6

D. 7

7. 下述哪一条是顺序存储结构的优点 (满分:5)

A. 存储密度大

B. 插入运算方便

C. 删除运算方便

D. 可方便地用于各种逻辑结构的存储表示

8. 设给定权值总数有n 个，其哈夫曼树的结点总数为 (满分:5)

A. 不确定

B. 2n

C. 2n+1

D. 2n-1

9. 二维数组A按行优先顺序存储，其中每个元素占1个存储单元。若A［1］［1］的存储地址为420，A［3］［3］的存储地址为446，则A［5］［5］的存储地址为 (满分:5)

A. 470

B. 471

C. 472

D. 473

10. 抽象数据类型的三个组成部分分别为 (满分:5)

A. 数据对象、数据关系和基本操作

B. 数据元素、逻辑结构和存储结构

C. 数据项、数据元素和数据类型

D. 数据元素、数据结构和数据类型

11.数据结构中所定义的数据元素，是用于表示数据的 (满分:5)

A. 最小单位

B. 最大单位

C. 基本单位

D. 不可分割的单位

12. 以下数据结构中，属于线性结构的是 (满分:5)

A. 广义表

B. 二叉树

C. 稀疏矩阵

D. 串

13. 多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为 (满分:5)

A. 数组的元素处在行和列两个关系中

B. 数组的元素必须从左到右顺序排列

C. 数组的元素之间存在次序关系

D. 数组是多维结构，内存是一维结构

14. 索引非顺序文件的特点是 (满分:5)

A. 主文件无序，索引表有序

B. 主文件有序，索引表无序

C. 主文件有序，索引表有序

D. 主文件无序，索引表无序

15. 若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的 (满分:5)

A. 层次遍历算法

B. 前序遍历算法

C. 中序遍历算法

D. 后序遍历算法

16. 下列编码中属于前缀编码的是 (满分:5)

A. {1

01

000

001}

B. {1

01

011

010}

C. {0

10

110

11}

D. {0

1

00

11}

17. 设数组A[m]为循环队列Q的存储空间，front为队头指针，rear为队尾指针，则判定Q 为空队列的条件是 (满分:5)

A. (rear-front)%m= =1

B. front= =rear

C.(rear-front)%m= =m-1

D. front= =(rear+1)%m

18. 导致栈上溢的操作是 (满分:5)

A. 栈满时执行的出栈

B. 栈满时执行的入栈

C. 栈空时执行的出栈

D. 栈空时执行的入栈

19. 一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为 (满分:5)

A. O(n)

B. O(e)

C. O(n+e)

D. O(n2)

20. n个顶点的强连通图中至少含有 (满分:5)

A. n-1条有向边

B. n条有向边

C. n(n-1)/2条有向边

D. n(n-1)条有向边

16春学期《数据结构Ⅰ》在线作业3

一、单选题：

1. 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是 (满分:5)

A. n

B. 2n-1

C. 2n

D. n-1

2. 为便于判别有向图中是否存在回路，可借助于 (满分:5)

A. 广度优先搜索算法

B. 最小生成树算法

C. 最短路径算法

D. 拓扑排序算法

3. 在平衡二叉树中插入一个结点后引起了不平衡，设最低(最接近于叶子)的不平衡点是A，并已知A的左、右孩子的平衡因子分别为-1和0，则应进行的平衡旋转是 (满分:5)

A. LL型

B. LR型

C. RL型

D. RR型

4. 一个有向无环图的拓扑排序序列是 (满分:5)

A. 一定唯一的

B. 一定不唯一的

C. 不一定唯一的

D. 都不对

5. 设给定权值总数有n 个，其哈夫曼树的结点总数为 (满分:5)

A. 不确定

C. 2n+1

D. 2n-1

6. 以下属于逻辑结构的是 (满分:5)

A. 顺序表

B. 哈希表

C. 有序表

D. 单链表

7. 执行下列程序段后，串X的值为S=〞abcdefgh〞; T=〞xyzw〞; substr(X,S,2,strlen(T)); substr(Y,S, stelen(T),2); strcat(X,Y); (满分:5)

A. 〞cdefgh〞

B. 〞cdxyzw〞

C. 〞cdefxy〞

D. 〞cdefef〞

8. 下列数据结构中，属于非线性数据结构的是 (满分:5)

A. 栈

B. 队列

C. 完全二叉树

D. 堆

9. 若数组s[0..n-1]为两个栈s1和s2的共用存储空间，且仅当s[0..n-1]全满时，各栈才不能进行进栈操作，则为这两个栈分配空间的最佳方案是：s1和s2的栈顶指针的初值分别为 (满分:5)

A. 1和n+1

B. 1和n/2

C. －1和n

D. －1和n+1

10. . 对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关键字比较次数的平均值为 (满分:5)

A. 39/15

B. 49/15.

C. 51/15

D. 55/15

11. 假设在构建散列表时，采用线性探测解决冲突。若连续插入的n个关键字都是同义词，则查找其中最后插入的关键字时，所需进行的比较次数为 (满分:5)

A. n-1

B. n

C. n+1

D. n+2

12. 以下数据结构中，属于线性结构的是 (满分:5)

A. 广义表

B. 二叉树

C. 稀疏矩阵

D. 串

13. 在一棵高度为k的满二叉树中，结点总数为 (满分:5)

B. 2k

C. 2k-1

D. log2k?+1

14. 如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是 (满分:5)

A. 栈

B. 队列

C. 树

D. 图

15. 在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系 (满分:5)

A. 不一定相同

B. 都相同

C. 都不相同

D. 互为逆序

16. 倒排文件的主要优点是 (满分:5)

A. 便于进行插入和删除运算

B. 便于进行文件的恢复

C. 便于进行多关键字查询

D. 节省存储空间

17. 已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为 (满分:5)

A. 0

B. 1

C. 48

D. 49

18. 含n个关键字的二叉排序树的平均查找长度主要取决于 (满分:5)

A. 关键字的个数

B. 树的形态

C. 关键字的取值范围

D. 关键字的数据类型

19. 算法的时间复杂度主要取决于 (满分:5)

A. 问题的规模

B. 待处理数据的初态

C. 难度

D. A和B

20. 假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为 (满分:5)

A. (rear-front-1)％n

B. (rear-front)％n

C. (front-rear+1)％n

D. (rear-front+n)％n