《西北工业大学21秋《数据结构》在线作业二答案参考62》由会员分享，可在线阅读，更多相关《西北工业大学21秋《数据结构》在线作业二答案参考62（13页珍藏版）》请在金锄头文库上搜索。
1、西北工业大学21秋数据结构在线作业二答案参考1. 右图中的拓扑序列为( )A.C1，C2，C6，C7，C5，C4，C3B.C1，C2，C6，C3，C4，C5，C7C.C1，C4，C2，C3，C5，C6，C7D.C5，C7，C4，C1，C2，C6，C3参考答案：D2. 线性表的唯一存储形式就是链表。( )A.正确B.错误参考答案：A3. 假设以S和X分别表示进栈和退栈操作，则对输入序列a，b，c，d，e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为abbccddedc。( )A、错误B、正确参考答案：A4. 假设三维数组A1098按行优先顺序存储，若每个元素占3个存储单元，且首地址为
2、100，则元素A987的存储地址是501。( )A、错误B、正确参考答案：A5. 下面哪些方法可以判断出一个有向图是否有环(回路)?( )A.求最短路径B.求关键路径C.拓扑排序D.广(宽)度优先遍历参考答案：C6. 由带权为9，2，5，7的四个叶子结点构造一颗哈夫曼树，该树的带权路径长度为( )。A.23B.37C.46D.44参考答案：D7. 对线性表进行二分查找时，要求线性表必须( )。A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且结点按关键字有序排列D.以链接方式存储，且结点按关键字有序排列参考答案：C8. 链式栈与顺序栈相比，一个比较明显的优点是( )A.插入操作更加方便
3、B.通常不会出现栈满的情况C.不会出现栈空的情况D.删除操作更加方便参考答案：B9. 对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。( )A、错误B、正确参考答案：B10. 已知指针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参考答案：A11. 满二叉树一定是完全二叉
4、树，完全二叉树不一定是满二叉树。( )A.正确B.错误参考答案：A12. head指向的带表头结点的单链表为空的判定条件是( )。A.head-next=headB.head-next=NULLC.head=NULLD.head!=NULL参考答案：B13. 在一个长度为n的单链表L中，删除链表中*p的前驱结点的时间复杂度为O(n)。( )A、错误B、正确参考答案：B14. 不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。( )A.正确B.错误参考答案：A15. 二维数组A的每个元素是由6个字符组成的串，其行下标i=0，1，8，列下标为j=1，2，10。设
5、每个字符占一个字节，若按行先存储，元素A8，5的起始地址与A按列存储时起始地址相同的元素是( )。A.A8，5B.A3，10C.A5，8D.A0，9参考答案：B16. 向二叉搜索树中插入一个元素时，其时间复杂度大致为( )A.O(log2n)B.O(n)C.O(1)D.O(2n)参考答案：A17. 两个串相等的充分必要条件是两个串的长度相等且字母相同。( )A、错误B、正确参考答案：B18. 以下数据结构中，属于线性结构的是( )。A.广义表B.二叉树C.稀疏矩阵D.串参考答案：A19. 一个加权的无向连通图的最小生成树( )。A.有一颗或多颗B.只有一颗C.一定有多颗D.可能不存在参考答案：
6、A20. 插入、删除只能在同一端进行的线性表，称为( )。A.队列B.栈C.循环队列D.循环栈参考答案：B21. 在一个图中所有顶点的度数之和等于所有边数的( )倍。A.1/2B.2C.1D.4参考答案：B22. 一个有向无环图的拓扑排序序列( )是唯一的。A.可能B.不一定C.三者均不对D.一定参考答案：B23. B+树应用在( )文件系统中。A.顺序B.散列C.VSAMD.ISAM参考答案：C24. 程序一定是算法。( )A.正确B.错误参考答案：B25. 串是一种特殊的线性表，其特殊性体现在( )。A.数据元素是一个字符B.数据元素可以是多个字符C.可以顺序存储D.可以链接存储参考答案：
7、A26. Prim(普里姆)算法适用于求( )的网的最小生成树; kruskal(克鲁斯卡尔)算法适用于求( )的网的最小生成树。A.边稠密，边稀疏B.边稀疏，边稠密C.边稠密，边稠密D.边稀疏，边稀疏参考答案：A27. 一个队列的入队序列是1、2、3、4，则队列的首次输出元素是( )。A.1B.2C.3D.4参考答案：A28. 有关二叉树下列说法正确的是( )。A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为2参考答案：B29. 健壮的算法不会因非法的输人数据而出现莫名其妙的状态。( )A.正确B.错误参考答案：A30. n个顶
8、点的连通图至少有( )条边。A.n-1B.nC.n+1D.0参考答案：A31. 在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是堆排序。( )A、错误B、正确参考答案：A32. 结构就是用户定义的，( )的一个集合体。参考答案：不同数据类型33. 线性表中的所有元素都有一个前驱元素和后继元素。( )A.正确B.错误参考答案：A34. AVL树是一种平衡的二叉排序树，树中任一结点的( )A.左、右子树的高度均相同B.左、右子树高度差的绝对值不超过1C.左子树的高度均大于右子树的高度D.左子树的高度均小于右子树的高度参考答案：B35. 将两个各有n个元素的有序表归并成一个有序表
9、，其最少的比较次数是( )。A.nB.2n-1C.2nD.n-1参考答案：A36. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( )A.正确B.错误参考答案：B37. 已知循环队列的存储空间为数组data21，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为( )。A.5B.6C.16D.17参考答案：C38. 设s1=“abc”，则strlen(s1)=( )。A.3B.2C.1D.0参考答案：A39. 在关键字序列(12，23，34，45，56，67，78，89，91)中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为( )。A.4，4，3B
10、.4，3，3C.3，4，4D.3，3，4参考答案：B40. 任何有向网的拓扑排序的结果是唯一的。( )A.正确B.错误参考答案：B41. 连通网的最小生成树是其所有生成树中( )。A.顶点集最小的生成树B.边集最小的生成树C.顶点权值之和最小的生成树D.边的权值之和最小的生成树参考答案：D42. 线性链表是通过( )方式表示元素之间的关系A.后继元素地址B.元素的存储顺序C.左、右孩子地址D.元素的相对存储位置参考答案：A43. 在长度为n的顺表表的第i个位置上插入一个元素(1in+1)，元素的移动次数为( )。A.n-i+1B.n-iC.iD.i-1参考答案：C44. 在线性表的下列运算中，
11、不改变数据元素之间结构关系的运算是( )。A、插入B、删除C、排序D、定位参考答案：D45. 已知广义表LS=(a，b，c)，(d，e，f)，运算head和tail函数取出元素e的运算是( )。A.head(tail(LS)B.tail(head(LS)C.head(tail(head(tail(LS)D.head(tail(tail(head(LS)参考答案：C46. 链表不具备的特点是( )。A.可随机访问任意一个结点B.插入和删除不需要移动任何元素C.不必事先估计存储空间D.所需空间与其长度成正比参考答案：A47. 算法分析的两个主要方面是( )。A.正确性与健壮性B.时间复杂度与空间复
12、杂度C.数据复杂性与程序复杂性D.可读性与可用性参考答案：B48. 若一棵满三叉树中含有121个结点，则该树的深度为6。( )A、错误B、正确参考答案：A49. 深度为k的二叉树至多有2k-1个结点。( )A、错误B、正确参考答案：A50. 在存储数据时，通常不仅要存储各数据元素的值，而且还要存储( )。A.数据的处理方法B.数据元素的类型C.数据元素之间的关系D.数据的存储方法参考答案：C51. 数据的存储结构是数据的逻辑结构在计算机存储器上的实现，它是依赖于计算机的。( )A.正确B.错误参考答案：A52. 下列描述中正确的是( )。A.选择合适的数据结构是解决应用问题的关键步骤B.线性表
13、的逻辑顺序与存储顺序总是一致的C.每种数据结构都具备查找、插入和删除三种基本运算D.数据结构实质上包括逻辑结构和存储结构两方面的内容参考答案：A53. 中序遍历的递归算法平均空间复杂度为( )。A.2(n)B.n(2)C.0(n)D.2n参考答案：C54. 假设以行优先顺序存储三维数组A567，其中元素A000的地址为1100，并且每个元素占2个存储单元，则A432的地址是1264。( )A、错误B、正确参考答案：A55. 若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为O(n)。( )A、错误B、正确参考答案：A56. 设二维数组A0.m-10.n-1按行优先顺序存储且每个元素占c个单元，则元素Aij的地址为( )。A.LOC(A00)+
