西工大17春《数据结构》在线作业

西工大17春《数据结构》在线作业一、单选题（共 40 道试题，共 80 分。

）1. 设无向图G中顶点数为n，图G最多（）有条边。

A. nB. n-1C. n*(n-1)/2D. n*(n-1)正确答案：A2. 如果某图的邻接矩阵时对角线元素均为零的上三角矩阵，则此图是（）。

A. 有向完全图B. 连通图C. 强连通图D. 有向无环图正确答案：D3. 常采用下面几种方式解决散列法中出现的冲突问题（）。

A. 数字分析法、除余法、平均取中法B. 数字分析法、除余法、线性探测法C. 数字分析法、线性探测法、散列多重法D. 线性探测法、散列多重法、链地址法正确答案：D4. 在n个顶点的有向完全图中，边的总数为（）条。

A. n(n-1)/2B. n(n-1)C. n(n-2)D. 2n正确答案：B5. 有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主序，A11为第一个元素，其存储地址为1，每个元素占1个地址空间，则A85的地址为（）。

A. 13B. 33C. 18D. 40正确答案：B6. 在有n个结点的二叉链表中，值为空的链域个数为（）。

A. n-1B. 2n-1C. n+1D. 2n+1正确答案：C7. 串是一种特殊的线性表，其特殊性体现在（）。

A. 串中所含不同字母的个数B. 串中所含字符的个数C. 串中所含不同字符的个数D. 串中所含非空格字符的个数正确答案：B8. 已知广义表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))正确答案：C9. 下面关于串的叙述中，哪一个是不正确的（）。

A. 串是字符的有限序列B. 空串是由空格构成的串C. 模式匹配是串的一种重要运算D. 串既可以采用顺序存储，也可以采用链式存储正确答案：B10. 在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）。

A. eB. 2e正确答案：B11. 希尔排序的增量序列必须是（）。

A. 递增的B. 随机的C. 递减的D. 非递减的正确答案：C12. 为了方便的在线性结构的数据中插入一个数据元素，则其数据结构宜采用（）。

A. 顺序存储B. 链式存储C. 索引存储D. 散列存储正确答案：B13. 折半查找法的时间复杂度是（）。

A. O(n*n)B. O(n)C. O(nlogn)D. O(logn)正确答案：D14. 对于哈希函数H（key）=key%13，被称为同义词的关键字是（）。

A. 35和41B. 23和39C. 15和44D. 25和51正确答案：D15. 设有两个串p和q，其中q是p的字串，求q在p中首次出现的位置的算法称为（）。

A. 求子串B. 联接C. 匹配D. 求串长正确答案：C16. 计算机识别、存储和加工处理的对象被统称为（）。

A. 数据B. 数据元素C. 数据结构D. 数据类型正确答案：A17. 散列表的平均查找长度（）。

A. 与处理冲突方法有关而与表的长度无关B. 与处理冲突方法无关而与表的长度有关C. 与处理冲突方法有关且与表的长度有关D. 与处理冲突方法无关且与表的长度无关正确答案：C18. 已知广义表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)))正确答案：D19. 若串S=’syntax’，其字串的数目是（）。

A. 6B. 21C. 22D. 7正确答案：C20. 线索二叉树是一种（）结构。

A. 逻辑B. 逻辑和存储C. 物理D. 线性正确答案：C21. 设有5000个元素，希望用最快速度挑选出其中前10个最大的元素，在以下的排序方法中，采用那一种最好（）。

A. 快速排序B. 堆排序C. 归并排序D. 基数排序和shell排序正确答案：B22. n个顶点的强连通图至少有（）条边。

A. n-1B. nC. 2nD. n(n-1)正确答案：A23. 对于单链表形式的队列，队空的条件是（）。

A. F=R=nullB. F=RC. F≠null且R=nullD. R-F=1正确答案：B24. 对表长为n的顺序表进行顺序查找，在查找概率相等的情况下，查找成功的平均查找长度为（）。

A. （n-1）/2B. n/2C. (n+1)/2D. n正确答案：C25. 算法指的是（）。

A. 计算机程序B. 解决问题的计算方法C. 排序算法D. 解决问题的有限运算序列正确答案：D26. 一个n*n的对称矩阵，如果以行或列为主序存入内存，则其容量为（）。

