《西北工业大学21春《数据结构》在线作业二满分答案2》由会员分享，可在线阅读，更多相关《西北工业大学21春《数据结构》在线作业二满分答案2（13页珍藏版）》请在金锄头文库上搜索。
1、西北工业大学21春数据结构在线作业二满分答案1. 在指定结点之后插入新结点时，双链表比单链表更方便。( )A.正确B.错误参考答案：B2. 广义表运算式tail(a，b)，(c，d)的操作结果是( )。A.dB.c，dC.(c，d)D.(c，d)参考答案：D3. 允许对队列进行的操作有( )。A.对队列中的元素排序B.取出最近进队的元素C.在队头元素之前插入元素D.删除队头元素参考答案：D4. 假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi相关的所有弧的时间复杂度是( )A.O(n)B.O(e)C.O(n+e)D.O(n*e)参考答案：C5. 对长度为n的关键字序列进行堆
2、排序的空间复杂度为( )。A.O(log2n)B.O(1)C.O(n)D.O(n*log2n)参考答案：B6. 在对含n个结点的二叉树进行先序、中序和后序遍历时，其时间复杂度( )。A.都不相同B.完全相同C.先序和中序相同，而与后序不同D.中序和后序相同，而与先序不同参考答案：B7. 完全二叉树中的叶子结点只可能在最后两层中出现。( )A.正确B.错误参考答案：A8. 已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为k。( )A、错误B、正确参考答案：A9. 如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的
3、适当位置，则该排序方法称为( )。A.插入排序B.归并排序C.冒泡排序D.堆排序参考答案：A10. 若一棵满三叉树中含有121个结点，则该树的深度为6。( )A、错误B、正确参考答案：A11. 在一个长度为n的单链表L中，删除链表中*p的前驱结点的时间复杂度为O(n)。( )A、错误B、正确参考答案：B12. 如果最常用的操作是取第i个结点及其前驱，则采用( )存储方式最节省时间。A.单链表B.双链表C.单循环链表D.顺序表参考答案：D13. 为使平均查找长度达到最小，当由关键字集合05，11，21，25，37，40，41，62，84构建二叉排序树时，第一个插入的关键字应为( )。A.5B.3
4、7C.41D.62参考答案：B14. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是( )。A.9B.11C.15D.不能确定参考答案：C15. 若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个( )。A.上三角矩阵B.稀疏矩阵C.对角矩阵D.对称矩阵参考答案：D16. 计算机识别、存储和加工处理的对象被统称为( )。A、数据B、数据元素C、数据结构D、数据类型参考答案：A17. 深度为h的满m叉树的第k层的结点(1=A.mk-1B.mk-1C.mh-1D.mh-1参考答案：A18. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除
5、运算，则节省时间的存储方式是( )。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表参考答案：A19. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( )A.正确B.错误参考答案：B20. 在下列排序算法中，哪一个算法的时间复杂度与记录初始排列无关?( )A.直接选择排序B.直接插入排序C.快速排序D.冒泡排序参考答案：A21. 在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系( )。A.不一定相同B.都相同C.都不相同D.互为逆序参考答案：B22. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q
6、，若6个元素出队的序列是e2，e4，e3，e6，e5，e1则栈S的容量至少应该是( )。A.6B.4C.3D.2参考答案：C23. 结构就是用户定义的，( )的一个集合体。参考答案：不同数据类型24. 在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是堆排序。( )A、错误B、正确参考答案：A25. 一组记录的关键字经一趟二路归并排序后得到含有5个长度为2的有序表如下：25，48，16，35，79，82，23，40，36，72，在此基础上按二路归并排序方法再对该序列进行一趟归并后的结果为( )A.16，25，35，48，23，40，79，82，36，72B.16，25，35，
7、48，23，40，79，82，72，36C.16，25，48，35，79，82，23，36，40，72D.16，25，35，48，79，23，36，40，72，82参考答案：D26. 广义表(a，b，c，d)的表头是( )。A.(b，c，d)B.(a，b，c，d)C.aD.(a)参考答案：B27. 若有序表的关键字序列为(b，c，d，e，f，g，q，r，s，t)，则在二分查找关键字b的过程中，先后进行比较的关键字依次为( )。A.f，c，bB.f，d，bC.g，c，bD.g，d，b参考答案：A28. 设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域为空的结点有( )
8、A.n-1B.nC.n+1D.n+2参考答案：B29. 归并排序的辅助存储空间代价为O(1)。( )A.正确B.错误参考答案：B30. 连通网的最小生成树是其所有生成树中( )。A.顶点集最小的生成树B.边集最小的生成树C.顶点权值之和最小的生成树D.边的权值之和最小的生成树参考答案：D31. 由于排序过程中涉及的存储器不同，可以将排序方法分为( )。A、稳定排序B、不稳定排序C、内部排序D、外部排序参考答案：CD32. 假设一棵完全二叉树含1000个结点,则其中度为2的结点数为512个。( )A、错误B、正确参考答案：A33. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则
9、可能出现的出栈序列为( )。A、3，2，6，1，4，5B、3，4，2，1，6，5C、1，2，5，3，4，6D、5，6，4，2，3，1参考答案：B34. 按层次次序将一颗有n个结点的完全二叉树的所有结点从1到n编号，当iA.2i-1B.2iC.2i+1D.不确定参考答案：B35. 下面程序段的时间复杂度为( )。for(i=0; im; i+)for(j=0; jn; j+)Aij=i*j;A、O(m2)B、O(n2)C、O(m*n)D、O(m+n)参考答案：C36. 产生冲突现象的两个关键字称为该散列函数的同义字。( )A、错误B、正确参考答案：B37. 如果入栈序列是1，3，5，97，99，
10、且出栈序列的第一个元素为99，则出栈序列中第30个元素为47。( )A、错误B、正确参考答案：B38. 在有向图中，以顶点v为终点的边的数目称为v的入度。( )A、错误B、正确参考答案：B39. 在线性表的下列运算中，不改变数据元素之间结构关系的运算是( )。A、插入B、删除C、排序D、定位参考答案：D40. 用ISAM组织文件适合于( )。A.磁盘B.磁带C.外存储器D.光盘参考答案：A41. 若要在单链表中的结点p之后插入一个结点s，则应执行的语句是( )。A.s-next=p-next; p-next=sB.p-next=s; s-next=p-nextC.p-next=s-next;
11、s-next=pD.s-next=p; p-next=s-next参考答案：A42. 如果要求一个线性表既能较快地查找、又能适应动态变化的要求，则可采用的查找方法是( )。A.顺序查找B.折半查找C.基于属性的查找D.分块查找参考答案：D43. n个顶点的连通图至少有( )条边。A.n-1B.nC.n+1D.0参考答案：A44. 将森树转成二叉树，根结点没有右子树。( )A.正确B.错误参考答案：B45. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是( )。A.(rear+1)%n=frontB.rear=frontC.rear+1=frontD.(rear-l
12、)%n=front参考答案：B46. 栈下溢是指在栈空时进行出栈操作。( )A、错误B、正确参考答案：B47. 已知一个散列表如图所示，其散列函数为H(key)=key%11，采用二次探查法处理冲突，则下一个插入的关键字49的地址为( )。A.2B.3C.8D.9参考答案：C48. 设某完全无向图中有n个顶点，则该完全无向图中有( )条边。A.n(n-1)/2B.n(n-1)C.n2D.n2-1参考答案：A49. 在一个单链表中，若删除*p结点的后继结点，则执行操作( )。A.q=p-next; p-next=q-next; free(q)B.p=p-next; p-next=p-next-n
13、ext; free(p)C.p-next=q-next; free(p-next)D.p=p-next-next; free(p-next)参考答案：A50. 在对链队列作出队操作时，不会改变front指针的值。( )A、错误B、正确参考答案：A51. 在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是( )。A.O(1)B.O(n)C.O(n2)D.O(nlog2n)参考答案：B52. 向二叉搜索树中插入一个元素时，其时间复杂度大致为( )A.O(log2n)B.O(n)C.O(1)D.O(2n)参考答案：A53. 在链队列中，假设f和r分别为队首和队尾指针，则删除一个结点的操作是( )。A.r=r-nextB.r=f-nextC.f=r-nextD.f=f-next参考答案：D54. 链表中的表头指针与表头结点起到相同的作用。( )A.正确B.错误参考答案
