|
|
14秋学期《数据结构Ⅰ》在线作业1
试卷总分：100 测试时间：--
一、单选题（共20道试题，共100分。）
1.
在一个单链表中，已知q结点是p结点的前驱结点，若在q 和p之间插入结点s，则执行操作
A. s->next=p->next;p->next=s;
B. s->next=p; q->next=s
C. q->next=s;s->next=p; D. p->next=s;s->next=q;
D. q->next=s;s->next=p; D. p->next=s;s->next=q;
满分：5分
2.
在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是
A. O(1)
B. O(n)
C. O(nlogn)
D. O(n2)
满分：5分
3.
高度为5的完全二叉树中含有的结点数至少为
A. 16
B. 17
C. 31
D. 32
满分：5分
4.
下列编码中属于前缀编码的是
A. {1,01,000,001}
B. {1,01,011,010}
C. {0,10,110,11}
D. {0,1,00,11}
满分：5分
5.
下面说法错误的是
(1）算法原地工作的含义是指不需要任何额外的辅助空间
（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法
（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
（4）同一个算法，实现语言的级别越高，执行效率就越低
A.
(1)
B. (1),(2)
C.
(1),(4)
D. (3)
满分：5分
6.
顺序存储设计时，存储单元的地址
A.
一定连续
B. 一定不连续
C. 不一定连续
D. 部分连续，部分不连续
满分：5分
7.
下列关键字序列中，构成小根堆的是
A.
{84，46，62，41，28，58，15，37}
B.
{84，62，58，46，41，37，28，15}
C.
{15，28，46，37，84，41，58，62}
D.
{15，28，46，37，84，58，62，41}
满分：5分
8.
下面哪一方法可以判断出一个有向图是否有回路
A.
深度优先遍历
B. 求关键路径
C.
求最短路径
D. A和C
满分：5分
9.
设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为
A. 21
B. 23
C. 41
D. 62
满分：5分
10.
带行表的三元组表是稀疏矩阵的一种
A. 顺序存储结构
B. 链式存储结构
C. 索引存储结构
D. 散列存储结构
满分：5分
11.
判定“带头结点的链队列为空”的条件是
A. Q.front==NULL
B. Q.rear==NULL
C. Q.front==Q.rear
D. Q.front!=Q.rear
满分：5分
12.
上溢现象通常出现在
A.
顺序栈的入栈操作过程中
B. 顺序栈的出栈操作过程中
C.
链栈的入栈操作过程中
D. 链栈的出栈操作过程中
满分：5分
13.
已知一组关键字为{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}
满分：5分
14.
栈的两种常用存储结构分别为
A.
顺序存储结构和链式存储结构
B. 顺序存储结构和散列存储结构
C.
链式存储结构和索引存储结构
D. 链式存储结构和散列存储结构
满分：5分
15.
以下与数据的存储结构无关的术语是
A.
循环队列
B. 链表
C. 哈希表
D. 栈
满分：5分
16.
栈和队列都是
A. 限制存取位置的线性结构
B. 顺序存储的线性结构
C. 链式存储的线性结构
D. 限制存取位置的非线性结构
满分：5分
17.
在目标串T［0..n-1］=″xwxxyxy″中，对模式串P［0..m-1］=″xy″进行子串定位操作的结果是
A. 0
B. 2
C. 3
D. 5
满分：5分
18.
已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为
A. 5
B. 8
C. 11
D. 18
满分：5分
19.
若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得
到的输出序列是
A. 1234
B. 4132
C. 4231
D. 4213
满分：5分
20.
用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为
A. n-1
B. n
C. n+1
D. 2n
满分：5分
14秋学期《数据结构Ⅰ》在线作业2
试卷总分：100 测试时间：--
一、单选题（共20道试题，共100分。）
1.
数据元素及其关系在计算机存储器内的表示，称为数据的
A. 逻辑结构
B. 存储结构
C. 线性结构
D. 非线性结构
满分：5分
2.
下列关键字序列中，构成小根堆的是
A.
{84，46，62，41，28，58，15，37}
B.
{84，62，58，46，41，37，28，15}
C.
{15，28，46，37，84，41，58，62}
D.
{15，28，46，37，84，58，62，41}
满分：5分
3.
设给定权值总数有n 个，其哈夫曼树的结点总数为
A. 不确定
B. 2n
C. 2n+1
D. 2n-1
满分：5分
4.
适宜进行批量处理的文件类型是
A. 顺序文件
B. 索引顺序文件
C. 散列文件
D. 多关键字文件
满分：5分
5.
已知一个散列表如图所示，其散列函数为H(key)=key％11，采用二次探查法处理冲突，则下一个插入的关键字49的地址为
012345678910
15386184
A. 2
B. 3
C. 8
D. 9
满分：5分
6.
下列陈述中正确的是
A. 二叉树是度为2的有序树
B. 二叉树中结点只有一个孩子时无左右之分
C. 二叉树中必有度为2的结点
D. 二叉树中最多只有两棵子树，并且有左右之分
满分：5分
7.
一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少的结点数有
A. 2h
B. 2h-1
C. 2h+1
D. h+1
满分：5分
8.
. 若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为
A. X的双亲
B. X的右子树中最左的结点
C. X的左子树中最右结点
D. X的左子树中最右叶结点
满分：5分
9.
一棵完全二叉树上有1001个结点，其中叶子结点的个数是
A. 250
B. 500
C. 254
D. 以上答案都不对
满分：5分
10.
若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得
到的输出序列是
A. 1234
B. 4132
C. 4231
D. 4213
满分：5分
11.
当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为
A. A．左子树的叶子结点
B. B．左子树的分支结点
C. C．右子树的叶子结点
D. D．右子树的分支结点
满分：5分
12.
在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系
A. 不一定相同
B. 都相同
C. 都不相同
D. 互为逆序
满分：5分
13.
已知函数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. S=″SCIENCE″
D. S=″STUDY″
满分：5分
14.
一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是
A. 0
B. 1
C. 2
D. 不确定
满分：5分
15.
在一棵高度为k的满二叉树中，结点总数为
A. 2k-1
B. 2k
C. 2k-1
D. log2k+1
满分：5分
16.
在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是
A. O(1)
B. O(n)
C. O(nlogn)
D. O(n2)
满分：5分
17.
在下列存储形式中，哪一个不是树的存储形式
A. 双亲表示法
B. 孩子链表表示法
C. 孩子兄弟表示法
D. 顺序存储表示法
满分：5分
18.
带行表的三元组表是稀疏矩阵的一种
A. 顺序存储结构
B. 链式存储结构
C. 索引存储结构
D. 散列存储结构
满分：5分
19.
下面关于线性表的叙述中，错误的是
A.
线性表采用顺序存储，必须占用一片连续的存储单元。
B.
线性表采用顺序存储，便于进行插入和删除操作。
C.
线性表采用链接存储，不必占用一片连续的存储单元。
D.
线性表采用链接存储，便于插入和删除操作。
满分：5分
20.
多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为
A.
数组的元素处在行和列两个关系中
B. 数组的元素必须从左到右顺序排列
C.
数组的元素之间存在次序关系
D. 数组是多维结构，内存是一维结构
满分：5分
14秋学期《数据结构Ⅰ》在线作业3
试卷总分：100 测试时间：--
一、单选题（共20道试题，共100分。）
1.
若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为
A. f,c,b
B. f,d,b
C. g,c,b
D. g,d,b
满分：5分
2.
一棵具有 n个结点的完全二叉树的树高度（深度）是
A. logn+1
B. logn+1
C. logn
D. logn-1
满分：5分
3.
适宜进行批量处理的文件类型是
A. 顺序文件
B. 索引顺序文件
C. 散列文件
D. 多关键字文件
满分：5分
4.
已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为
A. 5
B. 6
C. 16
D. 17
满分：5分
5.
设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是
A. A，B，C，D
B. D，C，B，A
C. A，C，D，B
D. D，A，B，C
满分：5分
6.
设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为
A. 21
B. 23
C. 41
D. 62
满分：5分
7.
已知散列表的存储空间为T[0..18]，散列函数H（key）=key%17,并用二次探测法处理冲突。散列表中已插入
下列关键字：T[5]=39，T[6]=57和T[7]=7，则下一个关键字23插入的位置是
A. T[2]
B. T[4]
C. T[8]
D. T[10]
满分：5分
8.
链栈与顺序栈相比，比较明显的优点是
A.
插入操作更加方便
B. 删除操作更加方便
C.
不会出现下溢的情况
D. 不会出现上溢的情况
满分：5分
9.
若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为
A. O(0)
B. O(1)
C. O(n)
D. O(n2)
满分：5分
10.
一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少的结点数有
A. 2h
B. 2h-1
C. 2h+1
D. h+1
满分：5分
11.
如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是
A. 有向完全图
B. 连通图
C. 强连通图
D. 有向无环图
满分：5分
12.
下列陈述中正确的是
A. 二叉树是度为2的有序树
B. 二叉树中结点只有一个孩子时无左右之分
C. 二叉树中必有度为2的结点
D. 二叉树中最多只有两棵子树，并且有左右之分
满分：5分
13.
在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用
A. 数据元素的相邻地址表示
B. 数据元素在表中的序号表示
C. 指向后继元素的指针表示
D. 数据元素的值表示
满分：5分
14.
设给定权值总数有n 个，其哈夫曼树的结点总数为
A. 不确定
B. 2n
C. 2n+1
D. 2n-1
满分：5分
15.
连通图是指图中任意两个顶点之间
A. 都连通的无向图
B. 都不连通的无向图
C. 都连通的有向图
D. 都不连通的有向图
满分：5分
16.
下面哪一方法可以判断出一个有向图是否有回路
A.
深度优先遍历
B. 求关键路径
C.
求最短路径
D. A和C
满分：5分
17.
若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得
到的输出序列是
A. 1234
B. 4132
C. 4231
D. 4213
满分：5分
18.
下面说法错误的是
(1）算法原地工作的含义是指不需要任何额外的辅助空间
（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法
（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
（4）同一个算法，实现语言的级别越高，执行效率就越低
A.
(1)
B. (1),(2)
C.
(1),(4)
D. (3)
满分：5分
19.
计算机识别、存储和加工处理的对象被统称为
A. 数据
B. 数据元素
C. 数据结构
D. 数据类型
满分：5分
20.
若允许表达式内多种括号混合嵌套，则为检查表达式中括号是否正确配对的算法，通常选用的辅助结构是
A.
栈
B. 线性表
C.
队列
D. 二叉排序树
满分：5分
答案请在附件下载，需要辅导请联系客服qq 761296021
|
|