A. n*nB. n*(n+1)/2C. (n+1)*(n+1)/2D. (n-1)*n/2正确答案：B27. 二维数组a的每个元素是由6个字符组成的串，行下标i的范围从0～8，列下标j的范围从1～10。

若a按行存放，元素a[8,5]的起始地址与当a按列存放时的元素（）的起始地址一致（每个字符占一个字节）。

A. a[8,5]B. a[3,10]C. a[5,8]D. a[0,9]正确答案：B28. 广义表运算式tail[((a,b),(c,d))]的结果为（）。

A. c,dB. (c,d)C. ((c,d))D. d,c正确答案：C29. 下列程序段的时间复杂度是（）。

for(i=0;i<="" a[i][j]="0;" for(j="1;j<m;j++)">A. O(n)B. O(m+n+1)C. O(m+n)D. O(m*n)正确答案：D30. 深度为5的二叉树至多有结点数为（）。

A. 16B. 30C. 31D. 32正确答案：C31. 适于对动态查找表进行高效率查找的组织结构是（）。

A. 有序表B. 分块有序表C. 三叉排序树D. 线性链表正确答案：D32. 下列排序方法中，平均时间性能为O(nlogn)且空间性能最好的是（）。

A. 快速排序B. 堆排序C. 归并排序D. 基数排序正确答案：B33. 若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为（）。

A. 顺序存储结构B. 链式存储结构C. 索引存储结构D. 散列存储结构正确答案：D34. 在数据结构中，数据的逻辑结构可以分为（）。

A. 内部结构和外部结构B. 线性结构和非线性结构C. 紧凑结构和非紧凑结构D. 动态结构和静态结构正确答案：B35. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则应作（）型调整以使其平衡。

A. LLB. LRC. RLD. RR正确答案：B36. 数组b[1..10，-2..6，2..8]以行优先的顺序存储，设第一个元素的首址是100，每个元素的长度为3。

元素b[5,0,7]的存储首址为（）。

A. 900B. 912C. 910D. 913正确答案：D37. 向顺序栈中压入新元素时，习惯上应当（）。

A. 先移动栈顶指针，再存入元素B. 先存入元素，再移动栈顶指针C. 先后次序无关紧要D. 同时进行正确答案：B38. 对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（）。

A. 2*nB. 2*eC. nD. e正确答案：B39. 如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2结点的（）。

A. 先序B. 中序C. 后序D. 层序正确答案：B40. 若待排序列已基本有序，要使它们完全有序，从关键码比较次数和移动次数考虑，应当使用的排序方法是（）。

A. 归并排序B. 直接插入排序C. 直接选择排序D. 快速排序正确答案：A西工大17春《数据结构》在线作业二、判断题（共 10 道试题，共 20 分。

）1. 数据结构是指定义了一组按某些关系结合在一起的数组元素。

（）A. 错误B. 正确正确答案：B2. 队列中还有空余的空间，但元素不能进入队列的现象称为假溢出现象。

（）A. 错误B. 正确正确答案：B3. 线性表采用顺序存储表示时，必须占用一片连续的存储单元。

（）A. 错误B. 正确正确答案：B4. 设一数列的顺序为1,2,3,4,5,6，通过栈操作，可以得到顺序为3,2,5,6,4,1的输出序列。

（）A. 错误B. 正确正确答案：B5. 线性表中元素数量基本稳定，且很少进行插入和删除，要求以最快的速度存取线性表中的元素，此线性表宜采用链式存储结构。

（）A. 错误B. 正确正确答案：A6. 在单链表中只能由当前结点访问其后的任一结点，而在双向链表中，可以由当前结点出发访问链表中的任一结点。

（）A. 错误B. 正确正确答案：B7. 图的生成树是不唯一的，一个连通图的生成树是一个最小连通子图，n个顶点的生成树有n-1条边，最小代价生成树是唯一的。

（）A. 错误B. 正确正确答案：B8. 含零个字符的串称为空串。

任何串中所含字符的个数为该串的长度。

A. 错误B. 正确正确答案：B9. 被计算机加工的数据元素不是孤立无关的，它们彼此之间一般存在着某种联系通常将数据元素间的这种联系关系称为结构。

（）A. 错误B. 正确正确答案：B10. 模式串P=’abaabcac’的next函数值序列为01122313。

（）A. 错误B. 正确正确答案：A。