北航991真题2013年答案

1 选C 2 选A 3 选D

4 选B，通过前序中的50来排除AC，同时这是一个排序树，可以构建出其结构 5 选C 6 选B 7 选D

8 选A，不要被顺序表所迷惑，顺序表不一定时有序的 9 不在考点里了 10 选D

二、 顺序表

1 顺序 2 O(m)

3 log2(k)+1取上界，向上取整，2^(h-2)< k <= 2^(h-1) 4 234或235 5 2(n+1)

6 有向图中不含有回路 7 看公式 8 B树不考了

9插入排序 10 9次4+3+2=9次

三、综合题

1 多个堆栈可以节约存储空间，可以充分利用全部的存储空间，但是某个堆栈满了之后移动空间麻烦，（2）操作方面，但单个堆栈难以确定分配的空间大小，会出现溢出或存储无法充分利用的情况（3）一般不会出现堆栈溢出的情况，且不需要预先分配空间，但需要用到了指针，需要额外的存储空间

2 T->lchild==NULL&&T->rchild==NULL，T->lchild，T->rchild，显然这是个前序遍历，注意题目说明，输出叶结点的数据信息，所以if是判断是否为叶节点，其实还可以改进算法 3 虽说不在考点，建议还是看看 4 （1）11/0.61=18，除以18 （2）

四、算法设计题

void sort(int A[],int n) { int i,j;

for(i = 1;i <= n/2; i++) {

int minIndex=i,maxIndex=i; for(j = i+1; j < n - i + 2; j++)

{

if(A[minIndex] > A[j]) minIndex = j; if(A[maxIndex] < A[j]) maxIndex = j; } //交换值 int temp = A[i]; A[i] = A[minIndex]; A[minIndex] = temp; temp = A[n-i+1]; A[n-i+1] = A[maxIndex]; A[maxIndex] = temp; } }

五、填空题

1 break a/q

2 a[1]>=a[0]，FUNC2(a,n-1)，这是一个简单的题目，但算法写的太烂了，可以改进 3 a[i][i] a[i][N-1-i] 4 i>0 n%10+’0’ 5 ch=ch-30 ch=ch-26

6 s[i] t++ 7 strlen(p)-1 p10 argv[1]，”rb” argv[2]，”wb”

六、简答题

1 （1）参数传递（2）return语句（3）全局变量 2 与整数进行加减，指针相减，比较

3 （1）所有成员共享同一块存储空间，占用空间为占用空间最大的，（2）同一时间只有一个（3）在定义的时候不能初始化

4 包含头文件，定义文件指针，打开文件，进行读写操作，关闭文件

七、程序设计题

#include

int main(int argc,char *argv[]) {

int n = 100; int a[100]; int i; //输入数组 for(i = 0; i < n; i++)

scanf(\"%d\ //寻找最小的元素 int min = 0; int*p = a;

for(i = 0; i < n; i++) if(*(p+min)>*(p+i)) min = i; //删除最小的元素 for(i = min; i < n - 1; i++) *(p+i) = *(p+i+1); n--; return 0; }

八、程序设计题

char*maxword(char*s,char*t) {

char*p,*q; p = s,q = t; int maxlen = 0; int maxbegin = -1; int i,j,k;

int sword[80]={0}; int tword[80]={0}; int swordlen[80]; int twordlen[80]; int snum = 0,tnum = 0; for(i = 0; p[i]; i++) {

if(p[i] == ' ') {

sword[++snum] = i + 1;

swordlen[snum-1] = sword[snum] - sword[snum-1] - 1; } }

swordlen[snum] = i - sword[snum]; snum++;

for(i = 0; q[i]; i++) {

if(q[i] == ' ') {

tword[++tnum] = i + 1;

twordlen[tnum-1] = tword[tnum] - tword[tnum-1] - 1;

} }

twordlen[tnum] = i -tword[tnum]; tnum++;

for(i = 0; i < snum; i++) printf(\"%d \ printf(\"\\n\");

for(i = 0; i < snum; i++) printf(\"%d \ for(i = 0;i < snum; i++) for(j = 0; j < tnum; j++) {

if(swordlen[i] == twordlen[j] && maxlen < swordlen[i]) {

for(k = 0; k < swordlen[i]; k++) {

if(p[sword[i]+k] != q[tword[j]+k]) break; }

if(k == swordlen[i]) {

maxlen = k;

maxbegin = sword[i]; } } }

printf(\"begin:%s,%d\}