《数据结构2011年秋季期末复习提纲+习题new.doc》由会员分享，可在线阅读，更多相关《数据结构2011年秋季期末复习提纲+习题new.doc（9页珍藏版）》请在金锄头文库上搜索。
1、数据结构2011年秋季期末复习提纲期末考试形式：闭卷试卷总评成绩：试卷70%+平时30%试卷题型：1.选择题（20分） ，2.应用题（30分）3.程序填空题（30分）4.算法设计题（20分）每章复习要点：第1章：概念理解：数据结构，时间复杂度程序段： i=1; while(i=n) i=i*2;第2章：表的顺序存储结构，链式存储结构（单链表、循环链表、双向链表），表的基本操作与应用，本章所占分值在15分左右，会考表的算法。(1)顺序存储结构1、下面关于线性表的叙述中，错误的是哪一个？（ ） A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表
2、采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。2、对于顺序表的优缺点，以下说法错误的是：（）A、无需为表示节点间的逻辑关系而增加额外的存储空间；B、可以方便地随机存取表中的任一节点；C、插入和删除运算较方便；D、由于顺序表要求占用连续的空间，存储分配智能预先进行。(2) 链式存储结构1、链表不具备的特点是？（ ） A可随机访问任一节点。B插入删除不需要移动元素。C不必事先估计存储空间。D所需空间与其长度成正比。2、（1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。(2) 静态链表中能容纳的元素个数的最大数在表
3、定义时就确定了，以后不能增加。(3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是（ ）。A（1）（2） B（1） C（1）（2）(3) D（2）3、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是A、head=NULL B、headnext=NULL C、headnext=head D、head!=NULL4、如果对线性表的运算只有两种，即删除第一个元素，在最后一个元素后面插入新元素，最好使用（）A、只有表头指针而没有表尾指针的循环单链表B、只有表尾指针而没有表头指针的循环单链表C、非循环双链表D、循环双链表5、线性表（ a1,a2,an）以链
4、接方式存储时，访问第i位置元素的时间复杂性为（ ）AO（i） BO（1） CO（n） DO（i-1）第3章：栈的实现，栈的应用（数制转换，括号匹配），Hanoi塔不考，队列的实现（其中循环队列重点）。本章所占分值在10分左右，可能会考算法。（1）栈1、一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ ）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 22、输入序列为ABC，输出为ABC时（假设元素出栈则输出），经过的栈操作为（ ）。Apush,pop,push,pop,push,pop Bpush,push,p
5、ush,pop,pop,popCpush,push,pop,pop,push,pop Dpush,pop,push,push,pop,pop（2）队列1、循环队列用数组A【0Maxsize】存放其元素值，头尾指针是front和rear，则队列中元素个数是（）A、（rear-front-1）%MaxsizeB、rear-frontC、（rear-front+1）%MaxsizeD、（rear-front+Maxsize）%Maxsize2、一个队列的入队序列是1，2，3，4，则队列的输出序列是（ ）。A. 4，3，2，1 B. 1，2，3，4 C.1，4，3，2 D. 3，2，1，43、用一个大
6、小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear 和front 的值分别为多少？( )。A. 1 和 5 B. 2 和 4 C. 4 和2 D. 5 和1第4章：只考计算模式串的NEXT值,不考算法，本章所占分值在5分左右1、串ababaaababaa的next数组为（ ）。A012345678999 B012121111212 C011234223456 D012301232234第5章：数组的存储位置计算，压缩矩阵的存储（不考算法）本章所占分值在5分左右1、n阶对称矩阵A,将其上三角的元按列优先顺序压缩存放在一维数组
7、B1n(n+1)/2中，第一个元素a1，1存于B1中，则应存放到Bk中的元素ai,j(1 = i = n,i = j = n)的下标i，j与k的对应关系是k=（ ）。A. i(i+1)/2 + j B. i(i-1)/2 + j C. j(j+1)/2 + i D. j(j-1)/2 + i2、设有数组Ai,j，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A5，8的存储地址为( )。A. BA+141 B. BA+180 C. BA+222 D. BA+225第6章：二叉树的二叉链表存储，二叉树的遍历，霍夫曼树，本章肯
8、定会考二叉树相关算法本章所占分值在20分左右1、一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）。A250 B500 C505 D5012、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果为（ ）。ACBEFDA BFEDCBA CCBEDFA D不定 3、已知一棵二叉树的先序遍历序列为ABD#E#FG#C#H#，#表示空树，请画出对应的二叉树。4、 已知下列字符A、B、C、D、E、F、G 的权值分别为3、12、7、4、2、8、11，试填写出其对应哈夫曼树HT存储结构的终态，即把下表填充完整。（生成的哈夫曼树权值左孩子小右孩子大，权值相等时编
9、号小的先取）weightparentlchildrchild125、写出求二叉树高度的算法。6、一颗度为7的树有8个度为1的结点、7个度为2的结点、6个度为3的结点、5个度为4的结点、4个度为5的结点、3个度为6的结点、2个度为7的结点，该树有（）个叶子结点。7、 已知一棵二叉树的先序、中序和后序序列如下，其中空缺了部分，请画出该二叉树。先序: _BC_EFG_IJK_中序：CBED_GAJ_H_L后序：_E_FD_J_L_HA第7章：图的四种存储结构，图的遍历，最小生成树，拓扑排序，关键路径与最短路径，本章所占分值在15分左右，可能会考算法，但算法主要考察图的遍历算法，其他算法不考。1、已知
10、无向带权连通图G(V, E)的邻接表如下所示，请画出该图，并使用Prim或Kruskal算法求出该图的最小生成树。其中边结点的3个域为：顶点号边上的权值指针4181632121V12V2225231213V3161442254V443181105V54102222、如G3有向图中，顶点表示课程，弧表示课程间的先后关系。如果每人每学期中学一门课程，则应当如何安排课程学习？给出三种方案。第9章：顺序查找表，折半查找表，二叉排序树（重点），平衡二叉树，哈希表，本章所占分值在15分左右，会考表的算法（顺序查找，折半，二叉排序树相关算法）。1、对长度为8的有序表，给出折半查找的判定树，给出等概率情况下的
11、平均查找长度。2、输入一个正整数序列40，28，6，72，100，3，54，1，80，91，38，建立一颗二叉排序树。3、依次把结点10,20,50,100,120,30,90,80,70,110,60插入到初始状态为空的平衡二叉树中,使得在每次插入后保持该树仍然是平衡二叉树。依次画出每次插入后所形成的平衡二叉树。4、使用哈希函数H(key)=key % 9，把一个整数值转换成哈希表下标，现要把数据1，13，12，34，38，33，27，22插入到哈希表中（表长为9）。1）使用线性探测法构造哈希表。2) 使用链地址法构造哈希表。第10章：所有的排序方法，本章所占分值在15分左右，会考算法（所有
12、的排序方法）。1. 已知待排序的序列为（503，87，512，61，908，170，897，275，653，462），将待排序的序列升序排序，请用二叉树的形式画出初建堆的过程（只给出建初始堆的过程）。2. 一组记录的关键字为（22，5，37，14，12），利用快速排序的方法，以第一个记录为基准，画出一次划分的过程（6分）。3. 将数据序列(28,76,54,39,87,14,46,25,78,62)按shell排序法进行排序,增量序列为5，3，1，请写出每倘排序完成之后的序列状态。4. 将数据序列(986,321,123,432,500,654,018,765,987,210)进行基数排序,请
13、写出每趟分配、收集排序过程。5. 将数据序列(46,35,78,12,62,38,80,29)进行归并排序,请写出每趟排序过程。2009年统考计算机考研真题一单项选择题，每小题2分，共80分。1.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是A.栈B.队列C.树D.图2.设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是bdcfeag，则栈S的容量至少是A1B.2C.3D.43.给定二叉树图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3，1，7，5，6，2，4，则其遍历方式是ALRNB.NRLC.RLND.RNL 4.下列二叉排序树中，满足平衡二叉树定义的是5.已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则完全二叉树的结点个数最多是A39B.52C.111D.1196.将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是I父子关系II.兄弟关系III.u的父结点与v的父结点是兄弟关系A.只有IIB.I和IIC.I和IIID.I、II和III7.下列关于无向连通图特性的叙述
