《西北工业大学21秋《数据结构》综合测试题库答案参考78》由会员分享，可在线阅读，更多相关《西北工业大学21秋《数据结构》综合测试题库答案参考78（13页珍藏版）》请在金锄头文库上搜索。
1、西北工业大学21秋数据结构综合测试题库答案参考1. 下列序列中，不构成堆的是( )。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)参考答案：D2. 任何有向网的拓扑排序的结果是唯一的。( )A.正确B.错误参考答案：B3. 若要在单链表中的结点p之后插入一个结点s，则应执行的语句是( )。A.s-next=p-next; p-next=sB.p-next=s; s-next=p-nextC.p-next=s-next; s-next=pD.s-next=p;
2、 p-next=s-next参考答案：A4. 一棵树可以只有1个结点。( )A、错误B、正确参考答案：B5. 数据结构是指( )。A.数据元素的组织形式B.数据类型C.据存储结构D.数据定义参考答案：A6. 通用的处理哈希冲突的方法有( )。A、开放定址法B、再哈希法C、链地址法D、建立公共溢出区参考答案：ABCD7. 下面程序段的时间复杂度是( )。for(i=0; in; i+) for(j=1; jm; j+) Aij=0;A、O(n)B、O(m+n+1)C、O(m+n)D、O(m*n)参考答案：D8. 为使平均查找长度达到最小，当由关键字集合05，11，21，25，37，40，41，6
3、2，84构建二叉排序树时，第一个插入的关键字应为( )。A.5B.37C.41D.62参考答案：B9. 在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是( )。A.O(1)B.O(n)C.O(n2)D.O(nlog2n)参考答案：B10. 若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的( )。A.层次遍历算法B.前序遍历算法C.中序遍历算法D.后序遍历算法参考答案：C11. 栈和队列都是限制存取点的线性结构。( )A.正确B.错误参考答案：A12. 下列关于数据结构基本概念的叙述中，正确的是( )。A.数据的逻辑结构分为表结构和树结构B.数据的存储结
4、构分为线性结构和非线性结构C.数据元素是数据的基本单位D.结点是有独立含义的数据最小单位参考答案：C13. 数据项是数据的基本单位。( )A.正确B.错误参考答案：A14. 如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用( )。A.深度优先搜索算法B.广度优先搜索算法C.求最小生成树的prim算法D.拓扑排序算法参考答案：B15. 队列允许在队尾删除，在队头插入。( )A.正确B.错误参考答案：A16. 若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为( )。A.4B.5C.8D.9参考答案：C17. 若用一个大小为6的数组来实现循环队列，且当前rear和
5、front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为( )。A.1和5B.2和4C.4和2D.5和1参考答案：B18. 有向图用邻接矩阵表示后，顶点i的入度等于邻接矩阵中第i列的元素个数。( )A、错误B、正确参考答案：B19. 在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用( )。A.数据元素的相邻地址表示B.数据元素在表中的序号表示C.指向后继元素的指针表示D.数据元素的值表示参考答案：C20. 若有18个元素的有序表存放在一堆数组A19中，第一个元素放A1中，现进行二分查找，则查找A3的比较序列的下标依次为( )。A.1，2，3B
6、.9，5，2，3C.9，5，3D.9，4，2，3参考答案：D21. 归并排序是一种稳定的排序方法。( )A.正确B.错误参考答案：A22. 线性表中的所有元素都有一个前驱元素和后继元素。( )A.正确B.错误参考答案：A23. n个结点的线索二叉树上含有的线索数为( )。A.n-1B.n+1C.nD.2n参考答案：B24. 一个队列的入队序列是a、b、c、d，则队列的输出序列是( )。A.dcbaB.cbdaC.adcbD.abcd参考答案：D25. 已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为k。( )A、错误B、正确参考答案：A26.
7、 在二叉树中插入结点，则此二叉树便不再是二叉树了。( )A.正确B.错误参考答案：B27. 在一个长度为n的循环链表中，删除其元素值为x的结点的时间复杂度为O(n)。( )A、错误B、正确参考答案：B28. 某二叉树的前序和后序序列正好相同，则该二叉树一定是( )的二叉树。A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子参考答案：A29. B+树应用在( )文件系统中。A.顺序B.散列C.VSAMD.ISAM参考答案：C30. 最小生成树问题是构造带权连通图(网)的最小代价生成树。( )A.正确B.错误参考答案：A31. 分块查找的基本思想是首先在索引表中进行查
8、找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。( )A.正确B.错误参考答案：A32. 在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度(即x与元素的平均比较次数，假定查找每个元素的概率都相等)为( )。A.nB.n/2C.(n+1)/2D.(n-1)/2参考答案：C33. 下列描述中正确的是( )。A.选择合适的数据结构是解决应用问题的关键步骤B.线性表的逻辑顺序与存储顺序总是一致的C.每种数据结构都具备查找、插入和删除三种基本运算D.数据结构实质上包括逻辑结构和存储结构两方面的内容参考答案：A34. 采用顺序查找方法查找长度为n的线性表
9、时，每个元素的平均查找长度为( )。A.n/2B.nC.(n-1)/2D.(n+1)/2参考答案：D35. 对于线性表(7，34，55，25，64，46，20，10)进行散列存储时，若选用H(K)=K%9作为散列函数，则散列地址为1的元素有( )个。A.1B.2C.3D.4参考答案：D36. 下列排序中，某一趟结束后未必能选出一个元素放在其最终位置上的是( )。A.直接插入排序B.冒泡排序C.快速排序D.堆排序参考答案：A37. 对某二叉树进行前序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果为( )A.DBFEACB.DFEBCAC.BDFECAD.BDEFAC参考
10、答案：B38. 已知一个散列表如图所示，其散列函数为H(key)=key%11，采用二次探查法处理冲突，则下一个插入的关键字49的地址为( )。A.2B.3C.8D.9参考答案：C39. 数据的逻辑结构是指各数据元素之间的逻辑关系。( )A.正确B.错误参考答案：A40. 一个有向无环图的拓扑排序序列( )是唯一的。A.可能B.不一定C.三者均不对D.一定参考答案：B41. 假设一棵完全二叉树含1000个结点,则其中度为2的结点数为512个。( )A、错误B、正确参考答案：A42. 一棵含18个结点的二叉树的高度至少为( )。A、3B、4C、5D、6参考答案：C43. 在指定结点之前插入新结点
11、时，双链表比单链表更方便。( )A.正确B.错误参考答案：A44. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的( )。A.先序遍历B.中序遍历C.后序遍历D.按层遍历参考答案：C45. 队列的修改是按照先进先出的原则进行的。( )A、错误B、正确参考答案：B46. 采用邻接表存储的图的广度优先遍历算法类似于二叉树的( )。A.先序遍历B.中序遍历C.后序遍历D.按层遍历参考答案：D47. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是( )。A.单链表B.静态链表C.线性链表D.顺序存储结构参考答案：C48. Prim(普里姆)算法适用于求( )的网的最小生成树; k
12、ruskal(克鲁斯卡尔)算法适用于求( )的网的最小生成树。A.边稠密，边稀疏B.边稀疏，边稠密C.边稠密，边稠密D.边稀疏，边稀疏参考答案：A49. 下列程序段for(i=1; iA.O(1)B.O(0)C.O(1+n)D.O(n)参考答案：D50. 在计算机内实现递归算法时所需的辅助数据结构是( )。A、栈B、队列C、树D、图参考答案：A51. 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。( )A.正确B.错误参考答案：A52. 链式栈与顺序栈相比，一个比较明显的优点是( )A.插入操作更加方便B.通常不会出现栈满的情况C.不会出现栈空的情况D.删除操作更加方便参考答案：B53
13、. 算法有以下几种特性( )。A、有穷性B、确定性C、可行性D、输入和输出参考答案：ABCD54. 下列陈述中正确的是( )。A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分C.二叉树中必有度为2的结点D.二叉树中最多只有两棵子树，并且有左右之分参考答案：D55. 中序遍历二叉排序树可以得到一个有序的序列。( )A.正确B.错误参考答案：A56. 在无向图中，若从顶点a到顶点b存在通路，则称a与b之间是连通的。( )A、错误B、正确参考答案：B57. 线性链表不具有的特点是( )A.随机访问B.不必事先估计所需存储空间大小C.插入与删除时不必移动元素D.所需空间与线性表长度成正比参考答案：A58. 线性表的唯一存储形式就是链表。( )A.正确B.错误参考答案：A59. 对一棵有
