作业题（一） 一、单项选择题 1. 从逻辑上可以把数据结构分为（ ）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 2. 链表不具有的特点是（ ） A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 3.下面程序段的时间复杂度的量级为（ ）。 For(i=1;i<=n;i++) For(j=1;j<=I;j++) For(k=1;k<=j;k++) X=x+1; A．O(1) B．O(n) C．O(n²) D．O(n³) 4.在 一个 带 头 结点的双 向 循 环 链表中 ，若 要在 p 所指 向 的结点之 前 插入一个 新 结点，则 需要相 继 修 改（ ）个 指 针 域 的值 。 A．2 B．3 C．4 D．6 5、一个 顺序存储线性表的第 一个 元素的存储地 址 是90， 每 个 元素的长度是2， 则 第6 个 元素的存储地 址是（ ）。 A．98 B．100 C．102 D．106 6、判 定 一个 栈 s（最 多 元素为m0）为空的条 件 是（ ）。 A．s-〉 top! =0 B．s-〉 top= =0 C．s-〉 top! =m0 D．s-〉 top= =m0 7、循 环 队 列用数组A[m]（下标从0 到m-1）存放其元素值 ， 已知其头 尾指 针 分别是front 和rear， 则 当前 队 列中 的元素个 数是（ ）。 A．（rear-front+m）%m B．rear-front+1 C．rear-front-1 D． rear-front 8、设有两个 串S1 与S2， 求串S2 在 S1 中 首次出现位置的运算称作（ ）。 A．连接 B．求子串 C．模式匹配 D．判 子串 9、设串S1='ABCDEFG'， S2='PQRST'， 函数con（x， y）返 回 x 和y 串的连接串， subs(s,i,j)返 回 串S 的的从序号i的字符开始的j个字符组成的子串，len(s) 返回串S的长度，则con(subs(S1,2,len(S2)),subs(S1,len(S2),2))的结果 是（ ）。 A．BCDEF B．BCDEFG C．BCPQRST D．BCDEFEF 10、数组常用的两种基本操作是（ ）。 A．建立与查找 B．删除与查找 C．插入与索引 D．查找与修改 二、填空题 1. 所谓稀疏矩阵指的是________且分布没有规律。 2. 队列是________的线性表，其运算遵循________的原则。 3. 空格串是________________________________。 4.简单选择排序和起泡排序中比较次数与序列初态无关的算法有________。 5、设图 G 有 n 个顶点和 e 条边，则对用邻接矩阵表示的图进行深度或广度优先搜索遍历时的...
