《西北工业大学22春《数据结构》综合作业二答案参考40》由会员分享,可在线阅读,更多相关《西北工业大学22春《数据结构》综合作业二答案参考40(13页珍藏版)》请在金锄头文库上搜索。
1、西北工业大学22春数据结构综合作业二答案参考1. 一个好的算法有( )设计要求。A、正确性B、可读性C、健壮性D、效率与低存储量要求参考答案:ABCD2. 如果在数据结构中每个数据元素只可能有一个直接前驱,但可以有多个直接后继,则该结构是( )。A.栈B.队列C.树D.图参考答案:C3. 假设一棵完全二叉树含1000个结点,则其中度为2的结点数为512个。( )A、错误B、正确参考答案:A4. 对任何一棵二叉树,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1。( )A、错误B、正确参考答案:B5. 设有100个关键字,用折半查找法进行查找时,最大比较次数为( )。A.7B.6C
2、.50D.25参考答案:A6. 下面程序段的时间复杂度是( )。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)参考答案:D7. 一个关键字序列为46,79,56,38,40,84,采用快速排序以位于最左位置的元素为基准而得到的第一次划分结果为( )A.38,46,79,56,40,84B.38,79,56,46,40,84C.40,38,46,56,79,84D.38,46,56,79,40,84参考答案:C8. 可以用队列实现数值转换算法。( )A.正确B.错误参考答案:A9. 有向图用邻接矩阵
3、表示后,顶点i的入度等于邻接矩阵中第i列的元素个数。( )A、错误B、正确参考答案:B10. 按照二叉树的定义,具有3个结点的二叉树有( )种。A.3B.4C.5D.6参考答案:C11. 平衡二叉树的平衡因子只可能是-1、0、1。( )A.正确B.错误参考答案:A12. 在指定结点之前插入新结点时,双链表比单链表更方便。( )A.正确B.错误参考答案:A13. 按层次次序将一颗有n个结点的完全二叉树的所有结点从1到n编号,当iA.2i-1B.2iC.2i+1D.不确定参考答案:B14. 空格串的长度是空格的个数。( )A、错误B、正确参考答案:B15. 如果最常用的操作是取第i个结点及其前驱,
4、则采用( )存储方式最节省时间。A.单链表B.双链表C.单循环链表D.顺序表参考答案:D16. 非空的双向循环链表中任何结点的前驱指针均不为空。( )A.正确B.错误参考答案:A17. 在无向图中,若从顶点a到顶点b存在通路,则称a与b之间是连通的。( )A、错误B、正确参考答案:B18. 队列的插入操作是在( )。A.队尾B.队头C.队列任意位置D.队头元素后参考答案:A19. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则节省时间的存储方式是( )。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表参考答案:A20. 对于哈希函数H(key)=key%
5、13,被称为同义词的关键字是( )。A、35和41B、23和39C、15和44D、25和51参考答案:D21. 二叉树中除叶结点外,任一结点X,其左子树根结点的值小于该结点X的值;其右子树根结点的值大于等于该结点X的值,则此二叉树一定是二叉排序树。( )A.正确B.错误参考答案:B22. 将森树转成二叉树,根结点没有右子树。( )A.正确B.错误参考答案:B23. 线性链表是通过( )方式表示元素之间的关系A.后继元素地址B.元素的存储顺序C.左、右孩子地址D.元素的相对存储位置参考答案:A24. 设结点A有3个兄弟结点且结点B为结点A的双亲结点,则结点B的度数为( )A.3B.4C.5D.1
6、参考答案:B25. 由于排序过程中涉及的存储器不同,可以将排序方法分为( )。A、稳定排序B、不稳定排序C、内部排序D、外部排序参考答案:CD26. 设有向图有n个顶点和e条边,采用领接表作为其存储表示,在进行拓扑排序时,总的计算时间为( )A.O(nlog2e)B.O(n+e)C.O(ne)D.O(n2)参考答案:B27. 在含100个结点的完全二叉树中,叶子结点的个数为36。( )A、错误B、正确参考答案:A28. 下列描述中正确的是( )。A.选择合适的数据结构是解决应用问题的关键步骤B.线性表的逻辑顺序与存储顺序总是一致的C.每种数据结构都具备查找、插入和删除三种基本运算D.数据结构实
7、质上包括逻辑结构和存储结构两方面的内容参考答案:A29. 数据结构是指( )。A.数据元素的组织形式B.数据类型C.据存储结构D.数据定义参考答案:A30. 四个元素进入队列QU的顺序是U、V、X、Y,进行DeQueue(QU,x)操作后,队头元素是( )。A.YB.XC.VD.U参考答案:C31. 用一维数组存储二叉树时,总是以前序遍历顺序存储结点。( )A.正确B.错误参考答案:B32. 数据结构是( )。A、一种数据类型B、数据的存储结构C、一组性质相同的数据元素的集合D、相互之间存在一种或多种特定关系的数据元素的集合参考答案:D33. 假设以S和X分别表示进栈和退栈操作,则对输入序列a
8、,b,c,d,e进行一系列栈操作SSXSXSSXXX之后,得到的输出序列为abbccddedc。( )A、错误B、正确参考答案:A34. 向顺序栈中压入新元素时,应当( )A.先移动栈顶位置,再存入元素B.先存入元素,再移动栈顶位置C.先后 次序无关紧要D.同时进行参考答案:A35. 算法分析的两个主要方面是( )。A.正确性与健壮性B.时间复杂度与空间复杂度C.数据复杂性与程序复杂性D.可读性与可用性参考答案:B36. 在指定结点之后插入新结点时,双链表比单链表更方便。( )A.正确B.错误参考答案:B37. 在计算机内实现递归算法时所需的辅助数据结构是( )。A、栈B、队列C、树D、图参考
9、答案:A38. 算法分析的两个主要方面是( )。A.空间复杂度和时间复杂度B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性参考答案:A39. 串S=”I am a worker的长度是10。( )A、错误B、正确参考答案:A40. 已知一个散列表如图所示,其散列函数为H(key)=key%11,采用二次探查法处理冲突,则下一个插入的关键字49的地址为( )。A.2B.3C.8D.9参考答案:C41. 数组的逻辑结构不同于下列( )的逻辑结构。A.线性表B.栈C.队列D.树参考答案:D42. 在对含n个结点的二叉树进行先序、中序和后序遍历时,其时间复杂度( )。A.都不相同B.完全
10、相同C.先序和中序相同,而与后序不同D.中序和后序相同,而与先序不同参考答案:B43. 带行表的三元组表是稀疏矩阵的一种( )。A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构参考答案:A44. 二叉树中必有度为2的结点。( )A、错误B、正确参考答案:A45. AVL树是一种平衡的二叉排序树,树中任一结点的( )A.左、右子树的高度均相同B.左、右子树高度差的绝对值不超过1C.左子树的高度均大于右子树的高度D.左子树的高度均小于右子树的高度参考答案:B46. 链接存储结构属静态存储方式。( )A.正确B.错误参考答案:B47. 散列函数有一个共同的性质,即函数值应当以下面的哪
11、一项来取其值域的每个值?( )A.最小概率B.最大概率C.平均概率D.同等概率参考答案:D48. 对于顺序存储的线性表,访问结点和增加、删除结点的时间复杂度为( )。A.O(n) O(n)B.O(n) O(1)C.O(1) O(n)D.O(1) O(1)参考答案:C49. 某二叉树的先序序列和后序序列正好相反,则该二叉树的特点一定是( )。A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子参考答案:B50. 若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点的个数是( )。A.9B.11C.15D.不能确定参考答案:C51. 链表不具备的特点是(
12、 )。A.可随机访问任意一个结点B.插入和删除不需要移动任何元素C.不必事先估计存储空间D.所需空间与其长度成正比参考答案:A52. 一个有向无环图的拓扑排序序列是( )。A.一定唯一的B.一定不唯一的C.不一定唯一的D.都不对参考答案:C53. 在目标串T0.n-1=“xwxxyxy”中,对模式串P0.m-1=“xy”进行子串定位操作的结果是( )。A.1B.2C.3D.5参考答案:C54. 在线性表的下列运算中,不改变数据元素之间结构关系的运算是( )。A、插入B、删除C、排序D、定位参考答案:D55. 结构的存储密度定义为数据本身所占的存储量与整个结构所占的存储量之比。( )A.正确B.
13、错误参考答案:A56. 若哈希表(散列表)的负载因子l,则可避免冲突的产生。( )A.正确B.错误参考答案:B57. 若采用邻接矩阵法存储一个n个顶点的无向图,则该邻接矩阵是一个( )。A.上三角矩阵B.稀疏矩阵C.对角矩阵D.对称矩阵参考答案:D58. 以下数据结构中,属于线性结构的是( )。A.广义表B.二叉树C.稀疏矩阵D.串参考答案:A59. 在任意一棵二叉树的前序序列和后序序列中,各叶子之间的相对次序关系( )。A.不一定相同B.都相同C.都不相同D.互为逆序参考答案:B60. 单链表中,增加一个头结点的目的是为了( )。A.使单链表至少有一个结点B.标识表结点中首结点的位置C.方便运算的实现D.说明单链表是线性表的链式存储