数据库结构111.ppt

  1. 1、本文档共14页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
* 数据结构 学位考试 复习提纲 2012年4月 考试时间 90 分钟 第一部分 题型 1.单选题:2分×15=30分  概述1、线性表2、栈队串2、数组广义表1、树3、图2、排序2、查找2 2.判断题:2分×10=20分  概述1、线性表1、栈队串1、数组广义表1、树2、图2、排序1、查找1 3.填空题:2分×11=22分  概述1、线性表1、栈队串1、数组广义表2、树2、图2、排序1、查找1 4.应用题:8分× 2=16分  树1、排序1 5.程序题:6分× 2=12分  二叉链表1、顺序表1 1、四种基本逻辑结构是:____?可把它们分成哪两类:____? 2、算法区别于程序的主要地方是____。 3、算法评价一般考虑哪四个方面? 4、算法分析含义? 5、算法的时间复杂性越高,则提高计算机速度得到的收益就越大吗? 计算机速度提高10倍,则同等时间内可求解的问题规模也可提高10倍吗? 第二部分 复习提纲(不分题型) 1、顺序表和链表哪个可以按序号随机存取?按值能否随机存取? 2、与顺序表相比,链表的优点是? 3、链表前插等效算法? 4、单链表中的头结点就是单链表的第一个结点吗? 5、带头结点的单链表L为空的条件是____。 6.例:将顺序表中所有负数移动到表的前端,要求移动次数小。 解:双向扫描:从前向后找一个正数,再从后向前找一个负数,然后交换两者位置。复杂性为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??; } } } + - - + - - + + - + - - + - 7.例:删除顺序表中所有的正数,要求移动次数小。 解:有哪些信誉好的足球投注网站顺序表,对每一个正数,先不删除,而是累计当前正数个数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、设输入序列为A,B,C,D,能否通过栈得到输出序列DBAC? 3、队列在使用中一定要设置两个指针吗(用以指出队头和队尾)? 4、用尾指针表示循环链队列,则出队和入队的时间复杂度如何? 5、strcat、strlen、strcmp等串函数含义? 1、为什么说数组是随机存储结构? 2、数组的基本运算是读、写。没有插入删除等运算 3、矩阵按三元组形式存贮,就可节省存储空间吗?(稀疏矩阵才可) 4、十字链表中的储存、运算大致特点? 5、用head()和tail()运算在广义表中取出指定项 (a,(b,(c,d)),(e,f)) 1、完全二叉树的概念?识别? 2、深度为k的二叉树,结点数至多为____,结点数至少为____。 3、结点在前序、中序和后序遍历序列中的相对次序会变吗?(叶子不变) 4、有无可能三种遍历序列相同? 5、何谓线索?线索二叉链表中判断某结点有无左、右孩子? 6、递归程序转化成非递归程序时一定要通过栈来实现吗? 7、如何由后序遍历和中序遍历的序列还原二叉树? 例:后序 F B D E C A 中序 F B A D C E 8.如何画中序、先序、后序线索二叉链表(线索二叉树)? 解:以中序线索二叉链表为例,下列二叉树的中序线索二叉链表如图所示。详细过程见课本。 A B C D E F C B D E A 0 0 0 0 0 F 1 1 1 1 1 1 1 NULL NULL 中序:D B E F A C A B C D E F NULL NULL 中序线索二叉树 中序线索二叉链表 9.例:求二叉树叶子数。 解:设二叉树根指针类型为bitree,函数名为detect,函数返回叶子数 int leaf(bitree t) { int L,R; if(t==NULL) return 0; //当前树为空

文档评论(0)

资料 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档