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

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

第1页 / 共4页

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

第2页 / 共4页

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

第3页 / 共4页

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

第4页 / 共4页

文本预览

2017 年江西师范大学数据结构与程序设计考研真题一、单项选择题(每小题 2 分，共 20 分) 1.顺序存储表示中数据元素之间的逻辑关系是由( )表示的。 A. 指针 B. 逻辑顺序 C.存储位置 D. 问题的上下文 2. 将长度为 n 的单链表链接在长度为 m 的单链表之后的算法的时间复杂度为()。 A.0(1) B.0(n) C.0(m) D.0(m+n) 3. 在单链表中，指针 p 指向元素为 x 的结点，实现“删除 x 的后继”的语句是() 。 A. p=p->next; B.p->next=p->next->next; C. p->next=p; D.p=p->next->next; 4. 若进栈序列为 1,2,3,4,5,6,且进栈和出栈可以穿插进行，则不可能出现的出栈序列是 ()。 A.2,4,3,1,5,6 B.2,3,5,1,6,4 C.4,3,2,1,5,6 D.3,2,4,1,6,5 5. 对于一颗具有 n 个结点的树，该树中所有结点的度数之和为( )。 A. n- 1 B.n+1 C.n D.2n 6.按照二叉树的定义，具有 3 个结点的二叉树有()不同的形态。 A.6 B.5 C.4 D.3 7. 如果在排序过程中，每次均将一个待排序的记录按关键宇大小加入到前面已经有序的子表中的适当位置，则该排序方法称为( )。 A.插入排序 B . 归并排序 C.冒泡排序 D.堆排序 8. 对于哈希函数 H(key)=key%13,被称为同义词的关键字是()。 A . 35 和 41

B . 23 和 39 C . 15 和 44 D .25 和 51 9. 若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为() A. 顺序存储结构 B.链式存储结构 C . 索引存储结构 D .散列存储结构 10.有 n 个顶点的无向连通图最少有()条边。 A.2n B.n+1 C.n D.n- 1 二、填空题(每小题 2 分，共 20 分) 1.数据的逻辑结构包括线性结构、（） 2. 顺序循环队列中(数组大小为 6),队首指示 front 和队尾指示 rear 的值分别为 3 和 0,当从队列中删除 1 个元素，再插入 2 个元素后，front 和 rear 的值分别为（）和（） 3.表达式 a*(b+c*b)-d 的后缀表达式是（）。 4.在一个单链表中，若 p 所指结点不是最后结点，在 p 之后插入 s 所指结点，则执行的语句是（） 5.具有 33 个结点的完全二叉树的高度为（）, 有（）个叶结点。 6.若从键盘输入 n 个元素，则建立一个有序单向链表的时间复杂度为（）。 7.如下图所示的有向无环图可以排出（）种不同的拓扑序列。 D C F A B 8.表示一个有 50 个顶点，50 条边的有向图的邻接矩阵有（）个非零元素。 9.要解决散列引起的哈希冲突问题，常用的 3 种方法是；开放定址法，（） 10. 在关键字序列(12,23,34,45,56,67,78,89,91)中二分查找关键字为 45 的结点时，所需进行的比较次数为（）三、程序填空与程序分析题(每小题 6 分，共 24 分) 1.设单链表的存储定义如下： typedef int datatype; typedef struct linknode{ datatypeinfo; struct linknode *next; }node; typedef node * linklist; 已知用有序链表存储整数集合的元素。阅读算法 funl, 并回答程序后的问题： int funl(linklist ha,linklist hb) {/* linklist 是带有头结点的单链表，ha 和 hb 分别为指向存储两个有序整数集合的链表

的头指针 */ linklist pa=ha->next,pb=hb->next ; while(pa&&pb&&pa->info==pb->info) {pa=pa->next; pb=pb->nēxt; } if(pa==NULL && pb==NULL)return 1;else return 0; (1)写出执行 fun1(a,b)的返回值，其中 a 和 b 分别为指向存储集合{2,4,5,7,9, 12}和 {2,4,5,7,9}的链表的头指针； (2)简述算法 fun1 的功能。 2.阅读如下程序代码，并回答程序后的问题： #define MAXSIZE100 typedef int datatype; typedef struct{ datatype a[MAXSIZE]; int size; }sequencelist; Voidfun2(sequencelist*L){ datatypet; int i; for(i=0;isize/2;i++) { t=L->a[i]; L->a[i]=L->a[L->size- 1-i]; L->a[L->size- 1-i]=t; (1)若顺序表 L 的数据值为{2,4,5,7,9,12},求执行 fun2(&L)以后，顺序表 L 的数据值。 (2)简述算法 fun2 的功能。 3. 设二叉树的存储定义如下： typedef char datatype;/*结点属性值的类型*/ typedef struct node{/*二叉树结点的类型*/ datatypedata; struct node *lchild,*rchild; } bintnode; typedef bintnode *bintree; bintreeroot; 函数 change 的功能是将一棵给定二叉树中所有结点的左、右子女互换。请将程序空白处补充完整。 void change(bintree t) {bintreep; if( ①) {p=t->lchild; t->1child=t->rchild; t->rchild=p; ② ③ 4.设顺序表的存储定义同第三大题第 2 小题。函数 binsearch1 的功能是采用非递归二分查找算法，查找元素值为 key 在有序表 L 中的位

置，并将查找结果作为函数值返回，若查找失败则返回-1。请将程序空白处补充完整。 int binsearch1(sequencelist L,datatype key) {int low=0,high=L.size- 1,mid; while(①){ mid=(low+high)/2; if(L.a[mid]==key)return mid; if(L.a[mid]>key)high=mid- 1; else low=mid+1; 四、解答题(每小题 10 分，共 40 分) 1. 已知二叉树的前序序列和中序序列分别为 HDACBGFE 和 ADCBHFEG。 (1)画出该二叉树； (2)画出与(1)求得的二叉树对应的森林。 2. 已知一个无向图的顶点集为{A,B,C,D,E},其邻接矩阵如下所示： 3. 设待排序的 7 个记录的排序码序列为{ 27,12,45,6,18,51,32},画出使用二路归并排序算法进行排序的状态变化过程。 4. 从空树起，依次插入关键字 40,8,90,15,62,95,12,23,56,构造一棵二叉排序树。 (1)画出该二叉排序树 (2)画出删去该树中元素值为 90 的结点之后的二叉排序树。五、算法与程序设计题(第 1、2 题每小题 14 分，第 3 小题 18 分，共 46 分) 答题要求： ①用自然语言说明所采用算法的思想； ②用 C 语言(或其他程序设计语言)写出对应的算法程序，并加上必要的注释。 1、设单链表的存储定义同第三大题第 1 小题。设计一个算法，判断一个不带头结点的单链表中各个结点值是否有序。 2、设二叉树的存储定义同第三大题第 3 小题。设计一个函数返回一棵给定二叉树中叶子结点的个数。 3、设中序穿线二叉树在链接方式下的数据类型定义： typedef char datatype; typedefstruct node { datatypedata; int ltag,rtag; struct node *lchild,*rchild; } binthrnode; typedefbinthrnode *binthrtree; 设计一个算法输出中序穿线二叉树进行中序遍历下的所有结点。

分享到：

赞收藏

资料库

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

相关推荐

考研

热门标签

最新资料