1、 数据的存贮结构是数据的逻辑结构的存贮映象。
2、 数据结构的概念包括数据的逻辑结构、数据在计算机中的存储方式和数据的运算三个方面。 3、 用顺序表来存储线性表时，不需要另外开辟空间来保存数据元素之间的相互关系。 4、 线性表简称为“顺序表”。
5、 从循环单链表的任一结点出发，可以找到表中所有结点。
6、 线性表的顺序存储方式是按逻辑次序将元素存放在一片地址连续的空间中。
7、 线性表中的元素可以是各式各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。 8、 在线性表的链式存储中，逻辑上相邻的两个元素在物理位置上不一定相邻。 9、 对任何数据结构链式存储结构一定优于顺序存储结构。 10、 链表中的头结点仅起到标识的作用。
11、 串是一种数据对象和操作都特殊的线性表。 12、 一个稀疏矩阵Am*n采用三元组形式表示， 若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。
13、 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。
二、 选择题(有的题可以多选)
1. 算法的计算量的大小称为计算的（ ）。
A．效率 B. 复杂性 C. 现实性 D. 难度 2. 与线性表的链接存储相符的特性是（ ）
A. 插入和删除操作灵活 B. 需要连续存储空间 C. 便于随机访问 D. 存储密度大
3. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（ ）。
A．s->next=p; p->next=s; B．s->next=p->next; p->next=s C．s->next=p->next; p=s; D．p->next=s; s->next=p;
4. 线性表是具有n个（ ）的有限序列。
A、表元素 B、字符 C、数据元素 D、数据项
5. 如果线性表的总数基本稳定并很少进行插入和删除，现要求以最快的速度存取线性表中的元素，则应选用线性
表的（ ）存储结构。
A、顺序 B、链式 C、索引 D、散列 6. 在用p指针访问单链表是，判断不是访问结束的条件是（ ），在访问单循环链表时，判断不是访问结束的
条件是（ ）。
A、p!=NULL B、p!=head C、p->next!=NULL D、p->next！=head 7. 下面的叙述不正确的是（ ）【南京理工大学 1996 一、10（2分）】
A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关
C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关
8. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ）。
A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)
9. 在作进栈运算时,应先判别栈是否( ① ),在作退栈运算时应先判别栈是否( ② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③ )。
为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 ( ④ )分别设在这片内存空间的两端,这样,当( ⑤ )时，才产生上溢。
①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 ④: A. 长度 B. 深度 C. 栈顶 D. 栈底 ⑤: A. 两个栈的栈顶同时到达栈空间的中心点.
B. 其中一个栈的栈顶到达栈空间的中心点.
C. 两个栈的栈顶在栈空间的某一位置相遇.
D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底.
10. 一个栈的输入序列为123„n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）。
A. 不确定 B. n-i+1 C. i D. n-i
11. 若一个栈的输入序列为1,2,3,„,n，输出序列的第一个元素是i，则第j个输出元素是（ ）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的 12. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，
栈2的底在V[m]，则栈满的条件是（ ）。
A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2] 13. 栈在（ ）中应用。
A. 递归调用 B. 子程序调用 C. 表达式求值 D. A，Ｂ，Ｃ 14. 表达式a*(b+c)-d的后缀表达式是( )。
A．abcd*+- B. abc+*d- C. abc*+d- D. -+*abcd 15. 用链接方式存储的队列，在进行删除运算时（ ）。
A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 16. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，
再加入两个元素后，rear和front的值分别为多少？( )
A. 1和 5 B. 2和4 C. 4和2 D. 5和1
17. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，
若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( )。 A． 6 B. 4 C. 3 D. 2 18. 下面关于串的的叙述中，哪一个是不正确的？（ ）
A．串是字符的有限序列 B．空串是由空格构成的串
C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 19. 串的长度是指（ ）
A．串中所含不同字母的个数 B．串中所含字符的个数
C．串中所含不同字符的个数 D．串中所含非空格字符的个数
20. 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个
元素占一个地址空间，则a85的地址为（ ）。
A. 13 B. 33 C. 18 D. 40
21. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA
开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( )。Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*k A. BA+141 B. BA+180 C. BA+222 D. BA+225
23. 有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字
节数是（ ）。【南京理工大学 1999 二、8 （2分）】
A. 60 B. 66 C. 18000 D. 33 24. 对稀疏矩阵进行压缩存储目的是（ ）。【北京工商大学 2001 一、1 (3分)】
A． 便于进行矩阵运算 B．便于输入和输出 C．节省存储空间 D．降低运算的时间复杂度
25. 广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（ ）。【北京邮电大学1999一、2（2分）】
Head(Tail(Head(Tail(Tail(A)))))
A. (g) B. (d) C. c D. d 26. 下面说法不正确的是( )。 【南京理工大学 2001 一、3 （1.5分）】
A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表 C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构
三、填空题
1. 在长度为n的顺序线性表中，删除第i个元素需向前移动 个元素。
2. 在长度为n的顺序线性表中,在第i个节点前插入一个元素需要向后移动 个元素。
3. 串是一种特殊的线性表，其特殊性表现在_ _ __；串的两种最基本的存储方式是_ 、_ _；两个串
相等的充分必要条件是__ _。
4. 下列程序判断字符串s 是否对称，对称则返回1，否则返回0；如 f(\"abba\")返回1，f(\"abab\")返回0； int f( (1)___) {int i=0,j=0;
while (s[j]) (2)____;
for(j--; i 6. 设n行n列的下三角矩阵A已压缩到一维数组B[1..n*（n+1）/2]中，若按行为主序存储，则A[i,j]对应的B 中存储位置为_ ____。 一、 选择题 1. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ） A．5 B．6 C．7 D．8 2. 算术表达式a+b*（c+d/e）转为后缀表达式后为（ ）【中山大学 1999 一、5】 A．ab+cde/* B．abcde/+*+ C．abcde/*++ D．abcde*/++ 3. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ） A．9 B．11 C．15 D．不确定 4. 设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ）。 A．M1 B．M1+M2 C．M3 D．M2+M3 5. 设给定权值总数有n 个，其哈夫曼树的结点总数为( ) A．不确定 B．2n C．2n+1 D．2n-1 分析：哈弗曼树中只有度为2的结点和叶子结点，则结点个数为：n-1+n=2n-1 6. 有关二叉树下列说法正确的是（ ）【南京理工大学 2000 一、11 （1.5分）】 A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2 7. 在一棵高度为k的满二叉树中，结点总数为（ ）【北京工商大学 2001 一、3 (3分)】 k-1 k k A．2B．2C．2k-1 D．log2+1 8. 利用二叉链表存储树，则根结点的右指针是（ ）。【青岛大学 2001 五、5 （2分）】 A．指向最左孩子 B．指向最右孩子 C．空 D．非空 9. 已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ ）。 A．CBEFDA B． FEDCBA C． CBEDFA D．不定 10. 已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（ ）。 A．acbed B．decab C．deabc D．cedba 11. 对于前序遍历与中序遍历结果相同的二叉树为（ F ）; 对于前序遍历和后序遍历结果相同的二叉树为（ B ）。 A．一般二叉树 B．只有根结点的二叉树 C．根结点无左孩子的二叉树 D．根结点无右孩子的二叉树 E．所有结点只有左子数的二叉树 F．所有结点只有右子树的二叉树 12. 引入二叉线索树的目的是（ ） A．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除 C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一 13. 一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有( )个。 A. 32 B. 33 C. 34 D. 30 14. 在一棵树中，（ ）没有前驱结点。 A．父结点 B. 叶子结点 C. 树根结点 D. 孩子结点 15. n个顶点的无向连通图中至少含有( )条边。 A．n-1 B．n C．n(n-1)／2 D. n(n-1) 16. 要连通具有n个顶点的有向图，至少需要（ ）条边。 A．n-l B．n C．n+l D．2n 17. 设无向图的顶点个数为n，则该图最多有（ ）条边。 2 A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n 18. 在一个有向图中,所有顶点的入度之和等于所有弧数和的（ ）倍。 A．1 B. 2 C. 3 D. 4 19. 在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。 A．1/2 B．2 C．1 D．4 20. 下列哪一种图的邻接矩阵是对称矩阵？（ ）【北方交通大学 2001 一、11 （2分）】 A．有向图 B．无向图 C．AOV网 D．AOE网 A01010110021. 从邻接阵矩可以看出，该图共有（ B ）个顶点；如果是有向图该图共有（B ） 条弧；如果是无 向图，则共有（D ）条边。【中科院软件所 1999 六、2（3分）】 ①．A．9 B．3 C．6 D．1 E．以上答案均不正确 ②．A．5 B．4 C．3 D．2 E．以上答案均不正确 ③．A．5 B．4 C．3 D．2 E．以上答案均不正确 22. 无向图G=(V,E),其中：V={a,b,c,d,e,f}, E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。【南京理工大学 2001 一、14 （1.5分）】 A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b 23. 下面哪一方法可以判断出一个有向图是否有环（回路）：【东北大学 2000 4、2（4分）】 A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径 24. 已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}， E={ A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7 C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V7 25. 关键路径是事件结点网络中（ ）。【西安电子科技大学 2001应用 一、4 （2分）】 A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最长回路 D．最短回路 26. 下面关于求关键路径的说法不正确的是（ ）。【南京理工大学 1998 一、12 （2分）】 A．求关键路径是以拓扑排序为基础的 B．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同 C．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差（应该为：活动的最迟开始时间为该活动的弧头所指事件最迟开始时间与该活动的持续时间的差） D．关键活动一定位于关键路径上 二、 判断题 1. 深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 2. 完全二叉树中，若一个结点没有左孩子，则它必是树叶。 3. 树形结构中元素之间存在一个对多个的关系。 4. 将一棵树转成二叉树，根结点没有左子树 5. 当一棵具有n个叶子结点的二叉树的WPL值为最小时，称其树为Huffman树，且其二叉树的形状必是唯一的。 6. 在有向图G中， 8. 树中的结点和图中的顶点就是指数据结构中的数据元素。 9. 在n个结点的无向图中，若边数大于n-1,则该图必是连通图。 10. 有e条边的无向图，在邻接表中有e个结点。 11. 有n个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接矩阵中非零元素之和的一半。 12. 邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。 13. 连通图上各边权值均不相同，则该图的最小生成树是唯一的。 14. 关键活动不按期完成就会影响整个工程的完成时间。 15. 无环有向图才能进行拓扑排序。 16. 关键路径是AOE网中从源点到终点的最长路径。 三、 填空题 1. 一棵深度为K的满二叉树的结点总数为 ，一个深度为K的完全二叉树的结点总数最小为 ，最大为 2. 加上表示指向前驱和 的线索的二叉树称为线索二叉树。 3. 利用树的孩子兄弟表示法存储，可以将一棵树转换为___ ___。 4. 具有n个结点的满二叉树，其叶结点的个数是__ ___。 5. 有一份电文中共使用 6个字符:a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9，试构造一棵哈夫曼树，则其加权路径长度WPL为_ __。 6. 在有n个顶点的有向图中，每个顶点的度最大可达 。 7. 在有向图的邻接矩阵表示中，计算第i个顶点入度的方法是_ ____。 8. 克鲁斯卡尔算法的时间复杂度为_ ,它对__ _____图较为适合;Prim（普里姆）算法的时间复杂度为 ,它对_ ____图较为适合。 四、 综合应用题 1. 有一无向图G，如图所示，请给出该图的： 18 2 1 6 5 23 12 4 8 7 3 5 25 15 7 10 4 6 20 （1） 邻接矩阵； （2） 邻接表(要求表头节点从1开始按升序排列，表节点按升序排列，否则不给分)； （3） 从顶点1出发进行广度优先搜索所得到的顶点序列； （4） 利用普里姆算法构造图G的一棵最小生成树，要求按算法画出构造过程，选择顶点1开始。 2．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF. (1)请画出该二叉树 (2)将该二叉树转换为树或者森林。 3、已知某系统在通讯时，只出现A、B、C、D、E五种字符，它们出现的频率依次为2，4，7，3，8·。 （1）画出该Huffman树 （2）设计Huffman编码。 （3）计算WPL值 因篇幅问题不能全部显示，请点此查看更多更全内容