西北工业大学22春《数据结构》在线作业二及答案参考23

《西北工业大学22春《数据结构》在线作业二及答案参考23》由会员分享，可在线阅读，更多相关《西北工业大学22春《数据结构》在线作业二及答案参考23（13页珍藏版）》请在装配图网上搜索。

1、西北工业大学22春数据结构在线作业二及答案参考1. 链接存储结构属动态存储方式。( )A.正确B.错误参考答案：A2. 给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。( )A、错误B、正确参考答案：A3. 字符串“sgabacbadfgbacst”中存在有6个与字符串“ba”相同的子串。( )A、错误B、正确参考答案：A4. 设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数为( )A.3B.4C.5D.1参考答案：B5. 若有向图的邻接矩阵中，主对角线以下元素均为零，则该图的拓扑有序序列( )。A.存在B.可能不存在C.不存在D.不一定存在参考答案：A6. 在下列

2、排序算法中，哪一个算法的时间复杂度与记录初始排列无关?( )A.直接选择排序B.直接插入排序C.快速排序D.冒泡排序参考答案：A7. 程序一定是算法。( )A.正确B.错误参考答案：B8. 一组记录的关键字经一趟二路归并排序后得到含有5个长度为2的有序表如下：25，48，16，35，79，82，23，40，36，72，在此基础上按二路归并排序方法再对该序列进行一趟归并后的结果为( )A.16，25，35，48，23，40，79，82，36，72B.16，25，35，48，23，40，79，82，72，36C.16，25，48，35，79，82，23，36，40，72D.16，25，35，48，

3、79，23，36，40，72，82参考答案：D9. 对于3个结点a、b、c，可构成不同的二叉树的棵数为( )。A.32B.30C.28D.24参考答案：B10. 下列四种基本的逻辑结构中，数据元素之间关系最弱的是( )。A.集合B.线性结构C.树形结构D.图状结构参考答案：A11. 中序遍历二叉排序树可以得到一个有序的序列。( )A.正确B.错误参考答案：A12. 在长度为n的顺表表的第i个位置上插入一个元素(1in+1)，元素的移动次数为( )。A.n-i+1B.n-iC.iD.i-1参考答案：C13. 在计算机内实现递归算法时所需的辅助数据结构是( )。A、栈B、队列C、树D、图参考答案：

4、A14. 从未排序序列中挑选元素，并将其依次插入已排序序列(初始时为空)的一端的方法，称为( )。A.希尔排序B.归并排序C.插入排序D.选择排序参考答案：D15. 算法分析的两个主要方面是( )。A.正确性与健壮性B.时间复杂度与空间复杂度C.数据复杂性与程序复杂性D.可读性与可用性参考答案：B16. 在指定结点之后插入新结点时，双链表比单链表更方便。( )A.正确B.错误参考答案：B17. 数据的逻辑结构描述数据元素之间的逻辑关系，与存储方式无关。( )A、错误B、正确参考答案：B18. 由于排序过程中涉及的存储器不同，可以将排序方法分为( )。A、稳定排序B、不稳定排序C、内部排序D、外

5、部排序参考答案：CD19. 设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有( )个空指针域。A.2m-1B.2mC.2m+1D.4m参考答案：B20. 线性表的链接实现有利于( )运算。A.插入B.读表元C.查找D.定位参考答案：A21. 数据结构中所定义的数据元素，是用于表示数据的( )。A.最小单位B.最大单位C.基本单位D.不可分割的单位参考答案：C22. 稀疏矩阵压缩存储后，必会失去随机存取功能。( )A.正确B.错误参考答案：A23. 数据项是数据的基本单位。( )A.正确B.错误参考答案：A24. 在一个长度为n的单链表L中，删除链表中*p的前驱结点

6、的时间复杂度为O(n)。( )A、错误B、正确参考答案：B25. 与单链表相比，双链表的优点之一是( )。A.插入、删除操作更简单B.可以进行随机访问C.可以省略表头指针或表尾指针D.顺序访问相邻结点更灵活参考答案：C26. 设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为( )。A.21B.23C.41D.62参考答案：C27. 高度为5的完全二叉树中含有的结点数至少为( )。A、16B、17C、31D、32参考答案：A28. 向二叉搜索树中插入一个元素时，其时

