《西工大16秋《数据结构》在线作业》由会员分享,可在线阅读,更多相关《西工大16秋《数据结构》在线作业(8页珍藏版)》请在金锄头文库上搜索。
1、奥鹏 17 春西工大 16 秋数据结构在线作业一、单选题(共 40 道试题,共 80 分。 )1. 已知广义表 ls=(a,(b,c,d),e),运用 head 和 tail 函数取出 ls 中原子 b 的运算是( ) 。 A. head(head(ls) B. tail(head(ls) C. head(head(tail(ls) D. head(tail(ls) 正确答案: 2. 在双向循环链表中,在 p 指针所指向的结点前插入一个指针 q 所指向的新结点其修改 指针的操作是( ) 。 (双向链表的结点结构是 llink,data,rlink) A. p-llink=q;q-rlink=p
2、;p-llink-rlink=q;q-llink=q; B. p-llink=q; p-llink-rlink=q; q -rlink=p;q-llink= p-llink; C. p-llink=q; q-llink= p-llink; p-llink-rlink=q;p-llink=q; D. q-llink= p-llink;q-rlink=p; p-llink =q;p-llink=q; 正确答案: 3. 树形结构最适合用来描述( ) 。 A. 有序的数据元素 B. 无序的数据元素 C. 数据元素之间的具有层次关系的数据 D. 数据元素之间没有关系的数据 正确答案: 4. 下列程序段的
3、时间复杂度是( ) 。 for(i=0;i A. O(n) B. O(m+n+1) C. O(m+n) D. O(m*n) 正确答案: 5. 如果 T2 是由有序树 T 转换而来的二叉树,那么 T 中结点的后序就是 T2 结点的( ) 。 A. 先序 B. 中序 C. 后序 D. 层序 正确答案: 6. 折半查找法的时间复杂度是( ) 。 A. O(n*n) B. O(n) C. O(nlogn)D. O(logn) 正确答案: 7. 有一个 10 阶的对称矩阵 A,采用压缩存储方式,以行序为主序,A11 为第一个元素, 其存储地址为 1,每个元素占 1 个地址空间,则 A85 的地址为( )
4、 。 A. 13 B. 33 C. 18 D. 40 正确答案: 8. 表达式 INDEX(DATASTRUCTURE,STR)的运算结果是( ) 。 A. 5 B. 4 C. 6 D. 3 正确答案: 9. 若结点的存储地址与其关键字之间存在某种映射关系,则称这种存储结构为( ) 。 A. 顺序存储结构 B. 链式存储结构 C. 索引存储结构 D. 散列存储结构 正确答案: 10. 算法指的是( ) 。 A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 正确答案: 11. 数据表 A 中有 10000 个元素,如果仅要求求出其中最大的 10 个元素,则
5、采用( )排 序算法最节省时间。 A. 堆排序 B. 希尔排序 C. 快速排序 D. 直接选择排序 正确答案: 12. 已知广义表 a=(a,b,c),(d,e,f),从 a 中取出原子 e 的运算是( ) 。 A. tail(head(a) B. head(tail(a) C. head(tail(tail(head(a) D. head(tail(tail(a) 正确答案: 13. 广义表运算式 tail(a,b),(c,d)的结果为( ) 。 A. c,d B. (c,d) C. (c,d)D. d,c 正确答案: 14. 希尔排序的增量序列必须是( ) 。 A. 递增的 B. 随机的
6、C. 递减的 D. 非递减的 正确答案: 15. 设有两个串 p 和 q,其中 q 是 p 的字串,求 q 在 p 中首次出现的位置的算法称为( ) 。A. 求子串 B. 联接 C. 匹配 D. 求串长 正确答案: 16. 若串 S=syntax ,其字串的数目是( ) 。 A. 6 B. 21 C. 22 D. 7 正确答案: 17. 深度为 5 的二叉树至多有结点数为( ) 。 A. 16 B. 30 C. 31 D. 32 正确答案: 18. n 个顶点的强连通图至少有( )条边。 A. n-1 B. n C. 2n D. n(n-1) 正确答案: 19. 具有 65 个结点的完全二叉树
7、的高度为( ) 。 (根的层次号为 0) A. 8 B. 7 C. 6 D. 5 正确答案: 20. 在数据结构中,数据的逻辑结构可以分为( ) 。 A. 内部结构和外部结构 B. 线性结构和非线性结构 C. 紧凑结构和非紧凑结构 D. 动态结构和静态结构正确答案: 21. 在 n 个顶点的有向完全图中,边的总数为( )条。 A. n(n-1)/2 B. n(n-1) C. n(n-2) D. 2n 正确答案: 22. 适于对动态查找表进行高效率查找的组织结构是( ) 。 A. 有序表 B. 分块有序表 C. 三叉排序树 D. 线性链表 正确答案: 23. 对于一个具有 n 个顶点和 e 条边
8、的无向图,若采用邻接表表示,则所有顶点邻接表中 的结点总数为( ) 。 A. 2*n B. 2*e C. n D. e 正确答案: 24. 线索二叉树是一种( )结构。 A. 逻辑 B. 逻辑和存储 C. 物理 D. 线性 正确答案: 25. 计算机识别、存储和加工处理的对象被统称为( ) 。 A. 数据 B. 数据元素 C. 数据结构 D. 数据类型 正确答案: 26. 若待排序列已基本有序,要使它们完全有序,从关键码比较次数和移动次数考虑,应 当使用的排序方法是( ) 。 A. 归并排序 B. 直接插入排序 C. 直接选择排序 D. 快速排序 正确答案: 27. 在平衡二叉树中插入一个结点
9、后造成了不平衡,设最低的不平衡结点为 A,并已知 A 的左孩子的平衡因子为-1,右孩子的平衡因子为 0,则应作( )型调整以使其平衡。 A. LL B. LR C. RLD. RR 正确答案: 28. 一个广义表为(a,(a,b),d,e,(i,j),k),则该广义表的长度和深度分别为( ) 。 A. 5 和 3 B. 5 和 4 C. 4 和 3 D. 4 和 4 正确答案: 29. 设无向图 G 中顶点数为 n,图 G 最多( )有条边。 A. n B. n-1 C. n*(n-1)/2 D. n*(n-1) 正确答案: 30. 一个 n*n 的对称矩阵,如果以行或列为主序存入内存,则其容
10、量为( ) 。 A. n*n B. n*(n+1)/2 C. (n+1)*(n+1)/2 D. (n-1)*n/2 正确答案: 31. 为了方便的在线性结构的数据中插入一个数据元素,则其数据结构宜采用( ) 。 A. 顺序存储 B. 链式存储 C. 索引存储 D. 散列存储 正确答案: 32. 二维数组 a 的每个元素是由 6 个字符组成的串,行下标 i 的范围从 08,列下标 j 的 范围从 110。若 a 按行存放,元素 a8,5的起始地址与当 a 按列存放时的元素( )的起 始地址一致(每个字符占一个字节) 。 A. a8,5 B. a3,10 C. a5,8 D. a0,9 正确答案:
11、 33. 对表长为 n 的顺序表进行顺序查找,在查找概率相等的情况下,查找成功的平均查找 长度为( ) 。 A. (n-1)/2 B. n/2 C. (n+1)/2 D. n 正确答案: 34. 如果某图的邻接矩阵时对角线元素均为零的上三角矩阵,则此图是( ) 。 A. 有向完全图 B. 连通图C. 强连通图 D. 有向无环图 正确答案: 35. 对于哈希函数 H(key)=key%13,被称为同义词的关键字是( ) 。 A. 35 和 41 B. 23 和 39 C. 15 和 44 D. 25 和 51 正确答案: 36. 下述排序算法中,稳定的是( ) 。 A. 直接选择排序 B. 表插
12、入排序 C. 快速排序 D. 堆排序 正确答案: 37. 对于单链表形式的队列,队空的条件是( ) 。 A. F=R=null B. F=RC. Fnull 且 R=null D. R-F=1 正确答案: 38. 设有 5000 个元素,希望用最快速度挑选出其中前 10 个最大的元素,在以下的排序方 法中,采用那一种最好( ) 。 A. 快速排序 B. 堆排序 C. 归并排序 D. 基数排序和 shell 排序 正确答案: 39. 向顺序栈中压入新元素时,习惯上应当( ) 。 A. 先移动栈顶指针,再存入元素 B. 先存入元素,再移动栈顶指针 C. 先后次序无关紧要 D. 同时进行 正确答案:
13、 40. 数组 b1.10,-2.6,2.8以行优先的顺序存储,设第一个元素的首址是 100,每个元 素的长度为 3。元素 b5,0,7的存储首址为( ) 。 A. 900 B. 912 C. 910 D. 913 正确答案:西工大 16 秋数据结构在线作业二、判断题(共 10 道试题,共 20 分。 )1. 在链表中存储线性表中的第一个数据元素的结点是首元结点。 ( ) A. 错误 B. 正确 正确答案: 2. 根据线性表的链式存储结构,每个结点所含指针的个数,链表分为循环链表和普通链 表。 ( ) A. 错误 B. 正确 正确答案: 3. 若一个栈的输出序列是 1,2,3,.,n,输出序列
14、的第一个元素是 n,则第 i 个输出元素 是 n-i+1。 ( ) A. 错误 B. 正确 正确答案: 4. POP(PUSH(S,A) )的运算步骤是首先将元素 A 压入栈中,若栈 S 满,出现上溢现 象,否则将元素 A 压入栈顶,且元素个数加 1,然后做 POP(S)运算,将栈顶元素弹出, 且元素个数减一。 ( ) A. 错误 B. 正确 正确答案: 5. 图的生成树是不唯一的,一个连通图的生成树是一个最小连通子图,n 个顶点的生成树 有 n-1 条边,最小代价生成树是唯一的。 ( ) A. 错误 B. 正确 正确答案: 6. 算法的计算量的大小称为计算的复杂性。 ( ) A. 错误 B.
15、 正确 正确答案: 7. 模式串 P=abaabcac的 next 函数值序列为 01122313。 ( ) A. 错误 B. 正确 正确答案: 8. 线性表中元素数量基本稳定,且很少进行插入和删除,要求以最快的速度存取线性表 中的元素,此线性表宜采用链式存储结构。 ( ) A. 错误 B. 正确正确答案: 9. 被计算机加工的数据元素不是孤立无关的,它们彼此之间一般存在着某种联系通常将 数据元素间的这种联系关系称为结构。 ( ) A. 错误 B. 正确 正确答案: 10. 在顺序表中插入或删除一个元素,需要平均移动 n/2 个元素,具体移动的元素个数与 插入或删除元素的位置有关。 ( ) A. 错误 B. 正确 正确答案: