天津大学23春“计算机科学与技术”《数据结构》考试高频考点参考题库含答案

长风破浪会有时，直挂云帆济沧海。天津大学23春“计算机科学与技术”《数据结构》考试高频考点参考题库带答案（图片大小可自由调整）第I卷一.综合考核(共15题)1.设有一个10阶的下三角矩阵A(包括对角线)，按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为()。A.55B.28C.19D.102.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为()。A.O(n2)B.O(n)C.O(1og2n)D.O(1)3.二叉树的第k层的结点数最多为()。A.B.C.2K-1D.2K+14.设串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.BCDEF5.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过()。A.log2n-1B.log2n+1C.log2nD.log2(n+1)6.快速排序方法在()情况下最不利于发挥其长处。A.要排序的数据量太大B.要排序的数据已基本有序C.要排序的数据中含有多个相同值D.要排序的数据个数为奇数7.对一个满二叉树，m个树叶，n个结点，深度为h，则()。A.n=h+mB.n=2的h次方-1C.m=h-1D.h+m=2n8.设一组初始记录关键字序列为(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，X9.设顺序表的长度为n，则顺序查找的平均比较次数为()。A.n/2B.nC.(n-1)/2D.(n+1)/210.设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={，，，}，则数据结构A是()。A.集合B.线性结构C.树型结构D.图型结构11.下列四种排序中()的空间复杂度最大。A.插入排序B.归并排序C.堆排序D.冒泡排序12.设指针变量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->right13.如果只想得到1024个元素组成的序列中第5个最小元素之前的部分排序的序列，用()方法最快。A.起泡排序B.简单选择排序C.快速排序D.堆排序14.在一个单链表中，若删除p所指结点的后续结点，则执行()。A.p=p->next;p->next=p->next->nextB.p=p->next->nextC.p->next=p->next->nextD.p->next=p->next15.在一非空二叉树的中序遍历序列中，根结点的右边()。A.只有左子树上的部分结点B.只有左子树上的所有结点C.只有右子树上的部分结点D.只有右子树上的所有结点第II卷一.综合考核(共15题)1.判定一个顺序栈ST(最多元素为m0)为栈满的条件是()。A.top!=m0B.top!=0C.top==m0-1D.top==02.从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行()。(不带空的头结点)A.x=HS->data;HS=HS->nextB.x=HS->dataC.x=HS;HS=HS->nextD.HS=HS->next;x=HS->data3.在一个图中，所有顶点的度数之和等于所有边数的()倍。A.4B.2C.1/2D.14.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A[3]的比较序列的下标依次为()。A.9，5，3B.9，5，2，3C.9，4，2，3D.1，2，35.有8个结点的无向图最多有()条边。A.56B.28C.14D.1126.二叉排序树中左子树上所有结点的值均()根结点的值。A.>B.=C.D.!=7.线性表若采用链式存储结构时，要求内存中可用存储单元的地址()。A.部分地址必须是连续的B.连续或不连续都可以C.必须是连续的D.一定是不连续的8.判定一个顺序栈ST(最多元素为m0)为空的条件是()。A.top==m0-1B.top==0C.top!=m0D.top!=09.一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为()。A.40，38，46，84，56，79B.40，38，46，79，56，84C.40，38，46，56，79，84D.38，40，46，56，79，8410.树最适合用来表示()。A.有序数据元素B.无序数据元素C.元素之间无联系的数据D.元素之间具有分支层次关系的数据11.把一棵树转换为二叉树后，这棵二叉树的形态是()。A.有多种，但根结点都没有左孩子B.有多种，但根结点都没有右孩子C.有多种D.唯一的12.设无向图G中有n个顶点，则该无向图的最小生成树上有()条边。A.n-1B.nC.2n-1D.2n13.按照二叉树的定义，具有3个不同数据结点的不同的二叉树有()种。A.6B.5C.32D.3014.任何一个无向连通图的最小生成树()。A.有一棵或多棵B.可能不存在C.只有一棵D.一定有多棵15.在以下的叙述中，正确的是()。A.线性表的顺序存储结构适用于频繁插入/删除数据元素的情况B.线性表的顺序存储结构优于链表存储结构C.线性表的链表存储结构适用于频繁插入/删除数据元素的情况D.线性表的链表存储结构优于顺序存储结构第III卷一.综合考核(共15题)1.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为()。A.n/2B.nC.(n-1)/2D.(n+1)/22.设某散列表的长度为100，散列函数H(k)=k%P，则P通常情况下最好选择()。A.99B.97C.93D.913.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为()个。A.47B.17C.16D.154.具有五层结点的二叉平衡树至少有()个结点。A.17B.15C.12D.105.用链接方式存储的队列，在进行插入运算时()。A.头、尾指针都要修改B.头、尾指针可能都要修改C.仅修改尾指针D.仅修改头指针6.深度为5的二叉树至多有()个结点。A.32B.31C.16D.107.队列是一种()的线性表。A.只能插入B.只能删除C.先进后出D.先进先出8.用某种排序方法对线性表(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.希尔排序9.设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为()。A.N2+N3B.N2-1C.N1+N3D.N1-110.设散列表中有m个存储单元，散列函数H(key)=key%p，则p最好选择()。A.小于等于m的最大素数B.小于等于m的最大奇数C.小于等于m的最大合数D.小于等于m的最大偶数11.有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为()。A.43/12B.39/12C.37/12D.35/1212.设一棵二叉树的深度为k，则该二叉树中最多有()个结点。A.2k-1B.C.D.13.以下叙述中正确的是()。A.空串就是空白串B.串的长度必须大于零C.串是一种特殊的线性表D.串中无素只能是字母14.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是()。A.gdbehfcaB.gdbecfhaC.bdgcefhaD.bdgaechf15.设一个顺序有序表A[1:14]中有14个元素，则采用二分法查找元素A[4]的过程中比较元素的顺序为()。A.A[7]，A[5]，A[3]，A[4]B.A[7]，A[3]，A[5]，A[4]C.A[1]，A[2]，A[3]，A[4]D.A[1]，A[14]，A[7]，A[4]第I卷参考答案一.综合考核1.参考答案：C2.参考答案：C3.参考答案：B4.参考答案：C5.参考答案：B6.参考答案：B7.参考答案：B8.参考答案：B9.参考答案：D10.参考答案：D11.参考答案：B12.参考答案：B13.参考答案：D14.参考答案：B15.参考答案：D第II卷参考答案一.综合考核1.参考答案：C2.参考答案：A3.参考答案：B4.参考答案：C5.参考答案：B6.参考