1、1北京邮电大学远程教育计算机科学与技术专业三年级（高起本）数据结构期中作业一、单项选择题1、栈结构通常采用的两种存储结构是 A 。A、线性存储结构和链表存储结构；B、散列方式和索引方式；C、链表存储结构和数组； D、线性存储结构和非线性存储结构。2、判定一个栈 ST（最多元素为 m0）为栈满的条件是 D 。A、STtop!=0； B、STtop=0；C、STtop!=m0-1； D、STtop=m0-13、判定一个队列 Qu（最多元素为 m0）为空的条件是 D 。A、Qurear-Qufront=m0； B、Qurear-Qufront-1=m0；C、Qufront=Qurear； D、Quf
2、ront=Qurear+1。4、非空的循环单链表 head 的尾结点（由 P 所指向）满足 C 。A、Pnext=NULL； B、P=NULL；C、Pnext=head； D、P=head5、从一个栈顶指针为 HS 的链栈中删除一个结点时，用 x 保存被删结点的值，则执行 D 。A、x=HS；HS=HSnext； B、x=HSdata；C、HS=HSnext； x=HSdata ； D、x=HSdata； HS=HSnext。26、常对数组进行的两种基本操作是 C 。A、建立与删除； B、索引和修改；C、查找和修改； D、查找和索引。7、广义表（a ）,a ）的表头是 D ，表尾是 A 。A、
3、a； B、b； C、(a)； D、(a)。8、二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法 A 。A、正确； B、错误。9、计算递归函数如不用递归过程通常借助的数据结构是 D 。A、线性表； B、双向队列； C、树； D、栈。10、就平均性能而言，最快的排序方法是 C 。A、冒泡排序； B、希尔排序； C、快速排序； D、插入排序。11、若串 S=goodstudents,其子串的数目是 D 。A、12； B、13； C、78； D、79。12、对线性表进行折半查找最方便的存储结构是 A 。A、顺序表； B、有序的顺序表； C、链表； D、有序的链表。313、深度为 5
4、 的二叉树其结点数最多为 C 。A、16； B、30； C、31； D、32。14、如果 T2 是由有序树 T 转换来的二叉树，则 T 中结点的后序排列是 T2 结点的 。A、先序排列； B、中序排列； C、后序排列； D、层序排列。15、在一棵度为 3 的树中，度为 3 的结点个数为 2，度为 2 的结点个数为 1，则度为 0 的结点个数为 C 。A、4； B、5； C、6； D、7。16、如下图所示二叉树的中序遍历序列是 B 。A、abcdgef； B、dfebagc； C、dbaefcg； D、defbagc。acbfegd417 采用邻接表存储的图的广度优先遍历算法类似于二叉树的 D
5、。A、先序遍历； B、中序遍历； C、后序遍历； D、按层遍历。18、下面程序段的时间复杂性的量级为 D 。for(i=1;in; i+)for(j=1;jm; j+)cij=0;for(k=1;kw;k+)cij+=aik*bkjA、O(i*j*k)； B、O(n*m*k)； C、O(n*j*k)； D、O(n*m*w)。19、在一个长度为 n 的线性表中，删除值为 x 的元素时需要比较元素和移动元素的总次数为 C 。A、 （n+1）/2； B、n/2； C、n； D、n+1。20、利用 3，6，8，12，5，7 这六个值作为叶子结点的权，生成一棵哈夫曼树，该树的深度为 B 。A、3； B、
6、4； C、5； D、621、一棵二叉树的广义表表示为 a(b(c,d),e(,f(g),则得到的层次遍历序列为 D 。5A、a,b,c,d,e,f,g； B、c,b,d,a,e,g,f； C、c,d,b,g,f,e,a； D、a,b,e,c,d,f,g。22、对于一个无向图，下面 A 的说法是正确的。A、每个顶点的入度等于出度； B、每个顶点的度等于其入度与出度之和； C、每个顶点的入度为 O； D、每个顶点的出度为 O。23、若一个图的边集为,则从顶点 1开始对该图进行深度优先搜索，得到的顶点序列可能为 C 。A、1，2，5，4，3； B、1，2，3，4，5； C、1，2，5，3，4； D、
7、1，4，3，2，5。24、若一个图的边集为（A，B） ， （A，C） ， （B，D） ， （C，F） ， （D，E） ，（D，F），则从顶点 A 开始对该图进行广度优先搜索，得到的顶点序列可能是 A 。A、A，B，C，D，E，F； B、A，B，C，F，D，E； C、A，B，D，C，E，F； D、A，C，B，F，D，E。25、已知一个有向图的边集为,则由该图产生的一种可能的拓扑序列为 B 。A、a,b,c,d,e； B、a,b,d,e,b； C、a,c,b,e,d； D、a,c,d,b,e。26、若一个图中包含有 k 个连通分量，若按照深度优先搜索的方法访问所有顶点，则必须调用 C 次深度优先搜
8、索遍历的算法。6A、k； B、1； C、k-1； D、k+127、在一个具有 n 个顶点的有向图中，若所有顶点的出度数之和为 S，则所有顶点的度数之和 D 。A、S； B、S-1； C、S+1； D、2S28、对长度为 3 的顺序表进行查找，若查找第一个元素的概率为 1/2，查找第二个元素的概率为 1/3，查找第三个元素的概率为 1/6，则查找任一元素的平均查找长度为 A 。A、5/3； B、2； C、7/3； D、4/3。29、若要对 1000 个元素排序，要求既快又节省存储空间，则最好采用 D 方法。A、直接插入排序； B、归并排序； C、堆排序； D、快速排序。30、假定对元素序列（7，
9、3，5，9，1，12）进行堆排序，并且采用小根堆，则由初始数据构成的初始堆为 B 。A、1，3，5，7，9，12； B、1，3，5，9，7，12； C、1，5，3，7，9，12； D、1，5，3，9，12，7。二、填空题1、数据的逻辑结构被分为 ， ， 和 四种。2、数据的存储结构被分为 ， ， 和 四种。3、从一维数组 an中顺序查找出一个最大值元素的平均时间复杂度为 ，读取一个二维数组 bmn中任一元素的时间复杂度为 。74、线性表的链接存储比顺序存储最有利于进行 操作。5、线性表的两种存储结构分别为 和 。6、对于一个长度为 n 的顺序存储的线性表，在表头插入元素的时间复杂性为 ，在表尾
10、插入元素的时间复杂性为 。7、在以 HL 为表头指针的带表头附加结点的单链表和循环单链表中，链表为空的条件分别为 和 。8、在一个带头结点的循环单链表中，在表头插入或删除与在其他位置插入或删除，其操作过程是否相同？ 。9、在一个用一维数组 aN表示的顺序栈中，该栈所含元素的个数最少为个，最多为 个。10、一个顺序栈存储于一维数组 a0M-1中，栈顶指针用 top 表示，当栈顶指针等于 时，则为空栈；栈顶指针等于 时，则为满栈。11、设元素 a,b,c,d 依次进栈，若要在输出端得到序列 cbda，则应进行的操作序列为 push（s,a）,push(s,b),push(s,c), , , ,po
11、p(s),pop(s)。12、有一个 88 的下三角矩阵 A，若采用行序为主序进行顺序存储于一维数组a1N中，则 N 的值为 。13、假定一棵树的广义表表示为 A（B（C，D（E，F，G） ，H（I，J） ） ） ，则树中所含的结点数为 个，树的深度为 ,树的度为 。14、在一棵二叉树中，假定双分支结点数为 5 个，单分支结点数为 6 个，则叶子结点数为 个。15、假定一棵二叉树广义表表示为 a(b(c),d(e,f),则对它进行的先序遍历结果为 ,中序遍历结果为 ,后序遍历结果为 ,按层遍历结果为 。816、若由 3，6，8，12，10 作为叶子结点的值生成一棵哈夫曼树，则该树的高度为 ,带
12、权路径长度为 。17、在一个连通图中存在着 个连通分量。18、图中的一条路径长度为 k，该路径所含的顶点数为 。19、若一个连通图中每个边上的权值均不同，则得到的最小生成树是 的。20、以二分查找方法在一个查找表上进行查找时，该查找表必须组织成 存储的 表.三、编写一个函数将一个向量 A（有 n 个元素且任何元素均不为 0）分拆成两个向量，使 A 中大于 0 的元素存放在 B 中，小于 0 的元素存放在 C 中。四、有一个单链表 L（至少有 1 个结点） ，其头结点指针为 head，编写一个函数将 L 逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。五、若 h
13、是采用单链表存储的串，编写一个函数将其中的所有 c 替换成 s 字符。六、有如下递归函数：int dunno(int m)int value;if (m=0) value=3;else value=dunno(m-1)+5;9return(value);执行语句 printf(“%dn”,dunno(3)；的结果是： 七、由下图所示的二叉树，回答下列问题：（1）其中序遍历序列为 。（2）其前序遍历序列为 。（3）其后序遍历序列为 。（4）该二叉树的中序线索二叉树为 。（5）该二叉树对应的森林为 。abgihefcd10八、使用普里姆算法构造出图 G 的一棵最小生成树。6 1 55 53 6 4 26图 G12 3654
