《西北工业大学22春《数据结构》综合作业一答案参考22》由会员分享，可在线阅读，更多相关《西北工业大学22春《数据结构》综合作业一答案参考22（13页珍藏版）》请在金锄头文库上搜索。
1、西北工业大学22春数据结构综合作业一答案参考1. 设某完全无向图中有n个顶点，则该完全无向图中有( )条边。A.n(n-1)/2B.n(n-1)C.n2D.n2-1参考答案：A2. 如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是( )。A.栈B.队列C.树D.图参考答案：C3. 若链串结点中的指针占4个字节，每个字符占1个字节，则结点大小为2的链串的存储密度为2/6。( )A、错误B、正确参考答案：B4. 最佳二叉排序树是AVL树(平衡二叉排序树)。( )A.正确B.错误参考答案：A5. 数据元素及其关系在计算机存储器内的表示，称为数据的( )。A.逻辑结构
2、B.存储结构C.线性结构D.非线性结构参考答案：B6. 二叉树的叶结点，在前序遍历、中序遍历和后序遍历下皆以相同的相对位置出现。( )A.正确B.错误参考答案：A7. 广义表(a，b，c，d)的表头是( )。A.(b，c，d)B.(a，b，c，d)C.aD.(a)参考答案：B8. 二叉树中的叶子结点就是二叉树中没有左右子树的结点。( )A、错误B、正确参考答案：B9. 在有向图中，以顶点v为终点的边的数目称为v的入度。( )A、错误B、正确参考答案：B10. 若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。A.(n-1)2B.
3、n2C.(n+1)2D.n参考答案：C11. 若哈希表(散列表)的负载因子l，则可避免冲突的产生。( )A.正确B.错误参考答案：B12. 任何一个递归过程都可以转换成非递归过程。( )A.正确B.错误参考答案：A13. 若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列3，2，5，6，4，1。( )A.正确B.错误参考答案：A14. 不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。( )A.正确B.错误参考答案：A15. 无向图的邻接矩阵可用一维数组存储。( )A.正确B.错误参考答案：A16. 已知完全二叉树T的第5层只有7个结点，则该树共有15个叶子结点。
4、( )A、错误B、正确参考答案：A17. n个顶点的强连通图中至少含有( )。A.n-1条有向边B.n条有向边C.n(n-1)/2条有向边D.n(n-1)条有向边参考答案：B18. 带行表的三元组表是稀疏矩阵的一种( )。A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构参考答案：A19. 字符串“sgabacbadfgbacst”中存在有6个与字符串“ba”相同的子串。( )A、错误B、正确参考答案：A20. 一个队列的入队序列是1、2、3、4，则队列的首次输出元素是( )。A.1B.2C.3D.4参考答案：A21. 如果入栈序列是1，3，5，97，99，且出栈序列的第一个元素
5、为99，则出栈序列中第30个元素为47。( )A、错误B、正确参考答案：B22. 设某棵二叉树中有2000个结点，则该二叉树的最小高度为( )。A.9B.10C.11D.12参考答案：C23. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为( )。A.1和5B.2和4C.4和2D.5和1参考答案：B24. 若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为( )。A.4B.5C.8D.9参考答案：C25. 若一棵满三叉树中含有121个结点，则该树的深度为6。( )
6、A、错误B、正确参考答案：A26. 已知指针p指向某单链表中的一个结点，则判别该结点有且仅有一个后继结点的条件是p-next-next=null。( )A、错误B、正确参考答案：B27. n个顶点的连通图至少有( )条边。A.n-1B.nC.n+1D.0参考答案：A28. 在指定结点之后插入新结点时，双链表比单链表更方便。( )A.正确B.错误参考答案：B29. 在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为( )。A.O(n)B.O(n+e)C.O(n2)D.O(n3)参考答案：B30. 通常将链串的结点大小设置为大于1是为了( )。A、提高串匹配效率B、提高存储密度C、便于
7、插入操作D、便于删除操作参考答案：A31. 采用邻接表存储的图的广度优先遍历算法类似于二叉树的( )。A.先序遍历B.中序遍历C.后序遍历D.按层遍历参考答案：D32. 用链表表示线性表的优点是( )A.便于随机存取B.花费的存储空间比顺序表少C.便于插入与删除D.数据元素的物理顺序与逻辑顺序相同参考答案：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. 已知广义表LS=(a，b，c)，(d，e，f
8、)，运算head和tail函数取出元素e的运算是( )。A.head(tail(LS)B.tail(head(LS)C.head(tail(head(tail(LS)D.head(tail(tail(head(LS)参考答案：C35. 若有序表的关键字序列为(b，c，d，e，f，g，q，r，s，t)，则在二分查找关键字b的过程中，先后进行比较的关键字依次为( )。A.f，c，bB.f，d，bC.g，c，bD.g，d，b参考答案：A36. 程序一定是算法。( )A.正确B.错误参考答案：B37. 设某算法的问题规模函数f(n)=300n2+8000n+900，则它的渐进时间复杂度为( )A.O(
9、n3)B.O(n2)C.O(n)D.O(1)参考答案：B38. 下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序?( )A.堆B.哈夫曼树C.二叉排序树D.AVL树参考答案：A39. 对线性表进行二分查找时，要求线性表必须( )。A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且结点按关键字有序排列D.以链接方式存储，且结点按关键字有序排列参考答案：C40. 为使平均查找长度达到最小，当由关键字集合05，11，21，25，37，40，41，62，84构建二叉排序树时，第一个插入的关键字应为( )。A.5B.37C.41D.62参考答案：B41. 下
10、列关于数据结构基本概念的叙述中，正确的是( )。A.数据的逻辑结构分为表结构和树结构B.数据的存储结构分为线性结构和非线性结构C.数据元素是数据的基本单位D.结点是有独立含义的数据最小单位参考答案：C42. 数据结构是带有结构的数据元素的集合。( )A.正确B.错误参考答案：A43. 顺序存储结构是通过( )表示元素之间的关系的;链式存储结构是通过( )表示元素之间的关系的。A.物理上相邻，指针B.逻辑上相邻，指针C.逻辑上相临，结点D.物理上相邻，结点参考答案：A44. 快速排序方法在( )情况下最不利于发挥其长处。A.被排序的数据量太大B.被排序数据中含有多个相同值C.被排序数据已基本有序
11、D.被排序数据数目为奇数参考答案：C45. 在一个长度为n的循环链表中，删除其元素值为x的结点的时间复杂度为O(n)。( )A、错误B、正确参考答案：B46. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是( )。A.单链表B.静态链表C.线性链表D.顺序存储结构参考答案：C47. 已知循环队列的存储空间为数组data21，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为( )。A.5B.6C.16D.17参考答案：C48. 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。( )A.正确B.错误参考答案：B49. 广义表运算式tail(a，b)
12、，(c，d)的操作结果是( )。A.dB.c，dC.(c，d)D.(c，d)参考答案：D50. 在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针P所指向的结点，则执行( )A.q-next=p-next;p=qB.p-next=q-next;q=pC.q-next=p-next;p-next=qD.p-next=q-next;q-next=p参考答案：D51. 完全二叉树中的叶子结点只可能在最后两层中出现。( )A.正确B.错误参考答案：A52. 已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为( )。A.DEBAFCB.DEFBCAC.DEBCFAD.DE
13、BFCA参考答案：B53. 链接存储结构属动态存储方式。( )A.正确B.错误参考答案：A54. 设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数为( )A.3B.4C.5D.1参考答案：B55. 对无序表用折半查找比顺序查找快。( )A.正确B.错误参考答案：B56. 链接存储结构属静态存储方式。( )A.正确B.错误参考答案：B57. 在长度为n的顺序表的第i(1in+1)个位置上插入一个元素，元素的移动次数为( )。A、n-i+1B、n-iC、iD、i-1参考答案：A58. 顺序查找法适合于存储结构为( )的线性表。A.散列存储B.顺序存储或链式存储C.压缩存储D.索引存储参考答案：B59. 算法分析的两个主要方面是( )。A.正确性与健壮性B.时间复杂度与空间复
