一、单项选择题(本大题共15小题,每小题2分,总计30分)
( C )1.数据在计算机存储器内表示时,物理地址与逻辑地址相同并且是连续的,称之为:
(A)存储结构 (B)逻辑结构 (C)顺序存储结构 (D)链式存储结构
( A )2. 在n个结点的顺序表中,算法的时间复杂度是O(1)的操作是:
(A) 访问第i个结点(1≤i≤n)和求第i个结点的直接前驱(2≤i≤n)
(B) 在第i个结点后插入一个新结点(1≤i≤n)
(C) 删除第i个结点(1≤i≤n) (D) 将n个结点从小到大排序
( A )3. 链接存储的存储结构所占存储空间:
(A) 分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针
(B) 只有一部分,存放结点值
(C) 只有一部分,存储表示结点间关系的指针
(D) 分两部分,一部分存放结点值,另一部分存放结点所占单元数
( D )4. 线性表若采用链式存储结构时,要求内存中可用存储单元的地址:
(A)必须是连续的 (B)部分地址必须是连续的
(C)一定是不连续的 (D)连续或不连续都可以
( B )5. 线性表L在 情况下适用于使用链式结构实现。
(A)需经常修改L中的结点值 (B)需不断对L进行删除插入
(C)L中含有大量的结点 (D)L中结点结构复杂
( B )6. 单链表的存储密度
(A)大于1; (B)等于1; (C)小于1; (D)不能确定
( B )7. 栈中元素的进出原则是
A.先进先出 B.后进先出 C.栈空则进 D.栈满则出
( C )8. 若已知一个栈的入栈序列是1,2,3,…,n,其输出序列为p1,p2,p3,…,pn,若p1=n,则pi为
A.i B.n=i C.n-i+1 D.不确定
9. 设有4个数据元素a1、a2、a3和a4,对他们分别进行栈操作或队操作。在进栈或进队操作时,按a1、a2、a3、a4次序每次进入一个元素。假设栈或队的初始状态都是空。
现要进行的栈操作是进栈两次,出栈一次,再进栈两次,出栈一次;这时,第一次出栈得到的元素是 A ,第二次出栈得到的元素是 B ;类似地,考虑对这四个数据元素进行的队操作是进队两次,出队一次,再进队两次,出队一次;这时,第一次出队得到的元素是 C ,第二次出队得到的元素是 D 。经操作后,最后在栈中或队中的元素还有 E 个。
供选择的答案:
A~D:①a1 ②a2 ③ a3 ④a4 E: ①1 ②2 ③ 3 ④ 0
答:A、B、C、D、E分别为 2 、 4 、 1 、 2 、 2
10.若非空队列采用链式存储结构,队头元素指针与队尾元素指针分别为front和rear,删除队列的一个元素的过程是依次执行:p=front,__D__,free(p)。
A.rear=p B.rear=p->next C.rear=p->next D.front=p->next
11. 设存储分配是从低地址到高地址进行的。若每个元素占用4个存储单元,则某元素的地
址是指它所占用的单元的( A)。
A.第1个单元的地址 B.第2个单元的地址
C.第3个单元的地址 D.第4个单元的地址
二、算法
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
题(本大题共6小题,总计70分)
1.已知线性表A与线性表B的长度分别为n与m,并且都采用顺序存储结构,写一算法,在线性表A的第i个位置插入线性表B。约定:不考虑存储空间溢出问题。(20分)
2.已知非空线性链表的第一个链结点的存储地址为list,写出删除该链表第i个链结点的算法。(15分)
3. 使用栈的原理,编写一算法,当从键盘上输入一个任意的非负十进制整数时,输出与其等值的八进值数。(15分)
4.假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针),试编写相应的队列初始化、入队列和出队列的算法。(20分)