《华东师范大学-839-2009-真题》由会员分享，可在线阅读，更多相关《华东师范大学-839-2009-真题（4页珍藏版）》请在金锄头文库上搜索。
1、华东师范大学 2009 年攻读硕士学位研究生入学试题 共 4 页 考试科目代码及名称： 839 数据结构（含 C 语言程序设计） 招生专业： 系统科学（包括系统理论、系统分析与集成） 考生注意：无论以下试题中是否有答题位置，均应将答案做在考场另发的答题纸上（写明题号） 。 第一部分第一部分 C C 语言程序设计（共语言程序设计（共 7070 分分) ) 一. 回答问题（本大题共 2 小题，每小题 5 分，共 10 分） 1. 在标准库的头文件 stdio.h 中#ifndef/#define/#endif 起什么作用？ 2. 在标准库的头文件 string.h 中 strcpy 的函数原型为：
2、 char* strcpy(char *, const char *); 其中的关键字 const 的意义是什么？ 二. 阅读分析程序并写出程序运行结果（10 分） #include #include #include #define LEN 81 #define N 10 int compare1(const void* a,const void* b) return strlen(*(char(*)LEN)b) - strlen(*(char(*)LEN)a); int compare2(const void* a,const void* b) return strcmp(*(char(*
3、)LEN)a,*(char(*)LEN)b); int main(int argc,char *argv) FILE* fp=fopen(argv1,r); char sNLEN; int i,cnt=0; while (fscanf(fp,%s,scnt)=1) printf(%s ,scnt+); printf(n); qsort(s,cnt,sizeof(charLEN),compare1); /*快速排序标准库函数*/ for (i=0;icnt;i+) printf(%s ,si); printf(n); qsort(s,cnt,sizeof(charLEN),compare2);
4、for (i=0;icnt;i+) printf(%s ,si); printf(n); return 0; 程序运行的命令行为：执行程序名 languages 文件 languages 中含一行信息：BASIC FORTRAN C C+ JAVA C# PERL PASCAL 三. 按要求写函数定义（本大题共 2 小题，每小题 10 分，共 20 分) 1. 用递归方法定义一个不用数组就能将给定十进制自然数以二进制形式输出的函数 natural2binary。 2. 定义一个函数计算两个矩阵的和。函数原型： void matrixAdd(int* a, int* b, int* c, int
5、 row, int col); 矩阵均有 row 行和 col 列，函数将矩阵 a 及矩阵 b 的和放在矩阵 c 中。 第 1 页 各个学校计算机/软件专业考研真题 免费分享 h t t p s :/g i t h u b .co m /cs s e k y /cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研 四. 按要求写程序（本大题共 2 小题，每小题 15 分，共 30 分） 1. 写一个程序，以十六进制形式显示一个文件（可以是文本文件，也可以是二进制文件）中的每个字节的值。文件名由命令行参数给定。每行显示分成
6、三栏：第一栏以 8 位十六进制形式显示与文件头的偏移量，第二栏以 2 位十六进制形式显示 16 个字节值，第三栏显示各字节对应的 ACSII 字符（不可显示字符用.表示)。 以下是显示一个文件的例子： 00000000 00 01 02 03 04 05 06 07 08 09 0a 0b Oc Od Oe Of . 00000010 10 11 12 13 14 15 16 17 18 19 1a 1b 1c 1d 1e 1f . 00000020 20 21 22 23 24 25 26 27 28 29 2a 2b 2c 2d 2e 2f !#$%&()*+,-./ 00000030 3
7、0 31 32 33 34 35 36 37 38 39 3a 3b 3c 3d 3e 3f 0123456789:;? 00000040 40 41 42 43 44 45 46 47 48 49 4a 4b 4c 4d 4e 4f ABC0EFGHIJKLMN0 00000050 50 51 52 53 54 55 56 57 58 59 5a 5b 5c 5d 5e 5f PQRSTUVWXYZ_ 00000060 60 61 62 63 64 65 66 67 68 69 6a 6b 6c 6d 6e 6f abcdefghijklmno 00000070 70 71 72 73 74
8、 75 76 77 78 79 7a 7b 7c 7d 7e 7f pqrstuvwxyz|. 00000080 80 81 82 83 84 85 86 87 88 89 8a 8b 8c 8d 8e 8f . 00000090 90 91 92 93 94 95 96 97 98 99 9a 9b 9c 9d 9e 9f . OOOOOOaO aO al a2 a3 a4 a5 a6 a7 a8 a9 aa ab ac ad ae af . OOOOOObO bO bl b2 b3 b4 b5 b6 b7 b8 b9 ba bb be bd be bf . 000000c0 cO cl c
9、2 c3 c4 c5 c6 c7 c8 c9 ca cb cc cd ce cf . OOOOOOdO d0 dl d2 d3 d4 d5 d6 d7 d8 d9 da db dc dd de df . OOOOOOeO eO el e2 e3 e4 e5 e6 e7 e8 e9 ea eb ec ed ee ef . 000000f0 fO fl f2 f3 f4 f5 f6 f7 f8 f9 fa fb fc fd fe ff . 00000100 00 01 02 03 04 05 06 07 08 09 0a 0b 0c Od Oe Of . 00000110 10 11 12 13
10、14 15 16 17 18 19 1a 1b 1c 1d 1e 1f . 00000120 20 21 22 23 24 25 26 27 28 29 2a 2b !#$%&()*+ 2. 次考试由 10 道是非题构成。答对一题得 1 分，答错得 0 分。有三名考生 A、B、C 的答卷如下： 题号 1 2 3 4 5 6 7 8 9 10 A 考生 F T T T F T F F T F B 考生 F F T T T F T T F F C 考生 T F T F T T T F T T 阅卷结果是这三名考生的成绩均为 7 分，但在几天后正确答案丢失了。 写一个程序，显示出这 10 道是非题的
11、正确答案。 第二部分第二部分 数据结构部分（共数据结构部分（共 8080 分分） 一. 在一个表长为 5 的双向链表中，p 所指的结点不是头结点，请写出插入 q 所指的结点使其成为 p 所指的结点的直接前趋结点的主要语句序列。（10 分） 二. 设 P 为一个长度为 n 的字符串， 其中的字符各不相同， 请简要分析出 P 中互不相等的子串的总个数。（10 分） 第 2 页 各个学校计算机/软件专业考研真题 免费分享 h t t p s :/g i t h u b .co m /cs s e k y /cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考
12、研 微信公众号 计算机与软件考研 三. 己知 n 个数顺序存储于一维数组 a 中，填空完成下面的冒泡排序函数（每空 2 分，共12 分）。 void bubble_sort(a,n) int a; int n; int i,j; int t; n ; while(n 0) j= ; for(i=0;irtag |t-rchild=NULL) return (t-rchild); t=t- ; while(t-ltag ) t=t- ; return (t); 五. （1）请简要分析出具有 12 个结点的平衡查找树 T 的最大高度是多少？（6 分） （2）画出一棵这棵的平衡查找树 T。（4 分）
13、 （3）求出在等概率情况下对 T 进行成功查找时的平均查找长度。（4 分） 第 3 页 各个学校计算机/软件专业考研真题 免费分享 h t t p s :/g i t h u b .co m /cs s e k y /cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研六. 请写出用 Floyd 算法求下面这个有向图中各对顶点之间最短路径的整个过程。（12分）七. 己知一棵二叉树 T 按标准形式存储（指向树根的指针为 t)，T 中各结点值互不相同，T 中有值为 x 和 y 和 z 的 3 个结点， 写函数判断值为 x 的结点是否为值为 y 和 z 的结点的共同祖先。（答题时，请先简要写出所写函数的算法思想，然后写函数)。（14 分）第 4 页 4 3 1 1 2 5 1 4 2 3 各个学校计算机/软件专业考研真题 免费分享 h t t p s :/g i t h u b .co m /cs s e k y /cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研
