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

1、北师大数据结构在线作业1/ 顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的线性结构非线性结构存储位置指针2/ 算法指的是（ ）对特定问题求解步骤的一种描述，是指令的有限序列计算机程序解决问题的计算方法数据处理3/ 算法在发生非法操作时可以作出处理的特性称为（ ）健壮性确定性可行性正确性4/ 若某线性表中最常用的操作是取第 i 个元素和找第 i 个元素的前趋，则采用 （ ）存储方法最节省时间。顺序表单链表双链表单循环链表5/ 头结点的单链表 head为空的判定条件是（ ）。head=NULLhead-next=NULLhead-next=headhead!=NULL6/ 单循环链表的主要优

2、点是（ ）。不再需要头指针了从表中任一结点出发都能扫描到整个链表；已知某个结点的位置后，能够容易找到它的直接前趋；在进行插入、删除操作时，能更好地保证链表不断开。7/ 使用双向链表存储线性表，其优点是可以（ ）。方便双向查找更方便数据的插入和删除节约存储空间很快回收存储空间8/设数组 Sn 作为两个栈 S1和 S2的存储空间，对任何一个栈只有当 Sn 全满 时才不能进行进栈操作。为这两个栈分配空间的最佳方案是（ ）。S1的栈底位置为 0，S2 的栈底位置为 n-1S1的栈底位置为 0，S2 的栈底位置为 n/2S1的栈底位置为 0，S2 的栈底位置为 nS1的栈底位置为 0，S2 的栈底位置为

3、 19/设栈 S和队列 Q的初始状态为空，元素 e1、e2、e3、e4、e5、e6依次通过栈 S，一个元素出栈后即进入队列 Q，若 6 个元素出队的顺序是 e2、e4、e3、e6、 e5、e1，则栈 S 的容量至少应该是（ ）。643210/ 表达式 a*（b+c）-d 的后缀表达式是（ ）。abcd*+-abc+*d-abc*+d-+*abcd11/深度为 k 的完全二叉树至少有（）个结点。2k-2+12k-12k-12k1-112/ 一个高度为 h的满二叉树共有 n个结点，其中有 m个叶子结点，则有（）成 立。n=h+mh+m=2nm=h-1n=2h-113/ 设森林中有 4棵树，树中结点

4、的个数依次为 n1、n2、n3、n4，则把森林转换 成二叉树后，根结点的左子树上有（）个结点。n1-1简答带头结点的链表和不带头结点的链表有什么不同？ 单链表是一种最为基本的数据结构，常用的单链表又分为带头结点和不带头结点两种。从线性表的定义可以知道， 线性表要求允许在任意位置进行插入和删除操作。所有的链 表都有一个头指针 head ， 带头结点的链表中 head 的数据项为空 。具体分析。1. 带头节点的链表的插入， 首先使用临时变量 p 等于要插入之前的节点（不管具体的 插入位置） ，之后不管要插入的节点 x 是插到链表头还是插到链表的其他位置都是如 下语句 : x-next = p-ne

5、xt;p-next = x;2. 不带头结点的链表的插入， 若要插到链表的开头则x-next = head-next;head = x;/ 这里不再是 head-next = x若插到链表的其他位置则p = 插入之前的节点x-next = p-next;p-next = x;3. 带头结点的链表的删除， 不解释，同样不存在删除位置的差异。4. 不带头结点的链表的删除， 删除第一个节点时， head=head-next 。删除其他节点 时， head 的值不会改变。综上所述，带头节点的单链表，不论删除和插入的位置如何，不需要修改 head 的值， 不带头结点的单链表则需要修改 head 的值。所

6、以单链表 一般为带头结点的单链表 论述 如果矩阵 A 中存在这样的一个元素 Aij 满足条件： Aij 是第 i 行中值最小的元素， 且又是第 j 列中值最大的元素，则称之为该矩阵的一个马鞍点。编写一个函数计算出 m n 的矩阵 A 的所有马鞍点。提示：依题意，先求出每行的最小值元素，放入 minm 之中，再求出每列的最大值元 素，放入 maxn 之中，若某元素既在 mini 中，又在 maxj 中，则该元素 Aij 便是马鞍点，找出所有这样的元素 ,即找到了所有马鞍点/#include stdafx.h/vc+6.0#include stdio.hvoid main(void)int a55,i,j,jj,n,m,x,max,f;printf(Enter m & n(Positive integer).n);scanf(%d%d,&m,&n);printf(Type some data.n);for(i=0;im;i+)for(j=0;jn;scanf(%d,&aij+);for(max=(1sizeof(int)*8-1),f=i=0;im