东北大学13秋《数据结构Ⅰ》在线作业答案
东北大学13秋学期《数据结构Ⅰ》在线作业1试卷总分：100 测试时间：--
一、单选题（共20道试题，共100分。）
1.对n个关键字的序列进行快速排序，平均情况下的空间复杂度为
A. O(1)
B. O(logn)
C.
D.
满分：5分
2.要求具有同一逻辑结构的数据元素具有相同的特性，其含义为
A. 不仅数据元素包含的数据项的个数相同，而且其对应数据项的类型要一致
B. 每个数据元素都一样
C.
D.
满分：5分
3.设计归并算法采用的主要技术是
A. 穷举法
B. 分治法
C.
D.
满分：5分
4.数据结构中所定义的数据元素，是用于表示数据的
A. 基本单位
B. 不可分割的单位
C.
D.
满分：5分
5.解决图的最小生成树问题的prim算法，采用的技术是
A. 动态规划
B. 贪心法
C.
D.
满分：5分
6.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为
A. O(1)O(n)
B. O(1)O(1)
C.
D.
满分：5分
7.已知循环队列的存储空间为数组data，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为
A. 16
B. 17
C.
D.
满分：5分
8.引起循环队列队头位置发生变化的操作是
A. 取队头元素
B. 取队尾元素
C.
D.
满分：5分
9.n个顶点的强连通图中至少含有
A. n-1条有向边
B. n条有向边
C.
D.
满分：5分
10.已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为
A. DEBAFC
B. DEFBCA
C.
D.
满分：5分
11.设有一个顺序栈，6个元素1、2 、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是
A. 2
B. 3
C.
D.
满分：5分
12.若数组s为两个栈s1和s2的共用存储空间，且仅当s全满时，各栈才不能进行进栈操作， 则为这两个栈分配空间的最佳方案是：s1和s2的栈顶指针的初值分别为
A. －1和n
B. －1和n+1
C.
D.
满分：5分
13.下面说法错误的是 （1）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
A. -1
B. (1),(3)
C.
D.
满分：5分
14.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为
A. n-i+1
B. n-i
C.
D.
满分：5分
15.当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为
A. 左子树的叶子结点
B. 左子树的分支结点
C.
D.
满分：5分
16.一个有n个结点的图，最少连通分量的个数是
A. 0
B. 1
C.
D.
满分：5分
17.无向图中一个顶点的度是指图中
A. 通过该顶点的回路数
B. 与该顶点连通的顶点数
C.
D.
满分：5分
18.三维数组A按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A［３］的存储地址为
A. 356
B. 358
C.
D.
满分：5分
19.为使平均查找长度达到最小,当由关键字集合{05,11,21,25,37,40,41,62,84}构建二叉排序树时,第一个插入的关键字应为
A. 5
B. 37
C.
D.
满分：5分
20.一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是
东北大学13秋学期《数据结构Ⅰ》在线作业2
试卷总分：100 测试时间：--
一、单选题（共20道试题，共100分。）
1.设有一个顺序栈，6个元素1、2 、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是
A. 2
B. 3
C.
D.
满分：5分
2.队列和栈的主要区别是
A. 所包含的运算个数不同
B. 限定插入和删除的位置不同
C.
D.
满分：5分
3.在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中关键字元素的个数为
A. n-i
B. n-i+1
C.
D.
满分：5分
4.为使平均查找长度达到最小,当由关键字集合{05,11,21,25,37,40,41,62,84}构建二叉排序树时,第一个插入的关键字应为
A. 5
B. 37
C.
D.
满分：5分
5.下述编码中哪一个不是前缀码
A. （00，01，10，11）
B. （0，1，00，11）
C.
D.
满分：5分
6.一个有n个结点的图，最少连通分量的个数是
A. 0
B. 1
C.
D.
满分：5分
7.计算机算法指的是
A. 解决问题的步骤序列
B. 调度方法
C.
D.
满分：5分
8.如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是
A. 强连通图
B. 有向无环图
C.
D.
满分：5分
9.下列各式中，按增长率由小至大的顺序正确排列的是
A. 2n，logn，nlogn，n3/2
B. 2100，logn,2n,nn
C.
D.
满分：5分
10.在一个带权连通图G中，权值最小的边一定包含在G的
A. 广度优先生成树中
B. 深度优先生成森林中
C.
D.
满分：5分
11.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是
A. 树
B. 图
C.
D.
满分：5分
12.设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为
A. 41
B. 62
C.
D.
满分：5分
13.两个字符串相等的条件是
A. 都是非空串
B. 串的长度相等且对应的字符相同
C.
D.
满分：5分
14.下面关于算法说法错误的是
A. 算法的正确性包括指指令不能有二义性
B. 上面说法都是错误的
C.
D.
满分：5分
15.引起循环队列队头位置发生变化的操作是
A. 取队头元素
B. 取队尾元素
C.
D.
满分：5分
16.表达式a*(b+c)-d的后缀表达式是
A. abcd*+-
B. abc+*d-
C.
D.
满分：5分
17.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则节省时间的存储方式是
A. 顺序表
B. 双链表
C.
D.
满分：5分
18.二维数组A［12］［18］采用列优先的存储方法，若每个元素各占3个存储单元，且第1个元素的地址为150，则元素A［9］［7］的地址为
A. 429
B. 432
C.
D.
满分：5分
19.导致栈上溢的操作是
A. 栈满时执行的出栈
B. 栈满时执行的入栈
C.
D.
满分：5分
20.无向图中一个顶点的度是指图中
A. 通过该顶点的回路数
B. 与该顶点连通的顶点数
C.
东北大学13秋学期《数据结构Ⅰ》在线作业3
试卷总分：100 测试时间：--
一、单选题（共20道试题，共100分。）
1.在线性表的下列运算中，不改变数据元素之间结构关系的运算是
A. 排序
B. 定位
C.
D.
满分：5分
2.计算机算法指的是
A. 解决问题的步骤序列
B. 调度方法
C.
D.
满分：5分
3.假设以数组A存放循环队列的元素，其头、尾指针分别为front和rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为
A. (front-rear+1)％n
B. rear-front+n)％n
C.
D.
满分：5分
4.图的邻接矩阵表示法适用于表示
A. 稠密图
B. 稀疏图
C.
D.
满分：5分
5.已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为
A. 48
B. 49
C.
D.
满分：5分
6.三维数组A按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A［３］的存储地址为
A. 356
B. 358
C.
D.
满分：5分
7.n个顶点的有向完全图中含有向边的数目最多为
A. n(n-1)/2
B. n(n-1)
C.
D.
满分：5分
8.设给定权值总数有n 个，其哈夫曼树的结点总数为
A. 2n+1
B. 2n-1
C.
D.
满分：5分
9.二叉树中第5层上的结点个数最多为
A. 16
B. 32
C.
D.
满分：5分
10.算法分析的目的是
A. 辨别数据结构的合理性
B. 评价算法的效率
C.
D.
满分：5分
11.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是
A. .O(1)
B. O(n)
C.
D.
满分：5分
12.．以下与数据的存储结构无关的术语是
A. 哈希表
B. 栈
C.
D.
满分：5分
13.设计归并算法采用的主要技术是
A. 穷举法
B. 分治法
C.
D.
满分：5分
14.在计算机内实现递归算法时所需的辅助数据结构是
A. 栈
B. 队列
C.
D.
满分：5分
15.下列序列中，不构成堆的是
A. （10，9，8，7，3，5，4，6，2）
B. （1，2，3，4，10，9，8，7，6，5）
C.
D.
满分：5分
16.某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则该二叉树对应的森林包括的树的棵树是
A. l
B. 2
C.
D.
满分：5分
17.数据元素及其关系在计算机存储器内的表示，称为数据的
A. 逻辑结构
B. 存储结构
C.
D.
满分：5分
18.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为
A. X的左子树中最右结点
B. X的左子树中最右叶结点
C.
D.
满分：5分
19.已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t 到s。若字符串S=″SCIENCESTUDY″，则调用函数Scopy(P,Sub(S,1,7))后得到
A. P=″SCIENCE″
B. P=″STUDY″
C.
D.
满分：5分
20.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为
A. 7
B. 8
C.
D.
满分：5分
页:
[1]