当前位置：文档之家 › 东大17秋学期《数据结构》在线作业3

东大17秋学期《数据结构》在线作业3

  • 格式：doc
  • 大小：99.50 KB
  • 文档页数：6

18春奥鹏东大17秋学期《数据结构Ⅱ》在线作业3
试卷总分：100 测试时间：--
单选题
、单选题（共20 道试题，共100 分。

）
1.
树有先根遍历和后根遍历，树可以转化为对应的二叉树。

下面的说法正确的是
A. 树的后根遍历与其对应的二叉树的后根遍历相同
B. 树的后根遍历与其对应的二叉树的中根遍历相同
C. 树的先根遍历与其对应的二叉树的中根遍历相同
D.
以上都不对
满分：5 分
2.
若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为
A.
n-1
B.
?n/m?-1
C.
é(n-1)/(m-1)ù
D.
én/(m-1)ù-1
满分：5 分
3.
已知一个散列表如图所示，其散列函数为H(key)=key％11，采用二次探查法处理冲突，则下一个插入的关键字49的地址为
A. 2
B. 3
C. 8
D. 9
满分：5 分
4.
设有一个顺序栈的入栈序列是a、b、c，则3个元素都出栈的可能不同排列个数为
A. 4
B. 5
C. 6
D. 7
满分：5 分
5.
采用ISAM或VSAM组织的文件是
A. 索引非顺序文件
B. 顺序文件
C. 索引顺序文件
D. 散列文件
满分：5 分
6.
通常将链串的结点大小设置为大于1是为了
A.
提高串匹配效率
B.
提高存储密度
C.
便于插入操作
D.
便于删除操作
满分：5 分
7.
如果将矩阵An×n的每一列看成一个子表，整个矩阵看成是一个广义表L，即L=((a11,a21,…,an1),
( a12,a22,…,an2),…，（a1n,a2n,…,ann）),并且可以通过求表头head和求表尾tail的运算求取矩阵中的每一个元素，则求得a21的运算是
A. head (tail (head (L)))
B. head (head(head(L)))
C.
tail (head (tail (L)))
D.
head (head (tail (L)))
满分：5 分
8.
下列编码中属于前缀编码的是
A. {1,01,000,001}
B. {1,01,011,010}
C.
{0,10,110,11}
D. {0,1,00,11}
满分：5 分
9.
希尔排序的增量序列必须是
A.
递增的
B.
随机的
C.
递减的
D.
非递减的
满分：5 分
10.
高度为5的完全二叉树中含有的结点数至少为
A. 16
B. 17
C. 31
D. 32
满分：5 分
11.
一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少的结点数有
A. 2h
B. 2h-1
C. 2h+1
D. h+1
满分：5 分
12.
某带头结点的单链表的头指针为head，判定该链表为非空的条件是
A. head==NULL
B. head->next==NULL
C.
head!=NULL
D. head->next!=NULL
满分：5 分
13.
二维数组A的每个元素是由6个字符组成的串，其行下标i=0，l，...，8，列下标为j=1，2． (10)
设每个字符占一个字节,若按行先存储，元素A[8，5]的起始地址与A按列存储时起始地址相同的元素是
A. A[8，5]
B. A[3，10]
C.
A[5，8]
D.
A[0，9]
满分：5 分
14.
适宜进行批量处理的文件类型是
A. 顺序文件
B. 索引顺序文件
C. 散列文件
D. 多关键字文件
满分：5 分
15.
一个有向无环图的拓扑排序序列是
A. 一定唯一的
B. 一定不唯一的
C.
不一定唯一的
D.
都不对
满分：5 分
16.
队列和栈的主要区别是
A. 逻辑结构不同
B. 存储结构不同
C. 所包含的运算个数不同
D. 限定插入和删除的位置不同
满分：5 分
17.
已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为
A. ABCDEF
B. ABCEFD
C.
ABFCDE
D.
ABCDFE
满分：5 分
18.
下列程序段for(i=1;i<=n;i++) A[I,j]=0; 的时间复杂度是
A.
O(1)
B.
O(0)
C. O(1+n)
D. O(n)
满分：5 分
19.
含n个关键字的二叉排序树的平均查找长度主要取决于
A. 关键字的个数
B. 树的形态
C.
关键字的取值范围
D.
关键字的数据类型
满分：5 分
20.
当采用分快查找时，数据的组织方式为
A. 数据分成若干块，每块内数据有序
B.
数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
C.
数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
D.
数据分成若干块，每块（除最后一块外）中数据个数需相同
满分：5 分
解决方法。

合集下载

东北师范大学数据结构17秋在线作业1-1

东北师范大学数据结构17秋在线作业1-1

东北师范大学数据结构17秋在线作业1一、单选题1、B2、D3、A4、A5、C一、单选题（共 20 道试题，共 60 分。

