《西北工业大学22春《数据结构》离线作业二及答案参考12》由会员分享，可在线阅读，更多相关《西北工业大学22春《数据结构》离线作业二及答案参考12（13页珍藏版）》请在金锄头文库上搜索。
1、西北工业大学22春数据结构离线作业二及答案参考1. 数据的逻辑结构在计算机存储器内的表示，称为数据的逻辑结构。( )A、错误B、正确参考答案：A2. 假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi相关的所有弧的时间复杂度是( )A.O(n)B.O(e)C.O(n+e)D.O(n*e)参考答案：C3. 采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为( )。A.n/2B.nC.(n-1)/2D.(n+1)/2参考答案：D4. 稀疏矩阵常用的压缩存储方法有两种，它们是( )。A.散列和十字链表B.二维数组和三维数组C.三元组和散列D.三元组和十字链表参考答案：
2、D5. 任何有向网的拓扑排序的结果是唯一的。( )A.正确B.错误参考答案：B6. 队列的队尾位置通常是随着入队操作而变化的。( )A、错误B、正确参考答案：B7. 下列序列中，不构成堆的是( )。A.(1，2，5，3，4，6，7，8，9，10)B.(10，5，8，4，2，6，7，1，3)C.(10，9，8，7，3，5，4，6，2)D.(1，2，3，4，10，9，8，7，6，5)参考答案：D8. 若有向图的邻接矩阵中，主对角线以下元素均为零，则该图的拓扑有序序列( )。A.存在B.可能不存在C.不存在D.不一定存在参考答案：A9. 从未排序序列中挑选元素，并将其依次插入已排序序列(初始时为空)
3、的一端的方法，称为( )。A.希尔排序B.归并排序C.插入排序D.选择排序参考答案：D10. 平衡二叉树的平衡因子只可能是-1、0、1。( )A.正确B.错误参考答案：A11. 假设以S和X分别表示进栈和退栈操作，则对输入序列a，b，c，d，e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为abbccddedc。( )A、错误B、正确参考答案：A12. 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是( )。A.nB.2n-1C.2nD.n-1参考答案：A13. 不含任何字符的串称为空串。( )A、错误B、正确参考答案：B14. 若有序表的关键字序列为(b，c，d，e，
4、f，g，q，r，s，t)，则在二分查找关键字b的过程中，先后进行比较的关键字依次为( )。A.f，c，bB.f，d，bC.g，c，bD.g，d，b参考答案：A15. 具有线性结构的数据结构是( )A.赫夫曼树B.栈C.图D.树参考答案：B16. 一个加权的无向连通图的最小生成树( )。A.有一颗或多颗B.只有一颗C.一定有多颗D.可能不存在参考答案：A17. B+树应用在( )文件系统中。A.顺序B.散列C.VSAMD.ISAM参考答案：C18. 深度为15的满二叉树上，第11层有211个结点。( )A、错误B、正确参考答案：A19. 最大容量为n的循环队列，队尾指针是rear，队头是fron
5、t，则队空的条件是( )。A.(rear+1)%n=frontB.rear=frontC.rear+1=frontD.(rear-l)%n=front参考答案：B20. 由于排序过程中涉及的存储器不同，可以将排序方法分为( )。A、稳定排序B、不稳定排序C、内部排序D、外部排序参考答案：CD21. 深度为k的二叉树至多有2k-1个结点。( )A、错误B、正确参考答案：A22. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为( )。A.1和5B.2和4C.4和2D.5和1参考答案：B23.
6、 若进栈序列为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参考答案：B24. 下列描述中正确的是( )。A.选择合适的数据结构是解决应用问题的关键步骤B.线性表的逻辑顺序与存储顺序总是一致的C.每种数据结构都具备查找、插入和删除三种基本运算D.数据结构实质上包括逻辑结构和存储结构两方面的内容参考答案：A25. 抽象数据类型是指数据逻辑结构及与之相关的操作。( )A、错误B、正确参考答案：B26. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为
7、0的结点的个数是( )。A.9B.11C.15D.不能确定参考答案：C27. 在单链表中设置头结点的作用是( )。A.主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表指针不变B.便于查找C.便于连接D.快速插入记录参考答案：A28. 若哈希表(散列表)的负载因子l，则可避免冲突的产生。( )A.正确B.错误参考答案：B29. 如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是( )。A.栈B.队列C.树D.图参考答案：C30. 按层次次序将一颗有n个结点的完全二叉树的所有结点从1到n编号，当iA.2
8、i-1B.2iC.2i+1D.不确定参考答案：B31. 线性表中的所有元素都有一个前驱元素和后继元素。( )A.正确B.错误参考答案：A32. 设有一个10阶的对称矩阵A1010，采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组BA00存入B0中，则A85在B中( )A.32B.33C.41D.65参考答案：C33. 已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为k。( )A、错误B、正确参考答案：A34. 用链接方式存储的队列，在进行插入运算时( )。A.仅修改头指针B.头、尾指针都要修改C.仅修改尾指针D.头、尾指针可能都要修改
9、参考答案：D35. 任何一个递归过程都可以转换成非递归过程。( )A.正确B.错误参考答案：A36. 设有100个关键字，用折半查找法进行查找时，最大比较次数为( )。A.7B.6C.50D.25参考答案：A37. 线性表的链接实现有利于( )运算。A.插入B.读表元C.查找D.定位参考答案：A38. 取顺序表的第i个元素的时间与i的大小无关。( )A.正确B.错误参考答案：A39. 在有向图中，以顶点v为终点的边的数目称为v的入度。( )A、错误B、正确参考答案：B40. 向顺序栈中压入新元素时，应当( )A.先移动栈顶位置，再存入元素B.先存入元素，再移动栈顶位置C.先后 次序无关紧要D.
10、同时进行参考答案：A41. 结构就是用户定义的，( )的一个集合体。参考答案：不同数据类型42. 设串s1=Data Structures with Java，s2=it，则子串定位函数index(s1,s2)的值为( )。A、15B、16C、17D、18参考答案：D43. 在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是( )。A.O(1)B.O(n)C.O(n2)D.O(nlog2n)参考答案：B44. 在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p-next-next=head，则( )。A、p指向头结点B、p指向尾结点C、*p的直接
11、后继是头结点D、*P的直接后继是尾结点参考答案：D45. 对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的左孩子的编号为98。( )A、错误B、正确参考答案：B46. 对于3个结点a、b、c，可构成不同的二叉树的棵数为( )。A.32B.30C.28D.24参考答案：B47. 有向图用邻接矩阵表示后，顶点i的入度等于邻接矩阵中第i列的元素个数。( )A、错误B、正确参考答案：B48. n个结点的线索二叉树上含有的线索数为( )。A.n-1B.n+1C.nD.2n参考答案：B49. 下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是(
12、 )。A.直接选择排序B.直接插入排序C.快速排序D.堆排序参考答案：C50. 对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。( )A、错误B、正确参考答案：B51. 二叉树中除叶结点外，任一结点X，其左子树根结点的值小于该结点X的值;其右子树根结点的值大于等于该结点X的值，则此二叉树一定是二叉排序树。( )A.正确B.错误参考答案：B52. 在计算机内实现递归算法时所需的辅助数据结构是( )。A、栈B、队列C、树D、图参考答案：A53. 一个有向无环图的拓扑排序序列( )是唯一的。A.可能B.不一定C.三者均不对D.一定参考答案：B54. 依次在初始为空的
13、队列中插入元素X，Y，Z，W以后，紧接着作了两次删除操作，此时的队头元素是( )A.XB.YC.ZD.W参考答案：C55. 链式队列Q为空的判定条件：( )A.Q.front=Q.rearB.Q.front=QC.Q=Q.rearD.没有正确参考答案：A56. 下面关于串的叙述中，哪一个是不正确的?( )A.空串是由空格构成的串B.模式匹配是串的一种重要运算C.串是字符的有限序列D.串既可以采用顺序存储，也可以采用链式存储参考答案：A57. 如果最常用的操作是取第i个结点及其前驱，则采用( )存储方式最节省时间。A.单链表B.双链表C.单循环链表D.顺序表参考答案：D58. 无向图中一个顶点的度是指图中( )。A、通过该顶点的简单路径数B、与该顶点相邻接的顶点数C、通过该顶点的回路数D、与该顶点连通的顶点数参
