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

1/顺序存储结构中数据元素之间的逻辑关系是由（）表示的。线性结构非线性结构存储位置指针2/算法指的是（）。对特定问题求解步骤的一种描述，是指令的有限序列。计算机程序解决问题的计算方法数据处理3/算法在发生非法操作时可以作出处理的特性称为（）。健壮性确定性可行性正确性4/若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋，则采用（）存储方法最节省时间。顺序表单链表双链表单循环链表5/头结点的单链表head为空的判定条件是（）。head==NULLhead-next==NULLhead-next==headhead!=NULL6/单循环链表的主要优点是（）。不再需要头指针了从表中任一结点出发都能扫描到整个链表；已知某个结点的位置后，能够容易找到它的直接前趋；在进行插入、删除操作时，能更好地保证链表不断开。7/使用双向链表存储线性表，其优点是可以（）。方便双向查找更方便数据的插入和删除节约存储空间很快回收存储空间8/设数组S[n]作为两个栈S1和S2的存储空间，对任何一个栈只有当S[n]全满时才不能进行进栈操作。为这两个栈分配空间的最佳方案是（）。S1的栈底位置为0，S2的栈底位置为n-1S1的栈底位置为0，S2的栈底位置为n/2S1的栈底位置为0，S2的栈底位置为nS1的栈底位置为0，S2的栈底位置为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-12k–1-112/一个高度为h的满二叉树共有n个结点，其中有m个叶子结点，则有（）成立。n=h+mh+m=2nm=h-1n=2h-113/设森林中有4棵树，树中结点的个数依次为n1、n2、n3、n4，则把森林转换成二叉树后，根结点的左子树上有（）个结点。n1-1n1n1+n2+n3n2+n3+n414/有一个按元素值排好序的顺序表（长度大于2），分别用顺序查找和折半查找与给定值相等的元素，比较次数分别是s和b，在查找不成功的情况下，s和b的关系是（）。s=bsbs不一定15/散列技术中的冲突指的是（）。两个元素具有相同的序号两个元素的键值不同，而其他属性相同数据元素过多不同键值的元素对应于相同的存储地址简答带头结点的链表和不带头结点的链表有什么不同？单链表是一种最为基本的数据结构，常用的单链表又分为带头结点和不带头结点两种。从线性表的定义可以知道，线性表要求允许在任意位置进行插入和删除操作。所有的链表都有一个头指针head，带头结点的链表中head的数据项为空。具体分析。1.带头节点的链表的插入，首先使用临时变量p等于要插入之前的节点（不管具体的插入位置），之后不管要插入的节点x是插到链表头还是插到链表的其他位置都是如下语句:x-next=p-next;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的值。所以单链表一般为带头结点的单链表。论述如果矩阵A中存在这样的一个元素A[i][j]满足条件：A[i][j]是第i行中值最小的元素，且又是第j列中值最大的元素，则称之为该矩阵的一个马鞍点。编写一个函数计算出m×n的矩阵A的所有马鞍点。提示：依题意，先求出每行的最小值元素，放入min[m]之中，再求出每列的最大值元素，放入max[n]之中，若某元素既在min[i]中，又在max[j]中，则该元素A[i][j]便是马鞍点，找出所有这样的元素,即找到了所有马鞍点//#includestdafx.h//vc++6.0#includestdio.hvoidmain(void){inta[5][5],i,j,jj,n,m,x,max,f;printf(Enterm&n(Positiveinteger)...\n);scanf(%d%d,&m,&n);printf(Typesomedata...\n);for(i=0;im;i++)for(j=0;jn;scanf(%d,&a[i][j++]));for(max=~(1sizeof(int)*8-1),f=i=0;im;i++){for(x=max,j=0;jn;j++)if(xa[i][j])x=a[i][jj=j];for(j=0;jm;j++)if(a[j][jj]x)break;if(j==m)printf(%4d,f=x);}if(!f)printf(No!\n);printf(\n);}