return Locate(t->rchild, x); /*右子树*/ }

09年专升本数据结构考题解答(共100分)

一、 单项选择题（12小题，每小题2分，共24分）

1、要表示高校校、系、班级的有关数据及其关系，选择______比较合适。 A. 线性结构 B. 树结构 C. 图结构 D.集合结构 2、下列函数中复杂度最小的是 A. T(n)=nlog2n+5000n B. T(n)=n2-8000n C. T(n)=nlog22n-6000n D. T(n)=2nlog22n-7000n

nlog22n= nlog22+log2n=n1+log2n=n*n log2n

3、已知一个栈s以及一个输入序列(A，B，C，D，E)，每个元素按照A，B，C，D，E顺序进栈一次，进栈后可立即出栈，也可在栈中停留一段时间后再出栈，则不能得到（）序列。

A．A、B、C、D、E B. B、A、E、D、C C．C、B、A、D、E D. D、C、A、B、E 4、平均排序效率最好的排序方法是（）。 A．直接插入排序 B．快速排序 C．简单选择排序 D．冒泡排序

5、某链表中最常用的操作是在已知的一个结点之前插入一个新结点和删除其之前一个结点，则采用（）存储方式最节省运算时间。 A．双向链表 B．带头指针的单向链表 C．带尾指针的单向链表 D．单向循环链表

6、在逻辑结构不变的情况下，不是导致一个图的遍历序列不唯一的因素是（）。 A．出发点不同 B．存储(物理)结构不同 C．遍历方法不同 D．画法不同

7、散列函数有一个共同的要求，即函数值应当尽量以（）取其值域的每个值。 A．最大概率 B．最小概率 C．正态分布概率 D．均等概率

8、下面（）方法可以判断出一个图中是否存在环(回路)。 A．排序 B．深度和广度遍历 C．求最短路径 D．求关键路径 9．最佳二叉搜索(排序)树是（）。 A．关键码个数最小的二叉搜索树 B．退化为线性的二叉搜索树 ，

C．搜索中平均比较次数最小的二叉搜索树 D．任何结点的度数为0或2的二叉搜索树 10．（）是数据的基本单位，即数据集合(对象)中的个体。 A．数据结构 B．数据项 C．数据元素 D．数据对象 11． (线性)表是一个（）。

A．有限序列，可以为空 B．有限序列，不能为空 C．无限序列，可以为空 D．无限序列，不能为空 12．树是结点的集合，它（）根结点。 A．有0个或1个 B．有0个或多个

C．有且只有1个 D．有1个或1个以上

二、填空题(本大题共7小题，每空2分，共16分) 请将答案写在答题纸相应的位置上。

13． 在有n个顶点的有向图中，每个顶点的度(=入度+出度)最大可达（2n-2）。 14． 以下程序段的时间复杂度是（）。 i=0； j=0; while ( i+j<=n) {

if(i>j)j++;

else i++； }

每次只做i++或j++，不会同时 i++而且j++， n的值不变，因此循环n次，复杂度O(n) 15． 右图所示的二叉树后序遍历的结果是（EDCBIHJGFA）。

16． 在一个双向链表中p所指结点之前插入一个由指针s所指的新结点，写出可执行的操作序列：（）。(前指和后指的指针域分别为prior和next)

1. s->prior=p->prior；

2. s->next=p； 1和2顺序可换 3. p->prior->next=s；

4. p->prior=s； 注意p->prior要最后改变，因为之前要用

17. (线性)表有两种存储结构：顺序存储结构和链式存储结构，请就这两种存储结构完成下列填充：（顺序存储结构）存储密度较大，可以随机存取：（链式存储结构）不可以随机存取，插入和删除操作比较方便。

18．递归的程序执行时使用（堆栈）来保存各层递归调用时的现场信息，以保证可以正确返回。

19．设数组a[M](M为最大空间个数)作为循环队列Q的存储空间，front为队头指针(指向第一个存放数据的位置)，rear为队尾指针(指向最后一个存放数据位置的下一个)，则判定Q队列的队满条件是（）。 队满条件与方案无关，总是(rear+1)%n==front

三、应用题(本大题共4小题，每小题10分，共40分) 请将答案写在答题纸相应的位置上。

20．设字符集D={A，B，C，D，E}，各字符使用频率W={10，2，5，6，4}，画出对字符进行哈夫曼编码时所对应的哈夫曼树，并给出各字符的编码。

21．用普里姆(Prim)算法从右图中的顶点1开始逐步构造最小支撑(代价生成)树，要求画出构造的每一步。

22．给定待排关键字集合为{23，14，48，25，5，19}，按关键字非递减(从小到大)排序，写出采用冒泡排序的每一趟(最外层循环的每一次)排序结果。 23．(1)图示表示右边有向图的邻接表。(4分)

(2)写出从顶点1开始分别进行深度优先和广度优先遍历的顶点序列各一种。(6分)

四、算法设计题(本大题共2小题，每小题10分，共20分) 请将答案写在答题纸相应的位置上。

24．假定用一个有头结点循环链表来存储一个有序的线性表，线性表从头到尾

为非递减(从小到大)有序(如下图)。用指针current从head开始搜索数据域等于key的元素在线性表中位置，如果搜索成功则current指向搜索到的结点，函数返回该指针：如果搜索不成功，函数返回空指针NULL。请在函数

SortedlistLocate(head，key)

内填空，完成下列算法以实现这种搜索，并使得搜索不成功的平均比较次数小于链表长度。（发现current指向结点的数据域比key大，则停止搜索，后面肯定没有key，搜索失败。这样就没有必要走到链表的尾部，不成功的平均比较次数=(0+1+2+..+n)/(n+1)=n/2）

注意：有头结点，是单循环链表。空表如下

typedef struct node{

elemtype data；/*数据域*/ struct node next；/*指针域*/ }lnode，*linklist；

注意typedef，lnode和linklist是类型名 linklist SortedlistLocate ( linklist head，

elemtype key){

linklist current；

if(_head==NULL_)return ERROR；

/*错误提示*/

current ___=head->next____;

/*循链搜索其值等于key的结点*/

while(_current!=head_&&_current->data

current=current-->next；

/*排除空表*/

if ( _ current !=head && current->data==key _) return current； /*找到，返回结点地址*/ else

return NULL； /*末找到，返回空指针*/ }

25．r[]为一维数组，其中r[0]到r[n-1]为待排序的n个元素，排序好的元素仍放在r[0]到r[n-1]中。请写出对该数组进行非递减排序的直接插入排序算法， 取名为InsertSort(elemtype r[]，int n)。