华师大数据结构复习题师大数据结构复习题.ppt

数据结构　学位考试　复习提纲 2013年10月;1、四种基本逻辑结构是：____？ 2、算法区别于程序的主要地方是____。 3、算法评价一般考虑四个方面：____、 ____ 、____、____；其中在数据结构里主要考虑____。 4、时间和空间性能往往是一对矛盾吗？ 5、空间耗费包括代码部分吗？ 6、程序段时间复杂性的简单判断？ 7、算法的时间复杂性越高，则从计算机速度提高得到的收益就越大吗？?;1、顺序表和链表哪个可以按序号随机存取？按值能否随机存取？ 2．顺序表和链表中的逻辑关系分别用什么表示？ 3．链表中结点物理地址一定不连续吗？ 4、寻找单链表中当前结点的后继和前趋的时间复杂度分别是____。 5、单链表中插入、删除结点的执行步骤？ 6、何谓存储密度？顺序表、链表分别如何？;7、例：将顺序表中所有负数移动到表的前端，要求移动次数小。 解：双向扫描：从前向???找一个正数，再从后向前找一个负数，然后交换两者位置。复杂性为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??; } } };8、例：删除顺序表中所有的正数，要求移动次数小。 解：有哪些信誉好的足球投注网站顺序表，对每一个正数，先不删除，而是累计当前正数个数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、C语言中，串的存储方式是_____。 5、空串、空白串、串相等、模式匹配含义？ 6、strcmp()、strlen()、strcat()、strcpy()函数功能？;1、数组的基本运算是读、写。没有插入删除等运算 2、为什么说数组是随机存储结构？ 3、对称矩阵、稀疏矩阵，谁压缩存储后还可以随机存取？ 4、十字链表中的结点需存储非零元素的哪五个信息？ 5、广义表的分类，图形表示与识别？ 6、广义表不仅是线性表的推广，也是树的推广。 7、用head()和tail()函数在广义表A=(a,(x,y,z),b)中取出原子b。 ;1、3个结点可构成____个不同形态的二叉树。 2、二叉树的先根遍历序列和后根遍历序列相同，则该二叉树的特征是____。 3、能否有二叉树，其任何遍历次序都相同？ 4、某完全二叉树有5个叶子，则其结点总数为____。 (10或9，一般2n或2n-1) 5、某完全二叉树的第5层只有6个结点，则其叶子结点数是____。 6、树的先根遍历需要借助__来实现、层次遍历需要借助__来实现。(栈,队列) 7、线索二叉树上，求结点的(遍历)前趋和后继时可利用线索得到，是否就不必进行遍历了？ 8、线索二叉树中，线索的含义？ 9、哈夫曼树的特点？;10、如何画中序、先序、后序线索二叉链表（线索二叉树）？ 解：以中序线索二叉链表为例，下列二叉树的中序线索二叉链表如图所示。详细过程见课本。;11．如何由先序＋中序、后序＋中序还原出二叉树？ 解： ①对前序序列，序列的第一个点就是整个二叉树的根； ②对后序序列，序列的最后一个点就是整个二叉树的根； ③对中序序列，以根为界，序列的前一部分为根的左子树，后一部分为根的右子树；并且，前一部分是左子树的中序序列，后一部分是右子树的中序序列。 若给定了前序和中序序列，反复利用上面的①和③，即由前序序列找到根，由中序序列得到左、右子树；再对每个子树由前序序列找到子树的根，由中序序列得到子树的左、右子树，等等类推，每次得到一个点(子树的根)，从而逐渐还原和构造出该二叉树。;例　 由先根和中根序列构造二叉树;12、例：判断二叉树是否所有结点都为正数。 解：设二叉树根指针类型为bitree，函数名为detect，函数返回判断结果 int detect(bitree t) { if