数据结构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．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于插入和删除操作。
2、对于顺序表的优缺点，以下说法错误的是：（）
A、无需为表示节点间的逻辑关系而增加额外的存储空间；
B、可以方便地随机存取表中的任一节点；
C、插入和删除运算较方便；
D、由于顺序表要求占用连续的空间，存储分配智能预先进行。
(2) 链式存储结构
1、链表不具备的特点是？（    ）
A．可随机访问任一节点。
B．插入删除不需要移动元素。
C．不必事先估计存储空间。
D．所需空间与其长度成正比。
2、（1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。(3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是（  ）。
A．（1）（2）      B．（1）        C．（1）（2）(3)      D．（2）
3、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是
A、head==NULL  B、head→next==NULL    C、head→next==head  D、head!=NULL
4、如果对线性表的运算只有两种，即删除第一个元素，在最后一个元素后面插入新元素，最好使用（）
A、只有表头指针而没有表尾指针的循环单链表
B、只有表尾指针而没有表头指针的循环单链表
C、非循环双链表
D、循环双链表
5、线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（    ）
A．二叉树定义O（i）      B．O（1）      C．O（n）      D．O（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 2
2、输入序列为ABC，输出为ABC时（假设元素出栈则输出），经过的栈操作为（ ）。
A．push,pop,push,pop,push,pop      B．push,push,push,pop,pop,pop
C．push,push,pop,pop,push,pop        D．push,pop,push,push,pop,pop
（2）队列
1、循环队列用数组A【0…Maxsize】存放其元素值，头尾指针是front和rear，则队列中元素个数是（）
A、（rear-front-1）%Maxsize
B、rear-front
C、（rear-front+1）%Maxsize
D、（rear-front+Maxsize）%Maxsize
2、一个队列的入队序列是1，2，3，4，则队列的输出序列是（    ）。
A. 4，3，2，1      B. 1，2，3，4    C.1，4，3，2      D. 3，2，1，4
3、用一个大小为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数组为（ ）。
A．012345678999        B．012121111212   
C．011234223456        D．012301232234
第5章：数组的存储位置计算，压缩矩阵的存储（不考算法）本章所占分值在5分左右
1、n阶对称矩阵A,将其上三角的元按列优先顺序压缩存放在一维数组B[1…n(n+1)/2]中，第一个元素a1，1存于B[1]中，则应存放到B[k]中的元素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 + i
2、设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储地址为(    )。
A. BA+141      B. BA+180    C. BA+222      D. BA+225
第6章：二叉树的二叉链表存储，二叉树的遍历，霍夫曼树，本章肯定会考二叉树相关算法本章所占分值在20分左右
1、一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）。
A．250  B．500  C．505  D．501
2、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果为（ ）。
A．CBEFDA    B．FEDCBA    C．CBEDFA        D．不定
3、已知一棵二叉树的先序遍历序列为ABD#E##FG###C#H##，#表示空树，请画出对应的二叉树。
4、 已知下列字符A、B、C、D、E、F、G 的权值分别为3、12、7、4、2、8、11，试填写出其对应哈夫曼树HT存储结构的终态，即把下表填充完整。（生成的哈夫曼树权值左孩子小右孩子大，权值相等时编号小的先取）
weight
parent
lchild
rchild
1
2
…
5、写出求二叉树高度的算法。
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、已知无向带权连通图G(V, E)的邻接表如下所示，请画出该图，并使用Prim或Kruskal算法求出该图的最小生成树。
其中边结点的3个域为：
顶点号
边上的权值
指针
4
^
18
16
3
2
12
1
V1
2
V2
22
5
2
3
12
1
^
3
V3
16
1
^
4
4
2
2
5
4
V4
4
3
18
1
^
10
5
V5
4
^
10
22
2
2、如G3有向图中，顶点表示课程，弧表示课程间的先后关系。如果每人每学期中学一门课程，则应当如何安排课程学习？给出三种方案。
第9章：顺序查表，折半查表，二叉排序树（重点），平衡二叉树，哈希表，本章所占分值在15分左右，会考表的算法（顺序查，折半，二叉排序树相关算法）。
1、对长度为8的有序表，给出折半查的判定树，给出等概率情况下的平均查长度。
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分左右，会考算法（所有的排序方法）。
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)进行基数排序,请写出每趟分配、收集排序过程。
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的容量至少是  A．1 B.2  C.3  D.4   
3.给定二叉树图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3，1，7，5，6，2，4，则其遍历方式是     A．LRN  B.NRL  C.RLN  D.RNL 
                                                   

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。