数据结构 第2次.doc

第2次作业一、单项选择题（本大题共60分，共 20 小题，每小题 3 分）1. 按克鲁斯卡尔算法建的最小生成树（ ）。A. B. 有多种 C. 不确定 2. 以下关于单链表的叙述中，错误的是（ ）。A. B. 在单链表中删除一个结点必须先找到其前驱结点 C. 在单链表中只能通过结点的next指针向后查找结点 D. 在单链表中查找第i个结点的时间复杂度是O(1) 3. 输入序列为ABC，可以变为CBA时，经过的栈操作为（ ）。A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop 4. 如图所示，可得到一个拓扑排序序列（? ）。 A. v1,v6,v4,v3,v2,v5 B. v1,v2,v6,v4,v3,v5 C. v1,v2,v6,v3,v4,v5 D. v1,v4,v6,v3,v2,v5 5. 下列排序方法中，哪一个是稳定的排序方法？（ 　） A. B. 堆排序 C. 希尔排序 D. 快速排序 6. 一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有（ ）结点。A. 2h B. 2h-1 C. 2h+1 D. h+1 7. 平衡二叉树的平衡因子的取值可能是（ ）。A. 1 B. 2 C. 3 D. 4 8. 一个有n个顶点的无向图最多有（ ）条边。A. n　B. n(n-1) C. n(n-1)/2 D. 2n 9. 在迷宫求解问题中，用（）作为转换过程中的数据存储结构。A. B. 栈 C. 队列 D. 单链表 10. 计算机算法指的是（ ）。A. B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 11. 基数排序是（ ）。A. B. 不稳定的 C. 看具体情况 D. 未知 12. 对（70.83.100.65.10.32.7.9）进行简单选择排序，排序后第一趟结果为（ ）。A. 7.83.100.65.10.32.70.9 B. 7.9.100.65.10.32.70.83 C. 7.9.10.65.100.32.70.83 D. 7.9.10.32.100.65.70.83 13. 对于一个有向图的逆邻接链表表示，第i 个链表中有x个结点，则顶点i的出度为（ ）。A. x B. x+1 C. x+i D. 14. 1348转化为8进制结果是（ ）。A. 2504 B. 2405 C. 4052 D. 2054 15. 二维数组A［10］［20］采用按行为主序的存储方式，每个元素占4个存储单元，若A［0］［0］的存储地址为300，则A［10］［10］的地址为（ ）。A. 700 B. 1120 C. 1180 D. 1140 16. 已知Head(Tail([Head(S),Head(Tail(Tail(S)))]))=[a]，广义表S满足上式，则S为（ ）(其中，方括号表示广义表，圆括号表示函数，如[a,b]表示由a,b 构成的广义表，而Head()表示取广义表的头部）。A. B. [[b,a],[a],[b]] C. [[a],[a,b],[b]] D. [[b],[b,a],[a]] 17. 若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为（ ）。A. B. X的右子树中最左的结点 C. X的左子树中最右结点 D. X的左子树中最右叶结点 18. 在对应于序列(12，5，8，15，25，10，30，7)的二叉排序树中查找30需要进行多少次比较。（ ）A. 1 B. 2 C. 3 D. 4 19. 对长度为155的顺序表在等概率情况下进行顺序查找的平均查找长度为（ ）。A. 78 B. 77.5 C. 155 D. 156 20. 对于三个结点的二叉树有多少种形态？ （ ）A. 3 B. 4 C. 5 D. 6 二、判断题（本大题共40分，共 20 小题，每小题 2 分）1. 判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用求最短路径的Dijkstra方法。2. 在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每