2014年江西师范大学数据结构与程序设计考研真题.doc

发布时间：2023-11-16 发布人：admin 分类：说明书资料大小：0.26M 资料格式：doc 举报版权申诉

第1页 / 共5页

2014年江西师范大学数据结构与程序设计考研真题.doc.pdf-第2页.jpg

第2页 / 共5页

2014年江西师范大学数据结构与程序设计考研真题.doc.pdf-第3页.jpg

第3页 / 共5页

2014年江西师范大学数据结构与程序设计考研真题.doc.pdf-第4页.jpg

第4页 / 共5页

2014年江西师范大学数据结构与程序设计考研真题.doc.pdf-第5页.jpg

第5页 / 共5页

文本预览

2014 年江西师范大学数据结构与程序设计考研真题一、单项选择题(每小题 2 分，共 20 分) 1. 在一个长度为 n 的顺序表中删除第 i 个元素(1<=i<=n)时，需向前移动（）个元素。 A. n-i B.n i+1 C.n-i- 1 D.i 2. 已知循环队列的存储空间为数组 data[21],且当前队列的头指针和尾指针的值分别为 8 和 3,则该队列的当前长度为（）。 A.5 B.6 C.16 D.17 3. 在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（）。 A.队列 B .栈 C.线性表 D. 有序表 4. 一棵含 18 个结点的二叉树的高度至少为（）。 A.3 B.4 C.5 D.6 5. 非空的循环单链表 head 的尾结点(由 p 所指向)满足（）。 A. p->next==NULL B.p->next==head C.p=NULL D.p=head 6. 无向图 G=(V,E), 其中： V={a,b,c,d,e;f},E={(a,b),(a,e),(a,c),(b,e),(c,f), (f,d),(e,d)},对该图进行深度优先遍历，得到的顶点序列正确的是（）。 A.a,b,e,c,d,f B.a,c,f,e,b,d C.a,e,d,f,c,b D.a,e,b,c,f,d 7. 对于哈希函数 H(key)=key%13,被称为同义词的关键字是（）。 A . 3 5 和 4 1 B .25 和 51 C .2 3 和 3 9 D .15 和 44 8. 下列说法错误的是（）。 A.冒泡排序在数据有序的情况下具有最少的比较次数。

B.直接插入排序在数据有序的情况下具有最少的比较次数。 C.二路归并排序需要借助 0(n)的存储空间。 D.基数排序适合于实型数据的排序。 9. 如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为（）。 A.插入排序 B.归并排序 C.冒泡排序 D.堆排序 10. 设二叉排序树中关键字由 1 至 1000 的整数构成，现要检索关键字为 363 的结点，下述关键字序列哪一个不可能是二叉排序树上搜索到的序列（）。 A.2, 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,363 二、填空题(每小题 2 分，共 20 分) 1. 若一个算法中的语句频度之和为 T(n)=10n+2nlogzn,则算法的时间复杂度为（） 2. 如果入栈序列是 1,3,5, … ,97,99,且出栈序列的第一个元素为 99,则出栈序列中第 30 个元素为（） 3. 某二叉树的先根遍历序列为 ABDC,中根遍历序列为 BDAC,则该二叉树根结点的右孩子是（） 4. 若对序列(15,2,48,60,89,25)采用二路归并法升序排序，则进行一趟归并后产生的序列为（） 5. 算术表达式 a*(b+c)-d 的对应的后缀表达式是（） 6. 假设一个 6 阶的下三角矩阵 B 按列优先顺序压缩存储在一维数组 A 中，其中 A[0]存储矩阵的第一个元素 bu,则 A[14]存储的元素是（） 7. 顺序循环队列中(数组的大小为 n),队头指示 front 指向队列的第 1 个元素，队尾指示 rear 指向队列最后元素的后 1 个位置，则循环队列中存放了 n-1 个元素，即循环队列满的条件为（） 8. 在含 100 个结点的完全二叉树中，叶子结点的个数为（） 9.包含有 n 个顶点的有向强连通图最多（）条边。 10. 如下图所示的有向无环图可以排出（）种不同的拓扑序列。三、程序填空与程序分析题(每小题 6 分，共 24 分) 1. 阅读下面的递归程序，写出程序的运行结果。 #include int fun(int n) {int i; if(n>=1) {fun(n- 1);

for(i=1;i<=2*n- 1;i++) printf("*"); printf("\n"); int main（） { fun(6); } 2. 二叉树存储结构定义为： typedef int datatype; typedef struct node {datatype data; struct node *lchild,*rchild; } bintnode; typedef bintnode *bintree; 阅读算法 fun（）。 void fun( bintree *t) {bintree temp; if(*t==NULL)return; else if((*t)->lchild==NULL&&(*t)>rchild==NULL)) else{temp=(*t)->lchild; return; (*t)->lchild=(*t)->rchild; (*t)->rchild=temp; fun(&(*t)->lchild); fun(&(*t)->rchild); } } (1)说明算法 fun（）的功能； (2)画出算法执行于上图所示的二叉树 t 后所得的二叉树。 3. 带头结点的单链表存储结构定义如下： typedef intdatatype; typedefstructnode {datatypedata; struct node*next; }linknode; typedef linknode*linklist; 函数 max（）的功能是在带头结点的单链表 head 中找最大值所在的位置作为函数的返回结果，请将程序补充完整。 linklistmax(linklisthead) { linklistpmax,p;//pmax 用于记录最大数结点所在的位置 pmax=head->next; (1) while(p) {if(p->data>pmax->data)

(2) (3) return pmax; 4.函数 vid insertsort(int a[],int n)采用直接插入法对长度为 n 的整型数组进行升序排序，请在横线上填上适当的语句。 voidinsertsort(inta[],intn) {inti,j,x; or(i[n;;i++) j=. (4); while(j>=0&&a[jl>x) a[j+{1]=a[j]; (5) (6)=X; 四、解答题(每小题 10 分，共 40 分) 1. 已知一棵二叉树如下图所示，试求： (1)写出该二叉树前序、中序和后序遍历的结果； (2)试对该二叉树进行中序线索化。 2. 设散列函数 H(key)=key mod 6,给定键值序列为 11、23、15、34、16、13、24、37、 29、56,采用拉链法解决冲突，试画出相应的开散列表，并计算在等概率情况下查找成功时的平均查找长度。 3. 对数据{12、3、4、56、7、9、5、13、21、38}应用堆排序算法，画出建立小根堆(最小堆)的过程。 4. 下图是一个无向网络及其邻接表表示。其中结点用自然数表示，邻接表中的边结点存储有边上的权值。请解答如下问题： (1)写出从结点 0 出发深度优先遍历序列； (2)画出从 0 结点出发用 Prim 方法建立最小生成树的过程图示。

五、算法与程序设计题(第 1、2 题每小题 14 分，第 3 小题 18 分，共 46 分) 答题要求：根据设计思想和实现步骤，采用 C 语言写出对应的算法程序，关键之处请给出注释， 1. 设计算法 linklist delodd(linklist head),删除带头结点的单链表 head 中所有值为奇数值的结点，函数返回链表头结点地址。 2. 设计算法 int binSearch(int a[,int left,int right,int x),采用二分查找算法在按升序排列的整型数组段 a[left.right]中查找值为 x 的数据位置，若查找成功，则返回该数所在的位置，否则返回-1。 3. 定义二叉排序树存储结构，并设计算法程序，根据键盘输入数据序列建立一棵二叉排序树。

分享到：

赞收藏

资料库

2014年江西师范大学数据结构与程序设计考研真题.doc

相关推荐

考研

热门标签

最新资料