[2017年整理]秋数据结构复习提纲.pptVIP

数据结构　期末考试　复习提纲 2015年12月;1、算法满足的五个重要特性是：____、____、____、输入、输出；其中区别于程序的地方是____。 2、算法评价一般考虑的四个方面是：____、可读性、____、____；其中在数据结构里主要考虑____。 3、算法分析的目的是分析算法是否正确吗？ 4、算法的时间复杂性是指在计算机上的实际运行时间吗？ ? 5、算法的时间复杂性、空间复杂性往往是一对矛盾吗？? 6、计算机的内、外存越大，算法的空间复杂性就越低吗？ ? 7、算法的正确性，一般不进行形式化的证明，而是用测试来验证。 ? 8、简单程序段复杂性判断。;sum=0;for(i=1;i=n;i++) sum+=i;;1、顺序表和链表中的逻辑关系分别用什么表示？ 2、顺序表任何位置插入和删除结点都要移动其它结点吗？ ? 3、求单链表中当前结点的后继和前趋的时间复杂度分别是____。 4、单链表中增加头结点的目的？ 5、单链表中取第i个元素的时间与i成正吗？? 6、带头结点的循环单链表L为空的条件是____。 L- next==L 7、带头结点的单链表L为空的判定条件是____。 L- next==NULL 8、非空单循环链表L中结点*p是尾结点的条件是____。p- next==L 9、每节点1个链域的链表是单链表，每节点2个链域的链表是双链表吗？ ?;10、例：将顺序表中所有负数移动到表的前端，要求移动次数小。 解：双向扫描：从前向后找一个正数，再从后向前找一个负数，然后交换两者位置。复杂性为O（n）。 void moves(sqlist *L) { int i,j; datatype x; i=1;j=L-n; //设数组下标从1开始 while(ij) { while(L-data[i]0 ij) i++; //从前向后找正数 while(L-data[j]=0 ij) j??;//从后向前找负数 if(ij) {//交换 x=L-data[i];L-data[i]=L-data[j];L-data[j]=x; i++;j??; } } };11、例：删除顺序表中所有的正数，要求移动次数小。 解：有哪些信誉好的足球投注网站顺序表，对每一个正数，先不删除，而是累计当前正数个数s，于是，对每个非正数，将它一次性前移s位。算法复杂性为O（n）。 void dels(sqlist *L) { int s,i; s=0; //正数计数器 for(i=0;iL-n;i++) if(L-data[i]0 s++; //累计当前正数 else if(s0) L-data[i-s]=l-data[i];//向前移动s位 L-n=L-n-s; //调整表长 };1、栈操作的原则是_____。 2、栈和队列通常采用的两种存储方式是 _____。 3、设计算法判断表达式中左右括号是否配对，采用_____数据结构最好。 4、队列在使用中必须设置两个指针，分别指向真正的队头和队尾吗？ ? 5、设循环链队列的长度为n，若只设尾指针，则出队和入队的时间复杂度分别是____和____。 O(1)、O(1) 6、若进栈序列为a,b,c，则出栈序列可能有哪些？ 7、设进栈序列为A,B,C,D，则出栈序列可以为B,D,A,C吗？ 8、头指针为F、尾指针为R、带头结点的链队列为空的条件是____。R==F 9、空串并不是由空白字符组成的串。;1、数组A[1..8][1..10]中，每个元素占3个单元，从首地址SA开始存放，若该数组按列存放，则元素A[8][5]的地址是____。SA+117 2、对称矩阵、稀疏矩阵压缩存储后还可以随机存取吗？ 3、稀疏矩阵的三元组表示中，三元组是指非零元素的____、____和____三项。4、稀疏矩阵就是矩阵的元素很少吗？ 5、十字链表中的结点需存储非零元素的哪五个信息？ 6、十字链表的行链表、列链表的头结点为什么能共用？ 7、对广义表((x),(a,b))，长度是____，深度是____。 8、对广义表((x),(a,b))，表头是____，表尾是____。 9、广义表的图形表示？ (识别线性表、纯表、再入表、递归表);1、树的度是指树中结点的最大度数，所以二叉树的度就为2 吗？ 2、若完全二叉树顺序时根结点存放在数组元素BT[0]，且双亲孩子关系如何？ 3、200个结点的二叉树，深度至多为____，深度至少为____。 4、深度为k的二叉树，结点数至多为____，结点数至少为____。 5、深度为k的二叉树，叶子数至多为____，叶子数至少为____。2k-1、1 6、在深度