西北民族大学数据结构题库

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，仅有一个孩子的结点数为30，则总节点数为

2、（ ）。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的结点时，（ ）次比较后查找成功。A. 2B. 3C. 4D. 97. 下列不是

3、算法的特性的是（ ）。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,则栈的不可能输出序列是( )。A. dceab B. abcde C. ed

4、cba 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(n)=f(n-1)+n D. f(n)=n16. 串

5、是一种特殊的线性表，其特殊性体现在( )。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)20. 广义表(a,b),c,d)的表尾是( )。A.

6、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. 29H. 1525. 已知二叉树中有两个孩子的结点数为18，仅有一个孩

7、子的结点数为30，则总节点数为（ ）。E. 48F. 65G. 67H. 77填空题1. 数据结构包括（ ）三个方面。（用英文逗号分隔，即*结构，*结构，*结构，注意按次序填写） 逻辑结构，存储结构，预算结构或逻辑结构，存储结构，操作结构2. 数据结构被形式地定义为一个二元组DS=（D,S）其中D是（1）的有限集合，S是D上关系的有限集合。 数据元素3. 当线性表的元素综述总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应该采用（ ）存储结构4. 对于双向链表，删除一个存在的结点需修改的指针为（ ）个。 25. （ ）是限定仅在表尾进行插入或删除操作的线性表。栈

8、 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. 二维数组Mij的每个元素占4个存储单元，行下表i的范围从0到4，列下表j的范围从0到6，M按列存储时M15元素的起始地址与M按

9、行存储时元素（ ）的起始地址相同。M3510. 将整型数组A1818按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A73的地址是（ ） 110011. 已知完全二叉树的第6层有32个叶子节点，则整个二叉树的节点数最少是（ ）6312. 已知完全二叉树的第7层有14个叶子结点，则整个二叉树的结点数最多时（ ）。22713. 二叉树的第10层至多有（ ）个结点。51214. 深度为4的二叉树至多有（ ）个结点。1515. 将一棵有50个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号16. 二叉树的第9层至多有（ ）个节点。25617.

10、深度为7的二叉树至多有（ ）个结点。12718. 将一棵有81个结点的完全二叉树从跟这一层开始，每一层从左到右以此对结点进行编号，根结点的编号为1，则编号为66的结点的双亲编号为（ ）3319. 设广义表L=（a，（a，b），d，e（i，j），k），则L的深度是（ ） 320.21. 是对客观事物的符号表示，能被计算机处理的符号总称。22. 数据的存储结构通常包括数据的_存储和_存储。23. 数据的逻辑结构可形式地用一个二元组S(D，R)来表示，其中D是_，R是_。24. 所有插入和删除都在表的一端进行的线性表称为 。25. 插入和删除分别在表的两端进行的线性表称为 。26. 栈是一种 受限的

11、线性表。27. 当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为 ，设元素占1个空间容量。28. 串的两种基本存储方式是 和 。29. 串S=”hell o”的长度是_。30. 串S=”worker”的子串数目是_。31. 空串是指数据元素个数为_的串。32. 已知数组A0909的每个元素占5个存储单元，将其按行存储在起始地址为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的深度是 ,表头

12、为 ，表尾是 。36. 空格串是指由_符所组成的字符串。37. 数据结构包括_三个方面。38. 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应该采用_存储结构39. 对于双向链表，删除一个存在的结点需修改的指针为_个。 240. _是限定仅在表尾进行插入或删除操作的线性表。 判断题1. 线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。2. 链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序存储结构中效率高。3. 队列是一种插入与删除操作分别在表的两段进行的线性表，是一种先进后出型结构。4. 队列逻辑上是一个上端

13、和下端既能增加又能减少的线性表。5. 如果两个含有相同的字符，则说他们相等。6. 空串与空格串是相同的。7. 所谓取广义表的表尾就是返回广义表中最后一个元素。8. 由于二叉树中每个结点的度最大为2，所以二叉树就是一种特殊的树。9. 二叉树中的叶子结点就是二叉树中没有左右子树的结点，除了根结点外。10. 二叉树的中序遍历中，任意一个结点均处在其子女结点的后面。11. 森林的先序遍历次序与其转换得到的二叉树的中序遍历次序相同。12. 已知一个森林的先序遍历和中序遍历，一定能构造出该森林。 A13. 有向图用邻接矩阵表示后，顶点i的出度等于第i行中非0且非的元素个数。14. 在一个有向图中，所有顶点

14、的入度之和等于出度之和。15. 所谓平衡二叉树是指左、右子树的深度差的绝对值不大于1的二叉排序树。且左、右子树均为平衡二叉树。16. 所谓平衡二叉树是指左右子树的高度差的绝对值不大于1的二叉排序树。 B17. 数据结构包括数据的逻辑结构和存储结构 。 18. 程序一定是算法。19. 线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。20. 链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序存储结构中效率高。21. 队列是一种插入与删除操作分别在表的两段进行的线性表，是一种先进后出型结构。22. 顺序表中逻辑上相邻的元素，物理上一定邻接。 23. 顺序表中所有结点

