当前位置：文档之家 › 数据结构第一次作业华南理工网络教育学院

数据结构第一次作业华南理工网络教育学院

  • 格式：doc
  • 大小：53.50 KB
  • 文档页数：4

1判断题
（√）1. 数据的逻辑结构与数据元素本身的内容和形式无关。

（X）2. 线性表的逻辑顺序与物理顺序总是一致的。

（√）3. 若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。

（X）4. 对于同一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的二叉搜索树都是相同的。

（√）5. 最优二叉搜索树的任何子树都是最优二叉搜索树。

（√）6. 在二叉搜索树上插入新结点时，不必移动其它结点，仅需改动某个结点的指针，使它由空变为非空即可。

（√）7. 有n（n≥1）个顶点的有向强连通图最少有n条边。

（X）8. 连通分量是无向图中的极小连通子图。

（X）9. 二叉树中任何一个结点的度都是2。

（X）10. 单链表从任何一个结点出发，都能访问到所有结点。

二、单选题
1 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。

A．8 B. 63.5 C. 63 D. 7
2 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644（10），A[2][2]存放位置在676（10），每个元素占一个空间，则A[3][3]在（A）位置，（10）表明用10进数表示。

A．692（10） B. 626（10） C. 709（10） D. 724（10）
3 N个顶点的连通图至少有（A）条边。

A．N－1 B. N C. N＋1 D. 0
4 下面程序的时间复杂度为（C）。

for(int i=0; i<m;i++)
for(int j=0; j<n;j++)
a[i][j]=i*j;
A．O(m2) B. O(n2) C. O(m*n) D. O(m+n)
5 设单链表中结点的结构为(data, link)。

已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s,则应执行下列哪一个操作（ B ）。

A．s->link=p->link; p->link =s; B. q->link=s; s->link =p;
C. p->link=s->link; s->link =q;
D. p->link=s; s->link =q;
6栈的插入和删除操作在（A）进行。

A．栈顶 B. 栈底 C. 任意位置 D. 指定位置
7 若让元素1，2，3依次进栈，则出栈次序不可能出现哪种情况（C）。

A．3，2，1 B. 2，1，3 C. 3，1，2 D. 1，3，2
8 广义表A(a),则表尾为（C）。

A．a B. (()) C. 空表 D. （a）。

合集下载

华南理工大学网络教育学院 数据结构同步练习册答案

华南理工大学网络教育学院 数据结构同步练习册答案


6.3 分别写出题 6.1 所示二叉树的先根，中根和后根序列。 答：先根：ABCDEFGHIJ 二叉树。 答： 由后根遍历序列得到二叉树的根结点 A （后根序列中最后一个结点） ； 在中序序列中， A 的左力是 A 的左子树上的结点，A 的右边是 A 的右子树上的结点；再到后根序列中找左子 树和右子树的根结点，依次类推，直到画出该二叉树。 中根：DCBAFEHJIG 后根：DCBFJIHGEA 6.4 已知一棵二叉树的中根序列和后根序列分别为 BDCEAFHG 和 DECBHGFA，试画出这棵
(4) int x = 91, y = 100；
while (y > 0) { if (x > 100) else x++; } 答：100 解析： x=91; //1 y=100; //1
{
x = x -10; y--;
}
while(y>0) //1101 if(x>100) //1100 { x=x-10; //100 y--; //100 } else x++; //1000 以上程序段右侧列出了执行次数。该程序段的执行时间为： T(n)=O(1)
while ( i <= n ) { k = k+10*i; i++; } 答：n-1
解析： i=1; //1 k=0; //1 while(i<n) //n { k=k+10*i; //n-1 i++; //n-1 } 由以上列出的各语句的频度，可得该程序段的时间消耗： T(n)=1+1+n+(n-1)+(n-1)=3n 可表示为 T(n)=O(n)
x++; y++;
西南大学网教 (0012)《数据结构》大作业A 答案

西南大学网教 (0012)《数据结构》大作业A 答案

则关键字为49的地址为。

9）数据结构被形式地定义为（D, R），其中D是的有限集合，R是D上的有限集合。

10）一个算法的效率分为效率和效率。

3、应用题1）编写算法,将一个头指针为head不带头结点的单链表改造为一个单向循环链表，并分析算法的时间复杂度。

2）已知二叉树的先序遍历序列为ABCDEFGH，中序遍历序列为CBEDFAGH，画出二叉树。

然后写出该二叉树的后序遍历序列。

