线性结构总复习.docVIP

线性结构总复习 填空题 1 _____是数据的基本单位，.........是具有独立含义的最小标识单位。 2 数据之间的关系（逻辑结构）有四种——、——、——、——。 3 数据的存储结构包括.......................、...........................。 4 float sum2(int n){ ???? /* 计算1！+2！+…+n! */ sum2=0; for (i=1; i=n; ++i){ ????? p=1; ????? for (j=1; j=i; ++j) p=p*j; ????? sum2=sum2+p; ????? } 上述程序段的时间复杂度为 。 5 在单链表中，指针p所指结点为最后一个结点的条件是 。 6 在单链的循环链表中，指针p所指结点为最后一个结点的条件是 。 7 在初始为空的队列中插入元素a,b,c,d以后，紧接着作了两次删除操作，此时的队尾元素是 。 8 设字符串 S1=“ABCDEFG”， S2=“PQRST”，则运算： S=Concat（Substring（S1，2，Length（S2））， Substring（S1，Length（S2），2）） 后的串值S为 。 9 模式串t=‘abcaabbcabcaabdab’，该模式串的next数组的值为 ，nextval数组的值为 。 选择题 1.线性链表不具有的特点是（ ）。 A．随机访问 B．不必事先估计所需存储空间大小 C．插入与删除时不必移动元素 D．所需空间与线性表长度成正比 2.线性表采用链式存储时，其地址（ ）。 A 必须是连续的 B 一定是不连续的 C 部分地址必须是连续的 D 连续与否均可以. 3、下列哪一个程序片段是在链表中间插入一个结点。（假设新结点为NEW，欲插入在Pointer结点之后） A NEW-next=Pointer B NEW-next=Pointer-next Pointer=NEW Pointer-next=NEW C Pointer-next=NEW-next D 以上皆非 NEW-next=Pointer 4. 在单链表中,增加头结点的目的是 （ ） A. 使单链表至少有一结点 B. 标志表中首结点位置 C. 方便运算的实现 D.说明单链表是线性表的链式存储实现 5． 线性表Ｌ在 情况下适用于使用链式结构实现。（ ） （Ａ）需经常修改Ｌ中的结点值 （Ｂ）需不断对Ｌ进行删除插入 （Ｃ）Ｌ中含有大量的结点 （Ｄ）Ｌ中结点结构复杂 6、向一个有127个元素原顺序表中插入一个新元素并保存原来顺序不变，平均要移动（ ）个元素。 A、8 B、63.5 C、63 D、7 7.对于顺序存储的队列，存储空间大小为n，头指针为F，尾指针为R。若在逻辑上看一个环，则队列中元素的个数为 [ ] (1).R-F ⑵.n+R-F ⑶.(R-F+1)mod n ⑷.(n+R-F)mod n 8. 若一个序列的进栈顺序为1,2,3,4, 那么不可能的出栈序列是 [ ] A. 4,2,3,1 B. 3,2,1,4 C. 4,3,2,1 D. 1,2,3,4 9、一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程（ ） A．较快 B．较慢 C．相同 D 不确定 10 设有一个二维数组 A [ m ][ n ] ，采用行序优先存储的方式，假设 A [0][0] 存放位置在 644 (10) ， A [2][2] 存放位置在 676 (10) ，每个元素占一个空间，问 A [3][3] (10) 存放在什么位置（ ）脚注 (10) 表示用 10 进制表示。 A． 676 B。 650 C 。 600 D 。 692 11 对矩阵压缩存储是为了（ )。 A方便