当前位置：问答库＞考研试题

一、填空题

1． 设有一个空找，栈顶指针为1000H （十六进制），现有输入序列为1，2，3, 4, 5，经过PUSH ，PUSH , POP , PUSH , POP ，PUSH ，PUSH 之后，输出序列是_____，而栈顶指针值是_____。设栈为顺序栈，每个元素占4个字节。

【答案】23; 100CH

2． 下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空：

【答案】

【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。

3． 按LSD 进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用_____的排序方法。

【答案】稳定

4． 在下面的程序段中，对X 的赋值语句的时间复杂度为_____（表示为n 的函数）。

【答案】1＋（1＋2）＋（1＋2＋3）＋"•＋（l ＋2＋... ＋n ）=n（n ＋1）（n ＋2）/6，即

【解析】当i=l时，赋值语句就被执行了一次。当i=2时，赋值语句被执行了1＋2次。当i=3时，赋值语句被执行了1＋2＋3次。可以推出赋值语句总共被执行了1＋（1＋2）＋（1＋2＋3）＋…＋（l ＋2＋... ＋n ）=n（n ＋1）（n ＋2）/6次。

5． 完善算法：求KMP 算法.next 数组。

END ； 【答案】

要使前者快于后者，n 至少为

6． 设有两个算法在同一机器上运行，其执行时闻分别为_____。

【答案】15

【解析】当时，而

，时，

7． 在n 个顶点的非空无向图中，最多有_____个连通分量。

【答案】n

【解析】当n 个顶点之间没有边，都是孤立的顶点时，有n 个连通分量。

8． 模式串的next 函数值序列为_____。

【答案】01122312

9． 表达式

【答案】

的后缀表达式是_____。

10．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_____存储结构。

【答案】顺序

【解析】顺序存储结构的存取操作比较方便，但插入和删除操作不如链式存储结构方便，而且需要连续的存储空间，由于该线性表的元素总数基本稳定，而且很少进行插入删除操作，为了更快的存取元素，顺序表更合适。

二、算法设计题

11．已知深度为h 的二叉树, 以一维数组应的算法。

【答案】算法如下： int Leaves （int BT[]，int n）

//计算深度为h. 以一维数BT 作为其存储结构的二叉树的叶结点数，n 为数组长度{int num=0; //

作为其存储结构，试编写一算法，求该二叉

树中叶结点的个数，为简单起见，设二叉树中元素结点为非负整数，要求写出算法基本思想及相

记叶结点数

for （i=0; i

2*i+l

BT （2*i+l】<0） num++; }//若结点无孩子，则是叶子else if

（BT[i]>0） num++； //存储在数组后一半的元素是叶结点

return num; }//结束Leaves

12．设整数序列给出求解最大值的递归程序。

【答案】算法如下：

13．设计算法将一棵以二叉链表存储的二叉树按顺序方式存储到一维数组中（注：按层从上到下，由左到右）。

【答案】算法如下：

typedef struc {DiTree data ; int num ; }tnode // num 是结点在一维数组中的编号tnodc Q[maxsize]; //队列，容量足够大

void BiToSeqt{BiTree t, ELemType seq[]}

//本算法将二叉树的二叉链表存储结构转换为顺序存储结构seq {int front=0, rear:=0; tnode q; Bitree p; if （!t ） exit （0）;

for （i=1; i

{tq=Q[++front]; p=tq.data; l=tq.num; seq[i]=p->data; //存入顺序存储结构 if （p->lchild）{tq.data=p->lchild; tq.num=2*i; Q[++rear}//左子女入队 if （p->rchild）{tq.data=p->rchild; tq.num=2*i+1; Q[++rear]=tq; }//右子女入队 } }

14．起泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）；请给出上浮和下沉过程交替的起泡排序算法。

【答案】算法如下：