1、第 1 页，共 6 页江西师范大学硕士研究生入学考试试题（样卷）专业: 081200 计算机科学与技术 科目： 数据结构与程序设计 注：考生答题时，请写在考点下发的答题纸上，写在本试题纸或其它答题纸上的一律无效！（本试题共计 页）一、选择题（每小题 2 分，共 20 分）1、 若语句 S 的执行时间为 O（1） ，那么下列程序段的时间复杂度为：（ ）for（i=0; inext=p; p-next=s; （B ）p-next=s; s-next=p;（C）s-next=p-next; p=s; （D ）s-next=p-next; p-next=s;3、设高度为 h 的二叉树上只有度为 0 和
2、度为 2 的结点，则此类二叉树中所包含的结点数至少为（ ） （注：只含有一个根结点的树高为 1）（A） 2h （B） 2h-1 （C） 2h+1 （D） h+14、一组记录的关键码为（ 46，79，56，38，40，84） ，则利用堆排序的方法建立的初始堆为（ ） 。（A）84，79，56，38，40， 46 （B）79，46，56，38，40，80 （C）84，79，56，46，40， 38 （D）84，56，79，40，46，385、设二叉排序树中关键字由 1 至 1000 的整数构成，现要检索关键字为 363 的结点，下述关键字序列哪一个不可能是二叉排序树上搜索到的序列（ ） 。（A）2
3、， 252， 401， 398， 330， 344， 397， 363（B）924， 220， 911， 244， 898， 258， 362， 363（C）952， 202， 911， 240， 912， 245， 363（D）2， 399， 387， 219， 266， 382， 381， 278， 3636、已知某完全二叉树采用顺序存储结构，结点数据信息 A、B、C、D、E、F、G、H，顺序存放在数组的前 8 个单元，则该完全二叉树的后序遍历序列为（ ） 。（A）HDEBFGCA （B）HEDBFGCA （C ）HDEBAFGC （D）HDEFGBCA7、稀疏矩阵一般的压缩存储方法有（
4、）两种。（A）二维数组和三维数组 （B）三元组和散列表（C）三元组和十字链表 （D）散列表和十字链表8、下列哪棵树不是 AVL 树（ ） 。（A） （ B） （C） （D）第 2 页，共 6 页9、设有一个有向图如图 1 所示，请指出下列哪个序列不是该图的拓扑排序序列（ ） 。（A）EAFBGDC （B）AEBCGFD （C ）ABCGEFD （D）EABGFCD10、判断一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用（ ） 。（A）单源最短路 Dijkstra 算法 （B）所有顶点对最短路 Floyd 算法（C）广度优先遍历算法 （D）深度优先遍历算法二、填空题（每小题 2 分
5、，共 20 分）1、数据的存储结构一般分为顺序存储、链式存储、 和 四种方式。2、中缀表达式 (A + B) * D + E / (F + A * D) + C 对应的后缀表达式是 。3、KMP 算法是解决模式匹配的有效算法，设数组下标从 0 从始，则模式串“babbabbab”对应的 next值是 。4、一棵具有 46 个叶结点的完全二叉树，最多有 个结点。5、若 p 已指向了二叉树 t 的树根，则让 p 指向这棵二叉树的中序首点（中序遍历下的第一个结点）可以用以下的语句实现： 。6、编号为 1，2，3，4 的四列火车通过一个栈式的列车调度站，可能得到的调度结果有 种。7、排序方法采用的是二
6、分法的思想，排序方法其数据结构的组织采用的是完全二叉树结构。8、若函数 int max（int a，int n）用于求长度为 n（n0）的整型组 a 中的最大值，其递归定义可以表示为： 。9、若一棵度为 7 的树有 8 个度为 1 的结点，有 7 个度为 2 的结点，有 6 个度为 3 的结点，有 5 个度为 4 的结点，有 4 个度为 5 的结点，有 3 个度为 6 的结点，有 2 个度为 7 的结点，该树一共有_个叶结点。10、散列函数 以为自变量，函数值作为结点的 。三、程序填空与程序分析题（每小题 6 分，共 24 分）1、函数 frequency（）的功能统计字符串 s 中各个不同字
7、符出现的频度，数组 a 记录 s 中不同的字符，数组 c 中记录每一种字符的出现次数，k 返回不同字符的总数，请将程序补充完整。void frequency(char s,char a,int c,int *k) int i,j,len=strlen(s);if ( !len ) /*原字符串为空*/图 1第 3 页，共 6 页 printf(“The string is empty.n “); *k = 0;return;else /*原字符串不为空*/ a0 = s0; c0 = 1; *k = 1; /*处理第一个字符*/for ( i = 1; i next;while (p) pre
8、=p;s=p-next;while (s!=NULL)while (s 第 4 页，共 6 页if (s!=NULL) /*找到了与 p 相同的结点 s*/ pre-next=s-next; p=p-next;return head;3、二叉排序树链式存储结构定义如下：typedef int datatype;typedef struct node datatype key; /*结点值*/struct node *lchild,*rchild; /*左、右孩子指针*/bsnode;typedef bsnode *bstree;函数 insertbstree（）的功能是在二叉排序树 t 中插入
9、一个新结点 x（若树中存在相同结点则不做插入操作） ，请将其补充完整。void insertbstree(bstree *t,datatype x) bstree f,p; while (p) /*查找插入位置*/ if (x=p-key) /* 若二叉排序树 t 中已有 key，则无需插入*/f=p; /* f 用于保存新结点的最终插入位置 */p=(xkey)? p=(bstree) malloc(sizeof(bsnode); /*生成待插入的新结点 */p-key=x; if (*t=NULL) /*原树为空*/elseif (xkey) else f-rchild=p;4、阅读下面的
10、递归程序，说明这个函数的功能是什么？如果数组的大小为 n，则该程序的时间复杂度是多少？设数组 a 的初始值是 21,30,52,35,69,70,90,61,78,99，则执行change1（a,0,9）后，数组 a 的内容是什么？void change1(int a,int low,int high) int i,j,t;第 5 页，共 6 页i=low;j=high;if (ij) while (ij while (ij if (i!=j)t=ai;ai=aj;aj=t;change1(a,i+1,j-1);四、解答题（每小题 10 分，共 40 分）1、 一棵前序序列为 1，2，3，4
11、的二叉树，其中序序列可能是 4，1，2，3 吗？设一棵二叉树的前序序列为 1，2，3，4，5，6，7，8，9，其中序序列为2，3，1，5，4，7，8，6，9，试画出该二叉树。2、 假定用于通信的电文仅由 8 个字母 c1， c2， c3， c4， c5， c6， c7， c8 组成， 各字母在电文中出现的频率分别为 5， 25， 3， 6， 10， 11， 36， 4。试构造哈夫曼树，并为这 8 个字母设计不等长 Huffman 编码。3、 顺序表的快速排序为何采用由外向内来回比较法，是否可以从同一个方向扫描？采用带头结点的单链表存储的线性表是否可以做快速排序？对初始序列（50，20，79，2
12、4，49，84，3，99，12）以 50 作为“枢轴”进行第一次划分后的结果是什么？4、 给定无向网如下图 2 所示，请采用 prim 算法用图示描述求解该图的最小生成树的过程。（初始入选点为 A，每选取一条边画一个图）第 6 页，共 6 页五、算法与程序设计题（第 1、2 题每小题 14 分，第 3 小题 18 分，共 46 分）答题要求：描述算法的基本设计思想；给出每个算法所需的数据结构定义；根据设计思想和实现步骤，采用用 C 语言写出对应的算法程序，关键之处请给出简要注释。1、设一带头结点的单链表的头指针为 head，链表的记录中包含着整数类型的 info 域，试采用直接插入法将此链表的记录按照 info 递增的次序进行就地排序。2、二叉树采用二叉链表存储结构，t 为其根结点，分别用递归与非递归方法编写函数，返回二叉树的前序尾点地址（前序遍历下的最后一个结点） 。3、AOV 网采用带入度域的邻接表存储结构如图 3 所示。请用 C 语言定义这种结构，编写程序建立一个有向图的这种存储结构（出边表） ，并输出图中入度为 0 的顶点。图 3图 2
