1、选择题1. 在数据结构中，逻辑上可以把数据结构分为（）A. 动态结构和静态结构B. 紧凑结构和非紧凑结构C. 线性结构和非线性结构D. 内部结构和外部结构2. 在一个单链表中，若删除 p 所指结点的后继结点，则执行（ ） 。A. p-next=p-next-nextB. p=p-next,p-next=p-next-nextC. p-next=p-nextD. p=p-next-next3. 设高度为 15 的二叉树上只有度为 0 和 1 的结点，则此类二叉树中所包含的结点数至少为（ ） 。A. 30B. 31C. 29D. 154. 已知二叉树中有两个孩子的结点数为 18，仅有一个孩子的结点
2、数为 30，则总节点数为（ ） 。A. 48B. 65C. 67D. 775. 无向图 G=（V,E） ，其中：V=(a,b),(a,e),(a,c),(b,e),(e,f),(f,d),(e,d),在下面的 5 个序列中，符合深度优先遍历的序列有多少？（ ）（1 ） a e b d f c （2） a c f d e b （3） a e d f c b（4）a e f d c b （5）a e f d b cA. 5 个B. 4 个C. 3 个D. 2 个6. 有一个有序表1,3,5,7,8,10,15,17,19,30,41,50,70，当二分查找值为 19 的结点时， （ ）次比较后查找
3、成功。A. 2B. 3C. 4D. 97. 下列不是算法的特性的是（ ）。A. 有穷性 B. 确定性C. 可能性 D. 输入和输出特性8. 线性表若采用链式结构时，要求内存中可用存储单元的地址( )。A. 一定是不连续的 B. 连续不连续都可以C. 必须是连续的 D. 部分地址必须是连续的9. 在一个单链表中，若删除p所指结点的后续结点，则执行( )。A. p-next=p-next-next; B. p=p-next;p-next=p-next-next;C. p-next=p-next; D. p=p-next-next10. 一个栈的入栈序列是a,b,c,d,e,则栈的不可能输出序列是(
4、 )。A. dceab B. abcde C. edcba D. decba11. 限定线性表有（ ）。A.栈 B.队列 C.树 D.A和B12. 进行入队运算时，必须先判断队列是否（ ）。A. 空 B. 满 C. 下溢 D. 上溢13. 进行出栈运算时，必须先判断栈是否（ ）。A. 空 B. 满 C. 下溢 D. 上溢14. 判定一个栈ST(栈的存储空间大小为M)为空的条件是( )。A. ST-top!=0 B. ST-top=0C. ST-top!=M D. ST-top=M15. 递归函数f(n)=f(n-1)+n(n1)的递归体是( )。A. f(1)=0 B. f(0)=1C. f(
5、n)=f(n-1)+n D. f(n)=n16. 串是一种特殊的线性表，其特殊性体现在( )。A. 数据元素是一个字符 B. 数据元素可以是多个字符C. 可以顺序存储 D. 可以链式存储 17. 若串S=”software” ,则其子串的数目是( )。A. 8 B. 7 C. 6 D. 918. 两个字符串相等的充分必要条件是（ ）。A 、两个串的长度相等 B 、两个串包含的字符相等C 、两个串的长度相等，并且两个串包含的字符相等。 D、 两个串的长度相等，并且对应位置上的字符相等。19. 已知广义表L=(a,(b,c),其表头是( )。A. a B. b C. (a,b) D. (c,d)2
6、0. 广义表(a,b),c,d)的表尾是( )。A. a B. b C. (a,b) D. (c,d)21. 树最适合用来表示( )。A 、有序数据元素 B 、无序数据元素C 、元素之间具有分支层次关系的数据 D、 元素之间无联系的数据22. 在树型结构中，每一个结点都可以有（ ）个孩子结点。A. 2 B. 1 C. 0 D. 任意多23. 关键路径是时间节点网络中（ ）。A. 从源点到汇点的最长路径 B. 从源点到汇点的最短路径C. 最长回路 D. 最短回路24. 设高度为 15 的二叉树上只有度为 0 和 1 的结点，则此类二叉树中所包含的结点数至少为（ ） 。E. 30F. 31G. 2
7、9H. 1525. 已知二叉树中有两个孩子的结点数为 18，仅有一个孩子的结点数为 30，则总节点数为（ ） 。E. 48F. 65G. 67H. 77填空题1. 数据结构包括（ ）三个方面。 （用英文逗号分隔，即 *结构，*结构，* 结构，注意按次序填写） 逻辑结构，存储结构，预算结构或逻辑结构，存储结构，操作结构2. 数据结构被形式地定义为一个二元组 DS=（D,S ）其中 D 是（1 ）的有限集合，S 是 D上关系的有限集合。 数据元素3. 当线性表的元素综述总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应该采用（ ）存储结构4. 对于双向链表，删除一个
8、存在的结点需修改的指针为（ ）个。 25. （ ）是限定仅在表尾进行插入或删除操作的线性表。栈 6. 设有一个栈，栈顶指针为 1000H（十六进制） ，现有输入序列为 1,2,3,4,5 经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH 之后，栈顶指针是（ ）H。设栈为顺序栈，每个元素占 4 个字节。 100C7. 设串 s1=”ABCDEFG”,s2=”PQRST”，则 Strcat(substr(s1,2,strlen(s2),substr(s1,strlen(s2),2)结果是（ ） 。BCDEFEF8. 空格串是指由（ ）字符所组成的字符串。 空格9. 二维数组 M
9、ij的每个元素占 4 个存储单元，行下表 i 的范围从 0 到 4，列下表 j 的范围从 0 到 6，M 按列存储时 M15元素的起始地址与 M 按行存储时元素（ ）的起始地址相同。M3510. 将整型数组 A1818按行优先次序存储在起始地址为 1000 的连续的内存单元中，则元素 A73的地址是（ ） 110011. 已知完全二叉树的第 6 层有 32 个叶子节点，则整个二叉树的节点数最少是（ ）6312. 已知完全二叉树的第 7 层有 14 个叶子结点，则整个二叉树的结点数最多时（ ） 。22713. 二叉树的第 10 层至多有（ ）个结点。51214. 深度为 4 的二叉树至多有（ ）
10、个结点。1515. 将一棵有 50 个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为 1，则编号16. 二叉树的第 9 层至多有（ ）个节点。25617. 深度为 7 的二叉树至多有（ ）个结点。12718. 将一棵有 81 个结点的完全二叉树从跟这一层开始，每一层从左到右以此对结点进行编号，根结点的编号为 1，则编号为 66 的结点的双亲编号为（ ）3319. 设广义表 L=（a， （a ，b） ，d，e（i，j） ，k ） ） ，则 L 的深度是（ ） 320.21. 是对客观事物的符号表示，能被计算机处理的符号总称。22. 数据的存储结构通常包括数据的
11、_存储和_存储。23. 数据的逻辑结构可形式地用一个二元组 S(D，R) 来表示，其中 D 是_，R 是_。24. 所有插入和删除都在表的一端进行的线性表称为 。25. 插入和删除分别在表的两端进行的线性表称为 。26. 栈是一种 受限的线性表。27. 当栈中元素为 n 个，作进栈运算时发生上溢，则说明该栈的最大容量为 ，设元素占 1 个空间容量。28. 串的两种基本存储方式是 和 。29. 串 S=”hell o”的长度是_。30. 串 S=”worker”的子串数目是 _。31. 空串是指数据元素个数为_的串。32. 已知数组 A0909的每个元素占 5 个存储单元，将其按行存储在起始地址
12、为 1000的连续的内存单元中，则元素 A68的地址为 33. 广义表(a,(a,b),d,e,(i,j),k)的长度是 34. 设广义表 L=（a） ） ） ） ，则 L 的长度为_，深度为 .35. 设广义表 L=（a， （a ，b） ，d，e,（i， （j ） ） ，k） ） ，则 L 的深度是 ,表头为 ，表尾是 。36. 空格串是指由_符所组成的字符串。37. 数据结构包括_三个方面。38. 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应该采用_存储结构39. 对于双向链表，删除一个存在的结点需修改的指针为_个。 240. _是限定仅
13、在表尾进行插入或删除操作的线性表。 判断题1. 线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。2. 链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序存储结构中效率高。3. 队列是一种插入与删除操作分别在表的两段进行的线性表，是一种先进后出型结构。4. 队列逻辑上是一个上端和下端既能增加又能减少的线性表。5. 如果两个含有相同的字符，则说他们相等。6. 空串与空格串是相同的。7. 所谓取广义表的表尾就是返回广义表中最后一个元素。8. 由于二叉树中每个结点的度最大为 2，所以二叉树就是一种特殊的树。9. 二叉树中的叶子结点就是二叉树中没有左右子树的结点，除了根
14、结点外。10. 二叉树的中序遍历中，任意一个结点均处在其子女结点的后面。11. 森林的先序遍历次序与其转换得到的二叉树的中序遍历次序相同。12. 已知一个森林的先序遍历和中序遍历，一定能构造出该森林。 A13. 有向图用邻接矩阵表示后，顶点 i 的出度等于第 i 行中非 0 且非的元素个数。14. 在一个有向图中，所有顶点的入度之和等于出度之和。15. 所谓平衡二叉树是指左、右子树的深度差的绝对值不大于 1 的二叉排序树。且左、右子树均为平衡二叉树。16. 所谓平衡二叉树是指左右子树的高度差的绝对值不大于 1 的二叉排序树。 B17. 数据结构包括数据的逻辑结构和存储结构 。 18. 程序一定
15、是算法。19. 线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。20. 链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序存储结构中效率高。21. 队列是一种插入与删除操作分别在表的两段进行的线性表，是一种先进后出型结构。22. 顺序表中逻辑上相邻的元素，物理上一定邻接。 23. 顺序表中所有结点的类型必须相同。 24. 由于不需预先分配空间，线性链表的结点结构可以不相同。 25. 队列是一种先进后出的线性结构。26. 队列逻辑上是一个下端和上端既能增加又能减少的线性表。 27. 栈是一种先进后出的线性结构。 28. 循环队列通常用指针来实现队列的首尾相接。
16、29. 串是一种数据对象和操作都特殊的线性表。 30. 矩阵压缩存储的目的是为了节省运算时间。 31. 广义表的节点元素的类型必须相同。 32. 广义表是线性表的一种扩展。 33. 一个广义表的表尾总是一个广义表。 34. 如果两个含有相同的字符，则说他们相等。35. 空串与空格串是相同的。36. 所谓取广义表的表尾就是返回广义表中最后一个元素。应用题1. 设有一个栈，元素进栈的次序为：A ，B，C，D ，E，用 I 表示进栈操作，O 表示出栈操作，写出下列出栈的操作序列。（1）C， B，A，D，E（2）A，C，B，E，D参考答案：（1）IIIOOOIOIO（2）IOIIOOIIOO2. 在双
17、链表中，删除指针变量 p 所指结点，请按顺序写出必要的操作步骤。参考答案：p-front-rear=p-rear;p-rear-front=p-front;3. 在双向链表中，要在指针变量 q 所指结点之后插入一个新结点 p，请按顺序写出必要的算法步骤。(设：P 所指结点不是链表的首尾结点，q 是与 p 同类型的指针变量)参考答案：p-front=q;p-rear=q-rear;q-rear-front=p;q-rear=p;4. 求后缀表达式。（1） ABC/D（2） -A+B*C+D/E（3） A*(B+C)*D-E（4） (A+B)*C-E/(F+G/H)-D（5） 8/(5+2)-6参
18、考答案: （1 ） A B C D / （2 ） A B C * + D E / +（3 ） A B C + * D * E -（4 ） A B + C * E F G H / + / - D -（5 ） 8 5 2 + / 6 -5. 一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来，填空构造该二叉树。 （注意用大写字符按位置填写，不要加其他符号）先序：A（1）CD（2）F（3 ） H Z（4 ）K中序：（5）B E D F A（6）J K Z G后序：C（7 ）F（8）B（9）J Z H G（10）B E G J C H E D K A6. 根据下图所示，分别求二叉树的先序
19、遍历次序（1） ，中序遍历次序（ 2） ，后序遍历次序（3） 。 （注意次序结点间不要加空格或标点符号，例 ABCDE 即可）7.参考答案： 先序：ABDCGKHTY 中序：BCGDAHYTK 后序：GCDBYTHKA8. 某通信系统中只可能有 A、B、C、D 、E、F、G 、H、K 9 种字符，其出现的概率分别为0.03,0.06，0.04,0.05,0.1,0.18,0.22,0.12,0.2，试为这 9 个字符设置哈夫曼编码，按下表对应序号填空，并计算出带权路径长度 WPL=（10） （注意构造哈夫曼树时要求左小右大，前小后大，编码时用左 0 右 1 编码）字符 A B C D E F
20、G H K频率 0.03 0.06 0.04 0.05 0.1 0.18 0.22 0.12 0.2编码11000 1001 11001 1000 1101 111 01 101 00 WPL=2.939. 通信电文由 A、B 、C、D 、E、F、G 、H、K 9 种字符组成，其出现的概率如下表所示，试为这 9 个字符设置哈夫曼编码，按下表对应序号填空，并计算出带权路径长度WPL=（10） （注意构造哈夫曼树时要求左小右大，前小后大，编码时用左 0 右 1 编码）字符 A B C D E F G H K频率 4 31 11 6 12 23 1 5 7编码00011 11 001 1010 10
21、0 01 00010 0000 1011 WPL=27410. 求下图顶点 1 到其余顶点的最短路径，按要求填表。 （注意用顶点大写字母 V+序号表示，路径用顶点序列构成，如填写 V1V3V5 等即可，不用分隔。其他填写方式均不得分）源点 终点 路径 最小值V1 V2V1 V3V1 V4V1 V5V1 V6V1 V7V1 V8V1 V9V1 V1011. 求下图顶点 1 到其余顶点的最短路径，按要求填表。 （注意用顶点大写字母 V+序号表示，路径用顶点序列构成，如填写 V1V3V5 等即可，不用分隔。其他填写方式均不得分）源点 终点 路径 最小值V1 V2V1 V3V1 V4V1 V5V1 V
22、6V1 V7V1 V8V1 V9V1 V1012. 已知图的邻接表存储结构如下图，试求从 1 顶点出发求深度优先遍历次序（ ）及深度优先遍历生成树（ ）和广度优先遍历次序（ ）以及广度优先遍历生成树（ ） 。12345（注意次序用顶点序号表示，用英文逗号分隔，如填写 1,2,3,4,5 即可。生成树用序偶表示，如填写 等。次序必须按遍历生成次序依次填写。其它填写方式均不得分）13. 已知图的邻接表存储结构如下图，试求从顶点 1 出发求深度优先遍历次序（ ）及深度优先遍历生成树（ ）和广度优先遍历次序（ ）及广度优先遍历生成树（ ）（注意次序用顶点序号表示，用英文逗号隔开，如填写 1,2,3,4
23、,5 即可。生成树用序偶表示，如填写 等。次序必须按照遍历生成次序依次填写。其它填写方式均不得分）14. 用迪杰斯特拉算法求下图顶点 1 到其余各顶点的最短路径，按要求填表。 （注意用顶点大写字母 V+序号表示，路径用顶点序列构成，如填写 V1V3V5 等即可，不用分割。其它填写方式均不得分）源点 终点 路径 最小值V1 V2V1 V3V1 V4V1 V5V1 V6V1 V7V1 V8V1 V9V1 V10算法填空1. 下面程序是把两个串 s1 和 s2 首尾相连的程序，即： r1=r1+r22431212 45533typedef structchar vecMAXLEN;/定义合并后串的最
24、大长度int len;/len 为串的长度Str;void ConCatStr(Str *r1, Str *r2) /字符串连接函数int i;coutveclen+r2-len _ (1)_ )coutvec_ (3)_ =r2-veci;r1-vecr1-len+i= (4) ; /添上字符串结束标志r1-len= _(5) ;/修改新串长度MAXLEN,r2-len,r1-len+i,0,r1-len+r2-len2. 下列算法的功能是递归方法实现快速排序。void Quick_Sort(DataType R,int s,int t)/对顺序表 RsRt作快速排序if (_(1)_) i=Partition(R,s,t); /算法 Partition(R,s,t)功能为将表 RsRt一分为二，返回值为分界点Quick_Sort(R,s,_(2)_); Quick_Sort(R,i+1,_(3)_); void Quick(DataType R,int n)Quick_Sort(R,1,n);(1)st (2)i-1 (3)t1. 下面程序是把两个串 r1 和 r2 首尾相连的程序，即：r1=r1+r2，阅读程序并填空。typedef struct char vecMAXLEN; /定义串的最大长度int len;/len 为串的长度Str;