）V 1. 若对n阶对称矩阵A按行优先顺序将其下三角形的元素（包括主对角线上的所有元素）依次存放于一维数组 B [1..n(n+1)/2 ] 中，则在B中确定aij ( i < j）的位置k的关系为 () 。

A. i*(i-1)/2+jB. j*(j-1)/2+iC. i*(i+1)/2+jD. j*(j+1)/2+i正确答案：B2. 在下述几种排序方法中，辅助空间需要最多的是 ()。

A. 直接插入排序B. 快速排序C. 直接选择排序D. 归并排序正确答案：D3. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是 ()。

A. 直接插入排序B. 快速排序C. 直接选择排序D. 归并排序正确答案：A4. 在查找过程中，仅进行查找操作，没有引起表本身的改动，这种查找则称为 ()。

A. 静态查找B. 动态查找C. 内查找D. 外查找正确答案：A5. 设F是一个森林， B是由F变换得到的二叉树。

若F中有n个非终端结点，则B中右指针域为空的结点有 ( ) 个。

A. n-1B. nC. n +1D. n+2正确答案：C6. 一棵左子树为空的二叉树在前序线索化后，其中空的链域的个数是：( )。

A. 不确定B. 0C. 1D. 2正确答案：D7. 若设根结点的层数为0，则高(或深)度为4的二叉树至多含有的结点数为 ( )。

东大17秋学期《数据结构Ⅱ》在线作业3满分答案

东大17秋学期《数据结构Ⅱ》在线作业3满分答案

D.以上都不对
满分：5分
正确答案:B
2.
若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为
A.
nБайду номын сангаас1
B.
?n/m?-1
C.
é(n-1)/(m-1)ù
D.
én/(m-1)ù-1
满分：5分
正确答案:C
3.
已知一个散列表如图所示，其散列函数为H(key)=key％11，采用二次探查法处理冲突，则下一个插入的关键字49的地址为
取矩阵中的每一个元素，则求得a21的运算是
A. head (tail (head (L)))
B. head (head(head(L)))
C.
tail (head (tail (L)))
D.
head (head (tail (L)))
满分：5分
正确答案:A
8.
下列编码中属于前缀编码的是
A. {1,01,000,001}
正确答案:D
18.
下列程序段for(i=1;i<=n;i++) A[I,j]=0;的时间复杂度是
A.
O(1)
B.
O(0)
C. O(1+n)
D. O(n)
满分：5分
正确答案:D
19.
含n个关键字的二叉排序树的平均查找长度主要取决于
A.关键字的个数
B.树的形态
C.
关键字的取值范围
D.
关键字的数据类型
满分：5分
17秋学期《数据结构Ⅱ》在线作业3
试卷总分:100得分:100
一、单选题(共20道试题,共100分)
1.
树有先根遍历和后根遍历，树可以转化为对应的二叉树。下面的说法正确的是
《数据结构》作业3参考答案

《数据结构》作业3参考答案


= 15
所以 (3,3) = (0,0) + 3 × 15 + 3 = 644 + 45 + 3 = 692
4.9 习题答案
第一步，计算 P 的 next 值，如图所示。
j
0
1
P
a
a
next[j]
-1
0
第二步，用 KMP 算法进行快速匹配，如下图。
0
1
234567
T
a
b
abbaab
P
a
a
b
j=1,next[1]=0
图 4.10(1)
(2).答案：
( , , ( ) , ( ))的图形表示和存储表示如图所示。
图 4.10(2)
4.11 习题答案
(1) Head(Tail(Tail(L1))) (2) Head(Head(Tail(L2))) (3) Head(Head(Tail(Tail(Head(L3))))) (4) Head(Head(Tail(Tail(L4)))) (5) Head(Tail(Head(L5))) (6) Head(Head(Tail(Head(Tail(L6)))))
a
a
j=0,next[0]=-1
aab
j=1,next[1]=0
aab
j=0,next[0]=-1
aab
ห้องสมุดไป่ตู้
j=0,next[0]=-1
aa
图 4.9
2 b 1 89 aA
b j=3,成功
4.10 习题答案 (1).答案：
( ( ), ( ), ( , ( , , )))的图形表示和存储表示如图所示。
数据结构作业3参考答案答案作业三数据结构作业题参考答案作业3及答案3及答案作业及答案
数据结构大作业3

数据结构大作业3

数据结构大作业一、大作业的性质和目的数据结构大作业是对软件设计的综合训练，包括问题分析、总体设计、用户界面设计、程序设计基本技能和技巧，以至一套软件工作规范的训练和科学作风的培养。

在数据结构实验中，完成的只是单一而“小”的算法，而本课程设计是对学生的整体编程能力的锻炼。

数据结构大作业的目的是训练学生对问题的抽象能力和算法的运用能力。

二、大作业安排每位同学独立完成，可自选题目或根据选择后面的一个参考题目来完成。

开学第一周统一提交到教学在线。

提交的内容包括：(1)设计报告文档。

该文档是评分的重要依据之一，请认真对待。

该文档包括如下内容：●需求分析： (陈述要解决的问题，要实现的功能),●详细设计：包括设计算法流程图、算法分析、使用的数据结构（要求详细论证）；●软件测试：包括测试数据和测试结果记录●总结：设计过程中遇到的问题及解决方法；尚未解决的问题及考虑应对的策略；收获和心得；(2)源代码。

要求注释清晰，编写规范，模块化。

(3)可运行的exe文件。

要求充分测试，在XP操作系统中能正常运行。

以上内容打包后提交到教学在线。

三、考核和成绩评定老师根据设计文档、源代码和可执行文件，进行判分。

对于出现以下情况的学生，要求统一进行答辩：●执行文件无法正常运行。

●源程序疑似抄袭。

如果有发现两个同学的代码相类似则需要共同出席答辩。

如果判定抄袭，则为不及格。

开发过程可以部分复用网上的开源代码，但必须体现自己的工作，如果没有自己工作的部分，同样判为抄袭。

五、题目（任选其中之一或自拟）1. 数字化校园（1）设计华南理工大学的校园平面图，至少包括10个以上的地点，每两个地点间可以有不同的路，且路长可能不同。

以图中顶点表示校内各地点，存放名称、代号、简介等信息；用边表示路径，存放路径长度等相关信息。

（2）提供图中任意地点相关信息的查询。

（3）提供图中任意地点的问路查询，即查询任意两个地点之间的一条最短路径。

（4）学校要新建一间超市，请为超市选址，实现总体最优。