华南理工网络教育 数据结构 第1~5章作业 答案

华南理工大学网络教育学院数据库同步练习册答案答案：第一章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” 的部门经理的职工号。

数据结构（含课程设计），随堂第一章绪论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.(单选题) 以下关于线性表和有序表的叙述中正确的是（）。

随堂练习提交截止时间：2018-06-15 23:59:59当前页有10题，你已做10题，已提交10题，其中答对10题。

答题： A. B. C.答题： A. B. C.答题： A. B. C.答题： A. B. C.答题： A. B. C.答题： A. B. C. D.（已提交）参考答案：B 问题解析：7.(单选题) 在OSI 参考模型中能实现路由选择、拥塞控制与互连功能的层是________。

A.传输层B.应用层C.网络层D.物理层答题：A.B.C.D.（已提交）参考答案：C 问题解析：8.(单选题) 下列说法中不对的是：_________。

A.可以同时双向传输信号的通信方式称为全双工通信方式；？B.在数字通信信道上，直接传送基带信号的方法称为频带传输；？ IP 参考模型共分为四层，最底层为网络接口层，最高层是应用层；？ D.类型不同的网络只要使用TCP/IP 协议都可以互连成网。

答题：A.B.C.D.（已提交）参考答案：B 问题解析：9.(单选题) 在网络工程中通常用的线缆标准为_________。

答题：A.B.C.D.（已提交）参考答案：B 问题解析：10.(单选题) 不属于计算机网络应用的是____ _____。

A.电子邮件的收发 B.用“写字板”写文章？C.用计算机传真软件远程收发传真D.用浏览器浏览“上海热线”网站答题：A.B.C.D.（已提交）参考答案：B 问题解析：随堂练习提交截止时间：2018-06-15 23:59:59当前页有10题，你已做10题，已提交10题，其中答对10题。

答题： A. B. C.答题： A. B. C.C.这种接入方式采用的是分组交换技术D.这种接入方式采用的是同步传输技术答题： A. B. C. D.（已提交）参考答案：C问题解析：4.(单选题) 以下信道中哪一种是广播共享信道________。

A.载波侦听多路访问信道B.频份多路复用信道C.时分多路复用信道D.以上三种都是共享广播信道答题： A. B. C. D.（已提交）参考答案：A问题解析：5.(单选题) 在计算机网络中，表征数据传输有效性的指标是_________。

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. 72 设有一个二维数组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. 04 下面程序的时间复杂度为（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）进行。

数据结构习题参考答案第一章答案一、填空题1．数据元素，数据项2． O(1)，O(n)，O(log 2n)，O(n 2)3．线性结构，非线性结构，顺序结构，链式结构4．无，一，无，一5．前驱，一，无，任意6．任意7． O(n 1/2)8.O(1)<o(2n<="") 第二章答案一、填空题1． n/2，(n-1)/2分析：当在顺序线性表中的第i （1<=i<=n+1）个位置之前插入一个新元素时，从第i 个元素起向后的n+1-i 个元素均要向后移动一个位置。