3）试用权集合{12,4,5,6,1,2}构造哈夫曼树，并计算哈夫曼树的带权路径长度。

4）已知图G如下所示，根据Prim算法，构造最小生成树。

（要求给出生成过程）5）设哈希表HT表长m为13，哈希函数为H(k)=k MOD m，给定的关键值序列为{19,14,23,10,68,20,84,27,55,11}。

试求出用线性探测法解决冲突时所构造的哈希表，并求出在等概率的情况下查找成功的平均查找长度ASL。

二、大作业要求大作业共需要完成22道题：第1大题必做，满分30分；第2大题必做，满分30分；第3大题选作2题，满分40分。

答卷提交要求：考试题提前公布，学生下载试题和答题卷后，在答题卷上答题。

完成后需网上提交答卷。

答卷于11月20日－－12月6日通过点击页面左侧导航栏内“我的考试”－“课程论文/大作业”提交。

1、选择题1) C 2) C 3) D 4) A 5) C6) C 7) B 8) D 9) A 10) A2、填空题1) l==l->next2)栈顶3)三元组顺序表十字链表。

4)LOC (A[0][0])+(n*i+j)*k5)R[2i+1]6) 先序遍历7)n-18)99) 数据元素关系10)时间效率空间效率3、应用题2）已知二叉树的先序遍历序列为ABCDEFGH，中序遍历序列为CBEDFAGH，画出二叉树。

然后写出该二叉树的后序遍历序列。

答：后序遍历序列CEFDBHGA3）试用权集合{12,4,5,6,1,2}构造哈夫曼树，并计算哈夫曼树的带权路径长度。

华南理工大学网络教育学院数据库同步练习册答案

华南理工大学网络教育学院数据库同步练习册答案

华南理工大学网络教育学院数据库同步练习册答案答案：第一章1.A2.A3.D4.A5.C6.A7.数据库管理系统（DBMS）、数据库管理员（DBA）8. 概念模式或逻辑模式9.人工管理、数据库10.概念模式第二章1.B2.C3.C4.C5.A6.A7.B8.109. 课程名，课程号10. 答：外键的充要条件：1) FK和K的取值域是一样的；2) 对于R中任何一个元组t，要么t[FK]上的值为null，要么存在R'中的元组t',使得t[FK]=t'[K]。

作用：形成关系（表）与关系（表）之间的联系11. 答：每个关系应有一个主键，每个元组的主键的应是唯一的。

这就是实体完整性约束。

如关系：student(学号，姓名，性别)中，有一个主键“学号”，每条学生记录的学号都不同，这是就关系student中的实体完整性约束。

12.R4为：ABa1b1a2b113.ПENO(EPM σmanager=’001’(DEPT))= ПENO(σmanager=’001’(EPM╳DEPT))SELECT ENO FROM EMP, DEPT WHERE DEPT.MANAGER=‘001’ AND EMP.DNO=DEPT.DNO14. 答：1.2.客户（身份证号，客户姓名，联系电话，地址，邮政编码）主键：身份证号业务员（业务员代号，业务员姓名，电话号码）主键：业务员代号房间（房间号，居室数，使用面积，建筑面积，单位，金额，合同号）主键：房间号外键：合同号合同（合同号，日期，付款方式，总金额，身份证号，业务员代号）主键：合同号外键：身份证号，业务员代号15.文本框: 客户客户业务员房间购房合同经办出售111mmm司机（驾照号，姓名，地址，邮编，电话）PK=驾照号机动车（牌照号，型号，制造厂，生产日期）PK=牌照号警察（警察编号，姓名）PK=警察编号处罚通知（编号，日期，时间，地点，驾照号，牌照号，警告，罚款，暂扣，警察编号）PK=编号FK=驾照号，牌照号，警察编号第三章1.B2.A3.B4.A5.B6.B7.D8.grant revoke9. (1)select sname from student,course,sc where credit>3 and grade<70 andstudent.sno=sc.sno and /doc/3c2526876.html,o=http://www.doczj .com/doc/3c2526876.html,o(2) ПSNAME(σs.sno=sc.sno and/doc/3c2526876.html,o=http://www.doczj .com/doc/3c2526876.html,o and credit>3 and grade<70 (STUDENT×COURSE×SC))(3) select sname,/doc/3c2526876.html,o,credit from student, course ,sc where grade is nulland student.sno=sc.sno and /doc/3c2526876.html,o=http://www.doczj .com/doc/3c2526876.html,o(4) Select cno,count(sno),max(grade),min(grade), avg(grade) from sc wheregroup by cno order by cno(5) 二步：第一步：CREATE TABLE FGRADE(SNAME VARCHAR(8) NOT NULL,CNO CHAR(6) NOT NULL,文本框: 司机司机机动车警察下发处罚通知包含开出11mmm1GRADE DEC(4,1) DEFAULT NULL);第二步：INSERT INTO FGRADE SELECT SNAME,CNO,GRADE FROM STUDENT,SC WHERESTUDENT.SNO=SC.SNO AND SEX=‘女’;10.(1) select ename,dname from emp,dept where salary>=600 and emp.dno=dept.dno(2)select dname from emp,dept where eno=’001’and emp.dno=dept.dnoПdname(σeno=’001’and emp.dno=dept.dno (emp×dept)) 或者Пdname(emp eno=’001’dept)(3) update emp set salary=salary*1.1 where salary<600 and dno in (select dnofrom dept where dname=’销售部’)(4) 查询编号为“001” 的部门经理的职工号。

