《西北工业大学21秋《数据结构》在线作业三满分答案73》由会员分享，可在线阅读，更多相关《西北工业大学21秋《数据结构》在线作业三满分答案73（13页珍藏版）》请在金锄头文库上搜索。
1、西北工业大学21秋数据结构在线作业三满分答案1. 链表与顺序存储结构相比，在链表中进行插入、删除操作的效率高。( )A.正确B.错误参考答案：A2. 下列陈述中正确的是( )。A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分C.二叉树中必有度为2的结点D.二叉树中最多只有两棵子树，并且有左右之分参考答案：D3. 按层次次序将一颗有n个结点的完全二叉树的所有结点从1到n编号，当iA.2i-1B.2iC.2i+1D.不确定参考答案：B4. 一个栈的入栈序列是abcde，则栈的不可能的输出序列是( )。A.edcbaB.decbaC.dceabD.abcde参考答案：C5. 在所有
2、排序方法中，关键字比较的次数与记录的初始排列次序无关的是( )。A.希尔排序B.快速排序C.插入排序D.选择排序参考答案：D6. 若采用邻接矩阵法存储一个N个顶点的无向图，则该邻接矩阵是一个( )A.队头元素的前一个位置B.队头元素的后一个位置C.队头元素位置D.队尾元素的前一位置参考答案：A7. 已知一组关键字为25，48，36，72，79，82，23，40，16，35，其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是( )。A.25，36，48，72，23，40，79，82，16，35B.25，36，48，72，16，23，40，79，82，35C.25，36，48，72，
3、16，23，35，40，79，82D.16，23，25，35，36，40，48，72，79，82参考答案：D8. 按排序过程中依据的原则分类，快速排序属于( )。A.插入类的排序方法B.选择类的排序方法C.交换类的排序方法D.归并类的排序方法参考答案：C9. 设某棵二叉树中有2000个结点，则该二叉树的最小高度为( )。A.9B.10C.11D.12参考答案：C10. 已知循环队列的存储空间为数组data21，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为( )。A.5B.6C.16D.17参考答案：C11. 如果最常用的操作是取第i个结点及其前驱，则采用( )存储方式最节省
4、时间。A.单链表B.双链表C.单循环链表D.顺序表参考答案：D12. 数据的逻辑结构是指各数据元素之间的逻辑关系。( )A.正确B.错误参考答案：A13. 在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为( )。A.O(n)B.O(n+e)C.O(n2)D.O(n3)参考答案：B14. 后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。( )A.正确B.错误参考答案：A15. 若进栈序列为a，b，c，则通过入出栈操作可能得到的a，b，c的不同排列个数为( )。A、4B、5C、6D、7参考答案：B16. 若已知一个栈序列是1，2，3，.，n，其输出序列为p1，p2，p3，.，
5、pn，若p1=n，则pi为( )。A.iB.n-iC.n-i+1D.不确定参考答案：C17. 顺序查找法适合于存储结构为( )的线性表。A.散列存储B.顺序存储或链式存储C.压缩存储D.索引存储参考答案：B18. 在队列中，允许进行删除操作的一端称为队尾。( )A、错误B、正确参考答案：B19. 两个串相等的充分必要条件是两个串的长度相等且字母相同。( )A、错误B、正确参考答案：B20. 用有向无环图描述表达式(A+B)*(A+B)/A)，至少需要顶点的数目为( )。A.5B.6C.8D.9参考答案：A21. 数组的逻辑结构不同于下列( )的逻辑结构。A.线性表B.栈C.队列D.树参考答案：
6、D22. 已知广义表LS=(a，b，c)，(d，e，f)，运算head和tail函数取出元素e的运算是( )。A.head(tail(LS)B.tail(head(LS)C.head(tail(head(tail(LS)D.head(tail(tail(head(LS)参考答案：C23. 在k叉树中，无父母的结点称为( )。A.祖先B.根C.子孙D.叶参考答案：B24. 在单链表中设置头结点的作用是( )。A.主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表指针不变B.便于查找C.便于连接D.快速插入记录参考答案：A25. 在计算
7、机内实现递归算法时所需的辅助数据结构是( )。A、栈B、队列C、树D、图参考答案：A26. 数据结构是指( )。A.数据元素的组织形式B.数据类型C.据存储结构D.数据定义参考答案：A27. 向顺序栈中压入新元素时，应当( )A.先移动栈顶位置，再存入元素B.先存入元素，再移动栈顶位置C.先后 次序无关紧要D.同时进行参考答案：A28. AOV网的含义是以顶点表示活动的网。( )A.正确B.错误参考答案：A29. 在k叉树中，度为0的结点称为( )。A.祖先B.根C.子孙D.叶参考答案：D30. 若哈希表(散列表)的负载因子l，则可避免冲突的产生。( )A.正确B.错误参考答案：B31. 若一
8、个有向图的邻接距阵中，主对角线以下的元素均为零，则该图的拓扑有序序列( )。A.一定存在B.一定不存在C.不一定存在D.不确定参考答案：A32. 依次在初始为空的队列中插入元素X，Y，Z，W以后，紧接着作了两次删除操作，此时的队头元素是( )A.XB.YC.ZD.W参考答案：C33. 假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi相关的所有弧的时间复杂度是( )A.O(n)B.O(e)C.O(n+e)D.O(n*e)参考答案：C34. 散列函数有一个共同的性质，即函数值应当以下面的哪一项来取其值域的每个值?( )A.最小概率B.最大概率C.平均概率D.同等概率参考答案：D
9、35. 设有100个数据元素，采用折半搜索时，最大比较次数为( )A.6B.7C.8D.10参考答案：B36. 任何一棵二叉树的叶结点在前序、中序和后序遍历序列中的相对次序( )。A.稍有改变B.发生改变C.不能确定D.不发生改变参考答案：D37. 完全二叉树中的叶子结点只可能在最后两层中出现。( )A.正确B.错误参考答案：A38. 取顺序表的第i个元素的时间与i的大小无关。( )A.正确B.错误参考答案：A39. 有关二叉树下列说法正确的是( )。A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为2参考答案：B40. 队列的修改
10、是按照先进先出的原则进行的。( )A、错误B、正确参考答案：B41. 采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为( )。A.n/2B.nC.(n-1)/2D.(n+1)/2参考答案：D42. 一个具有4个顶点的无向完全图有6条边。( )A、错误B、正确参考答案：B43. 在下列各种文件中，不能进行顺序查找的文件是( )。A.顺序文件B.索引文件C.散列文件D.多重表文件参考答案：C44. 某二叉树的前序和后序序列正好相同，则该二叉树一定是( )的二叉树。A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子参考答案：A45. 任何一个递归过程都可
11、以转换成非递归过程。( )A.正确B.错误参考答案：A46. 线性链表是通过( )方式表示元素之间的关系A.后继元素地址B.元素的存储顺序C.左、右孩子地址D.元素的相对存储位置参考答案：A47. 队列允许在队尾删除，在队头插入。( )A.正确B.错误参考答案：A48. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为( )。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参考答案：B49. 非空的双向循环链表中任何结点的前驱指针均不为空。( )A.正确B.错误参考答案：A50. 队列的修改是按先进先出
12、的原则进行的。( )A、错误B、正确参考答案：B51. 对线性表进行二分查找时，要求线性表必须( )。A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且结点按关键字有序排列D.以链接方式存储，且结点按关键字有序排列参考答案：C52. 对于3个结点a、b、c，可构成不同的二叉树的棵数为( )。A.32B.30C.28D.24参考答案：B53. 具有65个结点的完全二叉树其深度为(根的层次号为1)( )。A.8B.7C.6D.5参考答案：B54. 已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为(
13、)。A、q-next=s-next; s-next=pB、s-next=p; q-next=s-nextC、p-next=s-next; s-next=qD、s-next=q; p-next=s-next参考答案：A55. 对5个不同的数据元素进行直接插入排序，最多需要进行( )次比较A.8B.10C.15D.25参考答案：B56. 用链接方式存储的队列，在进行插入运算时( )。A.仅修改头指针B.头、尾指针都要修改C.仅修改尾指针D.头、尾指针可能都要修改参考答案：D57. 若用n表示图中顶点数目，则有( )条边的无向图成为完全图。A.nB.n-1C.n(n-1)2D.n(n+1)2参考答案：C58. 在队列中，允许进行插入操作的一端称为队头。( )A、错
