川农《数据结构(本科)》17年9月在线作业

《数据结构（本科）》17年9月在线作业

一、单选题（共 20 道试题，共 100 分。）

1. 设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（ ） A. front=front+1

B. front=(front+1)%(m-1) C. front=(front-1)%m D. front=(front+1)%m 正确答案：D

2. 设有100个数据元素，采用折半搜索时，最大比较次数为( ) A. 6 B. 7 C. 8 D. 10

正确答案：B

3. 线性链表不具有的特点是( ) A. 随机访问

B. 不必事先估计所需存储空间大小 C. 插入与删除时不必移动元素 D. 所需空间与线性表长度成正比 正确答案：A

4. 深度为8的二叉树至多有（ ）个结点 A. 7 B. 15 C. 127 D. 255

正确答案：D

5. 线性表是一个具有n个（ ）的有限序列。 A. 表元素 B. 字符 C. 数据元素 D. 数据项 正确答案：C

6. 设某算法的问题规模函数f(n)=300n2+8000n+900，则它的渐进时间复杂度为（ ) A. O(n3) B. O(n2) C. O(n) D. O(1)

正确答案：B

7. 与数据元素本身的形式、内容、相对位置、个数无关的是数据的( ) A. 存储结构 B. 逻辑结构 C. 算法 D. 操作 正确答案：B

8. 若采用邻接矩阵法存储一个N个顶点的无向图，则该邻接矩阵是一个( ) A. 队头元素的前一个位置 B. 队头元素的后一个位置 C. 队头元素位置

D. 队尾元素的前一位置 正确答案：A

9. 下列存储形式中不是树的存储形式( ) A. 双亲表示法 B. 孩子兄弟表示法 C. 顺序表示法 D. 广义表表示法 正确答案：D

10. 依次在初始为空的队列中插入元素X，Y，Z，W以后，紧接着作了两次删除操作，此时的队头元素是（ ) A. X B. Y C. Z D. W

正确答案：C

11. 设有一个含有n 个(n>2)关键字的有序表，分别用顺序查找法和二分查找法查找一个给定的关键字，比较次数分别为s和h，在查找成功的情况下，s和h的关系是( ) A. s = h B. s > h C. s < h D. 不能确定 正确答案：A

12. 设有一个10阶的对称矩阵A[10][10]，采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组B[ ]A[0][0]存入B[0]中，则A[8][5]在B[ ]中（ ) A. 32 B. 33 C. 41 D. 65

正确答案：C

13. 一个关键字序列为{46，79，56，38，40，84}，采用快速排序以位于最左位置的元素为基准而得到的第一次划分结果为（ ) A. {38，46，79，56，40，84} B. {38，79，56，46，40，84}

C. {40，38，46，56，79，84} D. {38，46，56，79，40，84} 正确答案：C

14. 设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域为空的结点有（ ) A. n-1 B. n C. n+1 D. n+2

正确答案：B

15. 假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是（ ) A. O(n) B. O(e) C. O(n+e) D. O(n×e) 正确答案：C

16. 对5个不同的数据元素进行直接插入排序，最多需要进行（ ）次比较 A. 8 B. 10 C. 15 D. 25

正确答案：B

17. 设有整型二维数组M[7][6]，每个元素（整数）占4个存储单元，元素按行的顺序存储，数组的起始地址为1000，元素M[5][3]的地址是（ ) A. 1032 B. 1132 C. 1192 D. 1232 正确答案：B

18. 设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为( ) A. O（nlog2e） B. O（n+e） C. O(ne) D. O(n2) 正确答案：B

19. 链式栈与顺序栈相比，一个比较明显的优点是( ) A. 插入操作更加方便

B. 通常不会出现栈满的情况 C. 不会出现栈空的情况 D. 删除操作更加方便 正确答案：B

20. 右图中的拓扑序列为（ )

A. C1，C2，C6，C7，C5，C4，C3 B. C1，C2，C6，C3，C4，C5，C7 C. C1，C4，C2，C3，C5，C6，C7 D. C5，C7，C4，C1，C2，C6，C3 正确答案：D