因此在等概率情况下，插入操作中元素的平均移动次数为∑+==-++=112)1(11)(n i ni n n n f ；当在顺序线性表中删除第i （1<=i<=n ）个位置上的元素，从第i+1个元素起向后的n-i 个元素均要向前移动一个位置。

因此在等概率情况下，删除操作中元素的平均移动次数为∑=-=-= n i n i n n n f 121)(1)(。

2．向后3．向前4．指针域5．一定，不一定6． O(n)7． O(n)8．消除空表的特殊性，统一表示和处理空表和非空表的情形，从而简化插入和删除等操作的某些细节。

9．前驱，后继10．O(n)二、填空题1． (1)2． (1)3． (4)4． (2)5． (2)6． (4)7． (4)8． (1)9． (4)10．(1)11．(2)12．(3)第三章参考答案一、填空题1．线性，任何，栈顶，队尾，队头2．先进后出（FILO ），队尾，队头，先进先出（FIFO ）3． top==0，top==m4． 235415．前一个位置，所在位置，m-1分析：在顺序循环队列中约定头指针front 和尾指针rear 所指向的位置，是牺牲掉一个存储单元而方便表示队列空和队列满的条件，因此顺序循环队列中实际可用的存储单元只有m-1个。

6． (rear+1)%m==front ，rear==front7． O(1)8．返回地址，返回地址二、选择题1.(3) 2.(3) 3.(3) 4. (2)5. (2)6. (3)7. (1)8. (4)因为：顺序循环队列中的元素个数=??<+-≥-front rear m front rear front rear front rear ，整理合并可写成(rear-front+m)%m 。

第1章绪论5．选择题：CCBDCA6．试分析下面各程序段的时间复杂度。

（1）O（1）（2）O（m*n）（3）O（n2）（4）O（log3n）（5）因为x++共执行了n-1+n-2+……＋1= n(n-1)/2，所以执行时间为O（n2）（6）O(n)第2章线性表1．选择题babadbcabdcddac2．算法设计题（6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。

ElemType Max (LinkList L ){if(L->next==NULL) return NULL;pmax=L->next; //假定第一个结点中数据具有最大值p=L->next->next;while(p != NULL ){//如果下一个结点存在if(p->data > pmax->data) pmax=p;p=p->next;}return pmax->data;（7）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。

void inverse(LinkList &L) {// 逆置带头结点的单链表 Lp=L->next; L->next=NULL;while ( p) {q=p->next; // q指向*p的后继p->next=L->next;L->next=p; // *p插入在头结点之后p = q;}}（10）已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为item的数据元素。

[题目分析] 在顺序存储的线性表上删除元素，通常要涉及到一系列元素的移动（删第i个元素，第i+1至第n个元素要依次前移）。

本题要求删除线性表中所有值为item的数据元素，并未要求元素间的相对位置不变。

因此可以考虑设头尾两个指针（i=1，j=n），从两端向中间移动，凡遇到值item的数据元素时，直接将右端元素左移至值为item的数据元素位置。

《数据结构》教材课后习题+答案数据结构第一章介绍数据结构是计算机科学中重要的概念，它涉及到组织和存储数据的方法和技术。

数据结构的选择对于算法的效率有着重要的影响。

本教材为读者提供了丰富的课后习题，以帮助读者巩固所学知识并提高解决问题的能力。

下面是一些选定的习题及其答案，供读者参考。

第二章线性表习题一：给定一个顺序表L，编写一个算法，实现将其中元素逆置的功能。

答案一：算法思路：1. 初始化两个指针i和j，分别指向线性表L的首尾两个元素2. 对于L中的每一个元素，通过交换i和j所指向的元素，将元素逆置3. 当i>=j时，停止逆置算法实现：```pythondef reverse_list(L):i, j = 0, len(L)-1while i < j:L[i], L[j] = L[j], L[i]i += 1j -= 1```习题二：给定两个线性表A和B，编写一个算法，将线性表B中的元素按顺序插入到线性表A中。

答案二：算法思路：1. 遍历线性表B中的每一个元素2. 将B中的元素依次插入到A的末尾算法实现：```pythondef merge_lists(A, B):for element in B:A.append(element)```第三章栈和队列习题一：编写一个算法，判断一个表达式中的括号是否匹配。

表达式中的括号包括小括号"()"、中括号"[]"和大括号"{}"。

答案一：算法思路：1. 遍历表达式中的每一个字符2. 当遇到左括号时，将其推入栈中3. 当遇到右括号时，判断栈顶元素是否与其匹配4. 当遇到其他字符时，继续遍历下一个字符5. 最后判断栈是否为空，若为空则表示括号匹配算法实现：```pythondef is_matching(expression):stack = []for char in expression:if char in "([{":stack.append(char)elif char in ")]}":if not stack:return Falseelif (char == ")" and stack[-1] == "(") or (char == "]" and stack[-1] == "[") or (char == "}" and stack[-1] == "{"):stack.pop()else:return Falsereturn not stack```习题二：利用两个栈实现一个队列。

第1章绪论一、填空题01、【操作对象】【关系和运算】02、【数据元素】【关系】03、【逻辑结构】【存储结构】【运算】04、【线性结构】【非线性结构】05、【一对一】【一对多】【多对多】06、【没有】【没有】07、【前驱】【1】【后续】【任意多个】08、【任意多个】09、【顺序】【链式】【索引】【散列】10、【集合】【线性结构】【树形结构】【图状结构】11、【插入】【删除】【修改】【查找】【排序】12、【时间】【空间】13、【时间复杂度】【空间复杂度】14、【映射】15、【有穷性】【确定性】【可行性】16、【n+1】【n】【n(n+3)/2】【n(n+1)/2】17、【n(n+1)(n+2)/6】【O(n3)】18、【O(n2 log)】19、【O(nn2 log)】20、【O(22log n)】21、【(n+3)(n-2)/2】22、【n(n-1)/2】二、判断题01-05、×××√×06-10、×√×××11-12、√×三、单项选择题B01 BD02 A03 C04 C05A06 C07 B08 A09 C10B11 A12 C13 D14 A15C16四、分析下面各程序段的时间复杂度01、O（nm ）02、O（2n）03、答：O（2n）04、答：O（n3 log）五、设有数据逻辑结构S=(D,R)，试按各小题所给条件画出这些逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点？01、此图为线性结构d1→d2→d3→d4d1—无直接前驱，是首结点d4—无直接后继是尾结点02、此图为树形结构d1—无直接前驱，是根结点d2,d5,d7,d9—无直接后继是叶子结点03、此图为图形结构d1，d2—无直接前驱，是开始结点d6,d7—无直接后继是终端结点六、简述题01、什么是数据结构?答：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。