数据结构结课试卷

数据结构结课试卷

您的姓名：［填空题］*

1.数据结构是相互之间存在一种或多种特定关系的数据元素的结合［判断题］*

对

错

2.二叉树在逻辑上算线性，图在逻辑上算非线性［判断题］*

对

错（正确答案）

3.顺序存储不要求逻辑上相邻的数据元素在物理上也相邻［判断题］*

对

错（正确答案）

4.顺序线性表中有n个元素，删除第i个元素需要移动i个元素的位置［判断题］*

对

错（正确答案）

5.当栈未满，入栈时，栈顶指针先加1,再送值到栈顶元素［判断题］*

对（正确答案）

错

6.队列的插入、删除都只能在对头进行［判断题］*

对

错（正确答案）

7.在循环队列中判断队满的公式为：Q.front==Q.rear［判断题］*

对

错（正确答案）

8.在C语言中，字符串的结尾符号是空格［判断题］*

对

错（正确答案）

9.对称矩阵的压缩过程中只需要存储其中n（n-l）/2个元素［判断题］*

对

错（正确答案）

10.广义表氏（a,（b,（c））,E）的深度为3［判断题］*

对

错（正确答案）

11.树特别适用于表达数据元素之间的层次关系，且树都有左右之分［判断题］*

对

错（正确答案）

12.构造好的一棵哈夫曼树共有29个结点，其中度为2的结点个数为14［判断题］

对（正确答案）

错

13.无向图的邻接矩阵是一个对称矩阵［判断题］*

对

错

14.广度优先搜素时，“先被访问的顶点的邻接点”后于“后被访问的顶点的邻接点”

被访问［判断题］*

对

错（正确答案）

15.Prim构造最小生成树时，采用的方法是在边集选择代价最小的边，若该边依附

的顶点落在树中不同的连通分量上，则将此边加入到树中［判断题］*

对

错（正确答案）

16.折半查找在最坏情况下查找成功的比较次数不会超过判定树的深度［判断题］*

对

错

17.最小生成树不是唯一的，最小生成树的边的权值之和也是不唯一的「判断题］*

对

错（正确答案）

18.堆中左子树的值一定小于堆顶的值，右子树的值一定大于堆顶的值［判断题］*

对

错（正确答案）

19.在执行冒泡排序时，不需要借助辅助空间［判断题］*

对

错（正确答案）

20.堆是一个特殊的完全二叉树，其根要么比左右子树都小，要么比左右子树都大

［判断题］*

对

错

21.快速排序每一次不一定能确定一个元素的最终位置［判断题］*

对

错(正确答案)

22.算法的基本要求不包括如下()方面的内容［单选题］*

A.健壮性和可读性

B.并行性

C.正确性

D.高效性

23.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执

行()［单选题］*

A.p->next=HL->next;HL->next=p;

B.p->next=HL;HL=p;

C.p->next=HL;p=HL;

D.HL=p;p->next=HL;

24.对线性表，在下列哪种情况下应当采用链表表示？()［单选题］*

A.经常需要随机地存取元素

B.经常需要进行插入和删除操作

C.表中元素需要占据一片连续的存储空间

D.表中元素的个数不变

25.一个栈的输入序列为123,则下列序列中不可能是栈的输出序列的是()［单选

题］*

A.231

B.321

C.312（正确答案）

D.123

26.二叉树的第k层的结点数最多为（）［单选题］*

A.2*+1

A.

B.2"+1

B.

C.2*-1

C.

D.2川

D.

27.设有n个结点的无向图，该图至少应有（）条边才能确保是一个连通图［单选题］

*

A“1（正确答案）

B.n

C.n+l

D.n+2

28.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（）

［单选题］*

A.0(1)

B.0(n)

C.O(m)(正确答案)

D.O(m+n)

29.设数组data［m］作为循环队列SQ的存储空间，front为队头指针，rear为队尾指

针，则执行出队操作后其头指针front值为()［单选题］*

A.front=front+l

B.front=(front+1)%(m-1)

C.front=(front-1)%m

D.front=(front+1)%m

30.一个非空广义表的表头()［单选题］*

A.不可能是子表

B.只能是子表

C.只能是原子

D.可以是子表或原子三确答安)

31.设数据结构A=(D,R),其中D={1,2,3,4},R={r},r={<l,2>,<2,3>,

<3,4>,<4,1>},则数据结构A是()［单选题］*

A.线性结构

B.树形结构

C.图形结构

D.集合

32.设某棵二叉树的中序遍历序列为ABCD,前序遍历序列为CABD,则后序遍历

该二叉树得到序列为()［单选题］*

A.BADC（正田

B.BCDA

C.CDAB

D.CBDA

33.设某棵二叉树中有2000个结点，则该二叉树的最小高度为（）［单选题］*

A.9

B.10

C.11（正确答案）

D.12

34.设一组初始记录关键字序列（5,2,6,3,8）,以第一个记录关键字5为基准进

行一趟快速排序的结果为（）［单选题］*

A.2,3,5,8,6

B.3,2,5,8,6

C.3,2,5,6,8（正确答案）

D.2,3,6,5,8

35.下面程序的时间复杂为（）

for（i=l,s=0；i<=n；i++）{t=l；for（j=l；j<=i；j++）t=t*j；s=s+t；}

