2017 数据结构(四川师范大学)1002349021 最新满分章节测试答案

本答案对应课程为:点我自动跳转查看
本课程起止时间为:2017-09-15到2018-02-28
本篇答案更新状态:已完结

第1周 第1周测验

1、 问题:图书馆的数目检索系统采用 关系的数据结构
选项：
A:集合
B:线性
C:树形
D:图状
答案: 【线性】

2、 问题: 是相互之间存在一种或多种特定关系的数据元素的集合。
选项：
A:数据
B:数据元素
C:数据项
D:数据结构
答案: 【数据结构】

3、 问题: 是一个值的集合和定义在这个值集上的一组操作的总称。
选项：
A:数据类型
B:数据元素
C:数据项
D:数据结构
答案: 【数据类型】

4、 问题:算法的确定性是指（ ）
选项：
A:当输入数据非法时，算法也能作出反应或进行处理
B:在任何情况下，算法不会出现死循环
C:算法中的每一条指令必须有确切的含义
D:算法中没有逻辑错误
答案: 【算法中的每一条指令必须有确切的含义】

第8周 第8周测验

1、 问题:对线性表进行二分查找时,要求线性表必须（ ）。
选项：
A:以顺序方式存储
B:以链接方式存储
C:以顺序方式存储,且结点按关键字有序排序
D:以链接方式存储,且结点按关键字有序排序
答案: 【以顺序方式存储,且结点按关键字有序排序】

2、 问题:下列描述中不符合二叉排序树特点的是（ ）
选项：
A:左子树中所有结点的关键字小于根结点的关键字
B:右字树中所有结点的关键字大于根节点的关键字
C:根结点的关键字大于左、右子树中所有结点的关键字
D:关键字插入的顺序影响二叉排序树的形态
答案: 【根结点的关键字大于左、右子树中所有结点的关键字】

3、 问题:设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点：addr (15)=4; addr (38)=5; addr (61)=6; addr (84)=7如用二次探测再散列处理冲突，关键字为49的结点的地址是（ ）。
选项：
A:8
B:3
C:5
D:9
答案: 【9】

4、 问题:试将折半查找的算法改写成递归算法。 Int bisearch (sqlist L,int low, int high , elemtype x ) { If (low>high) reeturn( 0 ); else { mid=(low+high)/2; if (L.data[mid]= =x) return (mid); else if (L.data[mid]>x) bisearch(L,low,mid-1,x); else ; } }//bisearch
答案: 【bisearch(L,mid+1,high,x)】

5、 问题:设计算法判定给定二叉树是否为二叉排序树。void BSTree(BiTree t,int &flag,int &last);//声明Status IsBSTree(BiTree t){ int flag = 1; int last =0; BSTree(t,flag,last); return flag;}void BSTree(BiTree t,int &flag,int &last){//取地址不需要返回值 if(t->lchild&&flag) BSTree(t->lchild,flag,last);//遍历左子树 if(t->data.key>last&&flag) last = t->data.key;else flag=0;//last原为父节点值，但到了树叶节点后被树叶节点的key值覆盖，然后开始向上反馈keyif(t->rchild&&flag) ；}
答案: 【BSTree(t->rchild,flag,last)】

【作业】第8周 第8周作业

1、 问题:画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。
评分规则: 【 能画出正确的判定树
求出等概率时查找成功的平均查找长度
】

2、 问题:已知如下所示长度为12的表(Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec)(1)试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。(2)若对表中元素先进行排序构成有序表，求其在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。(3)按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。
评分规则: 【 完成第（1）问，且答案准确
完成第（2）问，且答案准确
完成第（3）问，且答案准确
】

3、 问题:试从空树开始，画出按以下次序向2-3树即3阶B-树中插入关键码的建树过程：20,30,50,52,60,68,70。如果此后删除50和68，画出每一步执行后2-3树的状态。
评分规则: 【 按要求画出整个建树过程
正确画出删除50和68的执行过程
】

第2周 第2周测验

1、 问题:用顺序结构存储，删除最后一个结点时（ ）
选项：
A:会移动其它结点位置
B:一定不会移动其它结点位置
C:可能会移动其它结点位置
D:其它
答案: 【一定不会移动其它结点位置】

