《西北工业大学2022年3月《数据结构》期末考核试题库及答案参考4》由会员分享，可在线阅读，更多相关《西北工业大学2022年3月《数据结构》期末考核试题库及答案参考4（13页珍藏版）》请在装配图网上搜索。
1、西北工业大学2022年3月数据结构期末考核试题库及答案参考1. 与单链表相比，双链表的优点之一是( )。A.插入、删除操作更简单B.可以进行随机访问C.可以省略表头指针或表尾指针D.顺序访问相邻结点更灵活参考答案：C2. 判断线索二叉树中某结点p有右子女的条件是( )。A.p-rtag=1B.p-rtag=0C.p-lchild!=NULLD.p!=NULL参考答案：B3. 若有序表的关键字序列为(b，c，d，e，f，g，q，r，s，t)，则在二分查找关键字b的过程中，先后进行比较的关键字依次为( )。A.f，c，bB.f，d，bC.g，c，bD.g，d，b参考答案：A4. 已知一个散列表如图
2、所示，其散列函数为H(key)=key%11，采用二次探查法处理冲突，则下一个插入的关键字49的地址为( )。A.2B.3C.8D.9参考答案：C5. 对无序表用折半查找比顺序查找快。( )A.正确B.错误参考答案：B6. 在下列各种文件中，不能进行顺序查找的文件是( )。A.顺序文件B.索引文件C.散列文件D.多重表文件参考答案：C7. 下列序列中，不构成堆的是( )。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. 数组的逻辑结构不同于下列
3、( )的逻辑结构。A.线性表B.栈C.队列D.树参考答案：D9. 向一个有127个元素原顺序表中插入一个新元素并保存原来顺序不变，平均要移动( )个元素。A.8B.63.5C.63D.7参考答案：B10. 链表不具备的特点是( )。A.可随机访问任意一个结点B.插入和删除不需要移动任何元素C.不必事先估计存储空间D.所需空间与其长度成正比参考答案：A11. 由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间多。( )A、错误B、正确参考答案：A12. 散列函数有一个共同的性质，即函数值应当以下面的哪一项来取其值域的每个值?( )A.最小概率B.最大概率C.平均概率D.同
4、等概率参考答案：D13. 在有向图中，以顶点v为终点的边的数目称为v的入度。( )A、错误B、正确参考答案：B14. 非空的双向循环链表中任何结点的前驱指针均不为空。( )A.正确B.错误参考答案：A15. 栈是一种操作受限的线性结构，其操作的主要特征是( )。A、先进先出B、后进先出C、进优于出D、出优于进参考答案：B16. 在关键字序列(12，23，34，45，56，67，78，89，91)中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为( )。A.4，4，3B.4，3，3C.3，4，4D.3，3，4参考答案：B17. 下列描述中正确的是( )。A.选择合适的数据结构是
5、解决应用问题的关键步骤B.线性表的逻辑顺序与存储顺序总是一致的C.每种数据结构都具备查找、插入和删除三种基本运算D.数据结构实质上包括逻辑结构和存储结构两方面的内容参考答案：A18. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是( )。A.0B.1C.2D.3参考答案：B19. 数据的逻辑结构是指数据的各数据项之间的逻辑关系。( )A.正确B.错误参考答案：B20. 用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为( )。A.n-1B.nC.n+lD.2n参考答案：C21. 某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是( )。A.空或只有一个结点B
6、.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子参考答案：B22. n个结点的线索二叉树上含有的线索数为( )。A.n-1B.n+1C.nD.2n参考答案：B23. 在下列排序算法中，哪一个算法的时间复杂度与记录初始排列无关?( )A.直接选择排序B.直接插入排序C.快速排序D.冒泡排序参考答案：A24. 在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用( )。A.数据元素的相邻地址表示B.数据元素在表中的序号表示C.指向后继元素的指针表示D.数据元素的值表示参考答案：C25. 在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系( )。A.不一定相同B.都相同C
7、.都不相同D.互为逆序参考答案：B26. 在长度为n的顺序表的第i(1in+1)个位置上插入一个元素，元素的移动次数为( )。A、n-i+1B、n-iC、iD、i-1参考答案：A27. 一个有向无环图的拓扑排序序列是( )。A.一定唯一的B.一定不唯一的C.不一定唯一的D.都不对参考答案：C28. 下列四种基本的逻辑结构中，数据元素之间关系最弱的是( )。A.集合B.线性结构C.树形结构D.图状结构参考答案：A29. 算法分析的目的是( )。A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易读性和文档性参考答案：C30. 线性链表是通过( )方式
8、表示元素之间的关系A.后继元素地址B.元素的存储顺序C.左、右孩子地址D.元素的相对存储位置参考答案：A31. 通常将链串的结点大小设置为大于1是为了( )。A、提高串匹配效率B、提高存储密度C、便于插入操作D、便于删除操作参考答案：A32. 深度为5的二叉树至多有( )个结点。A.16B.32C.31D.10参考答案：C33. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1则栈S的容量至少应该是( )。A.6B.4C.3D.2参考答案：C34. 指针p所指的元素是双向循环链表
9、L的尾元素的条件是( )。A.p=LB.p=NULLC.p-prior=LD.p-next=L参考答案：D35. 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。( )A.正确B.错误参考答案：A36. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则节省时间的存储方式是( )。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表参考答案：A37. 数据的逻辑结构是指各数据元素之间的逻辑关系。( )A.正确B.错误参考答案：A38. 设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找
10、，则在查找概率相等的情况下，分块查找成功时的平均查找长度为( )。A.21B.23C.41D.62参考答案：C39. 队列的插入操作是在( )。A.队尾B.队头C.队列任意位置D.队头元素后参考答案：A40. 算法分析的两个主要方面是( )。A.空间复杂度和时间复杂度B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性参考答案：A41. 完全二叉树中的叶子结点只可能在最后两层中出现。( )A.正确B.错误参考答案：A42. 哈希表不需要进行比较便可以直接取得所查记录。( )A.正确B.错误参考答案：A43. 在队列中，允许进行插入操作的一端称为队头。( )A、错误B、正确参考答案：B
11、44. 数组是同类型值的集合。( )A.正确B.错误参考答案：B45. 若进栈序列为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参考答案：B46. 对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的左孩子的编号为98。( )A、错误B、正确参考答案：B47. 在指定结点之前插入新结点时，双链表比单链表更方便。( )A.正确B.错误参考答案：A48. 在线性表的下列运算中，不改变数据元素之间结构关系的运算是( )。A、插入B、删除C、排序D、
12、定位参考答案：D49. 线性表(a1，a2，.，an)以链式方式存储，访问第i位置元素的时间复杂度为( )。A.O(0)B.O(1)C.O(n)D.O(n2)参考答案：C50. 下列关于数据结构基本概念的叙述中，正确的是( )。A.数据的逻辑结构分为表结构和树结构B.数据的存储结构分为线性结构和非线性结构C.数据元素是数据的基本单位D.结点是有独立含义的数据最小单位参考答案：C51. 在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是堆排序。( )A、错误B、正确参考答案：A52. 如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则
13、该排序方法称为( )。A.插入排序B.归并排序C.冒泡排序D.堆排序参考答案：A53. 若哈希表(散列表)的负载因子l，则可避免冲突的产生。( )A.正确B.错误参考答案：B54. 中序遍历二叉排序树可以得到一个有序的序列。( )A.正确B.错误参考答案：A55. 如果入栈序列是1，3，5，97，99，且出栈序列的第一个元素为99，则出栈序列中第30个元素为47。( )A、错误B、正确参考答案：B56. 将森树转成二叉树，根结点没有右子树。( )A.正确B.错误参考答案：B57. 下列四种排序中( )的空间复杂度最大。A.插入排序B.冒泡排序C.堆排序D.归并排序参考答案：C58. 某二叉树结点的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为( )。A.3B.2C.4D.5参考答案：C59. 一个加权的无向连通图的最小生成树( )。A.有一颗或多颗B.只有一颗C.一定有多颗D.可能不存在参考答案：A60. 二叉树中除叶结点外，任一结点X，其左子树根结点的值小于该结点X的值;其右子树根结点的值大于等于该结点X的值，则此二叉树一定是二叉排序树。( )A.正确B.错误参考答案：B
西北工业大学2022年3月《数据结构》期末考核试题库及答案参考4