［单选题］*

Qin）

A.

。厅）

B.（正确答案）

O(rP)

C.

0(n+

D.

36.设有n个待排序的记录关键字，则在堆排序中需要（）个辅助记录单元［单选

题］*

A.1（正确答案）

B.n

nlog2n

C.

n2*

D.

37.设有5（）0万个待排序的记录关键字，如果需要用最快的方法选出其中最小的10

个记录关键字，则用下列（）方法可以达到此目的［单选题］*

A.快速排列

B.堆排列（正确答案）

C.归并排列

D.插入排列

38.设一组初始记录关键字序列为（25,50,15,35,80,85,20,40,36,70）,

其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行

一趟归并后的结果为（）［单选题］*

A.15,25,35,5（）,20,40,80,85,36,70（正确答案）

B.15,25,35,50,80,20,85,40,70,36

C.15,25,35,50,80,85,20,36,40,70

D.15,25,35,50,80,20,36,40,70,85

39.函数substr("DATASTRUCTURE”，5,9)的返回值为()［单选题］*

A."STRUCTURE”通答案)

B.“DATA”

C."ASTRUCTUR”

D."DATASTRUCTURE”

40.()二叉排序树可以得到一个从小到大的有序序列［单选题］*

A.先序遍历

B.中序遍历(正确答案)

C.后序遍历

D.层次遍历

41.设无向图G中的边的集合E={(a,b),(a,e),(a,c),(b,e),(e,d),(d,

0,(f,c)},则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为()

［单选题］*

A.aedfcb

B.acfebd

C.aebcfd

D.aedfbc

42.设有序表中的元素为(13,18,24,35,47,5(),62),则在其中利用二分法查

找值为24的元素需要经过()次比较［单选题］*

A.1

B.2

C.3(正确答案)

D.4

43.一个栈依次入栈字符序列为ABCDABCD,当执行完PUSH();

PUSH();PUSH();PUSH();POP();PUSH();POP();后，再执行POP()；会输出()【单选题】

*

A.A

B.B

C.C(正确答案)

D.D

44.平衡二叉树的平衡因子不可能是()［单选题］*

A.-1

B.1

C.0

D.2(正确答案)

45.当一个顺序表删除一个元素时。被删除元素之后的所有元素均需()一个位置［单

选题］*

A.前移(正确答案)

B.后移

C.跳跃

D.原地不动，不移动

46.数组的逻辑结构不同于下列()的逻辑结构［单选题］*

A.线性表

B.图(正确答案)

C.队列

D.栈

47.在n个元素的顺序表中查找值为x的元素。

for(i=0;i<L.length;i++)

if()break;

if(i<L.length)

printf(“找到叫；

else

printf(“未找到”)；

[单选题]*

A.L.elem[i]==x(正确答案)

B.L.elem[i]=x

C.i>L.length

D.L.elem[i]>x

48.删除：在n个元素的顺序表中，将第i(ign)个元素删除。

boolListDelete(SqList&L,inti,DataType&x)

(

if(L.length==0||i<l||i>L.length)returnfalse;//失败

x=L.elem[i-1];

for(j=i;j<L.length;j++)

L.elemjj-l]=L.elem[j];

___________,

returntrue;//删除成功

}

[单选题]*

A.L』ength--(正确答案)

B.x=L.elem[j-l]

C.returnfalse

D.L.length++

49.

删除单链表List中第i个位置的数据元素。

typedefstructnode(

datatypedata;

structnode*next:

)*LinkList;

intDeleteLinkList(LinkListList,inti)

(

LinkListp,q;

p=GegLinkList(L,i-l);/*p指向第i-1个位置的数据元素节点*/

/*删除前已经检测过第i个数据节点存在*/

q=p->next;

free(q);/*释放q*/

retum(l);

)

单选题］*

A.p=q->next;

B.p->next=q->next;

C.p=q;

D.p->next=q

50.请填写完成下列关于入栈的代码：

boolPush(sqStack&s,ElemTypex)

{if()

returnfalse;

s.data[++s.top]=x;

returntrue;}[单选题]*

A.s.stop==0

B.s.top==Maxsize-l

C.s.top==Maxsize

D.s.top==-1

51.将下列折半查找的代码补充完整

intBinSearch(SeqListR,KeyTypeK)

{intlow=l,high=n,mid；

while(low<=high)

{mid=(low+high)/2；

if(R[mid].key==K)returnmid；

if(R[mid].key>K)

else

return0；

}

[单选题]*

A.high=mid-1low=mid+l

B.low=mid+1high=mid-l

C.high=midlow=mid

D.low二midhigh=mid

52.下列是在循环队列中插入数据元素e的算法，请将算法补充完整。

删除单链表List中第i个位置的数据元素。

typedefstructnode{

datatypedata;

structnode*next:

}*LinkList;

intDeleteLinkList(LinkListLi)

(

LinkListp,q;

p=GegLinkList(L,i-l);/*p指向第i-1个位置的数据元素节点*/

/*删除前已经检测过第i个数据节点存在*/

q=p->next;

free(q);/*释放q*/

retum(l);

}

［单选题］*

A.Q.front++；

B.Q.front=(Q.front+l)%MAXSIZE

C.Q.rear=(Q.rear+l)%MAXSIZE正确答案)

D.Q.re