《西北工业大学21春《数据结构》在线作业二满分答案_53》由会员分享，可在线阅读，更多相关《西北工业大学21春《数据结构》在线作业二满分答案_53（13页珍藏版）》请在金锄头文库上搜索。
1、西北工业大学21春数据结构在线作业二满分答案1. 用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。A.逆拓扑有序B.拓扑有序C.无序的D.A和B参考答案：A2. 二叉树中必有度为2的结点。( )A、错误B、正确参考答案：A3. 线性表中的所有元素都有一个前驱元素和后继元素。( )A.正确B.错误参考答案：A4. 链表与顺序存储结构相比，在链表中进行插入、删除操作的效率高。( )A.正确B.错误参考答案：A5. 下列描述中正确的是( )。A.选择合适的数据结构是解决应用问题的关键步骤B.线性表的逻辑顺序与存储顺序总是一致的C.每种数据结构都具备查找、
2、插入和删除三种基本运算D.数据结构实质上包括逻辑结构和存储结构两方面的内容参考答案：A6. 不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。( )A.正确B.错误参考答案：A7. 一个关键字序列为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、的关键字经一趟二路归并排序后得到含有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，79，23，36，40，72，82参考答案：D10. 下面说法错误的是( )。 (1)算法原地工作的含义是指不需要任何额外的辅助空间; (2)在相同的规模n下，复杂度O(n)的算法在时间上总是优于复
4、杂度O(2n)的算法; (3)所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界; (4)同一个算法，实现语言的级别越高，执行效率就越低。A.(1)B.(1)，(2)C.(1)，(4)D.(3)参考答案：C11. 高度为5的完全二叉树中含有的结点数至少为( )。A、16B、17C、31D、32参考答案：A12. AOV网的含义是以顶点表示活动的网。( )A.正确B.错误参考答案：A13. 若要在单链表中的结点p之后插入一个结点s，则应执行的语句是( )。A.s-next=p-next; p-next=sB.p-next=s; s-next=p-nextC.p-next=s-next; s
5、-next=pD.s-next=p; p-next=s-next参考答案：A14. 单链表中，增加一个头结点的目的是为了( )。A.使单链表至少有一个结点B.标识表结点中首结点的位置C.方便运算的实现D.说明单链表是线性表的链式存储参考答案：C15. 设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域为空的结点有( )A.n-1B.nC.n+1D.n+2参考答案：B16. 链表中的表头指针与表头结点起到相同的作用。( )A.正确B.错误参考答案：B17. 归并排序是一种稳定的排序方法。( )A.正确B.错误参考答案：A18. 通常将链串的结点大小设置为大于1是为了(
6、)。A、提高串匹配效率B、提高存储密度C、便于插入操作D、便于删除操作参考答案：A19. 用有向无环图描述表达式(A+B)*(A+B)/A)，至少需要顶点的数目为( )。A.5B.6C.8D.9参考答案：A20. 线性表的链式存储结构是一种( )。A.随机存取的存储结构B.顺序存取的存储结构C.索引存取的存储结构D.Hash存取的存储结构参考答案：A21. 依次在初始为空的队列中插入元素X，Y，Z，W以后，紧接着作了两次删除操作，此时的队头元素是( )A.XB.YC.ZD.W参考答案：C22. 向二叉搜索树中插入一个元素时，其时间复杂度大致为( )A.O(log2n)B.O(n)C.O(1)D
7、.O(2n)参考答案：A23. 取顺序表的第i个元素的时间与i的大小无关。( )A.正确B.错误参考答案：A24. 二叉树中的叶子结点就是二叉树中没有左右子树的结点。( )A、错误B、正确参考答案：B25. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是( )。A.0B.1C.2D.3参考答案：B26. 向一个有127个元素原顺序表中插入一个新元素并保存原来顺序不变，平均要移动( )个元素。A.8B.63.5C.63D.7参考答案：B27. 四个元素进入队列QU的顺序是U、V、X、Y，进行DeQueue(QU，x)操作后，队头元素是( )。A.YB.XC.VD.U参考答案：C2
8、8. 不含任何字符的串称为空串。( )A、错误B、正确参考答案：B29. 以下( )不是队列的基本运算。A.从队尾插入一个新元素B.从队列中删除第i个元素C.判断一个队列是否为空D.读取队头元素的值参考答案：B30. 设根结点层次为1，某二叉树的结点前序序列和后序序列正好相反，则该二叉树一定是( )。A.高度等于其结点数B.空或只有一个结点C.任一结点无左子女D.任一结点无右子女参考答案：A31. 串是一种特殊的线性表，其特殊性体现在( )。A.数据元素是一个字符B.数据元素可以是多个字符C.可以顺序存储D.可以链接存储参考答案：A32. 含n个顶点的无向连通图中至少含有n条边。( )A、错误
9、B、正确参考答案：A33. 若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。A.(n-1)2B.n2C.(n+1)2D.n参考答案：C34. 已知完全二叉树T的第5层只有7个结点，则该树共有15个叶子结点。( )A、错误B、正确参考答案：A35. 链接存储结构属静态存储方式。( )A.正确B.错误参考答案：B36. 下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是( )。A.直接选择排序B.直接插入排序C.快速排序D.堆排序参考答案：C37. 在关键字序列(12，23，34，45，
10、56，67，78，89，91)中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为( )。A.4，4，3B.4，3，3C.3，4，4D.3，3，4参考答案：B38. 删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。( )A、错误B、正确参考答案：A39. 在一个长度为n的单链表L中，删除链表中*p的前驱结点的时间复杂度为O(n)。( )A、错误B、正确参考答案：B40. 数据元素及其关系在计算机存储器内的表示，称为数据的( )。A.逻辑结构B.存储结构C.线性结构D.非线性结构参考答案：B41. 已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的
11、叶子结点，则该树中含有的叶子结点的数目为k。( )A、错误B、正确参考答案：A42. 在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为( )。A.O(n)B.O(n+e)C.O(n2)D.O(n3)参考答案：B43. 用ISAM组织文件适合于( )。A.磁盘B.磁带C.外存储器D.光盘参考答案：A44. 在目标串T0.n-1=“xwxxyxy”中，对模式串P0.m-1=“xy”进行子串定位操作的结果是( )。A.1B.2C.3D.5参考答案：C45. 若链串结点中的指针占4个字节，每个字符占1个字节，则结点大小为2的链串的存储密度为2/6。( )A、错误B、正确参考答案：B46.
12、 二叉排序树上左子树上所有结点的值均小于它的根结点的值。( )A.正确B.错误参考答案：A47. 设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有( )个空指针域。A.2m-1B.2mC.2m+1D.4m参考答案：B48. 两个串相等的充分必要条件是两个串的长度相等且字母相同。( )A、错误B、正确参考答案：B49. 无向图中一个顶点的度是指图中( )。A、通过该顶点的简单路径数B、与该顶点相邻接的顶点数C、通过该顶点的回路数D、与该顶点连通的顶点数参考答案：B50. 若采用邻接矩阵法存储一个N个顶点的无向图，则该邻接矩阵是一个( )A.队头元素的前一个位置B.队
13、头元素的后一个位置C.队头元素位置D.队尾元素的前一位置参考答案：A51. 在一个单链表中，若删除*p结点的后继结点，则执行操作( )。A.q=p-next; p-next=q-next; free(q)B.p=p-next; p-next=p-next-next; free(p)C.p-next=q-next; free(p-next)D.p=p-next-next; free(p-next)参考答案：A52. 稀疏矩阵压缩存储后，必会失去随机存取功能。( )A.正确B.错误参考答案：A53. 产生冲突现象的两个关键字称为该散列函数的同义字。( )A、错误B、正确参考答案：B54. 邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。( )A.正确B.错误参考答案：B55. 一个有向图的邻接表和逆邻接表中结点的个数可能不等。( )A.正确B.错误
