《西北工业大学21春《数据结构》离线作业2参考答案72》由会员分享，可在线阅读，更多相关《西北工业大学21春《数据结构》离线作业2参考答案72（12页珍藏版）》请在金锄头文库上搜索。
1、西北工业大学21春数据结构离线作业2参考答案1. n个结点的线索二叉树上含有的线索数为( )。A.n-1B.n+1C.nD.2n参考答案：B2. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的( )。A.先序遍历B.中序遍历C.后序遍历D.按层遍历参考答案：C3. 若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是( )。A.1234B.4132C.4231D.4213参考答案：C4. 含n个顶点的无向连通图中至少含有n条边。( )A、错误B、正确参考答案：A5. 最佳二叉排序树是AVL树(平衡二叉排序树)。( )A.正确B.错
2、误参考答案：A6. 采用分快查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分( )个结点最佳。A.10B.25C.6D.625参考答案：B7. 若有18个元素的有序表存放在一堆数组A19中，第一个元素放A1中，现进行二分查找，则查找A3的比较序列的下标依次为( )。A.1，2，3B.9，5，2，3C.9，5，3D.9，4，2，3参考答案：D8. 允许对队列进行的操作有( )。A.对队列中的元素排序B.取出最近进队的元素C.在队头元素之前插入元素D.删除队头元素参考答案：D9. 若一棵满三叉树中含有121个结点，则该树的深度为6。( )A
3、、错误B、正确参考答案：A10. 由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间多。( )A、错误B、正确参考答案：A11. 设串sl=DataStructureswithJava，s2=it，则子串定位函数index(s1,s2)的值为( )A.15B.16C.17D.18参考答案：D12. 在k叉树中，度为0的结点称为( )。A.祖先B.根C.子孙D.叶参考答案：D13. 对于线性表(7，34，55，25，64，46，20，10)进行散列存储时，若选用H(K)=K%9作为散列函数，则散列地址为1的元素有( )个。A.1B.2C.3D.4参考答案：D14. 结构就
4、是用户定义的，( )的一个集合体。参考答案：不同数据类型15. 已知函数Sub(s,I,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=SCIENCESTUDY，则调用函数Scopy(P,Sub(S,1,7)后得到( )。A、P=SCIENCEB、P=STUDYC、S=SCIENCED、S=STUDY参考答案：A16. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。A.插入B.选择C.交换D.二路归并参考答案：A17. 二叉排序树上左子树上所有结点的值均
5、小于它的根结点的值。( )A.正确B.错误参考答案：A18. 计算机识别、存储和加工处理的对象被统称为( )。A、数据B、数据元素C、数据结构D、数据类型参考答案：A19. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( )A.正确B.错误参考答案：B20. 右图中的拓扑序列为( )A.C1，C2，C6，C7，C5，C4，C3B.C1，C2，C6，C3，C4，C5，C7C.C1，C4，C2，C3，C5，C6，C7D.C5，C7，C4，C1，C2，C6，C3参考答案：D21. 邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。( )
6、A.正确B.错误参考答案：B22. 队列的修改是按先进先出的原则进行的。( )A、错误B、正确参考答案：B23. 链表与顺序存储结构相比，在链表中进行插入、删除操作的效率高。( )A.正确B.错误参考答案：A24. 在单链表中设置头结点的作用是( )。A.主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表指针不变B.便于查找C.便于连接D.快速插入记录参考答案：A25. 用链表表示线性表的优点是( )A.便于随机存取B.花费的存储空间比顺序表少C.便于插入与删除D.数据元素的物理顺序与逻辑顺序相同参考答案：C26. 在一个具有n个结
7、点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是( )。A.O(1)B.O(n)C.O(n2)D.O(nlog2n)参考答案：B27. 抽象数据类型是指数据逻辑结构及与之相关的操作。( )A、错误B、正确参考答案：B28. 完全二叉树中的叶子结点只可能在最后两层中出现。( )A.正确B.错误参考答案：A29. 广义表(a，b，c，d)的表头是( )。A.(b，c，d)B.(a，b，c，d)C.aD.(a)参考答案：B30. 采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为( )。A.n/2B.nC.(n-1)/2D.(n+1)/2参考答案：D31. 设栈S和队列Q的初
8、始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1则栈S的容量至少应该是( )。A.6B.4C.3D.2参考答案：C32. 在目标串T0.n-1=“xwxxyxy”中，对模式串P0.m-1=“xy”进行子串定位操作的结果是( )。A.1B.2C.3D.5参考答案：C33. 下列四种基本的逻辑结构中，数据元素之间关系最弱的是( )。A.集合B.线性结构C.树形结构D.图状结构参考答案：A34. 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。( )A.正确B.错误参考答案：B35. 后
9、序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。( )A.正确B.错误参考答案：A36. 算法有以下几种特性( )。A、有穷性B、确定性C、可行性D、输入和输出参考答案：ABCD37. 通常将链串的结点大小设置为大于1是为了( )。A、提高串匹配效率B、提高存储密度C、便于插入操作D、便于删除操作参考答案：A38. 在长度为n的顺序表的第i(1in+1)个位置上插入一个元素，元素的移动次数为( )。A、n-i+1B、n-iC、iD、i-1参考答案：A39. 由于排序过程中涉及的存储器不同，可以将排序方法分为( )。A、稳定排序B、不稳定排序C、内部排序D、外部排序参考答案：CD40. 以
10、下数据结构中，属于线性结构的是( )。A.广义表B.二叉树C.稀疏矩阵D.串参考答案：A41. 散列函数有一个共同的性质，即函数值应当以下面的哪一项来取其值域的每个值?( )A.最小概率B.最大概率C.平均概率D.同等概率参考答案：D42. 任何一棵二叉树的叶结点在前序、中序和后序遍历序列中的相对次序( )。A.稍有改变B.发生改变C.不能确定D.不发生改变参考答案：D43. 结构的存储密度定义为数据本身所占的存储量与整个结构所占的存储量之比。( )A.正确B.错误参考答案：A44. 数据结构中的任一数据元素至多只有一个前驱和一个后继，该数据结构是( )。A.线性表B.树形结构C.广义表D.图
11、结构参考答案：A45. 如果入栈序列是1，3，5，97，99，且出栈序列的第一个元素为99，则出栈序列中第30个元素为47。( )A、错误B、正确参考答案：B46. 在k叉树中，无父母的结点称为( )。A.祖先B.根C.子孙D.叶参考答案：B47. 在头指针为head的非空单循环链表中，指针p指向尾结点，下列关系成立的是( )。A、p-next=headB、p-next-next=headC、p-next=NULLD、p=head参考答案：A48. 中序遍历的递归算法平均空间复杂度为( )。A.2(n)B.n(2)C.0(n)D.2n参考答案：C49. 已知循环队列的存储空间为数组data21，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为( )。A.5B.6C.16D.17参考答案：C50. 依次在初始为空的队列中插入元素X，Y，Z，W以后，紧接着作了两次删除操作，此时的队头元素是( )A.XB.YC.ZD.W参考答案：C