2、 问题:链表中逻辑上相邻的元素的物理地址 相邻。
选项：
A:必定
B:不一定
C:一定不
D:其它
答案: 【不一定】

3、 问题:线性表中的数据元素有一个前驱多个后继
选项：
A:正确
B:错误
答案: 【错误】

4、 问题:假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序(即非递增有序，允许表中含有值相同的元素)排列的线性表C，并要求利用原表(即A表和B表)的结点空间构造C表。// 将合并逆置后的结果放在C表中，并删除B表Status ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C){ LinkList pa,pb,qa,qb; pa=A; pb=B; qa=pa; // 保存pa的前驱指针 qb=pb; // 保存pb的前驱指针 pa=pa->next; pb=pb->next; A->next=NULL; C=A; while(pa&&pb){ if(pa->datadata){ qa=pa; pa=pa->next; qa->next=A->next; A->next=qa; } else{ qb=pb; pb=pb->next; //将当前最小结点插入A表表头 A->next=qb; } } while(pa){ qa=pa; pa=pa->next; qa->next=A->next; A->next=qa; } while(pb){ qb=pb; pb=pb->next; qb->next=A->next; A->next=qb; } pb=B; free(pb); return OK;}
答案: 【qb->next=A->next;】

5、 问题:假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。Status ListDelete_CL(LinkList &S){ LinkList p,q; if(S==S->next)return ERROR; q=S; p=S->next; while( ){ q=p; p=p->next; } q->next=p->next; free(p)； return OK;}
答案: 【p->next!=s】

【作业】第2周 第2周作业

1、 问题:设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。
评分规则: 【 算法基本思路正确
逻辑无错误
算法整体可行
】

2、 问题:已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效的算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素），同时释放被删结点空间，并分析你的算法的时间复杂度（注意，mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。
评分规则: 【 算法基本思路正确
逻辑无错误，算法整体可行
算法能实现题目中的所有要求，并分析出算法的时间复杂度
】

【作业】第1周 第1周作业

1、 问题:说说数据结构和程序设计的关系
评分规则: 【 能说出关键点，且语句通顺
】

2、 问题:数据的逻辑关系，数据的存储结构及数据的运算之间存在着怎样的关系？
评分规则: 【 能正确地说出三者之间的关系
】

3、 问题:当你为解决某一问题而选择数据结构时，应从哪些方面考虑？在编辑管理通讯录时，什么样的数据结构合适？为什么？
评分规则: 【 要点基本回答正确
】

第9周 第9周测验

1、 问题:设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4 的一趟希尔排序结束后前4条记录关键字为（）。
选项：
A:40，50，20，95
B:15，40，60，20
C:15，20，40，45
D:45，40，15，20
答案: 【15，40，60，20】

2、 问题:快速排序方法在情况下最不利于发挥其长处。( )
选项：
A:要排序的数据量太大
B:要排序的数据中含有多个相同值
C:要排序的数据已基本有序
D:要排序的数据个数为奇数
答案: 【要排序的数据已基本有序】

3、 问题:一组记录的排序码为(46,79,56,38,40,84),则利用堆排序的方法建立的初始推为（）
选项：
A:79,46,56,38,40,80
B:84,79,56,38,40,46
C:84,79,56,46,40,38
D:84,56,79,40,46,38
答案: 【84,79,56,38,40,46】

4、 问题:设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（ A ）。
选项：
A:15，25，35，50，20，40，80，85，36，70
B:15，25，35，50，80，20，85，40，70，36
C:15，25，35，50，80，85，20，36，40，70
D:15，25，35，50，80，20，36，40，70，85
答案: 【15，25，35，50，20，40，80，85，36，70】

5、 问题:设有1000个无序的元素,希望用最快的速度挑选出其中前10个最大的元素,最好的排序方法是（）。
选项：
A:选择排序
B:快速排序
C:堆排序
D:插入排序
答案: 【选择排序】

6、 问题:具有10个记录的序列，采用冒泡排序最少的比较次数是 ( )