天津大学22春“计算机科学与技术”《数据结构》综合作业三辅导答案1

书山有路勤为径，学海无涯苦作舟！ 住在富人区的她天津大学22春“计算机科学与技术”数据结构综合作业三辅导答案一.综合考核(共50题)1.一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是()。A.edcbaB.decbaC.dceabD.abcde参考答案：C2.二叉树是非线性数据结构，所以()。A.顺序存储结构和链式存储结构都能存储B.顺序存储结构和链式存储结构都不能使用C.它不能用顺序存储结构存储D.它不能用链式存储结构存储参考答案：A3.设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为()。A.s-left=p;s-right=p-right;p-right=s;p-right-left=sB.s-left=p;s-right=p-right;p-right-left=s;p-right=sC.p-right=s;s-left=p;p-right-left=s;s-right=p-rightD.p-right=s;p-right-left=s;s-left=p;s-right=p-right参考答案：B4.在以下的叙述中，正确的是()。A.线性表的顺序存储结构适用于频繁插入/删除数据元素的情况B.线性表的顺序存储结构优于链表存储结构C.线性表的链表存储结构适用于频繁插入/删除数据元素的情况D.线性表的链表存储结构优于顺序存储结构参考答案：C5.对于一个有向图，若一个顶点的入度为k1，出度为k2，则对应逆邻接表中该顶点单链表中的结点数为()。A.k2B.k1-k2C.k1+k2D.k1参考答案：D6.设带有头结点的单向循环链表的头指针变量为head，则其判空条件是()。A.head=0B.head-next=headC.head-next=0D.head!=0参考答案：B7.在双向循环链表的p所指结点之后插入s所指结点的操作是()。A.s-left=p;s-right=p-right;p-right=s;p-right-left=sB.s-left=p;s-right=p-right;p-right-left=s;p-right=sC.p-right=s;s-left=p;p-right-left=s;s-right=p-rightD.p-right=s;p-right-left=s;s-left=p;s-right=p-right参考答案：B8.如果只想得到1024个元素组成的序列中第5个最小元素之前的部分排序的序列，用()方法最快。A.起泡排序B.简单选择排序C.快速排序D.堆排序参考答案：D9.任何一个无向连通图的最小生成树()。A.有一棵或多棵B.可能不存在C.只有一棵D.一定有多棵参考答案：A10.栈结构通常采用的两种存储结构是()。A.顺序存储结构和链式存储结构B.链表存储结构和数组C.线性存储结构和非线性存储结构D.散列方式和索引方式参考答案：A11.用链接方式存储的队列，在进行插入运算时()。A.头、尾指针都要修改B.头、尾指针可能都要修改C.仅修改尾指针D.仅修改头指针参考答案：B12.带头结点的单链表head为空的判定条件是()。A.head=NULLB.head-next=headC.head-next=NULLD.head!=NULL参考答案：C13.设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为()。A.3，2，5，8，6B.3，2，5，6，8C.2，3，6，5，8D.2，3，5，8，6参考答案：B14.设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是()。A.P，A，C，S，Q，D，F，X，R，H，M，YB.H，C，Q，P，A，M，S，R，D，F，X，YC.F，H，C，D，P，A，M，Q，R，S，Y，XD.A，D，C，R，F，Q，M，S，Y，P，H，X参考答案：B15.判定一个顺序栈ST(最多元素为m0)为栈满的条件是()。A.top!=m0B.top!=0C.top=m0-1D.top=0参考答案：C16.在一个单链表中，若删除p所指结点的后续结点，则执行()。A.p=p-next;p-next=p-next-nextB.p=p-next-nextC.p-next=p-next-nextD.p-next=p-next参考答案：B17.在一个图中，所有顶点的度数之和等于所有边数的()倍。A.4B.2C.1/2D.1参考答案：B18.设一个顺序有序表A1:14中有14个元素，则采用二分法查找元素A4的过程中比较元素的顺序为()。A.A7，A5，A3，A4B.A7，A3，A5，A4C.A1，A2，A3，A4D.A1，A14，A7，A4参考答案：B19.用某种排序方法对线性表(25，84，21，47，15，27，68，35，20)进行排序时，元素序列的变化情况如下： 25，84，21，47，15，27，68，35，20; 20，15，21，25，47，27，68，35，84; 15，20，21，25，35，27，47，68，84; 15，20，21，25，27，35，47，68，84。则所采用的排序方法是()。A.选择排序B.快速排序C.归并排序D.希尔排序参考答案：B20.树的基本遍历策略可分为先根遍历和后根遍历;二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论()是正确的。A.树的后根遍历序列与其对应的二叉树的后序遍历序列相同B.树的先根遍历序列与其对应的二叉树的先序遍历序列相同C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同D.以上都不对参考答案：B21.在二叉排序树中插入一个关键字值的平均时间复杂度为()。A.O(nlog2n)B.O(n2)C.O(n)D.O(1og2n)参考答案：D22.设无向图G中有n个顶点，则该无向图的最小生成树上有()条边。A.n-1B.nC.2n-1D.2n参考答案：A23.设散列表中有m个存储单元，散列函数H(key)=key%p，则p最好选择()。A.小于等于m的最大素数B.小于等于m的最大奇数C.小于等于m的最大合数D.小于等于m的最大偶数参考答案：A24.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为()。A.O(n2)B.O(n)C.O(1og2n)D.O(1)参考答案：C25.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过()。A.log2n-1B.log2n+1C.log2nD.log2(n+1)参考答案：B26.快速排序方法在()情况下最不利于发挥其长处。A.要排序的数据量太大B.要排序的数据已基本有序C.要排序的数据中含有多个相同值D.要排序的数据个数为奇数参考答案：B27.一个有n个顶点的无向图最多有()条边。A.n(n-1)/2B.n(n-1)C.nD.2n参考答案：A28.设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为()。A.5，3，4，6，1，2B.3，2，5，6，4，1C.3，1，2，5，4，6D.1，5，4，6，2，3参考答案：B29.设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为()。A.N2+N3B.N2-1C.N1+N3D.N1-1参考答案：D30.若有18个元素的有序表存放在一维数组A19中，第一个元素放A1中，现进行二分查找，则查找A3的比较序列的下标依次为()。A.9，5，3B.9，5，2，3C.9，4，2，3D.1，2，3参考答案：C31.对一个满二叉树，m个树叶，n个结点，深度为h，则()。A.n=h+mB.n=2的h次方-1C.m=h-1D.h+m=2n参考答案：B32.设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为()。A.nB.eC.2nD.2e参考答案：D33.下面关于线性表的叙述错误的是()。A.线性表采用顺序存储必须占用一片连续的存储空间B.线性表采用顺序存储便于插入和删除操作的实现C.线性表采用链式存储便于插入和删除操作的实现D.线性表采用链式存储不必占用一片连续的存储空间参考答案：B34.设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为()。A.s-next=p-next;p-next=-sB.q-next=s;s-next=pC.p-next=s;s-next=qD.p-next=s-next;s-next=p参考答案：B35.堆的形状是一棵()。A.满二叉树B.平衡二叉树C.完全二叉树D.二叉排序树参考答案：C36.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的()倍。A.4B.2C.1/2D.1参考答案：D37.设串s1=ABCDEFG，s2=PQRST，函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,len(s2),subs(s1,len(s2),2)的结果串是()。A.BCPQRSTB.BCDEFGC.BCDEFEFD.BCDEF参考答案：C38.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有()个空指针域。A.4mB.2m-1C.2m+1D.2m参考答案：D39.二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A74的起始地址为()。A.SA+225B.SA+222C.SA+144D.SA+141参考答案：B40.设有一个10阶的下三角矩阵A(包括对角线)，按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A54地址与A00的地址之差为()。A.55B.28C.19D.10参考答案：C41.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为()个。A.47B.17C.16D.15参考答案：C42.设某散列表的长度为100，散列函数H(k)=k% P，则P通常情况下最好选择()。A.99B.97C.93D.91参考答案：B43.队列是一种()的线性表。A.只能插入B.只能删除C.先进后出D.先进先出参考答案：D44.判定一个顺序栈ST(最多元素为m0)为空的条件是()。A.top=m0-1B.top=0C.top!=m0D.top!=0参考答案：B45.下列四种排序中()的空间复杂度最大。A.插入排序B.归并排序C.堆排序D.冒泡排序参考答案：B46.从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行()。(不带空的头结点)A.x=HS-data;HS=HS-nextB.x=HS-dataC.x=HS;HS=HS-nextD.HS=HS-next;x=HS-data参考答案：A47.二叉树的第k层的结点数最多为()。A.B.C.2K-1D.2K+1参考答案：B48.二叉树中第i(i1)层上的结点数最多有()个。A.2i-1B.2的i-1次方C.2的i次方D.2i参考答案：B49.具有五层结点的二叉平衡树至少有()个结点。A.17B.15C.12D.10参考答案：C50.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为()。A.n/2B.nC.(n-1)/2D.(n+1)/2参考答案：D