数据结构(含课程设计)·随堂练习2019春华南理工大学网络教育答案

数据结构(含课程设计)·随堂练习2019春华南理工大学网络教育答案

数据结构（含课程设计），随堂第一章绪论1.(单选题) 计算机所处理的数据一般具备某种内在联系，这是指（）。

A、数据和数据之间存在某种关系 B.元素和元素之间存在某种关系C元素内部具有某种结构 D.数据项和数据项之间存在某种关系答题： A. B. C. D. （已提交）参考答案：B问题解析：2.(单选题) 在数据结构中，与所使用计算机无关的是数据的（）结构.A.逻辑B.存储C.逻辑和存储D. 物理答题： A. B. C. D. （已提交）参考答案：A问题解析：3.(单选题) 数据结构在计算机中的表示称为数据的（）A.存储结构B.抽象数据类型C.顺序结构D.逻辑结构答题： A. B. C. D. （已提交）参考答案：A问题解析：4.(单选题) 在计算机中存储数据时，通常不仅要存储各数据元素的值，还要存储（）.A.数据的处理方法B.数据元素的类型C.数据元素之间的关系D.数据的存储方法答题： A. B. C. D. （已提交）参考答案：C问题解析：5.(单选题) 在计算机的存储器中表示数据时，逻辑上相邻的两个元素对应的物理地址也是相邻的，这种存储结构称为（）A.逻辑结构B.顺序存储结构C.链式存储结构D.以上都正确答题： A. B. C. D. （已提交）参考答案：B问题解析：6.(单选题) 当数据采用链式存储结构时，要求（）.A.每个结点占用一片连续的存储区域B.所有结点占用一片连续的存储区域C结点的最后一个数据域是指针类型D.每个结点有多少个后继就设多少个指针域答题： A. B. C. D. （已提交）参考答案：A问题解析：7.(单选题) 以下关于算法的说法正确的是（）.A.算法最终必须由计算机程序实现B.算法等同于程序C算法的可行性是指指令不能有二义性D.以上都是错误的答题： A. B. C. D. （已提交）参考答案：D问题解析：8.(单选题) 算法的时间复杂度与（）有关.A问题规模 B.计算机硬件性能C编译程序质量 D.程序设计语言答题： A. B. C. D. （已提交）参考答案：A问题解析：9.(单选题) 算法的主要任务之一是分析（）A算法是否具有较好的可读姓,B算法中是否存在语法错误,C算法的功能是否符合设计要求D.算法的执行时间和问题规模之间的关系答题： A. B. C. D. （已提交）参考答案：D问题解析：10.(单选题) 某算法的时间复杂度为O()，表明该算法的（）A问题规模是 B执行时间等于C.执行时间与成正比D.问题规模与成正比答题： A. B. C. D. （已提交）参考答案：C问题解析：第二章线性表1.(单选题) 线性表是具有n个（）的有限序列.A.关系 B字符C数据元素 D.数据项答题： A. B. C. D. （已提交）参考答案：C问题解析：2.(单选题) 以下关于线性表的叙述中正确的是（）A.每个元素都有一个前趋元素和一个后继元素B线性表中至少有一个元素C.线性表中元素的排列次序必须是由小到大或由大到小D.除第一个和最后一个元素外，每个元素都有一个且仅有一个前趋元素和后继元素答题： A. B. C. D. （已提交）参考答案：D问题解析：3.(单选题) 以下关于线性表和有序表的叙述中正确的是（）。