北师大《数据结构》在线作业.docxVIP

北师大《数据结构》在线作业 北师大《数据结构》在线作业 PAGEPAGE5 北师大《数据结构》在线作业 1/顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的。 线性结构 非线性结构 存储位置 指针 2/算法指的是（ ）。 对特定问题求解步骤的一种描述，是指令的有限序列。 计算机程序 解决问题的计算方法 数据处理 3/算法在发生非法操作时可以作出处理的特性称为（ ）。 健壮性 确定性 可行性 正确性 4/若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋，则采用（ ）存储方法最节省时间。 顺序表 单链表 双链表 单循环链表 5/头结点的单链表head为空的判定条件是（ ）。 head==NULL head-next==NULL head-next==head head!=NULL 6/单循环链表的主要优点是（ ）。 不再需要头指针了 从表中任一结点出发都能扫描到整个链表； 已知某个结点的位置后，能够容易找到它的直接前趋； 在进行插入、删除操作时，能更好地保证链表不断开。 7/使用双向链表存储线性表，其优点是可以（ ）。 方便双向查找 更方便数据的插入和删除 节约存储空间 很快回收存储空间 8/设数组S[n]作为两个栈S1和S2的存储空间，对任何一个栈只有当S[n]全满时才不能进行进栈操作。为这两个栈分配空间的最佳方案是（ ）。 S1的栈底位置为0，S2的栈底位置为n-1 S1的栈底位置为0，S2的栈底位置为n/2 S1的栈底位置为0，S2的栈底位置为n S1的栈底位置为0，S2的栈底位置为1 9/设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（ ）。 6 4 3 2 10/表达式a*(b+c)-d的后缀表达式是（ ）。 abcd*+- abc+*d- abc*+d- -+*abcd 11/深度为k的完全二叉树至少有（）个结点。 2k-2+1 2k-1 2k-1 2k–1-1 12/一个高度为h的满二叉树共有n个结点，其中有m个叶子结点，则有（）成立。 n=h+m h+m=2n m=h-1 n=2h-1 13/设森林中有4棵树，树中结点的个数依次为n1、n2、n3、n4，则把森林转换成二叉树后，根结点的左子树上有（）个结点。 n1-1 n1 n1+n2+n3 n2+n3+n4 14/有一个按元素值排好序的顺序表（长度大于2），分别用顺序查找和折半查找与给定值相等的元素，比较次数分别是s和b，在查找不成功的情况下，s和b的关系是（ ）。 s=b sb s 不一定 15/散列技术中的冲突指的是（ ）。 两个元素具有相同的序号 两个元素的键值不同，而其他属性相同 数据元素过多 不同键值的元素对应于相同的存储地址 简答 带头结点的链表和不带头结点的链表有什么不同？ 单链表是一种最为基本的数据结构，常用的单链表又分为带头结点和不带头结点两种。从线性表的定义可以知道，线性表要求允许在任意位置进行插入和删除操作。所有的链表都有一个头指针head， 带头结点的链表中head的数据项为空 。 具体分析。 1.带头节点的链表的插入， 首先使用临时变量p等于要插入之前的节点（不管具体的插入位置） ，之后不管要插入的节点x是插到链表头还是插到链表的其他位置都是如下语句: x-next = p-next;p-next = x; 2.不带头结点的链表的插入， 若要插到链表的开头则 x-next = head-next; head = x;头结点的链表的删除， 不解释，同样不存在删除位置的差异。 4.不带头结点的链表的删除，删除第一个节点时，head=head-next。删除其他节点时，head的值不会改变。 综上所述，带头节点的单链表，不论删除和插入的位置如何，不需要修改head的值，不带头结点的单链表则需要修改head的值。所以单链表 一般为带头结点的单链表 。 论述 如果矩阵A中存在这样的一个元素A[i][j]满足条件：A[i][j]是第i行中值最小的元素，且又是第j列中值最大的元素，则称之为该矩阵的一个马鞍点。编写一个函数计算出m×n的矩阵A的所有马鞍点。 提示：依题意，先求出每行的最小值元素，放入min[m]之中，再求出每列的最大值元素，放入max[n]之中，若某元素既在min[i]中，又在max[j]中，则该元素A[i][j]便是马鞍点，找出所有这样的元素,即找到了所有马鞍点 .\n); scanf(%d%d,m,n); printf(Type some data...\n); for(i=0;im;i++) for(j=0;jn;scanf(%d,a[