《西北工业大学21秋《数据结构》期末考核试题及答案参考22》由会员分享，可在线阅读，更多相关《西北工业大学21秋《数据结构》期末考核试题及答案参考22（11页珍藏版）》请在金锄头文库上搜索。
1、西北工业大学21秋数据结构期末考核试题及答案参考1. 已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于( )。A.1.0B.2.9C.3.4D.5.5参考答案：B2. 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。( )A.正确B.错误参考答案：A3. 若进栈序列为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参考答案：B4. 在队列中，允许进行插入操作的一端称为队头。( )A、错误B、正确参考答案
2、：B5. 数据结构是带有结构的数据元素的集合。( )A.正确B.错误参考答案：A6. 四个元素进入队列QU的顺序是U、V、X、Y，进行DeQueue(QU，x)操作后，队头元素是( )。A.YB.XC.VD.U参考答案：C7. 两个串相等的充分必要条件是两个串的长度相等且字母相同。( )A、错误B、正确参考答案：B8. 插入、删除只能在同一端进行的线性表，称为( )。A.队列B.栈C.循环队列D.循环栈参考答案：B9. 若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为( )。A.4B.5C.8D.9参考答案：C10. 在关键字序列(12，23，34，45，56，67，
3、78，89，91)中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为( )。A.4，4，3B.4，3，3C.3，4，4D.3，3，4参考答案：B11. 依次在初始为空的队列中插入元素X，Y，Z，W以后，紧接着作了两次删除操作，此时的队头元素是( )A.XB.YC.ZD.W参考答案：C12. 队列允许在队尾删除，在队头插入。( )A.正确B.错误参考答案：A13. 对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。( )A、错误B、正确参考答案：B14. 设某完全无向图中有n个顶点，则该完全无向图中有( )条边。A.n(n-1)/2B.n(n-1
4、)C.n2D.n2-1参考答案：A15. 下列四种排序中( )的空间复杂度最大。A.插入排序B.冒泡排序C.堆排序D.归并排序参考答案：C16. 某二叉树结点的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为( )。A.3B.2C.4D.5参考答案：C17. 设根结点层次为1，某二叉树的结点前序序列和后序序列正好相反，则该二叉树一定是( )。A.高度等于其结点数B.空或只有一个结点C.任一结点无左子女D.任一结点无右子女参考答案：A18. 分块查找在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中的元素个数有关。( )A.正确B.错误参考答案：A1
5、9. 对于线性表(7，34，55，25，64，46，20，10)进行散列存储时，若选用H(K)=K%9作为散列函数，则散列地址为1的元素有( )个。A.1B.2C.3D.4参考答案：D20. 二叉树中结点只有一个孩子时无左右之分。( )A、错误B、正确参考答案：A21. 右图中的拓扑序列为( )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参考答案：D22. 内部排序是根据关键词的大小重新安排各( )的顺序。A.关键词B.数据项C.文件D.数据元素参考答案：B23.
6、 用ISAM组织文件适合于( )。A.磁盘B.磁带C.外存储器D.光盘参考答案：A24. 具有n个结点的连通图至少有( )条边。A.n-1B.nC.n(n-1)/2D.2n参考答案：A25. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是( )。A.9B.11C.15D.不能确定参考答案：C26. head指向的带表头结点的单链表为空的判定条件是( )。A.head-next=headB.head-next=NULLC.head=NULLD.head!=NULL参考答案：B27. 任何一棵二叉树的叶结点在前序、中序和后序遍历序列中的相对次序( )。A.稍有改变B.
7、发生改变C.不能确定D.不发生改变参考答案：D28. 下列程序段for(i=1; iA.O(1)B.O(0)C.O(1+n)D.O(n)参考答案：D29. 深度为k的二叉树至多有2k-1个结点。( )A、错误B、正确参考答案：A30. 对5个不同的数据元素进行直接插入排序，最多需要进行( )次比较A.8B.10C.15D.25参考答案：B31. 在长度为n的顺序表的第i(1in+1)个位置上插入一个元素，元素的移动次数为( )。A、n-i+1B、n-iC、iD、i-1参考答案：A32. 在计算机内实现递归算法时所需的辅助数据结构是( )。A、栈B、队列C、树D、图参考答案：A33. 在链表的结
8、点中，数据元素所占的存储量和整个结点所占的存储量之比称作存储密度。( )A、错误B、正确参考答案：B34. 线性表(a1，a2，.，an)以链式方式存储，访问第i位置元素的时间复杂度为( )。A.O(0)B.O(1)C.O(n)D.O(n2)参考答案：C35. 若一个有向图的邻接距阵中，主对角线以下的元素均为零，则该图的拓扑有序序列( )。A.一定存在B.一定不存在C.不一定存在D.不确定参考答案：A36. 在下列各种文件中，不能进行顺序查找的文件是( )。A.顺序文件B.索引文件C.散列文件D.多重表文件参考答案：C37. 删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树
9、。( )A、错误B、正确参考答案：A38. 对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )。A.顺序表B.用头指针表示的循环单链表C.用尾指针表示的循环单链表D.单链表参考答案：C39. 抽象数据类型的三个组成部分分别为( )。A、数据对象、数据关系和基本操作B、数据元素、逻辑结构和存储结构C、数据项、数据元素和数据类型D、数据元素、数据结构和数据类型参考答案：A40. 引入二叉线索树的目的是( )。A.加快查找结点的前驱或后继的速度B.使二叉树的遍历结果唯一C.为了能方便的找到双亲D.为了能在二叉树中方便的进行插入与删除参考答案：A41. 中序遍历的递归算法平均空间复杂
10、度为( )。A.2(n)B.n(2)C.0(n)D.2n参考答案：C42. 若有18个元素的有序表存放在一堆数组A19中，第一个元素放A1中，现进行二分查找，则查找A3的比较序列的下标依次为( )。A.1，2，3B.9，5，2，3C.9，5，3D.9，4，2，3参考答案：D43. 若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是( )。A.10B.11C.12D.15参考答案：A44. 将一个A1.100，1.100的三对角矩阵，按行优先次序存入一维数组B1.298中，A中元素A66，65在数组B中的位置K为( )。A.199B.197C.195D.193参考答案：C45. 不含任何字符的串称为空串。( )A、错误B、正确参考答案：B46. 可以用队列实现数值转换算法。( )A.正确B.错误参考答案：A47. 一个具有4个顶点的无向完全图有6条边。( )A、错误B、正确参考答案：B48. 线性链表是通过( )方式表示元素之间的关系A.后继元素地址B.元素的存储顺序C.左、右孩子地址D.元素的相对存储位置参考答案：A49. 若进栈序列为a，b，c，且进栈和出栈可以穿插进行，则可能出现6个不同的出栈序列。( )A、错误B、正确参考答案：A50. 一个有向图的邻接表和逆邻接表中结点的个数可能不等。( )A.正确B.错误参考答案：B