15、的类型必须相同。 24. 由于不需预先分配空间，线性链表的结点结构可以不相同。 25. 队列是一种先进后出的线性结构。26. 队列逻辑上是一个下端和上端既能增加又能减少的线性表。 27. 栈是一种先进后出的线性结构。 28. 循环队列通常用指针来实现队列的首尾相接。 29. 串是一种数据对象和操作都特殊的线性表。 30. 矩阵压缩存储的目的是为了节省运算时间。 31. 广义表的节点元素的类型必须相同。 32. 广义表是线性表的一种扩展。 33. 一个广义表的表尾总是一个广义表。 34. 如果两个含有相同的字符，则说他们相等。35. 空串与空格串是相同的。36. 所谓取广义表的表尾就是返回广义表

16、中最后一个元素。应用题1. 设有一个栈，元素进栈的次序为：A，B，C，D，E，用I表示进栈操作，O表示出栈操作，写出下列出栈的操作序列。（1）C，B，A，D，E（2）A，C，B，E，D参考答案：（1）IIIOOOIOIO（2）IOIIOOIIOO2. 在双链表中，删除指针变量p所指结点，请按顺序写出必要的操作步骤。参考答案：p-front-rear=p-rear;p-rear-front=p-front;3. 在双向链表中，要在指针变量q所指结点之后插入一个新结点p，请按顺序写出必要的算法步骤。 (设：P所指结点不是链表的首尾结点，q是与p同类型的指针变量)参考答案：p-front=q;p-r

17、ear=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参考答案: （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）

18、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. 根据下图所示，分别求二叉树的先序遍历次序（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个

19、字符设置哈夫曼编码，按下表对应序号填空，并计算出带权路径长度WPL=（10）（注意构造哈夫曼树时要求左小右大，前小后大，编码时用左0右1编码）字符ABCDEFGHK频率0.030.060.040.050.10.180.220.120.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编码）字符ABCDEF

20、GHK频率4311161223157 编码 00011 11 001 1010 100 01 00010 0000 1011 WPL=27410. 求下图顶点1到其余顶点的最短路径，按要求填表。（注意用顶点大写字母V+序号表示，路径用顶点序列构成，如填写V1V3V5等即可，不用分隔。其他填写方式均不得分）源点终点路径最小值V1V2V1V3V1V4V1V5V1V6V1V7V1V8V1V9V1V1011. 求下图顶点1到其余顶点的最短路径，按要求填表。（注意用顶点大写字母V+序号表示，路径用顶点序列构成，如填写V1V3V5等即可，不用分隔。其他填写方式均不得分）源点终点路径最小值V1V2V1V3V

21、1V4V1V5V1V6V1V7V1V8V1V9V1V1012. 已知图的邻接表存储结构如下图，试求从1顶点出发求深度优先遍历次序（ ）及深度优先遍历生成树（ ）和广度优先遍历次序（ ）以及广度优先遍历生成树（ ）。24312124553312345（注意次序用顶点序号表示，用英文逗号分隔，如填写1,2,3,4,5即可。生成树用序偶表示，如填写等。次序必须按遍历生成次序依次填写。其它填写方式均不得分）13. 已知图的邻接表存储结构如下图，试求从顶点1出发求深度优先遍历次序（ ）及深度优先遍历生成树（ ）和广度优先遍历次序（ ）及广度优先遍历生成树（ ）（注意次序用顶点序号表示，用英文逗号隔开，如

22、填写1,2,3,4,5即可。生成树用序偶表示，如填写等。次序必须按照遍历生成次序依次填写。其它填写方式均不得分） 14. 用迪杰斯特拉算法求下图顶点1到其余各顶点的最短路径，按要求填表。（注意用顶点大写字母V+序号表示，路径用顶点序列构成，如填写V1V3V5等即可，不用分割。其它填写方式均不得分）源点终点路径最小值V1V2V1V3V1V4V1V5V1V6V1V7V1V8V1V9V1V10算法填空1. 下面程序是把两个串s1和s2首尾相连的程序，即：r1=r1+r2typedef structchar vecMAXLEN;/定义合并后串的最大长度int len;/len为串的长度Str;void

23、 ConCatStr(Str *r1, Str *r2) /字符串连接函数int i;coutveclen+r2-len _ (1)_ )cout两个串太长，溢出！;elsefor(i=0;ivec_ (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)slen+r2-len _ (1)_ )cout两个串太长，溢出！;elsefor(i=0;ivec_ (3)_ =r2-veci