2003年上海华东师范大学数据结构考研真题.doc

发布时间：2022-09-19 发布人：admin 分类：说明书资料大小：0.93M 资料格式：doc 举报版权申诉

第1页 / 共6页

第2页 / 共6页

第3页 / 共6页

第4页 / 共6页

第5页 / 共6页

第6页 / 共6页

文本预览

2003 年上海华东师范大学数据结构考研真题第一部分 C 语言程序设计一.回答下列问题（本题共 10 分，每小题 5 分） 1.设有下面的变量定义∶ int v[4][6],*p[4],**q; int j; 且设已执行了下面的语句∶ for(j=0;j<4;++j)p[j]=v[j];q = p; 请分别指出下面的每个语句使哪个变量的值增加了 1∶ (1)(*p[3])++; (2)q[3][0]++; (3)p[3][0]++: 1 2.设有数组变量 d 的定义如下∶ int d[16][8]; 数组 d 可以被看成是一个 16 行 8 列的数表。现需要使用一个指针，例如 p，可以在程序执行期间指向该数表中的一行，并且可以通过对指针 p 的运算，例如++p，使其指向数表的下一行。你认为下面三种关于变量 p 定义，哪一种是正确的?简述其理由。 (1) int **p::((2) int(*p)[8];(3)int *p[8]; 二、按要求指出下面的程序或程序段的输出内容（本题共 20 分，每小题 10 分） 1.设有函数 f 的定义如下∶ 设数组变量 s 前 3 个元素的值依次为 16、24、8。请指出语句 printf("f=%n", f(s,3)); 执行时的输出 2.设有函数 f 和 g 的定义如下∶

且假定 int 类型的数组变量 v 中的 8 个数据依次为∶ 1 3 7 6 5 7 8 9 请指出语句 f（v，8，0）;执行时的输出。三.按要求写出下面的函数定义（本题共 30 分，每小题 15 分） 1.按下面的要求写函数定义∶ 2. 按下面的要求写函数定义∶

返回值∶ 1 正常终止; 0 异常终止（矩阵内不存在这样的 3 阶子方阵）。例第二部分数据结构一.多重选择填空题（每小题 4 分，共 28 分。每道小题都可能有一个以上的正确选项，须选出所有的正确选项，不答不得分，多选、少选或选错都将按比例扣分。请将答案写在答题纸上。） 1.链表不具有的特点是（）。（A）可随机访问任一个元素（B）插入和删除时不需要移动元素（C）不必事先估计存储空间（D）所需空间与线性表的长度成正比 2.假设有 10 个关键字，它们具有相同的 Hash 函数值，用线性探测法把这 10 个关键字存入 Hash 地址空间中至少要做（）次探测。 (A)110 (B)100

(C)55 (D)45 3. 某二叉树的前序序列和中序序列正好相反，则该二叉树一定具有（）的特征。（A）二叉树为空或只有一个结点（B）若二叉树不为空，则任一结点不能同时拥有左孩子和右孩子（C）若二叉树不为空，则任一结点没有左孩子（D）若二叉树不为空，则任一结点没有右孩子 4.在有 n 个叶子结点的哈夫曼树中，其结点总数为（）。 (A)n (B)2n (C)2n+1 (D)2n-1 5.下列排序算法中，（）算法可能会出现下面情况∶初始数据有序时，花费时间反而最多。（A）堆排序（B）冒泡排序（C）快速排序（D）希尔排序 6.具有 2000 个节点的二叉树，其高度至少为（）。（注∶空的二叉树的高度为-1，非空 \ 的二叉树的高度为其左、右子树的高度的较大者加 1） (A)9 (B)10 (C)11 (D)12 (E)13 7. 一棵二叉树如下图，该树是（）。

（A）平衡树（B）查找树（C）堆（D）以上都不是二. 应用题（每小题 8 分，共 24 分） 1.对如（图 1）所示的图，写出其邻接矩阵。画出用 Kruskal 算法构造其最小生成树的每步结果（只要求用图表示即可）。 2.对一组关键字∶26，5，37，1，62，11，59，15 采用快速排序方法进行排序，用第一关键字作分划元素，请写出每趟划分的结果。 3.在 C 语言中用数组 Q[n]以顺序存储的方法实现环形队列，头指针为 f，指向队列的头结点所在的位置，尾指针为 r，指向队列的尾结点后面的一个位置，请给出计算队列中的元素个数、判端队列是否为空的和判端队列是否为满的方法，画出你的方案的示意图。三. 算法设计题

1.设在一个整数数组中存储了一个堆，请编写一 C 函数，将一个新的元素插入此堆，要求算法的时间复杂性和空间复杂性最小，请给出你的算法的时间复杂性和空间复杂性。（14 分） 2.设有以标准形式存储的二叉树 T，请编写两个 C 函数，分别计算 T 的高度和宽度。（注∶ 空的二叉树的高度为-1，非空的二叉树的高度为其左、右了树的高度的较大者加 1;空的一叉树的宽度为 0，对一棵非空的二叉树各层所包含的结点个数分别进行计数，其中的最大者即为此非空的二叉树的宽度）。（8 分+16 分）

分享到：

赞收藏

资料库

2003年上海华东师范大学数据结构考研真题.doc

相关推荐

考研

热门标签

最新资料