《数据结构》期中测试题软件技术用.pdfVIP

《数据结构》期中测试题软件技术用--第1页

自信考试诚信做人

《数据结构》期中测试-2014软件技术用

1-12每题3分

1.以下算法的时间复杂度为（）

for(i=1,s=0;i=n;i++）{for(j=1;j=i;j++)s+=j;}

nn2

A.O(n)B.O(n*log)C.O(log)D.O(n)

22

2.下面的叙述正确的是（）

A．线性表在链式存储时，查找第i个元素的时间同i的值成正比

B.线性表在链式存储时，删除第i个元素的时间同i的值无关

C.线性表在顺序存储时，查找第i个元素的时间同i的值成正比

D.线性表在顺序存储时，删除第i个元素的时间同i的值无关

3.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采

用（）存储方式最节省运算时间。

A．单链表B．仅有头指针的单循环链表C．双向链表

D．仅有尾指针的单循环链表

4.设指针变量p指向单链表中的某结点，q指向其后继节点，删除q所指结点的操作序列为

()。

A.free(q);q=q-next;B.p-next=q-next;free(q);

C.p=q;free(q);D.q-next=p-next;free(q);

5.设栈S的初始状态为空，元素abcdefg依次进入栈S。若出栈顺序为bdcfeag，则栈S的容量

至少是（）。

A.1B.2C.3D.4

6.假设链队列头指针直接指向队头元素，进行出队操作时需要的操作为（）。

A.仅修改头指针B.仅修改尾指针C.头、尾指针都必须修改

D.头、尾指针可能都要修改

7.对于容量为n的循环队列Q，队尾指针是Q.rear，队头指针是Q.front，则出队时头尾指针需

要进行的操作为（）

A.Q.rear=Q.rear+1B.Q.rear=(Q.rear+1)%n

C．Q.front=Q.front+1D.Q.front=(Q.front+1)%n

8.一棵完全二叉树上有62个结点，其中叶子结点的个数是（）

A．31B．32C．33D．前述答案均不正确

用心用情1服务社会

《数据结构》期中测试题软件技术用--第1页

《数据结构》期中测试题软件技术用--第2页

自信考试诚信做人

9.在树中结点u与v是兄弟，将其转换为二叉树后，u和v可能具有的关系是（）

A.兄弟关系

B.u是v的父结点或祖先结点

C.v是u的父结点或祖先结点

D.以上都不正确

10.一棵二叉树具有10个度为2的结点，5个度为1的结点，则该二叉树中的空指针域数量