7、间复杂度大致为( )A.O(log2n)B.O(n)C.O(1)D.O(2n)参考答案：A29. 基数排序需要进行关键字的比较。( )A.正确B.错误参考答案：B30. 栈下溢是指在栈空时进行出栈操作。( )A、错误B、正确参考答案：B31. 删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。( )A、错误B、正确参考答案：A32. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是( )。A.单链表B.静态链表C.线性链表D.顺序存储结构参考答案：C33. 若有18个元素的有序表存放在一堆数组A19中，第一个元素放A1中，现进行二分查找，则查找A3的比较序列

8、的下标依次为( )。A.1，2，3B.9，5，2，3C.9，5，3D.9，4，2，3参考答案：D34. 数组的逻辑结构不同于下列( )的逻辑结构。A.线性表B.栈C.队列D.树参考答案：D35. 在下列各种文件中，不能进行顺序查找的文件是( )。A.顺序文件B.索引文件C.散列文件D.多重表文件参考答案：C36. 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。( )A.正确B.错误参考答案：A37. 若哈希表(散列表)的负载因子l，则可避免冲突的产生。( )A.正确B.错误参考答案：B38. 取顺序表的第i个元素的时间与i的大小无关。( )A.正确B.错误参考答案：A39. 若一棵二叉

9、树有11个叶子结点，则该二叉树中度为2的结点个数是( )。A.10B.11C.12D.15参考答案：A40. 设有以下四种排序方法，则( )的空间复杂度最大。A.冒泡排序B.快速排序C.堆排序D.希尔排序参考答案：B41. n个顶点的连通图至少有( )条边。A.n-1B.nC.n+1D.0参考答案：A42. 设根结点层次为1，某二叉树的结点前序序列和后序序列正好相反，则该二叉树一定是( )。A.高度等于其结点数B.空或只有一个结点C.任一结点无左子女D.任一结点无右子女参考答案：A43. 一棵树可以只有1个结点。( )A、错误B、正确参考答案：B44. 在无向图中，若从顶点a到顶点b存在通路，

10、则称a与b之间是连通的。( )A、错误B、正确参考答案：B45. 顺序查找法适合于存储结构为( )的线性表。A.散列存储B.顺序存储或链式存储C.压缩存储D.索引存储参考答案：B46. 顺序存储结构是通过( )表示元素之间的关系的;链式存储结构是通过( )表示元素之间的关系的。A.物理上相邻，指针B.逻辑上相邻，指针C.逻辑上相临，结点D.物理上相邻，结点参考答案：A47. 若让元素1，2，3依次进栈，则出栈次序不可能出现种情况( )A.3，2，1B.2，1，3C.3，1，2D.1，3，2参考答案：C48. 对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的左孩子的编号为98。

11、( )A、错误B、正确参考答案：B49. 按照二叉树的定义，具有3个结点的二叉树有( )种。A.3B.4C.5D.6参考答案：C50. 含n个顶点的无向连通图中至少含有n条边。( )A、错误B、正确参考答案：A51. 对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。( )A、错误B、正确参考答案：B52. 广义表(a，b，c，d)的表头是( )。A.(b，c，d)B.(a，b，c，d)C.aD.(a)参考答案：B53. 线性链表不具有的特点是( )A.随机访问B.不必事先估计所需存储空间大小C.插入与删除时不必移动元素D.所需空间与线性表长度成正比参考答案：A

12、54. 已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为( )。A、q-next=s-next; s-next=pB、s-next=p; q-next=s-nextC、p-next=s-next; s-next=qD、s-next=q; p-next=s-next参考答案：A55. 在长度为n的顺序表的第i(1in+1)个位置上插入一个元素，元素的移动次数为( )。A、n-i+1B、n-iC、iD、i-1参考答案：A56. 设串s1=Data Structures with Java，s2=it，则子串定位函数index(s1,s2)的值为( )。A、15B、16C、17D、18参考答案：D57. 线性表中的所有元素都有一个前驱元素和后继元素。( )A.正确B.错误参考答案：A58. 具有65个结点的完全二叉树其深度为(根的层次号为1)( )。A.8B.7C.6D.5参考答案：B59. 完全二叉树中的叶子结点只可能在最后两层中出现。( )A.正确B.错误参考答案：A60. 在有向图中，以顶点v为终点的边的数目称为v的入度。( )A、错误B、正确参考答案：B