参考答案
一、单项选择题(每小题2分，共30分} CADCC ACACB BDCDB
二、填空题(每题2分，共24分) 16．11 17．21 18．中序 19．树形 20．物理(存储) 21．线性 22．gdbeihfca 23．N-1 24．不正确 25．正确
26．深度优先搜索遍历 27．相等
三、综合应用题(每小题10分，共30分) 28．(1)
广度优先搜索遍历
后序
(2)．102，52，42，82，16，6?，32，57
第 6 页 共 30 页
29．．(1)原序列16 15 20 53 64 7 15 16 20 53 7 15 16 20 7 15 16 7 15 7 7 (2)
64
53 64
20 53 64
16 20 53 64
15 16 20 53 64
(3)平均查找长度=(1*1+2*2+3*3)/6=14/6 30．(1)
(2)三次，四次
四、程序填空题(每空2分，共16分) 31．(1)malloc(sizeof(struct node)) (2)rear->next=p
第 7 页 共 30 页
(3)p 32．(1)j
一、单项选择题（每小题2分，共30分）
1．数据的物理结构( )。 A．与数据的逻辑结构无关
B．仅仅包括数据元素的表示 D．包括数据元素的表示和关系的表示
C．只包括数据元素间关系的表示 2．从n个数中选取最大元素( )。 A．基本操作是数据元素间的交换 C．算法的时间复杂度是O(n)
B．算法的时间复杂度是O(n) D．需要进行(n+1)次数据元素间的比较
2
3．线性表的顺序结构中，( )。
A．逻辑上相邻的元素在物理位置上不一定相邻 B．数据元素是不能随机访问的
C．逻辑上相邻的元素在物理位置上也相邻 D．进行数据元素的插入、删除效率较高
4．带头结点的单向链表为空的判断条件是( )(设头指针为head)。 A．head==NULL
B．head->next==NULL D．head!=NULL
C．head->next==head
5．线性结构中数据元素的位置之间存在( )的关系。
第 8 页 共 30 页
A．一对一 C．多对多
B．一对多
D．每一个元素都有-个直接前驱和一个直接后继
6．设顺序存储的线性表长度为n，要删除第i个元素，按课本的算法，当i=( )，移动元素的次数为3。
A．3
B．n/2 D．4
C．n-3
7．以下说法不正确的是( )。 A．栈的特点是后进先出 B．队列的特点是先进先出
C栈的删除操作在栈底进行，插入操作在栈顶进行 B队列的插入操作在队尾进行，删除操作在队头进行
8．一个栈的进栈序列是a，h，c，d，则栈的不可能的出栈序列是( )。 A．adbc C．cbad
B．bead D．dcba
9．设top是一个链榜的栈顶指针，栈中每个结点由一个数据域data和指针域next组成，设用x接收栈顶元素，则出栈操作为( )。
A．x=top->data;top=top->next; C．x=top->next;top=top->data;
B．top=top->next;x=top->data; D．top->next=top;x=top->data;
10．设有一个带头结点的链队列，队列中每个结点由一个数据域data和指针域next组成，front和rear分别为链队列的头指针和尾指针，要执行出队操作，用x保存出队元素的值，p为指向结点类型的指针，可执行如下操作:p=front->next;x=p->data;然后执行( )。
A．front=p->next; C．front=p;
B．front->next=p->next; D．front->next=p;
11．以下说法正确的是( )。 A．队列是后进先出 B．栈的特点是后进后出
C．拢的删除和插入操作都只能在栈顶进行 D．队列的删除和插入操作都只能在队头进行
12．在C语言中，存储字符串\需要占用( )字节。 A．4 C．5
B．2 D．3
第 9 页 共 30 页
13．串函数StrCmp(\，\的值为( )。 A．1
B．0 D．-1
C．\
14．设有一个10阶的对称矩阵A，采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b中。(矩阵A的第一个元素为al,l，数组b的下标从1开始)，则矩阵元素a5,3对应一维数组b的数组元素是( )。
A．b[18] C．b[13]
B．b[8] D．b[lO]
15．已知如图1所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为( )。
A．abecdf c．aebcfd
二、填空题{每小黯2分，共24分}
16．通常数据的逻辑结构包括集合、线性、________________、________________四种类型。 17．通常可以把某城市中各公交站点间的线路图抽象成_________________结构。
18．设有一个单向链表，结点的指针域为next，头指针为head，p指向尾结点，为了使该单向链表改为单向循环链表，可用语句_________________。
19．循环队列的队头指针为f，队尾指针为r，当_________________时表明队列已空。
20．设有一个链钱，栈顶指针为hs，现有一个s所指向的结点要入栈，则可执行操作_________________和hs=s。
21．在-个链队中，f和r分别为队头和队尾指针，队结点的指针域为next，则插入一个s所指结点的操作为_________________；r=s。
22．串的两种最基本的存储方式分别是_________________和_________________。 23．一棵二叉树中顺序编号为i的结点，若它存在左、右孩子，则左、右孩子编号分别为
第 10 页 共 30 页
B．acfebd D．aedfcb