华东理工大学数据结构(新)作业及期末复习题.docx

一、判断（共计40分，每题2.5分）1、线性表中的所有元素都有一个前驱元素和后继元素。（）A.正确B.错误参考答案：【B】2、入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。（）A.正确B.错误参考答案：【A】3、不管线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间 复杂度均为O（n）。（）A.正确B.错误参考答案：【A】4、假设一个叶子结点是某二叉树的中序遍历序列的最后一个结点，那么它必是该二 叉树的先序遍历序列中的最后一个结点。（）A.正确B错误参考答案：【A】5、如果某个有向图的邻接表中第i条单链表为空，那么第i个顶点的出度为零。（）A.正确B.错误参考答案：【A】6、图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点 是否被访问过。（）A.正确B.错误参考答案：【A】7、不管是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情 况。（）A.正确B.错误参考答案：【A】8、哈夫曼树中没有度数为1的结点。（）A.正确B.错误参考答案：【A】9、冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（）A.正确B.错误参考答案：【A】10、调用一次深度优先遍历可以访问到图中的所有顶点。（）A.正确参考答案：【。31、()二叉排序树可以得到一个从小到大的有序序列。A.先序遍历B.中序遍历C.后序遍历D.层次遍历参考答案：【B】32、在二叉排序树中插入一个关键字值的平均时间复杂度为()oA. 0(n)O(log2n)B. O(nlog2n)0(n2)参考答案：【B】33、假设要唯一地确定一棵二叉树，只需知道该二叉树的A.前序序列B.中序序列C.前序和后序序列D.中序和后序序列参考答案：【D】34、栈和队列的共同特点是()0A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点参考答案：【A】35、一个队列的入队序列是1, 2, 3, 4,那么队列的输出序列是A. 1, 2, 3, 4B.4, 3, 2, 1C. 1, 4, 3, 23, 2, 4, 1参考答案：【A】36、设某哈夫曼树中有199个结点，那么该哈夫曼树中有()个叶子结点。A. 99100B. 101102参考答案：【B】37、设输入序列是1、2、3、n,经过栈的作用后输出序列的第一个元素 是n,那么输出序列中第i个输出元素是()oA. n-in-l-iB. n+l-iD.不能确定参考答案：【C】38、设一棵完全二叉树中有65个结点，那么该完全二叉树的深度为（）oA. 87B. 65参考答案：【B】39、二叉排序树中左子树上所有结点的值均（）根结点的值。A. C.=D. !=参考答案：【A】40、队列是一种（）的线性表。A.先进先出B.先进后出C.只能插入D.只能删除参考答案：【A】一、判断（共计40分，每题2.5分）1、线性表中的所有元素都有一个前驱元素和后继元素。（）A.正确B.错误参考答案：【B】2、调用一次深度优先遍历可以访问到图中的所有顶点。（）A.正确B.错误参考答案：【B】3、哈夫曼树中没有度数为1的结点。（）A.正确B.错误参考答案：【A】4、如果某个有向图的邻接表中第i条单链表为空，那么第i个顶点的出度为零。（）A.正确B.错误参考答案：【A】5、假设一个叶子结点是某二叉树的中序遍历序列的最后一个结点，那么它必是该二 叉树的先序遍历序列中的最后一个结点。（）A.正确B.借误参考答案：【A】6、入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。（）A.正确B.错误参考答案：【A】7、设一棵树T可以转化成二叉树BT,那么二叉树BT中一定没有右子树。（）A.正确B.错误参考答案：【A】8、图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点 是否被访问过。（）A.正确B.错误参考答案：【A】9、不管线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间 复杂度均为0（n）。（）A.正确B.错误参考答案：【A】10、子串“ABC”在主串“AABCABCD”中的位置为2。（）A.正确B.错误参考答案：【A】11、设一棵二叉树的先序序列和后序序列，那么能够唯一确定出该二叉树的形状。（）A.正确B.错误参考答案：【B】12、冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（）A.正确B错误参考答案：【A】13、带权无向图的最小生成树是唯一的。（）A.正确B.错误参考答案：【B】14、对链表进行插入和删除操作时不必移动链表中结点。（）A.正确B.错误参考答案：【A】15、不管是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情 况。（）A.正确B.错误参考答案：【A】16、先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（）A.正确B.错误参考答案：【A】二、单项选择（共计60分,每题2.5分）17、设一组初始记录关键字序列为（45, 80, 55, 40, 42, 85）,那么以第一个记录关键字45为基准而得到一趟快速排序的结果是（）o40, 42, 45, 55, 80, 83A. 42, 40, 45, 80, 85, 8842, 40, 45, 55, 80, 85D.42, 40, 45, 85, 55, 80参考答案：【C】18、具有n个结点的完全二叉树的深度为F Iog2n J +1A. Iog2n+1Iog2nB. Iog2n参考答案：【D】19、设无向图G中有n个顶点e条边，那么其对应的邻接表中的表头结点和表结 点的个数分别为（）。A. n, eB. e, nC.2n, eD.n, 2e参考答案：【D】20、假设有18个元素的有序表存放在一维数组A19中，第一个元素放Al中，现进行二分查找，那么查找A 3的比拟序列的下标依次为（）1, 2, 3A. 9, 5, 2, 39, 5, 3B. 9, 4, 2, 3参考答案：【D】21、设一组初始记录关键字序列为（Q, H, C, Y, P, A, M, S, R, D, F, X）, 那么按字母升序的第一趟冒泡排序结束后的结果是（）o2nA. n+l2n-lB. 2n+l参考答案：【D】22、数据的最小单位是（）oA.数据项B.数据类型C.数据元素D.数据变量参考答案：【A】23、设一组初始记录关键字序列为（25, 50, 15, 35, 80, 85, 20, 40, 36, 70）, 其中含有5个长度为2的有序子表，那么用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（）oA. 15, 25,A. 15, 25,35, 50, 20,B. 15, 25, 35, 50, 80,40, 80, 85, 36, 7020, 85, 40, 70, 36C. 15,C. 15,25, 35, 50, 80, 85,D. 15, 25, 35, 50, 参考答案：【A】80, 20,20, 36, 40, 7036, 40, 70, 85)o24、在二叉排序树中插入一个关键字值的平均时间复杂度为（O（n）A. O（log2n）O（nlog2n）B. O（n2）参考答案：【B】25、快速排序在 情况下最易发挥其长处。A.被排序的数据中含有多个相同排序码B.被排序的数据已基本有序C.被排序的数据完全无序D.被排序的数据中的最大值和最小值相差悬殊参考答案：【C】26、二分查找要求结点A.有序、顺序存储B.有序、链接存储C.无序、顺序存储D.无序、链接存储参考答案：【A】27、一个链栈的栈顶指针是top,那么执行出栈操作时（栈非空），用x保存被删除 结点，那么执行A. x=top;top=top-next;x=top-data;B. top=top-next;x=top-data;x=top-data;top=top-next;参考答案：【D】28、设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的 队尾指针，指针变量s指向将要入队列的结点X,那么入队列的操作序列为（）o A. front-next=s； front=s；B. s-next=rear； rear=s；rear-next=s； rear=s；C. s-next=front； front=s；参考答案：【C】29、在n个结点的顺序表中，算法的时间复杂度是0 （1）的操作是A.访问第i个结点（lWiWn）B.在第i个结点后插入一个新结点（lWWn）C.删除第i个结点（lWWn）D.将n个结点从小到大排序参考答案：【A】30、队列是一种（）的线性表。A.先进先出 B.先进后出 C.只能插入 D.只能删除 参考答案：【A】 31、设一个栈的输入序列为A, B, C, D,那么借助一个栈所得到的输出序列不可 能是（）o A. A, B9 C, D B.A, C, D9 B C. D, C, B, A D. D, A ? B, C 参考答案：【D】 32、单链表的存储密度A.大于1B.等于1 C.小于1 D.不能确定 参考答案：【C】 33、设一棵完全二叉树中有65个结点，那么该完全二叉树的深度为（）o A. 87B. 65 参考答案：【B】34、设某哈夫曼树中有199个结点，那么该哈夫曼树中有（）个叶子结点。A. 99100B. 101102 参考答案：【B】35、每一个存储结点只含有一个数据元素，数据元素按散列函数确定存储位置的 存储方式是A.顺序存储 B.链式存储 C.索引存储 D.散列存储 参考答案：【D】 36、假设线性表最常用的操作是存取第i个元素的值，那么采用 存储方式节省时间。A.单链表 B.双链表 C.单循环链表 D.顺序表参考答案：【D】37、一个队列的入队序列是1, 2, 3, 4,那么队列的输出序列是1, 2, 3, 4A. 4, 3, 2, 11, 4, 3, 2B. 3, 2, 4, 1参考答案：【A】38、深度为k的完全二叉树中最少有（）个结点。A. 2k-l-l2k-lB. 2k-l+l2k-l参考答案：【B】39、假设有18个元素的有序表存放在一维数组A19中，第一个元素放Al中，现进行二分查找，那么查找A 3的比拟序列的下标依次为（）1, 2, 3A. 9, 5, 2, 39, 5, 3B. 9, 4, 2, 3参考答案：【D】40、下面关于线性表的表达错误的选项是（）oA.线性表采用顺序存储必须占用一片连续的存储空间B.线性表采用链式存储不必占用一片连续的存储空间C.线性表采用链式存储便于插入和删除操作的实现D.线性表采用顺序存储便于插入和删除操作的实现参考答案：【D】一、判断（共计40分，每题2.5分）1、设一棵二叉树的先序序列和后序序列，那么能够唯一确定出该二叉树的形状。（）A.正确B.错误参考答案：【B】2、假设一个叶子结点是某二叉树的中序遍历序列的最后一个结点，那么它必是该二 叉树的先序遍历序列中的最后一个结点。（）A.正确B.错误参考答案：【A】3、子串“ABC”在主串“AABCABCD”中的位置为2。（）A.正确B.错误参考答案：【A】4、线性表中的所有元素都有一个前驱元素和后继元素。（）A.正确B.错误参考答案：【B】5、设一棵树T可以转化成二叉树BT,那么二叉树BT中一定没有右子树。（）A.正确B.错误参考答案：【A】6、如果某个有向图的邻接表中第i条单链表为空，那么第i个顶点的出度为零。（）A.正确B.错误参考答案：【A】7、冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（）A.正确B.错误参考答案：【A】8、图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点 是否被访问过。（）A.正确B.错误参考答案：【A】9、不管线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间 复杂度均为0（n）。（）A.正确B.错误参考答案：【A】10、对链表进行插入和删除操作时不必移动链表中结点。（）A.正确B.错误参考答案：【A】11、不管是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情 况。（）A.正确B.错误参考答案：【A】12、哈夫曼树中没有度数为1的结点。（）A.正确B.错误参考答案：【A】13、调用一次深度优先遍历可以访问到图中的所有顶点。（）A.正确B.借误参考答案：【B】14、先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（）A.正确B.错误参考答案：【A】15、入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。()A.正确B.错误参考答案：【A】16、带权无向图的最小生成树是唯一的。()A.正确B.错误参考答案：【B】二、单项选择(共计60分，每题2.5分)17、对于线性表(7, 34, 55, 25, 64, 46, 20, 10)进行散列存储口寸，假设选用 H (K)=K%9作为散列函数，那么散列地址为1的元素有()个。A. 12B. 34参考答案：【D】18、设某有向图的邻接表中有n个表头结点和m个表结点，那么该图中有() 条有向边。A. nn-1B. mm-1参考答案：【C】19、一个链栈的栈顶指针是top,那么执行出栈操作时(栈非空)，用x保存被删除 结点，那么执行A. x=top;top=top-next;x=top-data;B. top=top-next;x=top-data;x=top-data;top=top-next;参考答案：【D】20、设散列表中有m个存储单元,散列函数H(key)= key % p,那么p最好选择()。A.小于等于m的最大奇数B.小于等于m的最大素数C.小于等于m的最大偶数D.小于等于m的最大合数参考答案：【B】21、循环队列SQ的存储空间是数组dm,队头、尾指针分别是front和rear,那么 执行入队后其尾指针值rear是A. rear=rear+lrear=(rear+l)%(m-l)B. rear=(rear+l)%mrear=(rear-l)%m参考答案：【C】22、设有n个待排序的记录关键字，那么在堆排序中需要()个辅助记录单元。A. 1nB. nlog2nn2参考答案：【A】23、以下四种排序中()的空间复杂度最大。A.插入排序B.冒泡排序C.堆排序D.归并排序参考答案：【D】24、利用直接插入排序法的思想建立一个有序线性表的时间复杂度为()oA. 0(n)O(nlog2n)B. 0(n2)O(log2n)参考答案：【C】25、下面程序的时间复杂度为()for (i=l, s=0； i=n； i+) t=l； for(j=l； j=i; j+) s=s+t； A. 0(n)0(n2)B. 0(n3)0(n4)参考答案：【B】26、设 si=贝ij strlen(sl)的值是A. 01B. 23参考答案：【A】27、设有序顺序表中有n个数据元素，那么利用二分查找法查找数据元素X的最多 比拟次数不超过()oA. Iog2n+1Iog2n-1B. Iog2nIog2(n+1)参考答案：【A】28、二叉排序树中左子树上所有结点的值均()根结点的值。A. C.=D. !=参考答案：【A】B.错误参考答案：【B】11、设一棵树T可以转化成二叉树BT,那么二叉树BT中一定没有右子树。()A.正确B.错误参考答案：【A】12、设一棵二叉树的先序序列和后序序列，那么能够唯一确定出该二叉树的形状。()A.正确B.错误参考答案：【B】13、带权无向图的最小生成树是唯一的。()A.正确B.错误参考答案：【B】14、先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。()A.正确B.错误参考答案：【A】15、子串“ABC”在主串“AABCABCD”中的位置为2。()A.正确B.错误参考答案：【A】16、对链表进行插入和删除操作时不必移动链表中结点。()A.正确B.错误参考答案：【A】二、单项选择(共计60分，每题2.5分)17、对n个记录的文件进行快速排序，所需要的辅助存储空间大致为()A. O (1)0 (n)B. 0 (log2n)0 (n2)参考答案：【C】18、一个链栈的栈顶指针是top,那么执行出栈操作时(栈非空)，用x保存被删除 结点，那么执行A. x=top;top=top-next;x=top-data;B. top=top-next;x=top-data;x=top-data;top=top-next;参考答案：【D】19、设一组初始记录关键字序列为(45, 80, 55, 40, 42, 85),那么以第一个记录关键字45为基准而得到一趟快速排序的结果是()oA. 40, 42, 45, 55, 80, 8329、快速排序在 情况下最易发挥其长处。A.被排序的数据中含有多个相同排序码B.被排序的数据已基本有序C.被排序的数据完全无序D.被排序的数据中的最大值和最小值相差悬殊参考答案：【C】30、数据的最小单位是()。A.数据项B.数据类型C.数据元素D.数据变量参考答案：【A】31、单链表的存储密度A.大于1B.等于1C.小于1D.不能确定参考答案：【C】32、设有序表中的元素为(13, 18, 24, 35, 47, 50, 62),那么在其中利用二分法 查找值为24的元素需要经过()次比拟。A. 12B. 34参考答案：33、以下算法的时间复杂度是for(i=0;inext=p-next； p-next=-sB. q-next=s； s-next=pp-next=s-next； s-next=pC. p-next=s； s-next=q参考答案：【B】30、设某有向图的邻接表中有n个表头结点和m个表结点，那么该图中有（） 条有向边。A. nn-1B. mm-1参考答案：31、下面关于线性表的表达错误的选项是（）oA.线性表采用顺序存储必须占用一片连续的存储空间B.线性表采用链式存储不必占用一片连续的存储空间C.线性表采用链式存储便于插入和删除操作的实现D.线性表采用顺序存储便于插入和删除操作的实现参考答案：【D】32、设有一个二维数组假设A存放位置在644（10）, A22存放位 置在676（10）,每个元素占一个空间，问A（10）存放在什么位置？脚注（10）表 示用10进制表示。A. 688678B. 692696参考答案：33、()二叉排序树可以得到一个从小到大的有序序列。A.先序遍历B.中序遍历C.后序遍历D.层次遍历参考答案：【B】34、每一个存储结点只含有一个数据元素，数据元素按散列函数确定存储位置的 存储方式是A.顺序存储B.链式存储C.索引存储D.散列存储参考答案：【D】35、以下算法的时间复杂度是for(i=0;in;i+) ci=i;A. 0(1)0(n)B. O(log2n)O(nlog2n)参考答案：【B】36、二路归并排序的时间复杂度为()oA. 0(n)0(n2)B. O(nlog2n)O(log2n)参考答案：【C】37、设有序表中的元素为(13, 18, 24, 35, 47, 50, 62),那么在其中利用二分法 查找值为24的元素需要经过()次比拟。A. 12B. 34参考答案：38、用某种排序方法对线性表(25, 87, 21, 47, 15, 27, 63, 35, 20)进行 排序时,元素序列的变化情况如下：(1) 25, 87, 21, 47, 15, 27, 63, 35, 20 (2) 20, 15, 21, 25, 47, 27, 63, 35, 87 (3) 15, 20, 21, 25, 35, 27, 47, 63, 87 (4) 15, 20, 21, 25, 27, 35, 47, 63, 87 那么采用的排序方 法是 排序长度为4oA.交换排序法B.选择排序法C.插入排序D.选择排序参考答案：39、对于线性表(7, 34, 55, 25, 64, 46, 20, 10)进行散列存储时，假设选用 H (K)=K%9作为散列函数，那么散列地址为1的元素有()个。A. 12B. 3D.4参考答案：【D】40、设一组权值集合W=2, 3, 4, 5, 6,那么由该权值集合构造的哈夫曼树中带 权路径长度之和为（）oA. 2030B. 4045参考答案：【D】一、判断（共计40分,每题2.5分）1、设一棵树T可以转化成二叉树BT,那么二叉树BT中一定没有右子树。（）A.正确B.错误参考答案：【A】2、对链表进行插入和删除操作时不必移动链表中结点。（）A.正确B.错误参考答案：【A】3、线性表中的所有元素都有一个前驱元素和后继元素。（）A.正确B.错误参考答案：【B】4、入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。（）A.正确B.错误参考答案：【A】5、假设一个叶子结点是某二叉树的中序遍历序列的最后一个结点，那么它必是该二 叉树的先序遍历序列中的最后一个结点。（）A.正确B.错误参考答案：【A】6、先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（）A.正确B.错误参考答案：【A】7、冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（）A.正确B.错误参考答案：【A】8、不管线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为0（n）。（）A.正确B.错误参考答案：【A】9、调用一次深度优先遍历可以访问到图中的所有顶点。（）A.正确B.错误参考答案：【B】10、如果某个有向图的邻接表中第i条单链表为空，那么第i个顶点的出度为零。（）A.正确B.错误参考答案：【A】11、图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点 是否被访问过。（）A.正确B.错误参考答案：【A】12、带权无向图的最小生成树是唯一的。（）A.正确B.错误参考答案：【B】13、不管是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情 况。（）A.正确B.错误参考答案：【A】14、哈夫曼树中没有度数为1的结点。（）A.正确B.错误参考答案：【A】15、设一棵二叉树的先序序列和后序序列，那么能够唯一确定出该二叉树的形状。（）A.正确B.错误参考答案：【B】16、子串“ABC”在主串“AABCABCD”中的位置为2。（）A.正确B.借误参考答案：【A】二、单项选择（共计60分，每题2.5分）17、设某有向图的邻接表中有n个表头结点和m个表结点，那么该图中有（） 条有向边。A. nn-1C. mD. m-1参考答案：【C】18、具有n个结点的完全二叉树的深度为A. Iog2n+1Iog2n+1B. Iog2nIog2n参考答案：【D】19、设一组初始记录关键字序列为(25, 50, 15, 35, 80, 85, 20, 40, 36, 70), 其中含有5个长度为2的有序子表，那么用归并排序的方法对该记录关键字序列进行一趟归并后的结果为(A. 15,B. 15,C. 15,D. 15,25,25,25,25,参考答案:35, 35, 35, 35, A50,50,50,50,20,80,80,80,40,20,85,20,)o80,85,20,36,85,40,36,40,36,70,40,70,703670855, 6,那么由该权值集合构造的哈夫曼树中带20、设一组权值集合W=2, 3, 4, 权路径长度之和为()oA. 20B. 3040C. 45参考答案：【D】21、设有序顺序表中有n个数据元素，那么利用二分查找法查找数据元素X的最多 比拟次数不超过()oIog2n+1A. Iog2n-1Iog2nB. Iog2(n+1)参考答案：【A】22、设一组权值集合W=(15, 3, 14, 2, 6, 9, 16, 17),要求根据这些权值集 合构造一棵哈夫曼树，那么这棵哈夫曼树的带权路径长度为()o129A. 219189B. 229参考答案：【D】23、设完全无向图中有n个顶点，那么该完全无向图中有()条边。A. n(n-l)/2n(n-l)B. n(n+l)/2D.(n-l)/2参考答案：【A】24、下面关于线性表的表达错误的选项是()oA.线性表采用顺序存储必须占用一片连续的存储空间 B.线性表采用链式存储不必占用一片连续的存储空间 C.线性表采用链式存储便于插入和删除操作的实现 D.线性表采用顺序存储便于插入和删除操作的实现 参考答案：【D】25、设无向图G中有n个顶点e条边，那么其对应的邻接表中的表头结点和表结 点的个数分别为()o A. n, e B. e, n C. 2n, e D.n, 2e 参考答案：【D】26、快速排序在 情况下最易发挥其长处。A.被排序的数据中含有多个相同排序码B.被排序的数据已基本有序 C.被排序的数据完全无序 D.被排序的数据中的最大值和最小值相差悬殊 参考答案： 27、深度为k的完全二叉树中最少有()个结点。 A. 2k-l-l B. 2k-l C. 2k-l+l D. 2k-l 参考答案：【B】28、在n个结点的顺序表中，算法的时间复杂度是。(1)的操作是 A.访问第i个结点(lin)B.在第i个结点后插入一个新结点(lWWn) C.删除第i个结点(lWiWn) D.将n个结点从小到大排序 参考答案：【A】29、设一组初始记录关键字序列为(Q, H, C, Y, P, A, M, S, R, D, F, X), 那么按字母升序的第一趟冒泡排序结束后的结果是()oA. 2n B. n+l C. 2n-l D. 2n+l 参考答案：【D】 30、对n个记录的文件进行快速排序，所需要的辅助存储空间大致为() A. O (1) B. O (n)C. 0 (log2n)0 (n2)