北航数据结构与程序设计真题14年真题及答案.doc

一、1. P=rear-link-link;rear-link-link=p-link;free(p); 2. 两个栈顶相遇 3. 95 4. 后序 5. 连通图 6. f,c,b 7. 每个分支结点最多有m棵子树 8. n(n-1)/2 9.插入排序法 10. an,deng,shi,bai,fang,liu,tang,wang 二、1. 有穷性、确定性、可行性、输入、输出 (1) (2) (3) (4) 顺 O(1) O(1) O(n) O(n) 链 O(n) O(1) O(n) O(n) 3. 2^(n-1) 链地址 三、1. 321 231 213 123 132 3. 11 4. 可以（08年 一4） 四 void DEGREE(VLink G[], int n) { int num,i; VLink v; ELink *p; for(i=0; in; i++){ v=G[i]; num=0; p=v.link; while(p!=NULL){ num++; p=p-next; } G[i].degree=num; } } 五、1-5 DACCA 6-10 BDCAB 六、1. 不正确，因为数组名a代表数组首元素的地址，它是一个指针常量，它的值在程序运行期间是不变的 2. sizeof是算符，strlen是函数；strlen是返回字符串的长度，而sizeof却是用来取得变量所占用的内存；返回的单位不一样 3. s1必须定义得足够大，以便容纳被复制的字符串s2，s1的长度不应小于s2的长度 4. 函数指针是一个指向某函数起始地址的指针；指针函数是带指针的函数，返回类型是某一类型的指针 5. 返回地址信息、实参信息 七、1. a[k-1] a[9-k] 2. k%j==0 continue Substr[k+1]==’\0’ i+1 4. *p==*q *olds++ *new=’\0’ fopen(“file.dat”, “r”) fp, “%d”, num i==count #includestdio.h #includestring.h main() { int STRCOUNT(char *str, char *substr); char str[80], substr[80]; int num; printf(“Input sring:”); gets(str); printf(“Input substring:”); gets(substr); num=STRCOUNT(str, substr); printf(“num = %d”, num); } int STRCOUNT(char *str, char *substr) //根据第七大题4改写的 { char *p, *q; int num=0; while(*str!=’\0’){ for(p=str, q=substr; *p!=’\0’*q!=’\0’*p==*q; p++, q++); if(*q!=’\0’) *str++; else{ num++; str=p; } } return num; } By Jason Lee Roc° 卡卡